Ce este Clustering K-Means?

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

Răspunsul scurt este că clustering K-Means funcționează prin crearea unui punct de referință (un centroid) pentru un număr dorit de clase, și apoi asignarea 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 K-Means, să luăm ceva timp pentru a explora mai în profunzime clustering K-Means și pentru a obține o mai bună înțelegere a modului în care funcționează.

Definirea Clusteringului

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

Clusterurile sunt doar grupuri de articole, și clusteringul este doar plasarea articolelor în aceste grupuri. În sensul științei datelor, algoritmii de clustering încearcă 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 clusteruri diferite sunt cât mai puțin asemănătoare între ele.

Algoritmii de clustering grupează articolele împreună pe baza unei metrice de asemănare. Acest lucru se face adesea prin găsirea “centroidului” grupurilor 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, pentru a determina grupurile intrinseci unui set de date.

Clustering K-Means

Clustering K-Means este unul dintre cele mai vechi și mai utilizate 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 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 clusteruri create.
• Pe baza acestor centroiduri, asigurați-vă că fiecare punct este asignat la un cluster specific.
• Calculați distanțele de la fiecare punct la centroiduri și asigurați-vă că punctele sunt asignate la clusterurile unde distanța de la centroid este minimă.
• După ce punctele au fost asignate la clusteruri, găsiți noul centroid al clusterurilor.

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.
Photo: 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 K-Means ca o alternanță între două faze diferite: etichetarea punctelor de date și actualizarea centroidurilor.

În al doilea pas, o metrică de distanță, cum ar fi distanța Euclideană, este utilizată pentru a calcula care centroid este cel mai apropiat de un punct dat, și apoi punctele sunt asignate la clasa centroidului respectiv. Photo: 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 asignat cu o etichetă care îl plasează în clusterul care aparține centroidului cel mai apropiat. Centroidul cel mai apropiat este determinat în mod normal utilizând distanța Euclideană pătrată, deși alte metrice de distanță, cum ar fi distanța Manhattan, Cosinus și Jaccard, pot fi utilizate în funcție de tipul de date care sunt introduse în algoritmul de clustering.

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

În pașul 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 K-Means este un algoritm nesupervizat și numărul de clase nu este cunoscut în avans, cum decideți asupra numărului adecvat de clase/valoarea corectă pentru K?

O tehnică pentru selectarea valorii corecte a lui K este ceea ce se numește “tehnica cotului”. Tehnica cotului constă în rularea unui algoritm de clustering K-Means pentru o serie de valori K diferite ș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” vine de la 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 valoarea cea mai bună pentru K, deoarece există randamente rapid diminuate după această valoare.

Clustering K-Means Mini-Batch

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

Clustering K-Means Mini-Batch este o variantă a clusteringului K-Means în care dimensiunea setului de date luat în considerare este limitată. Clustering K-Means normal funcționează pe întregul set de date/batch deodată, în timp ce clustering K-Means Mini-Batch împarte setul de date în subseturi. Mini-batch-urile sunt eșantionate aleatoriu din întregul set de date și pentru fiecare nouă iterație, un nou eșantion aleatoriu este selectat și utilizat pentru a actualiza poziția centroidurilor.

În clustering K-Means Mini-Batch, clusterurile sunt actualizate cu o combinație a valorilor mini-batch ș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ă schimbări în clusteruri.

Rezultatele studiilor privind eficacitatea clusteringului K-Means Mini-Batch sugerează că poate reduce cu succes timpul de calcul, cu un compromis mic în calitatea clusterurilor.

Apliicații ale Clusteringului K-Means

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

Clustering K-Means poate fi aplicat la clasificarea documentelor, grupând documentele pe baza caracteristicilor cum ar fi subiecte, etichete, utilizarea cuvintelor, metadate și alte caracteristici ale documentelor. De asemenea, poate fi utilizat pentru a clasifica utilizatorii ca roboți sau nu roboți pe baza modelelor de activitate, cum ar fi postări și comentarii. Clustering 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 cum ar fi comorbidități, vârstă, istoricul pacientului, etc.

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