Evoluții recente în analiza clusterelor din analitica

În ultimii ani s-au depus eforturi considerabile pentru îmbunătățirea performanței algoritmilor existenți. Printre aceștia se numără CLARANS (Ng și Han, 1994) și BIRCH (Zhang și colab., 1996). Odată cu necesitatea recentă de a procesa seturi de date din ce în ce mai mari (cunoscute și sub denumirea de megadate sau big data), dorința de a schimba semnificația semantică a clusterelor generate pentru performanță a crescut. Acest lucru a condus la dezvoltarea unor metode de pre-clustering, cum ar fi canopy clustering, care poate procesa seturi de date uriașe în mod eficient, dar „clusterele” rezultate sunt doar o pre-partiționare brută a setului de date pentru a analiza apoi partițiile cu metode mai lente existente, cum ar fi ca clustering pe bază de medii k. Au fost încercate diverse alte abordări ale clutserelor, cum ar fi clustering pe bază de granulație.

Pentru datele cu dimensiuni mari, multe dintre metodele existente eșuează din cauza blestemului dimensionalității, care face ca anumite funcții de distanță să fie problematice în spațiile cu dimensiuni mari. Acest lucru a condus la noi algoritmi de clustering pentru date cu dimensiuni mari care se concentrează pe clustering subspațial (unde se folosesc doar unele atribute, iar modelele de cluster includ atributele relevante pentru cluster) și clustering de corelație care caută, de asemenea, clusterele subspațiului rotat arbitrar („corelat”), care pot fi modelate oferind o corelație a atributelor lor. Exemple de astfel de algoritmi de clustering sunt CLIQUE și SUBCLU.

Ideile din metodele de clustering bazate pe densitate (în special familia de algoritmi DBSCAN/OPTICS) au fost adoptate pentru clusteringul subspațial (HiSC, clustering subspațial ierarhic și DiSH) și clusteringul de corelație (HiCO, clustering de corelație ierarhică, 4C folosind „conectivitate de corelație” și ERiC explorează clustere de corelație ierarhice bazate pe densitate).

Au fost propuse mai multe sisteme de clustering diferite bazate pe informații reciproce. Una este metrica variației informației a lui Marina Meilă; altul oferă clustering ierarhic. Folosind algoritmi genetici, o gamă largă de funcții de potrivire diferite pot fi optimizate, inclusiv informații reciproce. De asemenea, algoritmii de transmitere a mesajelor, o dezvoltare recentă în informatică și fizica statistică, au condus la crearea de noi tipuri de algoritmi de clustering.

Alte metode

Schema algoritmică secvențială de bază (BSAS)

Evaluare și apreciere

Evaluarea rezultatelor clusteringului este uneori denumită validare cluster.

Au existat mai multe sugestii pentru o măsură a similitudinii între două clustere. O astfel de măsură poate fi utilizată pentru a compara cât de bine performează diferiții algoritmi de clustering a datelor pe un set de date. Aceste măsuri sunt de obicei legate de tipul de criteriu luat în considerare la evaluarea calității unei metode de clustering.

Evaluare internă

Când un rezultat de clustering este evaluat pe baza datelor care au fost grupate în sine, aceasta se numește evaluare internă. Aceste metode atribuie, de obicei, cel mai bun punctaj algoritmului care produce clustere cu similaritate mare în cadrul unui cluster și similaritate scăzută între clustere. Un dezavantaj al utilizării criteriilor interne în evaluarea clusterului este că scorurile ridicate la o măsură internă nu duc neapărat la aplicații eficiente de regăsire a informațiilor. În plus, această evaluare este părtinitoare față de algoritmi care folosesc același model de cluster. De exemplu, gruparea k-Means optimizează în mod natural distanțele obiectelor, iar un criteriu intern bazat pe distanță va supraevalua probabil clusteringul rezultat.

