Szomszédság-alapú kiugró érték észlelés

Bár sok változata létezik a szomszédság-alapú kiugró érték észlelésnek, az alapötlet magától értetődő. Egy objektum rendellenesség, ha távol van a legtöbb ponttól. Ez a megközelítés általánosabb és könnyebben alkalmazható a statisztikai megközelítéseknél, hiszen könnyebb egy értelmes szomszédsági mértéket az adatokra kiszámolni, mint meghatározni azok statisztikai eloszlását.

A k -legközelebbi szomszédjától vett távolság használata az egyik legegyszerűbb mód annak mérésére, hogy vajon egy objektum távol van-e a legtöbb ponttól. Ezt ragadja meg 10.3. definíció. A kiugró érték pontszám legkisebb értéke 0, míg a legnagyobb értéke a távolságfüggvény legnagyobb lehetséges értéke -- ez általában végtelen.

10.4. Definíció

(Távolság a k -legközelebbi szomszédtól) Egy objektum kiugró érték pontszáma (outlier score) a k -legközelebbi szomszédjától vett távolsága.

A 10.4. ábra kétdimenziós pontok egy halmazát mutatja. Minden egyes pont színezése a kiugró érték pontszámát jelzi k = 5 választással. Vegyük észre, hogy a C kiugró pont helyesen kapott magas kiugró érték pontszámot.

A kiugró érték pontszám erősen érzékeny lehet k értékére. Ha k túl kicsi, például 1, akkor néhány egymáshoz közeli kiugró érték alacsony kiugró érték pontszámot okozhat. Például a 10.5. ábra kétdimenziós pontok egy olyan halmazát mutatja, ahol egy további pont is közel van C -hez. A színezés a kiugró érték pontszámot jelzi k=1 -re. Vegyük észre, hogy C és szomszédja is kis kiugró érték pontszámú. Ha k túl nagy, akkor elképzelhető, hogy egy k -nál kisebb elemszámú klaszter minden objektuma kiugró értékké válik. A 10.6. ábra például egy olyan kétdimenziós ponthalmazt mutat, amely egy 5 elemű természetes klasztert tartalmaz egy nagyobb, 30 elemű klaszter mellett. A kis klaszter minden pontjának nagyon nagy a kiugró érték pontszáma k=5 -re. Hogy a sémát robusztusabbá tegyük k választására, úgy módosíthatjuk a 10.4. definíciót, hogy az első k -legközelebbi szomszédtól vett távolságok átlagát használja.

10.4. ábra - Kiugró érték pontszám az ötödik legközelebbi szomszédtól vett távolság alapján

Kiugró érték pontszám az ötödik legközelebbi szomszédtól vett távolság alapján

10.5. ábra - Kiugró érték pontszám az első legközelebbi szomszédtól vett távolság alapján. A közeli kiugró értékek kis kiugró érték pontszámúak.

Kiugró érték pontszám az első legközelebbi szomszédtól vett távolság alapján. A közeli kiugró értékek kis kiugró érték pontszámúak.

10.6. ábra - Kiugró érték pontszám az ötödik legközelebbi szomszédtól vett távolság alapján. Egy kis klaszter kiugróvá válik.

Kiugró érték pontszám az ötödik legközelebbi szomszédtól vett távolság alapján. Egy kis klaszter kiugróvá válik.

10.7. ábra - Kiugró érték pontszám az ötödik legközelebbi szomszédtól vett távolság alapján. Különböző sűrűségű klaszterek.

Kiugró érték pontszám az ötödik legközelebbi szomszédtól vett távolság alapján. Különböző sűrűségű klaszterek.

Erősségek és gyengeségek

A fentiekben bemutatott távolság-alapú séma és más, hasonló sémák egyszerűek. A szomszédság-alapú megközelítésekhez azonban tipikusan O( m 2 ) időre van szükség. Nagy adathalmazokra ez túl költséges lehet, bár specializált algoritmusok segítségével alacsony dimenziójú esetben javítható a teljesítményük. A megközelítés érzékeny a paraméterek megválasztására is. Nem tud kezelni továbbá nagyon eltérő sűrűségű tartományokból álló adatokat, mivel globális küszöbértékeket alkalmaz, amelyek nem tudják figyelembe venni az ilyen sűrűségváltozásokat. Ennek szemléltetéséhez tekintsük a 10.7. ábra kétdimenziós ponthalmazát. Ez az ábra egy meglehetősen laza pontklaszterből, egy másik sűrű pontklaszterből, és az ettől a két klasztertől elég távoli C és D pontból áll. A kiugró érték pontszámok 10.4. definíció szerinti hozzárendelése a pontokhoz k=5 esetén helyesen azonosítja a C pontot kiugró értékként, de kis kiugró érték pontszámot mutat a D pontra. A D pont kiugró érték pontszáma valójában jóval kisebb, mint a ritka klaszterhez tartozó számos ponté.