Algoritmi de grupare: de la început până la stadiul tehnicii

Nu este un moment rău pentru a fi un Data Scientist. Oamenii serioși s-ar putea să găsească interes pentru tine dacă îndrepți conversația către „Big Data”, iar restul mulțimii petrecerii va fi intrigat când menționezi „Inteligenta artificială” și „Învățare automată”. Chiar și Google crede că nu ești rău și că devii și mai bun. Există o mulțime de algoritmi „inteligenti” care îi ajută pe oamenii de știință de date să-și facă vrăjitoria. Totul poate părea complicat, dar dacă înțelegem și organizăm un pic 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 despre data mining sau machine learning vor începe de obicei cu clustering, deoarece este atât simplu, cât și util. Este o parte importantă a unui domeniu oarecum mai extins de învățare nesupravegheată, în care datele pe care vrem să le descriem nu sunt etichetate. În cele mai multe cazuri, acesta este cazul în care utilizatorul nu ne-a oferit prea multe informații despre rezultatul așteptat. Algoritmul are doar datele și ar trebui să facă tot ce poate. În cazul nostru, ar trebui să efectueze clustering - separarea datelor în grupuri (clustere) care conțin puncte de date similare, în timp ce diferența dintre grupuri este cât mai mare posibil. Punctele de date pot reprezenta orice, cum ar fi clienții noștri. Clusteringul poate fi util dacă, de exemplu, dorim să grupăm utilizatori similari și apoi să derulă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 clustering eficient, utilizat pe scară largă. Înainte de a o rula efectiv, trebuie să definim o funcție de distanță între punctele de date (de exemplu, distanța euclidiană dacă dorim să grupăm puncte în spațiu) și trebuie să setăm numărul de clustere pe care îl dorim (k).

Algoritmul începe prin a selecta k puncte ca centroizi de pornire („centre” de clustere). Putem selecta orice k puncte aleatoare sau putem folosi o altă abordare, dar alegerea punctelor aleatorii este un început bun. Apoi, repetam iterativ doi pasi:

1. Pasul de atribuire: fiecare dintre m puncte din setul nostru de date este atribuit unui cluster care este reprezentat de cel mai apropiat dintre 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. Pas de actualizare: pentru fiecare cluster, un nou centroid este calculat ca medie a tuturor punctelor din cluster. Din pasul anterior, avem un set de puncte care sunt alocate unui cluster. Acum, pentru fiecare astfel de mulțime, calculăm o medie prin care declarăm un nou centroid al clusterului.

După fiecare iterație, centroizii se mișcă încet, iar distanța totală de la fiecare punct la centroidul atribuit devine din ce în ce mai mică. Cei doi pași sunt alternați până la convergență, adică până când nu mai apar modificări în alocarea clusterului. După un număr de iterații, același set de puncte va fi atribuit fiecărui centroid, conducând, prin urmare, la aceleași centroizi. K-Means este garantat să converge către un optim local. Cu toate acestea, aceasta 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, așa că s-a gândit mult la această problemă. O soluție simplă este doar să rulați K-Means de câteva ori cu atribuiri inițiale aleatorii. Putem selecta apoi cel mai bun rezultat luând-o pe cel cu suma minimă a distanțelor de la fiecare punct la grupul său – valoarea de eroare pe care încercăm să o minimizăm în primul rând.

Alte abordări ale selectării 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 valorile aberante, acele puncte rare care sunt doar „dezactivate”, care pot fi doar niște erori. Deoarece sunt departe de orice grup semnificativ, fiecare astfel de puncte poate ajunge să fie propriul său „cluster”. Un echilibru bun este varianta K-Means++ [Arthur și Vassilvitskii, 2007], a cărei inițializare va alege totuși puncte aleatorii, dar cu probabilitate proporțională cu distanța pătrată de la centroizii alocați anterior. Punctele care sunt mai departe 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, de asemenea, mai mare pe măsură ce probabilitățile lor se adună, rezolvând problema abere pe care am menționat-o.

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

Java (Weka)

 // Load some data Instances data = DataSource.read("data.arff"); // Create the model SimpleKMeans kMeans = new SimpleKMeans(); // We want three clusters kMeans.setNumClusters(3); // Run K-Means kMeans.buildClusterer(data); // Print the centroids Instances centroids = kMeans.getClusterCentroids(); for (Instance centroid: centroids) { System.out.println(centroid); } // Print cluster membership for each instance for (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[::10]) [1 1 1 1 1 0 0 0 0 0 2 2 2 2 2] > >> print(yiris[::10]) [0 0 0 0 0 1 1 1 1 1 2 2 2 2 2]

În exemplul Python de mai sus, am folosit un exemplu standard de set de date „Iris”, care conține dimensiunile petale de flori și sepal pentru trei specii diferite de iris. Le-am grupat în trei grupuri și am comparat grupurile obținute cu speciile reale (țintă), pentru a vedea că se potrivesc perfect.

