Helyi kibocsátási szint

A lokális kiugró szint egy algoritmus az anomália-észlelésben , amelyet Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng és Jörg Sander javasoltak 2000-ben, hogy kiugró adatpontokat találjanak egy adott pont helyi eltérésének mérésével a szomszédaitól. [1] .

A lokális kiugró szint olyan fogalmakon osztozik, mint a DBSCAN és az OPTICS , mint például az "alaptávolság" és az "elérhető távolság" [2] fogalma , amelyeket a helyi sűrűség becslésére használnak [3] .

Alapötlet

A lokális kiugró szint a lokális sűrűség fogalmán alapul, ahol a lokalitást a legközelebbi szomszédok adják meg, akiknek távolsága alapján becsüljük meg a sűrűséget. Ha egy objektum lokális sűrűségét a szomszédai lokális sűrűségével hasonlítjuk össze, hasonló sűrűségű területek és pontok azonosíthatók, amelyek sűrűsége lényegesen kisebb, mint a szomszédaié. Ezek a pontok kiugrónak számítanak . $k$

A helyi sűrűséget a szomszédos pontoktól „elérhető” tipikus távolság alapján becsüljük meg. Az algoritmusban használt "elérhető távolság" definíciója egy további intézkedés a klasztereken belüli robusztusabb eredmények eléréséhez.

Formai leírás

Legyen az objektum és a k -edik legközelebbi szomszéd távolsága. Ne feledje, hogy a k legközelebbi szomszéd halmaza tartalmazza az összes objektumot, amely attól a távolságtól van, és egy "csomópont" esetén több mint k objektumot tartalmazhat. A k legközelebbi szomszéd halmazát jelöljük . ${\mbox{k-distance}}(A)$ $A$ $N_{k}(A)$

Ez a távolság az elérhető távolság meghatározására szolgál ( eng. reachability-distance ):

${\mbox{elérhetőség-távolság}}_{k}(A,B)=\max\{{\mbox{k-távolság}}(B),d(A,B)\}$

Más szóval, egy objektumtól elérhető távolság a két objektum valódi távolsága. Azokat a jellemzőket, amelyek a pont k legközelebbi szomszédjához tartoznak (a pont "magpontjai" , lásd DBSCAN ), a stabilabb eredmények érdekében azonos távolságra lévőnek tekintjük. Vegye figyelembe, hogy ez a távolság nem távolság matematikai értelemben, mivel nem szimmetrikus. (Gyakori hiba, hogy mindig alkalmazzuk, így ez egy kicsit más módszert ad, az úgynevezett egyszerűsített lokális kiugró módszert [4] ) $A$ $B$ $B$ $B$ ${\mbox{k-distance))$

Egy objektum helyi elérhetőségi sűrűsége a következőképpen van meghatározva $A$

${\mbox{lrd}}_{k}(A):=1/\left({\frac {\sum _{B\in N_{k}(A)}{\mbox{elérhetőségi távolság }}_{k}(A,B)}{|N_{k}(A)|}}\jobbra)$ ,

ami egy objektum szomszédaitól való átlagos elérhetőségi távolságának reciproka. Megjegyzendő, hogy ez nem a szomszédok átlagos elérhetőségi távolsága a ponttól (amelynek definíció szerint kellene lennie ), hanem az a távolság, amelyen A "elérhető" a szomszédaitól. Ismétlődő pontok esetén ez az érték végtelenné válhat. $A$ $A$ ${\mbox{k-distance}}(A)$

A helyi elérhetőségi sűrűségeket ezután összehasonlítják a szomszédok helyi elérhetőségi sűrűségével

${\mbox{LOF}}_{k}(A):={\frac {\sum _{B\in N_{k}(A)}{\frac {{\mbox{lrd}}( B)}{{\mbox{lrd}}(A)}}}{|N_{k}(A)|}}={\frac {\sum _{B\in N_{k}(A)}{ \mbox{lrd}}(B)}{|N_{k}(A)|}}/{\mbox{lrd}}(A)$

amely a szomszédok átlagos lokális elérhetőségi sűrűsége osztva magának az objektumnak a lokális elérhetőségi sűrűségével. A hozzávetőlegesen egyenlő érték azt jelenti, hogy az objektum összehasonlítható a szomszédaival (és akkor nem kiugró érték). A -nál kisebb érték sűrű területet jelent (amely lehet a belső terület), míg a -nál lényegesen nagyobb értékek kiugró értékeket jeleznek. $egy$ $egy$ $egy$

Előnyök

A megközelítés lokális elhelyezkedéséből adódóan a lokális kiugró szintű algoritmus képes olyan kiugró értékeket észlelni az adatkészletben, amelyek az adatkészlet más területein esetleg nem lehetnek kiugróak. Például a sűrű klasztertől "kis" távolságra lévő pont kiugró érték, míg egy ritka klaszteren belüli pont hasonló távolságra lehet a szomszédaitól.

