И.Д. Мандель - Кластерный анализ (1185344), страница 35
Текст из файла (страница 35)
Более гибкими в этом смысле выступают непараметрические процедуры, названные выше, хотя точных исследований не проводилось. В экспериментальном отношении критерии качества изучались мало. Г. Миллиган [14!] проверил 30 функционалов на своем полигоне, частично описанном в 2.4. Четырьмя иерархическими алгоритмами (методы дальней, ближней и средней связи, Уорда) классифицировались искусственные данные, а затем на уровнях, отвечающих числу сгенерированных кластеров, вычислялись значения всех критериев качества.
Определялся коэффициент Рэнда внешней близости машинного и алгоритмического разбиений, а также коэффициент Жаккарда (см. !.3). Затем для всего набора расчетов (при изменении вида алгоритмов, числа классов, характера ошибок и т. д.) вычислялись коэффициенты корреляции Спирмена и Пирсона между внутренними 30 критериями и двумя внешними. 154 Т а б л и ц а 4.3. Результаты зксаернментального сравнения критернеа каиестна классификации [141, с.
1921 Приведем эти значения для тех 10 критериев, которые попали в наш обзор, в табл. 4.3. Как видно, лидирующее положение занимают критерии двух видов: типа непараметрических (25, 27, 28) и параметрических (26, 30) характеристик соответствия между внутри- и межкластерными расстояниями. На последних местах — критерии дисперсионного типа (особенно удивляет слабый результат, полученный популярной величиной Ее). Конечно, эти расчеты нельзя трактовать как «приговор» тем или иным статистикам. Из описания методики видно, что алгоритмы не стремились оптимизировать критерии, а просто фиксировали их уровень. Однако даже при таком подходе прослеживается эффективность непараметрических измерителей качества (о чем говорилось в 4.2.2), а также выгодность двусторонних оценок типа «вне — внутри» по сравнению с раздельными их составляющими.
Показательно, что в группу лучших вошла корреляционная статистика гзы которая, как отмечалось в 2.3, связана с аппроксимационным подходом 2.3.4 и тоже имеет вид «вне — внутри>. Сравнительные преимущества прямого и оптимизационного подхода не раз обсуждались в 2.2, 2.3, поэтому отметим лишь, что для выделения кластеров сложной формы лучше использовать прямые методы (для этой цели, кстати, хорошо подходят и «плохие в среднем» алгоритмы ближнего соседа, «вроцлавской таксономии» и др., особенно перспективным выглядит метод !9 из таол. 2.3, о чем говорилось в 4.2.2). Попробуем компактно охарактеризовать в целом последовательность этапов и критериев, которыми целесообразно руководствоваться исследователю при выборе алгоритмов классификации (рис.
4.6). Ставить вопросы и отвечать на них желательно именно в том порядке, который показан на схеме. При последовательном ее применении в каждом отдельном случае множество возможных алгоритмов будет резко сокращено. Рис. 4.6. Общая схема выбора алгоритма кластер-анализа для решения прикладных задач 4ЦК4.
ВЫВОР ПАРАМВТРОВ АЛГОРИТМОВ КЛАССИФИКАЦИИ Как видно из рнс. 4.5, более половины рассмотренных в книге алгоритмов требуют знания числа классов, !Оой-ного порога типа расстояния до центра класса. Как выбирать значения этих и других параметров? 1. Число классов иногда легко определить из сушества задачи: например, требуется, зная взаимное отношение людей, разделить их на три исследовательские группы; разбить предприятия на группы хороших, средних и плохих и т.
д. Но в общем случае этот вопрос очень не тривиален. Если допускаются единичные классы (а чаще всего так и делается), то он тесно смыкается с проблемой робастных оценок. Действительно, задавая некоторое число классов и даже зная, сколько классов имеется на самом деле, всегда есть риск, что вместо скоплений выделяется именно засоряющие совокупность объекты. Алгоритмы типа иерархических процедур или диагонализации сравнительно легко выделяют такие аномалии, а для эталонных процедур они могут стать серьезной помехой.
Поэтому целесообразны следующие приемы: проверить точки на ближайшее окружение (см. алг. 47, 48); до классификации отбросить несколько самых удаленных точек (проверить по сумме расстояний или по минимальному расстоянию), как это делается 156 при определении среднего балла фигуристов, и др. Уже после такой очистки можно задавать число классов. Некоторые способы определения числа классов были описаны в 2.2 и 2.3; табл. 4.! дает представление о тех методах классификации, в которых число классов определяется либо автоматически, либо с участием человека (особенно часто в последнем случае используется идея выявления скачка расстояния при переходе от класса к классу).
В этих алгоритмах процесс задания числа классов «встроен» в сами вычисления. Когда же этого нет, требуется проводить дополнительные расчеты. Самый простой способ — задать целый спектр значений классов и из полученных разбиений выбрать наилучшее в каком-то смысле (содержательном или формальном). Так часто и поступают, привнося, конечно, сильный субъективизм в принятие решения. Т а б л и н а 4.4. Результаты экспериментального сравнении критериев выбора числа классов (142, р. 165 — 176) № п/п Число классов, показываемое критерием Критерии, авторы, годы Ранги по К+2 К+3 и более Истин- К+1 нос число К К вЂ” 2 и ме- нее К вЂ” ! (142) Существует множество рекомендаций по количественным критериям определения числа классов — чаще всего в той же ситуации многократного прогона алгоритма. Г.
Миллиган и М. Купер в 1985 г. опубликовали результаты сравнения 30 тестов такого рода уже по известной нам схеме генерации данных и с использованием нескольких иерархических процедур. На каждом уровне иерархии определялось значение критериев и проверялась точность «угадывания» критерием истинного числа классов. В общей сложности каждый критерий проверялся на 432 выборках, отличающихся типами ошибок н т. д. (число объектов — 50). Истинное число классов было равно 2, 3, 4, 5.
В табл. 4.4 приведена небольшая выдержка из обширной таблицы [142]. Опишем коротко новые критерии по номерам таблицы (остальные, см. табл. 2.5). 157 1 2 3 4 5 6 7 8 9 1О 11 !2 Калинский, Харабаш, 1974 Дуда, Харт, 1973 Хьюберт, Левин,!976, Етб Бейкер, Хьюберт, !975, Рте Бил, 1969 Рэй, 1982; Сэрль, !983 Миллиган, 1980, гы Рольф, !974, Ртг Рольф, 1974, Ры Фридман, Рубин, 1969, Ри Мак-Клайн, Рао, 1975, гзю Фридман, Рубин, !969, г1~ 1 2 3 4 5 6 7 8 17 23 28 30 1 0 4 8 7 0 25 4 74 81 0 0 !8 23 29 37 55 22 83 36 126 1!8 6 0 390 388 347 339 331 321 308 297 202 !2! 25 0 12 8 10 11 ! 35 9 6 1О 62 6 0 5 7 2 2 4 22 4 0 7 18 ! 0 6 6 40 35 34 32 3 89 !О 32 400 432 1.
(!гВ/(й — 1)/!г)г/(п-й), где  — матрица межклассового разброса, Ж' — внутриклассового разброса (см. описание Ен — Еы в 2.3), 2. !км//лц, где /кю — сумма квадратов ошибок внутри кластера, когда данные разделены на два кластера, /кп — когда они объединены в ! кластер. Критерий является статистическим, если в предположении нормальности выборок он превышает критическое значение (рекомендуют 3, 2). Классы стоит объединять. 3, 4. См, в табл.
2.5. 5. Величина, аналогичная критерию 2 и тоже ориентированная на нормальность: Š— критерий для дисперсий в объединяемых кластерах. 6. «Кубический критерий»; основан на гипотезе о равномерном законе распределения и о сгущении в нем (это более реалистичная посылка, чем в двух предыдущих статистиках). Равен величине !п((1 — Е()г')/(1 — й~)), где /г' — доля дисперсии, объясняемая кластерами, Е(!г) — ее ожидаемое значение в предположении справедливости гипотезы. Данные табл. 4.4 весьма красноречивы. В целом опять можно констатировать преимущества непараметрических критериев и критериев для расстояний типа «вне — внутри». Неудача Еы, видимо, говорит о большей выгоде сложения расстояний (как в Е»), чем об их делении.
«Инвариантные критерии» Фридмана — Рубина ведут себя плохо. Несколько неожиданно лидерство дисперсионного критерия Калинского — Харабаша; скорее всего дело в особой нормировке дисперсионных матриц, так как другие их комбинации приводят, как видно, к неудачам. Определение «истинного числа классов» означает, конечно, нечто большее, чем задание рабочего параметра алгоритма. В известной мере это узловая проблемы кластер-анализа, и неудивительно, что она не находит однозначного решения.
Так, уже после появления работы (142) и с учетом ее был предложен весьма перспективный метод оценки числа классов с использованием статистической техники бутстрэпа, свободной от параметрических гипотез (153). Для нахождения числа классов полезно применить два-три способа, но здесь вероятность успеха, видимо, выше, чем для выбора алгоритмов, ибо решение носит более грубый характер. 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
