Paikallinen päästötaso

Paikallinen poikkeava taso on poikkeamien havaitsemisen algoritmi, jota Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng ja Jörg Sander ehdottivat vuonna 2000 poikkeavien datapisteiden löytämiseksi mittaamalla tietyn pisteen paikallinen poikkeama sen naapureiden perusteella. [1] .

Paikallinen outlier-taso jakaa käsitteet DBSCANin ja OPTICSin kanssa , kuten käsitteet "perusetäisyys" ja "saavutettava etäisyys" [ 2] , joita käytetään paikallisen tiheyden arvioinnissa [3] .

Perusidea

Paikallinen outlier-taso perustuu paikallistiheyden käsitteeseen, jossa paikallisuuden antavat lähimmät naapurit, joiden etäisyyksiä käytetään tiheyden arvioinnissa. Vertaamalla kohteen paikallista tiheyttä sen naapureiden paikalliseen tiheyteen, on mahdollista tunnistaa alueita, joilla on samanlainen tiheys, ja pisteitä, joiden tiheys on huomattavasti pienempi kuin sen naapureiden. Näitä kohtia pidetään poikkeavina . $k$

Paikallinen tiheys arvioidaan tyypillisellä etäisyydellä, joka pisteeseen voidaan "päästää" viereisistä pisteistä. Algoritmissa käytetty "saavutettavan etäisyyden" määritelmä on lisätoimenpide, jolla saadaan luotettavampia tuloksia klustereissa.

Muodollinen kuvaus

Olkoon etäisyys esineestä k -nneksi lähimpään naapuriin. Huomaa, että k lähimmän naapurin joukko sisältää kaikki objektit tällä etäisyydellä ja "solmun" tapauksessa voi sisältää enemmän kuin k kohdetta. Merkitään k lähimpien naapurien joukkoa . ${\mbox{k-distance}}(A)$ $A$ $N_{k}(A)$

Tätä etäisyyttä käytetään saavutettavan etäisyyden määrittämiseen ( eng. reachability-distance ):

${\mbox{saatettavuusetäisyys}}_{k}(A,B)=\max\{{\mbox{k-etäisyys}}(B),d(A,B)\}$

Toisin sanoen kohteen tavoitettavissa oleva etäisyys on kahden kohteen todellinen etäisyys. Ominaisuudet, jotka kuuluvat pisteen k lähimpään naapuriin (pisteen "ydinpisteet" , katso DBSCAN ), katsotaan olevan samalla etäisyydellä vakaampien tulosten saamiseksi. Huomaa, että tämä etäisyys ei ole etäisyys matemaattisessa mielessä, koska se ei ole symmetrinen. (Yleinen virhe on soveltaa aina, joten tämä antaa hieman erilaisen menetelmän, jota kutsutaan yksinkertaistetuksi paikalliseksi outlier-menetelmäksi [4] ) $A$ $B$ $B$ $B$ ${\mbox{k-distance))$

Objektin paikallinen saavutettavuustiheys määritellään seuraavasti $A$

${\mbox{lrd}}_{k}(A):=1/\left({\frac {\sum _{B\in N_{k}(A)}{\mbox{ tavoitettavuus-etäisyys }}_{k}(A,B)}{|N_{k}(A)|}}\oikea)$ ,

joka on kohteen keskimääräisen saavutettavuusetäisyyden käänteisluku sen naapureista. Huomaa, että tämä ei ole naapureiden keskimääräinen saavutettavuusetäisyys pisteestä (jonka määritelmän mukaan pitäisi olla ), vaan etäisyys, jolla A voidaan "tavoita" naapureistaan . Kaksoispisteillä tästä arvosta voi tulla ääretön. $A$ $A$ ${\mbox{k-distance}}(A)$

Paikallisia saavutettavuustiheyksiä verrataan sitten naapureiden paikallisiin saavutettavuustiheyksiin

${\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)$

joka on naapureiden keskimääräinen paikallinen saavutettavuustiheys jaettuna itse kohteen paikallisella saavutettavuustiheydellä. Arvo, joka on suunnilleen yhtä suuri kuin , tarkoittaa, että kohde on verrattavissa naapureihinsa (ja silloin se ei ole poikkeava). Arvo pienempi kuin tarkoittaa tiheää aluetta (joka voi olla sisäosa), kun taas arvot, jotka ovat huomattavasti suuremmat kuin , osoittavat poikkeavia arvoja. $yksi$ $yksi$ $yksi$

Edut

Lähestymistavan paikallisuudesta johtuen paikallinen poikkeava tason algoritmi pystyy havaitsemaan tietojoukosta poikkeavia, jotka eivät välttämättä ole poikkeavia tietojoukon muilla alueilla. Esimerkiksi piste, joka on "pienellä" etäisyydellä mistä tahansa tiheästä klusterista, on poikkeava, kun taas harvassa klusterissa olevalla pisteellä voi olla samanlaiset etäisyydet naapureihinsa.

