У статистиці однозв'язна кластеризація є одним із методів ієрархічної кластеризації. Цей метод заснований на групуванні кластерів за принципом [en]» (агломеративна кластеризація), на кожному кроці об'єднуючи два кластери, які містять найближчу пару елементів, які ще не належать до одного кластера.
Недоліком цього методу є те, що він має тенденцію створювати довгі тонкі кластери, в яких сусідні елементи одного кластера мають малу відстань, але елементи на протилежних кінцях кластера можуть бути набагато далі один від одного, ніж два елементи інших кластерів. Це може призвести до труднощів у визначенні класів, які могли б ефективно розділити дані.
Огляд методів агломераційної кластеризації
На початку процесу агломераційної кластеризації кожен елемент знаходиться у власному кластері. Потім кластери послідовно об'єднуються у більші кластери, поки всі елементи не опиняться в одному кластері. На кожному кроці об'єднуються два кластери, розділені найменшою відстанню. Функція, яка використовується для визначення відстані між двома кластерами, відома як функція зв'язності, є тим, що вирізняє методи агломеративного кластеризування.
У однозв'язній кластеризації відстань між двома кластерами визначається однією парою елементів: тими двома елементами (по одному в кожному кластері), які найближче один до одного. Найкоротша з усіх попарних відстаней, що залишається на будь-якому кроці, призводить до злиття двох кластерів, на елементах яких досягається ця мінімальна відстань. Метод також відомий як кластеризація найближчих сусідів. Результат кластеризації можна візуалізувати як [en], яка показує послідовність об'єднання кластерів і відстані, на яких відбувалося кожне злиття.
Математично функція зв'язності — відстань D(X, Y) між кластерами X і Y — описується виразом
де X і Y — будь-які дві множини елементів, які розглядаються як кластери, а d(x, y) позначає відстань між двома елементами x і y.
Наївний алгоритм
Наступний алгоритм — це агломеративна схема, яка вилучає рядки та стовпці в матриці близькості, коли старі кластери об'єднуються в нові. Матриця розміру є матрицею близькості та містить усі відстані . Кластеризаціям присвоюються порядкові номери і — це рівень -ї кластеризації. Кластер з порядковим номером m позначається (m), а близькість між кластерами і позначається як .
Алгоритм однозв'язної кластеризації складається з наступних кроків:
- Почніть з кластеризації, у якій кожен елемент належить окремому кластеру. Вона має рівень і порядковий номер .
- Знайдіть найбільш схожу пару кластерів у поточній кластеризації, скажімо пару , відповідно до функції відстані , де мінімум береться по всім парам кластерів у поточній кластеризації.
- Збільшити порядковий номер: . Об'єднати кластери і в один кластер для формування наступної кластеризації . Встановіть рівень цієї кластеризації на .
- Оновити матрицю близкості , шляхом видалення рядків і стовпців, що відповідають кластерам і і додавання рядка та стовпця, що відповідають новосформованому кластеру. Близькість між новим кластером позначена і старим кластером визначається як .
- Якщо всі об'єкти знаходяться в одному кластері, зупиніться. Інакше перейдіть до кроку 2.
Приклад
Цей реальний приклад базується на матриці генетичної відстані [en], обчислений на основі порівняння послідовності 5S рибосомної РНК п'яти бактерій: Bacillus subtilis (), Bacillus stearothermophilus (), [en] (), [en] (), і Micrococcus luteus ().
Перший крок
- Перша кластеризація
Припустимо, що у нас п'ять елементів і наступна матриця попарних відстаней між ними:
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 |
У цьому прикладі є найменшим значенням , тому ми групуємо елементи a і b.
- Оцінка довжини першої гілки
Нехай u позначає вузол, до якого тепер підєднані a і b. Встановлення значень гарантує, що елементи a і b рівновіддалені від u. Це відповідає очікуванням гіпотези ультраметричності. Тоді гілки, що сполучають a і b з u, мають довжини (див. кінцеву дендрограму)
- Перше оновлення матриці відстаней
Потім ми переходимо до оновлення початкової матриці близькості у нову матрицю близькості (див. нижче), ми зменшуємо розмір матриці на один рядок і один стовпець через кластеризацію a з b. Значення в виділені жирним шрифтом відповідають новим відстаням, розрахованим шляхом збереження мінімальної відстані між кожним елементом першого кластера і кожним з елементів, що залишилися:
Значення виділені курсивом в залишаються без змін при оновленні матриці, оскільки вони відповідають відстаням між елементами, які не беруть участь у першому кластері.
Другий крок
- Друга кластеризація
Тепер ми повторюємо три попередні дії, починаючи з нової матриці відстані :
(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 |
Тут і є найменшими значеннями , тому ми приєднуємося до кластеру елемент c і елемент e.
- Оцінка довжини другої гілки
Нехай v позначає вузол, до якого , c і e тепер приєднані. Через накладення умови ультраметричності, гілки, що з'єднують a або b з v, і c з v, а також e з v, рівні та мають таку загальну довжину:
Виводимо відсутню довжину гілки:
- Друге оновлення матриці відстані
Потім ми переходимо до оновлення матриці у нову матрицю відстаней (див. нижче), спочатку зменшуємо розмір матриці на два рядки та два стовпці через кластеризацію з c і з e:
Заключний крок
Підсумкова матриця це:
((a, b), c,e) | d | |
---|---|---|
((a, b), c,e) | 0 | 28 |
d | 28 | 0 |
Тож об'єднуємо кластери і .
Нехай позначає (кореневий) вузол, до якого приєднані і . З'єднання гілок і до мають такі довжини:
Виводимо довжину гілки, що залишилася:
Однозв'язна дендрограма
Дендрограма готова. Вона ультраметрична, тому що всі елементи (, , , , і ) знаходяться на однаковій відстані від :
Таким чином, дендрограма має корінь , як найглибший вузол.
Інші зв'язності
Наївний алгоритм для однозв'язної кластеризації по суті такий самий, як алгоритм Крускала для мінімальних кістякових дерев. Однак у однозв'язній кластеризації важливий порядок, у якому утворюються кластери, тоді як для мінімальних кістякових дерев важливим є множиною пар точок, які утворюють відстані, вибрані алгоритмом.
Альтернативні схеми зв'язностей включають [en], середньозв'язну кластеризацію ([en] та [en]) і [en]. У простому алгоритмі для агломеративної кластеризації впровадження іншої схеми зв'язностей може бути виконано просто за допомогою іншої формули для обчислення міжкластерних відстаней в алгоритмі. У наведеному вище описі алгоритму формулу, яку потрібно відкоригувати, виділено жирним шрифтом. Однак більш ефективні алгоритми, такі як описаний нижче, не поширюються на всі схеми зв'язностей однаково.
Однозв'язна кластеризації | [en] | Середньозв'язна кластеризацію: [en] | Середньозв'язна кластеризацію: [en] |
Швидші алгоритми
Наївний алгоритм однозв'язної кластеризації простий для розуміння, але повільний і має часову складність . У 1973 р. Р. Сібсон запропонував алгоритм з часовою складністю і складність простору (обидва оптимальні), відомі як SLINK. Алгоритм SLINK представляє кластеризацію на множині пронумерованих елементів за двома функціями. Обидві ці функції визначаються шляхом пошуку найменшого кластера , який містить обидва елементи і принаймні один елемент із більшим номером. Перша функція, , відображає елемент до елемента з найбільшим номером у кластері . Друга функція, , відображає елемент до відстані, пов'язаної зі створенням кластера . Зберігання цих функцій у двох масивах, які відображають кожен номер елемента в його функціональному значенні, займає у памяті місця, і цієї інформації достатньо для визначення самої кластеризації. Як показує Сібсон, коли новий елемент додається до множини елементів, оновлені функції, що представляють нову кластеризацію з одним зв'язком для доповненої множини, представлену таким же чином, можуть бути побудовані на основі старої кластеризації в часі . Алгоритм SLINK потім перебирає елементи один за одним, додаючи їх до представлення кластеризації.
Альтернативний алгоритм, що працює в тих самих оптимальних часових і просторових межах, заснований на еквівалентності між наївним алгоритмом і алгоритмом Крускала для мінімальних кістякових дерев. Замість використання алгоритму Крускала можна використати алгоритм Прима у варіації без бінарних куп, що потребує часу і простору для побудови мінімального кістякового дерева (але не кластеризації) із заданих елементів і відстаней. Потім застосування алгоритму Крускала до розрідженого графа, утвореного ребрами мінімального кістякового дерева, створює саму кластеризацію за додатковий час і з використанням простору .
Див. також
Примітки
- Everitt B (2011). Cluster analysis. Chichester, West Sussex, U.K: Wiley. ISBN .
- 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 .
- 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
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U statistici odnozv yazna klasterizaciya ye odnim iz metodiv iyerarhichnoyi klasterizaciyi Cej metod zasnovanij na grupuvanni klasteriv za principom en aglomerativna klasterizaciya na kozhnomu kroci ob yednuyuchi dva klasteri yaki mistyat najblizhchu paru elementiv yaki she ne nalezhat do odnogo klastera Nedolikom cogo metodu ye te sho vin maye tendenciyu stvoryuvati dovgi tonki klasteri v yakih susidni elementi odnogo klastera mayut malu vidstan ale elementi na protilezhnih kincyah klastera mozhut buti nabagato dali odin vid odnogo nizh dva elementi inshih klasteriv Ce mozhe prizvesti do trudnoshiv u viznachenni klasiv yaki mogli b efektivno rozdiliti dani Oglyad metodiv aglomeracijnoyi klasterizaciyiNa pochatku procesu aglomeracijnoyi klasterizaciyi kozhen element znahoditsya u vlasnomu klasteri Potim klasteri poslidovno ob yednuyutsya u bilshi klasteri poki vsi elementi ne opinyatsya v odnomu klasteri Na kozhnomu kroci ob yednuyutsya dva klasteri rozdileni najmenshoyu vidstannyu Funkciya yaka vikoristovuyetsya dlya viznachennya vidstani mizh dvoma klasterami vidoma yak funkciya zv yaznosti ye tim sho viriznyaye metodi aglomerativnogo klasterizuvannya U odnozv yaznij klasterizaciyi vidstan mizh dvoma klasterami viznachayetsya odniyeyu paroyu elementiv timi dvoma elementami po odnomu v kozhnomu klasteri yaki najblizhche odin do odnogo Najkorotsha z usih poparnih vidstanej sho zalishayetsya na bud yakomu kroci prizvodit do zlittya dvoh klasteriv na elementah yakih dosyagayetsya cya minimalna vidstan Metod takozh vidomij yak klasterizaciya najblizhchih susidiv Rezultat klasterizaciyi mozhna vizualizuvati yak en yaka pokazuye poslidovnist ob yednannya klasteriv i vidstani na yakih vidbuvalosya kozhne zlittya Matematichno funkciya zv yaznosti vidstan D X Y mizh klasterami X i Y opisuyetsya virazom D X Y min x X y Y d x y displaystyle D X Y min x in X y in Y d x y de X i Y bud yaki dvi mnozhini elementiv yaki rozglyadayutsya yak klasteri a d x y poznachaye vidstan mizh dvoma elementami x i y Nayivnij algoritmNastupnij algoritm ce aglomerativna shema yaka viluchaye ryadki ta stovpci v matrici blizkosti koli stari klasteri ob yednuyutsya v novi Matricya rozmiru N N displaystyle N times N ye matriceyu blizkosti D displaystyle D ta mistit usi vidstani d i j displaystyle d i j Klasterizaciyam prisvoyuyutsya poryadkovi nomeri 0 1 n 1 displaystyle 0 1 ldots n 1 i L k displaystyle L k ce riven k displaystyle k yi klasterizaciyi Klaster z poryadkovim nomerom m poznachayetsya m a blizkist mizh klasterami r displaystyle r i s displaystyle s poznachayetsya yak d r s displaystyle d r s Algoritm odnozv yaznoyi klasterizaciyi skladayetsya z nastupnih krokiv Pochnit z klasterizaciyi u yakij kozhen element nalezhit okremomu klasteru Vona maye riven L 0 0 displaystyle L 0 0 i poryadkovij nomer m 0 displaystyle m 0 Znajdit najbilsh shozhu paru klasteriv u potochnij klasterizaciyi skazhimo paru r s displaystyle r s vidpovidno do funkciyi vidstani d r s min d i j displaystyle d r s min d i j de minimum beretsya po vsim param klasteriv u potochnij klasterizaciyi Zbilshiti poryadkovij nomer m m 1 displaystyle m m 1 Ob yednati klasteri r displaystyle r i s displaystyle s v odin klaster dlya formuvannya nastupnoyi klasterizaciyi m displaystyle m Vstanovit riven ciyeyi klasterizaciyi na L m d r s displaystyle L m d r s Onoviti matricyu blizkosti D displaystyle D shlyahom vidalennya ryadkiv i stovpciv sho vidpovidayut klasteram r displaystyle r i s displaystyle s i dodavannya ryadka ta stovpcya sho vidpovidayut novosformovanomu klasteru Blizkist mizh novim klasterom poznachena r s displaystyle r s i starim klasterom k displaystyle k viznachayetsya yak d r s k min d k r d k s displaystyle d r s k min d k r d k s Yaksho vsi ob yekti znahodyatsya v odnomu klasteri zupinitsya Inakshe perejdit do kroku 2 PrikladCej realnij priklad bazuyetsya na matrici genetichnoyi vidstani en obchislenij na osnovi porivnyannya poslidovnosti 5S ribosomnoyi RNK p yati bakterij Bacillus subtilis a displaystyle a Bacillus stearothermophilus b displaystyle b en c displaystyle c en d displaystyle d i Micrococcus luteus e displaystyle e Pershij krok Persha klasterizaciya Pripustimo sho u nas p yat elementiv a b c d e displaystyle a b c d e i nastupna matricya D 1 displaystyle D 1 poparnih vidstanej mizh nimi 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 U comu prikladi D 1 a b 17 displaystyle D 1 a b 17 ye najmenshim znachennyam D 1 displaystyle D 1 tomu mi grupuyemo elementi a i b Ocinka dovzhini pershoyi gilki Nehaj u poznachaye vuzol do yakogo teper pidyednani a i b Vstanovlennya znachen d a u d b u D 1 a b 2 displaystyle delta a u delta b u D 1 a b 2 garantuye sho elementi a i b rivnoviddaleni vid u Ce vidpovidaye ochikuvannyam gipotezi ultrametrichnosti Todi gilki sho spoluchayut a i b z u mayut dovzhini d a u d b u 17 2 8 5 displaystyle delta a u delta b u 17 2 8 5 div kincevu dendrogramu Pershe onovlennya matrici vidstanej Potim mi perehodimo do onovlennya pochatkovoyi matrici blizkosti D 1 displaystyle D 1 u novu matricyu blizkosti D 2 displaystyle D 2 div nizhche mi zmenshuyemo rozmir matrici na odin ryadok i odin stovpec cherez klasterizaciyu a z b Znachennya v D 2 displaystyle D 2 vidileni zhirnim shriftom vidpovidayut novim vidstanyam rozrahovanim shlyahom zberezhennya minimalnoyi vidstani mizh kozhnim elementom pershogo klastera a b displaystyle a b i kozhnim z elementiv sho zalishilisya 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 displaystyle begin array lllllll D 2 a b c amp amp min D 1 a c D 1 b c amp amp min 21 30 amp amp 21 D 2 a b d amp amp min D 1 a d D 1 b d amp amp min 31 34 amp amp 31 D 2 a b e amp amp min D 1 a e D 1 b e amp amp min 23 21 amp amp 21 end array Znachennya vidileni kursivom v D 2 displaystyle D 2 zalishayutsya bez zmin pri onovlenni matrici oskilki voni vidpovidayut vidstanyam mizh elementami yaki ne berut uchast u pershomu klasteri Drugij krok Druga klasterizaciya Teper mi povtoryuyemo tri poperedni diyi pochinayuchi z novoyi matrici vidstani D 2 displaystyle 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 Tut D 2 a b c 21 displaystyle D 2 a b c 21 i D 2 a b e 21 displaystyle D 2 a b e 21 ye najmenshimi znachennyami D 2 displaystyle D 2 tomu mi priyednuyemosya do klasteru a b displaystyle a b element c i element e Ocinka dovzhini drugoyi gilki Nehaj v poznachaye vuzol do yakogo a b displaystyle a b c i e teper priyednani Cherez nakladennya umovi ultrametrichnosti gilki sho z yednuyut a abo b z v i c z v a takozh e z v rivni ta mayut taku zagalnu dovzhinu d a v d b v d c v d e v 21 2 10 5 displaystyle delta a v delta b v delta c v delta e v 21 2 10 5 Vivodimo vidsutnyu dovzhinu gilki d u v d c v d a u d c v d b u 10 5 8 5 2 displaystyle delta u v delta c v delta a u delta c v delta b u 10 5 8 5 2 div kincevu dendrogramu Druge onovlennya matrici vidstani Potim mi perehodimo do onovlennya matrici D 2 displaystyle D 2 u novu matricyu vidstanej D 3 displaystyle D 3 div nizhche spochatku zmenshuyemo rozmir matrici na dva ryadki ta dva stovpci cherez klasterizaciyu a b displaystyle a b z c i z 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 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 Zaklyuchnij krok Pidsumkova matricya D 3 displaystyle D 3 ce a b c e d a b c e 0 28 d 28 0 Tozh ob yednuyemo klasteri a b c e displaystyle a b c e i d displaystyle d Nehaj r displaystyle r poznachaye korenevij vuzol do yakogo priyednani a b c e displaystyle a b c e i d displaystyle d Z yednannya gilok a b c e displaystyle a b c e i d displaystyle d do r displaystyle r mayut taki dovzhini d a b c e r d d r 28 2 14 displaystyle delta a b c e r delta d r 28 2 14 Vivodimo dovzhinu gilki sho zalishilasya d v r d a r d a v d b r d b v d c r d c v d e r d e v 14 10 5 3 5 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 Odnozv yazna dendrograma Dani odnozv yaznoyi dendrogrami 5S Dendrograma gotova Vona ultrametrichna tomu sho vsi elementi a displaystyle a b displaystyle b c displaystyle c e displaystyle e i d displaystyle d znahodyatsya na odnakovij vidstani vid r displaystyle r d a r d b r d c r d e r d d r 14 displaystyle delta a r delta b r delta c r delta e r delta d r 14 Takim chinom dendrograma maye korin r displaystyle r yak najglibshij vuzol Inshi zv yaznostiNayivnij algoritm dlya odnozv yaznoyi klasterizaciyi po suti takij samij yak algoritm Kruskala dlya minimalnih kistyakovih derev Odnak u odnozv yaznij klasterizaciyi vazhlivij poryadok u yakomu utvoryuyutsya klasteri todi yak dlya minimalnih kistyakovih derev vazhlivim ye mnozhinoyu par tochok yaki utvoryuyut vidstani vibrani algoritmom Alternativni shemi zv yaznostej vklyuchayut en serednozv yaznu klasterizaciyu en ta en i en U prostomu algoritmi dlya aglomerativnoyi klasterizaciyi vprovadzhennya inshoyi shemi zv yaznostej mozhe buti vikonano prosto za dopomogoyu inshoyi formuli dlya obchislennya mizhklasternih vidstanej v algoritmi U navedenomu vishe opisi algoritmu formulu yaku potribno vidkoriguvati vidileno zhirnim shriftom Odnak bilsh efektivni algoritmi taki yak opisanij nizhche ne poshiryuyutsya na vsi shemi zv yaznostej odnakovo Porivnyannya dendrogram otrimanih riznimi metodami klasterizaciyi dlya odniyeyi matrici vidstanej Odnozv yazna klasterizaciyi en Serednozv yazna klasterizaciyu en Serednozv yazna klasterizaciyu en Shvidshi algoritmiNayivnij algoritm odnozv yaznoyi klasterizaciyi prostij dlya rozuminnya ale povilnij i maye chasovu skladnist O n 3 displaystyle O n 3 U 1973 r R Sibson zaproponuvav algoritm z chasovoyu skladnistyu O n 2 displaystyle O n 2 i skladnist prostoru O n displaystyle O n obidva optimalni vidomi yak SLINK Algoritm SLINK predstavlyaye klasterizaciyu na mnozhini n displaystyle n pronumerovanih elementiv za dvoma funkciyami Obidvi ci funkciyi viznachayutsya shlyahom poshuku najmenshogo klastera C displaystyle C yakij mistit obidva elementi i displaystyle i i prinajmni odin element iz bilshim nomerom Persha funkciya p displaystyle pi vidobrazhaye element i displaystyle i do elementa z najbilshim nomerom u klasteri C displaystyle C Druga funkciya l displaystyle lambda vidobrazhaye element i displaystyle i do vidstani pov yazanoyi zi stvorennyam klastera C displaystyle C Zberigannya cih funkcij u dvoh masivah yaki vidobrazhayut kozhen nomer elementa v jogo funkcionalnomu znachenni zajmaye u pamyati O n displaystyle O n miscya i ciyeyi informaciyi dostatno dlya viznachennya samoyi klasterizaciyi Yak pokazuye Sibson koli novij element dodayetsya do mnozhini elementiv onovleni funkciyi sho predstavlyayut novu klasterizaciyu z odnim zv yazkom dlya dopovnenoyi mnozhini predstavlenu takim zhe chinom mozhut buti pobudovani na osnovi staroyi klasterizaciyi v chasi O n displaystyle O n Algoritm SLINK potim perebiraye elementi odin za odnim dodayuchi yih do predstavlennya klasterizaciyi Alternativnij algoritm sho pracyuye v tih samih optimalnih chasovih i prostorovih mezhah zasnovanij na ekvivalentnosti mizh nayivnim algoritmom i algoritmom Kruskala dlya minimalnih kistyakovih derev Zamist vikoristannya algoritmu Kruskala mozhna vikoristati algoritm Prima u variaciyi bez binarnih kup sho potrebuye chasu O n 2 displaystyle O n 2 i prostoru O n displaystyle O n dlya pobudovi minimalnogo kistyakovogo dereva ale ne klasterizaciyi iz zadanih elementiv i vidstanej Potim zastosuvannya algoritmu Kruskala do rozridzhenogo grafa utvorenogo rebrami minimalnogo kistyakovogo dereva stvoryuye samu klasterizaciyu za dodatkovij chas O n log n displaystyle O n log n i z vikoristannyam prostoru O n displaystyle O n Div takozhKlasternij analiz en Iyerarhichna klasterizaciya Molekulyarnij godinnik Metod priyednannya susidiv en en PrimitkiEveritt B 2011 Cluster analysis Chichester West Sussex U K Wiley ISBN 9780470749913 Numerical Ecology Developments in Environmental Modelling T 20 vid 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 PosilannyaZv yaznosti yaki vikoristovuyutsya v Matlab