A rács egy hatékony mód adatok elrendezéséhez, legalábbis kis dimenziószám esetén. Az ötlet az, hogy minden egyes attribútum lehetséges értékeit szomszédos intervallumokra osztjuk fel, rácscellák egy halmazát létrehozva. (Ebben a tárgyalásban és a szakasz további részében feltételezzük, hogy az attribútumaink sorrendi vagy intervallum típusúak, vagy pedig folytonos értékűek.) Minden egyes objektum beleesik egy rácscellába, amelyhez tartozó attribútum intervallumok magukban foglalják az objektum értékeit. Az adatokon egyszer végigfutva hozzá tudjuk rendelni az objektumokat a rácscellákhoz, ezzel egyidejűleg minden egyes celláról gyűjthető információ, mint például a pontok száma a cellában.

Sok lehetőség van rács használatával történő klaszterezésre, de a legtöbb ilyen megközelítés legalább részben a sűrűségen alapul, ezért ebben a szakaszban a rács-alapú klaszterezés fogalma alatt rács használatával történő sűrűség-alapú klaszterezést értünk. A 9.4. algoritmus egy alap megközelítést ír le a rács alapú klaszterezéshez. Ennek a megközelítésnek a különböző aspektusait tárjuk fel a következőkben.

Rácscellák definiálása

Ez a folyamat kulcslépése és ugyanakkor a legkevésbé jól definiált lépése, mert sokféle módon lehet az egyes attribútumok lehetséges értékeit szomszédos intervallumokba sorolni. Folytonos attribútumok esetén az egyik gyakori megközelítés az értékek egyforma hosszúságú intervallumokra történő osztása. Ha ezt a megközelítést az összes attribútumra alkalmazzuk, akkor az eredményül kapott rácscellák mind azonos térfogatúak lesznek és a cellák sűrűsége kényelmesen definiálható a cellába eső pontok számaként.

Kifinomultabb megközelítéseket is lehet azonban használni. Különösen folytonos attribútumok esetén használható bármely olyan eljárás, amelyeket tipikusan az attribútumok diszkretizálására alkalmazunk. (Lásd a 2.3.6. szakaszt.) A már említett azonos hosszúságú megközelítésen kívül ez magában foglalja (1) az attribútum értékeinek olyan intervallumokra történő felosztását, amelyek egyenlő számú pontot tartalmaznak, azaz az egyenlő gyakoriságú diszkretizálást, vagy (2) klaszterezés használatát. Egy másik, a MAFIA altér klaszterező algoritmus által használt megközelítés először nagyszámú, egyenlő hosszúságú intervallumra bontja fel az attribútum értékeinek halmazát, majd összevonja a hasonló sűrűségű intervallumokat.

A rács definíciója a választott megközelítéstől függetlenül nagy hatással van a klaszterezés eredményére. Ennek jellegzetes aspektusait később tekintjük át.

A rácscellák sűrűsége

Egy rácscella (vagy egy általánosabb alakú tartomány) sűrűségét természetes a pontok számának és a tartomány térfogatának hányadosaként definiálni. Más szavakkal, a sűrűség a pontok száma osztva a tér nagyságával, függetlenül a tér dimenziószámától. Jellegzetes kis dimenziószámú példák a sűrűségre: a közlekedési táblák száma kilométerenként (egydimenziós), a sasok száma az élőhelyükön négyzetkilométerenként (kétdimenziós), és a gázmolekulák száma köbcentiméterenként (háromdimenziós). Ahogy már említettük azonban, tipikus megközelítés olyan rácscellákat használni, amelyek azonos térfogatúak, így a pontok cellánkénti száma közvetlen mérőszáma a cellák sűrűségének.

9.8. Példa.

(Rács-alapú sűrűség) A 9.10. ábra két kétdimenziós ponthalmazt mutat, amelyeket egy 7×7 -es rács segítségével 49 cellára osztottunk fel. Az első halmaz 200 pontot tartalmaz a (2,3) középpontú, 2 sugarú körlapon vett egyenletes eloszlásból, míg a második halmaz 100 pontból áll, amelyet a (6,3) középpontú 1 sugarú körlapon vett egyenletes eloszlásból generáltunk. Az egyes cellákba eső pontok számát a 9.2. táblázat mutatja. Mivel a celláknak azonos a térfogata (területe), ezeket a számokat tekinthetjük a cellák sűrűségének.

