Однозв'язна кластеризація

У статистиці однозв'язна кластеризація є одним із методів ієрархічної кластеризації. Цей метод заснований на групуванні кластерів за принципом «знизу-вгору^[en]» (агломеративна кластеризація), на кожному кроці об'єднуючи два кластери, які містять найближчу пару елементів, які ще не належать до одного кластера.

Недоліком цього методу є те, що він має тенденцію створювати довгі тонкі кластери, в яких сусідні елементи одного кластера мають малу відстань, але елементи на протилежних кінцях кластера можуть бути набагато далі один від одного, ніж два елементи інших кластерів. Це може призвести до труднощів у визначенні класів, які могли б ефективно розділити дані.^[1]

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

На початку процесу агломераційної кластеризації кожен елемент знаходиться у власному кластері. Потім кластери послідовно об'єднуються у більші кластери, поки всі елементи не опиняться в одному кластері. На кожному кроці об'єднуються два кластери, розділені найменшою відстанню. Функція, яка використовується для визначення відстані між двома кластерами, відома як функція зв'язності, є тим, що вирізняє методи агломеративного кластеризування.

У однозв'язній кластеризації відстань між двома кластерами визначається однією парою елементів: тими двома елементами (по одному в кожному кластері), які найближче один до одного. Найкоротша з усіх попарних відстаней, що залишається на будь-якому кроці, призводить до злиття двох кластерів, на елементах яких досягається ця мінімальна відстань. Метод також відомий як кластеризація найближчих сусідів. Результат кластеризації можна візуалізувати як дендрограму^[en], яка показує послідовність об'єднання кластерів і відстані, на яких відбувалося кожне злиття.^[2]

Математично функція зв'язності — відстань 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^[en], обчислений на основі порівняння послідовності 5S рибосомної РНК п'яти бактерій: Bacillus subtilis ( $a$ ), Bacillus stearothermophilus ( $b$ ), Lactobacillus viridescens^[en] ( $c$ ), Acholeplasma modicum^[en] ( $d$ ), і Micrococcus luteus ( $e$ ).^[3]^[4]

Перший крок

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

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

	a	b	c	d	e
a	0	17	21	31	23
b	17	0	30	34	21
c	21	30	0	28	39
d	31	34	28	0	43
e	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}$ :

	(a, b)	c	d	e
(a, b)	0	21	31	21
c	21	0	28	39
d	31	28	0	43
e	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}$ це:

	((a, b), c,e)	d
((a, b), c,e)	0	28
d	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$ , як найглибший вузол.

Інші зв'язності

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

Альтернативні схеми зв'язностей включають повнозв'язну кластеризацію^[en], середньозв'язну кластеризацію (UPGMA^[en] та WPGMA^[en]) і метод Уорда^[en]. У простому алгоритмі для агломеративної кластеризації впровадження іншої схеми зв'язностей може бути виконано просто за допомогою іншої формули для обчислення міжкластерних відстаней в алгоритмі. У наведеному вище описі алгоритму формулу, яку потрібно відкоригувати, виділено жирним шрифтом. Однак більш ефективні алгоритми, такі як описаний нижче, не поширюються на всі схеми зв'язностей однаково.

Порівняння дендрограм, отриманих різними методами кластеризації для однієї матриці відстаней.

Однозв'язна кластеризації	Повнозв'язна кластеризація^[en]	Середньозв'язна кластеризацію: WPGMA^[en]	Середньозв'язна кластеризацію: UPGMA^[en]

Швидші алгоритми

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

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

Див. також

Примітки

↑ Everitt B (2011). Cluster analysis. Chichester, West Sussex, U.K: Wiley. ISBN 9780470749913.
↑ Numerical Ecology. Developments in Environmental Modelling. Т. 20 (вид. Second English). Amsterdam: Elsevier. 1998.
↑ Erdmann VA, Wolters J (1986). Collection of published 5S, 5.8S and 4.5S ribosomal RNA sequences. Nucleic Acids Research. 14 Suppl (Suppl): r1-59. doi:10.1093/nar/14.suppl.r1. PMC 341310. PMID 2422630.
↑ Olsen GJ (1988). Phylogenetic analysis using ribosomal RNA. Methods in Enzymology. 164: 793—812. doi:10.1016/s0076-6879(88)64084-5. PMID 3241556.
↑ Murtagh F, Contreras P (2012). Algorithms for hierarchical clustering: an overview. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. Wiley Online Library. 2 (1): 86—97. doi:10.1002/widm.53.
↑ Sibson R (1973). SLINK: an optimally efficient algorithm for the single-link cluster method (PDF). The Computer Journal. British Computer Society. 16 (1): 30—34. doi:10.1093/comjnl/16.1.30.
↑ Gan G (2007). Data clustering : theory, algorithms, and applications. Philadelphia, Pa. Alexandria, Va: SIAM, Society for Industrial and Applied Mathematics American Statistical Association. ISBN 9780898716238.
↑ Gower JC, Ross GJ (1969). Minimum spanning trees and single linkage cluster analysis. Journal of the Royal Statistical Society, Series C. 18 (1): 54—64. doi:10.2307/2346439. JSTOR 2346439. MR 0242315..

Посилання

Зв'язності, які використовуються в Matlab

[Everitt-1] Everitt B (2011). Cluster analysis. Chichester, West Sussex, U.K: Wiley. ISBN 9780470749913.

[2] Numerical Ecology. Developments in Environmental Modelling. Т. 20 (вид. Second English). Amsterdam: Elsevier. 1998.

[Erdmann1986-3] Erdmann VA, Wolters J (1986). Collection of published 5S, 5.8S and 4.5S ribosomal RNA sequences. Nucleic Acids Research. 14 Suppl (Suppl): r1-59. doi:10.1093/nar/14.suppl.r1. PMC 341310. PMID 2422630.

[Olsen1988-4] Olsen GJ (1988). Phylogenetic analysis using ribosomal RNA. Methods in Enzymology. 164: 793—812. doi:10.1016/s0076-6879(88)64084-5. PMID 3241556.

[5] Murtagh F, Contreras P (2012). Algorithms for hierarchical clustering: an overview. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. Wiley Online Library. 2 (1): 86—97. doi:10.1002/widm.53.

[6] Sibson R (1973). SLINK: an optimally efficient algorithm for the single-link cluster method (PDF). The Computer Journal. British Computer Society. 16 (1): 30—34. doi:10.1093/comjnl/16.1.30.

[7] Gan G (2007). Data clustering : theory, algorithms, and applications. Philadelphia, Pa. Alexandria, Va: SIAM, Society for Industrial and Applied Mathematics American Statistical Association. ISBN 9780898716238.

[8] Gower JC, Ross GJ (1969). Minimum spanning trees and single linkage cluster analysis. Journal of the Royal Statistical Society, Series C. 18 (1): 54—64. doi:10.2307/2346439. JSTOR 2346439. MR 0242315..

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]