Ce este Clustering-ul K-Means?

Clustering-ul K-Means este un algoritm de învățare nesupervizată, și dintre toate algoritmii de învățare nesupervizată, clustering-ul K-Means ar putea fi cel mai utilizat, datorită puterii și simplității sale. Cum funcționează exact clustering-ul K-Means?

Răspunsul scurt este că clustering-ul K-Means funcționează prin crearea unui punct de referință (un centroid) pentru un număr dorit de clase, și apoi atribuirea punctelor de date la clusterul de clase în funcție de care punct de referință este cel mai apropiat. În timp ce aceasta este o definiție rapidă pentru clustering-ul K-Means, să luăm ceva timp pentru a explora mai în profunzime clustering-ul K-Means și a obține o mai bună înțelegere a modului în care funcționează.

Definirea Clustering-ului

Înainte de a examina algoritmii exacti utilizați pentru a efectua clustering-ul K-Means, să luăm ceva timp pentru a defini clustering-ul în general.

Cluster-urile sunt doar grupuri de articole, și clustering-ul este doar plasarea articolelor în aceste grupuri. În sensul științei datelor, algoritmii de clustering își propun să facă două lucruri:

• Să asigure că toate punctele de date dintr-un cluster sunt cât mai asemănătoare între ele.
• Să asigure că toate punctele de date din cluster-e diferite sunt cât mai diferite între ele.

Algoritmii de clustering grupează articolele împreună pe baza unei metrice de asemănare. Acest lucru se face adesea prin găsirea “centroidului” diferitelor grupuri posibile din setul de date, deși nu exclusiv. Există o varietate de algoritmi de clustering diferiți, dar scopul tuturor algoritmilor de clustering este același, de a determina grupurile intrinseci unui set de date.

Clustering-ul K-Means

Clustering-ul K-Means este unul dintre cei mai vechi și mai utilizați tipuri de algoritmi de clustering, și funcționează pe baza cuantificării vectoriale. Există un punct în spațiu ales ca origine, și apoi vectori sunt desenați de la origine la toate punctele de date din setul de date.

În general, clustering-ul K-Means poate fi împărțit în cinci pași diferiți:

• Puneți toate instanțele în subseturi, unde numărul de subseturi este egal cu K.
• Găsiți punctul mediu/centroidul noilor cluster-e create.
• Pe baza acestor centroiduri, atribuiți fiecărui punct un cluster specific.
• Calculați distanțele de la fiecare punct la centroiduri și atribuiți punctele la cluster-urile unde distanța de la centroid este minimă.
• După ce punctele au fost atribuite la cluster-e, găsiți noul centroid al cluster-elor.

Pașii de mai sus sunt repetați până când procesul de antrenare este finalizat.

În faza inițială, centroidurile sunt plasate undeva printre punctele de date.
Foto: Weston.pace via wikimedia commons, GNU Free Documentation License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Alternativ, după ce centroidurile au fost plasate, putem concepe clustering-ul K-Means ca o alternanță între două faze diferite: etichetarea punctelor de date și actualizarea centroidurilor.

În al doilea pas, o metrică de distanță precum distanța Euclideană este utilizată pentru a calcula care centroid este cel mai apropiat de un punct dat, și apoi punctele sunt atribuite la clasa centroidului respectiv. Foto: Weston.pace via Wikimedia Commons, GNU Free Doc License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

În faza de etichetare a punctelor de date, fiecare punct de date este atribuit cu o etichetă care îl plasează în clusterul care aparține centroidului cel mai apropiat. Centroidul cel mai apropiat este determinat în general utilizând distanța Euclideană pătrată, deși alte metrice de distanță precum distanța Manhattan, Cosinus și Jaccard pot fi utilizate în funcție de tipul de date introduse în algoritmul de clustering.

În al treilea pas, centroidurile sunt mutate la media tuturor punctelor de date. Apoi, clasele sunt reatribuite. Foto: Weston.pace via Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

În faza de actualizare a centroidurilor, centroidurile sunt calculate prin găsirea distanței medii între toate punctele de date conținute într-un cluster.