În acest caz, știam că există trei grupuri (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? Aceste tipuri 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 atribuite lor) va fi mai mică. Deci, este o idee bună să setați un k mai mare? Putem încheia prin a avea k = m, adică fiecare punct având propriul său centroid, fiecare grup având un singur punct. Da, eroarea totală este 0, dar nu am primit o descriere mai simplă a datelor noastre și nici nu este suficient de generală pentru a acoperi câteva puncte noi care pot apărea. Acest lucru se numește supraajustare și nu vrem asta.

O modalitate de a rezolva această problemă este includerea unor penalizări pentru un număr mai mare de clustere. Deci, acum încercăm să minimizăm nu numai eroarea, ci și eroarea + penalizare . Eroarea va converge spre zero pe măsură ce creștem numărul de clustere, dar penalizarea va crește. La unele momente, câștigul din adăugarea unui alt cluster va fi mai mic decât penalizarea introdusă și vom avea rezultatul optim. O soluție care utilizează Bayesian Information Criterion (BIC) în acest scop se numește X-Means [Pelleg și Moore, 2000].

Un alt lucru pe care trebuie să-l definim corect este funcția de distanță. Uneori, aceasta este o sarcină simplă, una logică dată fiind natura datelor. Pentru punctele din spațiu, distanța euclidiană este o soluție evidentă, dar poate fi dificilă pentru caracteristicile diferitelor „unități”, pentru variabile discrete etc. Acest lucru poate necesita multe cunoștințe de domeniu. Sau putem apela la Machine Learning pentru ajutor. Putem încerca de fapt să învățăm funcția de distanță. Dacă avem un set de antrenament de puncte despre care știm cum ar trebui să fie grupate (adică punctele etichetate cu grupurile lor), putem folosi tehnici de învățare supravegheată pentru a găsi o funcție bună și apoi o aplicăm setului nostru țintă care nu este încă grupat. .

Metoda utilizată în K-Means, cu cei doi pași alternativi ai săi, seamănă cu o metodă de așteptare-maximizare (EM). De fapt, poate fi considerată o versiune foarte simplă a EM. Cu toate acestea, nu trebuie confundat cu algoritmul de grupare EM mai elaborat, chiar dacă împărtășește unele dintre aceleași principii.

Clustering EM

Deci, cu gruparea K-Means, fiecare punct este atribuit doar unui singur cluster, iar un cluster este descris doar de centrul său. Acest lucru nu este prea flexibil, deoarece este posibil să avem probleme cu grupurile care se suprapun sau cu cele care nu au formă circulară. Cu EM Clustering, putem acum să facem un pas mai departe și să descriem fiecare cluster prin centroid (media), covarianță (astfel încât să putem avea clustere eliptice) și greutate (dimensiunea clusterului). Probabilitatea ca un punct să aparțină unui cluster este acum dată de o distribuție de probabilitate gaussiană multivariată (multivariată - în funcție 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.

Acum începem 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). Acesta este pasul E. Dacă un grup este un candidat foarte bun pentru un punct, va avea o probabilitate apropiată de unul. Cu toate acestea, două sau mai multe clustere pot fi candidați acceptabili, astfel încât punctul are o distribuție a probabilităților peste clustere. Această proprietate a algoritmului, a punctelor care nu aparțin restricționate unui cluster se numește „clustering soft”.

Pasul M recalculează acum parametrii fiecărui cluster, folosind alocarea punctelor setului anterior de clustere. Pentru a calcula noua medie, covarianța și ponderea unui cluster, fiecare dată de punct este ponderată cu probabilitatea de a face parte din cluster, așa cum a fost calculată în pasul anterior.

Alternarea acestor doi pași va crește probabilitatea totală a logaritării până când converge. Din nou, maximul poate fi local, așa că putem rula algoritmul de mai multe ori pentru a obține clustere mai bune.

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

Propagarea afinității

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 tehnicii la standard de facto.

Principalele dezavantaje ale K-Means și ale algoritmilor similari sunt selectarea numărului de clustere și alegerea setului inițial de puncte. Propagarea prin afinitate, în schimb, ia ca intrare măsuri de similitudine între perechile de puncte de date și, simultan, consideră toate punctele de date ca exemple potențiale. Mesajele cu valoare reală sunt schimbate între punctele de date până când apare treptat un set de exemplare de înaltă calitate și grupuri corespunzătoare.

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

1. Asemănări între punctele de date, reprezentând cât de potrivit este un punct pentru a fi exemplul altuia. Dacă nu există nicio asemănare între două puncte, deoarece 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 caracterul adecvat al fiecărui punct de date pentru a fi un exemplar. S-ar putea să avem câteva informații a priori care puncte ar putea fi favorizate pentru acest rol și, astfel, îl putem reprezenta prin preferințe.

