Clustering (gruparea) este o metodă de a analiza date obţinute prin măsurători. Aceasta ne permite să grupăm datele în clase şi să utilizăm aşa-numitele clase obţinute drept bază în învăţarea automată. De asemenea, aceasta oferă analizarea mai rapidă a măsurătorilor sau valori aproximative ale unor măsurători viitoare, prin extrapolare. În secţiunile care urmează vom încerca să acoperim subiectul referitor la gruparea datelor. Această tehnică este utilă în special atunci când avem de-a face cu cantităţi mari de date, un scenariu care nu este neobişnuit având în vedere explozia de date şi informaţii din zilele noastre.
Clustering este un proces care examinează o colecţie de "puncte" şi grupează aşa-numitele puncte în "clusters" (grupe) potrivit unor măsurători ale distanţei. Scopul principal al procesului de clustering (al grupării) este să se obţină o stare în care punctele din acelaşi cluster (aceeaşi grupare) să aibă o distanţă mică unul faţă de altul, iar punctele din grupe diferite să fie la o distanţă mare unele de altele. Definirea termenilor de distanţă "mare" şi "mică" depinde de domeniul în care se aplică clustering (gruparea).
Un exemplu de clustering într-un spaţiu bi-dimensional poate fi văzut în următoarea imagine:
Totuşi, probleme moderne de clustering implică spaţii euclidiene de dimensiuni foarte mari sau şi mai amuzant este cazul în care sunt implicate spaţii care nu sunt euclidiene, făcând astfel ca măsurarea distanţei să nu fie deloc intuitivă.
Un scenariu de clustering posibil în lumea reală poate fi nevoia de a grupa documente după subiectul lor, în baza existenţei unor cuvinte neobişnuite, comune în documente sau cerinţa de a grupa persoanele care merg la film după tipul filmelor care le plac, în contextul diverselor proceduri de afaceri.
Conceptul de distanţă este o măsură descrisă prin câteva proprietăţi principale. O măsură de distanţă este întotdeauna non-negativă (numai distanţa dintre un punct şi sine însuşi este zero), este simetrică (nu contează ordinea în care sunt luate în considerare punctele atunci când măsurăm distanţa dintre ele) şi trebuie să respecte inegalitatea triunghiului (distanţa de la X la Y la Z nu este niciodată mai mică decât distanţa care merge direct de la X la Z).
Există două tipuri de strategii de clustering: algoritmi ierarhici şi algoritmi point-assignment.
Algoritmii ierarhici încep cu fiecare punct în propriul său cluster, combină clusteri-i în funcţie de diferitele definiţii de "apropiere" şi se opreşte atunci când combinaţii suplimentare ar duce la formarea unor clustere indezirabile (de exemplu atunci când am ajuns la un număr predeterminat de cluster-e pentru domeniul nostru sau când un cluster rezultat are puncte care sunt împrăştiate pe o regiune mult prea mare).
În algoritmii de atribuire a punctelor, punctele sunt luate în considerare într-o anumită ordine şi fiecare dintre ele este atribuit cluster-ului în care se potriveşte cel mai bine. Aceasta este de obicei precedată de o fază scurtă în care se estimează cluster-ele iniţiale. Ocazional, variaţii ale acestor algoritmi combină sau separă cluster-ele sau permit punctelor să fie dezatribuite, dacă acestea se află prea departe de oricare dintre cluster-ele actuale, pentru a reduce zgomotul.
Acest "blestem" să referă la fenomenele diverse care apar în contextul unor cantități mari de informație atunci când analizăm şi organizăm datele în spaţii supra-dimensionale. Tema comună a acestor probleme este că atunci când dimensionalitatea creşte, volumul spaţiului se măreşte atât de repede încât datele disponibile devin împrăştiate. Această raritate este problematică pentru orice metodă care necesită relevanţă statistică. Pentru a obţine un rezultat corect şi de încredere din punct de vedere statistic, cantitatea de date necesară pentru a susţine rezultatul creşte deseori exponenţial cu dimensionalitatea. De exemplu, spaţiile euclidiene supra-dimensionale şi de asemenea spaţiile non-euclidiene au un număr de proprietăţi non-intuitive, cum ar fi faptul că aproape toate perechile de puncte sunt distanţate în mod egal unele de altele sau aproape oricare doi vectori sunt ortogonali.
Pentru spaţiile euclidiene, cluster-ing (gruparea) începe cu fiecare punct în propriul său cluster şi apoi cluster-e mai mari vor fi construite prin combinarea a două cluster-e mai mici. În acest scenariu trebuie să decidem dinainte cum vor fi reprezentate cluster-ele, cum vom alege pe care două clustere să le unim şi când vom înceta să mai combinăm cluster-ele. Algoritmul de bază este ilustrat în figura de mai jos:
Pentru spaţii non-euclidiene trebuie să utilizăm o măsurare a distanţei care este calculată din puncte cum ar fi Jaccard, cosinus sau edit distance. O restricţie în acest scenariu este aceea că nu putem să bazăm distanţele pe "locaţia" punctelor. O altă restricţie este că nu putem să reprezentăm un cluster prin centroidul său şi astfel trebuie să alegem unul dintre punctele cluster-ului drept reprezentant echivalent şi în mod ideal, acesta ar trebui să fie un punct apropiat de toate celelalte puncte ale cluster-ului, astfel încât într-un fel să se găsească în "centru". Un asemenea punct este numit un clustroid şi poate fi obţinut prin următoarele tehnici:
Vom prezenta doar doi algoritmi de point-assignment clustering în secţiunea următoare, dar pot exista variaţii în funcţie de cerinţele diferitelor domenii.
Algoritmul K-means - presupune un spaţiu euclidian şi de asemenea numărul clusterelor, k, este cunoscut dinainte. Se poate deduce valoarea lui k prin încercare şi eroare sau alte metode. Algoritmul de bază este ilustrat în figura de mai jos:
O variaţie a acestui algoritm este BFR (Bradley, Fayyad şi Reina), algoritm ce ne permite să executăm k-means pe datele care sunt prea mari pentru a încăpea în memoria principală. Aceasta presupune că forma cluster-ului trebuie să fie distribuită normal în jurul centroidului, de exemplu, axele cluster-ului trebuie să se alinieze cu axele spaţiului, presupunere ilustrată în figura următoare.
Algoritmul începe prin selectarea k puncte. Punctele din fişierul de date sunt citite pe bucăţi şi fiecare bucată trebuie să conţină suficient de puţine puncte astfel încât acestea să poată fi procesate în memoria principală. Algoritmul depozitează în memoria principală rezumate ale clusterelor k şi alte date de ajutor, dar nu datele principale care sunt procesate.
Algoritmul CURE (Clustering Using REpresentatives) - Grupare utilizând reprezentanţi - este utilizat pentru clustering la scară largă şi nu presupune nimic în legătură cu forma cluster-elor. În loc să reprezinte cluster-ele prin centroidul lor, acesta foloseşte o colecţie de puncte reprezentative care se află la o distanţă cât mai mare posibil unele de altele şi care definesc graniţele cluster-ului.
Algoritmul trece apoi la atribuirea unor puncte noi clusterelor, în funcţie de cel mai apropiat punct reprezentativ. O ilustrare a rezultatului clustering-ului se poate vedea în figura de mai jos şi este o formă clar diferită de rezultatele procesului de cluster-ing prin algoritmii anteriori:
Analiza prin cluster sau clustering-ul este sarcina de a grupa un set de obiecte astfel încât obiectele din acelaşi grup numit cluster se aseamănă între ele într-un fel sau altul mai mult decât cu cele din alte clustere. Aceasta se foloseşte de obicei în extragerea datelor în scop de explorare şi analize de date statistice, utilizate în multe domenii precum învăţarea automată, recunoaşterea tiparelor, analiza imaginii, recuperarea de informaţii şi bioinformatica.
Analiza cluster nu este definită printr-un algoritm specific, dar sarcina generală care trebuie rezolvată poate fi îndeplinită prin diverşi algoritmi care diferă prin definirea a ceea ce constituie un cluster şi care este modul optim de a-i găsi.
"Mining of Massive Datasets", Anand Rajaraman, Jure Leskovec, Jeffrey D. Ullman Stanford University
S. Guha, R. Rastogi, and K. Shim, "CURE: An efficient clustering algorithm for large databases," Proc. ACM SIGMOD Intl. Conf. on Management of Data
de Ovidiu Mățan
de Ovidiu Mățan
de Victor Miron
