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

По генетике см. Полная связь

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

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

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

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

куда

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

Алгоритмы

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

Следующий алгоритм является агломеративный Схема, которая стирает строки и столбцы в матрице близости, когда старые кластеры объединяются в новые. В ${\displaystyle N\times N}$ матрица близости D содержит все расстояния d(я,j). Кластеризациям присваиваются порядковые номера 0,1, ......, (п - 1) и L(k) - уровень k-й кластеризации. Кластер с порядковым номером м обозначается (м) и близость кластеров (р) и (s) обозначается d[(р),(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)]=\max\{d[(k),(r)],d[(k),(s)]\}}$.
5. Если все объекты находятся в одном кластере, остановитесь. В противном случае перейдите к шагу 2.

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

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

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

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

Первый шаг

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

Предположим, что у нас есть пять элементов ${\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)=max(D_{1}(a,c),D_{1}(b,c))=max(21,30)=30}$

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

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

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

Второй шаг

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

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

	(а, б)	c	d	е
(а, б)	0	30	34	23
c	30	0	28	39
d	34	28	0	43
е	23	39	43	0

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

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

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

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

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

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

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

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

Третий шаг

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

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

	((а, б), д)	c	d
((а, б), д)	0	39	43
c	39	0	28
d	43	28	0

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

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

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

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

Необходимо обновить одну запись:${\displaystyle D_{4}((c,d),((a,b),e))=max(D_{3}(c,((a,b),e)),D_{3}(d,((a,b),e)))=max(39,43)=43}$

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

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

	((а, б), д)	(CD)
((а, б), д)	0	43
(CD)	43	0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Späth H (1980). Алгоритмы кластерного анализа. Чичестер: Эллис Хорвуд.