10. fejezet - Rendellenességek észlelése

Tartalom

Bevezető
Rendellenességek okai
Rendellenességek észlelésének módszerei
Osztálycímkék használata
Kérdések
Statisztikai megközelítések
Kiugró értékek észlelése egydimenziós normális eloszlásnál
Kiugró értékek a többdimenziós normális eloszlásnál
Keverék modell módszer rendellenesség észlelésre
Erősségek és gyengeségek
Szomszédság-alapú kiugró érték észlelés
Erősségek és gyengeségek
Sűrűség-alapú kiugró érték észlelés
Relatív sűrűség alapú kiugró érték észlelés
Erősségek és gyengeségek
Klaszterezés-alapú eljárások
Az objektumok klaszterhez tartozási mértékének megállapítása
A kiugró értékek hatása a kezdeti klaszterezésre
A használandó klaszterek száma
Erősségek és gyengeségek
Irodalmi megjegyzések
Feladatok

Az anomáliák, magyarul a rendellenességek észlelésénél olyan objektumok keresése a cél, amelyek a legtöbb más objektumtól különböznek. A rendellenes objektumokat gyakran kiugró értékeknek (outliers) nevezik, hiszen az adatok pontdiagramján távol esnek a többi ponttól. A rendellenesség észlelést gyakran eltérés észlelésnek (deviation detection) is nevezik, mert a rendellenes objektumok attribútumértékei jelentősen eltérnek a várt vagy tipikus attribútumértékektől, vagy kivétel bányászatnak (exception mining) is hívják, mert a rendellenességek bizonyos értelemben kivételesek. Ebben a fejezetben legtöbbször a rendellenesség (anomália) vagy kiugró érték elnevezést fogjuk használni.

Számos rendellenesség észlelő módszer ismert a különböző területekről, ideértve a statisztikát, gépi tanulást és adatbányászatot. Mindegyik azt az ötletet ragadja meg, hogy a rendellenes objektum szokatlan vagy valamilyen módon inkonzisztens más objektumokkal. Bár a szokatlan objektumok definíció szerint viszonylag ritkák, ez nem jelenti azt, hogy abszolút számban ne fordulnának elő gyakran. Például egy ezer esetből egyszer előforduló esemény milliószor is megjelenhet, ha milliárdnyi eseményt tekintünk.

A természetben, emberi társadalomban vagy az adatok körében a legtöbb esemény és objektum definíció szerint tipikus vagy hétköznapi. Mégis rendkívüli az érdeklődés a szokatlan vagy különleges objektumok lehetősége iránt. Ide tartoznak például különlegesen száraz vagy nedves évszakok, híres atléták, vagy egy olyan attribútumérték, amely sokkal kisebb vagy nagyobb az összes többinél. Az anomáliák, vagyis rendellenes események és objektumok azért érdekesek, mert gyakran különleges fontosságúak: az aszály a termést fenyegeti, győzelemhez vezethet, ha az atléta kiugró ügyességű, a kísérleti eredmények között talált rendellenességek vagy a kísérlettel kapcsolatos problémára, vagy vizsgálandó új jelenségre utalhatnak.

A következő példák olyan alkalmazásokat illusztrálnak, ahol a rendellenességek különösen érdekesek:

A rendellenesség észlelés iránti új érdeklődéshez olyan alkalmazások vezettek el, ahol az anomáliák vannak a középpontban, a rendellenességek észlelését (és eltávolítását) történetileg mégis a tipikus adatobjektumok elemzését javító módszernek tekintették. Viszonylag kis számú kiugró érték például el tudja téríteni az adatok átlagát és a szórását, vagy meg tudja változtatni egy klaszterező algoritmus által előállított klasztereket. A rendellenesség észlelés (és eltávolítás) ezért gyakran az adatok előfeldolgozásának része.

Ebben a fejezetben a rendellenességek észlelésére koncentrálunk. Rövid bevezető után részletesen bemutatjuk a legfontosabb módszereket, amelyeket a konkrét eljárásokra adott példákkal szemléltetünk.

Bevezető

Mielőtt rátérnénk az egyedi rendellenesség észlelő algoritmusok megvitatására, előbb kiegészítő háttérinformációkkal szolgálunk, miszerint (1) megvizsgáljuk a rendellenességek okait, (2) különböző rendellenesség észlelő módszereket mutatunk be, (3) különbséget teszünk a módszerek között aszerint, hogy használnak-e osztálycímke információt, és (4) megfogalmazzuk a rendellenesség észlelő módszerek közös kérdéseit.

Rendellenességek okai

A rendellenességek tipikus okai közé tartoznak többek között a következők: a különböző osztályokból származó adatok, a természetes szóródás, mérési és adatgyűjtési hibák.

