Universitatea babeş-bolyai cluj-napoca

2.3 Clasificarea tehnicilor de clustering

Există numeroase tipuri de clustering, bazate pe diferite metode, fiecare dintre acestea putând genera ca și rezultat diferite moduri de a grupa datele. O posibilă clasificare este aceea de a împărți algoritmii de clustering în două mari categorii: tehnici de clustering bazate pe partiționarea datelor și tehnici de clustering bazate pe metode ierarhice. De asemenea, există și algoritmi mai noi care se pot grupa în algoritmi bazați pe densitate, bazați pe grid sau bazați pe modele. Clasificarea algoritmilor de clustering nu este simplă, deseori se ajunge la concluzia că unele categorii de algoritmi se suprapun. Pe lângă tehnicile enumerate mai sus, se pot aminti: algoritmi de clustering bazați pe constrângeri, bazați pe grafe, algoritmi scalabili, algoritmi speciali pentru date cu multe dimensiuni. În cadrul învățării automate, au apărut și metode evloutive de clustering și unele care folosesc rețele neuronale. [6]

Algoritmii partiționali consideră că setul de date trebuie grupat in k clusteri partiționându-l, iar numărul k se pretinde a fi cunoscut de la început. În cadrul acestei metode se mai poate folosi și tehnica relocării iterative prin care se încearcă îmbunătățirea partiționării prin mutarea obiectelor dintr-un grup în altul. Cele mai cunoscute metode partiționale sunt: K-Means – care presupune calcularea centrului de greutate al unui cluster si asignarea unei entități acelui cluster în funcție de o anumită metrică, K-Medoids – presupune alegerea unui element reprezentativ (medoid) pentru fiecare cluster, la fiecare iterație, PAM (Partitioning Around Medoids), CLARA (Clustering Large Applications), CLARANS (Clustering Large Applications based upon RANdomized Search). [13] În timp ce algoritmii ierarhici construiesc clustere treptat, algoritmii de partiţionare învaţă clustere direct. În acest sens, ei încearcă să descopere clusteri fie prin relocalizarea iterativă a punctelor între subseturi, sau încercă să identifice clusterii ca şi zone foarte populate cu date.

Algoritmii ierarhici structurează setul de obiecte creând o ierarhie. Există două tipuri de abordări: aglomerativă și divizivă. În cadrul abordării aglomerative, sau “bottom-up”, fiecare obiect este asignat unui cluster, iar apoi clusterii se unesc pe baza unor măsuri de similaritate până când o anumită condiție este îndeplinită și s-au găsit un anumit număr de clusteri. Abordarea divizivă este una de tipul “top-down”, unde la început se consider că toate entitățile aparțin unui singur cluster, iar la fiecare iterație care urmează, fiecare cluster se divide în clusteri mai mici până când o condiție e satisfăcută.

Metoda de divizare ierarhică descoperă clustere succesive, utilizând clusterii deja formați, construind o ierarhie și producând o diagramă sub formă de arbore, numită dendogramă, și nu doar o simplă partiție a obiectelor.[7] Astfel, clusterii noi sunt formați prin realocarea apartenențelor unui punct, la fiecare pas, pe baza unei măsuri de similaritate, prin urmare se generează o ierarhie de clusteri imbricați. Aceste tehnici au ca avantaj simplitatea lor conceptuală și computațională, însă ele par potrivite mai ales atunci când datele privite ca structuri sunt regulate. [10]

Pentru acest caz nu este necesară cunoașterea de dinainte a numărului de clustere, dar se poate alege o anumită condiție de terminare.

Cele trei tipuri de clustering ierarhic sunt:

1. 
   Aglomerativ: în care perechi de obiecte/clustere sunt conectate succesiv, producând clustere mai mari.
   

Metoda constă în:

1. 
   Plasarea fiecărui obiect în propriul său cluster.
   
2. 
   La fiecare pas se unesc cele mai asemănătoare două clustere până când se obține unul singur sau o anumită condiție de terminare este îndeplinită.
   

2. 
   Diviziv: toate obiectele sunt plasate inițial într-un singur cluster, apoi succesiv sunt împărțite în grupuri separate.
   

Metoda constă în:

1. 
   Toate obiectele sunt considerate ca făcând parte din același unic cluster.
   
2. 
   La fiecare pas se divide clusterul cel mai distinctiv în clustere mai mici, procedându-se astfel până când se obține un anumit număr de clustere sau o anumită condiție de terminare este îndeplinită.
   

3. 
   Conceptual: inițial se consideră un nod rădăcină gol, obiectele fiind adăugate unul câte unul, utilizând clase (grupuri) deja existente, creând noi clase sau combinând și divizând clase existente. [7]
   

Algoritmii bazați pe densitatea datelor se leagă de conectivitatea care poate exista între entități și densitatea acestora dintr-o anumită regiune. În acest caz este folosită o funcție de densitate care încearcă modelarea legii de distribuție a datelor. Această metodă are ca avantaj modelarea unor clusteri de orice formă. Metoda de formare a clusterilor bazată pe grid nu este chiar una nouă, aceasta se poate modifica astfel încât să se rezume la un algoritm de clustering ierarhic, partițional sau bazat pe densitate. Ea presupune segmentarea spațiului în care se află datele în zone regulate, obiectele plasându-se pe un grid multi-dimensional.

Clusteringul bazat pe grafe în care mulțimea inițială de entități care urmează a fi împărțită în clusteri este privită ca o mulțime de noduri, cu ponderile muchiilor obținute pe baza aplicării unor măsuri de similaritate între perechile de noduri. Astfel, clasificarea se va face pe baza unei măsuri de conectivitate între anumite grupuri de noduri, iar strategia de clasificare se poate reduce la determinarea unui arbore minimal de acoperire și eliminarea unor muchii pentru obținerea de subgrafe. La final, partițiile rezultate vor fi reprezentate de subgrafele determinate. [10]

După tipul de apartenență a datelor la un anumit cluster, putem distinge: clustering de tip exact (Hard Clustering), în cadrul căruia fiecărei entități i se asociază o anumită etichetă ce reprezintă clusterul din care face parte, și clustering de tip Fuzzy, unde fiecărei entități i se asociază un grad sau o probabilitate de a face parte dintr-un anumit grup. În acest ultim caz, o entitate poate aparține mai multor clusteri.