Kaj je združevanje v skupine K-Means?

K-pomeni združevanje v gruče nenadzorovano učenje algoritma in izmed vseh algoritmov za nenadzorovano učenje je morda najpogosteje uporabljeno združevanje v gruče K-means, zahvaljujoč njegovi moči in preprostosti. Kako natančno deluje združevanje v gruče K-means?

Kratek odgovor je, da K-pomeni združevanje v gruče ustvarjanje referenčne točke (centroid) za želeno število razredov in nato dodeljevanje podatkovnih točk skupinam razredov glede na to, katera referenčna točka je najbližja. Čeprav je to kratka definicija za gručenje K-sredstev, si vzemimo nekaj časa, da se poglobimo v gručevanje K-sredstev in pridobimo boljšo intuicijo o tem, kako deluje.

Definiranje grozdenja

Preden preučimo natančne algoritme, ki se uporabljajo za izvedbo združevanja v gruče K-means, si vzemimo nekaj časa za splošno opredelitev združevanja v gruče.

Grozdi so le skupine elementov, združevanje v gruče pa je samo uvrščanje elementov v te skupine. V smislu podatkovne znanosti, algoritmi združevanja v gruče cilj narediti dve stvari:

• Zagotovite, da so vse podatkovne točke v gruči med seboj čim bolj podobne.
• Zagotovite, da so si vse podatkovne točke v različnih gručih čim bolj različne.

Algoritmi združevanja v gruče združujejo predmete skupaj na podlagi neke metrike podobnosti. To se pogosto naredi z iskanjem "centroida" različnih možnih skupin v naboru podatkov, čeprav ne izključno. Obstaja vrsta različnih algoritmov za združevanje v gruče, vendar je cilj vseh algoritmov za združevanje v gruče enak, določiti skupine, ki so del nabora podatkov.

K-pomeni združevanje v gruče

K-Means Clustering je ena najstarejših in najpogosteje uporabljenih vrst algoritmov za združevanje v gruče in deluje na podlagi vektorska kvantizacija. Za izhodišče je izbrana točka v prostoru, nato pa se vektorji narišejo iz izhodišča do vseh podatkovnih točk v naboru podatkov.

Na splošno lahko združevanje v skupine K-means razdelimo na pet različnih korakov:

• Vse primere postavite v podmnožice, kjer je število podmnožic enako K.
• Poiščite srednjo točko/centroid na novo ustvarjenih particij gruče.
• Na podlagi teh centroidov dodelite vsako točko določeni gruči.
• Izračunajte razdalje od vsake točke do centroidov in dodelite točke skupinam, kjer je razdalja od centroidov najmanjša.
• Ko so točke dodeljene grozdom, poiščite novo težišče grozdov.

Zgornji koraki se ponavljajo, dokler proces usposabljanja ni končan.

V začetni fazi so centroidi nameščeni nekje med podatkovnimi točkami.
Fotografija: Weston.pace prek wikimedia commons, GNU Free Documentation License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Druga možnost je, da si po postavitvi centroidov združevanje v skupine K-means predstavljamo kot preklapljanje med dvema različnima fazama: označevanje podatkovnih točk in posodabljanje centroidov.

V drugem koraku se metrika razdalje, kot je evklidska razdalja, uporabi za izračun, kateremu centroidu je dana točka najbližje, nato pa se točke dodelijo razredu tega centroida. Fotografija: Weston.pace prek Wikimedia Commons, GNU Free Doc License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

V fazi označevanja podatkovnih točk je vsaki podatkovni točki dodeljena oznaka, ki jo umesti v gručo, ki pripada najbližjemu centroidu. Najbližji centroid se običajno določi s kvadratom evklidske razdalje, čeprav je mogoče uporabiti druge metrike razdalje, kot so manhattanska razdalja, kosinus in razdalja Jaccard, odvisno od vrste podatkov, ki se dovajajo v algoritem za združevanje v gruče.

V tretjem koraku se centroid premakne na povprečje vseh podatkovnih točk. Razredi se nato prerazporedijo. Fotografija: Weston.pace prek Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

V koraku posodobitve centroida se centroid izračuna z iskanjem srednje razdalje med vsemi podatkovnimi točkami, ki so trenutno v gruči.

