Mi az a K-Means klaszterezés?

A K-közép klaszterezés egy felügyelet nélküli tanulás algoritmus, és az összes felügyelt tanulási algoritmus közül a K-közép klaszterezés lehet a legszélesebb körben használt, erejének és egyszerűségének köszönhetően. Hogyan működik pontosan a K-közép klaszterezés?

A rövid válasz az, hogy a K-közeli klaszterezés úgy működik referenciapont létrehozása (egy súlypont) a kívánt számú osztályra, majd adatpontok hozzárendelése osztályklaszterekhez amely alapján melyik referenciapont van a legközelebb. Bár ez egy gyors definíció a K-közép klaszterezéshez, szánjunk egy kis időt, hogy mélyebben belemerüljünk a K-közép klaszterezésbe, és jobban megértsük, hogyan működik.

Klaszterezés meghatározása

Mielőtt megvizsgálnánk a K-közép klaszterezés végrehajtásához használt pontos algoritmusokat, szánjunk egy kis időt a klaszterezés általános meghatározására.

A klaszterek csak elemek csoportjai, a fürtözés pedig csak az elemeket ezekbe a csoportokba helyezi. Adattudományi értelemben klaszterező algoritmusok célja két dolog:

• Győződjön meg arról, hogy a fürt összes adatpontja a lehető leghasonlóbb egymáshoz.
• Győződjön meg arról, hogy a különböző klaszterekben lévő összes adatpont a lehető legkülönbözőbb legyen.

A klaszterező algoritmusok az elemeket valamilyen hasonlósági mérőszám alapján csoportosítják. Ez gyakran úgy történik, hogy megkeresik az adatkészlet különböző lehetséges csoportjainak „centroidját”, bár nem kizárólagosan. Számos különböző klaszterezési algoritmus létezik, de az összes klaszterezési algoritmus célja ugyanaz, hogy meghatározzák az adatkészletben rejlő csoportokat.

K-Means klaszterezés

A K-Means Clustering az egyik legrégebbi és leggyakrabban használt klaszterezési algoritmus, amely a vektorkvantálás. A térben van egy pont, amelyet origóként választanak ki, majd vektorokat rajzolnak az origóból az adatkészlet összes adatpontjába.

Általában a K-közép klaszterezés öt különböző lépésre bontható:

• Helyezzen minden példányt részhalmazokba, ahol az alhalmazok száma egyenlő K-val.
• Keresse meg az újonnan létrehozott fürtpartíciók középpontját/centroidját.
• Ezen súlypontok alapján rendeljen minden pontot egy adott klaszterhez.
• Számítsa ki a távolságokat minden ponttól a súlypontokig, és rendeljen pontokat a klaszterekhez, ahol a távolság a súlyponttól a legkisebb.
• Miután a pontokat hozzárendelte a klaszterekhez, keresse meg a klaszterek új súlypontját.

A fenti lépéseket addig ismételjük, amíg az edzési folyamat be nem fejeződik.

A kezdeti fázisban a centroidokat valahol az adatpontok között helyezik el.
Fotó: Weston.pace a wikimedia commons-on keresztül, GNU Free Documentation License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Alternatív megoldásként a centroidok elhelyezése után elképzelhetjük a K-közép klaszterezést két különböző fázis között: az adatpontok címkézése és a centroidok frissítése.

A második lépésben egy távolságmérőt, például az euklideszi távolságot használjuk annak kiszámításához, hogy egy adott pont melyik súlyponthoz van a legközelebb, majd a pontokat hozzárendeljük a súlypont osztályához. Fotó: Weston.pace a Wikimedia Commonson keresztül, GNU Free Doc License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

Az adatpont címkézési fázisában minden adatponthoz hozzárendelnek egy címkét, amely a legközelebbi centroidhoz tartozó klaszterbe helyezi. A legközelebbi súlypontot általában négyzetes euklideszi távolság segítségével határozzák meg, bár a klaszterező algoritmusba betáplált adatok típusától függően más távolságmérők is használhatók, mint például a Manhattan távolság, a koszinusz és a Jaccard távolság.

A harmadik lépésben a súlypontot az összes adatpont átlagára mozgatjuk. Ezt követően az osztályokat újraosztják. Fotó: Weston.pace, Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

