A K -közép klaszterezési módszer egyszerű. mi pedig az alapvető algoritmus egy leírásával kezdjük. Első lépésként kiválasztunk K darab kezdő középpontot, ahol K a felhasználó által megadott paraméter, nevezetesen a klaszterek kívánt száma. Ezután minden adatpontot a hozzá legközelebb eső középponthoz rendelünk, és az így képzett csoportok lesznek a kiinduló klaszterek. Ezután mindegyik klaszter középpontját a klaszterhez rendelt pontok alapján frissítjük. A hozzárendelési és frissítési lépéseket felváltva folytatjuk addig, amíg egyetlen pont sem vált klasztert, vagy ezzel egyenértékűen, míg a középpontok ugyanazok nem maradnak.

A K -közép módszert formálisan a 8.1. algoritmus írja le. A módszer működését a 8.3. ábra szemlélteti, amely bemutatja, hogy hogyan ér el az algoritmus három kezdeti középpontból négy lépésben a végső klaszterekhez. Ezeken és más K -közép módszereket megjelenítő ábrákon a részábrák bemutatják (1) a középpontokat az iterációs lépés elején, és (2) a pontok hozzárendelését ezekhez a középpontokhoz. A középpontokat a ``+'' szimbólum, az ugyanahhoz a klaszterhez tartozó pontokat pedig ugyanaz a jel ábrázolja.

A 8.3. (a) ábrán látható első lépésben adatpontokat választunk ki középpontnak, amelyek mindegyike egy-egy nagyobb ponthalmazba esik. Ebben a példában az átlagok lesznek a középpontok. Miután minden pontot hozzárendeltük valamelyik középponthoz, frissítjük a középpontokat. Az ábrák ismét minden lépés kezdeti középpontjait, valamint a már hozzájuk rendelt pontokat mutatják. A második lépésben a pontokat az újraszámolt középpontokhoz rendeljük, és a középpontok újbóli frissítése következik. A második, harmadik, valamint negyedik lépések (8.3. (b), (c) és (d) ábrák) során a középpontok közül kettő az ábra alsó részén elhelyezkedő, két kisebb pontcsoport felé mozdul el. Amikor a K -közép algoritmus véget ér a negyedik lépés (8.3. (d) ábra) után, mivel nem történik több változás, a középpontok a pontok természetes csoportjait azonosítják.

Bizonyos szomszédsági függvények és középpont-típusok kombinációja esetén a K -közép módszer mindig egy megoldáshoz konvergál, azaz a módszer mindig elér egy olyan állapotot, amikor a pontok már nem lépnek át más klaszterbe, és ezért a középpontok már nem változnak. Mivel azonban a konvergencia jelentős része a korai lépések során történik, a 8. 1. algoritmus 5. sorában található feltétel egy gyengébbre cserélhető, például arra, hogy az ismétlés csak addig történjen, amíg az adatpontok több mint 1%-a vándorol.

A továbbiakban az alapvető K -közép módszer lépéseit tárgyaljuk részletesebben, majd az algoritmus idő- és tárbonyolultságát vizsgáljuk meg.

Pontok legközelebbi középponthoz rendelése

Ahhoz, hogy egy pontot a legközelebbi középponthoz tudjunk rendelni, szükségünk van egy olyan közelségi (távolsági) mértékre, amely mennyiségileg határozza meg a ``közelség'' fogalmát a vizsgált speciális adatoknál. Az euklideszi ( L 2 ) távolságot gyakran használjuk euklideszi térben elhelyezkedő pontoknál, míg dokumentumoknál alkalmasabb a koszinusz hasonlóság. Vannak azonban más közelségi mértékek is, melyek hasznosak lehetnek bizonyos típusú adatok esetén. Ilyen például a Manhattan ( L 1 ) távolság is, amelyet euklideszi térben elhelyezkedő adatokra lehet alkalmazni, valamint a Jaccard mérték, melyet dokumentumok esetén használnak előszeretettel.

A K -közép algoritmus általában egyszerű hasonlósági mértékeket használ, mivel az algoritmus újra meg újra kiszámolja a pontok és a középpontok közötti hasonlóságot. Néhány esetben, mint például az alacsony dimenziójú euklideszi terekben elhelyezkedő adatok esetén, azonban lehetőség van arra, hogy elkerüljük sok hasonlóság kiszámítását, így gyorsítva fel jelentősen a K -közép algoritmust. A 8.2.3. szakaszban leírt kettéosztó K -közép módszer egy másik megközelítés, amely a K -közép módszert azzal gyorsítja fel, hogy a kiszámolt hasonlóságok számát csökkentjük.

Középpontok és célfüggvények