Különböző osztályokból származó adatok

Egy objektum eltérhet a többi objektumtól -- azaz rendellenes lehet -- azért, mert más osztályból származik. Például valaki, aki hitelkártya csalást követ el, a kártyahasználók más osztályába tartozik, mint a jogosult felhasználók. A fejezet elején bemutatott példák többsége, úgymint a csalás, behatolás, betegségek kitörése és abnormális teszteredmények, olyan rendellenességek példái, amelyek objektumok külön osztályát képviselik. Az ilyen anomáliák gyakran érdekesek, és a rendellenesség észlelés középpontjában állnak az adatbányászat területén.

Az a gondolat, hogy a rendellenes objektumok más forrásból (osztályból) származnak, mint a legtöbb adatobjektum, megfogalmazódik a kiugró értéknek a statisztikus Douglas Hawkinstól származó, gyakran idézett definíciójában.

10.1. Definíció

(Hawkins kiugró érték definíciója) A kiugró érték olyan megfigyelés, ami annyira különbözik a többi megfigyeléstől, hogy felmerül annak a gyanúja, hogy más mechanizmus hozta létre.

Természetes ingadozás

Sok adathalmazt lehet modellezni olyan statisztikai eloszlásokkal, mint például a normális (Gauss) eloszlás, ahol az eloszlás középpontjától távolodva gyorsan csökken az adatobjektumok valószínűsége. Más szavakkal, a legtöbb objektum egy középponthoz (átlagos objektumhoz) közel helyezkedik el, és kicsi annak valószínűsége, hogy egy objektum jelentősen különbözzön ettől az átlagos objektumtól. Egy különlegesen magas ember például nem rendellenes abban az értelemben, hogy más osztályhoz tartozna, csupán abban az értelemben, hogy szélsőséges értékű az objektumok egy jellemzője (a magasság) szempontjából. Gyakran érdekesek azok a rendellenességek, amelyek szélsőséges vagy valószínűtlen ingadozást képviselnek.

Mérési és adatgyűjtési hibák

Az adatgyűjtési vagy mérési folyamatban bekövetkező hibák a rendellenességek egy másik forrását jelentik. Egy mérés hibásan kerülhet rögzítésre például emberi tévedés, a mérőeszköz hibája, vagy zaj jelenléte miatt. A cél az ilyen rendellenességek kiküszöbölése, mivel ezek nem nyújtanak érdekes információkat, csak rontják az adatok és az azokon alapuló elemzés minőségét. Valóban, az ilyen típusú rendellenességek kiszűrése az adatelőfeldolgozás, különösen az adattisztítás központi kérdése.

Összefoglalás

Egy rendellenesség lehet a fenti okok következménye, vagy más, nem tárgyalt okoké is. Valóban, az adatok anomáliái különböző forrásokból eredhetnek, és az egyes rendellenességek oka gyakran ismeretlen. A gyakorlatban a rendellenesség észlelő eljárások olyan objektumok megtalálására koncentrálnak, amelyek jelentősen eltérnek a legtöbb objektumtól, és a módszereket nem befolyásolják a rendellenességek forrásai. Így a rendellenesség mögött rejlő ok csak a tervezett alkalmazás szempontjából lényeges.

Rendellenességek észlelésének módszerei

Itt néhány rendellenesség észlelő módszer magas szintű leírását és a hozzájuk tartozó rendellenesség definíciókat adjuk meg. Valamennyi átfedés van ezen módszerek között, kapcsolatukat vizsgálja tovább sz 1. feladat s 705. oldalon.

Modell-alapú módszerek

Sok rendellenesség észlelő módszer először az adatokat modellezi. Rendellenességek azok az objektumok, amelyek nem illeszkednek jól a modellhez. Az adatok eloszlásának egy modelljét például megalkothathatjuk úgy, hogy az adatok alapján megbecsüljük egy valószínűségi eloszlás paramétereit. Egy objektum nem illeszkedik a modellhez, azaz rendellenes, ha az eloszlás mellett nem nagyon valószínű. Ha a modell klaszterek halmaza, akkor rendellenesség egy olyan objektum, amely egy klaszterhez sem tartozik szorosan. Ha regressziós modellt használunk, a rendellenesség olyan objektum, ami viszonylag távol van az előrejelzett értékétől.

Mivel a rendellenes és normális objektumok tekinthetőek úgy, mint amelyek két külön osztályt definiálnak, osztályozási eljárások alkalmazhatóak ennek a két osztálynak a modellezésére. Ilyen módszerek természetesen csak akkor használhatóak, ha az osztálycímkék legalább az objektumok egy részénél rendelkezésre állnak. Ugyancsak figyelembe kell venni az osztályozási eljárás és a kiértékelési mérték kiválasztásánál azt a tényt, hogy a rendellenességek viszonylag ritkák. (Lásd 5.7. szakaszt.)

