Кластеризация с одной связью

В статистике . кластеризация с одной связью является одним из нескольких методов иерархической кластеризации Он основан на группировке кластеров восходящим способом (агломеративная кластеризация), объединяя на каждом шаге два кластера, содержащие ближайшую пару элементов, еще не принадлежащих друг другу к одному кластеру.

Этот метод имеет тенденцию создавать длинные тонкие кластеры, в которых соседние элементы одного и того же кластера находятся на небольших расстояниях, но элементы на противоположных концах кластера могут находиться намного дальше друг от друга, чем два элемента других кластеров. Для некоторых классов данных это может привести к трудностям при определении классов, которые могли бы с пользой разделить данные. ^[1] Тем не менее, он популярен в астрономии для анализа скоплений галактик , которые часто могут включать длинные нити материи; в этом приложении он также известен как алгоритм друзей друзей. ^[2]

Обзор методов агломерационной кластеризации

В начале процесса агломеративной кластеризации каждый элемент находится в своем собственном кластере. Затем кластеры последовательно объединяются в более крупные кластеры, пока все элементы не окажутся в одном кластере. На каждом шаге объединяются два кластера, разделенные кратчайшим расстоянием. Функция, используемая для определения расстояния между двумя кластерами, известная как функция связи , — это то, что отличает методы агломеративной кластеризации.

При кластеризации с одной связью расстояние между двумя кластерами определяется одной парой элементов: теми двумя элементами (по одному в каждом кластере), которые находятся ближе всего друг к другу. Кратчайшее из этих попарных расстояний, остающихся на любом шаге, приводит к слиянию двух кластеров, элементы которых участвуют. Этот метод также известен как кластеризация ближайших соседей . Результат кластеризации можно визуализировать в виде дендрограммы , которая показывает последовательность объединения кластеров и расстояние, на котором происходило каждое слияние. ^[3]

Математически функция связи – расстояние D ( X , Y ) между кластерами X и Y – описывается выражением

D(X,Y)=\min _{x\in X,y\in Y}d(x,y),

где X и Y — любые два набора элементов, рассматриваемых как кластеры, а d ( x , y ) обозначает расстояние между двумя элементами x и y .

Наивный алгоритм

Следующий алгоритм представляет собой агломеративную схему, которая стирает строки и столбцы в матрице близости по мере объединения старых кластеров с новыми. $N\times N$ матрица близости $D$ содержит все расстояния $d(i,j)$ . Кластеризациям присваиваются порядковые номера. $0,1,\ldots ,n-1$ и $L(k)$ это уровень $k$ -я кластеризация. Кластер с порядковым номером m обозначается ( m ), а близость между кластерами $(r)$ и $(s)$ обозначается $d[(r),(s)]$ .

Алгоритм одиночной связи состоит из следующих шагов:

Начнем с несвязной кластеризации, имеющей уровень $L(0)=0$ и порядковый номер $m=0$ .
Найдите наиболее похожую пару кластеров в текущей кластеризации, скажем, пару $(r),(s)$ , в соответствии с $d[(r),(s)]=\min d[(i),(j)]$ где минимум приходится на все пары кластеров в текущей кластеризации.
Увеличьте порядковый номер: $m=m+1$ . Объединение кластеров $(r)$ и $(s)$ в один кластер для формирования следующей кластеризации $m$ . Установите уровень этой кластеризации на $L(m)=d[(r),(s)]$
Обновите матрицу близости, $D$ , удалив строки и столбцы, соответствующие кластерам $(r)$ и $(s)$ и добавление строки и столбца, соответствующих вновь сформированному кластеру. Близость между новым кластером, обозначаемая $(r,s)$ и старый кластер $(k)$ определяется как $d[(r,s),(k)]=\min\{d[(k),(r)],d[(k),(s)]\}$ .
Если все объекты находятся в одном кластере, остановитесь. В противном случае перейдите к шагу 2.

Рабочий пример

Этот рабочий пример основан на JC69 матрице генетических расстояний , рассчитанной на основе выравнивания последовательностей 5S рибосомальной РНК пяти бактерий: Bacillus subtilis ( $a$ ), Bacillus stearothermophilus ( $b$ ), Lactobacillus viridescens ( $c$ ), Ахолеплазма хоть ( $d$ ) и Micrococcus luteus ( $e$ ). ^[4]^[5]

Первый шаг

Первая кластеризация

Предположим, что у нас есть пять элементов $(a,b,c,d,e)$ и следующая матрица $D_{1}$ попарных расстояний между ними:

	а	б	с	д	и
