Egy m adatpontra vonatkozó m×m -es szomszédsági mátrixot meg lehet adni egy teljes gráfként, ahol minden csúcs össze van kötve az összes többivel és bármely két csúcs közötti él súlya megfelel a páronkénti közelségüknek. Bár minden objektum valamilyen szinten hasonló az összes többi objektumhoz, a legtöbb adathalmaz esetén az objektumok kis számú objektumhoz hasonlítanak nagyon és kissé hasonlóak az összes többi objektumhoz. Ez a tulajdonág használható a szomszédsági gráf (mátrix) olymódon történő ritkítására, hogy sok ilyen alacsony hasonlósági (magas különbözőségi) értéket 0-ra állítunk, mielőtt elkezdenénk a tulajdonképpeni klaszterező folyamatot. A ritkítást például elvégezhetjük úgy is, hogy minden olyan élt megszakítunk, amelyek hasonlósága (különbözősége) egy megadott küszöbérték alatt (felett) van, vagy csak olyan kapcsolatokat megtartva, amelyek a pontok k legközelebbi szomszédaihoz vezetnek. Az utóbbi megközelítés hozza létre az úgynevezett k -legközelebbi szomszéd gráfot.

A ritkításnak több előnyös tulajdonsága van:

A szomszédsági gráf ritkítását kezdőlépésnek kell tekinteni a tényleges klaszterező algoritmusok használata előtt. A tökéletes ritkítás után a megmaradó szomszédsági mátrix elméletileg a kívánt klasztereknek megfelelő összefüggő komponensekre bomlik fel, de a gyakorlatban ez ritkán történik meg. Könnyen előfordulhat, hogy egyetlen él kapcsolatot teremt két klaszter között vagy, hogy egy klaszter felbomlik több, nem összefüggő részklaszterre. Valóban, ahogy látni fogjuk a Jarvis-Patrick és az SNN sűrűség-alapú klaszterezés tárgyalásánál, a ritka szomszédsági gráfot gyakran módosítjuk ahhoz, hogy új szomszédsági gráfot kapjunk. Ez az új szomszédsági gráf ismét ritkítható. A klaszterező algoritmusok azzal a szomszédsági gráffal dolgoznak, amely az összes ilyen előfeldolgozó lépés után eredményként adódik. Ezt a folyamatot foglalja össze a 9.15. ábra.

A 8.3. szakaszban, ahol az agglomeratív hierarchikus klaszterező módszereket írtuk le, megjegyeztük, hogy felosztó hierarchikus klaszterező algoritmusok is léteznek. Láttunk is egy példát ilyen eljárásra, ez volt a kettéosztó K -közép a 8.2.3. szakaszban. Egy másik felosztó hierarchikus módszer, az MST, a szomszédsági gráf minimális feszítőfájával kezd, és úgy lehet tekinteni, mint a ritkítás egy alkalmazását a klaszterek megtalálására. Röviden írjuk le ezt az algoritmust. Érdekes módon ez az algoritmus ugyanazt a klaszterezést állítja elő, mint az egyszerű kapcsolású agglomeratív klaszterezés. (Lásd a 13. feladatot a 671. oldalon.)

Egy gráf minimális feszítőfája (MST -- minimum spanning tree) egy olyan részgráf, ami (1) nem tartalmaz kört, azaz fa, (2) a gráf minden csúcsát tartalmazza, és (3) minimális a teljes élsúlya az összes lehetséges feszítőfa közül. A minimális feszítőfa terminológia használata feltételezi, hogy csak különbözőségekkel vagy távolságokkal dolgozunk, mi is tartjuk magunkat ehhez a konvencióhoz. Ez nem jelent azonban korlátot, hiszen a hasonlóságokat át tudjuk alakítani különbözőségekké vagy módosíthatjuk a minimális feszítőfa fogalmát hasonlóságok kezeléséhez. A 9.16. ábrán látható egy példa néhány kétdimenziós pont minimális feszítőfájára.

A felosztó hierarchikus MST algoritmust mutatja a 9.7. algoritmus. Az első lépés az MST megkeresése az eredeti különbözőségi gráfban. Megjegyezzük, hogy a minimális feszítőfa tekinthető a ritkított gráf egy speciális típusának. A 3. lépést gráfritkításként is felfoghatjuk. Az MST tehát úgy tekinthető, mint egy olyan klaszterező algoritmus, amely a különbözőségi gráf ritkításán alapul.

