Иерархическая кластеризация

Поделись знанием:
Перейти к: навигация, поиск

Иерархическая кластеризация (также графовые алгоритмы кластеризации) — совокупность алгоритмов упорядочивания данных, визуализация которых обеспечивается с помощью графов.

Алгоритмы упорядочивания данных указанного типа исходят из того, что некое множество объектов характеризуется определённой степенью связности. Предполагается наличие вложенных групп (кластеров различного порядка). Алгоритмы, в свою очередь, подразделяются на агломеративные (объединительные) и дивизивные (разделяющие). По количеству признаков иногда выделяют монотетические и политетические методы классификации. Как и большинство визуальных способов представления зависимостей графы быстро теряют наглядность при увеличении числа объектов. Существует ряд специализированных программ для построения графов.





Дендрограмма

Под дендрограммой обычно понимается дерево, то есть граф без циклов, построенный по матрице мер близости. Дендрограмма позволяет изобразить взаимные связи между объектами из заданного множества[1]. Для создания дендрограммы требуется матрица сходства (или различия), которая определяет уровень сходства между парами объектов. Чаще используются агломеративные методы.

Далее необходимо выбрать метод построения дендрограммы, который определяет способ пересчёта матрицы сходства (различия) после объединения (или разделения) очередных двух объектов в кластер.

В работах по кластерному анализу описан довольно внушительный ряд способов построения (англ. sorting strategies) дендрограмм[2]:

  1. Метод одиночной связи (англ. single linkage). Также известен, как «метод ближайшего соседа».
  2. Метод полной связи (англ. complete linkage). Также известен, как «метод дальнего соседа».
  3. Метод средней связи (англ. pair-group method using arithmetic averages).
    • Невзвешенный (англ. unweighted).
    • Взвешенный (англ. weighted).
  4. Центроидный метод (англ. pair-group method using the centroid average).
    • Невзвешенный.
    • Взвешенный (медианный).
  5. Метод Уорда (англ. Ward’s method).

Для первых трёх методов существует общая формула, предложенная А. Н. Колмогоровым для мер сходства[3]:

<math> K_\eta([i,j],k) = \left [ \frac{(n_iK(i,k)^\eta + (n_jK(j,k)^\eta)}{n_i + n_j} \right ]^\frac{1}{\eta}, - \mathcal {1} \leqslant \eta \leqslant + \mathcal {1} </math>

где <math>[i, j]</math> — группа из двух объектов (кластеров) <math>i</math> и <math>j</math>; <math>k</math> — объект (кластер), с которым ищется сходство указанной группы; <math>n_i</math> — число элементов в кластере <math>i</math>; <math>n_j</math> — число элементов в кластере <math>j</math>. Для расстояний имеется аналогичная формула Ланса — Вильямса[4].

Центроидный метод использует для пересчёта матрицы расстояний[5]. В качестве расстояния между двумя кластерами в этом методе берётся расстояние между их центрами тяжести.

В методе Уорда в качестве расстояния между кластерами берётся прирост суммы квадратов расстояний объектов до центров кластеров, получаемый в результате их объединения[6]. В отличие от других методов кластерного анализа, для оценки расстояний между кластерами здесь используются методы дисперсионного анализа. На каждом шаге алгоритма объединяются такие два кластера, которые приводят к минимальному увеличению целевой функции, то есть внутригрупповой суммы квадратов. Этот метод направлен на объединение близко расположенных кластеров.

Корреляционные плеяды

Широко применяются в геоботанике и флористике. Их часто называют корреляционными плеядами[7][8][9][10].

Частным случаем является метод, известный как метод построения оптимальных деревьев (дендритов), который был предложен математиком львовской школы Гуго Штейнгаузом[11], впоследствии метод был развит математиками вроцлавской таксономической школы[12]. Дендриты также не должны образовывать циклов. Можно частично использовать направленные дуги графов при использовании дополнительно мер включения (несимметричных мер сходства).

Диаграмма Чекановского

Метод «диагонализации» матрицы различия и графическое изображение кластеров вдоль главной диагонали матрицы различия (диаграмма Чекановского) впервые предложен Яном Чекановским в 1909 году[13]. Приведём описание методики:

Сущность этого метода заключается в том, что всю амплитуду полученных величин сходства разбивают на ряд классов, а затем в матрице величин сходства заменяют эти величины штриховкой, различной для каждого класса, причём обычно для более высоких классов сходства применяют более тёмную штриховку. Затем, меняя порядок описаний в таблице, добиваются того, чтобы более сходные описания оказались рядом[14]

Приведём гипотетический пример получения вышеуказанной диаграммы. Основой метода является построение матрицы транзитивного замыкания[15]. Для построения матрицы транзитивного замыкания возьмём простую матрицу сходства и умножим её саму на себя:

<math> K^{(2)}(i,j) = max(min(K(i,1),K(1,j)),...,min(K(i,q),K(q,j)))</math>,

где <math>K(i, j)</math> — элемент, стоящий на пересечении <math>i</math>-ой строки и <math>j</math>-го столбца в новой (второй) матрице, полученной после первой итерации; <math>q</math> — общее количество строк (столбцов) матрицы сходства. Данную процедуру необходимо продолжать, пока матрица не станет идемпотентной (то есть самоподобной): <math> K^{(n)}(i,j) = K^{(n-1)}(i,j) </math>, где n — число итераций.

Далее преобразовываем матрицу таким образом, чтобы близкие числовые значения находились рядом. Если каждому числовому значению присвоить какой-либо цвет или оттенок цвета (как в нашем случае), то получим классическую диаграмму Чекановского. Традиционно более тёмный цвет соответствует большему сходству, а более светлый — меньшему. В этом она схожа с теплокартой для матрицы расстояний.

См. также

Источники и примечания

  1. ↑ Жамбю М. Иерархический кластер-анализ и соответствия. — М.: Финансы и статистика, 1988. — 345 с.
  2. ↑ Классификация и кластер. Под ред. Дж. Вэн Райзина. М.: Мир, 1980. 390 с.
  3. ↑ Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: Классификация и снижение размерности. — М.: Финансы и статистика, 1989. — 607 с.
  4. ↑ Lance G.N., Willams W.T. A general theory of classification sorting strategies. 1. Hierarchical systems // Comp. J. 1967. № 9. P. 373—380.
  5. ↑ Sneath P.H.A., Sokal R.R. Numerical taxonomy: The principles and practices of numerical classification. — San-Francisco: Freeman, 1973. — 573 p.
  6. ↑ Ward J.H. Hierarchical grouping to optimize an objective function // J. of the American Statistical Association, 1963. — 236 р.
  7. ↑ von Terentjev P.V. [biocomparison.ucoz.ru/_ld/0/91_terentjev_1931.pdf Biometrische Untersuchungen über die morphologischen Merkmale von Rana ridibunda Pall. (Amphibia, Salientia)] // Biometrika. 1931. № 23(1-2). P. 23-51.
  8. ↑ Терентьев П. В. Метод корреляционных плеяд // Вестн. ЛГУ. № 9. 1959. С. 35-43.
  9. ↑ Терентьев П. В. Дальнейшее развитие метода корреляционных плеяд // Применение математических методов в биологии. Т. 1. Л.: 1960. С. 42-58.
  10. ↑ Выханду Л. К. Об исследовании многопризнаковых биологических систем // Применение математических методов в биологии. Л.: вып. 3. 1964. С. 19-22.
  11. ↑ Штейнгауз Г. Математический калейдоскоп. — М.: Наука, 1981. — 160 с.
  12. ↑ Florek K., Lukaszewicz S., Percal S., Steinhaus H., Zubrzycki S. Taksonomia Wroclawska // Przegl. antropol. 1951. T. 17. S. 193—211.
  13. ↑ Czekanowski J. Zur differential Diagnose der Neandertalgruppe // Korrespbl. Dtsch. Ges. Anthropol. 1909. Bd 40. S. 44-47.
  14. ↑ Василевич В. И. Статистические методы в геоботанике. — Л.: Наука, 1969. — 232 с.
  15. ↑ Tamura S., Hiquchi S., Tanaka K. [biocomparison.ucoz.ru/_ld/0/90_tamura_1971.pdf Pattern classification based on fuzzy relation] // IEEE transaction on systems, man, and cybernetics, 1971, SMC 1, № 1, P. 61-67.

Напишите отзыв о статье "Иерархическая кластеризация"

Отрывок, характеризующий Иерархическая кластеризация

Вперед его во двор проскакали адъютанты. Кутузов, нетерпеливо подталкивая свою лошадь, плывшую иноходью под его тяжестью, и беспрестанно кивая головой, прикладывал руку к бедой кавалергардской (с красным околышем и без козырька) фуражке, которая была на нем. Подъехав к почетному караулу молодцов гренадеров, большей частью кавалеров, отдававших ему честь, он с минуту молча, внимательно посмотрел на них начальническим упорным взглядом и обернулся к толпе генералов и офицеров, стоявших вокруг него. Лицо его вдруг приняло тонкое выражение; он вздернул плечами с жестом недоумения.
– И с такими молодцами всё отступать и отступать! – сказал он. – Ну, до свиданья, генерал, – прибавил он и тронул лошадь в ворота мимо князя Андрея и Денисова.
– Ура! ура! ура! – кричали сзади его.
С тех пор как не видал его князь Андрей, Кутузов еще потолстел, обрюзг и оплыл жиром. Но знакомые ему белый глаз, и рана, и выражение усталости в его лице и фигуре были те же. Он был одет в мундирный сюртук (плеть на тонком ремне висела через плечо) и в белой кавалергардской фуражке. Он, тяжело расплываясь и раскачиваясь, сидел на своей бодрой лошадке.
– Фю… фю… фю… – засвистал он чуть слышно, въезжая на двор. На лице его выражалась радость успокоения человека, намеревающегося отдохнуть после представительства. Он вынул левую ногу из стремени, повалившись всем телом и поморщившись от усилия, с трудом занес ее на седло, облокотился коленкой, крякнул и спустился на руки к казакам и адъютантам, поддерживавшим его.
Он оправился, оглянулся своими сощуренными глазами и, взглянув на князя Андрея, видимо, не узнав его, зашагал своей ныряющей походкой к крыльцу.
– Фю… фю… фю, – просвистал он и опять оглянулся на князя Андрея. Впечатление лица князя Андрея только после нескольких секунд (как это часто бывает у стариков) связалось с воспоминанием о его личности.
– А, здравствуй, князь, здравствуй, голубчик, пойдем… – устало проговорил он, оглядываясь, и тяжело вошел на скрипящее под его тяжестью крыльцо. Он расстегнулся и сел на лавочку, стоявшую на крыльце.
– Ну, что отец?
– Вчера получил известие о его кончине, – коротко сказал князь Андрей.
Кутузов испуганно открытыми глазами посмотрел на князя Андрея, потом снял фуражку и перекрестился: «Царство ему небесное! Да будет воля божия над всеми нами!Он тяжело, всей грудью вздохнул и помолчал. „Я его любил и уважал и сочувствую тебе всей душой“. Он обнял князя Андрея, прижал его к своей жирной груди и долго не отпускал от себя. Когда он отпустил его, князь Андрей увидал, что расплывшие губы Кутузова дрожали и на глазах были слезы. Он вздохнул и взялся обеими руками за лавку, чтобы встать.
– Пойдем, пойдем ко мне, поговорим, – сказал он; но в это время Денисов, так же мало робевший перед начальством, как и перед неприятелем, несмотря на то, что адъютанты у крыльца сердитым шепотом останавливали его, смело, стуча шпорами по ступенькам, вошел на крыльцо. Кутузов, оставив руки упертыми на лавку, недовольно смотрел на Денисова. Денисов, назвав себя, объявил, что имеет сообщить его светлости дело большой важности для блага отечества. Кутузов усталым взглядом стал смотреть на Денисова и досадливым жестом, приняв руки и сложив их на животе, повторил: «Для блага отечества? Ну что такое? Говори». Денисов покраснел, как девушка (так странно было видеть краску на этом усатом, старом и пьяном лице), и смело начал излагать свой план разрезания операционной линии неприятеля между Смоленском и Вязьмой. Денисов жил в этих краях и знал хорошо местность. План его казался несомненно хорошим, в особенности по той силе убеждения, которая была в его словах. Кутузов смотрел себе на ноги и изредка оглядывался на двор соседней избы, как будто он ждал чего то неприятного оттуда. Из избы, на которую он смотрел, действительно во время речи Денисова показался генерал с портфелем под мышкой.
– Что? – в середине изложения Денисова проговорил Кутузов. – Уже готовы?
– Готов, ваша светлость, – сказал генерал. Кутузов покачал головой, как бы говоря: «Как это все успеть одному человеку», и продолжал слушать Денисова.
– Даю честное благородное слово гусского офицег'а, – говорил Денисов, – что я г'азог'ву сообщения Наполеона.
– Тебе Кирилл Андреевич Денисов, обер интендант, как приходится? – перебил его Кутузов.
– Дядя г'одной, ваша светлость.
– О! приятели были, – весело сказал Кутузов. – Хорошо, хорошо, голубчик, оставайся тут при штабе, завтра поговорим. – Кивнув головой Денисову, он отвернулся и протянул руку к бумагам, которые принес ему Коновницын.
– Не угодно ли вашей светлости пожаловать в комнаты, – недовольным голосом сказал дежурный генерал, – необходимо рассмотреть планы и подписать некоторые бумаги. – Вышедший из двери адъютант доложил, что в квартире все было готово. Но Кутузову, видимо, хотелось войти в комнаты уже свободным. Он поморщился…
– Нет, вели подать, голубчик, сюда столик, я тут посмотрю, – сказал он. – Ты не уходи, – прибавил он, обращаясь к князю Андрею. Князь Андрей остался на крыльце, слушая дежурного генерала.
Во время доклада за входной дверью князь Андрей слышал женское шептанье и хрустение женского шелкового платья. Несколько раз, взглянув по тому направлению, он замечал за дверью, в розовом платье и лиловом шелковом платке на голове, полную, румяную и красивую женщину с блюдом, которая, очевидно, ожидала входа влавввквмандующего. Адъютант Кутузова шепотом объяснил князю Андрею, что это была хозяйка дома, попадья, которая намеревалась подать хлеб соль его светлости. Муж ее встретил светлейшего с крестом в церкви, она дома… «Очень хорошенькая», – прибавил адъютант с улыбкой. Кутузов оглянулся на эти слова. Кутузов слушал доклад дежурного генерала (главным предметом которого была критика позиции при Цареве Займище) так же, как он слушал Денисова, так же, как он слушал семь лет тому назад прения Аустерлицкого военного совета. Он, очевидно, слушал только оттого, что у него были уши, которые, несмотря на то, что в одном из них был морской канат, не могли не слышать; но очевидно было, что ничто из того, что мог сказать ему дежурный генерал, не могло не только удивить или заинтересовать его, но что он знал вперед все, что ему скажут, и слушал все это только потому, что надо прослушать, как надо прослушать поющийся молебен. Все, что говорил Денисов, было дельно и умно. То, что говорил дежурный генерал, было еще дельнее и умнее, но очевидно было, что Кутузов презирал и знание и ум и знал что то другое, что должно было решить дело, – что то другое, независимое от ума и знания. Князь Андрей внимательно следил за выражением лица главнокомандующего, и единственное выражение, которое он мог заметить в нем, было выражение скуки, любопытства к тому, что такое означал женский шепот за дверью, и желание соблюсти приличие. Очевидно было, что Кутузов презирал ум, и знание, и даже патриотическое чувство, которое выказывал Денисов, но презирал не умом, не чувством, не знанием (потому что он и не старался выказывать их), а он презирал их чем то другим. Он презирал их своей старостью, своею опытностью жизни. Одно распоряжение, которое от себя в этот доклад сделал Кутузов, откосилось до мародерства русских войск. Дежурный редерал в конце доклада представил светлейшему к подписи бумагу о взысканий с армейских начальников по прошению помещика за скошенный зеленый овес.


Источник — «http://wiki-org.ru/wiki/index.php?title=Иерархическая_кластеризация&oldid=61203617»