Míg az algoritmus geometriai intuíciója csak kisdimenziós vektorterekre vonatkozik, az algoritmus bármilyen környezetben alkalmazható, ahol különbségi függvény definiálható. Kísérletileg kimutatták, hogy az algoritmus számos helyzetben jól működik, gyakran felülmúlva a riválisokat, például a behatolásérzékelő rendszerekben [5] és a feldolgozott osztályozási adatokon [6] .

A lokális kiugró szintű módszerek családja könnyen általánosítható, majd különféle más problémákra is alkalmazható, mint például a földrajzi adatokban, a videofolyamokban vagy a hitelhálózatokban található kiugró értékek észlelése [4] .

Hátrányok és bővítmények

Az így kapott értékek nehezen értelmezhetők. Az 1-es vagy akár egynél kisebb érték azt jelenti, hogy a pont tisztán belső, de nincs egyértelmű szabály, hogy egy pont kiugró érték. Egy adathalmazban az 1,1-es érték már kiugró értéket jelenthet, egy másik adathalmazban és paraméterezésben (erős lokális fluktuáció mellett) a 2-es érték még belsőt jelenthet. Ezek a különbségek ugyanazon adathalmazon belül is előfordulhatnak a metódus lokalitása miatt. Vannak metódusbővítmények, amelyek megpróbálják javítani az algoritmust:

A jellemzők zsákolása a jellemzők észleléséhez [7] helyi outlier szintű algoritmust hajt végre több vetületnél, és egyesíti az eredményeket a jobb észlelési minőség érdekében nagy dimenziókban. Ez az első ensemble-alapú megközelítés az izoláció detektálására, a többi lehetőségről lásd Zimek, Campello és Sander [8] .
A Local Outlier Probability ( LOOP) [9] a lokális kiugró szint módszeréből származó módszer, de takarékos helyi statisztikákat használ, hogy a módszert kevésbé érzékenyítse a k paraméter megválasztására . Ezenkívül az eredményül kapott értékeket a rendszer az értékre skálázza . $[0:1]$
A kiugró pontszámok értelmezése és egységesítése [ 10] magában foglalja a kiugró értékek becslésének intervallumra történő normalizálását statisztikai skálázással a használhatóság növelése érdekében, és az algoritmus a lokális kiugró valószínűség gondolatának továbbfejlesztett változatának tekinthető. $[0:1]$
Az Outlier Rankings and Outlier Scores értékeléséről [ 11] eszközt kínál a módszerek hasonlóságának és különbségének mérésére a kiugró értékek észlelési módszereinek fejlett halmazának felépítéséhez a lokális kiugró szint algoritmusának és más algoritmusok változatainak felhasználásával, valamint a jellemzők zsákolási megközelítésének javításával. fentebb volt szó.
Revised Local Outlier Detection: A lokalitás általános nézete térbeli kiugró-észlelési, videó- és hálózati outlier-észlelési alkalmazásokkal [4] tárgyalja a különféle lokális kiugró-észlelési módszerek általános keretrendszerét (beleértve a helyi outlier-szintű algoritmust, annak egyszerűsített változatát és az LLP-t) és a megfontolást általános elvekbe fordítja. Ezeket az elveket alkalmazzák például a földrajzi adatokban, a videofolyamokban és a hozzárendelési hálózatban található kiugró értékek azonosítására.

Jegyzetek

↑ Breunig, Kriegel, Ng, Sander, 2000 , p. 93–104.
↑ A szakirodalomban az "elérhető távolság" helyett az "elérhető" elnevezés is megtalálható.
↑ Breunig, Kriegel, Ng, Sander, 1999 , p. 262.
↑ 1 2 3 Schubert, Zimek, Kriegel, 2012 .
↑ Lazarevic, Ozgur, Ertoz, Srivastava, Kumar, 2003 , p. 25–36.
↑ Campos, Zimek, Sander, Campello et al., 2016 .
↑ Lazarevic és Kumar 2005 , p. 157–166.
↑ Zimek, Campello, Sander, 2014 , p. tizenegy.
↑ Kriegel, Kröger, Schubert, Zimek, 2009 , p. 1649–1652
↑ Kriegel, Kröger, Schubert, Zimek, 2011 , p. 13–24.
↑ Schubert, Wojdanowski, Zimek, Kriegel, 2012 , p. 1047–1058.

Irodalom

