Дюран Б._ Оделл П. - Кластерный анализ (1977) (1185343), страница 16
Текст из файла (страница 16)
Кластер расщепляется, если внутригрупповая дисперсия кластера 5„7 по любой характеристике х превышает пороговое значение 57. Таким образом, дисперсия 577 результирующего кластера 1 ограничена неравенством 57а~р57, где р — число характеристик. Вместо первоначальных центров подставляются новые и процесс продолжается до полной стабилизации (до полной сходимости). Описание программ ИСОМАН содер.-- жится у Холли [166). Первоначальный 'вариант программы ИСОМАН основан на евклидовой метрике. Вариант программы, описанной в 1166), основан на применении взвешенной евклидовой метрики. Кап и Холли 1194) предложили окончательный вариант ИСОМАН.
При распределении объектов по ближайшим кластерам (центрам кластеров) вместо евклидовой метрики они воспользовались метрикой 1,*. Мера вариации для каждой характеристики 57, оставалась той же. Для вычисления 11777 бралось взвешенное евклидово расстояние. Опишем применение окончательной рекомендации программы ИСОМАН Кана и Холли для мультиспектральных данных сканирования. Пример взят из работы Кана н Холли 1194]. Имеется 7=35 линий сканирования и с=45 столбцов или выборочных точек на каждой линии сканирования.
Таким образом, имеем л=35 45= =1575 наблюдений. Существуют четыре источника (способа) получения мультнспектральных данных сканирования, т. е. р=4. Пороговое значение расщепления равно 4,5, а пороговое значение объединения 3,2. Это означает, что нд некоторой итерации кластер расщепляется по 1'-му измерению, если дисперсия по 1-му измерению превосходит значение 4,5. Наоборот, если два кластера находятся на расстоянии меньшем, чем 3, 2 единицы, то они объединяются в один кластер. Программе потребовалось 12 итераций для образования семи кластеров с числом элементов, равным соответственно 565, 132, 2!9, 201, 180, 224 и 54. " См.
параграф 1.3. — Примеч. пер. 7 Заказ 67аа 91 Таблица 6,1. Итоговые статистики для каждого кластера Источннк среднее среднее среднее среднее среднее среднее среднее 98 стандартное отклонение стандартное отклонение стандартное отклоненне стандартное отклонение стандартное отклонение стандартное отклонение 182,59 176,91 1,779 2,671 178,35 172,44 3,619 2,840 166,68 163,63 2,250 2, 150 179,42 174,99 179,77 170,24 2,200 1,728 163,10 158,60 181,89 173,52 2,738 1,940 187,33 1,814 173,98 167,10 2,614 181,01 157,64 2,134 159,57 3,356 3,306 200,39 1,862 187,72 2,720 181,35 2,541 194,69 166,74 2,348 174,53 2,946 173,74 4, 006 В табл.
6.1 приводятся итоговые статистики для каждого кластера, а табл. 6.2 представляет собой матрицу межкластерных расстояний на конец 12-й итерации. Данные для примера Кана и Холли были взяты из 1409!. Остальные детали рассмотрены в !1941 Т а б л и ц а 6.2. Таблнпа межкластерных расстоиина Кластер Кластер 0,0 8,7 16,0 4,5 197 13,6 8,7 0,0 6,5 4,2 !0,9 9,9 5,2 16,0 6,5 0,0 11,1 9;9 4,4 8,2 22,3 10,9 9,9 16,5 0,0 9,6 4,0 19,7 9,9 4,4 14,7 9,6 0,0 10,0 4с5 4,2 11,1 0,0 16,5 14,7 9,4 13,6 5,5 8,2 9,4 4,0 10,0 0,0 Кластер ! 2 Сорт 49 1 0 14 Ирис «сетоса» Ирис «версикалор» Ирис «виркжииика» 17 !3 18 0 Если отнести кластер 1 к ирису «сетоса», кластеры 2, 3, 4, 6 — к ирису «версикалору», а кластеры 6, 7, 8, 9 — к ирису «вирджиника», то получится 22 класса.
Процесс кластеризации с помощью евклидова расстояния приводит к 8 классам. 7" 99 6.2. Применение метода оценивания функции плотности для данных Фишера по ирису [401 Данные Фишера по ирису состоят из четырех характеристик (р=4); при этом рассматриваются три сорта ирисов. Для каждого сорта имеется выборка объемом 60 наблюдений. Сорта ирисов следующие: ирис «сетоса», ирис «версикалор», ирис «вирджиника»; четырьмя. характеристиками служат: длина стебля, ширина стебля, длина лепестка н ширина лепестка. Кластерный анализ с помощью расстояния Махаланобиса привел к девяти кластерам, что в табл. 6.3 показано по сортам.
Т а б л и и а 6.3. Число элементов, принадлежащих кластерам, ралбнтые по сортам ГЛАВА т ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ В последние годы к области классификации наблюдений, а в особенности к кластерному анализу был проявлен огромный интерес. За это время в различных журналах появилось большое число публикаций по кластерному анализу, которые охватывают самые разнообразные вопросы.
В то же время отсутствуют работы, которые бы объединяли полученные результаты и в которых читатель нашел бы последовательное изложение всех вопросов, Первые шесть глав этой книги (может быть, за исключением главы 2) являются попыткой в этом направлении. В этой главе мы сделаем некоторые замечания о . развитии кластерного анализа за последние четыре десятилетия.
Первоначальное описание и определение предмета, известного сейчас под названием «кластерный анализ», было сделано Трионом [36!] в 1939 г. В недавно вышедшей книге Триона и Бейли [371, 1970) они рассматривают вычислительную систему ВСПУ, предназначенную для решения задач кластеризации и факторного анализа в области социологии. В книге Фишера [108, 1968) рассматриваются специальные методы, применяемые в задачах агрегирования в экономике. Коул [57, 1969) рассматривает работы, представленные на коллоквиум по численной таксономин. В недавно вышедшей книге Джардайна и Сибсона [180) читатель найдет математическое обоснование методов, которыми пользуются в биологической таксономии; эти методы на самом деле имеют более широкое применение.
Исследование этих методов продолжено в [175), [177], [178] и [179]. Ими же был предложен аксиоматический подход к кластерному анализу. Андерберг написал книгу по кластер- !оо ному анализу, цель которой предложить унифицированный подход к кластерному анализу на элементарном уровне; в этой книге обсуждается также большое коли-,' чество других вопросов кластерного анализа. Книга, Сокала и Снита [3361 служит хорошим справочным руководством, ориентированным на лиц, работающих в биологии; однако эта книга мало пригодна для исследо-' вателей других областей. Болл 1131 сделал прекрасный обзор и сравнение различных методов «поиска кластеров». Он разбивает .
все методы на семь групп: 1) вероятностные, 2) методы обнаружения сигнала, 3) кластеризации, 4) группировки, 5) собственных, значений, 6) отыскания минимальной моды, 7) остальные. Наиболее употребительными методами, под которыми обычно и понимается кластерный анализ, являются методы кластеризации (3) и методы группировки (4). Ступенчатые методы, которые обсуждались в главе 1,— это методы группировки, а методы минимальной дисперсии той же главы принадлежат к группе методов кластеризации. Метод отыскания минимальной моды требует предварительного раз.
биения наблюдений на классы. Класс собственных значений Холла сродни факторному анализу и методу главных компонент многомерного анализа. Другой класс, который включает в себя метод оценивания функции плотности, обсуждался в главе 5. Вероятностные методы Холла могут быть обобщены и на этот случай. Методы кластеризации в общем случае наиболее эффективны; эти методы также хорошо поддаются интерпретации.
Однако в исследованиях таксономии методы группировки более популярны. Исторически методы группировки были первыми методами кластеризации, которые впервые были применены в чнслециой таксономии. Работа Сокала и Скита 13361 может блужить хорошим справочным руководством по этим методам. Широкое признание нашел кластерный метод Болла и Холла 1151, 1161, 1181 ИСОМАН (итеративный самообучающийся метод анализа данных).
Этот метод был коротко упомянут в главе 1 как метод минимальной дисперсии. Он применялся; в частности, в задаче регистрации отдаленных объектов (мультнспектралыные данные сканирования) в НАСА, в Центре пилотируе- мых космических кораблей. Инструкцию по его эксплуа. тации можно найти в [166], [191], [193]. Окончательная версия ИСОМАНа была предложена Каном и Холли [194]. Применение ИСОМАН было показано на примере регистрации отдаленных объектов (мульти- спектральные данные сканирования),.который был описан в предыдущей главе. '. Другим полезным методом является добавочный (абйпп) алгоритм Хартигена (записн лекций), который также описан у Кана и Холли [194].
Этот метод относится к классу разделительных (б(ч!зе) иерархических алгоритмов. Кан и Холли обсуждают и другие меч тоды, которые также применяются и весьма полезны (см. [325], [208], [404] и [302]). Целью патерн-рекогносцировки, как и кластерного анализа,' является разбиение данных на группы.
Однако в патерн-анализе для каждого наблюдения известно, к какому классу информации оно принадлежит. Наджи [270] предлагает прекрасный обзор по патерн-рекогносцировке. Его статья насчитывает 148 ссылок. Методы кластеризации могут быть разбиты нв два больших 'класса:.1) разделительные, 2) агломератив« ные. Не надо только путать понятия алгоритма и метода. Данный метод может принадлежать либо к классу разделительных, либо к классу аеломеративных методов.
Разделительные методы разбивают множество объектов на группы, а агломеративные, наоборот, объединяют объекты в группы (кластеры). Разделительные методы были введены Эдвардсом и Кавалли-Сфорца [93], МакНотоном-Смитом и другими [235] и Ресчиньо и Макакоро [293], Класс агломеративных методов шие; некоторые из этих методов были описаны в главе 1, 223], [234], [387], Ступенчатый алгоритм кластеризации, рассмотренный в главе 1, является агломеративным алгоритмом. Агломеративные процедуры в общем случае не обязательно итеративные н предполагают существование правила объединения двух кластеров.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
