www.wikidata.uk-ua.nina.az

Однозв язна кластеризація У статистиці однозв язна кластеризація є одним із методів ієрархічної кластеризації Цей метод

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

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

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

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

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

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

Математично функція зв'язності — відстань D(X, Y) між кластерами X і Y — описується виразом

де X і Y — будь-які дві множини елементів, які розглядаються як кластери, а d(x, y) позначає відстань між двома елементами x і y.

Наївний алгоритм ред.

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

Алгоритм однозв'язної кластеризації складається з наступних кроків:

  1. Почніть з кластеризації, у якій кожен елемент належить окремому кластеру. Вона має рівень і порядковий номер .
  2. Знайдіть найбільш схожу пару кластерів у поточній кластеризації, скажімо пару , відповідно до функції відстані , де мінімум береться по всім парам кластерів у поточній кластеризації.
  3. Збільшити порядковий номер: . Об'єднати кластери і в один кластер для формування наступної кластеризації . Встановіть рівень цієї кластеризації на .
  4. Оновити матрицю близкості , шляхом видалення рядків і стовпців, що відповідають кластерам і і додавання рядка та стовпця, що відповідають новосформованому кластеру. Близькість між новим кластером позначена і старим кластером визначається як .
  5. Якщо всі об'єкти знаходяться в одному кластері, зупиніться. Інакше перейдіть до кроку 2.

Приклад ред.

Цей реальний приклад базується на матриці генетичної відстані JC69[en], обчислений на основі порівняння послідовності 5S рибосомної РНК п'яти бактерій: Bacillus subtilis (), Bacillus stearothermophilus (), Lactobacillus viridescens[en] (), Acholeplasma modicum[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

Тож об'єднуємо кластери і .

Нехай позначає (кореневий) вузол, до якого приєднані і . З'єднання гілок і до мають такі довжини:

Виводимо довжину гілки, що залишилася:

Однозв'язна дендрограма ред.

Дані однозв'язної дендрограми 5S

Дендрограма готова. Вона ультраметрична, тому що всі елементи (, , , , і ) знаходяться на однаковій відстані від :

Таким чином, дендрограма має корінь , як найглибший вузол.

Інші зв'язності ред.

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

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

Порівняння дендрограм, отриманих різними методами кластеризації для однієї матриці відстаней.
Однозв'язна кластеризації Повнозв'язна кластеризація[en] Середньозв'язна кластеризацію: WPGMA[en] Середньозв'язна кластеризацію: UPGMA[en]

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

Наївний алгоритм однозв'язної кластеризації простий для розуміння, але повільний і має часову складність . У 1973 р. Р. Сібсон запропонував алгоритм з часовою складністю і складність простору (обидва оптимальні), відомі як SLINK. Алгоритм SLINK представляє кластеризацію на множині пронумерованих елементів за двома функціями. Обидві ці функції визначаються шляхом пошуку найменшого кластера , який містить обидва елементи  і принаймні один елемент із більшим номером. Перша функція, , відображає елемент  до елемента з найбільшим номером у кластері . Друга функція, , відображає елемент  до відстані, пов'язаної зі створенням кластера . Зберігання цих функцій у двох масивах, які відображають кожен номер елемента в його функціональному значенні, займає у памяті місця, і цієї інформації достатньо для визначення самої кластеризації. Як показує Сібсон, коли новий елемент додається до множини елементів, оновлені функції, що представляють нову кластеризацію з одним зв'язком для доповненої множини, представлену таким же чином, можуть бути побудовані на основі старої кластеризації в часі . Алгоритм SLINK потім перебирає елементи один за одним, додаючи їх до представлення кластеризації.

Альтернативний алгоритм, що працює в тих самих оптимальних часових і просторових межах, заснований на еквівалентності між наївним алгоритмом і алгоритмом Крускала для мінімальних кістякових дерев. Замість використання алгоритму Крускала можна використати алгоритм Прима у варіації без бінарних куп, що потребує часу і простору для побудови мінімального кістякового дерева (але не кластеризації) із заданих елементів і відстаней. Потім застосування алгоритму Крускала до розрідженого графа, утвореного ребрами мінімального кістякового дерева, створює саму кластеризацію за додатковий час і з використанням простору .

Див. також ред.