Klaszterek kialakítása sűrű rácscellákból

A klaszterek kialakítása szomszédos sűrű rácscellákból viszonylag egyértelmű. (A 9.10. ábrán például egyértelmű, hogy két klaszter van.) Marad azért néhány kérdés. Definiálnunk kell, hogy mit értünk szomszédos cellák alatt. Egy kétdimenziós rácscellának például 4 szomszéd cellája van-e, vagy 8? A szomszédos cellák megkeresésére is szükséges egy hatékony módszer, különösen akkor, ha csak a foglalt cellákat tároljuk.

A 9.4. algoritmus által definiált klaszterező megközelítésnek van néhány korlátja, amelyek kezelését meg lehet célozni az algoritmus kissé kifinomultabbá tételével. Valószínűleg vannak például részben üres cellák egy klaszter határán. Ezek a cellák gyakran nem sűrűek. Ha ez így van, akkor eldobjuk őket és a klaszter egyes részei elvesznek. A 9.10. ábra és a 9.2. táblázat azt mutatják, hogy a nagyobb klaszter négy része elveszne, ha a sűrűségi küszöbérték 9 lenne. A klaszterezési folyamatot lehet úgy módosítani, hogy elkerülje az ilyen cellák eldobását, bár ez további feldolgozást igényelne.

Az is lehetséges, hogy az alapvető rács-alapú klaszterezést úgy javítjuk meg, hogy mást is használunk, nemcsak sűrűség-információt. Sok esetben vannak az adatoknak térbeli és nem térbeli attribútumai is. Más szavakkal, az attribútumok némelyike az objektumok helyét írja le időben vagy térben, míg más attribútumok az objektumok más aspektusait határozzák meg. Tipikus példák a házak, amelyeknek van helyük és számos más jellemzőjük, mint például áruk vagy négyzetméterben kifejezett alapterületük. A térbeli (vagy időbeni) autokorrelációk miatt egy adott cellában levő objektumok más attribútumai gyakran hasonló értékűek. Ilyen esetekben lehetséges a cellák szűrése egy vagy több nem térbeli attribútum statisztikai tulajdonságai alapján (például átlagos házár), ezután pedig klaszterek kialakítása a megmaradó pontok sűrűsége alapján.

Erősségek és korlátok

A pozitív oldalon áll, hogy a rács-alapú klaszterezés nagyon hatékony és eredményes tud lenni. Ha adott minden egyes attribútum egy particionálása, egy átfutás az adatokon meg tudja határozni minden egyes objektum celláját és a rácscellák gyakoriságát. Bár a lehetséges rácscellák száma nagy lehet, rácscellákat csak a nem üres cellákra kell létrehozni. Így a rács definiálása, az egyes objektumok egy cellához történő hozzárendelése és minden egyes cella sűrűségének kiszámítása csak O(m) idő- és tárbonyolultságú, ahol m a pontok száma. Ha a szomszédos, foglalt cellák hatékonyan érhetőek el például keresőfa alkalmazásával, akkor a teljes klaszterezési folyamat nagyon hatékony lesz, például O(mlogm) időbonyolultságú. Ezen okból a sűrűségi klaszterezés rács-alapú megközelítése az alapja több klaszterező algoritmusnak, mint például a STING, a GRIDCLUS, a WaveCluster, a Bang-Klaszterezés, a CLIQUE és a MAFIA.

A negatív oldalon áll, hogy a rács-alapú klaszterezés, mint a legtöbb sűrűség-alapú klaszterező séma, erősen függ a sűrűség τ küszöbértékétől. Ha τ túl nagy, elvesztünk klasztereket. Ha τ túl kicsi, két különálló klaszter egyesülhet. Továbbá, ha a klaszterek és a zaj különböző sűrűségűek, akkor elképzelhető, hogy nem lehet megadni egyetlen olyan τ értéket, ami működik az adattér minden részén.