Az OPOSSUM (Optimal Partitioning of Sparse Similarities Using METIS) egy klaszterező eljárás, amit kifejezetten a ritka, nagy dimenziószámú adatok klaszterezésére fejlesztettek ki, mint például a dokumentum vagy vásárlói kosár adatok. Az MST-hez hasonlóan a szomszédsági gráf ritkítása alapján végzi a klaszterezést. Az OPOSSUM azonban a METIS algoritmust használja, amit speciálisan ritka gráfok particionálására fejlesztettek ki. Az OPOSSUM lépéseit 9.4.3. algoritmus adja meg.

A használt hasonlósági mértékek azok, amelyek megfelelőek ritka, nagy dimenziószámú adatokra, mint például az általánosított Jaccard mérték vagy a koszinusz mérték. A METIS gráfparticionáló program egy ritka gráfot k diszjunkt komponensre bont, ahol k egy, a felhasználó által megadott paraméter, úgy, hogy (1) minimalizálja az élek súlyát (a hasonlóságot) a komponensek között és (2) kielégítsen egy egyensúlyi feltételt. Az OPOSSUM a következő két egyensúlyi feltétel egyikét használja: (1) az objektumok száma a klaszterekben legyen nagyjából egyforma, vagy (2) az attribútum értékek összege legyen nagyjából egyforma. A második feltétel hasznos lehet akkor, amikor az attribútumértékek például az egyes elemek költségét ábrázolják.

Erősségek és gyengeségek

Az OPOSSUM egyszerű és gyors. Az adatokat nagyjából azonos méretű klaszterekre bontja, ami a klaszterezés céljától függően tekinthető előnynek vagy hátránynak. Mivel nagyjából egyforma méretűeknek kell lenniük, a klaszterek felbomolhatnak vagy egyesülhetnek. Ha az OPOSSUM-ot nagy számú klaszter előállítására használjuk, akkor ezek a klaszterek azonban általában mégis nagyobb klaszterek viszonylag tiszta darabjai. Valóban, az OPOSSUM hasonló a következőként tárgyalt Chameleon klaszterező rutin kezdeti lépéséhez.

Az összevonó hierarchikus klaszterező módszerek a két leginkább hasonló klaszter egyesítésével működnek, ahol a klaszter-hasonlóság definíciója a konkrét algoritmustól függ. Néhány összevonó algoritmus, mint például a csoportátlag, két klaszter közötti kapcsolat erősségére (például a két klaszter pontjainak páronkénti hasonlóságára) alapozza a hasonlóságfogalmát, míg más módszerek, mint például az egyszerű kapcsolás, a klaszterek közelségét (például a különböző klaszterek pontjai közötti minimális távolságot) használják a klaszterek hasonlóságának mérésére. Bár két alapvető megközelítés létezik, csak az egyik használata hibákhoz vezethet a klaszterek egyesítésénél. Tekintsük a 9.17. ábrát, amely négy klasztert mutat. Ha a klaszterek közelségét használjuk egyesítési kritériumként (a különböző klaszterek pontjai közötti minimális távolsággal mérve), akkor a majdnem érintkező (c) és (d) kör alakú klasztereket egyesítenénk az (a) és (b) téglalap alakú klaszterek helyett, amelyeket egy kis rés választ el egymástól. Intuitív módon azonban az (a) és (b) téglalap alakú klasztereket kellene egyesítenünk. A 15. feladatban a 671. oldalon olyan helyzetre kell példát adni, ahol a kapcsolódás erejének alkalmazása ehhez hasonlóan az intuíciónkkal ellentétes eredményre vezet.

Egy másik probléma, hogy a legtöbb klaszterező módszernek egy globális (statikus) modellje van a klaszterekről. A K -közép azt feltételezi például, hogy a klaszterek gömb alakúak, míg a DBSCAN a klasztereket egyetlen sűrűségi küszöbérték alapján definiálja. A ilyen globális modellt használó klaszterező sémák nem képesek azokat az eseteket kezelni, amikor széles tartományban változnak a klaszterek között a klaszterek jellemzői, mint például a méret, alak és sűrűség. A klaszterek lokális (dinamikus) modellezése fontosságának egy példájaként tekintsük a 9.18. ábrát. Ha a klaszterek közelsége alapján döntjük el, hogy melyik klaszterpárt egyesítsük, ahogy ezt például az egyszerű kapcsolás klaszterező algoritmus alkalmazása esetén tennénk, akkor az (a) és (b) klasztereket egyesítenénk. Ekkor azonban nem vesszük figyelembe az egyes klaszterek jellemzőit. Konkrétan az egyes klaszterek sűrűségét hagyjuk figyelmen kívül. A viszonylag sűrű (a) és (b) klaszterekre a két klaszter közötti távolság jelentősen nagyobb, mint egy pont és a klaszteren belüli legközelebbi szomszédja közötti távolság. Nem ez a helyzet azonban a (c) és (d) klaszterre, amelyek viszonylag ritkák. Valóban, ha a (c) és (d) klasztereket egyesítjük, akkor olyan klasztert kapunk, amely hasonlóbbnak tűnik az eredeti klaszterekhez annál a klaszternél, amelyet az (a) és (b) klaszterek egyesítésével kapnánk.

