Klaszterezés-alapú eljárások

A klaszteranalízis szorosan összetartozó objektumok csoportjait keresi, míg az rendellenesség észlelés olyan objektumokat keres, amelyek nem kapcsolódnak szorosan más objektumokhoz. Ezek után nem lehet meglepő, hogy a klaszterezés kiugró érték észlelésére is használható. Ebben a szakaszban több ilyen módszert tárgyalunk.

A klaszterezés kiugró értékek észlelésére való felhasználásának egyik módja a többi klasztertől távoli kis klaszterek elhagyása. Ez a módszer használható bármely klaszterezési eljárással, de szükséges hozzá a minimális klaszterméret, valamint egy kis klaszter és a többi klaszter közötti távolság küszöbértéke. Gyakran egyszerűsítik az eljárást úgy, hogy az összes, a minimális méretnél kisebb klasztert elhagyják. Ez a séma nagyon érzékeny a kiválasztott klaszterek számára. Ugyancsak nehéz ennek a sémának a segítségével kiugró érték pontszámot rendelni az objektumokhoz. Megjegyezzük, hogy objektumok csoportjainak kiugró értékként tekintésével a kiugró érték fogalmát egyedi objektumokról objektumok csoportjaira terjesztjük ki, de ez a lényegen nem változtat semmit.

Egy szisztematikusabb módszer az, amely először klaszterezi az objektumokat, majd megállapítja, hogy egy objektum milyen mértékben tartozik bármelyik klaszterhez. Prototípus-alapú klaszterezésnél az objektumnak a klasztere középpontjától vett távolsága használható annak mérésére, hogy milyen mértékben tartozik az objektum a klaszterhez. Általánosabban, a célfüggvényen alapuló klaszterezési eljárásokhoz a célfüggvényt használhatjuk annak mérésére, hogy mennyire tartozik egy objektum bármely klaszterhez. Nevezetesen, ha egy objektum eltávolítása lényegesen javítja a célfüggvény értékét, akkor kiugró értékként osztályozzuk az objektumot. Hogy ezt megvilágítsuk, a K -közép módszernél egy, a klasztere középpontjától távoli objektum kihagyása jelentősen javíthatja a klaszter négyzetes hibaösszegét (SSE -- sum of squared errors). Összefoglalva, a klaszterezés adatok egy modelljét hozza létre, és a rendellenességek eltorzítják ezt a modellt. Ezt a gondolatot fogalmazza meg def:cluster_based_outlier. definíció.

10.8. Definíció

(Klaszterezés-alapú kiugró érték) Egy objektum klaszter-alapú kiugró érték, ha nem tartozik szorosan egy klaszterhez sem.

Amikor célfüggvényt használó klaszterezéssel használjuk, ez a definíció speciális esete a modell-alapú rendellenesség definíciójának. Bár a 10.8. definíció természetesebb prototípus-alapú vagy célfüggvényt használó sémák számára, magában foglalhatja a kiugró értékek észlelésére szolgáló sűrűség- és összefüggőség-alapú klaszterezési módszereket is. Nevezetesen, a sűrűség-alapú klaszterezésnél egy objektum nem tartozik szorosan egy klaszterbe sem, ha a sűrűsége túl kicsi, míg az összefüggőség-alapú klaszterezésnél egy objektum nem tartozik szorosan egy klaszterbe sem, ha nem erősen összefüggő.

A következőkben azokat a kérdéseket tekintjük át, amelyekkel minden klaszterezés-alapú kiugró érték észlelő algoritmusnak foglalkoznia kell. Tárgyalásunk a prototípus-alapú klaszterezési eljárásokra koncentrál, mint például a K -közép módszer.

Az objektumok klaszterhez tartozási mértékének megállapítása

Prototípus-alapú klasztereknél több lehetőség is van az objektumok klaszterhez tartozási mértékének megállapítására. Az egyik módszer az, hogy megmérjük az objektum távolságát a klaszter prototípusától, és ezt tekintjük az objektum kiugró érték pontszámának. Ha azonban a klaszterek eltérő sűrűségűek, akkor olyan kiugró érték pontszámot alkothatunk, amely az objektum relatív távolságát méri a klaszter prototípusától, a többi klaszterbeli objektum távolságához viszonyítva. Egy másik lehetőség a Mahalanobis távolság használata, feltéve, hogy a klasztereket pontosan lehet modellezni Gauss-eloszlásokkal.

Azoknál a klaszterező eljárásoknál, amelyek célfüggvénnyel rendelkeznek, egy objektumhoz hozzá lehet rendelni azt a kiugró érték pontszámot, ami a célfüggvény javulásának felel meg, ha kihagyjuk az adott objektumot. Nagy számításigényű lehet azonban annak megállapítása a célfüggvény alapján, hogy mennyire kiugró érték egy pont. Ezen okból gyakran előnyösebbek az előző bekezdés távolság-alapú módszerei.

10.3. Példa

(Klaszterezés-alapú példa) Ez a példa a 10.7. ábrán látható ponthalmazon alapul. A prototípus-alapú klaszterezés a K -közép algoritmust használja. Egy pont kiugró érték pontszáma kétféleképpen számolható: (1) a pont a hozzá legközelebbi centroidtól vett távolsága alapján, és (2) a pont a hozzá legközelebbi centroidtól vett relatív távolsága alapján, ahol a relatív távolság a pontnak a centroidtól vett távolsága és a klaszter pontjainak a centroidtól vett távolsága mediánjának hányadosa. Az utóbbi módszert használják a tömör és ritka klaszterek közötti nagy sűrűségkülönbség kiegyenlítésére.