Sok további kérdés is felmerül a rács-alapú megközelítéssel kapcsolatban. A 9.10. ábrán például a négyzetrács cellái nem adják pontosan vissza a kör alakú határterületek sűrűségét. Megpróbálhatjuk ezt a problémát a rács finomításával enyhíteni, de az egy klaszterhez tartozó pontok valószínűleg nagyobb ingadozást fognak mutatni a rácscellák között, mert a pontok nem egyenletes eloszlásúak a klaszterben. Valóban, néhány rácscella, köztük a klaszter belsejében levők is, akár üres is lehet. Egy másik kérdés, hogy a cellák elhelyezésétől és méretétől függően egy pontcsoport megjelenhet csak egy cellában, vagy felosztódhat több különböző cella között. Ugyanaz a pontcsoport egy klaszter része lehet az első esetben, de eldobásra kerülhet a második esetben. Végül, ahogy a dimenziószám nő, a lehetséges rácscellák száma gyorsan -- exponenciálisan -- nő. Bár nem szükséges az üres rácscellákat explicit módon tekinteni, könnyen előfordulhat, hogy a legtöbb rácscella csupán egyetlen objektumot tartalmaz. Más szavakkal, a rács-alapú klaszterezés hajlamos gyengén működni sokdimenziós adatokra.

Az eddig vizsgált klaszterező módszerek úgy találtak klasztereket, hogy minden attribútumot felhasználtak. De ha csak a jellemzők egy részhalmazát -- azaz az adatok altereit -- tekintjük, a megtalált klaszterek teljesen különbözőek lehetnek, ha az egyik altérről áttérünk a másikra. Két ok lehet, amelyek miatt az altér klaszterei érdekesek lehetnek. Először is az adatok klasztereződhetnek az attribútumok egy kis halmaza szerint, de véletlenszerű eloszlásúak lehetnek a fennmaradó attribútumok szerint. Másodszor, vannak esetek, amikor különböző klaszterek léteznek a dimenziók különböző halmazaiban. Tekintsünk egy adathalmazt, amely különböző árucikkek különböző időpontokban történő eladásait tartja nyilván. (Az időpontok a dimenziók, az árucikkek pedig az objektumok.) Néhány árucikk hasonló viselkedést mutathat (együtt klasztereződik) a hónapok bizonyos halmazaiban, például nyáron, de valószínűleg más klaszterek állnának elő más hónapokra (dimenzióra).

9.9. Példa.

(Altér klaszterek) A 9.11. (a) ábra egy ponthalmazt mutat a háromdimenziós térben. A teljes térben a pontok három klasztert alkotnak, amelyeket négyzetekkel, rombuszokkal és háromszögekkel ábrázoltunk. Van továbbá egy olyan ponthalmaz, melyet körökkel ábrázoltunk, és amely nem klaszter a háromdimenziós térben. A példa adathalmaz minden dimenzióját (attribútumát) rögzített számú ( η ) egyforma hosszú intervallumra osztottuk fel. η=20 számú intervallum van, mindegyik 0,1 hosszú. Ez az adatteret egyforma térfogatú kockákra bontja fel, és így minden cella sűrűsége az a részarány, amennyit a pontokból tartalmaz. A klaszterek sűrű cellák összefüggő csoportjai. Példaképpen, ha a sűrű cellákra vonatkozó küszöbérték ξ=0,06 , vagyis a pontok 6%-a, akkor három egydimenziós klasztert lehet beazonosítani a 9.12. ábrán, amelyen a 9.11. (a) ábra adatpontjai x attribútumának hisztogramja látható.