A Chameleon egy agglomeratív klaszterező algoritmus, amely az előző két bekezdés kérdéseit célozza meg. Az adatok egy hatékony gráfparticionáló algoritmus segítségével történő kezdeti felosztását egy új hierarchikus klaszterező sémával kombinálja, ami a közelség és összekapcsoltság fogalmát használja a klaszterek lokális modellezésével együtt. Az alapötlet az, hogy két klasztert csak akkor szabad összevonni, ha az eredményül adódó klaszter hasonló a két eredeti klaszterhez. Az önhasonlóság fogalmát írjuk le először , majd pedig a Chameleon algoritmus további részleteit adjuk meg.

Annak eldöntése, hogy mely klasztereket egyesítsük

A 8.3. szakaszban vizsgált agglomeratív hierarchikus klaszterező módszerek ismétlődően a két legközelebbi klasztert vonják össze és elsősorban abban különböznek egymástól, hogy miképpen definiálják a klaszterek közelségét. Ezzel ellentétben a Chameleon arra törekszik, hogy azt a klaszterpárt vonja össze, amely olyan klasztert eredményez, ami a leghasonlóbb az eredeti klaszterpárhoz a közelséggel és összekapcsoltsággal mérve. Mivel ez a megközelítés csak a klaszterpárokon múlik és nem egy globális modellen, a Chameleon kezelni tudja az olyan adatokat, amelyek jelentősen különböző jellemzőjű klasztereket tartalmaznak.

A következőkben részletesen kifejtjük a közelség és összekapcsoltság tulajdonságait. Ezen tulajdonságok megértéséhez egy szomszédsági gráf alapú nézőpontot kell felvennünk, és a kapcsolatok számát valamint ezen kapcsolatok erősségét kell tekintenünk egy klaszteren belül és a klaszterek között.

RC( C i , C j )= S ¯ EC ( C i , C j ) m i m i + m j S ¯ EC ( C i )+ m j m i + m j S ¯ EC ( C j ) , (9.17)

ahol m i és m j a C i és C j klaszterek mérete, S ¯ EC ( C i , C j ) a C i és C j klasztereket összekötő élek átlagos súlya (a k -legközelebbi szomszéd gráfban), S ¯ EC ( C i ) az élek átlagos súlya, ha kettévágjuk a C i klasztert, S ¯ EC ( C j ) pedig az élek átlagos súlya, ha kettévágjuk a C j klasztert. (Az EC az élvágást jelöli.) A 9.18. ábra szemlélteti a relatív közelség fogalmát. Az előzőekben tárgyaltak szerint míg az (a) és (b) klaszter abszolút értelemben közelebb van egymáshoz, mint a (c) és (d) klaszterek, ez nem igaz, ha a klaszterek természetét is figyelembe vesszük.

RI( C i , C j )= EC( C i , C j ) 1 2 (EC( C i )+EC( C j )) , (9.18)

ahol EC( C i , C j ) a C i és C j klasztereket összekötő élek összege (a k -legközelebbi szomszéd gráfban) , EC( C i ) az elvágó élek minimális összege, ha kettévágjuk a C i klasztert, EC( C j ) pedig az elvágó élek minimális összege, ha kettévágjuk a C j klasztert. A 9.19. ábra szemlélteti a relatív összekapcsoltság fogalmát. A két kör alakú klaszter, (c) és (d), több kapcsolattal rendelkezik, mint a téglalap alakú klaszterek, (a) és (b). A (c) és (d) egyesítése azonban olyan klasztert hoz létre, aminek az összefüggőségi szerkezete egészen más, mint a (c)-é és (d)-é. Ezzel ellentétben az (a) és (b) egyesítése olyan klasztert hoz létre, aminek az összefüggőségi szerkezete nagyon hasonló az (a)-éhoz és (b)-éhez.

Az RI és az RC sokféleképpen kombinálható, hogy az önhasonlóság egy általános mértékét adják. Az egyik ilyen, a Chameleon által használt megközelítés az RI( C i , C j )*RC ( C i , C j ) α értékét maximalizáló klaszterpár egyesítése, ahol α egy tipikusan 1-nél nagyobb, a felhasználó által megadott paraméter.

Chameleon algoritmus

A Chameleon három kulcslépésből áll: ritkítás, gráfparticionálás és hierarchikus klaszterezés. A 9.9. algoritmus és a 9.20. ábra írják le ezeket a lépéseket.