Az eredményül kapott kiugró érték pontszámokat a 10.9. és 10.10. ábrák mutatják. A korábbiak szerint a színezés jelzi a kiugró érték pontszámot, amelyet ebben az esetben a távolsággal vagy a relatív távolsággal mérünk. Minden esetben két klasztert használunk. A nyers távolságon alapuló megközelítésnek gondjai vannak a különböző klasztersűrűségekkel, például D -t nem tekinti kiugró értéknek. A relatív távolság alapú megközelítésnél is kiugró értékként jelennek meg azok a pontok ( A , C és D ), amelyeket korábban a LOF módszerrel kiugró értékként azonosítottunk.

10.8. ábra - Relatív sűrűség (LOF) alapú kiugró érték pontszámok a 10.7. ábra kétdimenziós pontjaira

Relatív sűrűség (LOF) alapú kiugró érték pontszámok a 10.7. ábra kétdimenziós pontjaira

10.9. ábra - Pontok távolsága a legközelebbi centroidtól

Pontok távolsága a legközelebbi centroidtól

10.10. ábra - Pontok relatív távolsága a legközelebbi centroidtól

Pontok relatív távolsága a legközelebbi centroidtól

A kiugró értékek hatása a kezdeti klaszterezésre

Ha klaszterezéssel észlelünk kiugró értékeket, kérdéses, hogy vajon az eredmények érvényesek-e, hiszen a kiugró értékek befolyásolják a klaszterezést. A probléma kezeléséhez a következő megközelítés használható: klaszterezzük az objektumokat, távolítsuk el a kiugró értékeket, majd klaszterezzük újra az objektumokat. Bár nincs biztosíték arra, hogy ez a módszer optimális eredményt ad, könnyen használható. Egy kifinomultabb megközelítés egy speciális csoport létrehozása azokból az objektumokból, amelyek nem illeszkednek jól egy klaszterbe sem. Ez a csoport potenciális kiugró értékeket képvisel. A klaszterezési folyamat előrehaladásával változnak a klaszterek. A szorosan már egyetlen klaszterhez sem tartozó objektumokat hozzávesszük a potenciális kiugró értékek halmazához, míg azokra az objektumokra, amelyek éppen ebben a halmazban vannak, megvizsgáljuk, hogy nem tartoznak-e most szorosan valamely klaszterhez, és eltávolíthatók-e a potenciális kiugró értékek halmazából. A klaszterezés végén a halmazban maradó objektumokat kiugró értékként osztályozzuk. Itt sem biztosított optimális megoldás, sőt, az sem, hogy ez a módszer jobban működik, mint az az egyszerű, amit az előzőekben mutattunk be. Például egy zajos pontokból álló klaszter hasonlíthat egy kiugró értékek nélküli valódi klaszterhez. Ez a probléma különösen súlyos akkor, ha a kigró érték pontszámot a relatív távolság alapján számoljuk.

A használandó klaszterek száma

A klaszterezési módszerek, például a K -közép módszer, nem határozzák meg automatikusan a klaszterek számát. Ez probléma, amikor a klaszterezést kiugró értékek észlelésére használjuk, mivel az, hogy egy objektumot kiugrónak tekintünk-e vagy sem, függhet a klaszterek számától. Például 10 objektum viszonylag közel lehet egymáshoz, de egy nagyobb klaszter részének tekinthetők, ha csak néhány nagy klasztert azonosítunk. Ebben az esetben mind a 10 pont kiugró értéknek tekinthető, még akkor is, ha klasztert alkottak volna akkor, ha elég nagy klaszterszámot határoztunk volna meg.

Néhány további kérdés mintájára erre a problémára sincs egyszerű válasz. Egy stratégia az elemzés megismétlése különböző számú klaszterrel. Egy másik megközelítés nagyszámú kis klaszter keresése. Itt az ötlet az, hogy (1) a kisebb klaszterek általában koherensebbek, (2) ha egy objektum még sok kis klaszter esetén is kiugró érték, akkor valószínűleg valódi kiugró érték. Ennek az a hátulütője, hogy a kiugró értékek csoportjai kis klasztereket alkothatnak, így nem lehet őket észlelni.

Erősségek és gyengeségek

Némely klaszterező eljárás, mint például a K -közép módszer, lineáris vagy közel lineáris idő- és tárbonyolultságú, így az ezeken alapuló kiugró érték észlelő algoritmusok nagyon hatékonyak lehetnek. A klaszter definíciója gyakran kiegészíti a kiugró érték definícióját, így általában lehetséges egyszerre megtalálni a klasztereket és a kiugró értékeket is. Hátrányként az hozható fel, hogy az előállított kiugró értékek halmaza és pontszámaik erősen függhetnek a használt klaszterek számától, valamint a kiugró értékek jelenlététől. Például a prototípus-alapú algoritmusok által előállított klasztereket eltorzíthatja a kiugró értékek jelenléte. Egy klaszterező algoritmus által előállított kiugró értékek minőségét nagyban befolyásolja az algoritmus által előállított klaszterek minősége. Ahogy ezt a 8. és a 9. fejezetekben tárgyaltuk, minden egyes klaszterező algoritmus csak bizonyos típusú adatokhoz alkalmas, ezért a klaszterező algoritmust körültekintően kell megválasztani.