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

Кластеризация с полной связью — один из нескольких методов агломеративной иерархической кластеризации . В начале процесса каждый элемент находится в своем кластере. Затем кластеры последовательно объединяются в более крупные кластеры, пока все элементы не окажутся в одном кластере. Этот метод также известен как кластеризация дальних соседей . Результат кластеризации можно визуализировать в виде дендрограммы , которая показывает последовательность слияния кластеров и расстояние, на котором происходило каждое слияние. ^[1]^[2]^[3]

Процедура кластеризации

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

Математически полная функция связи — расстояние $D(X,Y)$ между кластерами $X$ и $Y$ — описывается следующим выражением: $D(X,Y)=\max _{x\in X,y\in Y}d(x,y)$

где

$d(x,y)$ расстояние между элементами $x\in X$ и $y\in Y$ ;
$X$ и $Y$ представляют собой два набора элементов (кластеров).

Алгоритмы

Наивная схема

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

Полный алгоритм кластеризации связей состоит из следующих шагов:

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

Оптимально эффективная схема

Алгоритм, описанный выше, прост для понимания, но сложен. $O(n^{3})$ . В мае 1976 г. Д. Дефайс предложил оптимально эффективный алгоритм, сложность которого составляет всего лишь $O(n^{2})$ известный как CLINK (опубликовано в 1977 г.) ^[4] вдохновлен аналогичным алгоритмом SLINK для кластеризации с одной связью .

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

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

Первый шаг

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

Предположим, что у нас есть пять элементов $(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)$ и каждый из оставшихся элементов:

$D_{2}((a,b),c)=max(D_{1}(a,c),D_{1}(b,c))=max(21,30)=30$

$D_{2}((a,b),d)=max(D_{1}(a,d),D_{1}(b,d))=max(31,34)=34$

$D_{2}((a,b),e)=max(D_{1}(a,e),D_{1}(b,e))=max(23,21)=23$

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

Второй шаг

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

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

	(а, б)	с	д	и
(а, б)	0	30	34	23
с	30	0	28	39
д	34	28	0	43
и	23	39	43	0

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

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

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

Выводим недостающую длину ветки: $\delta (u,v)=\delta (e,v)-\delta (a,u)=\delta (e,v)-\delta (b,u)=11.5-8.5=3$ ( см. окончательную дендрограмму )

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

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

$D_{3}(((a,b),e),c)=max(D_{2}((a,b),c),D_{2}(e,c))=max(30,39)=39$

$D_{3}(((a,b),e),d)=max(D_{2}((a,b),d),D_{2}(e,d))=max(34,43)=43$

Третий шаг

Третья кластеризация

Мы снова повторяем три предыдущих шага, начиная с обновленной матрицы расстояний. $D_{3}$ .

	((а,б),д)	с	д
((а,б),д)	0	39	43
с	39	0	28
д	43	28	0

Здесь, $D_{3}(c,d)=28$ это наименьшее значение $D_{3}$ , поэтому мы соединяем элементы $c$ и $d$ .

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

Позволять $w$ обозначаем узел, к которому $c$ и $d$ теперь подключены.Ветви, соединяющиеся $c$ и $d$ к $w$ тогда есть длины $\delta (c,w)=\delta (d,w)=28/2=14$ ( см. окончательную дендрограмму )

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

Есть одна запись для обновления: $D_{4}((c,d),((a,b),e))=max(D_{3}(c,((a,b),e)),D_{3}(d,((a,b),e)))=max(39,43)=43$

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

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

	((а,б),д)	(в, г)
((а,б),д)	0	43
(в, г)	43	0

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

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

$\delta (((a,b),e),r)=\delta ((c,d),r)=43/2=21.5$

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

$\delta (v,r)=\delta (((a,b),e),r)-\delta (e,v)=21.5-11.5=10$

$\delta (w,r)=\delta ((c,d),r)-\delta (c,w)=21.5-14=7.5$

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

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

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

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

Сравнение с другими связями

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

Кластеризация с полной связью позволяет избежать недостатка альтернативного метода с одной связью - так называемого явления цепочки , при котором кластеры, сформированные с помощью кластеризации с одной связью, могут быть объединены вместе из-за того, что отдельные элементы находятся близко друг к другу, даже если многие элементы в каждом кластере могут быть очень далеки друг от друга. Полная связь имеет тенденцию находить компактные кластеры примерно одинакового диаметра. ^[7]

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

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

См. также

Ссылки

^ Соренсен Т. (1948). «Метод установления групп равной амплитуды в социологии растений, основанный на сходстве видов, и его применение к анализу растительности на территории Дании». Биологический Скрифтер . 5 : 1–34.
^ Лежандр П., Лежандр Л. (1998). Численная экология (второе английское изд.). п. 853.
^ Эверитт Б.С., Ландау С. , Лиз М. (2001). Кластерный анализ (Четвертое изд.). Лондон: Арнольд. ISBN 0-340-76119-9 .
^ Дефайс Д. (1977). «Эффективный алгоритм для метода полной ссылки». Компьютерный журнал . 20 (4). Британское компьютерное общество: 364–366. дои : 10.1093/comjnl/20.4.364 .
^ Эрдманн В.А., Уолтерс Дж. (1986). «Коллекция опубликованных последовательностей рибосомальных РНК 5S, 5,8S и 4,5S» . Исследования нуклеиновых кислот . 14 Дополнение (Suppl): r1-59. дои : 10.1093/nar/14.suppl.r1 . ПМК 341310 . ПМИД 2422630 .
^ Олсен Дж.Дж. (1988). «Филогенетический анализ с использованием рибосомальной РНК». Рибосомы . Методы энзимологии. Том. 164. стр. 793–812. дои : 10.1016/s0076-6879(88)64084-5 . ISBN 978-0-12-182065-7 . ПМИД 3241556 .
^ Эверитт, Ландау и Лиз (2001), стр. 62-64.

Дальнейшее чтение

Спет Х (1980). Алгоритмы кластерного анализа . Чичестер: Эллис Хорвуд.

[1] Соренсен Т. (1948). «Метод установления групп равной амплитуды в социологии растений, основанный на сходстве видов, и его применение к анализу растительности на территории Дании». Биологический Скрифтер . 5 : 1–34.

[2] Лежандр П., Лежандр Л. (1998). Численная экология (второе английское изд.). п. 853.

[3] Эверитт Б.С., Ландау С. , Лиз М. (2001). Кластерный анализ (Четвертое изд.). Лондон: Арнольд. ISBN 0-340-76119-9 .

[4] Дефайс Д. (1977). «Эффективный алгоритм для метода полной ссылки». Компьютерный журнал . 20 (4). Британское компьютерное общество: 364–366. дои : 10.1093/comjnl/20.4.364 .

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

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

[7] Эверитт, Ландау и Лиз (2001), стр. 62-64.

[1]

[2]

[3]

[4]

[5]

[6]

[7]