Ritkítás

A Chameleon első lépése egy k -legközelebbi szomszéd gráf létrehozása. Fogalmilag egy ilyen gráfot a szomszédsági gráfból származtathatunk, éleket pedig csak a pont és a k legközelebbi szomszédai között, azaz a hozzá legközelebb eső pontok között tartalmaz. Ahogy már említettük, a ritkított szomszédsági gráf alkalmazása a teljes szomszédsági gráf helyett jelentősen csökkenti a zaj és a kiugró értékek hatását, valamint javítja a számítási hatékonyságot.

Gráfparticionálás

Ha már megkaptuk a ritkított gráfot, egy hatékony többszintű gráfparticionáló algoritmust -- mint például a METIS (lásd az irodalmi megjegyzéseket) -- lehet használni az adatok felosztására. A Chameleon egy mindent tartalmazó gráffal (klaszterrel) kezd, majd kettévágja az aktuálisan legnagyobb részgráfot (klasztert), amíg nem marad már MIN_MÉRET -nél több pontot tartalmazó klaszter, ahol MIN_MÉRET egy a felhasználó által megadott paraméter. Ez a folyamat nagyszámú, jól összekötött csúcsokból (nagyon hasonló adatpontokból) álló nagyjából egyforma méretű csoportot eredményez. A cél annak biztosítása, hogy minden egyes partíció főleg egy igazi klaszterből származó objektumokat tartalmazzon.

Összevonó hierarchikus klaszterezés

A korábban tárgyaltak szerint a Chameleon az önhasonlóság alapján egyesíti a klasztereket. A Chameleon paraméterezhető úgy, hogy egyetlen lépésben több klaszterpárt egyesítsen, és hogy megálljon, mielőtt minden objektumot egyetlen klaszterben egyesítene.

Bonyolultság

Tegyük fel, hogy m adatpontunk van és p a partíciók száma. Összevonó hierarchikus klaszterezés végrehajtása a gráfparticionálás révén nyert p partíción O( p 2  log p) időigényű. (Lásd a 8.3.1. szakaszt.) A gráfparticionálásához szükséges idő O(mp+m log m) . A gráfritkítás időbonyolultsága azon múlik, hogy mennyi ideig tart a k -legközelebbi szomszéd gráf létrehozása. Kis dimenziószámú adatokra ez O(m log m) időt vesz igénybe, ha egy k d-fát vagy egy hasonló típusú adatszerkezet használunk. Sajnos az ilyen adatszerkezetek csak kis dimenziószámú adathalmazokra működnek jól, így sokdimenziós adathalmazokra a ritkítás időbonyolultsága O( m 2 ) lesz. Mivel csak a k -legközelebbi szomszédok listáját kell tárolni, a tárbonyolultság O(km) plusz az adatok tárolásához szükséges tárhely.

9.11. Példa.

A Chameleon-t arra a két adathalmazra alkalmaztuk, amelyeknek a klaszterezésével nehézségeik voltak az olyan klaszterező algoritmusoknak, mint a K -közép és a DBSCAN. Ennek a klaszterezésnek az eredményeit mutatja a 9.21. ábra. A klasztereket a pontok színezésével azonosítjuk. A 9.21. (a) ábrán a két klaszter szabálytalan alakú és elég közel van egymáshoz. Továbbá zaj is jelen van. A 9.21. (b) ábrán a két klasztert egy híd köti össze, és ismét jelen van zaj is. A Chameleon mégis klaszterként azonosítja, amit a legtöbb ember természetes klaszternek tekintene. A Chameleon különösen hatékonynak bizonyult térbeli adatok klaszterezésénél. Végül vegyük észre, hogy a Chameleon nem dobja el a zajos pontokat, mint más klaszterező sémák, hanem ehelyett a klaszterekhez rendeli hozzá őket.

Erősségek és korlátok

A Chameleon hatékonyan tud klaszterezni térbeli adatokat még zaj és kiugró értékek jelenlétében is, és ha a klaszterek különböző alakúak, méretűek és sűrűségűek. A Chameleon feltételezi, hogy a ritkítási és gráfparticionálási folyamat által előállított objektumcsoportok alklaszterek, azaz hogy egy partíció pontjainak többsége ugyanahhoz a valódi klaszterhez tartozik. Ha nem így van, akkor az összevonó hierarchikus klaszterezés csak a hibákat halmozza fel, mivel sosem fog tudni szétválasztani olyan objektumokat, amelyek tévedésből kerültek össze. (Lásd a 8.3.4. szakasz tárgyalását.) Ezért a Chameleon-nak problémái adódnak akkor, ha a particionálási folyamat nem állít elő alklasztereket, ami gyakran előfordul sokdimenziós adatok esetén.