Atât asemănările, cât și preferințele sunt adesea reprezentate printr-o singură matrice, unde valorile de pe diagonala principală reprezintă preferințe. Reprezentarea matriceală este bună pentru seturi de date dense. Acolo unde conexiunile dintre puncte sunt rare, este mai practic să nu stocați întreaga matrice nxn în memorie, ci să păstrați o listă de asemănări cu punctele conectate. În spatele scenei, „schimbul de mesaje între puncte” este același lucru cu manipularea matricelor și este doar o chestiune de perspectivă și implementare.

Algoritmul rulează apoi printr-un număr de iterații, până când converge. Fiecare iterație are doi pași de transmitere a mesajelor:

1. Calcularea responsabilităților: Responsabilitatea r(i, k) reflectă dovezile acumulate pentru cât de potrivit este punctul k să servească drept exemplu pentru punctul i, ținând cont de alte exemple potențiale pentru punctul i. Responsabilitatea este trimisă de la punctul de date i la punctul de exemplu candidat k.

2. Calcularea disponibilităților: Disponibilitatea a(i, k) reflectă dovezile acumulate pentru cât de adecvat ar fi ca punctul i să aleagă punctul k ca exemplu, ținând cont de suportul din alte puncte că punctul k ar trebui să fie un exemplar. Disponibilitatea este trimisă de la punctul k exemplu candidat la punctul i.

Pentru a calcula responsabilitățile, algoritmul folosește asemănări și disponibilități originale calculate în iterația anterioară (inițial, toate disponibilitățile sunt setate la zero). Responsabilitățile sunt stabilite la similitudinea de intrare între punctul i și punctul k ca exemplu, minus cea mai mare dintre suma 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 scade atunci când există un punct similar care se consideră un bun candidat, deci există un " competiție între cei doi până când unul se decide într-o iterație.

Calcularea disponibilităților folosește, prin urmare, responsabilitățile calculate ca dovadă dacă fiecare candidat ar fi un bun exemplu. Disponibilitatea a(i, k) este setată la autoresponsabilitatea r(k, k) plus suma responsabilităților pozitive pe care modelul candidat k le primește din 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 se atinge numărul maxim de iterații. În orice moment prin procedura de propagare a afinității, însumând matricele Responsabilitate (r) și Disponibilitate (a) ne oferă informațiile de grupare de care avem nevoie: pentru punctul i, k cu maxim r(i, k) + a(i, k) reprezintă punctul sunt exemplar. 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 exemplu.

Am văzut că, cu K-Means și algoritmi similari, decizia numărului de clustere poate fi dificilă. Cu AP, nu trebuie să-l specificăm în mod explicit, dar poate avea nevoie totuși de unele reglaje dacă obținem fie mai multe, fie mai puține clustere decât am putea găsi optim. Din fericire, doar prin ajustarea preferințelor putem reduce sau crește numărul de clustere. Setarea preferințelor la o valoare mai mare va duce la mai multe grupuri, deoarece fiecare punct este „mai sigur” de adecvarea lui pentru a fi un exemplar și, prin urmare, este mai greu de „învins” și de a-l include sub „dominarea” unui alt punct. În schimb, setarea preferințelor mai mici va avea ca rezultat mai puține grupuri; de parcă ar spune „nu, nu, te rog, ești un exemplu mai bun, mă voi alătura grupului 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ă asemănare pentru un număr moderat de clustere. Cu toate acestea, ar putea fi necesare câteva rulări cu preferințe de ajustare pentru a obține rezultatul care se potrivește exact nevoilor noastre.

Propagarea ierarhică a afinității este, de asemenea, demnă de 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 efectuând al doilea nivel de grupare.

În cele din urmă…

Există o întreagă gamă de algoritmi de grupare, fiecare cu avantajele și dezavantajele sale în ceea ce privește tipul de date cu care sunt, complexitatea timpului, punctele slabe și așa mai departe. Ca să menționăm mai mulți algoritmi, de exemplu există Clustering Agglomerative Hierarchical (sau Clustering Linkage), bun pentru atunci când nu avem neapărat clustere circulare (sau hiper-sferice) și nu știm în avans numărul de clustere. Începe cu fiecare punct fiind un grup separat și funcționează prin unirea a două grupuri cele mai apropiate în fiecare pas până când totul este într-un grup mare.

Cu clusteringul aglomerativ ierarhic, putem decide cu ușurință numărul de clustere ulterior tăind dendrograma (diagrama arborescentă) orizontal acolo unde găsim potrivit. Este, de asemenea, repetabilă (dă î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. Grupează punctele care sunt strâns împachetate, extinzând grupurile în orice direcție unde există puncte în apropiere, ocupându-se astfel cu diferite forme de clustere.

Acești 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ă folosești 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 a juca.