а	0	17	21	31	23
б	17	0	30	34	21
с	21	30	0	28	39
д	31	34	28	0	43
и	23	21	39	43	0

В этом примере $D_{1}(a,b)=17$ это наименьшее значение $D_{1}$ , поэтому мы кластеризуем элементы $a$ и $b$ .

Оценка длины первой ветки

Пусть $u$ обозначает узел, с которым $a$ и $b$ теперь соединены . Параметр $\delta (a,u)=\delta (b,u)=D_{1}(a,b)/2$ гарантирует, что элементы $a$ и $b$ равноудалены от $u$ . Это соответствует ожиданию гипотезы ультраметричности . Тогда ветви, соединяющие $a$ и $b$ с $u,$ имеют длину $\delta (a,u)=\delta (b,u)=17/2=8.5$ ( см. окончательную дендрограмму )

Первое обновление матрицы расстояний

Затем мы приступаем к обновлению исходной матрицы близости. $D_{1}$ в новую матрицу близости $D_{2}$ (см. ниже), уменьшенный в размере на одну строку и один столбец из-за кластеризации $a$ с $b$ .Жирные значения в $D_{2}$ соответствуют новым расстояниям, рассчитанным путем сохранения минимального расстояния между каждым элементом первого кластера $(a,b)$ и каждый из оставшихся элементов:

{\begin{array}{lllllll}D_{2}((a,b),c)&=&\min(D_{1}(a,c),D_{1}(b,c))&=&\min(21,30)&=&21\\D_{2}((a,b),d)&=&\min(D_{1}(a,d),D_{1}(b,d))&=&\min(31,34)&=&31\\D_{2}((a,b),e)&=&\min(D_{1}(a,e),D_{1}(b,e))&=&\min(23,21)&=&21\end{array}}

Курсивом выделены значения в $D_{2}$ на них не влияет обновление матрицы, поскольку они соответствуют расстояниям между элементами, не участвующими в первом кластере.

Второй шаг

Вторая кластеризация

Теперь мы повторяем три предыдущих действия, начиная с новой матрицы расстояний. $D_{2}$ :

	(а, б)	с	д	и
(а, б)	0	21	31	21
с	21	0	28	39
д	31	28	0	43
и	21	39	43	0

Здесь, $D_{2}((a,b),c)=21$ и $D_{2}((a,b),e)=21$ являются самыми низкими значениями $D_{2}$ , поэтому мы присоединяемся к кластеру $(a,b)$ с элементом $c$ и с элементом $e$ .

Оценка длины второй ветви

Обозначим через $v$ узел, к которому $(a,b)$ , $c$ и $e$ теперь соединены. Из-за ограничения ультраметричности ветви, соединяющие $a$ или $b$ с $v$ и $c$ с $v$ , а также $e$ с $v,$ равны и имеют следующую общую длину:

\delta (a,v)=\delta (b,v)=\delta (c,v)=\delta (e,v)=21/2=10.5

Выводим недостающую длину ветки:

\delta (u,v)=\delta (c,v)-\delta (a,u)=\delta (c,v)-\delta (b,u)=10.5-8.5=2

( см. окончательную дендрограмму )

Обновление матрицы второго расстояния

Затем мы приступаем к обновлению $D_{2}$ матрицу в новую матрицу расстояний $D_{3}$ (см. ниже), уменьшенный в размере на две строки и два столбца из-за кластеризации $(a,b)$ с $c$ и с $e$ :

D_{3}(((a,b),c,e),d)=\min(D_{2}((a,b),d),D_{2}(c,d),D_{2}(e,d))=\min(31,28,43)=28

Последний шаг

Финал $D_{3}$ матрица:

	((а,б),в,д)	д
((а,б),в,д)	0	28
д	28	0

Итак, мы объединяем кластеры $((a,b),c,e)$ и $d$ .

Позволять $r$ обозначают (корневой) узел, к которому $((a,b),c,e)$ и $d$ теперь подключены.Ветви, соединяющиеся $((a,b),c,e)$ и $d$ к $r$ тогда имейте длину:

$\delta (((a,b),c,e),r)=\delta (d,r)=28/2=14$

Выводим оставшуюся длину ветки:

$\delta (v,r)=\delta (a,r)-\delta (a,v)=\delta (b,r)-\delta (b,v)=\delta (c,r)-\delta (c,v)=\delta (e,r)-\delta (e,v)=14-10.5=3.5$

