Sok klaszterező algoritmus tárigénye lineárisnál rosszabb, például a hierarchikus klaszterezésnél a memóriaigény rendszerint O( m 2 ) , ahol m az objektumok száma. 10 000 000 objektumra például a szükséges memória mennyisége 10 14 -nel arányos, ez egy olyan szám, ami még jócskán meghaladja a jelenlegi rendszerek kapacitását. Megjegyezzük, hogy a közvetlen adathozzáférés szükségessége miatt sok klaszterező algoritmust nem lehet könnyen úgy módosítani, hogy hatékonyan használják a másodlagos tárhelyet (lemezt), aminél a közvetlen adathozzáférés lassú. Hasonlóan, néhány klaszterező algoritmus számításigénye lineárisnál rosszabb. A szakasz hátralevő részében olyan különböző módszereket tárgyalunk, amelyek egy klaszterező algoritmus számítás- vagy tárigényét csökkentik. A CURE és BIRCH algoritmusok ezen módszerek egy részét használják.

Többdimenziós vagy térbeli hozzáférési módszerek

Számos eljárás -- a K -közép, a Jarvis-Patrick klaszterezés és a DBSCAN -- meg kell, hogy keresse a legközelebbi középpontot, egy pont legközelebbi szomszédait, vagy az összes pontot egy megadott távolságon belül. Használhatóak a többdimenziós vagy térbeli hozzáférési módszereknek nevezett speciális eljárások ezen feladatok hatékonyabb elvégzéséhez, legalábbis kis dimenziószámú adatokra. Ezek a módszerek, mint például a k d-fa vagy az R * -fa, tipikusan az adattér egy hierarchikus felosztását állítják elő, amit fel lehet használni egy pont legközelebbi szomszédainak megtalálásához szükséges idő csökkentésére. Megjegyezzük, hogy a rács-alapú klaszterező sémák ugyancsak particionálják az adatteret.

Szomszédságra vonatkozó korlátok

Egy másik megközelítés a szomszédság-számítások elkerülésére korlátok alkalmazása. Euklideszi távolságok használata esetén például a háromszög egyenlőtlenség révén sok távolságszámítás elkerülhető. A hagyományos K -közép minden egyes lépésénél ki kell értékelni például, hogy vajon egy pont maradjon-e a jelenlegi klaszterében, vagy pedig át kell tenni egy új klaszterbe. Ha ismerjük a középpontok távolságát és egy pont távolságát azon klaszter (most frissített) középpontjától, amelyhez jelenleg tartozik, akkor használhatjuk a háromszög egyenlőtlenséget ahhoz, hogy elkerüljük a pont távolságának kiszámítását a többi középponttól. (Lásd a 21. feladatot a 672. oldalon.)

Mintavétel

A mintavétel egy másik megközelítés az időbonyolultság csökkentésére. Ebben a megközelítésben egy mintát veszünk a pontokból, ezeket a pontokat klaszterezzük, majd a kimaradó pontokat a kapott klaszterekhez rendeljük hozzá -- tipikusan a legközelebbi klaszterhez. Ha a minta pontjainak száma m , akkor egy O( m 2 ) algoritmus időbonyolultsága O(m) -re csökken. A mintavétel egy központi problémája ugyanakkor, hogy elveszthetünk kis klasztereket. A CURE algoritmus tárgyalásánál adunk módszert annak a vizsgálatára, hogy milyen gyakran lépnek fel ilyen problémák.

Az adatobjektumok particionálása

Egy másik gyakori megközelítés az időbonyolultság csökkentésére az adatok diszjunkt halmazokra történő felosztása valamilyen hatékony módszerrel, majd a halmazok külön-külön történő klaszterezése. A klaszterek végső halmaza vagy ezeknek a független klaszter-halmazoknak az uniója, vagy ezen független klaszter-halmazok kombinálásával és/vagy finomításával kapható meg. Mi csak a kettéosztó K -közép módszert (8.2.3. szakasz) tárgyaljuk ebben a szakaszban, bár sok egyéb felosztó megközelítés lehetséges. Egy ilyen megközelítést írunk majd le, amikor a CURE algoritmust ismertetjük később ebben szakaszban.