A hasonlóság és sűrűség standard megközelítéseire támaszkodó klaszterező módszerek bizonyos esetekben nem a kívánt eredményeket állítják elő a klaszterezés során. Ez a szakasz ennek okait vizsgálja és bevezeti a hasonlóság egy indirekt megközelítését, amely a következő elven alapul:

Ha két pont sok ugyanazon ponthoz hasonló, akkor ők is hasonlóak egymáshoz, még ha a hasonlóság közvetlen mérése ezt nem is jelzi.

A tárgyalást először két olyan probléma kifejtése motiválja, amelyeket a hasonlóság SNN változata kezel: az alacsony hasonlóságot és a sűrűségkülönbségeket.

A hagyományos hasonlóság problémái sokdimenziós adatoknál

Sokdimenziós terekben nem szokatlan, hogy kicsi a hasonlóság. Tekintsünk például egy dokumentumhalmazt, például az újság különböző rovataiból (szórakozás, pénzügy, külügy, közlekedés, belügy és sport) származó újságcikkek egy gyűjteményét. A 2. fejezetben leírtaknak megfelelően ezeket a dokumentumokat egy sokdimenziós tér vektoraiként tekinthetjük, ahol egy vektor komponensei (attribútumai) azt rögzítik, hogy egy szótár egyes szavai hányszor fordulnak elő a dokumentumban. A koszinusz hasonlósági mértéket gyakran használják a dokumentumok közötti hasonlóság megállapítására. Ehhez a példához, amely a Los Angeles Times cikkeinek gyűjteményéből származik, a 9.3. táblázat adja meg az átlagos koszinusz hasonlóságot az egyes rovatokban és a teljes dokumentumhalmazban.

Az egyes dokumentumok hasonlósága a hozzájuk legjobban hasonló dokumentumhoz (az első legközelebbi szomszédhoz) ennél jobb, átlagosan 0,39 . Az ugyanabba az osztályba tartozó objektumok közötti kis hasonlóság következménye azonban, hogy a legközelebbi szomszédjuk gyakran nem ugyanabból az osztályból származik. Azon dokumentumok közül, amelyekből a 9.3. táblázat készült, megközelítőleg 20%-nak van másik osztályban a legközelebbi szomszédja. Általában, ha a közvetlen hasonlóság kicsi, akkor megbízhatatlan útmutatóvá válik az objektumok klaszterezésénél, különösen az összevonó hierarchikus klaszterezés esetében, ahol a legközelebbi pontok kerülnek össze és később már nem lehet őket elválasztani. Ennek ellenére általában mégis az a helyzet, hogy egy objektum legközelebbi szomszédainak nagy többsége ugyanabba az osztályba tartozik. Ezt a tényt egy olyan szomszédsági mérték definiálásához lehet használni, ami megfelelőbb a klaszterezésre.

A sűrűségkülönbségek problémái

Egy másik probléma a klaszterek közötti sűrűségkülönbséggel kapcsolatos. A 9.22 ábrán kétdimenziós pontok különböző sűrűségű klaszterpárja látható. A jobb oldali klaszter alacsonyabb sűrűsége abban mutatkozik meg, hogy nagyobb a pontok közötti átlagos távolság. Bár a kevésbé sűrű klaszter pontjai éppen olyan érvényes klasztert alkotnak, a tipikus klaszterező módszerek számára nehezebb az ilyen klaszterek megtalálása. A kohézió normális mértékei, mint az SSE, ugyancsak azt fogják mutatni, hogy ezek a klaszterek kevésbé összefüggőek. Hogy valós példával szemléltetessük ezt a jelenséget: egy galaxis csillagai nem kevésbé valódi klaszterei az égi objektumoknak, mint a bolygók egy naprendszerben, pedig egy naprendszer bolygói átlagosan sokkal közelebb vannak egymáshoz, mint egy galaxis csillagai.

Az SNN hasonlóság kiszámítása

Az alapötlet mindkét szituációban a pontok környezetének figyelembe vétele a hasonlósági mérték definiálásánál. Ez az ötlet számszerűsíthető a hasonlóság közös legközelebbi szomszédokon alapuló definíciójával, ahogy ezt a 9.10. algoritmus mutatja. Az SNN hasonlóság lényegében a közös szomszédok száma, feltéve hogy mindkét objektum szerepel a másik legközelebbi szomszédainak listáján. Megjegyezzük, hogy a használt viszonymérték bármilyen értelmes hasonlósági vagy különbözőségi mérték lehet.

