Clustering ierarhic (de asemenea, algoritmi de clustering grafic și analiza cluster ierarhică ) este un set de algoritmi de ordonare a datelor care vizează crearea unei ierarhii ( arborele ) de clustere imbricate. Există două clase de metode de grupare ierarhică:
Algoritmii de grupare ierarhică presupun că setul de obiecte analizat este caracterizat de un anumit grad de conectivitate. În funcție de numărul de caracteristici, uneori se disting metodele monotetice și politetice de clasificare. La fel ca majoritatea modalităților vizuale de reprezentare a dependențelor, graficele își pierd rapid vizibilitatea pe măsură ce crește numărul de clustere. Există o serie de programe specializate pentru construirea de grafice .
O dendrogramă este de obicei înțeleasă ca un arbore construit dintr-o matrice de măsuri de proximitate. Dendrograma vă permite să descrieți relația dintre obiecte dintr-un anumit set [1] . Crearea unei dendrograme necesită o matrice de similaritate (sau diferență ) care determină nivelul de similaritate între perechile de clustere. Metodele aglomerative sunt mai frecvent utilizate.
Pentru a construi o matrice de similaritate (diferență), este necesar să se stabilească o măsură de distanță între două clustere. Cele mai utilizate metode pentru determinarea distanței ( strategii de sortare în limba engleză ) [2] :
Pentru primele trei metode, există o formulă generală propusă de A. N. Kolmogorov pentru măsurile de similaritate [5] :
unde este un grup de două obiecte (clustere) și ; — obiectul (clusterul) cu care se caută asemănarea grupului specificat; este numărul de elemente din cluster ; este numărul de elemente din cluster . Pentru distanțe există o formulă similară Lance-Williams [6] .
Folosit pe scară largă în geobotanica și florărie . Ele sunt adesea numite pleiade de corelație [7] [8] [9] [10] .
Un caz deosebit este metoda cunoscută sub numele de metoda de construire a arborilor optimi (dendrite) , care a fost propusă de matematicianul școlii din Lviv Hugo Steinhaus [11] , ulterior metoda a fost dezvoltată de matematicienii școlii taxonomice din Wroclaw [12] . De asemenea, dendritele nu ar trebui să formeze cicluri. Puteți utiliza parțial arcuri direcționate de grafice utilizând măsuri suplimentare de includere (măsuri de similaritate asimetrică).
Metoda „diagonalizării” matricei diferențelor și reprezentării grafice a clusterelor de-a lungul diagonalei principale a matricei diferențelor (diagrama lui Czekanowski) a fost propusă pentru prima dată de Jan Czekanowski în 1909 [13] . Iată o descriere a metodologiei:
Esența acestei metode constă în faptul că întreaga amplitudine a valorilor de similaritate obținute este împărțită într-un număr de clase, iar apoi în matricea valorilor de similaritate aceste valori sunt înlocuite cu umbrire diferită pentru fiecare clasă și, de obicei, umbrirea mai întunecată este folosită pentru clasele de similaritate mai înalte. Apoi, schimbând ordinea descrierilor în tabel, se asigură că urmează mai multe descrieri similare [14]
Să dăm un exemplu ipotetic de obținere a diagramei de mai sus. Baza metodei este construirea unei matrice de închidere tranzitivă [15] .
Pentru a construi o matrice de închidere tranzitivă, să luăm o matrice de similaritate simplă și să o înmulțim singur:
,unde este elementul de la intersecția rândului -lea și coloanei -lea din noua (a doua) matrice obținută după prima iterație; este numărul total de rânduri (coloane) din matricea de similaritate. Această procedură trebuie continuată până când matricea devine idempotentă (adică auto-similară): , unde n este numărul de iterații.
Apoi, transformăm matricea în așa fel încât valorile numerice apropiate să fie în apropiere. Dacă fiecărei valori numerice i se atribuie o culoare sau o nuanță de culoare (ca și în cazul nostru), atunci obținem diagrama clasică Czekanowski. În mod tradițional, o culoare mai închisă corespunde unei asemănări mai mari, iar o culoare mai deschisă corespunde uneia mai mici. În aceasta, este similar cu harta termică pentru matricea distanțelor .
Învățare automată și extragerea datelor | |
---|---|
Sarcini | |
Învățarea cu un profesor | |
analiza grupului | |
Reducerea dimensionalității | |
Prognoza structurală | |
Detectarea anomaliilor | |
Modele grafice probabilistice | |
Rețele neuronale | |
Consolidarea învățării |
|
Teorie | |
Reviste și conferințe |
|