A 9.11. (b) ábra mutatja a pontokat az xy síkban ábrázolva. (A z attribútumot figyelmen kívül hagytuk.) Ez az ábra is tartalmaz olyan hisztogramokat az x és y tengelyeken, amelyek a pontok eloszlását mutatják az x és y koordinátájuk szerint. (A magasabb oszlop azt mutatja, hogy a hozzá tartozó intervallum viszonylag több pontot tartalmaz, és fordítva.) Ha az y tengelyt tekintjük, három klasztert látunk. Egy a körrel jelölt pontokból áll, amelyek nem alkotnak klasztert a teljes térben, egy másik a négyzettel jelölt pontokból, egy harmadik pedig a háromszög és rombusz alakú pontokból. Ugyancsak három klaszter van az x dimenzióban, ezek megfelelnek a teljes tér három klaszterének (rombuszok, háromszögek és négyzetek). Ezek a pontok az xy síkban is diszjunkt klasztereket alkotnak. A 9.11. (c) ábra mutatja a pontokat az xz síkban ábrázolva. Két klaszter van, ha csak a z attribútumot tekintjük. Az egyik klaszter megfelel a körökkel ábrázolt pontoknak, míg a másik a rombusz, háromszög és négyzet alakú pontokat tartalmazza. Ezek a pontok diszjunkt klasztereket alkotnak az xz síkon is. A 9.11. (d) ábrán három klaszter van, ha mind az y , mind a z koordinátákat tekintjük. Ezen klaszterek egyike tartalmazza a köröket, egy másik pedig a négyzettel jelölt pontokat. A rombuszok és a háromszögek egy klasztert alkotnak az yz síkon.

Az ábrák számos fontos tényt szemléltetnek. Először is egy ponthalmaz -- a körök -- lehet, hogy nem alkot klasztert az egész adattérben, de klasztert alkothat egy altérben. Másodszor, a teljes adattérben (vagy akár egy altérben) létező klaszterek klaszterként jelennek meg az alacsonyabb dimenziós térben. Az első tény arra mutat rá, hogy szükséges lehet a dimenziók egyes részhalmazait vizsgálni ahhoz, hogy klasztereket találjunk, míg a második tény arra világít rá, hogy sok, az alterekben megtalált klaszter lehet, hogy csak ``árnyéka'' (vetülete) magasabb dimenziós klasztereknek. A cél az, hogy megtaláljuk a klasztereket, és azokat a dimenziókat, amelyekben léteznek, de tipikusan nem érdekesek számunkra azok a klaszterek, amelyek magasabb dimenziós klaszterek vetületei.

CLIQUE

A CLIQUE (CLustering In QUEst) egy rács-alapú klaszterező algoritmus, ami módszeresen keresi meg az altérbeli klasztereket. Nem praktikus minden altérben megvizsgálni a klasztereket, mert az ilyen alterek száma exponenciális a dimenziószám függvényében. Ehelyett a CLIQUE a következő tulajdonságon alapul:

A sűrűség-alapú klaszterek monotonitási tulajdonsága Ha pontok egy halmaza sűrűség-alapú klasztert hoz létre k számú dimenzióra (attribútumra), akkor ugyanez a ponthalmaz egy sűrűség-alapú klaszter része ezen dimenziók minden lehetséges részhalmazára is.

Tekintsük szomszédos k -dimenziós cellák olyan halmazát, amely klasztert alkot, azaz szomszédos cellák olyan összességét, amelynek a sűrűsége adott ξ küszöbértéknél nagyobb. A megfelelő ( k−1 )-dimenziós cellahalmaz megkapható, ha elhagyjuk a k dimenzió (attribútum) egyikét. Ezek az alacsonyabb dimenziós cellák továbbra is szomszédosak, és minden egyes alacsony dimenziójú cella minden pontot tartalmaz a megfelelő magas dimenziójú cellából, de további pontokat is tartalmazhat. Így az alacsony dimenziójú cella sűrűsége nagyobb vagy egyenlő, mint a megfelelő magas dimenziójú celláé. Tehát az alacsony dimenziójú cellák is klasztert alkotnak, azaz a pontok klasztert alkotnak a redukált attribútumhalmaz mellett.

A 9.5. algoritmus egy egyszerűsített változatát adja a CLIQUE lépéseinek. Fogalmilag a CLIQUE algoritmus hasonló a gyakori elemhalmazok keresésére szolgáló Apriori algoritmushoz. (Lásd a 6. fejezetet.)

A CLIQUE erősségei és korlátai

A CLIQUE leghasznosabb jellemzője, hogy hatékony módszert ad klaszterek keresésére az alterekben. Mivel ez a megközelítés az asszociációs elemzésből jól ismert Apriori elven alapul, a tulajdonságai is jól ismertek. Egy másik hasznos tulajdonság a CLIQUE azon képessége, hogy néhány egyenlőtlenséggel írja le a klasztereket alkotó cellák listáját.

