Clustering în învățarea automată: 5 algoritmi esențiali de clustering

Clusteringul în sine nu este un algoritm specific, ci o sarcină generală de rezolvat. Poți atinge acest obiectiv folosind diverși algoritmi care diferă semnificativ în modul în care înțeleg ce este un cluster și cum îl găsesc eficient. 

Construcția intuiției din spatele clusteringului

Înainte de a intra în detalii algoritmice, să construim mai întâi o intuiție folosind un exemplu simplu cu un set de date despre fructe. Să spunem că avem o colecție mare de imagini care conțin trei fructe: (i) căpșuni, (ii) pere și (iii) mere. 

În setul de date, toate imaginile sunt amestecate, iar cazul tău de utilizare este să grupezi fructele similare, adică să creezi trei grupuri, fiecare conținând un singur tip de fruct. Exact asta va face un algoritm de clustering. 

Criterii cheie de succes pentru analiza de clustering

Spre deosebire de cazuri de utilizare de învățare supravegheată, cum ar fi clasificarea sau regresia, clusteringul nu poate fi complet automatizat cap-coadă. În schimb, este un proces iterativ de descoperire a informațiilor care necesită expertiză de domeniu și judecată umană, folosite frecvent pentru a face ajustări asupra datelor și parametrilor modelului pentru a atinge rezultatul dorit. 

Cel mai important, pentru că clusteringul este învățare nesupravegheată și nu folosește date etichetate, nu putem calcula metrici de performanță precum acuratețe, AUC, RMSE etc. pentru a compara diferiți algoritmi sau tehnici de preprocesare a datelor. Drept urmare, este cu adevărat dificil și subiectiv să evaluezi performanța modelelor de clustering. 

Criteriile cheie de succes în modelele de clustering se învârt în jurul a:

• Este interpretabil?
• Este util pentru business rezultatul clusteringului?
• Ai învățat informații noi sau ai descoperit tipare noi în date pe care nu le cunoșteai înainte de clustering?

Măsurarea calității clusteringului

Fără date etichetate, nu poți calcula acuratețe sau AUC. Două metrici ajută la cuantificarea cât de bine sunt separate clusterele tale. Două măsuri comune:

• Silhouette Score măsoară cât de similar este un punct cu propriul cluster comparativ cu cel mai apropiat cluster vecin. Variează între -1 și 1; scorurile peste 0,5 sugerează clustere bine separate.
• Indicele Davies-Bouldin măsoară similaritatea medie dintre fiecare cluster și clusterul său cel mai similar — mai mic este mai bine.

Ambele sunt disponibile în scikit-learn: sklearn.metrics.silhouette_score(X, labels) și sklearn.metrics.davies_bouldin_score(X, labels).

1. K-Means

K-Means este cel mai folosit algoritm pentru sarcini de clustering, în mare parte pentru că pașii sunt ușor de urmărit, iar implementarea în scikit-learn este simplă. Este un algoritm bazat pe centroizi, unde utilizatorul trebuie să definească numărul necesar de clustere pe care vrea să le creeze. 

Aceasta derivă, de obicei, dintr-un caz de utilizare de business sau din încercarea mai multor valori pentru numărul de clustere și apoi evaluarea rezultatului. 

Clusteringul K-Means este un algoritm iterativ care creează clustere ne-suprapuse, ceea ce înseamnă că fiecare instanță din setul tău de date poate aparține exclusiv unui singur cluster. Cea mai simplă cale de a-ți forma intuiția pentru K-Means este să înțelegi pașii împreună cu diagrama de mai jos. Poți găsi și o descriere detaliată a procesului în tutorialele noastre K-Means Clustering în Python și K-Means Clustering în R. 

1. Utilizatorul specifică numărul de clustere.
2. Inițializează centroizii aleator în funcție de numărul de clustere. În diagrama de mai jos, în Iterația 1, observă că trei centroizi sunt inițializați aleator în culorile albastru, roșu și verde.
3. Calculează distanța dintre punctele de date și fiecare centroid și atribuie fiecare punct de date celui mai apropiat centroid.
4. Recalculează media centroidului pe baza tuturor punctelor de date alocate, ceea ce va schimba poziția centroidului, așa cum poți vedea în Iterațiile 2 - 9, până la convergență.
5. Iterațiile continuă până când nu mai există schimbări ale mediei centroidului sau până când se atinge parametrul max_iter, adică numărul maxim de iterații definit de utilizator în timpul antrenării. În scikit-learn, valoarea implicită pentru max_iter este 300.