Néhány esetben nehéz modellt építeni: például azért, mert az adatok statisztikai eloszlása ismeretlen, vagy mert nem állnak rendelkezésre tanulóadatok. Ezekben az esetekben azok a módszerek használhatóak, amelyekhez nincs szükség modellre, ilyeneket mutatunk be az alábbiakban.

Szomszédság-alapú módszerek

Gyakran lehetséges az objektumok között egy szomszédsági mértéket definiálni, és számos rendellenesség észlelő módszer alapul szomszédságon. A rendellenes objektumok azok, amelyek távol vannak a legtöbb objektumtól. Ezen terület sok módszere távolságokon alapul, amelyeket távolság-alapú kiugró érték észlelő módszereknek nevezünk. Amikor az adatokat két- vagy háromdimenziós pontdiagramon tudjuk ábrázolni, a távolság-alapú kiugró értékek szemmel is láthatóak, olyan pontokat keresve, amelyek a legtöbb ponttól elkülönülnek.

Sűrűség-alapú módszerek

Az objektumok sűrűségének becslését viszonylag könnyű kiszámolni, különösen akkor, ha rendelkezésre áll az objektumok egy szomszédsági mértéke. Az alacsony sűrűségű tartományokban lévő objektumok viszonylag távol vannak a szomszédaiktól és rendellenességeknek tekinthetőek. Egy ennél kifinomultabb megközelítés azt a tényt alkalmazza, hogy az adatok egymástól jelentősen eltérő sűrűségű tartományokból állhatnak, és csak akkor tekint egy pontot kiugró értéknek, ha a lokális sűrűsége jelentősen kisebb, mint a legtöbb szomszédjáé.

Osztálycímkék használata

Három alapvető megközelítése van a rendellenesség észlelésnek: felügyelet nélküli, felügyelt és félig felügyelt. A fő különbség az, hogy milyen mértékben állnak rendelkezésre osztálycímkék (rendellenes és normális) legalább az adatok egy részéhez.

Felügyelt rendellenesség észlelés

A felügyelt rendellenesség észlelő módszerekhez szükség van egy tanulóhalmazra, amely rendellenes és normális objektumokat is tartalmaz. (Megjegyzendő, hogy lehet egynél több normális vagy rendellenes osztály is.) Ahogy az előzőekben említettük, különösen fontosak azok az osztályozási módszerek, amelyek kezelni tudják az úgynevezett ritka osztály problémát, mert a rendellenességek viszonylag ritkák a normális objektumokhoz képest. (Lásd 5.7. szakaszt.)

Felügyel nélküli rendellenesség észlelés

Sok gyakorlati esetben nem állnak rendelkezésre az osztálycímkék. Ezekben az esetekben a cél az, hogy egy olyan pontszámot (vagy címkét) rendeljünk minden egyes példányhoz, amely az adott megfigyelés rendellenességének fokát jelzi. Érdemes megjegyezni, hogy sok egymáshoz hasonló rendellenesség jelenléte azt eredményezheti, hogy mindegyiket normálisnak címkézzük, vagy hogy alacsony kiugró érték pontszámot kapnak. Ezért a felügyelet nélküli rendellenesség észlelés csak akkor lehet sikeres, ha a rendellenességek különböznek egymástól és a normális objektumoktól is.

Félig felügyelt rendellenesség észlelés

Néha a tanulóadatbázis címkézett normális adatokat tartalmaz, de nincs információ a rendellenes objektumokról. A félig felügyelt esetben a cél egy rendellenességi címke vagy pontszám megtalálása adott objektumokhoz, a címkézett normális objektumok által biztosított információk alapján. Megjegyzendő, hogy ebben az esetben a pontozandó objektumok halmazában lévő nagy számú hasonló kiugró érték nem befolyásolja a kiugró értékek értékelését. Viszont sok gyakorlati helyzetben nehéz lehet megtalálni a reprezentatív normális objektumok egy kis halmazát.

A fejezetben bemutatása kerülő minden egyes rendellenesség észlelő sémát lehet felügyelt és felügyelet nélküli módon használni. A felügyelt sémák lényegében ugyanazok, mint 5.7. szakaszban bemutatott, ritka esetre vonatkozó osztályozási sémák.

Kérdések

Számos fontos kérdést kell megválaszolni, amikor rendellenességekkel foglalkozunk.

A rendellenesség definiálásánál használt attribútumok száma