A CLIQUE sok korlátja azonos más rács-alapú sűrűségi sémák korábban már tárgyalt korlátaival. Más korlátok pedig hasonlóak az Apriori algoritmuséhoz. Nevezetesen, ahogy a gyakori elemhalmazoknak lehetnek közös elemei, a CLIQUE által megtalált klasztereknek is lehetnek közös objektumai. A klaszterek átfedésének megengedése nagyban megnövelheti a klaszterek számát és nehezíti az értelmezésüket. Egy másik kérdés, hogy az Apriori (és a CLIQUE) potenciálisan exponenciális időbonyolultságú. A CLIQUE-nek különösen nehézséget okoz, ha túl sok sűrű cella kerül előállításra kis k értékek mellett. A ξ sűrűségi küszöbérték növelése enyhítheti ezt a problémát. A CLIQUE egy további potenciális korlátját tárja fel a 20. feladat a 672. oldalon.

A DENCLUE (DENsity CLUstEring -- sűrűség klaszterezés) egy sűrűség-alapú klaszterező megközelítés, ami egy ponthalmaz teljes sűrűségét az egyes pontokhoz tartozó hatásfüggvények összegeként modellezi. A kapott teljes sűrűségfüggvénynek lokális csúcsai lesznek, azaz lokális sűrűségmaximumai, ezeket a lokális csúcsokat pedig természetes módon lehet klaszterek definiálására használni. Nevezetesen, egy hegymászó eljárás minden adatpontra megtalálja a hozzá tartozó legközelebbi csúcsot, és egy adott csúcshoz (amit lokális sűrűség-attraktornak nevezünk) tartozó összes adatpont alkot egy klasztert. Ha viszont a sűrűség egy lokális maximumban túl kicsi, akkor a hozzá tartozó klaszter pontjait zajnak tekintjük és figyelmen kívül hagyjuk. Ha egy lokális maximum összeköthető egy másik lokális maximummal egy adatpontokból álló úttal, és az út minden pontjában a minimális sűrűségi küszöbértéknél nagyobb a sűrűség, akkor az ezekhez a lokális maximumokhoz tartozó klasztereket összevonjuk. Ezért bármilyen alakú klasztereket meg tudunk találni.

9.10. Példa.

(DENCLUE sűrűség) Ezeket a fogalmakat a 9.13. ábrával szemléltetjük, amely egy egydimenziós adathalmazra mutat egy lehetséges sűrűségfüggvényt. Az A--E pontok ennek a sűrűségfüggvénynek a csúcsai és lokális sűrűség-attraktorokat ábrázolnak. A pontozott függőleges vonalak választják el a lokális sűrűség-attraktorok lokális vonzási tartományait. Az ezekhez a tartományokhoz tartozó pontok lesznek a középpontok által definiált klaszterek. A szaggatott vízszintes vonal mutatja a ξ sűrűségi küszöbértéket. Elhagyunk minden olyan pontot, amely olyan lokális sűrűség-attraktorhoz tartozik, amelynek a sűrűsége ξ -nél kisebb. Minden más klasztert megtartunk. Megjegyezzük, hogy egy klaszter olyan pontokat is tartalmazhat, amelyek sűrűsége ξ -nél kisebb, ha olyan lokális sűrűség-attraktorokhoz tartoznak, amelyek sűrűsége ξ -nél nagyobb. Végül összevonjuk azokat a klasztereket, amelyeket ξ -nél nagyobb sűrűségű pontokból álló út köt össze. Az A és B klaszterek különállóak maradnak, míg a D és E klasztereket összevonjuk.

A DENCLUE algoritmus magas szintű részleteit a 9.6. algoritmus foglalja össze. A következőkben részletesebben mutatjuk be a DENCLUE különböző aspektusait. Először rövid áttekintést adunk a magfüggvényes sűrűségbecslésről, majd a rács-alapú megközelítést mutatjuk be, amelyet a DENCLUE használ a sűrűség közelítésére.

Magfüggvényes sűrűségbecslés

