И.Д. Мандель - Кластерный анализ (1185344), страница 10
Текст из файла (страница 10)
На самом деле лишь немногие алгоритмы не опираются ни на какие параметры (и они имеют человеко-машинный характер). 3,2. Задано число классов. Популярный способ — «ограничения» свободной классификации. Если такой алгоритм проработает в целом спектре численностей классов, «естественный» результат может быть выделен после дополнительной обработки.
3.3. Заданы пороговые значения величины близости объектов (классов). Способов задания порогов очень много (см. 2.2; 2.3). Объединим их, чтобы противопоставить предыдущему параметру— числу классов. На самом деле существует связь между этими параметрами для каждого алгоритма, но в явном виде она не изучена. 3.4.
Заданы комбинированные сведения (число классов и пороги разных типов). Процедуры носят наиболее «ограниченный» характер, но умелое использование многих параметров может сделать алгоритм довольно реалистичным и гибким (42, 43 в 2.2 и др.). 4. Характер работы алгоритма классификации Алгоритмы можно классифицировать по принципу устройства, но единых способов здесь нет. Наиболее общие результаты получены В. М. Бухштабером и др. 1181, но эту теорию еще нельзя считать окончательно разработанной.
Мы ограничимся делением алгоритмов по способу построения кластеров: эталонные и неэталонные [5). В процедурах эталонного типа на множестве объектов задается несколько эталонов — исходных зон, полей, с которых начинает работу алгоритм. Эталоны могут быть следующих видов: подмножество исходного множества (т. е. первоначальное разбиение на классы); отдельные объекты; отдельные зоны (точки) метрического пространства (например, центр тяжести класса или область, в которой предполагается модальная плотность на основании предыдущих исследований).
После задания (машинного или человеко- машинного) эталонов алгоритм производит классификацию, иногда меняя эталоны определенным способом. Существует множество процедур кластеризации, работающих по иному принципу: иерархические алгоритмы, процедуры диагонализации, разрезания графов и др. Определим другую особенность алгоритмов — зависимость результатов работы от порядка просмотра точек. 4.1. Процедуры, зависящие от порядка просмотра точек. Зависимость от нумерации точек является серьезным недостатком алго- 41 ритма, иногда преодолеваемым последующими действиями. Зависимость типична для эталонных процедур.
4.2. Процедуры, не зависящие от' порядка просмотра точек, например иерархические алгоритмы. С прикладной точки зрения очень важно было бы иметь оценки временной и пространственной трудоемкости алгоритмов и соответственно провести по ним классификацию. Однако задача определения трудоемкости, сильно развитая в других областях математики, в теории автоматической классификации изучена слабо. Оценки известны для редких алгоритмов. Общая классификация процедур на быстрые и медленные, требующие бо)зьшой и малой памяти ЭВМ, видимо, заменила бы предлагавшееся деление на параллельные н последовательные процедуры [5); в некоторых случаях мы приводим оценки. Сделаем сводку типов кластер-процедур и введем'условные обозначения (см.
табл. 2.1). Каждый алгоритм можно задать кодом из 4 элементов в соответствии с таблицей. Так, описание РП, М, К, 3 означает алгоритм, отыскивающий разбиение, в котором возможны пересечения (но не обязательны). Этот алгоритм осуществляется без вмешательства человека, работает с заданным числом классов, зависит от порядка просмотра точек. Сопоставляя свои содержательные представления с «марками» алгоритмов, исследователь может подобрать соответствующие процедуры для каждой задачи. Рекомендации представлены в 4.2. 1.2.
АЛГОРИТМЫ ПРЯМОЙ КЛАССИФИКАЦИИ 2.1.1. развитие идей Множество алгоритмов прямой кластеризации практически неисчерпаемо, поскольку из отдельных фрагментов имеющихся процедур можно «собирать» новые схемы. Поэтому преследовалась цель дать общее представление об этих методах, выделив круг основных идей.
Изложение ведется по принципу: краткий обзор н основная библиография, сжатое и унифицированное описание алгоритмов, нх короткое содержательное обсуждение н выводы. Конечно, отбор материала являетсн в известной мере субъентивным; что касается исторической стороны вопроса, то автор не может претендовать иа полное и детальное ее изложение, возможно, отдельные этапы разработки н методология кластер-анализа в обзоре упущены.
Относительно ссылон принята следующая схема: если предложенный за рубежом алгоритм' опубликован в доступных отечественных изданиях, то ссылка делается на них, а не на оригинал. В некоторых случаях трудно строго назвать первые публикации, тогда приводятся фамилии авторов наиболее ранних работ с описанием данного алгоритма (эти замечания относятся и к 2.3). Некоторые из числа рассмотренных в обзоре алгоритмов описаны не детально по двум причинам: их точное изложение заняло бы слишком много места и потребовало бы новых обозначений, тогда как в соответствующей литературе вся эта работа проведена. Алгоритмы прямой кластеризации явились наиболее ранними процедурами кластерного анализа.
Метод решения задачи группировки по многим признакам (отличный от комбинационной) был предложен немецким биологом Ф. Гейнке [88). «Правило Гейнке» заключалось в том, что объект приписывается той группе, к центру кото- рой он ближе всего. Близость измерялась 42 величиной:з ~( и ы) и, г ! Т а 6 ли ц а 2.1. Основные тмны процедур кластерного аналнза' Типы алгоритмов Свойства алгоритмов № п/и слов ные обо»каче ния прямая класснфн- оптимизация — номер кацня — номер ал- ункционала по 2.3 горитма по 2.2 Характер результирующего отношения Разбиение 2! — 48, 50 — 58, 60, ! — 17, 19 — 23, 25 — 28, 61, 63 — 65 30 — 42, 44, 45 49, 59, 62, 67, 6818, 24, 29, 43, 46 РП 1.2 2 нз 2.2» 1 — 9), 66 1.3 2 2.1 21 — 24, 26, 28 — 32 1 — 20, 25, 27, 33 — ! — 46 ЧМ Внд задаваемых параметров Свободная классификация СК 3 3.! 1 — 9, 14 — 22, 24— 26, 28 — 31, 53, 55 39 — 41, 45, 54, 57, 58, 60, 66 Число классов 3.2 1О, 27, 36, 37, 42, 47, 49, 52, 56, 59, 63, 65, 67, 68 43, 46, 51, 64 Пороги любых видов П 3.3 !8, 21, 24 бгнк но КП 3.4 4 у ц палы могут оптимизироваться алгорнтмамн разных типов 4.! Зависит от порядна просмот- ра объектов 3 ' В составе нерархнческнх процедур есть алгоритмы с раэмытымн решеннямн (см.
алг. !0) я задаваемыми порогамн (см. алг. ! 1 — !3), что в таблнйе не отражено во избежание пересечений. * Метод ближнего соседа оптнмкзнрует походную матрицу расстояннй в смысле ультраметрикн (см. 2.3.1 — 2.3.4), но специально теорию оптнмальных иерархических процедур мы не рассматривали (см. (122)). где! — номер объекта, ! — признака, й — группы. Зто напоминает чрезвычайно распространенную процедуру распределения объектов па блнжайшнм классам (например, в методе й-средних).
Однако правило Гейнке все же трудно причислить к методам кластерного анализа, так как сами группы (бнологнческне анды) предполагались заданпымя. Идеи еструктурной класснфнкацин» была выдвинута польскнн антропологом К. Чекановскнм в 1913 г. (71). Его метод являет собой типичный пример домашннной технология обработкн данных (сн. табл, 2.3), но содержит в себе, во-первых, узловую идею кластер-анализа — выделение компактных групп объектов н, во. 43 Разбненне с пересекающи- мися нлн размытыми класса- мя Иерархическое дерево Участие человека в прове- дения классификации Человеко-машннная классн- фикацня Машинная нласснфнкацня Число «лаосов н пороги Тдчяйнностн работы алгоритма Йе зависит от порядка просмотра объектов 1 — 20, 26 — 32, 34, 50, 53 — 55, 60, 67, 68 21 — 25, 33, 35 — 49, 51, 52, 56 — 59, 61 — 66 8, 9, 20, 23, 25, 28, 30, 31, 40, 42, 44 2, 6, 7, 11 — 14„16, 17, 19, 26, 27, 29, 32 — 35, 39, 41, 43 — 46 22, 31, 34 вторых, очень важный способ этого выделения — процедуру, лежащую в основе позднейших алгоритмов диагонализации матрицы связей.
В 1925 г. советским гидробиологом П. В. Терентьевым был разработан «метод корреляционных плеяд» [88). Хотн метод направлен на выделение групп тесно коррелирующих признаков (это, видимо, первый алгоритм группировки параметров), он используется и для классификации объектов. Идея подхода является фактически основой многочисленных пороговых алгоритмов, алгоритмов на графах и др. В !939 г.
английский ученый Р. Триои впервые использовал термин «кластер- анализ» [151). Интересно, что Трион имел в виду опять-таки группировку параметров, называя кластерный анализ «факторным анализом для бедняков». Он считал, что вместо факторного анализа (тогда под ним имелся в виду центроидный метод) лучше выделять «грозди» показателей, и предлагал соответствующий метод, который сводился к поиску групп с хорошим (тесно коррелируюшнм) признаком в каждой на них.
В известном смысле это предвосхищает методологию экстремальной группировки Э. М. Бравермана (см. [16)). В начале 50-х годов появились первые публикации по иерархическим процедурам — статьи Р. Льюса (1950, см. [!03) ), Е. Фикса и Дж. Ходя«еса (1951, см. [102) и др.). Тогда же был опубликован коллективом авторов (Г. Штейнгауз н др.) алгоритм «вроцлавской таксоиомии» (1951, см. [71[), получивший впоследствии известность.
За это десятилетие методы классификации развивались достаточно интенсивно, но главным образом в ширину, а не в глубину. Хорошее обобщение (преимущественно по иерархическим процедурам и на биологическом материале) сделано Р. Соналом и Дж. Снятом; их идеи оказали существенное влияние на развитие всей проблематики. Особый толчок кластер-анализу был даи в 1958 †19 гг. Р. Розенблатгом (см. [20, 91)). Им выдвинута идея распознающего устройства (персептрона) и, наряду с задачей его обучения, поставлена задача самообучения. И в связи с бурным развитием всей теории распознавания развивалась теория «распознавания без учителя». В 60-е годы предложено множество алгоритмов и получен ряд теоретических обобщений.
В качестве наиболее важных (и наиболее цитируемых) можно выделить работы следующих авторов: Г. Болла и Д. Холла, Дж. Мак-Кивав по методам й-средних; Р. Сокала и Дж. Синга, Г. Ланга и У. Уильямса, Н. Джардайна и Р. Снбсона и др.— по иерархическим процедурам; Дж. Роджерса и Т. Твннмото, Э. М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
