Sűrűség-alapú kiugró érték észlelés

Sűrűség-alapú kiugró érték észlelés
Vissza	10. fejezet - Rendellenességek észlelése	Előre

Sűrűség-alapú szempontból a kiugró értékek olyan objektumok, amelyek kis sűrűségű tartományokban vannak.

10.5. Definíció

(Sűrűség-alapú kiugró érték) Egy objektum kiugró érték pontszáma az objektum körüli sűrűség inverze.

A sűrűség-alapú kiugró érték észlelés szorosan kapcsolódik a szomszédság-alapú kiugró érték észleléshez, mivel a sűrűséget általában szomszédsággal adjuk meg. Az egyik gyakori módszer a sűrűséget a k -legközelebbi szomszédtól vett átlagos távolság reciprokaként definiálni. Ha ez a távolság kicsi, akkor a sűrűség nagy, és fordítva. Ezt ragadja meg a 10.6. definíció.

10.6. Definíció

(Inverz távolság)

sűrűség(x,k) = ( ∑ y∈N(x,k) távolság(x,y) |N(x,k)| ) −1 , (10.6)

ahol N(x,k) az x k -legközelebbi szomszédját tartalmazó halmaz, |N(x,k)| ennek a halmaznak az elemszáma, y pedig egy legközelebbi szomszéd.

A sűrűség egy másik definíciója az, amelyet a DBSCAN klaszterező algoritmus használ. (Lásd a 8.4. szakaszt.)

10.7. Definíció

(Adott sugáron belüli pontok száma) Egy objektum körüli sűrűség egyenlő az objektum d sugarú környezetén belüli objektumok számával.

A d paramétert körültekintően kell megválasztani. Ha d túl kicsi, akkor sok normális pont kis sűrűségű lehet, és így nagy kiugró érték pontszámú. Ha d értékét nagynak választjuk, akkor sok kiugró érték sűrűsége (és kiugró érték pontszáma) hasonló lehet a normális pontokéhoz.

Bármely sűrűségdefiníciót használjuk is a kiugró érték észleléshez, a módszerek tulajdonságai és korlátai hasonlóak lesznek 10.3. szakaszban tárgyalt szomszédság-alapú kiugró érték sémákéhoz. Többek között nem tudják helyesen azonosítani a kiugró értékeket akkor, ha az adatok különböző sűrűségű részeket tartalmaznak. (Lásd a 10.7. ábrát.) Ahhoz, hogy helyesen azonosítsuk a kiugró értékeket ilyen adathalmazokban, olyan sűrűségfogalomra van szükségünk, amely az objektum szomszédságához relatív. Például a 10.7. ábrán a D pont a 10.6. és a 10.7. definíciók szerint nagyobb abszolút sűrűségű, mint az A pont, de a legközelebbi szomszédjaihoz képest kisebb sűrűségű.

Sok lehetőség van egy objektum relatív sűrűségének definiálására. Az egyik lehetőséget, amit az SNN sűrűség-alapú klaszterező eljárás használ, a 9.4.8. szakaszban tárgyaljuk. Egy további lehetőség a relatív sűrűséget az x pont sűrűségének és az y legközelebbi szomszédjai átlagos sűrűségének hányadosaként számítani, a következőképpen:

átlagos relatív sűrűség(x,k)= sűrűség(x,k) ∑ y∈N(x,k) sűrűség(y,k)/|N(x,k)| . (10.7)

Relatív sűrűség alapú kiugró érték észlelés

Ebben a szakaszban egy olyan módszert mutatunk be, amely a relatív sűrűség fogalmán alapul. A 10.2. algoritmus írja le ezt a módszert, amely a lokális kiugró faktor (LOF -- Local Outlier Factor) eljárás egyszerűsített változata (lásd az irodalmi megjegyzéseket). Az algoritmust az alábbiakban részletesebben is megvizsgáljuk, de lényegét tekintve a következőképpen működik. Minden egyes objektum kiugró érték pontszámát kiszámítjuk adott számú ( k ) szomszédra, először a legközelebbi szomszédaik alapján az objektumok sűrűség(x,k) sűrűségét meghatározva. Ezután kiszámoljuk az egyes pontok szomszédainak átlagos sűrűségét, és ezt használjuk egy pont átlagos relatív sűrűségének kiszámításához a 10.7. egyenletben feltüntetett módon. Ez a mennyiség azt jelzi, hogy vajon x a szomszédság sűrűbb vagy ritkább részén helyezkedik-e el, mint a szomszédai, és ezt tekintjük x kiugró érték pontszámának.

10.2 algoritmus. Relatív sűrűség alapú kiugró érték pontszám algoritmus

1: k a legközelebbi szomszédok száma

2: for minden x objektumra do

3: Határozzuk meg x k -legközelebbi szomszédait, amelyeket N(x,k) jelöl

4: Határozzuk meg x k -legközelebbi szomszédait, amelyeket N(x,k) jelöl Határozzuk meg sűrűség(x,k) értékét, x sűrűségét, a legközelebbi szomszédai, azaz az N(x,k) -beli objektumok alapján

5: end for

6: for minden x objektumra do

7: Legyen kiugróértékpontszám(x,k)=átlagosrelatívsűrűség(x,k) a (10.7) egyenlet alapján

8: end for

10.2. Péda.

(Relatív sűrűség alapú kiugró érték észlelés) A relatív sűrűség alapú kiugró érték észlelő módszer teljesítményét a 10.7. ábrán látható mintaadatokon szemléltetjük. Példánkban k=10 . Ezen pontok kiugró érték pontszámait mutatja a 10.8. ábra. Minden egyes pont színezését a pontszáma határozza meg, azaz a nagy pontszámú pontok sötétebbek. Ezekkel az értékekkel címkéztük meg az A , C és D pontokat, amelyek a legnagyobb kiugró érték pontszámúak. Rendre ezek a pontok felelnek meg a legszélsőségesebb kiugró értéknek, a tömör ponthalmazhoz képest a legszélsőségesebb pontnak, és a ritka halmaz legszélsőségesebb pontjának.

Erősségek és gyengeségek

A relatív sűrűség alapú kiugró érték észlelés számszerű mértékét adja annak, hogy egy objektum mennyire kiugró érték. Jól működik akkor is, ha az adatokban különböző sűrűségű tartományok vannak. A távolság-alapú megközelítésekhez hasonlóan ezek a megközelítések természetszerűleg O( m 2 ) időbonyolultságúak (ahol m az objektumok száma), bár ez speciális adatszerkezetek segítségével O(mlogm) -re csökkenthető alacsony dimenziójú adatokra. A paraméterválasztás is nehéz lehet, bár a standard LOF algoritmus foglalkozik ezzel olyan módon, hogy számos különböző k értéket megvizsgál és a legnagyobb kiugró érték pontszámokat veszi. Ezen értékek felső és alsó korlátját azonban továbbra is meg kell adni.

Vissza	Fel	Előre
Szomszédság-alapú kiugró érték észlelés	Főoldal	Klaszterezés-alapú eljárások