Ha a K -közép módszert használjuk K számú klaszter megtalálására, akkor minden egyes iterációban kiszámoljuk minden egyes pont távolságát minden egyes klaszterközépponttól. Ha K nagy, akkor ez nagyon költséges tud lenni. A kettéosztó K -közép a teljes ponthalmazzal kezd és a K -közép módszert használja ismételten egy létező klaszter kettévágására mindaddig, amíg el nem jut K klaszterhez. A pontok távolságát minden egyes lépésben csak két klaszterközépponttól kell kiszámolni. Az első lépéstől eltekintve, amelyben a szétvágandó klaszter az összes pontból áll, csak a pontok egy részhalmazának távolságát számítjuk ki az éppen szóbajövő két középponttól. Emiatt a tény miatt a kettéosztó K -közép lényegesen gyorsabban tud futni, mint a megszokott K -közép.

Összefoglalás

A klaszterezés egy másik megközelítése az adatok tipikusan egyetlen menetben történő összefoglalása, majd az összefoglalt adatok klaszterezése. Például a leader algoritmus (lásd 1l. feladatot exer:leader_algo. oldalon) vagy a legközelebbi klaszterbe helyez egy adatobjektumot (ha ez a klaszter elég közel van), vagy egy új klasztert kezd, amely az aktuális objektumot tartalmazza. Ez az algoritmus lineáris az objektumok számában és használható az adatok összefoglalására úgy, hogy a kapott eredményre azután más klaszterező módszert alkalmazhatunk. Egy hasonló elvet használ a BIRCH algoritmus.

Párhuzamos és osztott számítások

Ha nem lehetséges előnyt kovácsolni az előzőekben leírt eljárásokból, vagy ezek a megközelítések nem nyújtják a kívánt pontosságot vagy számítási idő csökkenést, akkor más megközelítésekre van szükség. Nagyon hatékony módszer a számítás elosztása több processzor között.

A BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies -- kiegyensúlyozott iteratív csökkentés és klaszterezés hierarchiákkal) egy nagyon hatékony klaszterező módszer euklideszi vektorterek adataira, azaz olyan adatokra, ahol értelmük van átlagoknak. A BIRCH egy menetben hatékonyan tud klaszterezni ilyen adatokat és ezt a klaszterezést további menetekben tudja javítani. A BIRCH ugyancsak hatékonyan tudja kezelni a kiugró értékeket.

A BIRCH a klaszterező jellemző (CF -- Clustering Feature) és a CF fa fogalmán alapul. Az ötlet az, hogy adatpontok (vektorok) egy klasztere megadható egy (N,LS,SS) számhármassal, ahol N a klaszter pontjainak a száma, LS a pontok összege, SS pedig a pontok négyzetösszege. Ezek közönséges statisztikai mennyiségek, amiket növekményesen lehet frissíteni és amikből számos fontos mennyiséget ki lehet számolni, mint például egy klaszter középpontját és varianciáját (szórását). A varianciát a klaszterek átmérőjének mérőszámaként használjuk.

Ezeket a mennyiségeket a klaszterek közötti távolság kiszámítására is használhatjuk. A legegyszerűbb megközelítés a középpontok közötti L 1 (Manhattan) vagy L 2 (euklideszi) távolság kiszámítása. Az egyesített klaszter átmérőjét (varianciáját) is használhatjuk távolságként. A BIRCH a klaszterek számos távolságmértékét definiálja, de mindegyiket ki lehet számolni az alapstatisztikák segítségével.

A CF fa egy magasság-kiegyensúlyozott fa. Minden belső csúcs [C F i ,gyere k i ] alakú bejegyzéseket tartalmaz, ahol gyere k i egy mutató az i -edik gyerek csúcsra. Az egy bejegyzéshez tartozó hely és a lapméret határozza meg egy belső csúcs bejegyzéseinek számát. Az egyes bejegyzések helyét pedig a pontok attribútumainak száma határozza meg.

A levél csúcsok a CF   i klaszterező jellemzők egy sorozatából állnak, ahol minden klaszterező jellemző egy korábban már megvizsgált ponthalmazt ábrázol. A levélcsúcsokra az a megszorítás vonatkozik, hogy átmérőjük kisebb egy paraméterként megadható T küszöbértéknél. Az egyes bejegyzések által elfoglalt hely a lapmérettel együtt meghatározzák egy levél bejegyzéseinek számát.