A súlypont-frissítési lépésben a súlypontot úgy számítják ki, hogy megtalálják a klaszterben jelenleg található összes adatpont közötti átlagos távolságot.

Hogyan válasszuk ki a megfelelő „K” értéket

Tekintettel arra, hogy a K-közép klaszterezés egy nem felügyelt algoritmus, és az osztályok száma előre nem ismert, hogyan dönti el a megfelelő osztályok számát/a K megfelelő értékét?

A megfelelő K-érték kiválasztásának egyik technikája a „a könyök technika”. A könyöktechnika abból áll, hogy egy K-közép klaszterezési algoritmust futtatunk különböző K-értékek tartományára, és egy pontossági mérőszámot, jellemzően a Sum of Squared Error-t használunk annak meghatározására, hogy K mely értékei adják a legjobb eredményt. A négyzetes hiba összegét úgy határozzuk meg, hogy kiszámítjuk a klaszter súlypontja és a klaszter adatpontjai közötti átlagos távolságot.

A „könyöktechnika” kifejezés onnan ered, hogy amikor az SSE-t a K különböző értékeinek figyelembevételével ábrázolja, az eredményül kapott vonaldiagram gyakran „könyök” alakú lesz, ahol az SSE gyorsan csökken K első néhány értékénél, de aztán kiegyenlít. Ilyen körülmények között a könyöknél található K értéke a legjobb K értéke, mivel ezen érték után gyorsan csökken a hozam.

Mini-Batch K-Means klaszterezés

Az adatkészletek növekedésével a számítási idő is nő. Az alapvető K-közép fürtözés hosszú időt vehet igénybe, ha hatalmas adathalmazokon fut, és ennek eredményeként a K-közép fürtözést módosították, hogy csökkentsék az algoritmus térbeli és időbeli költségeit.

Mini-Batch K-klaszterezést jelent a K-közép klaszterezés egyik változata ahol a figyelembe vett adathalmaz mérete korlátozva van. A normál K-közép fürtözés egyszerre működik a teljes adatkészleten/kötegen, míg a Mini-batch K-közép fürtözés részhalmazokra bontja az adatkészletet. A mini-kötegek véletlenszerűen mintát vesznek a teljes adatkészletből, és minden új iterációhoz egy új véletlenszerű mintát választanak ki, és ezt használják a centroidok helyzetének frissítésére.

A Mini-Batch K-Means fürtözésben a fürtök a mini kötegértékek és a tanulási sebesség kombinációjával frissülnek. A tanulási sebesség az iterációk során csökken, és ez az egy adott fürtben elhelyezett adatpontok számának a fordítottja. A tanulási sebesség csökkentésének az a hatása, hogy az új adatok hatása csökken, és konvergencia érhető el, ha több iteráció után a klaszterekben nincs változás.

A Mini-batch K-means klaszterezés hatékonyságára vonatkozó tanulmányok eredményei arra utalnak, hogy sikeresen csökkentheti a számítási időt a klaszter minőségének enyhe kompromisszumával.

A K-Means klaszterezés alkalmazásai

A K-közép klaszterezés biztonságosan használható minden olyan helyzetben, ahol az adatpontok külön csoportokba/osztályokba szegmentálhatók. Íme néhány példa a K-közép klaszterezés általános használati eseteire.

A K-means klaszterezés alkalmazható a dokumentumok osztályozására, a dokumentumok csoportosítására olyan jellemzők alapján, mint a témák, címkék, szóhasználat, metaadatok és egyéb dokumentum jellemzők. Használható arra is, hogy a felhasználókat botként vagy nem botként osztályozza a tevékenységi minták, például a bejegyzések és megjegyzések alapján. A K-means klaszterezés arra is használható, hogy az embereket az egészségi állapotuk megfigyelése során aggodalomra okot adó szint alapján csoportokba sorolják, olyan jellemzők alapján, mint a társbetegségek, életkor, betegtörténet stb.

A K-means klaszterezés nyitottabb feladatokhoz is használható, például ajánlórendszerek létrehozásához. Az olyan rendszerek felhasználói, mint a Netflix, csoportosíthatók a megtekintési minták és az ajánlott hasonló tartalmak alapján. A K-means klaszterezés használható anomáliák felderítésére, kiemelve a csalás vagy a hibás tételek lehetséges eseteit.