Az a kérdés, hogy egyetlen attribútum alapján tekinthető-e egy objektum rendellenességnek, annak vizsgálatát jelenti, hogy vajon az adott objektum értéke ennél az attribútumnál rendellenesség-e. Viszont, mivel egy objektumnak sok attribútuma lehet, előfordulhat, hogy néhány attribútuma rendellenes értékű, más attribútumai azonban közönséges értékűek. Az is előfordulhat továbbá, hogy egy objektum rendellenes annak ellenére, hogy önmagában egyik attribútuma sem rendellenes. Megszokott például, hogy vannak 60 cm magas emberek (gyerekek) és 130 kg súlyú emberek is, de igen ritka az olyan 60 cm magas ember, aki 130 kg súlyú. A rendellenesség általános definíciójának meg kell adnia, hogyan lehet egyszerre több attribútumérték alapján meghatározni, hogy vajon egy objektum rendellenesség-e vagy sem. Ez különösen fontos kérdés, amikor az adatok sokdimenziósak.

Globális kontra lokális perspektíva

Egy objektum szokatlannak tűnhet, ha az összes objektumhoz viszonyítjuk, de nem az, ha csak a lokális környezetéhez hasonlítjuk. Például egy 198 cm magas ember szokatlanul magas az általános populációhoz képest, de nem az a profi kosárlabdázók között.

Pont rendellenességének foka

Számos módszernél bináris módon történik annak eldöntése, hogy vajon egy objektum rendellenesség-e: egy objektum vagy rendellenesség, vagy nem. Ez gyakran nem tükrözi azt az alapigazságot, hogy néhány objektum szélsőségesebb rendellenesség, mint mások. Ezért kívánatos az adott objektum rendellenességének fokát értékelni. Ezt az értékelést rendellenességi vagy kiugró érték pontszámnak (outlier score) nevezzük.

Rendellenességek azonosítása: egyenként kontra egyszerre többet

Bizonyos módszerek a rendellenességeket egyesével távolítják el, azaz a leginkább rendellenes eset kerül azonosításra és eltávolításra, majd a folyamat ismétlődik. Más módszereknél rendellenességek egy csoportját együtt azonosítjuk. Azok a módszerek, amelyek egyesével próbálják kiszűrni a rendellenességeket, gyakran szembesülnek az elfedéssel (masking), ahol a különböző rendellenességek jelenléte elfedi az összeset. Másrészt, azok a módszerek, amelyek rendellenességek egy csoportját egyszerre azonosítják, tapasztalhatják az elárasztás (swamping) jelenségét, ahol normális objektumokat osztályoznak kiugróként. Modell-alapú megközelítéseknél ezek a hatások azért fordulhatnak elő, mert a rendellenességek eltorzítják az adatmodellt.

Kiértékelés

Ha a rendellenességek és a normális adatok azonosítására osztálycímkék állnak rendelkezésre, akkor a rendellenesség észlelő séma hatékonysága kiértékelhető az osztályozási teljesítmény 5.7. szakaszban tárgyalt mérőszámaival. Mivel azonban a rendellenes osztály általában sokkal kisebb, mint a normális osztály, a pontosságnál megfelelőbbek az olyan mérőszámok, mint például a precizitás, felidézés és hamis pozitív arány. Ha címkék nem állnak rendelkezésre, akkor nehéz az értékelés. Modell-alapú megközelítéseknél a kiugró értékek észlelésének hatékonysága megítélhető a modell rendellenességek elhagyása utáni javulásával.

Hatékonyság

Lényeges különbségek vannak a különböző rendellenesség észlelő sémák számításigényei között. Az osztályozáson alapuló sémák az osztályozási modell megalkotásához jelentős mennyiségű erőforrást igényelhetnek, de általában olcsón alkalmazhatóak. Hasonlóan, a statisztikai megközelítések statisztikai modellt alkotnak, amely után konstans időben osztályoznak egy objektumot. A szomszédság-alapú megközelítések természetszerűleg O( m 2 ) bonyolultságúak, ahol m az objektumok száma, mert a szükséges információkat általában csak a szomszédsági mátrix kiszámítása révén tudják megszerezni. Ezt az időbonyolulságot bizonyos esetekben csökkenteni lehet, például alacsony dimenziójú adatok esetén, speciális adatszerkezet és algoritmusok használata révén. Más megközelítések időbonyolultságát vizsgálja 1f. feladat exer:anomaly_time_complexity. oldalon.

Ütemterv

A következő négy szakasz a rendellenesség észlelő algoritmusok több fő kategóriáját mutatja be: statisztikai, szomszédság-alapú, sűrűség-alapú és klaszter-alapú módszereket. Minden kategórián belül egy vagy több konkrét módszert tekintünk. Ezekben a szakaszokban a tipikus gyakorlatot követjük, és a kiugró érték elnevezést használjuk a rendellenesség helyett.