Дендрограмма одинарной связи

Дендрограмма готова. Он ультраметрический, потому что все кончики ( $a$ , $b$ , $c$ , $e$ , и $d$ ) равноудалены от $r$ :

$\delta (a,r)=\delta (b,r)=\delta (c,r)=\delta (e,r)=\delta (d,r)=14$

Таким образом, дендрограмма имеет корни $r$ , его самый глубокий узел.

Другие связи

Наивный алгоритм кластеризации с одной связью по существу такой же, как алгоритм Крускала для минимальных остовных деревьев . Однако при кластеризации с одной связью важен порядок формирования кластеров, тогда как для минимальных остовных деревьев важен набор пар точек, образующих расстояния, выбранные алгоритмом.

Альтернативные схемы связывания включают полную кластеризацию связей , кластеризацию средней связи ( UPGMA и WPGMA ) и метод Уорда . В простом алгоритме агломеративной кластеризации реализация другой схемы связи может быть достигнута просто за счет использования другой формулы для расчета расстояний между кластерами в алгоритме. Формула, которую следует скорректировать, выделена жирным шрифтом в приведенном выше описании алгоритма. Однако более эффективные алгоритмы, подобные описанному ниже, не распространяются на все схемы связи одинаково.

Сравнение дендрограмм, полученных разными методами кластеризации из одной и той же матрицы расстояний .

Кластеризация с одной связью	Кластеризация с полной связью	Кластеризация средних связей: WPGMA	Кластеризация средней связи: UPGMA

Более быстрые алгоритмы

Наивный алгоритм односвязной кластеризации прост для понимания, но медленный и требует временных затрат. $O(n^{3})$ . ^[6] В 1973 году Р. Сибсон предложил алгоритм с временной сложностью $O(n^{2})$ и пространственная сложность $O(n)$ (оба оптимальных), известный как SLINK. Алгоритм слинка представляет собой кластеризацию на наборе $n$ нумерованные элементы по двум функциям. Обе эти функции определяются путем поиска наименьшего кластера $C$ который содержит оба элемента $i$ и хотя бы один предмет с большим номером.Первая функция, $\pi$ , элемент карты $i$ к элементу с наибольшим номером в кластере $C$ .Вторая функция, $\lambda$ , элемент карты $i$ на расстояние, связанное с созданием кластера $C$ .Хранение этих функций в двух массивах, которые сопоставляют каждый номер элемента со значением его функции, занимает место. $O(n)$ , и этой информации достаточно для определения самой кластеризации. Как показывает Сибсон, когда к набору элементов добавляется новый элемент, обновленные функции, представляющие новую кластеризацию с одной связью для расширенного набора, представленного таким же образом, могут быть построены из старой кластеризации во времени. $O(n)$ . Затем алгоритм SLINK перебирает элементы один за другим, добавляя их к представлению кластеризации. ^[7]^[8]

Альтернативный алгоритм, работающий в тех же оптимальных временных и пространственных границах, основан на эквивалентности наивного алгоритма и алгоритма Краскала для минимальных остовных деревьев. Вместо использования алгоритма Крускала можно использовать алгоритм Прима в варианте без двоичных куч, который требует времени. $O(n^{2})$ и космос $O(n)$ построить минимальное остовное дерево (но не кластеризацию) заданных элементов и расстояний. Затем применение алгоритма Краскала к разреженному графу, образованному ребрами минимального остовного дерева, приводит к самой кластеризации за дополнительное время. $O(n\log n)$ и космос $O(n)$ . ^[9]

См. также

Ссылки

