Algoritmi de clustere: From Start To State Of The Art

Nu este un moment rău pentru a fi cercetător de date. Oamenii serioși s-ar putea să se intereseze de tine dacă întorci conversația spre „Big Data”, iar restul mulțimii de petrecăreți vor fi intrigați când vei menționa „Artificial Intelligence” și „Machine Learning”. Chiar și Google crede că nu sunteți rău și că deveniți și mai bun. Există o mulțime de algoritmi „inteligenți” care îi ajută pe cercetătorii de date să-și facă vrăjitoria. Totul poate părea complicat, dar dacă înțelegem și organizăm puțin algoritmii, nici măcar nu este atât de greu să îl găsim și să îl aplicăm pe cel de care avem nevoie.

Cursurile de data mining sau machine learning vor începe de obicei cu clusterizarea, pentru că este atât de simplă și utilă. Este o parte importantă a unui domeniu ceva mai larg al învățării nesupravegheate, în care datele pe care dorim să le descriem nu sunt etichetate. În cele mai multe cazuri, acest lucru se întâmplă atunci când utilizatorul nu ne-a oferit prea multe informații cu privire la rezultatul așteptat. Algoritmul dispune doar de date și ar trebui să facă tot ce poate. În cazul nostru, ar trebui să efectueze o clasificare – separarea datelor în grupuri (clustere) care conțin puncte de date similare, în timp ce disimilaritatea dintre grupuri este cât mai mare posibil. Punctele de date pot reprezenta orice, cum ar fi clienții noștri. Clusterizarea poate fi utilă dacă, de exemplu, dorim să grupăm utilizatori similari și apoi să desfășurăm campanii de marketing diferite pe fiecare cluster.

K-Means Clustering

După introducerea necesară, cursurile de Data Mining continuă întotdeauna cu K-Means; un algoritm de clusterizare eficient, utilizat pe scară largă și universal. Înainte de a-l rula efectiv, trebuie să definim o funcție de distanță între punctele de date (de exemplu, distanța euclidiană dacă dorim să grupăm punctele în spațiu) și trebuie să stabilim numărul de clustere pe care îl dorim (k).

Algoritmul începe prin selectarea a k puncte ca centroizi de pornire („centre” ale clusterelor). Putem selecta pur și simplu orice k puncte aleatorii sau putem folosi o altă abordare, dar alegerea unor puncte aleatorii este un bun început. Apoi, repetăm iterativ două etape:

1. Etapa de alocare: fiecare dintre cele m puncte din setul nostru de date este alocat unui cluster care este reprezentat de cel mai apropiat dintre cele k centroizi. Pentru fiecare punct, calculăm distanțele față de fiecare centroid și pur și simplu îl alegem pe cel mai puțin îndepărtat.

2. Etapa de actualizare: pentru fiecare cluster, se calculează un nou centroid ca medie a tuturor punctelor din cluster. Din etapa anterioară, avem un set de puncte care sunt atribuite unui cluster. Acum, pentru fiecare astfel de set, calculăm o medie pe care o declarăm un nou centroid al clusterului.

După fiecare iterație, centroizii se deplasează încet, iar distanța totală de la fiecare punct până la centroidul său atribuit devine din ce în ce mai mică. Cele două etape se alternează până la convergență, adică până când nu mai există modificări în atribuirea clusterelor. După un anumit număr de iterații, același set de puncte va fi atribuit fiecărui centroid, ceea ce duce din nou la aceiași centroizi. Se garantează că K-Means converge către un optim local. Cu toate acestea, acesta nu trebuie să fie neapărat cea mai bună soluție globală (optimul global).

Rezultatul final al grupării poate depinde de selecția centroizilor inițiali, astfel încât s-a reflectat mult asupra acestei probleme. O soluție simplă este doar să se ruleze K-Means de câteva ori cu atribuiri inițiale aleatorii. Putem selecta apoi cel mai bun rezultat luându-l pe cel cu suma minimă a distanțelor de la fiecare punct la clusterul său – valoarea erorii pe care încercăm să o minimizăm în primul rând.

Alte abordări pentru selectarea punctelor inițiale se pot baza pe selectarea punctelor îndepărtate. Acest lucru poate duce la rezultate mai bune, dar este posibil să avem o problemă cu punctele aberante, acele puncte singure și rare care sunt pur și simplu „off”, care pot fi doar niște erori. Deoarece sunt departe de orice grup semnificativ, fiecare astfel de punct poate sfârși prin a fi propriul său „grup”. Un bun echilibru este varianta K-Means++ , a cărei inițializare va alege în continuare puncte aleatorii, dar cu o probabilitate proporțională cu distanța pătratică față de centroizii atribuiți anterior. Punctele care sunt mai îndepărtate vor avea o probabilitate mai mare de a fi selectate ca centroizi de pornire. În consecință, dacă există un grup de puncte, probabilitatea ca un punct din grup să fie selectat devine și ea mai mare pe măsură ce probabilitățile lor se adună, rezolvând astfel problema outlier pe care am menționat-o.

