Односвязная кластеризация - Single-linkage clustering

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первый шаг

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

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

	а	б	c	d	е
а	0	17	21	31	23
б	17	0	30	34	21
c	21	30	0	28	39
d	31	34	28	0	43
е	23	21	39	43	0

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

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

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

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

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

${\displaystyle D_{2}((a,b),c)=min(D_{1}(a,c),D_{1}(b,c))=min(21,30)=21}$

${\displaystyle D_{2}((a,b),d)=min(D_{1}(a,d),D_{1}(b,d))=min(31,34)=31}$

${\displaystyle D_{2}((a,b),e)=min(D_{1}(a,e),D_{1}(b,e))=min(23,21)=21}$

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

Второй шаг

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

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

	(а, б)	c	d	е
(а, б)	0	21	31	21
c	21	0	28	39
d	31	28	0	43
е	21	39	43	0

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

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

Позволять ${\displaystyle v}$ обозначим узел, к которому ${\displaystyle (a,b)}$, ${\displaystyle c}$ и ${\displaystyle e}$ теперь подключены. Из-за ограничения ультраметричности ветви, соединяющиеся ${\displaystyle a}$ или же ${\displaystyle b}$ к ${\displaystyle v}$, и ${\displaystyle c}$ к ${\displaystyle v}$, а также ${\displaystyle e}$ к ${\displaystyle v}$ равны и имеют следующую общую длину:${\displaystyle \delta (a,v)=\delta (b,v)=\delta (c,v)=\delta (e,v)=21/2=10.5}$

Вычисляем недостающую длину ветки:${\displaystyle \delta (u,v)=\delta (c,v)-\delta (a,u)=\delta (c,v)-\delta (b,u)=10.5-8.5=2}$ (см. финальную дендрограмму )

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

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

${\displaystyle 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}$

Заключительный этап

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

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

Итак, мы присоединяемся к кластерам ${\displaystyle ((a,b),c,e)}$ и ${\displaystyle d}$.

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

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

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

${\displaystyle \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}$

Дендрограмма одинарного сцепления

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

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

Таким образом, дендрограмма основана на ${\displaystyle r}$, его самый глубокий узел.

Прочие связи

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

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

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

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

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

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

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

Смотрите также

• Кластерный анализ
• Кластеризация с полной связью
• Иерархическая кластеризация
• Молекулярные часы
• Соседство
• UPGMA
• WPGMA

Рекомендации

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

внешняя ссылка

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