Algoritmin geometrinen intuitio koskee vain pieniulotteisia vektoriavaruuksia, mutta algoritmia voidaan soveltaa missä tahansa kontekstissa, jossa voidaan määritellä erilaisuusfunktio. On kokeellisesti osoitettu, että algoritmi toimii hyvin useissa tilanteissa, usein kilpailijoita paremmin, esimerkiksi tunkeutumisen havaitsemisjärjestelmissä [5] ja käsitellyissä luokitustiedoissa [6] .

Paikallisten outlier-tason menetelmien perhe voidaan helposti yleistää ja sitten soveltaa useisiin muihin ongelmiin, kuten poikkeamien havaitsemiseen maantieteellisissä tiedoissa, videovirroissa tai luottoverkoissa [4] .

Haitat ja laajennukset

Tuloksena olevia arvoja on vaikea tulkita. Arvo 1 tai jopa pienempi kuin yksi tarkoittaa, että piste on puhtaasti sisäinen, mutta ei ole selvää sääntöä siitä, että piste on poikkeava. Yhdessä tietojoukossa arvo 1,1 voi jo tarkoittaa poikkeavaa arvoa, toisessa aineistossa ja parametroinnissa (joissa on voimakkaita paikallisia vaihteluita) arvo 2 voi silti tarkoittaa sisäistä. Nämä erot voivat esiintyä saman tietojoukon sisällä menetelmän sijainnin vuoksi. On olemassa menetelmälaajennuksia, jotka yrittävät parantaa algoritmia:

Ominaisuuspussit piirteiden havaitsemista varten [7] suorittaa paikallisen poikkeavien tason algoritmin useissa projektioissa ja yhdistää tulokset parantaakseen havaitsemisen laatua suurissa mitoissa. Tämä on ensimmäinen ryhmäpohjainen lähestymistapa eristyksen havaitsemiseen, muista vaihtoehdoista katso Zimek, Campello ja Sander [8] .
Local Outlier Probability ( LOOP ) [9] on menetelmä, joka on johdettu paikallisen outlier-tason menetelmästä, mutta käyttää säästäviä paikallisia tilastoja tehdäkseen menetelmästä vähemmän herkkiä parametrin k valinnalle . Lisäksi saadut arvot skaalataan arvoon . $[0:1]$
Outlier Scores [ 10] tulkinta ja yhdistäminen sisältää poikkeavien arvioiden normalisoinnin intervalliin käyttämällä tilastollista skaalausta käytettävyyden lisäämiseksi, ja algoritmia voidaan pitää parannetun versiona paikallisen poikkeavien todennäköisyyden ideasta. $[0:1]$
On Evaluation of Outlier Rankings and Outlier Scores [ 11] tarjoaa keinon mitata menetelmien samankaltaisuutta ja eroa kehittyneen outlier-havaitsemismenetelmien kokonaisuuden muodostamiseksi käyttämällä paikallisen outlier-tason algoritmin ja muiden algoritmien muunnelmia ja parantamalla ominaisuuspussitusta. keskusteltiin edellä.
Tarkistettu paikallisten poikkeamien havaitseminen: yleinen näkymä paikkakunnasta, jossa on sovelluksia alueellisten poikkeamien havaitsemiseen, video- ja verkkopoikkeamien havaitsemiseen [4] käsittelee yleistä viitekehystä erilaisissa paikallisten poikkeamien havaitsemismenetelmissä (mukaan lukien paikallisten poikkeamien tason algoritmi, sen yksinkertaistettu versio ja LLP) ja kääntää harkinnan yleisiksi periaatteiksi. Näitä periaatteita sovelletaan sitten esimerkiksi poikkeamien tunnistamiseen maantieteellisistä tiedoista, videovirroista ja attribuutioverkostosta.

Muistiinpanot

↑ Breunig, Kriegel, Ng, Sander, 2000 , s. 93–104.
↑ Kirjallisuudessa "saavutettavan etäisyyden" sijasta löytyy myös nimi "reach".
↑ Breunig, Kriegel, Ng, Sander, 1999 , s. 262.
↑ 1 2 3 Schubert, Zimek, Kriegel, 2012 .
↑ Lazarevic, Ozgur, Ertoz, Srivastava, Kumar, 2003 , s. 25–36.
↑ Campos, Zimek, Sander, Campello et al., 2016 .
↑ Lazarevic ja Kumar 2005 , s. 157-166.
↑ Zimek, Campello, Sander, 2014 , s. yksitoista.
↑ Kriegel, Kröger, Schubert, Zimek, 2009 , s. 1649-1652
↑ Kriegel, Kröger, Schubert, Zimek, 2011 , s. 13–24.
↑ Schubert, Wojdanowski, Zimek, Kriegel, 2012 , s. 1047–1058.