A T küszöbérték paraméter módosításával szabályozható a fa magassága. A T a klaszterezés finomságát szabályozza, azaz annak mértékét, hogy mennyire csökkentjük az eredeti adathalmaz adatait. A cél az, hogy a CF fát a T paraméter szükség szerinti beállításával a központi memóriában tudjuk tárolni.

Egy CF fát építünk az adatok beolvasása során. Ahogy az egyes adatpontokhoz érünk, bejárjuk a CF fát a gyökérből indulva és minden szinten a legközelebbi csúcsot választva. Amikor végül az aktuális adatponthoz azonosítjuk a legközelebbi levél klasztert, egy tesztet végzünk annak megállapításához, hogy ha az aktuális adatpontot hozzáadjuk a kiválasztott klaszterhez, akkor az új klaszter átmérője nagyobb lesz-e az adott T küszöbértéknél. Ha nem, akkor az adatpontot hozzáadjuk a kiválasztott klaszterhez a CF információk frissítésével. A levéltől a gyökérig minden csúcs klaszterinformációját is frissítjük.

Ha az új klaszter átmérője T -nél nagyobb, akkor egy új bejegyzést hozunk létre, ha a levélcsúcs még nem telt meg. Egyébként a levélcsúcsot fel kell bontani. A két legtávolabbi bejegyzést (klasztert) tekintjük magnak, a fennmaradó bejegyzéseket pedig aszerint osztjuk el a két új levélcsúcs között, hogy melyikük tartalmazza a közelebbi mag-klasztert. Ha felbontottuk a levélcsúcsot, a szülő csúcsot is frissítjük, valamint felbontjuk, ha szükséges, azaz ha megtelt. Ez a folyamat egészen a gyökérig folytatható.

A BIRCH minden felbontást egy egyesítési lépéssel folytat. Annál a belső csúcsnál, ahol a felbontás megállt, megkeressük a két legközelebbi bejegyzést. Ha ez a pár nem a felbontásból származó két bejegyzés, akkor kísérletet teszünk a bejegyzések és a hozzájuk tartozó gyerek csúcsok egyesítésére. Ennek a lépésnek a célja a helykihasználás javítása és az aszimmetrikus adatbeviteli sorrendből adódó problémák kiküszöbölése.

A BIRCH-nek a kiugró értékek eltávolítására is van módszere. Ha a fát újra kell építeni, mert megtelt a memória, akkor a kiugró értékeket opcionálisan ki lehet írni lemezre. (Kiugró értéknek egy olyan csúcsot tekintünk, amelynek az átlagosnál sokkal kevesebb adatpontja van.) A folyamat bizonyos pontjain átvizsgáljuk a kiugró értékeket, hogy beépíthetők-e a fába anélkül, hogy annak mérete növekedjen. Ha igen, akkor beépítjük, ha nem, akkor pedig töröljük őket.

A BIRCH a CF fa kezdeti létrehozásán túl számos fázisból áll. A BIRCH összes fázisát tömören a 9.13. algoritmus írja le.

A CURE (Clustering Using REpresentatives -- klaszterezés reprezentánsokkal) egy klaszterező algoritmus, ami különböző módszerek arzenálját használja egy olyan módszer megalkotásához, amely kezelni képes nagy adatállományokat, kiugró értékeket, valamint nem gömb alakú és nem egyforma méretű klasztereket. A CURE egy klasztert a klaszter több reprezentáns pontjával ad meg. Ezek a pontok fogják elméletileg a klaszter geometriáját és alakját tükrözni. Az első reprezentáns pontot úgy választjuk, hogy a klaszter középpontjától legtávolabbi pont legyen, míg a fennmaradó pontokat pedig úgy, hogy az összes eddig választott ponttól a legtávolabb legyenek. Ilyen módon a reprezentáns pontok természetszerűleg viszonylag jó eloszlásúak. A kiválasztandó pontok száma egy paraméter, de azt találták, hogy 10 vagy annál nagyobb érték jól működik.

Ha kiválasztottuk a reprezentáns pontokat, akkor ezeket a középpont felé húzzuk össze egy α szorzóval. Ez segít a középponttól általában távolabb lévő kiugró értékek hatásának mérséklésében, mivel ezek jobban zsugorodnak. Például egy a középponttól 10 egység távolságra lévő reprezentáns pont 3 egységgel mozdul el ( α=0,7 esetén), míg egy 1 egységnyi távolságra levő reprezentáns pont csak 0,3 egységgel.