Prin urmare, măsurile de evaluare internă sunt cele mai potrivite pentru a obține o perspectivă asupra situațiilor în care un algoritm funcționează mai bine decât altul, dar acest lucru nu înseamnă că un algoritm produce rezultate mai valide decât altul. Valabilitatea măsurată de un astfel de indice depinde de afirmația că acest tip de structură există în setul de date. Un algoritm conceput pentru un anumit tip de modele nu are nicio șansă dacă setul de date conține un set radical diferit de modele sau dacă evaluarea măsoară un criteriu radical diferit. De exemplu, gruparea k-means poate găsi numai clustere convexe, iar mulți indici de evaluare presupun clustere convexe. Pe un set de date cu clustere neconvexe, nici folosirea k-means, nici a unui criteriu de evaluare care presupune convexitatea nu este corectă.

Următoarele metode pot fi utilizate pentru a evalua calitatea algoritmilor de clustering pe baza criteriului intern:

Indicele Davies-Buldin

Indicele Davies-Bouldin poate fi calculat prin următoarea formulă:

DB = 1/n Σ_i=1ⁿmax_j≠i((σ_i + σ_j)/d(c_i,c_j))

unde n este numărul de clustere, c_x este centroidul clusterului x, σ_x este distanța medie a tuturor elementelor din cluster x la centroidul c_x și d(c_i, c_j) este distanța dintre centroizii c_i și c_j. Deoarece algoritmii care produc clustere cu distanțe mici intra-cluster (similaritate mare intra-cluster) și distanțe mari între cluster (asemănare scăzută între cluster) vor avea un indice Davies-Bouldin scăzut, algoritmul de clustering care produce o colecție de clustere cu cel mai mic indice Davies-Bouldin este considerat cel mai bun algoritm bazat pe acest criteriu.

Indicele Dunn

Indicele Dunn urmărește identificarea clusterelor dense și bine separate. Este definit ca raportul dintre distanța minimă între cluster și distanța maximă intracluster. Pentru fiecare partiție de cluster, indicele Dunn poate fi calculat prin următoarea formulă:

D = mini_1≤i<j≤nd(i,j)/max_1≤t≤nd'(k) ,

unde d(i,j) reprezintă distanța dintre clusterele i și j, iar d'(k) măsoară distanța intra-cluster a clusterului k. Distanța inter-cluster d(i,j) dintre două clustere poate fi orice număr de măsuri de distanță, cum ar fi distanța dintre centroizii clusterelor. În mod similar, distanța intra-cluster d'(k) poate fi măsurată într-o varietate de moduri, cum ar fi distanța maximă dintre orice pereche de elemente din grupul k. Întrucât criteriul intern caută clustere cu similaritate mare în interiorul clusterelor și similaritate redusă între clustere, algoritmii care produc clustere cu indice Dunn ridicat sunt mai de dorit.

Coeficientul de siluetă

Coeficientul de siluetă contrastează distanța medie față de elementele din același grup cu distanța medie față de elementele din alte grupuri. Obiectele cu o valoare mare a siluetei sunt considerate bine grupate, obiectele cu o valoare scăzută pot fi valori aberante. Acest index funcționează bine cu clusteringul k-means și este, de asemenea, utilizat pentru a determina numărul optim de clustere.

Evaluare externă

În evaluarea externă, rezultatele clusteringului sunt evaluate pe baza datelor care nu au fost utilizate pentru clustering, cum ar fi etichetele de clasă cunoscute și reperele externe. Astfel de repere constau dintr-un set de articole preclasificate, iar aceste seturi sunt adesea create de oameni (experți). Astfel, seturile de repere pot fi considerate ca un standard de aur pentru evaluare. Aceste tipuri de metode de evaluare măsoară cât de aproape este clusteringului de clasele de referință predeterminate. Cu toate acestea, s-a discutat recent dacă acest lucru este adecvat pentru date reale sau numai pentru seturi de date sintetice cu un adevăr de bază real, deoarece clasele pot conține structură internă, atributele prezente pot să nu permită separarea clusterelor sau clasele pot conține anomalii. În plus, din punctul de vedere al descoperirii cunoștințelor, reproducerea cunoștințelor cunoscute poate să nu fie neapărat rezultatul dorit. În scenariul special al clusteringului restrâns, în care metainformațiile (cum ar fi etichetele de clasă) sunt deja folosite în procesul de grupare, păstrarea informațiilor în scopuri de evaluare nu este banală.