Az SNN hasonlóság kiszámítását a.9.10. algoritmus írja le és grafikusan a 9.23. ábra szemlélteti. Mindkét fekete pontnak nyolc legközelebbi szomszédja van, egymást is beleértve. Ezek közül 4 közös (a szürke pontok). Így a két pont közös legközelebbi szomszéd hasonlósága 4.

Az objektumok közötti SNN hasonlóságok hasonlósági gráfja az úgynevezett SNN hasonlósági gráf. Mivel sok objektumpár SNN hasonlósága 0, ez egy nagyon ritka gráf.

SNN hasonlóság kontra direkt hasonlóság

Az SNN hasonlóság azért hasznos, mert megcélozza néhány olyan probléma kezelését, amelyek a direkt hasonlóságnál lépnek fel. Először is, mivel figyelembe veszi az objektum környezetét a közös legközelebbi szomszédok számának használatával, az SNN hasonlóság kezeli azt a helyzetet, amikor egy objektum viszonylag közel van egy másik objektumhoz, de mégis másik osztályba tartozik. Ilyen esetekben az objektumoknak tipikusan nincs sok közös közeli szomszédja és kicsi az SNN hasonlóságuk.

Az SNN hasonlóság kezeli azokat a problémákat is, amiket a változó sűrűségű klaszterek jelentenek. Egy alacsony sűrűségű tartományban az objektumok messzebb vannak egymástól, mint egy sűrűbb tartományban. Egy pontpár SNN hasonlósága viszont csak a közös legközelebbi szomszédok számától függ, nem pedig attól, hogy ezek a szomszédok milyen messze vannak az egyes objektumoktól. Az SNN hasonlóság így egy automatikus skálázást végez a pontok sűrűsége szerint.

A 9.10. algoritmus a Jarvis-Patrick (JP) klaszterező algoritmust fejti ki az előző szakasz fogalmaival. A JP klaszterező algoritmus két pont viszonyát az SNN hasonlósággal helyettesíti, amit a 9.10. algoritmus szerint számolunk. Ezután egy küszöbértéket használunk az SNN hasonlósági mátrix ritkításához. A gráfok nyelvén kifejezve, egy SNN hasonlósági gráfot hozunk létre és ritkítunk. A klaszterek egyszerűen az SNN gráf összefüggő komponensei.

A JP klaszterező algoritmus tárigénye csak O(km) , mivel nem szükséges az egész hasonlósági mátrixot tárolni, még kezdetben sem. A JP klaszterezés alap időbonyolultsága O( m 2 ) , mivel a k -legközelebbi szomszéd lista létrehozása szükségessé teheti O( m 2 ) közelség kiszámítását. Bizonyos típusú adatok esetén azonban, mint például kis dimenziószámú euklideszi adatoknál, speciális módszerek (például k d-fa) használhatók a k -legközelebbi szomszéd hatékonyabban, a teljes hasonlósági mátrix kiszámítása nélkül történő megkeresésére. Ez az időbonyolultságot O( m 2 ) -ről O(mlogm) -re tudja csökkenteni.

9.12. Példa.

(Egy kétdimenziós adathalmaz JP klaszterezése) A JP klaszterezést a 9.24. (a) ábrán látható ``hal'' adathalmazra alkalmaztuk, a megtalált klasztereket pedig a 9.24. (b) ábra mutatja. A legközelebbi szomszéd lista mérete 20 volt és két pontot ugyanabba a klaszterbe soroltunk, ha legalább 10 közös pontjuk volt. A különböző klasztereket különböző jelek és eltérő színezés mutatja. Az ``x'' jelű pontokat zajnak osztályozta a Jarvis-Patrick algoritmus. Ezek főleg a különböző sűrűségű klaszterek közötti átmeneti tartományban találhatóak.

Erősségek és korlátok

Mivel a JP klaszterezés az SNN hasonlóság fogalmán alapul, jó a zaj és a kiugró értékek kezelésében és kezelni tudja a különböző méretű, alakú és sűrűségű klasztereket. Az algoritmus jól működik sokdimenziós adatokra és különösen jó az erősen kapcsolódó objektumok szoros klasztereinek megtalálásában.

Ugyanakkor a JP klaszterezés egy klasztert az SNN hasonlósági gráf összefüggő komponenseként definiál. Így az, hogy vajon egy objektumhalmaz felbomlik-e két klaszterre vagy egyben marad, egyetlen kapcsolaton múlhat. Ezért a JP klaszterezés némileg törékeny, azaz szétbonthat valódi klasztereket, vagy egyesíthet olyan klasztereket, amelyeket külön kellene tartani.