Kirjallisuus

Breunig MM, Kriegel H.-P., Ng RT, Sander JR LOF: Tiheyspohjaisten paikallisten poikkeamien tunnistaminen // Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data . - 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 // Data Mining and Knowledge Discovery -periaatteet . - 1999. - T. 1704. - (Luentomuistiinpanot tietojenkäsittelytieteestä). - 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. Vertaileva tutkimus poikkeamien havaitsemismenetelmistä verkon tunkeutumisen havaitsemisessa // Proc. 3. SIAM:n kansainvälinen tiedonlouhintakonferenssi . — 2003. Arkistoitu 17. heinäkuuta 2013 Wayback Machinessa
Guilherme Campos, Arthur Zimek, Jörg Sander, Ricardo JGB Campello, Barbora Micenková, Erich Schubert, Ira Assent, Michael E. Houle. Valvomattoman outlier-ilmaisun arvioinnista: mittaukset, tietojoukot ja empiirinen tutkimus // Data Mining and Knowledge Discovery. - 2016. - ISSN 1384-5810 . - doi : 10.1007/s10618-015-0444-8 .
Lazarevic A., Kumar V. Ominaisuus pussitus outlier-detektioon // Proc. 11. ACM SIGKDD:n kansainvälinen konferenssi Knowledge Discovery in Data Mining -tutkimuksesta. - 2005. - doi : 10.1145/1081870.1081891 .
Zimek A., Campello RJGB, Sander JR Ensembles valvomattomaan poikkeamien havaitsemiseen // 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 International Conference on SIAM on Data Mining. - 2011. - ISBN 978-0-89871-992-5 . - doi : 10.1137/1.9781611972818.2 .
Schubert E., Wojdanowski R., Zimek A., Kriegel HP Outlier Rankings and Outlier Scores -arvioinnista // Proceedings of the 2012 International Conference on SIAM on Data Mining. - 2012. - ISBN 978-1-61197-232-0 . - doi : 10.1137/1.9781611972825.90 .
Schubert E., Zimek A., Kriegel H.-P. Paikallisten poikkeamien havaitseminen harkittu uudelleen: yleinen näkymä paikkakunnalle, jossa on sovelluksia tila-, video- ja verkkopoikkeamien havaitsemiseen // Data Mining and Knowledge Discovery. - 2012. - doi : 10.1007/s10618-012-0300-z .

Koneoppiminen ja tiedon louhinta
Tehtävät	Luokitteluongelma Oppiminen ilman opettajaa Opettajan avustama oppiminen Taantumisanalyysi AutoML Yhdistyksen säännöt Ominaisuuksien erottaminen Ominaisuuksien koulutus Ranking koulutus Kieliopillinen johtaminen Verkko-oppiminen
Opettajan kanssa oppimista	k-lähimmän naapurin menetelmä Naiivi Bayesin luokitin päätöspuu Tuki vektorikonetta Lineaarinen regressio Logistinen regressio perceptron Mallien kokoonpanot Pussittaminen tehostaa satunnainen metsä Asiaankuuluva vektorimenetelmä
ryhmäanalyysi	k-keinomenetelmä Sumea klusterointimenetelmä Hierarkkinen klusterointi EM-algoritmi KOIVU PARANTAA DBSCAN OPTIIKKA Keskimääräinen siirto
Mittasuhteiden vähentäminen	Tekijäanalyysi Pääkomponenttimenetelmä CCA ICA LDA Ei-negatiivinen matriisin laajennus t-SNE
Rakenteellinen ennustaminen	Graafinen todennäköisyysmalli Bayesin verkko Piilotettu Markovin malli CRF
Anomalian havaitseminen	k-lähimmän naapurin menetelmä Paikallinen päästötaso
Piirrä todennäköisyysmallit	Bayesin verkko Markovin verkko Piilotettu Markovin malli
Neuroverkot	Rajoitettu Boltzmann-kone itseorganisoituva kartta Aktivointitoiminto Sigmoidi softmax Radiaalinen kantafunktio Takaisin lisäysmenetelmä Syväoppiminen Monikerroksinen perceptroni Toistuva neuroverkko pitkä lyhytaikainen muisti Hallittu toistuva esto Konvoluutiohermoverkko U-Net Autoenkooderi
Vahvistusoppiminen	Markovin prosessi Bellmanin yhtälö Ahne algoritmi Q-oppiminen SARSA Aikaero (TD)
Teoria	Vapnik-Chervonenkis teoria Bias-dispersion dilemma Laskennallinen oppimisteoria Empiirinen riskin minimointi Occam oppii PAC-oppiminen Tilastollinen oppimisteoria
Lehdet ja konferenssit	NeurIPS ICML ML JMLR ArXiv:cs.LG