Дюран Б._ Оделл П. - Кластерный анализ (1977) (1185343), страница 6
Текст из файла (страница 6)
Имеются также и возражения против подхода, основанного на минимальной дисперсии в кластерном анализе. Так, изменение масштаба приведет к другому разбиению на кластеры. С этими и другими возражениями 34 и их обсуждением читатель может ознакомиться по р боте Уишарта (396). Там же рассматриваются методы, описанные выше. Фридман и Рубин (122] обсуждают некоторые инвариантные критерии группировки наблю- дений. 1.7. Алгоритм последовательной кластеризации о л* л'...а',„ о... е»~„ 1 1» 1» Предположим, что расстояние между 1» н 1» минималь- но, т.
е. что с»»»1 — ш»п(»»»1, 1чь1); образуем с помощью 1» и 1, новый кластер (1», 1»). Построим новую (и — !))»', К(п — 1) матрицу расстоянйя (см, табл. 1.5). Зе Схема последовательной кластеризации может быть описана следующим образом. Рассмотрим 1= (1», 1ь..., 1„) как множество кластеров (1»), (1»),..., (1е); выберем два из них, скажем 1» и 1и которые в некотором смысле наиболее близки друг к другу, и объединим их в один кластер. Новое множество кластеров, состоящее уже из п — 1 кластеров, будет (1»), (12), ° ° ° (1» 1»). ° ° ° (1е). , Повторяя процесс, мы получим последовательные множества кластеров, состоящие из п — 2, и — 3 и т.
д. кластеров. В конце втой процедуры получится кластер, состоящий из п объектов и.совпадающий с первоначальным множеством 1= (1ь 1ь °, 1 ). В качестве меры расстояния примем квадрат евклидовой метрики»1»' . Для наглядности вычислим матрицу 0 = (»1»1), где»»»е — квадрат расстояния между 1» и 1;. э Таблица Н4. Значения»»»1 Т е б л и и'в Кв, ЗнвеениЯ Н,1 поело первого объединения 11о 1з1 1з 1з 1» ...
1„ з з з з О Ап Азз Азз... Аз» О Аз Аз .. ° А» О Нзз ° .. А» О ... Нз» 11о 1з1 1з 1» О 36 Легко видеть, что п — 2 строкк для этой матрицы можно непосредственно взять из старой, однако первую строку необходимо вычислить заново. Очевидно, вычисления будут сведены к минимуму, если удастся выразить дз1», 1=1, 2,..., п, ЙФ1чь1' через элементы первоначальной матрицы. Ланс и Уильямс 12231 предложили рекурсивную процедуру, в которой вычисления матрицы расстояний опираются только на значения расстояний в предыдущей матрице.
Их рекурсивная схема предполагает использование минимального, и максимального локальных расстояний, медианы, групповых средних и центра. Все пять случаев, за исключением минимального локальнога расстояния и медианы, были описаны в параграфе !.б. Минимальное локальное расстояние между двумя кластерами ! и 7 было определено в параграфе 1.5; схема предусматривает объединение двух кластеров, имеющих наименьшее минимальное локальное расстояние. Медианный метод такой же, как и центроидный, за исключением того, что здесь при объединении кластеров 1н У предполагается, что Ьг=лю и поэтому центр нового кластера лежит точна посередине между центрами старых кластеров. Уишарт 13941 считает, что процедуру Уорда [3871 можно объединить с пятью, рассмотренными выше.
Как было показано в параграфе 1.5, объединение кластеров 2 н 7 ведет к увеличению ВсК на величину %'ы, котоРаз задается равенством Л2 ЛК вЂ” — — Л2 ЛК %'„= — (Х,-Ул)т(Х,— Х,) = а„, (1.!3) Л2+ЛК Л2+ЛЬ где д,', =(Х,— Х,)т(Х,— Хл). Если кластер 10Х=2. объединяется с К, то можно показать, что 2(К2 — (Хк— "ь) т (Хк — Хь) и П! 2 ПЬ 2 П2ПК Йль = — 1(кт+, — Йкл — —, Аю ° (1 14) ль 'ль П2Ь Более того, из (1.13) следует, что ПКПЬ 2 +П Кт' (1.15) Подставляя выражение (1.15) для каждого ~т2 в уравнение (1.14), получим: 1 ЧР«ь= — ((лт+лк) %к2+ (лр+лк) 2ккл ЛК+ПЬ ля%а) .
(!.16) . л'Равнение (1.16) определяет величину приращения ВСК прв объединении К и 7()7. Начиная с матрицы квадратов евклидовых расстояние (табл. 1.4) ьь= (21221 , 1= 1, 2, ..., Л; != 1, 2,..., л) процедура заключается в объединении таких кластеров 1» и 7,, для которых Ир»2=2%»ч минимально. Кластер 7», состоящий из одного объекта, заменяется на !р()7„ а расстояния 2(,', 1=1, 2,..., и; 1Фр, д в матрице 0 заиеняются на И,'р — — 2йг2р. Элементы д-го столбца и строки полагаютсЯ Равными нУлю, т. е. Яч становитсЯ- «недействительным» [394).
Соответственно лр заменяется . на лр+лч, а пч приравнивается нулю. Равенство И2р — — 2й2р (1.17) выполняется для всех (ь(121), 1, 1ФД. Подставляя %Р2р (фактически %";,) из уравнения (1 !6) в уравнение (1.17), получим 62р = 2йг2,= — ! (П1+лр) %';р+ 37 1 '+. (П3+и '! %'33 — п;Яурч) = ((п~+; 2 2 2 +пр)3(3р+ (п3+пд)Ач — Пг(рД, (1.18) где п„=пр+пч. Если на каждом шаге объединения р-е столбцы и строки матрицы 0 преобразовываются по формуле (1.18), то равенство (1.17) будет выполняться для всех д,3 и всех действительных множеств 5; и 5ь Заметим, что а1~31 в (1.17) не является евклндовым расстоянием, если не рассматриваются только два кластера, содержащих по одному элементу.
Алгоритм группировки окончательно может быть записан следующим образом 13941: !) Найдем 3(33 =ш(п(И3 ), 1=1,..., .1 — 1; =2,...,п; п;)О; п1)0; 2) Увеличение целевой функции при объединении 1 двух кластеров !р! равно Ф'рта - — Ы 3; 2 3) !р заменяется на 5р()53, 'строка (3(33 ) и столбец (а3 ) матрицы Й пересчитываются по формуле (1.18), 3=1, 2,..., р — 1; п;)О; ]=р+1,..., п; 1Фд; и;)О; 4) Полагаем па=ар+п, и пч=О, превращая 52 в недействительное множество; б) Записываем элементы кластера 53 в кластер 5р, возвращаемся к (1) и повторяем процедуру п — 2 раз. Ланс и Уильямс 12231 получили общее уравнение (1.19), аналогичное (1.18) и верное для всех пяти процессов кластеризации, описанных выше.
Это уравнение может быть записано в следующем виде: 3 3 2 Л 2 3 3133 = а13133+ а33(31+(!ам+у ~ йл3 — Йл;), (1.! 9) где аь аь (1 и у — параметры, задающне вид процесса. В уравнении (1.19) 3(33 обозначает меру расстояния между кластерами 13 и 13=7Щ. Значения параметров, входящих в общую формулу (1.19), соответствующие шести различным процессам кластеризации, приведены ниже: 1 минимальное локальное расстояние: а,=а;= —; р=О; 1 у= 1 Зз максимальное локальное расстояние: п«=а = — ' 8=0; 1. 1 21 1 2' 1 1, медиана: а«=пг= —; Р= — ' т'=9' 2' 4' среднее группы: а~=п;/па,' а~=л,!пж Р=у=б; центроидный метод: о«=п!пь: ат=п1lп»л Р= — г«~и~, у=О; метод Уорда: пч= э»+э вэ+пх — э» И1= — ' Р= — ' лэ+лэ лв+л~ и»+и» у=О.
Первые пять значений параметров приводятся в ра- боте Ланса и Уильямса [2231. Значения параметров в методе Уорда найдены Уишартом [3941 н получаются из уравнения (1.19). Все шесть методов были объеди- нены в одну вычислительную программу с параметра- ми а, 3 и у [3981, [399]. $.8. Другие вопросы кластерного анализа Одним из важнейших вопросов при решении кластерной проблемы является выбор необходимого числа кластеров. В некоторых случаях число кластеров т может быть выбрано априорно, однако в общем случае это число определяется в процессе разбиения множества на кластеры.
В этой книге мы не будем подробно останавливаться на этой сложной проблеме. Хорошо известно, что в некоторых задачах с боль-' шим числом наблюдений для практических целей пользуются методом случайного отбора. Фортьер и Соломон исследовали этн методы [1191 и нашли, что законы простого случайного отбора могут быть применены для вычисления числа кластеров, которое должно быть принято для достижения вероятности а того, что найдено наилучшее разбиение. Таким образом, оптимальное число разбиений является функцией задайной доли 8 «наилучших» или в некотором смысле допустимых разбиений в множестве всех возможных.
Общее рассеяние множества кластеров будет тем больше, чем выше доля й «допустнмых» разбиений. Фортьер и Соломон приводят таблицу, по которой можно найти необходимое число разбиений 8(а, (1) в зависимости от значеяий а н 8. При этом в качестве меры разнородности рассматрива- Таблица 1.6. Значения 3 (а, Р) 14 29 59 2 99 3026 32526 31 66 135 689 6977 75000 11 22 2 30 2326 25000 42 88 180 918 9303 100000 21 44 90 459 4652 55000 8 16 32 161 1626 17475 0,20 0,10 0,05 0,01 0,001 0 0001 При решении задачи кластерного анализа молчаливо принимается, что 1) выбранные характеристики в принципе допускают желательное разбиение на кластеры, 2) единицы измерения (масштаб) выбраны правильно, Первая проблема называется проблемой выбора свойств или характеристик объектов; этому вопросу посвящены работы [2291, [2301 и [2Щ .
Вообще предполагается, что проблема выбора характеристик решена до начала процесса кластеризации. Однако следует предупредить, что этим вносится некоторый произвол, что в отдельных случаях тоебует дополнительного рассмотрения. Другон вопрос, который всегда сопутствует измерению, — выбор масштаба — также играет большую роль. Как правило,' данные нормализуют вычитанием среднего и делением на стандартное отклонение; так что дисперсия оказывается рдвной единице. В случае же, когда исходят яз непосредственных (обычных) единиц измерения, возникает проблема интерпретации. Однако наиболее серьезная проблема возникает в связи с тем, что разбиение на кластеры зависит от выбора масштаба.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