Egy másik lehetséges korlát az, hogy nem minden objektumot klaszterez. Ezeket az objektumokat azonban hozzá lehet adni létező klaszterekhez, és vannak esetek, amikor nem követelmény a teljes klaszterezés. A JP klaszterezés alap időbonyolultsága O( m 2 ) , amely az egy objektumhalmaz legközelebbi szomszéd listájának kiszámításához szükséges idő az általános esetben. Bizonyos esetekben, például kis dimenziószámú adatokra, speciális eljárásokat lehet használni, hogy a legközelebbi szomszédok megkeresésének időbonyolultsága O(mlogm) -re csökkenjen. Végül, mint más klaszterező algoritmusoknál is, kihívást jelenthet a legjobb paraméterértékek megtalálása.

A szakasz bevezetőjében tárgyaltak szerint a hagyományos euklideszi sűrűség semmitmondóvá válik nagy dimenziószám esetén. Ez attól függetlenül igaz, hogy rács-alapú nézőpontot alkalmazunk-e, mint a CLIQUE, középpont-alapú nézőpontot, mint amit a DBSCAN használ, vagy egy magfüggvényes sűrűségbecslő megközelítést, mint amit a DENCLUE alkalmaz. Lehet a középpont-alapú sűrűség-definíciót egy olyan hasonlósági mértékkel együtt használni, ami jól működik magas dimenzióban -- mint például a koszinusz vagy a Jaccard --, de ahogy ezt a 9.4.5. szakaszban leírtuk, az ilyen mértékeknek még mindig vannak problémái. Mivel azonban az SNN hasonlósági mérték a pontok adattérbeli lokális elrendezését tükrözi, viszonylag érzéketlen a sűrűség ingadozásaira és a tér dimenziószámára, és így ígéretes jelölt a sűrűség új mértékére.

Ez a szakasz kifejti, hogyan definiáljuk az SNN sűrűség fogalmát az SNN hasonlóság felhasználásával és a DBSCAN a 8.4. szakaszban leírt megközelítését követve. Az érthetőség kedvéért megismételjük annak a szakasznak a definícióit olyan megfelelő módosításokkal, amelyeket az SNN hasonlóság használata indokol.

Belső pontok

Egy pont belső pont, ha egy adott környezetében található pontok száma (melyet az SNN hasonlóság és a megadott Eps paraméter határoz meg) meghalad egy bizonyos MinPts küszöbértéket, amelyet ugyancsak a felhasználó határozhat meg.

Határpontok

Egy pont határpont, ha nem belső pont, azaz nincs elég pont a szomszédságában ahhoz, hogy belső pont legyen, de beleesik egy belső pont szomszédságába.

Zajos pontok

Zajos pontok mindazok a pontok, amelyek nem belső vagy határpontok.

Az SNN sűrűség annak fokát méri, hogy egy pont mennyire van körülvéve hasonló pontokkal (a legközelebbi szomszédok szempontjából). Így a magas és alacsony sűrűségű tartományok pontjai tipikusan viszonylag magas SNN sűrűségűek lesznek, míg azok a tartományok, ahol alacsony sűrűségről nagy sűrűségre történő átmenet van (ezek a klaszterek közötti pontok), általában alacsony SNN sűrűségűek lesznek. Egy ilyen megközelítés alkalmasabb lehet olyan adathalmazokra, melyek sűrűsége széles tartományon változik, viszont az alacsony sűrűségű klaszterek is érdekesek.

9.13. Példa.

(Belső, határ és zajos pontok) Hogy konkrétabbá tegyük az SNN sűrűség előzőekben bemutatott tárgyalását, egy példát adunk arra, hogyan használható fel az SNN sűrűség belső pontok megkeresésére valamint a zaj és a kiugró értékek eltávolítására. A 9.25. (a) ábrán látható kétdimenziós adathalmazban 10 000 pont van. A 9.25. (b--d) ábrák az SNN sűrűségük alapján különböztetik meg ezeket a pontokat. A 9.25. (b) ábra a legnagyobb SNN sűrűségű pontokat mutatja, míg a 9.25. (c) ábra a közepes SNN sűrűségű pontokat, a 9.25. (d) ábra pedig a legkisebb SNN sűrűségű pontokat. Azt látjuk ezekből az ábrákból, hogy a nagy sűrűségű pontok (amelyek az SNN gráfban nagy összekapcsoltságúak) jönnek szóba reprezentatív vagy belső pontokként, mivel többnyire a klaszter mélyében találhatóak, míg az alacsony összekapcsoltságú pontok a jelöltek arra, hogy zajos pontok és kiugró értékek legyenek, mert többnyire a klasztereket övező területeken találhatóak.

