Ce este K-Means Clustering?

K-means clustering este an învățare nesupravegheată algoritm și dintre toți algoritmii de învățare nesupravegheați, gruparea K-means ar putea fi cea mai utilizată, datorită puterii și simplității sale. Cum funcționează exact gruparea K-means?

Răspunsul scurt este că gruparea 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 clusterelor de clase pe baza punctului de referință cel mai apropiat. Deși aceasta este o definiție rapidă pentru gruparea K-means, să luăm ceva timp pentru a ne aprofunda în gruparea K-means și să obținem o intuiție mai bună a modului în care funcționează.

Definirea clusterizării

Înainte de a examina algoritmii exacti utilizați pentru a realiza gruparea K-means, să ne luăm puțin timp pentru a defini gruparea în general.

Clusterele sunt doar grupuri de articole, iar gruparea înseamnă doar introducerea de elemente în acele grupuri. În sensul științei datelor, algoritmi de grupare scopul de a face două lucruri:

• Asigurați-vă că toate punctele de date dintr-un cluster sunt cât mai asemănătoare între ele.
• Asigurați-vă că toate punctele de date din grupuri diferite sunt cât mai diferite între ele.

Algoritmii de grupare grupează articolele pe baza unor metrici de similitudine. 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.

K-înseamnă grupare

K-Means Clustering este unul dintre cele mai vechi și mai frecvent utilizate tipuri de algoritmi de grupare și funcționează pe baza cuantificare vectorială. Există un punct în spațiu ales ca origine, iar vectorii sunt desenați de la origine la toate punctele de date din setul de date.

În general, gruparea K-means poate fi împărțită în cinci etape diferite:

• Plasați toate instanțele în subseturi, unde numărul de subseturi este egal cu K.
• Găsiți punctul/centroidul mediu al partițiilor cluster nou create.
• Pe baza acestor centroizi, atribuiți fiecare punct unui grup specific.
• Calculați distanțele de la fiecare punct la centroizi și atribuiți puncte clusterelor unde distanța de la centroid este minimă.
• După ce punctele au fost atribuite clusterelor, găsiți noul centroid al clusterelor.

Pașii de mai sus se repetă până la finalizarea procesului de antrenament.

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

Alternativ, după ce au fost plasați centroizii, putem concepe gruparea K-means ca schimbând înainte și înapoi între două faze diferite: etichetarea punctelor de date și actualizarea centroizilor.

În al doilea pas, o metrică a distanței, cum ar fi distanța euclidiană, este utilizată pentru a calcula de ce centroid este cel mai aproape un punct dat, iar apoi punctele sunt atribuite clasei acelui centroid. Foto: Weston.pace prin Wikimedia Commons, GNU Free Doc License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

În faza de etichetare a punctului de date, fiecărui punct de date i se atribuie o etichetă care îl plasează în clusterul aparținând celui mai apropiat centroid. Cel mai apropiat centroid este determinat în mod obișnuit folosind distanța euclidiană pătrată, deși alte metrici ale distanței, cum ar fi distanța Manhattan, Cosinus și distanța Jaccard, pot fi utilizate în funcție de tipul de date care sunt introduse în algoritmul de grupare.

În al treilea pas, centroidul sunt mutați la media tuturor punctelor de date. Clasele sunt apoi reatribuite. Foto: Weston.pace prin Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

În pasul de actualizare a centroidului, centroidul este calculat prin găsirea distanței medii dintre toate punctele de date conținute în prezent într-un cluster.

Cum să alegeți valoarea potrivită pentru „K”

Având în vedere că gruparea K-means este un algoritm nesupravegheat și numărul de clase nu este cunoscut în prealabil, cum vă decideți asupra numărului adecvat de clase/valoarea corectă pentru K?

O tehnică de selectare a valorii K corecte se numește „tehnica cotului”. Tehnica cotului constă în rularea unui algoritm de grupare K-means pentru o gamă de valori K diferite și utilizarea unei metrici de precizie, de obicei Suma erorii pătrate, pentru a determina care valori ale lui K dau cele mai bune rezultate. Suma erorii pătrate este determinată prin calcularea distanței medii dintre centroidul unui cluster și punctele de date din acel cluster.

Termenul „tehnică cot” provine din faptul că, atunci când trasați SSE cu privire la diferitele valori ale lui K, graficul de linii rezultat va avea adesea o formă de „cot”, unde SSE scade rapid pentru primele câteva valori ale lui K, dar apoi se nivelează. În astfel de condiții, valoarea lui K situată la cot este cea mai bună valoare pentru K, deoarece după această valoare există randamente în scădere rapidă.

Mini-loturi K-Means Clustering

Pe măsură ce seturile de date cresc, timpul de calcul crește și el. Clusteringul K-means de bază poate dura mult timp pentru a se finaliza atunci când este rulat pe seturi de date masive și, ca urmare, au fost făcute ajustări ale grupării K-means pentru a permite reducerea costurilor spațiale și temporale ale algoritmului.

Mini-Batch K înseamnă grupare este o variantă a grupării K-means unde dimensiunea setului de date luat în considerare este limitată. Gruparea K-means normală operează pe întregul set de date/lot simultan, în timp ce gruparea K-means mini-batch descompune setul de date în subseturi. Mini-loturile sunt eșantionate aleatoriu din întregul set de date și pentru fiecare nouă iterație o nouă probă aleatoare este selectată și utilizată pentru a actualiza poziția centroizilor.

În gruparea Mini-Batch K-Means, clusterele sunt actualizate cu o combinație a valorilor mini-loturi și o rată 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 se realizează convergența atunci când, după mai multe iterații, nu există modificări în clustere.

Rezultatele studiilor privind eficacitatea grupării Mini-batch K-means sugerează că poate reduce cu succes timpul de calcul cu un ușor compromis în calitatea clusterului.

Aplicații ale grupării K-Means

Gruparea 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 obișnuite pentru gruparea K-mean.

Gruparea K-means ar putea fi aplicată pentru clasificarea documentelor, gruparea documentelor pe baza unor caracteristici precum subiecte, etichete, utilizarea cuvintelor, metadate și alte caracteristici ale documentului. De asemenea, ar putea fi folosit pentru a clasifica utilizatorii ca boți sau nu pe baza tiparelor de activitate, cum ar fi postări și comentarii. Gruparea K-means poate fi, de asemenea, utilizată pentru a grupa oamenii în funcție de nivelurile de îngrijorare atunci când le monitorizează sănătatea, pe baza unor caracteristici precum comorbiditățile, vârsta, istoricul pacientului etc.

Gruparea K-means poate fi folosită și pentru sarcini mai deschise, cum ar fi crearea de sisteme de recomandare. Utilizatorii unui sistem precum Netflix pot fi grupați pe baza modelelor de vizualizare și a conținutului similar recomandat. Gruparea K-means ar putea fi utilizată pentru sarcinile de detectare a anomaliilor, evidențiind cazurile potențiale de fraudă sau articole defecte.