Sursa imaginii: Learnbymarketing.com

2. MeanShift

Spre deosebire de algoritmul K-Means, algoritmul MeanShift nu necesită specificarea numărului de clustere. Algoritmul determină automat numărul de clustere, ceea ce este un avantaj clar față de K-Means atunci când nu știi câte clustere conțin datele tale. 

MeanShift este, de asemenea, bazat pe centroizi și atribuie iterativ fiecare punct de date clusterelor. Cea mai frecventă utilizare pentru clusteringul MeanShift este segmentarea imaginilor.

Algoritmul MeanShift se bazează pe estimarea densității cu kernel. Similar cu K-Means, algoritmii MeanShift deplasează iterativ fiecare punct de date către cel mai apropiat centroid de cluster, care sunt inițializați aleator, iar fiecare punct este mutat iterativ în spațiu în funcție de unde sunt cele mai multe puncte, adică către modă (moda fiind cea mai mare densitate de puncte din regiune, în contextul MeanShift). 

Din acest motiv, algoritmul MeanShift este cunoscut și ca algoritmul „căutător de modă”. Pașii algoritmului MeanShift sunt următorii:

• Alege un punct aleator și creează o fereastră în jurul acelui punct.
• Calculează media tuturor punctelor din această fereastră.
• Deplasează fereastra urmând direcția modei. 
• Repetă pașii până la convergență.

Sursa imaginii: ResearchGate

Pentru un walkthrough pas cu pas al MeanShift în practică, vezi tutorialul Mean Shift Clustering.

3. DBSCAN

DBSCAN, sau Density-Based Spatial Clustering of Applications with Noise, este un algoritm de clustering nesupravegheat care pornește de la premisa că clusterele sunt regiuni dense separate de regiuni cu densitate mai scăzută. 

Cel mai mare avantaj față de K-Means și MeanShift este robustețea la valori aberante (outliers), adică nu va include punctele atipice în niciun cluster. 

Algoritmii DBSCAN necesită doar doi parametri de la utilizator: 

• Raza cercului creat în jurul fiecărui punct de date, cunoscută și ca epsilon

• minPoints, care definește numărul minim de puncte necesare în interiorul acelui cerc pentru ca punctul să fie clasificat drept punct Nucleu (Core).

Fiecare punct de date este înconjurat de un cerc cu rază epsilon, iar DBSCAN le identifică drept puncte Nucleu (Core), de Frontieră (Border) sau Zgomot (Noise). Un punct este considerat Nucleu dacă cercul care îl înconjoară conține cel puțin numărul de puncte specificat prin parametrul minPoints. 

Este considerat punct de Frontieră dacă numărul de puncte este sub minimul necesar, iar este considerat Zgomot dacă nu există puncte suplimentare situate în raza epsilon a vreunui punct. Punctele de zgomot nu sunt încadrate în niciun cluster (practic, sunt outlieri).

Câteva cazuri de utilizare comune pentru algoritmul DBSCAN:

• Performanță foarte bună la separarea clusterelor cu densitate mare față de densitate mică;
• Funcționează excelent pe seturi de date neliniare, și
• Poate fi folosit pentru detecția anomaliilor deoarece separă punctele de zgomot și nu le atribuie niciunui cluster.

DBSCAN vs K-Means

Comparând DBSCAN cu K-Means, cele mai frecvente diferențe sunt: 

• Algoritmul K-Means grupează toate instanțele din setul de date, în timp ce DBSCAN nu atribuie punctele de zgomot (outlieri) unui cluster valid
• K-Means are dificultăți cu clusterele non-globale, în timp ce DBSCAN le gestionează fără probleme
• Algoritmul K-Means presupune că toate punctele din setul de date provin dintr-o distribuție Gaussiană, în timp ce DBSCAN nu face nicio presupunere despre date.

Poți afla mai multe în ghidul nostru despre algoritmul de clustering DBSCAN, care acoperă reglarea parametrilor și exemple practice. 

Sursa imaginii: Medium

4. Clustering ierarhic

Clusteringul ierarhic este o metodă care construiește o ierarhie de clustere. Există două tipuri ale acestei metode. 