O serie de măsuri sunt adaptate din variantele utilizate pentru evaluarea sarcinilor de clasificare. În loc de numărare de câte ori o clasă a fost atribuită corect unui singur punct de date (cunoscute sub numele de adevărate pozitive), astfel de metrici de numărare a perechilor evaluează dacă fiecare pereche de puncte de date care se află cu adevărat în același cluster este estimată a fi în același cluster.

Unele dintre măsurările de calitate ale unui algoritm de cluster folosind criterii externi includ:

Măsurarea Rand (William M. Rand 1971)

Indicele Rand calculează cât de similare sunt clusterele (returnate de algoritmul de clustering) cu clasificările de referință. De asemenea, se poate vedea indicele Rand ca o măsură a procentului de decizii corecte luate de algoritm. Poate fi calculat folosind următoarea formulă:

RI = (TP + TN)/(TP + FP + FN + TN)

unde TP este numărul de pozitive adevărate, TN este numărul de negative adevărate, FP este numărul de pozitive false și FN este numărul de negative false. O problemă cu indicele Rand este că falsele pozitive și falsele negative sunt ponderate în mod egal. Aceasta poate fi o caracteristică nedorită pentru unele aplicații de clustering. Măsurarea F abordează această problemă, la fel ca și indicele Rand ajustat în funcție de șansă.

Măsurarea F

Măsurarea F poate fi utilizată pentru a echilibra contribuția falselor negative prin ponderarea rapelului printr-un parametru β ≥ 0. Fie ca precizia și rapelul să fie definite după cum urmează:

P = TP/(TP + FP)

R = TP/(TP + FN)

unde P este rata de precizie și R este rata de rapel. Putem calcula măsura F folosind următoarea formulă:

F_β = (β² +1) • P • R/(β²• P + R)

Observați că atunci când β = 0, F₀ = P. Cu alte cuvinte, rapelul nu are niciun impact asupra măsurării F atunci când β = 0, iar creșterea β alocă o cantitate din ce în ce mai mare de pondere pentru rapel în măsurarea F finală.

Indicele Jaccard

Indicele Jaccard este folosit pentru a cuantifica asemănarea dintre două seturi de date. Indicele Jaccard ia o valoare între 0 și 1. Un indice de 1 înseamnă că cele două seturi de date sunt identice, iar un indice de 0 indică faptul că seturile de date nu au elemente comune. Indicele Jaccard este definit prin următoarea formulă:

J(A, B) = |A∩B|/|A∪B| = TP/(TP + FP + FN)

Acesta este pur și simplu numărul de elemente unice comune ambelor seturi împărțit la numărul total de elemente unice din ambele seturi.

Indicele Fowlkes-Mallows (E. B. Fowlkes & C. L. Mallows 1983)

Indicele Fowlkes-Mallows calculează asemănarea dintre clusterele returnate de algoritmul de clustering și clasificările de referință. Cu cât valoarea indicelui Fowlkes-Mallows este mai mare, cu atât clusterele și clasificările de referință sunt mai asemănătoare. Poate fi calculat folosind următoarea formulă:

FM = √(TP/(TP + FP) • TP/(TP + FN))

unde TP este numărul de pozitive adevărate, FP este numărul de pozitive false și FN este numărul de negative false. Indicele FM este media geometrică a preciziei și a rapelului P și R, în timp ce măsura F este media lor armonică. Mai mult, precizia și rapelul sunt cunoscute și sub numele de indici B¹ și B^II ai lui Wallace.

Informația mutuală este o măsură teoretică a informațiilor despre câte informații sunt partajate între un clustering și o clasificare bazată pe adevăr, care poate detecta o similitudine neliniară între două clustere. Informația mutuală ajustată este varianta corectată-pentru-șansă a acesteia, care are o părtinire redusă pentru diferitele numere de cluster.

Matricea confuziei poate fi utilizată pentru a vizualiza rapid rezultatele unui algoritm de clasificare (sau grupare). Aceasta arată cât de diferit este un cluster de clusterul standard de aur.

Referințe

Ng, R.T. and Han, J. (1994) Efficient and Effective Clustering Methods for Spatial Data Mining. In: Proceedings of the VLDB Conference, Santiago, 144-155.
Zhang, Y. E.; Parsons, C. M., 1996. Effects of overprocessing on the nutritional quality of peanut meal. Poult. Sci., 75 (4): 514-518