Az algoritmus negyedik lépését elég általánosan úgy fogalmaztuk meg, hogy ``újraszámoljuk a klaszterek középpontjait'', mivel a középpont számításának módja változhat a közelségi mértéktől és a klaszterezés céljától függően. A klaszterezés célját jellemzően egy célfüggvény fejezi ki, amely a pontok egymás közötti vagy a pontok és a középpont közötti közelségtől (távolságtól) függ, például minimalizáljuk a pontok és a hozzájuk legközelebbi középpont négyzetes távolságának az összegét. Ezt két példával szemléltetjük. A lényeg azonban az, hogy amint meghatároztunk egy közelségi mértéket és egy célfüggvényt, a középpont, melyet választanunk kell, gyakran matematikailag meghatározható. A matematikai részleteket a 8.2.6. szakaszban adjuk meg, itt egy nem matematikai tárgyalást nyújtunk.

Adatok az euklideszi térben

Tekintsünk olyan adatokat, amelyek közelségi mértéke az euklideszi távolság. Célfüggvényként, amely egy klaszterezés minőségét méri, a négyzetes hibák összegét (SSE -- sum of the squared error) használjuk. Más szavakkal, minden pont esetén kiszámoljuk a hibát, azaz a legközelebbi középponttól mért euklideszi távolságot, majd a négyzetes hibák teljes összegét vesszük. A K -közép algoritmus két különböző futása során kapott két különböző klaszterhalmaz közül azt részesítjük előnyben, amelynek négyzetes hibaösszege kisebb, mivel ez azt jelenti, hogy ennek a klaszterezésnek a prototípusai (középpontjai) jobban képviselik a klasztereikben található pontokat. A 8.1. táblázat jelöléseivel az SSE definíciója a következő:

SSE= ∑ i=1 K ∑ x∈ C i d ( c i ,x) 2 , (8.1)

ahol d két, euklideszi térben elhelyezkedő objektum közötti standard euklideszi ( L 2 ) távolság.

Ezen feltételek mellett megmutatható (lásd a 8.2.6. szakaszban), hogy a a négyzetes hibaösszeget minimalizáló középpont az átlag. A 8.1. táblázat jelöléseivel az i -edik klaszter középpontját (átlagát) a (8.2) egyenlet adja meg.

c i = 1 m i ∑ x∈ C i x (8.2)