• Aglomerați: O abordare de jos în sus, în care fiecare observație este tratată inițial ca propriul cluster, iar pe măsură ce urcăm, observațiile sunt unite în perechi, iar perechile în clustere. 
• Diviziv: O abordare „de sus în jos”: toate observațiile încep într-un singur cluster, iar divizările sunt efectuate recursiv pe măsură ce coborâm.

Când vine vorba de analizarea datelor din rețele sociale, clusteringul ierarhic este de departe cea mai comună și populară metodă. Nodurile (ramurile) din graf sunt comparate între ele în funcție de gradul de similaritate dintre ele. Conectând grupuri mai mici de noduri înrudite, se pot crea grupări mai mari.

Cel mai mare avantaj al clusteringului ierarhic este că este ușor de înțeles și implementat. De obicei, rezultatul acestei metode este analizat într-o imagine ca cea de mai jos. Se numește dendrogramă.

Poți afla mai multe în tutorialul nostru despre clustering ierarhic, care prezintă cum să construiești și să citești dendrograme în Python. 

Sursa imaginii: ResearchGate

5. BIRCH

BIRCH înseamnă Balanced Iterative Hierarchical Based Clustering. Este folosit pe seturi de date foarte mari unde K-Means nu poate scala practic. Algoritmul BIRCH împarte datele mari în clustere mici și încearcă să rețină cât mai multă informație posibil. Grupurile mai mici sunt apoi clusterizate pentru un rezultat final în loc să se aplice clustering direct pe seturile de date mari. 

BIRCH este adesea folosit pentru a suplimenta alți algoritmi de clustering, generând un rezumat al informației pe care ceilalți algoritmi îl pot utiliza. Utilizatorii trebuie să definească numărul de clustere pentru antrenarea algoritmului BIRCH, similar cu K-Means.

Unul dintre beneficiile BIRCH este că poate clusteriza progresiv și dinamic puncte de date multidimensionale. Acest lucru se face pentru a crea clustere de cea mai înaltă calitate sub constrângeri date de memorie și timp. În majoritatea cazurilor, BIRCH are nevoie doar de o singură trecere prin baza de date, ceea ce îl face scalabil. 

Cel mai comun caz de utilizare pentru BIRCH este ca alternativă eficientă în memorie la K-Means, pentru a clusteriza seturi de date mari care nu pot fi gestionate cu K-Means din cauza limitărilor de memorie sau calcul.

Aplicații de business ale clusteringului

Clusteringul are aplicații largi în industrii: media, sănătate, producție, retail și oriunde ai cantități mari de date neetichetate. Iată câteva exemple practice.

Segmentarea clienților

Clienții sunt categorizați folosind algoritmi de clustering în funcție de comportamentul de cumpărare sau interese, pentru a dezvolta campanii de marketing țintite. 

Imaginează-ți că ai 10M de clienți și vrei să dezvolți campanii personalizate sau țintite. E puțin probabil să creezi 10M de campanii, așa că ce facem? Am putea folosi clusteringul pentru a grupa cei 10M de clienți în 25 de clustere și apoi să proiectăm 25 de campanii în loc de 10M.

Sursa imaginii: Medium

Clustering în retail

Există multe oportunități pentru clustering în retail. De exemplu, poți aduna date pentru fiecare magazin și să faci clustering la nivel de magazin pentru a genera insight-uri care îți pot spune ce locații sunt similare între ele pe baza unor atribute precum traficul pietonal, vânzarea medie pe magazin, numărul de SKU-uri etc. 

Un alt exemplu ar fi clusteringul la nivel de categorie. În diagrama de mai jos avem opt magazine. Culorile diferite reprezintă clustere diferite. Există patru clustere în acest exemplu. 

Observă că categoria deodorante din Magazinul 1 este reprezentată de clusterul roșu, în timp ce categoria deodorante din Magazinul 2 este reprezentată de clusterul albastru. Asta arată că Magazinele 1 și 2 au piețe-țintă complet diferite pentru categoria deodorante.

Sursa imaginii: dotactiv.com

Clustering în îngrijire clinică / managementul bolilor

Sănătatea și știința clinică oferă aplicații de clustering deosebit de solide. Un astfel de exemplu este cercetarea publicată de Komaru & Yoshida et al. 2020, unde au colectat date demografice și de laborator pentru 101 pacienți și apoi i-au segmentat în 3 clustere. 