A DENCLUE a statisztika és az alakfelismerés egy olyan jól kidolgozott területén alapul, amit magfüggvényes sűrűségbecslésnek neveznek. Ezen módszergyűjtemény célja (sok más statisztikai módszeré is), hogy egy függvénnyel írja le az adatok eloszlását. A magfüggvényes sűrűségbecslésnél az egyes pontok hozzájárulását a teljes sűrűségfüggvényhez a hatásfüggvény vagy magfüggvény segítségével fejezzük ki. A teljes sűrűségfüggvény egyszerűen az egyes pontokhoz tartozó hatásfüggvények összege.

A magfüggvény (vagy hatásfüggvény) tipikusan szimmetrikus (minden irányban azonos), és az értéke (hozzájárulása) csökken, ahogy a távolság nő a ponttól. Egy konkrét x pontra például gyakran használják magfüggvényként a Gauss függvényt: K(y)= e −távolság (x,y) 2 /2 σ 2 . A σ paraméter azt határozza meg, hogy milyen gyorsan cseng le a pont hatása (megfelel a szórásnak). A 9.14. (a) ábra mutatja, hogyan nézne ki a Gauss sűrűségfüggvény egy kétdimenziós pontra, míg a 9.14. (c) és a 9.14. (d) ábrák a teljes sűrűségfüggvényt mutatják, amit a Gauss hatásfüggvény alkalmazásával kaptunk a 9.14. (b) ábrán szereplő pontokra.

Implementációs kérdések

A magfüggvényes sűrűség kiszámítása meglehetősen költséges lehet, és a DENCLUE számos közelítést használ ahhoz, hogy hatékonyan implementálja az alapmegoldását. Először is csak az adatpontokra számol explicit módon sűrűséget. Ez azonban továbbra is O( m 2 ) időbonyolultságot eredményezne, mivel a sűrűség minden egyes pontban az összes pont által hozzájárult sűrűség függvénye. Az időbonyolultság csökkentésére a DENCLUE rács-alapú implementációt használ a környezetek hatékony definiálására, és így korlátozza azon pontok számát, amelyeket figyelembe kell venni egy pont sűrűségének definiálásánál. Először is egy előfeldolgozási lépés létrehozza rácscellák egy halmazát. Csak foglalt cellák kerülnek létrehozásra, ezen cellákhoz és a kapcsolódó információkhoz hatékonyan lehet hozzáférni keresőfa segítségével. Így amikor egy pont sűrűségét számoljuk és megkeressük a legközelebbi sűrűség-attraktorát, a DENCLUE csak a szomszédságba eső pontokat tekinti, azaz a pontokat ugyanebben a cellában és azokban a cellákban, amelyek össze vannak kötve a pont cellájával. Bár ez a megközelítés feláldozhat valamennyi pontosságot a sűrűségbecslésnél, a számítási bonyolultságot jelentősen csökkenti.

A DENCLUE erősségei és korlátai

A DENCLUE szilárd elméleti alapokra épül, mivel magfüggvényes sűrűségfüggvényeken és a magfüggvényes sűrűségbecslés fogalmán alapul, ami a statisztika egy kiforrott területe. Ezért a DENCLUE rugalmasabb és potenciálisan pontosabb eljárást ad a sűrűség kiszámítására, mint más rács-alapú klaszterező módszerek és a DBSCAN. (A DBSCAN speciális esete a DENCLUE-nak.) Egy magfüggvényes sűrűségfüggvényeken alapuló módszer természeténél fogva számításigényes, de a DENCLUE rács-alapú módszereket alkalmaz ezen kérdések kezelésére. Mindazonáltal a DENCLUE számításigényesebb lehet, mint más sűrűség-alapú klaszterező módszerek. A rács alkalmazása ugyancsak hátrányosan befolyásolhatja a sűrűségbecslést és a DENCLUE-t érzékennyé teszi a rács-alapú megközelítések tipikus problémáira, mint például a megfelelő rácsméret megválasztása. Általánosabban, a DENCLUE sok erőssége és korlátja megegyezik más sűrűség-alapú megközelítések erősségeivel és korlátaival. A DENCLUE például jól kezeli a zajt és a kiugró értékeket és képes megtalálni különböző alakú és méretű klasztereket, de problémái vannak a sokdimenziós adatokkal és az olyan adatokkal, amelyek jelentősen eltérő sűrűségű klasztereket tartalmaznak.