Szemléltetésképpen egy, három kétdimenziós pontot (úgymint (1,1) , (2,3) és (6,2) ) tartalmazó klaszter középpontja ((1+2+6)/3,((1+3+2)/3)=(3,2) .

A K -közép algoritmus harmadik és negyedik lépésének az SSE (vagy általánosabban, a célfüggvény) minimalizálása a cél. A harmadik lépésben klasztereket hozunk létre úgy, hogy a pontokat a hozzájuk legközelebb eső középponthoz rendeljük, amely minimalizálja az SSE-t középpontok egy adott halmazára. A negyedik lépésben újraszámoljuk a középpontokat, így csökkentve tovább az SSE-t. Az algoritmus 3. és 4. lépése azonban csak a lokális minimum megtalálását garantálja az SSE-re nézve, mivel csak a középpontok és a klaszterek speciális megválasztása mellett optimalizálja az SSE-t, nem minden lehetséges esetre. A későbbiekben láthatunk egy példát az optimálisnál rosszabb klaszterezésre.

Dokumentum adatok

Annak szemléltetésére, hogy a K -közép módszer nem szorítkozik euklideszi térben elhelyezkedő adatokra, tekintsük a koszinusz hasonlóságot, amelyet dokumentumokban található adatok közötti hasonlóság mérésére használhatunk. Feltételezzük, hogy a dokumentum adatokat sec:document_term_matrix. oldalon leírt dokumentum-kifejezés mátrixszal fejezzük ki. Célunk az, hogy maximalizáljuk az egy klaszterben lévő dokumentumok hasonlóságát a klaszter középpontjához. Ezt a mennyiséget a klaszter kohéziójának (cohesion) nevezzük. Ezen célfüggvény esetén megmutatható, hogy egy klaszter középpontja -- akárcsak az euklideszi adatoknál -- a mintaátlag. A teljes SSE-hez hasonló mennyiség a teljes kohézió, melyet a (8.3) egyenlet ad meg.

Teljes kohézió= ∑ i=1 K ∑ x∈ C i koszinusz(x, c i ) (8.3)

Az általános eset

Számos olyan választás van a közelségi függvényre, a középpontra és a célfüggvényre, amelyeket az alapvető K -közép algoritmusban használhatunk és amelyek garantáltan konvergálnak. A 8.2. táblázat néhány lehetséges választást ismertet, többek között az általunk fentebb tárgyalt két eljárást is. Megjegyezzük, hogy a Manhattan ( L 1 ) távolság és a távolságok összegének minimalizálása célfüggvény esetén az alkalmas középpont egy klaszter pontjainak a mediánja.

A táblázat utolsó sorában a Bregman divergencia (2.4.5. szakasz) valójában közelségi mértékek egy osztálya, amely magába foglalja a négyzetes euklideszi távolságot ( L 2 2 ), a Mahalanobis távolságot és a koszinusz-hasonlóságot. A Bregman divergencia függvények fontossága abban áll, hogy bármelyik ilyen függvény felhasználható egy olyan K -közép típusú klaszterező algoritmus alapjaként, ahol a középpont a mintaátlag. Pontosabban, ha egy Bregman divergenciát választunk közelségi függvénynek, akkor az eredményül kapott klaszterező algoritmus a K -közép algoritmus szokásos tulajdonságaival fog rendelkezni a konvegenciát, a lokális minimumot, stb. tekintve. Ilyen tulajdonságokkal rendelkező klaszterező eljárást továbbá az összes lehetséges Bregman divergenciához el lehet készíteni. A koszinusz hasonlóságot vagy a négyzetes euklideszi távolságot használó K -közép algoritmusok valójában a Bregman divergencián alapuló általános klaszterező eljárás egyedi esetei.

A K -közép algoritmus további tárgyalása során kétdimenziós adatokkal dolgozunk, mivel ezen az adattípuson könnyen magyarázható el az eljárás. Ahogyan azonban azt az utolsó pár bekezdés sugallja, a K -közép módszer egy általános klaszterező eljárás, és adattípusok olyan széles skáláján alkalmazható, mint a dokumentumok és az idősorok.

Kezdő középpontok választása

Ha a kezdeti középpontokat véletlenszerűen választjuk, akkor a K -közép módszer minden futása különböző teljes SSE-t szolgáltat. A jelenséget kétdimenziós pontok a 8.3. ábrán látható halmazával szemléltetjük, amely pontok három természetes klaszteréből áll. A 8.4. (a) ábra egy olyan klaszterezési megoldást mutat, amely a három klaszteres SSE globális minimuma, míg a 8.4. (b) ábrán egy olyan, az optimálisnál rosszabb klaszterezést láthatunk, amely csak lokális minimum.

A megfelelő kezdő középpontok kiválasztása a K -közép eljárás kulcslépése. Egy általános megközelítése, hogy véletlenszerű kezdő középpontokat választunk, ám ez gyakran gyenge klasztereket eredményez.

8.1. Példa

(Rossz kezdő középpontok) A véletlenszerűen kiválasztott kezdeti középpontok lehetnek rosszak is. Erre szolgáltatunk példát a 8.3. és a 8.4. ábrákon használt adathalmaz segítségével. Az ábrák két különböző kezdeti középpontokkal végrehajtott klaszterezés eredményét mutatják. (Mindkét ábrán keresztekkel jelöltük a különböző iterációknál a klaszterközéppontokat.) A 8.3. ábrán bár az összes kezdeti középpont mind egy természetes klaszterből van, az eljárás mégis megtalálja az SSE-t minimalizáló klaszterezést. A 8.5. ábrán azonban hiába tűnik úgy, hogy jobb a kezdeti középpontok eloszlása, az optimálisnál rosszabb klaszterezést kapunk nagyobb négyzetes hibával.

8.2. Példa

(A véletlen kezdőértékadás korlátai) A kezdő középpontok kiválasztására egy széles körben használt módszer, hogy többször futtatjuk le az algoritmust, futásonként véletlenszerűen választott kezdőpontok különböző halmazával, majd a legkisebb SSE-vel rendelkező klaszterhalmazt választjuk ki. Bár egyszerű, ez a stratégia nem minden esetben működik jól, sikere az adathalmaztól és a keresett klaszterek számától függ. Mindezt a 8.6. (a) ábrán látható minta adathalmazt használva szemléltetjük. Az adatok két klaszterpárból állnak, ahol mindkét (felső-alsó) pár esetén a párok tagjai közelebb vannak egymáshoz, mint a másik párbeli klaszterekhez. A 8.6. (b--d) ábra azt mutatja, hogy ha klaszterpáronként két-két kezdeti középponttal kezdünk, még akkor is, ha mindkét középpont ugyanabba a klaszterbe esik, a középpontok úgy rendezik át magukat, hogy az ``igazi'' klasztereket találjuk meg. Ugyanakkor a 8.7. ábrán az látható, hogy ha az egyik klaszterpárban csak egy, míg a másikban három középpont van, akkor két igazi klaszter összeolvad, egy igazi klaszter pedig kettéhasad.

Megjegyezzük, hogy optimális klaszterezést kapunk mindaddig, amíg két kezdeti középpont található akárhol egy klaszterpárban, mivel a középpontok úgy rendeződnek át, hogy mindegyik klaszterbe egy kerül. Sajnos ahogy a klaszterek száma nő, úgy egyre nagyobb eséllyel esik legalább egy klaszterpárba csupán egyetlen kezdő középpont. (Lásd a 4. feladatot az 578. oldalon.) Ebben az esetben, mivel a klaszterpárok távolabb esnek, mint a párokon belül található klaszterek, a K -közép algoritmus nem képes átrendezni a középpontokat a klaszterpárok között, és így csak lokális minimumot ér el.

A véletlenszerűen választott kezdeti középpontok használatával kapcsolatos problémák miatt, amelyeket még a többszöri újraindítás sem képes leküzdeni, gyakran alkalmaznak más módszereket a kezdőértékadás során. Az egyik hatásos hatásos megközelítés, hogy mintát veszünk a pontokból és egy hierarchikus klaszterező módszerrel klaszterezzük őket. A hierarchikus klaszterezésből K klasztert nyerünk ki, és ezen klaszterek középpontjai lesznek a kezdő középpontok. Ez a megközelítés gyakran hatásos, de csak akkor praktikus a használata, ha (1) a minta viszonylag kicsi, azaz nagysága pár száztól pár ezerig terjed (mivel a hierarchikus klaszterezés költséges), valamint (2) K viszonylag kicsi a mintanagysághoz képest.

A következő eljárás a kezdeti középpontok kiválasztásának egy másik megközelítése. Első pontnak válasszunk egy véletlenszerű pontot vagy válasszuk az összes pont középpontját. Ezután mindegyik egymás utáni kezdeti középpontnak azt a pontot választjuk, amely a legmesszebb esik a már kiválasztott középpontoktól. Ezáltal kezdeti középpontok egy olyan halmazát kapjuk, amely garantáltan nem csupán véletlenszerűen választott, de jól elkülönülő is egyben. Sajnos azonban egy ilyen megközelítés nagy sűrűségű területekbe (klaszterekbe) eső pontok helyett inkább kiugró értékek választhat. Továbbá a kezdeti középpontok aktuális halmazától legtávolabb eső pont kiszámítása költséges feladat. Ezen problémák áthidalása érdekében ezt a módszert gyakran egy, a pontokból vett mintán alkalmazzák. Mivel a kiugró értékek ritkák, általában nem jelennek meg egy véletlen mintában. Ezzel szemben valószínűleg minden sűrű területről kiválasztása kerülnek pontok, hacsak nem túl kicsi a minta. Továbbá a kezdő középpontok megtalálásához szükséges számítások is nagymértékben csökkennek, mivel a mintanagyság sokkal kisebb, mint pontok száma.

A későbbiekben még két olyan másik megközelítést is tárgyalunk, amelyek hasznosak a jobb minőségű (kisebb SSE értékű) klaszterezések előállításánál: a K -közép módszer egy változatának használát, amely kevésbé érzékeny a kezdőértékadási problémákra (kettéosztó K -közép módszer), valamint utófeldolgozás használatát a létrejövő klaszterek ``kijavítására''.

Idő- és tárbonyolultság

A K -közép módszer tárigénye szerény, mivel csak az adatpontokat és a középpontokat tároljuk el. Pontosabban, a szükséges tárhely O((m+K)n) , ahol m a pontok, n pedig az attribútumok száma. A módszer időigénye szintén szerény -- lineárisan nő az adatpontok számával. Részletesen, a szükséges idő O(I*K*m*n) , ahol I a konvergenciához szükséges iterációk száma. Mint említettük, az I gyakran kicsi, és rendszerint minden baj nélkül korlátozható, mivel a legtöbb változás az első néhány iteráció alatt történik. Következésképpen a K -közép módszer lineáris m -re (a pontok számára), valamint egyszerű és hatékony, feltéve, hogy a klaszterek K száma jelentősen kisebb, mint m .

Üres klaszterek kezelése

A korábban leírt alap K -közép módszer egyik hibája, hogy üres klaszterek jöhetnek létre, amennyiben egy klaszternek nem jutnak pontok a hozzárendelési lépés során. Ha ez történik, akkor egy eljárásra van szükségünk, amely kicserél egy középpontot, mivel ellenkező esetben a négyzetes hiba szükségtelenül nagy lesz. Egy lehetséges megközelítés, hogy a jelenlegi középpontoktól legmesszebb eső pontot választjuk. Ha más nem is történik, ez kiküszöböli azt a pontot, amely a legtöbbel járul hozzá a teljes négyzetes hibához. Egy másik megközelítés, hogy az új középpontot a legnagyobb SSE-vel rendelkező klaszterből választjuk. Ez általában szétvágja a klasztert, és így csökkenti a klaszterezés teljes SSE értékét. Ha több üres klaszter van, akkor ezek az eljárások többször megismételhetőek.

Kiugró értékek

Ha négyzetes hiba kritériumot használunk, a kiugró értékek helytelenül befolyásolhatják a megtalált klasztereket. A kiugró értékek jelenléte miatt az eredményül kapott klaszterközéppontok (prototípusok) lehet, hogy nem lesznek olyan reprezentatívak, mint egyébként, és így az SSE is nagyobb lesz. Emiatt gyakran hasznos a kiugró értékek előzetes felfedezése és eltávolítása. Fontos azonban figyelemmel lenni arra, hogy vannak bizonyos klaszterező alkalmazások, melyek esetén a kiugró értékeket nem szabad eltávolítani. Adattömörítésre használt klaszterezésnél minden pontot klaszterezni kell, valamint néhány esetben, mint például a pénzügyi elemzések, a nyilvánvalóan kiugró értékek (például szokatlanul nyereséges ügyfelek) lehetnek a legérdekesebb pontok.

Egy nyilvánvaló kérdés az, hogy hogyan azonosítsuk a kiugró értékeket. Számos, kiugró értékek azonosítására szolgáló módszert fogunk tárgyalni ch:anomaly 10. fejezetben. Ha olyan megközelítéseket alkalmazunk, melyek a klaszterezés előtt távolítják el a kiugró értékeket, elkerüljük a nehezen klaszterezhető pontok klaszterezését. Vagylagosan a kiugró értékek azonosíthatóak egy utófeldolgozási lépésben is. Számon tarthatjuk például, hogy a pontok egyenként mennyivel járulnak hozzá az SSE értékéhez, és eltávolíthatjuk azokat a pontokat, melyeknek szokatlanul nagy a hozzájárulása, főleg többszöri futtatás során. A kis klasztereket is el akarhatjuk távolítani, mivel ezek gyakran kiugró értékek csoportjait reprezentálják.

Az SSE csökkentése utófeldolgozással

A négyzetes hibaösszeg (SSE) csökkentésének egy kézenfekvő módja több klaszter keresése, azaz nagyobb K érték használata. Sok esetben azonban úgy szeretnénk javítani az SSE értékét, hogy nem akarjuk növelni a klaszterek számát. Ez gyakran lehetséges, mivel a K -közép módszer jellemzően egy lokális minimumba konvergál. Különféle módszereket használnak az eredményül kapott klasztereket ``javítgatására'' egy kisebb SSE értékű klaszterezés előállításának érdekében. A stratégia az, hogy az egyedi klaszterekre összpontosítunk, mivel a teljes SSE egyszerűen az egyes klaszterek SSE hozzájárulásának összege. (Elkerülendő az esetleges félreértéseket, a teljes SSE és klaszter SSE terminológiát használjuk.) A teljes SSE-t meg tudjuk változtatni a klasztereken különféle műveleteket végrehajtva, mint például a klaszterek szétvágása vagy összevonása. Az egyik általánosan használt megközelítés klaszter szétvágási és összevonási fázisok felváltva történő használata. Egy szétvágási fázis során klasztereket bontunk fel, míg egy összevonási fázis során klasztereket egyesítünk. Ilyen módon gyakran lehetséges a lokális minimumból kiugrani és továbbra is a kívánt számú klaszterből álló klaszterezést előállítani. A következőkben néhány, a szétvágási és összevonási fázisokban használt módszert sorolunk fel.

Két olyan stratégia, amely a teljes SSE-t a klaszterek számának növelésével csökkenti:

Egy klaszter szétvágása:

A legnagyobb SSE értékű klasztert választjuk általában, de szétvághatjuk azt a klasztert is, amelynél egy bizonyos attribútum szórása a legnagyobb.

Egy új klaszterközéppnt bevezetése:

Gyakran az összes klaszterközépponttól legtávolabbi pontot választjuk. Ez a pont könnyen meghatározható, ha nyomon követjük azt, hogy az egyes pontok mennyivel járulnak hozzá az SSE értékéhez. Egy másik megközelítés, ha véletlenszerűen választunk az összes pont közül vagy a legnagyobb SSE értékű pontok közül.

Két stratégia, mely úgy csökkenti a klaszterek számát, hogy közben minimalizálni próbálja a teljes SSE növekedését:

Egy klaszter eloszlatása:

Ezt a klaszterhez tartozó középpont eltávolításával és a pontjainak a többi klaszterhez történő hozzárendelésével érjük el. Ideális esetben azt a klasztert választjuk, amelynek eloszlatása a legkevésbé növeli a teljes SSE értékét.

Két klaszter összevonása:

Jellemzően azokat klasztert válaszjuk, amelyek középpontjai a legközelebb vannak egymáshoz, bár egy másik, talán jobb megközelítés annak a két klaszternek az összevonása, amely a legkisebb növekedést eredményezi a teljes SSE értékében. Ez a két összevonási stratégia rendre megegyezik a centroid módszer és a Ward módszer nevű hierarchikus klaszterező módszereknél használtakkal. Mindkét módszert a 8.3. szakasz tárgyalja.

A középpontok növekményes frissítése

Ahelyett, hogy az összes pont egy klaszterhez történő hozzárendelése után frissítjük a középpontokat, a frissítés történhet növekményesen, az egyes pontok egy klaszterhez való hozzárendelése után. Vegyük észre, hogy ez minden lépésben vagy két frissítését igényel a klaszterközéppontokhoz, vagy egyet sem, mivel egy pont vagy egy új klaszterbe kerül át (két frissítés), vagy az aktuális klaszterében marad (nincs frissítés). Egy növekményes frissítési stratégia garantálja, hogy nem jönnek létre üres klaszterek, mivel kezdetben minden klaszter egyetlen pontot tartalmaz, és ha egy klaszternek csak egy pontja van, akkor az a pont mindig a tartalmazó klaszterhez lesz ismét hozzárendelve.

Ráadásul, ha a növekményes frissítést használjuk, módosítható a hozzáadásra kerülő pont relatív súlya, például a klaszterezés előrehaladtával gyakran csökkentik a pontok súlyát. Bár ez nagyobb pontosságot és gyorsabb konvergenciát eredményezhet, sok esetben nehéz lehet a relatív súlyok megfelelő megválasztása. Ezek a frissítési kérdések hasonlóak a mesterséges neurális hálók súlyainak frissítésével kapcsolatosakhoz.

A növekményes frissítés egy másik előnye, hogy az ``SSE minimalizálás'' mellett más célokat is alkalmazhat. Tegyük fel, hogy egy tetszőleges célfüggvény segítségével mérjük egy klaszterhalmaz jóságát. Amikor egy pontot feldolgozunk, minden lehetséges klaszter hozzárendelésre kiszámíthatjuk a célfüggvény értékét, majd választhatjuk a célfüggvényt optimalizálót. Alternatív célfüggvényekre a 8.2. szakasz ad konkrét példákat.

Hátrányként az hozható fel, hogy a középpontok növekményes frissítésnél fellép egy sorrendségi függőség. Más szavakkal, az előállított klaszterek függhetnek a pontok feldolgozási sorrendjétől. Bár a probléma kezelése megcélozható a pontok feldolgozási sorrendjének randomizálásával, az alapvető K -közép módszer középpont frissítési megközelítésénél -- ahol a frissítés az összes pont klaszterhez való hozzárendelése után történik -- nincs sorrendi függés. A növekményes frissítés egy kissé költségesebb is. A K -közép módszer azonban eléggé gyorsan konvergál, így a klasztert váltó pontok száma gyorsan válik viszonylag kicsivé.

A kettéosztó K -közép algoritmus az alapvető K -közép algoritmus egy egyszerű kiterjesztése, amely egy egyszerű ötleten alapul: hogy K klasztert kapjunk, osszuk ketté az összes pontot két klaszterbe, majd válasszuk ki az így létrejött klaszterek közül az egyiket, és osszuk ismét ketté. Folytassuk ezt addig, míg elő nem állítunk K számú klasztert. Az algoritmus részleteit 8.2.3. algoritmus adja meg.

Számos különböző mód van a kettéosztandó klaszter kiválasztására. Minden lépésben választhatjuk a legnagyobb klasztert, a legnagyobb SSE értékű klasztert, vagy használhatunk a méreten és az SSE értékén alapuló feltételt is. Különböző választások különböző klasztereket eredményeznek.

Gyakran úgy finomítjuk tovább a kapott klasztereket, hogy a középpontjaikat kezdő középpontokként használjuk fel az alapvető K -közép algoritmus számára. Ez azért szükséges, mert -- bár a K -közép algoritmus garantáltan egy olyan klaszterezést talál, amely egy lokális minimumot jelet a SSE szempontjából -- a kettéosztó K -közép módszerben a K -közép algoritmust ``lokálisan'' használjuk, azaz egyedi klaszterek kettéosztására. Emiatt a végső klaszterhalmaz nem egy olyan klaszterezést képvisel, amely a teljes SSE egy lokális minimuma.

8.3. Példa

(Kettéosztó K -közép algoritmus és inicializálás) Annak szemléltetésére, hogy a kettéosztó K -közép kevésbé érzékeny az inicializálási problémákra, a 8.8. ábrán mutatjuk be, hogyan talál az algoritmus négy klasztert az eredetileg a 8.6. (a) ábrán látható adathalmazban. Az első iterációban az algoritmus két klaszterpárt talál, a második iterációban a jobb szélső, a harmadik iterációban pedig a bal szélső klaszterpár kerül kettéosztásra. A kettéosztó K -középnél kevesebb gondot jelent az inicializálás, mivel több próba kettéosztást végez és a legkisebb SSE értékűt veszi, és mert minden lépésben csak két középpont van.

Végül, használhatjuk a kettéosztó K -közép módszert egy hierarchikus klaszterezés előállítására is, ha a klaszterek K -közép módszerrel történő kettéosztása során rögzítjük a létrejövő klaszterzések sorozatát.

A K -közép módszernek és változatainak számos korlátja van különböző típusú klaszterek megtalálása tekintetében. Különösen a ``természetes'' klaszterek észlelése jelent nehézséget a K -közép számára, amikor a klaszterek nem gömb alakúak, vagy jelentősen különböző méretűek vagy sűrűségűek. Ezt a 8.9., 8.10. és 8.11. ábra szemlélteti. A 8.9. ábrán a K -közép nem képes megtalálni a három természetes klasztert, mivel az egyik sokkal nagyobb a másik kettőnél, ezért a nagyobb klaszter felbomlik, míg az egyik kisebb összeolvad a nagyobb klaszter egy részével. A 8.10. ábrán a K -közép azért nem találja meg a három természetes klasztert, mivel a két kisebb klaszter sokkal sűrűbb a nagyobb klaszternél. Végül a 8.11. ábrán a K -közép két olyan klasztert talál, amelyben a két természetes klaszter részei keverednek, mivel a természetes klaszterek nem gömb alakúak.

A szóban forgó három esetben az a nehézség, hogy a K -közép módszer célfüggvénye nem megfelelő az általunk megtalálni kívánt fajta klaszterekre, mivel azt egyforma méretű és sűrűségű gömb alakú klaszterek vagy jól elkülönülő klaszterek minimalizálják. Bizonyos értelemben azonban felül lehet kerekedni ezeken a korlátokon, ha a felhasználó hajlandó elfogadni egy olyan klaszterezést, amely a természetes klasztereket több alklaszterre bontja. A 8.12. ábra azt mutatja, hogy mi történik az előbbi három adathalmazzal, ha két vagy három helyett hat klasztert keresünk. Minden kisebb klaszter tiszta abban az értelemben, hogy csak egy természetes klaszter pontjait tartalmazza.

A K -közép módszer egyszerű és adattípusok széles skálájára alkalmazható. A módszer eléggé hatékony is, annak ellenére, hogy gyakran végeznek többszöri futtatást. Néhány változata, beleértve a kettéosztó K -közép módszert, még hatékonyabb és kezdőértékadási problémákra kevésbé érzékeny. A K -közép módszer azonban nem alkalmas az adatok minden típusára. Nem képes kezelni nem gömb alakú, vagy különböző méretű és sűrűségű klasztereket, bár jellemzően képes tiszta alkalszterek megtalálására, amennyiben elegendően nagy számú klasztert írunk elő. A módszernek problémát okoz a kiugró értékeket tartalmazó adatok klaszterezése. A kiugró értékek észlelése és eltávolítása jelentősen segít ezekben az esetekben. Végül a K -közép módszer csak olyan adatokra alkalmazható, amelyekre létezik a középpont (centroid) fogalma. Egy kapcsolódó módszer, a K -medoid klaszterezés, nem tartalmazza ezt a megkötést, ugyanakkor költségesebb is.

Ebben a szakaszban a K -közép módszer mögötti matematika mélyére hatolunk. A szakasz, amely a folyamatosság megtörése nélkül át is ugorható, a kalkulus parciális deriváltakon keresztüli ismeretét feltételezi. Az optimalizációs módszerekben való jártasság, különösen a gradiens módszeren alapulóakban, szintén segítséget nyújthat.

Ahogy korábban is említettük, ha a célfüggvényt úgy határozzuk meg, hogy ``minimalizáld az SSE-t'', akkor a klaszterezés optimalizációs problémaként is kezelhető. Az egyik mód, ahogy ezt a problémát -- a globális optimum megtalálását -- megoldhatjuk az, hogy a pontokat az összes lehetséges módon klaszterekbe osztjuk, majd azt a klaszterhalmazt választjuk, amely legjobban kielégíti a célfüggvényt, azaz amely minimalizálja a teljes SSE-t. Természtesen ez a kimerítő stratégia megvalósíthatatlanul számításigényes, aminek eredményeképpen praktikusabb megoldást kell keresnünk, még ha egy ilyen megközelítés nem is garantálja az optimális megoldás megtalálását. Egy módszer, amely gradiens módszer (gradient descent) néven ismert, azon alapszik, hogy gondosan kiválaszt egy kezdeti megoldást, majd a következő két lépést ismétli: kiszámolja a változást a célfüggvényt legjobban optimalizáló megoldáshoz, majd frissíti a megoldást.

Feltételezzük, hogy az adatok egydimenziósak, így a távolság: d(x,y)= (x−y) 2 . Ez a feltevés nem változtat semmi lényegesen, de nagymértékben egyszerűsíti a jelöléseket.

A K -közép módszer levezetése egy SSE-t minimalizáló algoritmusból

Ebben a szakaszban bemutatjuk, hogyan lehet a K -közép algoritmus középpontjait matematikailag meghatározni abban az esetben, ha a közelségi függvény az euklideszi távolság, és az SSE minimalizálása a cél. Speciálisan megvizsgáljuk, hogy hogyan lehet a legjobban frissíteni a klaszterek középpontjait azért, hogy a klaszter SSE-t minimalizáljuk. Matematikailag kifejezve a (8.1) egyenlet minimalizálása a cél, amelyet egydimenziós adatokra szabva megismétlünk itt:

SSE= ∑ i=1 K ∑ x∈ C i ( c i −x) 2 . (8.4)

Itt C i az i -edik klaszter, x egy C i -beli pont, c i pedig az i -edik klaszter átlaga. A jelölések teljes listáját a 8.1. táblázat tartalmazza.

A c k k -adik középpontot, amely a (8.4) egyenletet minimalizálja, megkaphatjuk az SSE differenciálásával, a derivált nullával egyenlővé tételével, és az egyenlet az alább jelzett módon történő megoldásával:

∂ ∂ c k SSE= ∂ ∂ c k ∑ i=1 K ∑ x∈ C i ( c i −x) 2

= ∑ i=1 K ∑ x∈ C i ∂ ∂ c k ( c i −x) 2

= ∑ x∈ C k 2*( c k − x k )=0

∑ x∈ C k 2*( c k − x k )=0⇒ m k c k = ∑ x∈ C k x k ⇒ c k = 1 m k ∑ x∈ C k x k

Így, ahogy azt korábban is jeleztük, a klaszter pontjainak átlaga a legjobb középpont, amely egy klaszter SSE-jét minimalizálja.

A K -közép módszer levezetése az abszolút hiba összege esetén

Annak szemléltetésére, hogy a K -közép algoritmus különböző fajtájú célfüggvények esetén alkalmazható, megmutatjuk, hogy az adatokat hogyan lehet K klaszterbe osztani úgy, hogy a pontok klasztereik középpontjától mért Manhattan ( L 1 ) távolságainak az összege minimális legyen. A következő egyenlet által definiált L 1 abszolút hiba összege (SAE -- sum of absolute errors) minimumát keressük, ahol d L 1 az L 1 távolságot jelöli. A jelölést egyszerűsítendő ismét egydimenziós adatokkal dolgozunk, azaz d L 1 =| c i −x| .

SAE= ∑ i=1 K ∑ x∈ C i d L 1 ( c i ,x) (8.5)

A (8.5) egyenletet minimalizáljuk c k -ra, a k -adik középpontra, amelyet megoldhatunk a SAE differenciálásával, a deriváltat nullával egyenlővé téve, és megoldva a kapott egyenletet.

∂ ∂ c k SAE= ∂ ∂ c k ∑ i=1 K ∑ x∈ C i | c i −x|

= ∑ i=1 K ∑ x∈ C i ∂ ∂ c k | c i −x|

= ∑ x∈ C k ∂ ∂ c k | c k −x|=0

∑ x∈ C k ∂ ∂ c k | c k −x|=0⇒ ∑ x∈ C k sgn(x− c k )=0

Az egyenletet c k -ra megoldva kapjuk, hogy c k =medián{x∈ C k } , azaz a klaszterbeli pontok mediánja. Egy ponthalmaz mediánjának egyszerű a számítása, és kevésbé érzékeny a kiugró értékek általi torzításra.