^ Эверитт Б. (2011). Кластерный анализ . Чичестер, Западный Суссекс, Великобритания: Wiley. ISBN 9780470749913 .
^ Фейгельсон, Эрик (2012). «Классификация в астрономии: прошлое и настоящее». В пути, Майкл Дж.; Скаргл, Джеффри Д.; Али, Камаль М.; Шривастава, Ашок Н. (ред.). Достижения в области машинного обучения и интеллектуального анализа данных для астрономии . Чепмен и Холл/CRC. стр. 3–10. Бибкод : 2012amld.book....3F . дои : 10.1201/b11822-7 .
^ Лежандр П., Лежандр Л. (1998). Численная экология . Развитие экологического моделирования. Том. 20 (Второе английское изд.). Амстердам: Эльзевир.
^ Эрдманн В.А., Уолтерс Дж. (1986). «Коллекция опубликованных последовательностей рибосомальных РНК 5S, 5,8S и 4,5S» . Исследования нуклеиновых кислот . 14 Дополнение (Suppl): r1-59. дои : 10.1093/nar/14.suppl.r1 . ПМК 341310 . ПМИД 2422630 .
^ Олсен Дж.Дж. (1988). «Филогенетический анализ с использованием рибосомальной РНК». В Noller HF Jr, Moldave K (ред.). Рибосомы . Методы энзимологии. Том. 164. стр. 793–812. дои : 10.1016/s0076-6879(88)64084-5 . ISBN 978-0-12-182065-7 . ПМИД 3241556 .
^ Мурта Ф., Контрерас П. (2012). «Алгоритмы иерархической кластеризации: обзор». Междисциплинарные обзоры Wiley: интеллектуальный анализ данных и обнаружение знаний . 2 (1). Интернет-библиотека Wiley: 86–97. дои : 10.1002/widm.53 .
^ Сибсон Р. (1973). «SLINK: оптимально эффективный алгоритм для метода однозвенной кластеризации» (PDF) . Компьютерный журнал . 16 (1). Британское компьютерное общество: 30–34. дои : 10.1093/comjnl/16.1.30 .
^ Ган Джи (2007). Кластеризация данных: теория, алгоритмы и приложения . Филадельфия, Пенсильвания. Александрия, Вирджиния: SIAM, Общество промышленной и прикладной математики Американской статистической ассоциации. ISBN 9780898716238 .
^ Гауэр Дж.К., Росс Дж.Дж. (1969). «Минимальные связующие деревья и кластерный анализ с одной связью». Журнал Королевского статистического общества, серия C. 18 (1): 54–64. дои : 10.2307/2346439 . JSTOR 2346439 . МР 0242315 . .

Внешние ссылки

Связи, используемые в Matlab

[Everitt-1] Эверитт Б. (2011). Кластерный анализ . Чичестер, Западный Суссекс, Великобритания: Wiley. ISBN 9780470749913 .

[2] Фейгельсон, Эрик (2012). «Классификация в астрономии: прошлое и настоящее». В пути, Майкл Дж.; Скаргл, Джеффри Д.; Али, Камаль М.; Шривастава, Ашок Н. (ред.). Достижения в области машинного обучения и интеллектуального анализа данных для астрономии . Чепмен и Холл/CRC. стр. 3–10. Бибкод : 2012amld.book....3F . дои : 10.1201/b11822-7 .

[3] Лежандр П., Лежандр Л. (1998). Численная экология . Развитие экологического моделирования. Том. 20 (Второе английское изд.). Амстердам: Эльзевир.

[Erdmann1986-4] Эрдманн В.А., Уолтерс Дж. (1986). «Коллекция опубликованных последовательностей рибосомальных РНК 5S, 5,8S и 4,5S» . Исследования нуклеиновых кислот . 14 Дополнение (Suppl): r1-59. дои : 10.1093/nar/14.suppl.r1 . ПМК 341310 . ПМИД 2422630 .

[Olsen1988-5] Олсен Дж.Дж. (1988). «Филогенетический анализ с использованием рибосомальной РНК». В Noller HF Jr, Moldave K (ред.). Рибосомы . Методы энзимологии. Том. 164. стр. 793–812. дои : 10.1016/s0076-6879(88)64084-5 . ISBN 978-0-12-182065-7 . ПМИД 3241556 .

[6] Мурта Ф., Контрерас П. (2012). «Алгоритмы иерархической кластеризации: обзор». Междисциплинарные обзоры Wiley: интеллектуальный анализ данных и обнаружение знаний . 2 (1). Интернет-библиотека Wiley: 86–97. дои : 10.1002/widm.53 .

[7] Сибсон Р. (1973). «SLINK: оптимально эффективный алгоритм для метода однозвенной кластеризации» (PDF) . Компьютерный журнал . 16 (1). Британское компьютерное общество: 30–34. дои : 10.1093/comjnl/16.1.30 .

[8] Ган Джи (2007). Кластеризация данных: теория, алгоритмы и приложения . Филадельфия, Пенсильвания. Александрия, Вирджиния: SIAM, Общество промышленной и прикладной математики Американской статистической ассоциации. ISBN 9780898716238 .

[9] Гауэр Дж.К., Росс Дж.Дж. (1969). «Минимальные связующие деревья и кластерный анализ с одной связью». Журнал Королевского статистического общества, серия C. 18 (1): 54–64. дои : 10.2307/2346439 . JSTOR 2346439 . МР 0242315 . .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]