Kako izbrati pravo vrednost za "K"

Glede na to, da je združevanje v gruče K-means nenadzorovan algoritem in število razredov ni vnaprej znano, kako se odločite za ustrezno število razredov/pravo vrednost za K?

Ena tehnika za izbiro prave vrednosti K se imenuje "tehnika komolca”. Tehnika komolca je sestavljena iz izvajanja algoritma za združevanje povprečij K za vrsto različnih vrednosti K in uporabe metrike natančnosti, običajno vsote kvadratne napake, za določitev, katere vrednosti K dajejo najboljše rezultate. Vsota kvadratov napake se določi z izračunom srednje razdalje med središčem gruče in podatkovnimi točkami v tej gruči.

Izraz "tehnika komolca" izhaja iz dejstva, da ko narišete SSE glede na različne vrednosti K, ima dobljeni črtni izris pogosto obliko "komolca", kjer se SSE hitro zmanjša za prvih nekaj vrednosti K, potem pa se izravna. V takšnih pogojih je vrednost K, ki se nahaja na komolcu, najboljša vrednost za K, saj po tej vrednosti hitro padajo donosi.

Mini-paketno združevanje v skupine K-Means

Ko nabori podatkov rastejo, se povečuje tudi čas izračuna. Osnovno združevanje v gruče K-sredstev lahko traja dolgo časa, če se izvaja na ogromnih naborih podatkov, zato so bile narejene prilagoditve združevanja v gruče K-sredstev, ki omogočajo zmanjšanje prostorskih in časovnih stroškov algoritma.

Mini-serija K-pomeni združevanje v gruče je različica združevanja v gruče K-sredstev kjer je velikost obravnavanega nabora podatkov omejena. Običajno združevanje v skupine K-means deluje na celotnem naboru podatkov/paketu naenkrat, medtem ko združevanje v skupine z mini-serijami K-means razdeli nabor podatkov na podnabore. Mini serije so naključno vzorčene iz celotnega nabora podatkov in za vsako novo ponovitev se izbere nov naključni vzorec, ki se uporabi za posodobitev položaja centroidov.

Pri mini-paketnem združevanju v gruče K-Means se gruče posodobijo s kombinacijo vrednosti mini-paketov in stopnje učenja. Hitrost učenja se z iteracijami zmanjšuje in je inverzna številu podatkovnih točk v določeni gruči. Učinek zmanjšanja stopnje učenja je, da se zmanjša vpliv novih podatkov in doseže konvergenca, ko po več iteracijah ni sprememb v grozdih.

Rezultati študij o učinkovitosti združevanja v gruče Mini-batch K-means kažejo, da lahko uspešno skrajša čas izračuna z rahlim kompromisom v kakovosti gruče.

Aplikacije združevanja v gruče K-Means

Gručenje K-means je mogoče varno uporabiti v kateri koli situaciji, kjer je mogoče podatkovne točke segmentirati v različne skupine/razrede. Tukaj je nekaj primerov običajnih primerov uporabe za združevanje v gruče K-mean.

Gručenje K-means bi lahko uporabili za klasifikacijo dokumentov, združevanje dokumentov na podlagi funkcij, kot so teme, oznake, uporaba besed, metapodatki in druge funkcije dokumenta. Uporablja se lahko tudi za razvrščanje uporabnikov med bote ali nebote na podlagi vzorcev dejavnosti, kot so objave in komentarji. Združevanje v skupine K-means se lahko uporablja tudi za razvrščanje ljudi v skupine na podlagi stopenj zaskrbljenosti pri spremljanju njihovega zdravja, na podlagi značilnosti, kot so sočasne bolezni, starost, anamneza bolnika itd.

Gručenje K-means se lahko uporablja tudi za bolj odprte naloge, kot je ustvarjanje sistemov priporočil. Uporabnike sistema, kot je Netflix, je mogoče združiti v skupine glede na vzorce gledanja in priporočeno podobno vsebino. Združevanje v gruče K-means bi se lahko uporabilo za naloge odkrivanja nepravilnosti, ki poudarjajo morebitne primere goljufij ali okvarjenih predmetov.