Cum să Alegeți Valoarea Corectă pentru “K”

Luând în considerare că clustering-ul K-Means este un algoritm nesupervizat și numărul de clase nu este cunoscut în avans, cum decideți asupra numărului corect de clase/valoarea corectă pentru K?

O tehnică pentru selectarea valorii corecte a lui K este numită “tehnica cotului”. Tehnica cotului constă în rularea unui algoritm de clustering K-Means pentru o serie de valori diferite ale lui K și utilizarea unei metrice de acuratețe, de obicei Suma Erorilor Pătrate, pentru a determina care valori ale lui K oferă cele mai bune rezultate. Suma Erorilor Pătrate este determinată prin calcularea distanței medii între centroidul unui cluster și punctele de date din acel cluster.

Termenul “tehnica cotului” provine din faptul că atunci când trasați SSE în funcție de diferitele valori ale lui K, graficul rezultat va avea adesea o formă de “cot”, unde SSE scade rapid pentru primele câteva valori ale lui K, dar apoi se stabilizează. În astfel de condiții, valoarea lui K situată la cot este cea mai bună valoare pentru K, deoarece există randamente rapid diminuate după această valoare.

Clustering-ul K-Means cu Mini-Loturi

Pe măsură ce seturile de date cresc în dimensiune, timpul de calcul crește și el. Clustering-ul K-Means de bază poate dura mult timp pentru a fi finalizat atunci când rulează pe seturi de date masive, și ca urmare, s-au făcut ajustări la clustering-ul K-Means pentru a reduce costurile spațiale și temporale ale algoritmului.

Clustering-ul K-Means cu mini-loturi este o variantă a clustering-ului K-Means în care dimensiunea setului de date luat în considerare este limitată. Clustering-ul K-Means normal rulează pe întregul set de date/batch la un moment dat, în timp ce clustering-ul K-Means cu mini-loturi împarte setul de date în subseturi. Mini-loturile sunt selectate aleatoriu din setul de date întreg și pentru fiecare nouă iterație, un nou eșantion aleatoriu este selectat și utilizat pentru a actualiza poziția centroidurilor.

În clustering-ul K-Means cu mini-loturi, cluster-urile sunt actualizate cu o combinație a valorilor mini-lotului și a unei rate de învățare. Rata de învățare scade pe parcursul iterațiilor, și este inversul numărului de puncte de date plasate într-un anumit cluster. Efectul reducerii ratei de învățare este că impactul noilor date este redus și convergența este atinsă atunci când, după mai multe iterații, nu există modificări în cluster-e.

Rezultatele studiilor privind eficacitatea clustering-ului K-Means cu mini-loturi sugerează că poate reduce cu succes timpul de calcul, cu un compromis mic în calitatea cluster-ului.

Aplikații ale Clustering-ului K-Means

Clustering-ul K-Means poate fi utilizat în siguranță în orice situație în care punctele de date pot fi segmentate în grupuri/clase distincte. Iată câteva exemple de cazuri de utilizare comune pentru clustering-ul K-Means.

Clustering-ul K-Means poate fi aplicat la clasificarea documentelor, grupând documentele pe baza caracteristicilor precum subiecte, etichete, utilizarea cuvintelor, metadate și alte caracteristici ale documentelor. De asemenea, poate fi utilizat pentru a clasifica utilizatorii ca roboți sau non-roboți pe baza modelelor de activitate precum postări și comentarii. Clustering-ul K-Means poate fi utilizat și pentru a plasa oamenii în grupuri pe baza nivelurilor de îngrijorare atunci când monitorizează starea lor de sănătate, pe baza caracteristicilor precum comorbidități, vârstă, istoricul pacientului, etc.

Clustering-ul K-Means poate fi utilizat și pentru sarcini mai deschise, precum crearea sistemelor de recomandare. Utilizatorii unui sistem precum Netflix pot fi grupați împreună pe baza modelelor de vizionare și li se pot recomanda conținuturi similare. Clustering-ul K-Means poate fi utilizat pentru detectarea anomaliilor, evidențiind posibilele cazuri de fraudă sau articole defecte.