Az előzőekben definiált SNN sűrűségfogalom kombinálható a DBSCAN algoritmussal egy új klaszterező algoritmus megalkotásához. Ez az algoritmus hasonló a JP klaszterező algoritmushoz annyiban, hogy az SNN hasonlósági gráfból indul ki. Ugyanakkor ahelyett, hogy egy küszöbértéket használna az SNN hasonlósági gráf ritkításához, majd klaszterként tekintené az összefüggő komponenseket, az SNN sűrűség-alapú klaszterező algoritmus egyszerűen a DBSCAN-t alkalmazza.

Az SNN sűrűség-alapú klaszterező algoritmus

Az SNN sűrűség-alapú klaszterező algoritmus lépéseit a 9.12. algoritmus mutatja.

Az algoritmus automatikusan határozza meg az adatokban található klaszterek számát. Megjegyezzük, hogy nem minden pont kerül klaszterezésre. A figyelmen kívül hagyott pontok magukban foglalják a zajt és a kiugró értékeket, ezen kívül az olyan pontokat, amelyek nem kapcsolódnak erősen egy pontcsoporthoz. Az SNN sűrűség-alapú klaszterezés olyan klasztereket talál, amelyekben a pontok erősen kapcsolódnak egymáshoz. Az alkalmazástól függően előfordulhat, hogy sok pontot figyelmen kívül akarunk hagyni. Az SNN sűrűség-alapú klaszterezés alkalmas például témák dokumentum-csoportokban történő megtalálására.

9.14. Példa

(Idősorok SNN sűrűség-alapú klaszterezése) Az ebben a szakaszban bemutatott SNN sűrűség-alapú klaszterező algoritmus rugalmasabb, mint a Jarvis-Patrick klaszterezés vagy a DBSCAN. A DBSCAN-től eltérően használható sokdimenziós adatokra és olyan esetekre is, ahol a klaszterek különböző sűrűségűek. A Jarvis-Patrick algoritmustól eltérően, ami egyszerűen egy küszöbértékhez viszonyít és az összefüggő komponenseket tekinti klasztereknek, az SNN sűrűség-alapú klaszterezés kevésbé törékeny megközelítést használ, ami az SNN sűrűség és a belső pontok fogalmán alapul.

Hogy bemutassuk az SNN sűrűség-alapú klaszterezés képességeit sokdimenziós adatokon, a Föld különböző pontjain mért légnyomás havi idősor adataira alkalmaztuk azt. Konkrétabban, az adathalmaz egy 2,5 ∘ -os hosszúsági-szélességi rács minden egyes pontjában mért havi átlagos, tengerszintre átszámított légnyomás adatainak 41 éves idősora. Az SNN sűrűség-alapú klaszterező algoritmus a 9.26. ábrán jelölt klasztereket (a szürke területeket) találta. Megjegyezzük, hogy ezek a klaszterek 492 hónap hosszúságú idősorok klaszterei, annak ellenére, hogy kétdimenziós tartományokként jelenítettük meg őket. A fehér területek olyan régiók, ahol a nyomás nem volt annyira egyenletes. A klaszterek a sarkok közelében meghosszabbodtak a gömbfelület téglalapként történő ábrázolásának torzítása miatt.

A tengerszintre átszámított légnyomás segítségével a földtudósok klímaindexeknek (climate indices) nevezett idősorokat definiáltak, amelyek hasznosak a Föld klímájával kapcsolatos jelenségek megragadására. A klímaindexek rendellenességei például kapcsolatban állnak a Föld különböző részein mért szokatlanul alacsony vagy magas csapadékmennyiségekkel vagy hőmérsékletekkel. Az SNN sűrűség-alapú klaszterezés által talált több klaszter is szoros kapcsolatban áll a földtudósok által ismert klímaindexekkel.

A 9.27. ábra mutatja azoknak az adatoknak az SNN sűrűségszerkezetét, amelyekből a klasztereket nyertük. A sűrűséget normalizáltuk, hogy 0 és 1 közé essen. Egy idősor sűrűsége szokatlan fogalomnak tűnhet, de annak fokát méri, hogy mennyiben közösek az idősornak és legközelebbi szomszédainak a legközelebbi szomszédai. Mivel minden idősorhoz kapcsolódik egy hely, ezeket a sűrűségeket meg tudjuk jeleníteni egy kétdimenziós ábrán. Az időbeni autokorreláció miatt ezek a sűrűségek értelmes mintázatokat rajzolnak ki, például szemmel azonosíthatóak 9.27. ábra klaszterei.

Erősségek és korlátok

Az SNN sűrűség-alapú klaszterezés erősségei és korlátai hasonlóak a JP klaszterezés erősségeihez és korlátaihoz. Ugyanakkor a belső pontok és az SNN sűrűség alkalmazása jelentős erőt és rugalmasságot ad ennek a megközelítésnek.