Примітки ред.

  1. Everitt, Brian (2011). Cluster analysis. Chichester, West Sussex, U.K: Wiley. ISBN 9780470749913.  Проігноровано невідомий параметр |name-list-style= (довідка)
  2. Numerical Ecology. Developments in Environmental Modelling 20 (вид. Second English). Amsterdam: Elsevier. 1998. 
  3. Collection of published 5S, 5.8S and 4.5S ribosomal RNA sequences. Nucleic Acids Research. 14 Suppl (Suppl): r1–59. 1986. PMC 341310. PMID 2422630. doi:10.1093/nar/14.suppl.r1.  Проігноровано невідомий параметр |vauthors= (довідка)
  4. Phylogenetic analysis using ribosomal RNA. Methods in Enzymology 164: 793–812. 1988. PMID 3241556. doi:10.1016/s0076-6879(88)64084-5.  Проігноровано невідомий параметр |vauthors= (довідка)
  5. Murtagh, Fionn; Contreras, Pedro (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.  Проігноровано невідомий параметр |name-list-style= (довідка)
  6. SLINK: an optimally efficient algorithm for the single-link cluster method. The Computer Journal (British Computer Society) 16 (1): 30–34. 1973. doi:10.1093/comjnl/16.1.30.  Проігноровано невідомий параметр |vauthors= (довідка)
  7. Gan, Guojun (2007). Data clustering : theory, algorithms, and applications. Philadelphia, Pa. Alexandria, Va: SIAM, Society for Industrial and Applied Mathematics American Statistical Association. ISBN 9780898716238.  Проігноровано невідомий параметр |name-list-style= (довідка)
  8. Minimum spanning trees and single linkage cluster analysis. Journal of the Royal Statistical Society, Series C 18 (1): 54–64. 1969. JSTOR 2346439. MR 0242315. doi:10.2307/2346439.  Проігноровано невідомий параметр |vauthors= (довідка).

Посилання ред.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
U statistici odnozv yazna klasterizaciya ye odnim iz metodiv iyerarhichnoyi klasterizaciyi Cej metod zasnovanij na grupuvanni klasteriv za principom znizu vgoru 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 1 Zmist 1 Oglyad metodiv aglomeracijnoyi klasterizaciyi 2 Nayivnij algoritm 3 Priklad 3 1 Pershij krok 3 2 Drugij krok 3 3 Zaklyuchnij krok 3 4 Odnozv yazna dendrograma 4 Inshi zv yaznosti 5 Shvidshi algoritmi 6 Div takozh 7 Primitki 8 PosilannyaOglyad metodiv aglomeracijnoyi klasterizaciyi red Na 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 dendrogramu en yaka pokazuye poslidovnist ob yednannya klasteriv i vidstani na yakih vidbuvalosya kozhne zlittya 2 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 nbsp 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 algoritm red Nastupnij 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 nbsp ye matriceyu blizkosti D displaystyle D nbsp ta mistit usi vidstani d i j displaystyle d i j nbsp Klasterizaciyam prisvoyuyutsya poryadkovi nomeri 0 1 n 1 displaystyle 0 1 ldots n 1 nbsp i L k displaystyle L k nbsp ce riven k displaystyle k nbsp yi klasterizaciyi Klaster z poryadkovim nomerom m poznachayetsya m a blizkist mizh klasterami r displaystyle r nbsp i s displaystyle s nbsp poznachayetsya yak d r s displaystyle d r s nbsp 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 nbsp i poryadkovij nomer m 0 displaystyle m 0 nbsp Znajdit najbilsh shozhu paru klasteriv u potochnij klasterizaciyi skazhimo paru r s displaystyle r s nbsp vidpovidno do funkciyi vidstani d r s min d i j displaystyle d r s min d i j nbsp de minimum beretsya po vsim param klasteriv u potochnij klasterizaciyi Zbilshiti poryadkovij nomer m m 1 displaystyle m m 1 nbsp Ob yednati klasteri r displaystyle r nbsp i s displaystyle s nbsp v odin klaster dlya formuvannya nastupnoyi klasterizaciyi m displaystyle m nbsp Vstanovit riven ciyeyi klasterizaciyi na L m d r s displaystyle L m d r s nbsp Onoviti matricyu blizkosti D displaystyle D nbsp shlyahom vidalennya ryadkiv i stovpciv sho vidpovidayut klasteram r displaystyle r nbsp i s displaystyle s nbsp i dodavannya ryadka ta stovpcya sho vidpovidayut novosformovanomu klasteru Blizkist mizh novim klasterom poznachena r s displaystyle r s nbsp i starim klasterom k displaystyle k nbsp 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 nbsp Yaksho vsi ob yekti znahodyatsya v odnomu klasteri zupinitsya Inakshe perejdit do kroku 2 Priklad red Cej realnij priklad bazuyetsya na matrici genetichnoyi vidstani JC69 en obchislenij na osnovi porivnyannya poslidovnosti 5S ribosomnoyi RNK p yati bakterij Bacillus subtilis a displaystyle a nbsp Bacillus stearothermophilus b displaystyle b nbsp Lactobacillus viridescens en c displaystyle c nbsp Acholeplasma modicum en d displaystyle d nbsp i Micrococcus luteus e displaystyle e nbsp 3 4 Pershij krok red Persha klasterizaciyaPripustimo sho u nas p yat elementiv a b c d e displaystyle a b c d e nbsp i nastupna matricya D 1 displaystyle D 1 nbsp poparnih vidstanej mizh nimi a b c d ea 0 17 21 31 23b 17 0 30 34 21c 21 30 0 28 39d 31 34 28 0 43e 23 21 39 43 0U comu prikladi D 1 a b 17 displaystyle D 1 a b 17 nbsp ye najmenshim znachennyam D 1 displaystyle D 1 nbsp tomu mi grupuyemo elementi a i b Ocinka dovzhini pershoyi gilkiNehaj 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 nbsp 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 nbsp div kincevu dendrogramu Pershe onovlennya matrici vidstanejPotim mi perehodimo do onovlennya pochatkovoyi matrici blizkosti D 1 displaystyle D 1 nbsp u novu matricyu blizkosti D 2 displaystyle D 2 nbsp div nizhche mi zmenshuyemo rozmir matrici na odin ryadok i odin stovpec cherez klasterizaciyu a z b Znachennya v D 2 displaystyle D 2 nbsp vidileni zhirnim shriftom vidpovidayut novim vidstanyam rozrahovanim shlyahom zberezhennya minimalnoyi vidstani mizh kozhnim elementom pershogo klastera a b displaystyle a b nbsp 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 nbsp Znachennya vidileni kursivom v D 2 displaystyle D 2 nbsp zalishayutsya bez zmin pri onovlenni matrici oskilki voni vidpovidayut vidstanyam mizh elementami yaki ne berut uchast u pershomu klasteri Drugij krok red Druga klasterizaciyaTeper mi povtoryuyemo tri poperedni diyi pochinayuchi z novoyi matrici vidstani D 2 displaystyle D 2 nbsp a b c d e a b 0 21 31 21c 21 0 28 39d 31 28 0 43e 21 39 43 0Tut D 2 a b c 21 displaystyle D 2 a b c 21 nbsp i D 2 a b e 21 displaystyle D 2 a b e 21 nbsp ye najmenshimi znachennyami D 2 displaystyle D 2 nbsp tomu mi priyednuyemosya do klasteru a b displaystyle a b nbsp element c i element e Ocinka dovzhini drugoyi gilkiNehaj v poznachaye vuzol do yakogo a b displaystyle a b nbsp 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 nbsp 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 nbsp div kincevu dendrogramu Druge onovlennya matrici vidstaniPotim mi perehodimo do onovlennya matrici D 2 displaystyle D 2 nbsp u novu matricyu vidstanej D 3 displaystyle D 3 nbsp div nizhche spochatku zmenshuyemo rozmir matrici na dva ryadki ta dva stovpci cherez klasterizaciyu a b displaystyle a b nbsp 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 nbsp Zaklyuchnij krok red Pidsumkova matricya D 3 displaystyle D 3 nbsp ce a b c e d a b c e 0 28d 28 0Tozh ob yednuyemo klasteri a b c e displaystyle a b c e nbsp i d displaystyle d nbsp Nehaj r displaystyle r nbsp poznachaye korenevij vuzol do yakogo priyednani a b c e displaystyle a b c e nbsp i d displaystyle d nbsp Z yednannya gilok a b c e displaystyle a b c e nbsp i d displaystyle d nbsp do r displaystyle r nbsp 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 nbsp 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 nbsp Odnozv yazna dendrograma red nbsp Dani odnozv yaznoyi dendrogrami 5SDendrograma gotova Vona ultrametrichna tomu sho vsi elementi a displaystyle a nbsp b displaystyle b nbsp c displaystyle c nbsp e displaystyle e nbsp i d displaystyle d nbsp znahodyatsya na odnakovij vidstani vid r displaystyle r nbsp 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 nbsp Takim chinom dendrograma maye korin r displaystyle r nbsp yak najglibshij vuzol Inshi zv yaznosti red Nayivnij 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 povnozv yaznu klasterizaciyu en serednozv yaznu klasterizaciyu UPGMA en ta WPGMA en i metod Uorda 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 nbsp nbsp nbsp nbsp Odnozv yazna klasterizaciyi Povnozv yazna klasterizaciya en Serednozv yazna klasterizaciyu WPGMA en Serednozv yazna klasterizaciyu UPGMA en Shvidshi algoritmi red Nayivnij algoritm odnozv yaznoyi klasterizaciyi prostij dlya rozuminnya ale povilnij i maye chasovu skladnist O n 3 displaystyle O n 3 nbsp 5 U 1973 r R Sibson zaproponuvav algoritm z chasovoyu skladnistyu O n 2 displaystyle O n 2 nbsp i skladnist prostoru O n displaystyle O n nbsp obidva optimalni vidomi yak SLINK Algoritm SLINK predstavlyaye klasterizaciyu na mnozhini n displaystyle n nbsp pronumerovanih elementiv za dvoma funkciyami Obidvi ci funkciyi viznachayutsya shlyahom poshuku najmenshogo klastera C displaystyle C nbsp yakij mistit obidva elementi i displaystyle i nbsp i prinajmni odin element iz bilshim nomerom Persha funkciya p displaystyle pi nbsp vidobrazhaye element i displaystyle i nbsp do elementa z najbilshim nomerom u klasteri C displaystyle C nbsp Druga funkciya l displaystyle lambda nbsp vidobrazhaye element i displaystyle i nbsp do vidstani pov yazanoyi zi stvorennyam klastera C displaystyle C nbsp Zberigannya cih funkcij u dvoh masivah yaki vidobrazhayut kozhen nomer elementa v jogo funkcionalnomu znachenni zajmaye u pamyati O n displaystyle O n nbsp 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 nbsp Algoritm SLINK potim perebiraye elementi odin za odnim dodayuchi yih do predstavlennya klasterizaciyi 6 7 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 nbsp i prostoru O n displaystyle O n nbsp 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 nbsp i z vikoristannyam prostoru O n displaystyle O n nbsp 8 Div takozh red Klasternij analiz Povnozv yazna klasterizaciya en Iyerarhichna klasterizaciya Molekulyarnij godinnik Metod priyednannya susidiv UPGMA en WPGMA en Primitki red Everitt Brian 2011 Cluster analysis Chichester West Sussex U K Wiley ISBN 9780470749913 Proignorovano nevidomij parametr name list style dovidka Numerical Ecology Developments in Environmental Modelling 20 vid Second English Amsterdam Elsevier 1998 Collection of published 5S 5 8S and 4 5S ribosomal RNA sequences Nucleic Acids Research 14 Suppl Suppl r1 59 1986 PMC 341310 PMID 2422630 doi 10 1093 nar 14 suppl r1 Proignorovano nevidomij parametr vauthors dovidka Phylogenetic analysis using ribosomal RNA Methods in Enzymology 164 793 812 1988 PMID 3241556 doi 10 1016 s0076 6879 88 64084 5 Proignorovano nevidomij parametr vauthors dovidka Murtagh Fionn Contreras Pedro 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 Proignorovano nevidomij parametr name list style dovidka SLINK an optimally efficient algorithm for the single link cluster method The Computer Journal British Computer Society 16 1 30 34 1973 doi 10 1093 comjnl 16 1 30 Proignorovano nevidomij parametr vauthors dovidka Gan Guojun 2007 Data clustering theory algorithms and applications Philadelphia Pa Alexandria Va SIAM Society for Industrial and Applied Mathematics American Statistical Association ISBN 9780898716238 Proignorovano nevidomij parametr name list style dovidka Minimum spanning trees and single linkage cluster analysis Journal of the Royal Statistical Society Series C 18 1 54 64 1969 JSTOR 2346439 MR 0242315 doi 10 2307 2346439 Proignorovano nevidomij parametr vauthors dovidka Posilannya red Zv yaznosti yaki vikoristovuyutsya v Matlab Otrimano z https uk wikipedia org w index php title Odnozv 27yazna klasterizaciya amp oldid 40589056