A CURE összevonó hierarchikus sémát használ a tényleges klaszterezésre. Két klaszter közötti távolság a bármely két reprezentáns pontjuk közötti távolság minimuma (miután összehúztuk őket a megfelelő középpontok irányába). Bár ez a séma nem igazán hasonlít egyik eddig látott hierarchikus sémához sem, ekvivalens a középpont-alapú hierarchikus klaszterezéssel, ha α=0 , és nagyjából ugyanaz, mint az egyszerű kapcsolású hierarchikus klaszterezés, ha α=1 . Vegyük észre, hogy bár hierarchikus klaszterező sémát használunk, a CURE célja a felhasználó által megadott számú klaszter megtalálása.

A CURE kihasználja a hierarchikus klaszterezési folyamat bizonyos jellemzőit, hogy eltávolítsa a kiugró értékeket a klaszterező folyamat két különböző pontján. Először, ha egy klaszter lassan nő, az azt jelentheti, hogy főleg kiugró értékekből áll, mivel a kiugró értékek definíció szerint távol vannak a többitől és nem fognak gyakran összekapcsolódni más pontokkal. A CURE-ban a kiugró értékek eltávolításának ez az első fázisa tipikusan akkor történik, amikor a klaszterek száma a pontok eredeti számának harmada. A kiugró értékek eltávolításának második fázisára akkor kerül sor, amikor a klaszterek száma K nagyságrendű ( K a kívánt klaszterszám). Ezen a ponton a kis klasztereket ismét eltávolítjuk.

Mivel a CURE bonyolultsága a legrosszabb esetben O( m 2 logm) , nem alkalmazható közvetlenül nagy adathalmazokra. Ezen okból a CURE két eljárást használ a klaszterezési folyamat felgyorsítására. Az első eljárás egy véletlen mintát vesz és hierarchikus klaszterezést végez a mintabeli adatpontokra. Ezt egy utolsó menet követi, amelynek során az adathalmaz minden egyes fennmaradó pontját valamelyik klaszterhez rendeljük hozzá, azt a klaszter választva, amely a hozzá legközelebbi reprezentánst tartalmazza. A CURE mintavételi módszerét később részletesebben tárgyaljuk.

Bizonyos esetekben a klaszterezéshez szükséges minta még mindig túl nagy és egy második kiegészítő eljárásra van szükség. Ebben az esetben a CURE particionálja a mintaadatokat, majd minden egyes partícióban klaszterezi a pontokat. Ezt az előklaszterezési lépést a közbenső klaszterek klaszterezése követi, majd egy utolsó menet, amely az adathalmaz minden egyes pontját a klaszterek valamelyikéhez rendeli hozzá. A CURE felosztó sémáját később szintén részletesebben tárgyaljuk.

A 9.14. algoritmus foglalja össze a CURE-t. Megjegyezzük, hogy K a klaszterek kívánt száma, m a pontok száma, p a partíciók száma, q pedig a partíciókban a pontok számának kívánt csökkenése, azaz a klaszterek száma egy partícióban m pq . Ezért a klaszterek teljes száma m q . Ha például m=10000 , p=10 , és q=100 , akkor minden partíció 10000/10=1000 pontot tartalmaz, 1000/100=10 klaszter lenne minden partícióban és 10000/100=100 klaszter lenne összesen.

Egy kulcskérdés a mintavételnél, hogy vajon a minta reprezentatív-e, azaz vajon megragadja-e az érdeklődésre számot tartó jellemzőket. A klaszterezésnél a kérdés az, hogy vajon ugyanazokat a klasztereket találjuk-e meg a mintában, mint az egész objektumhalmazban. Ideális esetben azt szeretnénk, hogy a minta minden egyes klaszterből tartalmazzon néhány objektumot és hogy a mintában külön klaszterbe kerüljenek azok az objektumok, amelyek külön klaszterbe tartoznak az egész adathalmazban.

Konkrétabb és elérhető cél annak (nagy valószínűséggel történő) biztosítása, hogy legalább néhány pontunk legyen minden egyes klaszterből. Az ehhez szükséges mintanagyság adathalmazról adathalmazra változik, és az objektumok számától valamint a klaszterek méretétől függ. A CURE alkotói levezettek egy korlátot a mintanagyságra, amely annak (nagy valószínűséggel történő) biztosításához szükséges, hogy legalább adott számú pontot kapjunk egy klaszterből. Ezt a korlátot a következő tétel adja meg könyvünk jelöléseivel.