Fiecare cluster a fost caracterizat de condiții diferite. De exemplu, clusterul 1 are pacienți cu WBC & CRP scăzute. Clusterul 2 are pacienți cu BMP & ser crescute, iar clusterul 3 are pacienți cu ser scăzut. Fiecare cluster reprezintă o traiectorie de supraviețuire diferită, având în vedere mortalitatea la 1 an după hemodializă.

Sursa imaginii: elsevierhealth.com

Segmentarea imaginilor

Segmentarea imaginilor este clasificarea unei imagini în grupuri diferite. S-a făcut multă cercetare în segmentarea imaginilor folosind clustering. Acest tip de clustering este util dacă vrei să izolezi obiecte într-o imagine pentru a le analiza individual și a vedea ce sunt. 

În exemplul de mai jos, partea stângă reprezintă imaginea originală, iar partea dreaptă este rezultatul algoritmului de clustering. Poți vedea clar că sunt 4 clustere, adică 4 obiecte diferite în imagine, determinate pe baza pixelilor (tigrul, iarba, apa și nisipul).

Compararea algoritmilor de clustering

Există 10 algoritmi de clustering nesupravegheat implementați în scikit-learn, o bibliotecă populară de învățare automată în Python. Există diferențe fundamentale în modul în care fiecare algoritm determină și atribuie clustere în setul de date. 

Diferențele de bază în modalitatea matematică a acestor algoritmi se reduc la patru aspecte după care îi putem compara și contrasta:

• Parametrii necesari modelului 
• Scalabilitate 
• Cazuri de utilizare, 
• Geometrie, adică metrica folosită pentru calculul distanțelor. 

În diagrama de mai jos, fiecare coloană reprezintă un rezultat de la un algoritm de clustering diferit, precum K-Means, Affinity Propagation, MeanShift etc. În total sunt 10 algoritmi antrenați pe același set de date.

Unii algoritmi au produs același rezultat. Observă că Agglomerative Clustering, DBSCAN, OPTICS și Spectral Clustering au dus la aceleași clustere. 

Totuși, dacă observi și compari rezultatul K-Means cu cel al algoritmului MeanShift, vei vedea că cele două au produs rezultate diferite. În cazul K-Means sunt doar două grupuri (clustere: albastru și portocaliu), în timp ce în cazul MeanShift sunt trei, adică albastru, verde și portocaliu. 

Sursa imaginii: scikit-learn

Din păcate (sau din fericire), nu există un răspuns corect sau greșit în clustering. Ar fi fost atât de simplu să spunem „Algoritmul X performează cel mai bine aici.” 

Acest lucru nu este posibil și tocmai de aceea clusteringul este o sarcină foarte provocatoare. 

În cele din urmă, care algoritm funcționează mai bine nu depinde de o metrică ușor de măsurat, ci de interpretare și de cât de util este rezultatul pentru cazul de utilizare în cauză.

Cum alegi algoritmul potrivit de clustering

Fiecare algoritm se potrivește unor condiții diferite ale datelor. Folosește acest tabel ca punct de plecare, apoi testează cel puțin două pe datele tale reale înainte de a te decide.

Un punct de plecare practic: încearcă mai întâi K-Means pentru viteză, treci la DBSCAN dacă datele tale au forme neregulate sau outlieri, și folosește clusteringul ierarhic când vrei să explorezi vizual structura clusterelor printr-o dendrogramă înainte de a alege k.

Gânduri finale

Clusteringul este mai greu de aplicat decât tehnicile supravegheate precum clasificarea și regresia din două motive: nu poți măsura performanța față de ținte etichetate, iar parametri precum numărul de clustere necesită judecată de domeniu, nu o selecție algoritmică. 

Clusteringul este o abilitate valoroasă pentru mai multe roluri: data scientists, ingineri ML și analiști se lovesc toți de probleme pe care clusteringul le poate rezolva. 

Dacă vrei să afli mai multe despre Clustering și învățarea nesupravegheată și să înveți implementarea în limbajele Python și R, cursurile de mai jos te pot ajuta să progresezi: 

• Cluster Analysis in Python
• Cluster Analysis in R
• Unsupervised Learning in Python
• Unsupervised Learning in R