K-Means++ este, de asemenea, inițializarea implicită pentru implementarea K-Means de la Scikit-learn din Python. Dacă folosiți Python, aceasta ar putea fi biblioteca dvs. de alegere. Pentru Java, biblioteca Weka poate fi un bun început:

Java (Weka)

// Load some dataInstances data = DataSource.read("data.arff");// Create the modelSimpleKMeans kMeans = new SimpleKMeans();// We want three clusterskMeans.setNumClusters(3);// Run K-MeanskMeans.buildClusterer(data);// Print the centroidsInstances centroids = kMeans.getClusterCentroids();for (Instance centroid: centroids) { System.out.println(centroid);}// Print cluster membership for each instancefor (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point));}

Python (Scikit-learn)

> >> from sklearn import cluster, datasets> >> iris = datasets.loadiris()> >> Xiris = iris.data> >> yiris = iris.target> >> kmeans = cluster.KMeans(nclusters=3)> >> kmeans.fit(Xiris)KMeans(copy_x=True, init='k-means++', ...> >> print(kmeans.labels)> >> print(yiris)

În exemplul Python de mai sus, am folosit un set de date standard de exemplu „Iris”, care conține dimensiunile petalelor și ale sepalelor florilor pentru trei specii diferite de iris. Le-am grupat în trei clustere și am comparat clusterele obținute cu speciile reale (țintă), pentru a vedea dacă se potrivesc perfect.

În acest caz, știam că există trei clustere (specii) diferite, iar K-Means a recunoscut corect care dintre ele merg împreună. Dar, cum alegem un număr bun de clustere k în general? Acest tip de întrebări sunt destul de frecvente în Machine Learning. Dacă solicităm mai multe clustere, acestea vor fi mai mici și, prin urmare, eroarea totală (totalul distanțelor de la puncte la clusterele care le-au fost atribuite) va fi mai mică. Așadar, este o idee bună să setați un k mai mare? Este posibil să ajungem să avem k = m, adică fiecare punct să fie propriul centroid, fiecare cluster având un singur punct. Da, eroarea totală este 0, dar nu am obținut o descriere mai simplă a datelor noastre și nici nu este suficient de generală pentru a acoperi unele puncte noi care pot apărea. Acest lucru se numește supraadaptare, iar noi nu ne dorim acest lucru.

O modalitate de a rezolva această problemă este de a include o anumită penalizare pentru un număr mai mare de clustere. Așadar, acum încercăm să minimizăm nu numai eroarea, ci și eroarea + penalizarea. Eroarea va converge pur și simplu spre zero pe măsură ce creștem numărul de clustere, dar penalizarea va crește. La un moment dat, câștigul obținut prin adăugarea unui alt cluster va fi mai mic decât penalizarea introdusă și vom obține rezultatul optim. O soluție care utilizează criteriul informațional Bayesian Information Criterion (BIC) în acest scop se numește X-Means .

Un alt lucru pe care trebuie să îl definim corect este funcția de distanță. Uneori, aceasta este o sarcină simplă, o sarcină logică având în vedere natura datelor. Pentru puncte în spațiu, distanța euclidiană este o soluție evidentă, dar poate fi complicat pentru caracteristici de diferite „unități”, pentru variabile discrete etc. Acest lucru poate necesita o mulțime de cunoștințe de domeniu. Sau, putem apela la învățarea automată pentru ajutor. De fapt, putem încerca să învățăm funcția de distanță. Dacă avem un set de puncte de antrenament pe care știm cum ar trebui să fie grupate (adică puncte etichetate cu clusterele lor), putem folosi tehnici de învățare supravegheată pentru a găsi o funcție bună și apoi să o aplicăm la setul nostru țintă care nu este încă grupat.

Metoda folosită în K-Means, cu cele două etape alternante, seamănă cu o metodă de așteptare-maximizare (EM). De fapt, ea poate fi considerată o versiune foarte simplă a EM. Cu toate acestea, nu trebuie confundată cu algoritmul mai elaborat de grupare EM, chiar dacă împărtășește unele dintre aceleași principii.

Grupare EM

Așadar, în cazul grupării K-Means, fiecare punct este atribuit doar unui singur grup, iar un grup este descris doar de centroidul său. Acest lucru nu este prea flexibil, deoarece putem avea probleme cu clusterele care se suprapun sau cu cele care nu au o formă circulară. Cu EM Clustering, putem acum să facem un pas mai departe și să descriem fiecare cluster prin centroidul său (media), covarianța (astfel încât să putem avea clustere eliptice) și greutatea (dimensiunea clusterului). Probabilitatea ca un punct să aparțină unui cluster este dată acum de o distribuție de probabilitate gaussiană multivariată (multivariată – care depinde de mai multe variabile). Aceasta înseamnă, de asemenea, că putem calcula probabilitatea ca un punct să se afle sub un „clopot” gaussian, adică probabilitatea ca un punct să aparțină unui cluster.

Începem acum procedura EM calculând, pentru fiecare punct, probabilitățile ca acesta să aparțină fiecăruia dintre clusterele curente (care, din nou, pot fi create aleatoriu la început). Aceasta este etapa E. În cazul în care un cluster este un candidat foarte bun pentru un punct, acesta va avea o probabilitate apropiată de unu. Cu toate acestea, două sau mai multe clustere pot fi candidați acceptabili, astfel încât punctul are o distribuție de probabilități pe clustere. Această proprietate a algoritmului, de neapartenență restrânsă a punctelor la un singur cluster, se numește „soft clustering”.

Etapa M recalculează acum parametrii fiecărui cluster, folosind atribuirile punctelor la setul anterior de clustere. Pentru a calcula noua medie, covarianță și pondere a unui cluster, datele fiecărui punct sunt ponderate cu probabilitatea sa de apartenență la cluster, așa cum a fost calculată în etapa precedentă.

Alternarea acestor două etape va crește probabilitatea logaritmică totală până când aceasta converge. Din nou, maximul poate fi local, astfel încât putem rula algoritmul de mai multe ori pentru a obține clustere mai bune.

Dacă acum dorim să determinăm un singur cluster pentru fiecare punct, putem pur și simplu să-l alegem pe cel mai probabil. Având un model de probabilitate, îl putem folosi, de asemenea, pentru a genera date similare, adică pentru a eșantiona mai multe puncte care sunt similare cu datele pe care le-am observat.

Affinity Propagation

Affinity Propagation (AP) a fost publicat de Frey și Dueck în 2007 și devine din ce în ce mai popular datorită simplității, aplicabilității generale și performanței sale. Își schimbă statutul de la stadiul de artă la standard de facto.

Principalele dezavantaje ale K-Means și ale algoritmilor similari sunt faptul că trebuie să selecteze numărul de clustere și alegerea setului inițial de puncte. Propagarea afinității, în schimb, ia ca intrare măsuri de similaritate între perechi de puncte de date și, simultan, consideră toate punctele de date ca fiind potențiale exemplare. Mesaje cu valori reale sunt schimbate între punctele de date până când apare treptat un set de exemplare de înaltă calitate și clusterele corespunzătoare.

Ca intrare, algoritmul ne cere să furnizăm două seturi de date:

1. Similitudini între punctele de date, reprezentând cât de bine se potrivește un punct să fie exemplarul altuia. În cazul în care nu există nicio similitudine între două puncte, adică nu pot aparține aceluiași cluster, această similitudine poate fi omisă sau setată la -Infinit, în funcție de implementare.

2. Preferințe, reprezentând aptitudinea fiecărui punct de date de a fi un exemplar. Este posibil să avem unele informații a priori despre ce puncte ar putea fi favorizate pentru acest rol, și astfel putem reprezenta acest lucru prin intermediul preferințelor.

Atât asemănările cât și preferințele sunt adesea reprezentate printr-o singură matrice, în care valorile de pe diagonala principală reprezintă preferințele. Reprezentarea matricei este bună pentru seturile de date dense. În cazul în care conexiunile dintre puncte sunt rare, este mai practic să nu se stocheze întreaga matrice n x n în memorie, ci să se păstreze o listă de similitudini cu punctele conectate. În spatele scenei, „schimbul de mesaje între puncte” este același lucru ca și manipularea matricelor și este doar o chestiune de perspectivă și de implementare.

Argitmul trece apoi printr-un număr de iterații, până când converge. Fiecare iterație are două etape de transmitere a mesajelor:

1. Calcularea responsabilităților: Responsabilitatea r(i, k) reflectă dovezile acumulate cu privire la cât de bine se potrivește punctul k să servească drept exemplar pentru punctul i, luând în considerare alte potențiale exemplare pentru punctul i. Responsabilitatea este trimisă de la punctul de date i la punctul exemplar candidat k.

2. Calcularea disponibilităților: Disponibilitatea a(i, k) reflectă dovezile acumulate cu privire la cât de adecvat ar fi ca punctul i să aleagă punctul k ca punct exemplar, luând în considerare susținerea din partea altor puncte că punctul k ar trebui să fie un punct exemplar. Disponibilitatea este trimisă de la punctul candidat exemplar k la punctul i.

Pentru a calcula responsabilitățile, algoritmul utilizează similitudinile originale și disponibilitățile calculate în iterația anterioară (inițial, toate disponibilitățile sunt stabilite la zero). Responsabilitățile sunt stabilite la similaritatea de intrare dintre punctul i și punctul k ca exemplar al acestuia, minus cea mai mare sumă a similarității și disponibilității dintre punctul i și alte exemplare candidate. Logica din spatele calculării cât de potrivit este un punct pentru un exemplar este că acesta este favorizat mai mult dacă preferința inițială a priori a fost mai mare, dar responsabilitatea devine mai mică atunci când există un punct similar care se consideră un bun candidat, astfel încât există o „competiție” între cele două până când se decide unul dintre ele într-o anumită iterație.

Calcularea disponibilităților, prin urmare, utilizează responsabilitățile calculate ca dovadă dacă fiecare candidat ar fi un bun exemplar. Disponibilitatea a(i, k) este stabilită la responsabilitatea proprie r(k, k) plus suma responsabilităților pozitive pe care candidatul exemplar k le primește de la alte puncte.

În cele din urmă, putem avea diferite criterii de oprire pentru a încheia procedura, cum ar fi atunci când modificările valorilor scad sub un anumit prag sau când este atins numărul maxim de iterații. În orice punct prin procedura de propagare a afinității, însumarea matricelor Responsabilitate (r) și Disponibilitate (a) ne oferă informațiile de grupare de care avem nevoie: pentru punctul i, k cu maximul r(i, k) + a(i, k) reprezintă exemplarul punctului i. Sau, dacă avem nevoie doar de setul de exemplare, putem scana diagonala principală. Dacă r(i, i) + a(i, i) > 0, punctul i este un exemplar.

Am văzut că, în cazul K-Means și al algoritmilor similari, decizia privind numărul de clustere poate fi dificilă. Cu AP, nu trebuie să îl specificăm în mod explicit, dar este posibil să fie nevoie totuși de un reglaj dacă obținem fie mai multe, fie mai puține clustere decât am putea considera optim. Din fericire, prin simpla ajustare a preferințelor putem reduce sau crește numărul de clustere. Dacă setați preferințele la o valoare mai mare, veți obține mai multe clustere, deoarece fiecare punct este „mai sigur” de capacitatea sa de a fi un exemplar și, prin urmare, este mai greu de „bătut” și de inclus sub „dominația” unui alt punct. Dimpotrivă, stabilirea unor preferințe mai scăzute va duce la apariția a mai puține clustere; ca și cum ar spune „nu, nu, te rog, tu ești un exemplar mai bun, mă voi alătura clusterului tău”. Ca regulă generală, putem seta toate preferințele la similaritatea mediană pentru un număr mediu spre mare de clustere, sau la cea mai mică similaritate pentru un număr moderat de clustere. Cu toate acestea, ar putea fi nevoie de câteva rulări cu ajustarea preferințelor pentru a obține rezultatul care se potrivește exact nevoilor noastre.

Propagarea ierarhică a afinității merită, de asemenea, să fie menționată, ca o variantă a algoritmului care se ocupă de complexitatea pătratică prin împărțirea setului de date în câteva subseturi, gruparea acestora separat și apoi efectuarea celui de-al doilea nivel de grupare.

În cele din urmă…

Există o întreagă gamă de algoritmi de clusterizare, fiecare cu avantajele și dezavantajele sale în ceea ce privește tipul de date cu care se confruntă, complexitatea în timp, punctele slabe și așa mai departe. Ca să menționez mai mulți algoritmi, de exemplu, există Hierarchical Agglomerative Clustering (sau Linkage Clustering), bun pentru cazurile în care nu avem neapărat clustere circulare (sau hiper-sferice) și nu știm dinainte numărul de clustere. Începe cu fiecare punct ca fiind un cluster separat și funcționează prin alăturarea celor mai apropiate două clustere în fiecare etapă, până când totul se află într-un singur cluster mare.

Cu Hierarchical Agglomerative Clustering, putem decide cu ușurință numărul de clustere după aceea, tăind dendrograma (diagrama arborescentă) pe orizontală acolo unde ni se pare potrivit. Este, de asemenea, repetabil (oferă întotdeauna același răspuns pentru același set de date), dar este și de o complexitate mai mare (pătratică).

Apoi, DBSCAN (Density-Based Spatial Clustering of Applications with Noise) este, de asemenea, un algoritm demn de menționat. Acesta grupează punctele care sunt foarte apropiate între ele, extinzând clusterele în orice direcție în care există puncte apropiate, tratând astfel diferite forme de clustere.

Aceste algoritmi merită un articol propriu și îi putem explora într-o postare separată mai târziu.

Este nevoie de experiență cu unele încercări și erori pentru a ști când să folosim un algoritm sau altul. Din fericire, avem o serie de implementări în diferite limbaje de programare, așa că încercarea lor necesită doar puțină dorință de joacă.

.