9.1. Tétel

Legyen f egy részarány, ahol 0≤f≤1 . Az m i méretű C i klaszter esetén legalább f* m i objektumot fogunk kapni a C i klaszterből 1−δ valószínűséggel ( 0≤δ≤1 ), ha az s mintanagyságot a következő képlet adja meg:

s=fm+ m m i *log 1 δ + m m i log 1 δ 2 +2*f* m i *log 1 δ , (9.19)

ahol m az objektumok száma.

Bár fenti a kifejezés ijesztőnek tűnhet, meglehetősen egyszerűen használható. Tegyük fel, hogy 100 000 objektum van és a cél az, hogy 80% eséllyel megkapjuk az 1000 elemű C i klaszter objektumainak 10%-át. Ebben az esetben f=0,1 , δ=0,2 , m=100000 , m i =1000 , és így s=11962 . Ha a cél 5%-nyi minta C i -ből, ami 50 objektumot jelent, akkor 6440 elemű minta elegendő.

Megismételjük, hogy a CURE a mintavételt a következőképpen használja. Először egy mintát veszünk, majd a CURE algoritmust használjuk a minta klaszterezésére. Miután megtaláltuk a klasztereket, minden egyes nem klaszterezett pontot a legközelebbi klaszterhez rendelünk hozzá.

Particionálás

Amikor a mintavétel nem elég, a CURE egy felosztó megközelítést is alkalmaz. Az alapgondolat az, hogy osszuk fel a pontokat p számú m/p méretű csoportra, és használjuk a CURE-t az egyes partíciók klaszterezésére, hogy az az objektumok száma egy q≥1 tényezővel csökkenjen, ahol q -ra nagyjából úgy gondolhatunk, mint a partíciókban az átlagos klaszterméretre. Összességében m q klaszter kerül előállításra. (Megjegyezzük, hogy mivel a CURE minden egyes klasztert adott számú reprezentáns ponttal ad meg, a csökkenés aránya az objektumok számában nem q .) Ezt az előklaszterezési lépést az m/q közbülső klaszter végső klaszterezése követi, amely a kívánt ( K ) számú klasztert állítja elő. Mindkét klaszterező menet a CURE hierarchikus klaszterező algoritmusát alkalmazza és mindkettőt egy olyan végső menet követi, ami az adathalmaz minden egyes pontját valamelyik klaszterhez rendeli hozzá.

Kulcsfontosságú kérdés p és q megválasztásának módja. O( m 2 ) vagy nagyobb az olyan algoritmusok időbonyolultsága, mint például a CURE, ezenkívül azt is igénylik, hogy minden adat a központi memóriában legyen. Ezért p értékét elég kicsinek akarjuk választani ahhoz, hogy egy teljes partíció feldolgozható legyen a központi memóriában ``ésszerű'' időn belül. Jelenleg egy tipikus asztali számítógép néhány másodpercen belül el tudja végezni néhány ezer objektum hierarchikus klaszterezését.

Egy másik tényező p és q megválasztásánál a klaszterezés minőségére vonatkozik. A cél speciálisan olyan p és q értékek választása, hogy az ugyanabból a klaszterből származó objektumok végül ugyanabba a klaszterbe kerüljenek. A szemléltetéshez tegyük fel, hogy 1000 objektumunk és egy 100 elemű klaszterünk van. Ha véletlenszerűen hozunk létre 100 partíciót, akkor minden egyes partíció átlagosan csak egy pontot fog tartalmazni a klaszterünkből. Ezek a pontok valószínűleg más klaszterekből származó pontokkal kerülnek egy klaszterbe, vagy el lesznek dobva kiugró értékként. Ha viszont csak 10 partíciót hozunk létre 100 objektumból, de q értéke 50, akkor az átlagosan a klaszterünkből származó 10 pont valószínűleg kombinálódni fog más klaszterekből származó pontokkal, mert minden partícióra csak két klasztert kell előállítanunk. A q megválasztására vonatkozó, utolsóként említett problémának az elkerülésére a javasolt stratégia az, hogy ne egyesítsünk klasztereket, ha túlságosan különbözőek.