Breunig MM, Kriegel H.-P., Ng RT, Sander JR LOF: Identifying Density-based Local Outliers // Proceedings of the 2000 ACM SIGMOD International Conference on Data Management . - 2000. - ( SIGMOD ). — ISBN 1-58113-217-4 . - doi : 10.1145/335191.335388 .
Breunig MM, Kriegel H.-P., Ng RT, Sander JR OPTICS-OF: Identifying Local Outliers // Principles of Data Mining and Knowledge Discovery . - 1999. - T. 1704. - (Számítástechnikai előadásjegyzetek). - ISBN 978-3-540-66490-1 . - doi : 10.1007/978-3-540-48247-5_28 .
Lazarevic A., Ozgur A., Ertoz L., Srivastava J., Kumar V. Az anomália-észlelési sémák összehasonlító vizsgálata a hálózati behatolás észlelésében // Proc. 3. SIAM Nemzetközi Adatbányászati Konferencia . — 2003. Archiválva : 2013. július 17. a Wayback Machine -nál
Guilherme Campos, Arthur Zimek, Jörg Sander, Ricardo JGB Campello, Barbora Micenková, Erich Schubert, Ira Assent, Michael E. Houle. A nem felügyelt kiugró értékek észlelésének értékeléséről: intézkedések, adatkészletek és empirikus vizsgálat // Adatbányászat és tudásfeltárás. - 2016. - ISSN 1384-5810 . - doi : 10.1007/s10618-015-0444-8 .
Lazarevic A., Kumar V. Feature bagging for outlier detection // Proc. 11. ACM SIGKDD nemzetközi konferencia a Knowledge Discovery in Data Mining témakörben. - 2005. - doi : 10.1145/1081870.1081891 .
Zimek A., Campello RJGB, Sander JR Ensembles for unsupervised outlier detection // ACM SIGKDD Explorations Newsletter. - 2014. - T. 15 . - doi : 10.1145/2594473.2594476 .
Kriegel H.-P., Kröger P., Schubert E., Zimek A. LooOP: Local Outlier Probabilities // Proceedings of the 18th ACM Conference on Information and Knowledge Management. - 2009. - ISBN 978-1-60558-512-3 . - doi : 10.1145/1645953.1646195 .
Kriegel H.-P., Kröger P., Schubert E., Zimek A. Interpreting and Unifying Outlier Scores // Proceedings of the 2011 SIAM International Conference on Data Mining. - 2011. - ISBN 978-0-89871-992-5 . - doi : 10.1137/1.9781611972818.2 .
Schubert E., Wojdanowski R., Zimek A., Kriegel HP On Evaluation of Outlier Rankings and Outlier Scores // Proceedings of the 2012 SIAM International Conference on Data Mining. - 2012. - ISBN 978-1-61197-232-0 . - doi : 10,1137/1,9781611972825,90 .
Schubert E., Zimek A., Kriegel H.-P. Helyi kiugró értékek észlelése újragondolva: A lokalitás általános nézete térbeli, videó- és hálózati kiugró értékek észlelésére szolgáló alkalmazásokkal // Data Mining and Knowledge Discovery. - 2012. - doi : 10.1007/s10618-012-0300-z .

Gépi tanulás és adatbányászat
Feladatok	Osztályozási probléma Tanulás tanár nélkül Tanár által segített tanulás Regresszió analízis AutoML Egyesületi szabályzat Funkció kivonás Tulajdonságok képzése Rangsorképzés Nyelvtani levezetés Online tanulás
Tanulás tanárral	k-legközelebbi szomszéd módszer Naiv Bayes osztályozó döntési fa Támogatja a vektoros gépet Lineáris regresszió Logisztikus regresszió perceptron Modellek együttesei Zsákolás fellendítése véletlenszerű erdő Releváns vektoros módszer
klaszteranalízis	k-közép módszer Fuzzy klaszterezési módszer Hierarchikus klaszterezés EM algoritmus NYÍR GYÓGYMÓD DBSCAN OPTIKA Átlageltolás
Dimenziócsökkentés	Faktoranalízis Főkomponens módszer CCA ICA LDA Nem negatív mátrix kiterjesztése t-SNE
Strukturális előrejelzés	Grafikon valószínűségi modell Bayesi hálózat Rejtett Markov-modell CRF
Anomália észlelése	k-legközelebbi szomszéd módszer Helyi kibocsátási szint
Grafikon valószínűségi modellek	Bayesi hálózat Markov hálózat Rejtett Markov-modell
Neurális hálózatok	Limitált Boltzmann gép önszerveződő térkép Aktiválási funkció Szigma alakú softmax Radiális bázisfüggvény Hátsó szaporítási módszer Mély tanulás Többrétegű perceptron Ismétlődő neurális hálózat hosszú távú rövid távú memória Ellenőrzött visszatérő blokk Konvolúciós Neurális Hálózat U-Net Autoencoder
Megerősítő tanulás	Markov folyamat Bellman egyenlet Mohó algoritmus Q-learning SARSA Időbeli különbség (TD)
Elmélet	Vapnik-Chervonenkis elmélet Elfogultság-diszperziós dilemma Számítógépes tanuláselmélet Empirikus kockázatminimalizálás Occam tanul PAC tanulás Statisztikai tanuláselmélet
Folyóiratok és konferenciák	NeurIPS ICML ML JMLR ArXiv:cs.LG