Analiza clusterelor în mineritul datelor: Clustering bazat pe conectivitate (Clustering ierarhic)

Clusteringul bazată pe conectivitate, cunoscut și sub denumirea de clustering ierarhic, se bazează pe ideea de bază că obiectele sunt mai mult legate de obiectele din apropiere decât de obiectele aflate la distanță. Acești algoritmi conectează „obiecte” pentru a forma „clustere” pe baza distanței lor. Un cluster poate fi descris în mare măsură prin distanța maximă necesară pentru a conecta părți ale clusterului. La diferite distanțe, se vor forma clustere diferite, care pot fi reprezentate folosind o dendrogramă, care explică de unde provine denumirea comună „clustering ierarhic”: acești algoritmi nu oferă o singură partiționare a setului de date, ci oferă o ierarhie extinsă de clustere care se contopesc între ele la anumite distanțe. Într-o dendrogramă, axa y marchează distanța la care clusterele se îmbină, în timp ce obiectele sunt plasate de-a lungul axei x, astfel încât clusterele să nu se amestece.

Clusteringul bazat pe conectivitate este o întreagă familie de metode care diferă prin modul în care sunt calculate distanțele. În afară de alegerea obișnuită a funcțiilor de distanță, utilizatorul trebuie să decidă și criteriul de conectare (deoarece un cluster este format din mai multe obiecte, există mai mulți candidați pentru a calcula distanța până la) de utilizat. Opțiunile populare sunt cunoscute sub denumirea de clustering cu o singură legătură (minimum de distanțe ale obiectelor), clustering cu legături complete (maximum de distanțe ale obiectelor) sau UPGMA („Unweighted Pair Group Method with Arithmetic Mean”, cunoscut și sub denumirea de clustering cu legături medii). În plus, gruparea ierarhică poate fi aglomerativă (începând cu elemente individuale și agregându-le în clustere) sau divizivă (începând cu setul complet de date și împărțindu-l în partiții).

Aceste metode nu vor produce o partiționare unică a setului de date, ci o ierarhie din care utilizatorul trebuie să aleagă clustere adecvate. Ele nu sunt foarte robuste față de valorile aberante, care fie vor apărea drept clustere suplimentare, fie chiar vor provoca fuziunea altor clustere (cunoscut sub numele de „fenomen de înlănțuire”, în special cu gruparea cu o singură legătură). În cazul general, complexitatea este O(n³) pentru clustering aglomerativ și O(2^n-1) pentru clustering divizibil, ceea ce le face prea lente pentru seturi de date mari. Pentru unele cazuri speciale, sunt cunoscute metode eficiente optime (de complexitate O(n²)): SLINK pentru o singură legătură și CLINK pentru gruparea cu conexiuni complete. În comunitatea de minerit a datelor, aceste metode sunt recunoscute ca o bază teoretică a analizei cluster, dar adesea considerate învechite. Cu toate acestea, au fost o inspirație pentru multe metode ulterioare, cum ar fi clusteringul bazată pe densitate.

Exemple de grupări de legături

Legătura unică pe datele gaussiene. La 35 de clustere, cel mai mare cluster începe să se fragmenteze în părți mai mici, în timp ce înainte era încă conectat la al doilea ca mărime datorită efectului de legătură unică.

Legătura unică pe clustere bazate pe densitate. S-au extras 20 de clustere, dintre care majoritatea conțin elemente unice, deoarece gruparea de legături nu are o noțiune de „zgomot”.