Místní úroveň emisí

Lokální odlehlá úroveň je algoritmus detekce anomálií , který navrhli Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng a Jörg Sander v roce 2000, aby našli odlehlé datové body měřením lokální odchylky daného bodu vzhledem k jeho sousedům. [1] .

Lokální odlehlá úroveň sdílí koncepty s DBSCAN a OPTICS , jako jsou koncepty „základní vzdálenosti“ a „dosažitelné vzdálenosti“ [2] , které se používají k odhadu místní hustoty [3] .

Základní myšlenka

Lokální odlehlá úroveň je založena na konceptu místní hustoty, kde lokalita je dána nejbližšími sousedy, jejichž vzdálenosti se používají k odhadu hustoty. Porovnáním místní hustoty objektu s místní hustotou jeho sousedů je možné identifikovat oblasti s podobnou hustotou a body, které mají výrazně nižší hustotu než jeho sousedé. Tyto body jsou považovány za odlehlé hodnoty . $k$

Místní hustota se odhaduje podle typické vzdálenosti bodu, kterou lze „dosáhnout“ od sousedních bodů. Definice "dosažitelné vzdálenosti" použitá v algoritmu je dalším opatřením k získání robustnějších výsledků v rámci shluků.

Formální popis

Nechť je vzdálenost od objektu ke k -tému nejbližšímu sousedovi. Všimněte si, že množina k nejbližších sousedů zahrnuje všechny objekty v dané vzdálenosti a v případě "uzlu" může obsahovat více než k objektů. Množinu k nejbližších sousedů označíme jako . ${\mbox{k-distance}}(A)$ $A$ $N_{k}(A)$

Tato vzdálenost se používá k určení dosažitelné vzdálenosti ( angl. reachability-distance ):

${\mbox{dosah-vzdálenost}}_{k}(A,B)=\max\{{\mbox{k-vzdálenost}}(B),d(A,B)\}$

Jinými slovy, dosažitelná vzdálenost objektu od je skutečná vzdálenost dvou objektů. Prvky, které patří k nejbližším sousedům bodu ( "jádrové body" bodu , viz DBSCAN ), jsou považovány za ve stejné vzdálenosti pro stabilnější výsledky. Všimněte si, že tato vzdálenost není vzdáleností v matematickém smyslu, protože není symetrická. (Obvyklou chybou je použít vždy, takže to dává trochu jinou metodu, nazývanou zjednodušená metoda místní odlehlé hodnoty [4] ) $A$ $B$ $B$ $B$ ${\mbox{k-distance))$

Hustota místní dosažitelnosti objektu je definována jako $A$

${\mbox{lrd}}_{k}(A):=1/\left({\frac {\sum _{B\in N_{k}(A)}{\mbox{dosah-vzdálenost }}_{k}(A,B)}{|N_{k}(A)|}}\right)$ ,

což je převrácená hodnota průměrné dosažitelné vzdálenosti objektu od jeho sousedů. Všimněte si, že toto není průměrná dosažitelná vzdálenost sousedů od bodu (která by podle definice musela být ), ale vzdálenost, na kterou může být A „dosaženo“ od svých sousedů. S duplicitními body může být tato hodnota nekonečná. $A$ $A$ ${\mbox{k-distance}}(A)$

Místní hustoty dosažitelnosti jsou pak porovnány s místními hustotami dosažitelnosti sousedů

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

což je průměrná místní hustota dosažitelnosti sousedů dělená místní hustotou dosažitelnosti samotného objektu. Hodnota přibližně rovna , znamená, že objekt je srovnatelný se svými sousedy (a pak nejde o odlehlou hodnotu). Hodnota menší než znamená hustou oblast (což může být vnitřek), zatímco hodnoty výrazně větší než označují odlehlé hodnoty. $jeden$ $jeden$ $jeden$

Výhody

Vzhledem k lokalitě přístupu je algoritmus místní úrovně odlehlých hodnot schopen detekovat odlehlé hodnoty v datové sadě, které nemusí být odlehlé v jiných oblastech datové sady. Například bod v „malé“ vzdálenosti od jakékoli husté shluku je odlehlý, zatímco bod v řídkém shluku může mít podobné vzdálenosti jako jeho sousedé.

Zatímco geometrická intuice algoritmu platí pouze pro nízkorozměrné vektorové prostory, algoritmus lze použít v jakémkoli kontextu, kde lze definovat funkci nepodobnosti. Experimentálně bylo prokázáno, že algoritmus funguje dobře ve velkém množství situací a často překonává soupeře, například v systémech detekce narušení [5] a na zpracovaných klasifikačních datech [6] .

Rodinu metod na místní úrovni odlehlých hodnot lze snadno zobecnit a poté aplikovat na různé další problémy, jako je detekce odlehlých hodnot v geografických datech, video streamech nebo kreditních sítích [4] .

Nevýhody a rozšíření

Výsledné hodnoty je obtížné interpretovat. Hodnota 1 nebo dokonce méně než jedna říká, že bod je čistě interní, ale neexistuje jasné pravidlo, že bod je odlehlá hodnota. V jednom datovém souboru může již hodnota 1,1 znamenat odlehlou hodnotu, v jiném datovém souboru a parametrizaci (se silnými lokálními výkyvy) může hodnota 2 stále znamenat vnitřek. Tyto rozdíly se mohou vyskytovat v rámci stejného souboru dat v důsledku lokality metody. Existují rozšíření metod, která se snaží algoritmus vylepšit:

Funkce ukládání do sáčků pro detekci funkcí [7] provádí algoritmus místní odlehlé úrovně na více projekcích a kombinuje výsledky pro lepší kvalitu detekce ve velkých rozměrech. Toto je první souborový přístup pro detekci izolace, další možnosti viz Zimek, Campello a Sander [8] .
Pravděpodobnost místní odlehlé hodnoty ( LOOP) [ 9] je metoda odvozená z metody na úrovni lokální odlehlé hodnoty, ale používá skromné místní statistiky, aby byla metoda méně citlivá na volbu parametru k . Výsledné hodnoty jsou navíc zmenšeny na hodnotu . $[0:1]$
Interpretace a sjednocení odlehlých skóre [ 10] zahrnuje normalizaci odhadu odlehlých hodnot na interval pomocí statistického škálování za účelem zvýšení použitelnosti a algoritmus lze považovat za vylepšenou verzi myšlenky místní odlehlé pravděpodobnosti. $[0:1]$
On Evaluation of Outlier Rankings and Outlier Scores [ 11] nabízí způsob měření podobnosti a rozdílu metod pro sestavení pokročilého souboru metod detekce odlehlých hodnot využívajících varianty algoritmu místní úrovně odlehlých hodnot a další algoritmy a zdokonalující přístup k ukládání funkcí, který bylo diskutováno výše.
Revidovaná místní detekce odlehlých hodnot: Zobecněný pohled na lokalitu s aplikacemi pro detekci prostorových odlehlých hodnot, video a síťovou detekci odlehlých hodnot [4] pojednává o obecném rámci v různých metodách detekce lokálních odlehlých hodnot (včetně algoritmu místní úrovně odlehlých hodnot, jeho zjednodušené verze a LLP) a převádí úvahu do obecných zásad. Tyto principy jsou pak aplikovány například na identifikaci odlehlých hodnot v geografických datech, video streamech a atribuční síti.

Poznámky

↑ Breunig, Kriegel, Ng, Sander, 2000 , str. 93–104.
↑ Místo „dosažitelné vzdálenosti“ se v literatuře vyskytuje i název „dosah“.
↑ Breunig, Kriegel, Ng, Sander, 1999 , str. 262.
↑ 1 2 3 Schubert, Zimek, Kriegel, 2012 .
↑ Lazarevic, Ozgur, Ertoz, Srivastava, Kumar, 2003 , str. 25–36.
↑ Campos, Zimek, Sander, Campello et al., 2016 .
↑ Lazarevic a Kumar 2005 , str. 157–166.
↑ Zimek, Campello, Sander, 2014 , str. jedenáct.
↑ Kriegel, Kröger, Schubert, Zimek, 2009 , str. 1649–1652
↑ Kriegel, Kröger, Schubert, Zimek, 2011 , str. 13–24.
↑ Schubert, Wojdanowski, Zimek, Kriegel, 2012 , str. 1047–1058.

Literatura

Breunig MM, Kriegel H.-P., Ng RT, Sander JR LOF: Identifying Density-based Local Outliers // Sborník z mezinárodní konference ACM SIGMOD o správě dat z roku 2000 . - 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. - (Poznámky z přednášek z informatiky). - 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. Srovnávací studie schémat detekce anomálií v detekci narušení sítě // Proc. 3. mezinárodní konference SIAM o dolování dat . — 2003. Archivováno 17. července 2013 na Wayback Machine
Guilherme Campos, Arthur Zimek, Jörg Sander, Ricardo JGB Campello, Barbora Micenková, Erich Schubert, Ira Assent, Michael E. Houle. O vyhodnocení detekce odlehlých hodnot bez dozoru: opatření, datové soubory a empirická studie // Data Mining and Knowledge Discovery. - 2016. - ISSN 1384-5810 . - doi : 10.1007/s10618-015-0444-8 .
Lazarevic A., Kumar V. Funkce pytlování pro detekci odlehlých hodnot // Proc. 11. mezinárodní konference ACM SIGKDD o objevování znalostí v dolování dat. - 2005. - doi : 10.1145/1081870.1081891 .
Zimek A., Campello RJGB, Sander JR Ensembles pro detekci odlehlých hodnot bez dozoru // Newsletter ACM SIGKDD Explorations. - 2014. - T. 15 . - doi : 10.1145/2594473.2594476 .
Kriegel H.-P., Kröger P., Schubert E., Zimek A. LoOP: Local Outlier Probabilities // Sborník příspěvků z 18. konference ACM o 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. Přehodnocení detekce místních odlehlých hodnot: Zobecněný pohled na lokalitu s aplikacemi pro detekci prostorových, video a síťových odlehlých hodnot // Dolování dat a zjišťování znalostí. - 2012. - doi : 10.1007/s10618-012-0300-z .

Strojové učení a dolování dat
Úkoly	Klasifikační problém Učení bez učitele Učení za pomoci učitele Regresní analýza AutoML Pravidla asociace Extrakce funkcí Trénink vlastností Žebříčkový trénink Gramatické odvozování Online učení
Učení s učitelem	metoda k-nejbližšího souseda Naivní Bayesův klasifikátor rozhodovací strom Podpora vektorového stroje Lineární regrese Logistická regrese perceptron Soubory modelů Pytlování posilování náhodný les Relevantní vektorová metoda
shluková analýza	metoda k-means Metoda fuzzy shlukování Hierarchické shlukování EM algoritmus BŘÍZA LÉK DBSCAN OPTIKA Střední posun
Redukce rozměrů	Faktorová analýza Metoda hlavní součásti CCA ICA LDA Nezáporná expanze matice t-SNE
Strukturální prognózy	Graf pravděpodobnosti modelu Bayesovská síť Skrytý Markovův model CRF
Detekce anomálií	metoda k-nejbližšího souseda Místní úroveň emisí
Grafové pravděpodobnostní modely	Bayesovská síť Markovská síť Skrytý Markovův model
Neuronové sítě	Limitovaný Boltzmannův stroj samoorganizující se mapa Aktivační funkce Sigmoid softmax Radiální základní funkce Metoda zpětného šíření Hluboké učení Vícevrstvý perceptron Rekurentní neuronová síť dlouhodobá krátkodobá paměť Řízený rekurentní blok Konvoluční neuronová síť U-Net Autokodér
Posílení učení	Markovský proces Bellmanova rovnice Chamtivý algoritmus Q-learning SARSA Časový rozdíl (TD)
Teorie	Vapnik-Chervonenkis teorie Dilema zkreslení Teorie počítačového učení Empirická minimalizace rizika Occam se učí PAC učení Statistická teorie učení
Časopisy a konference	NeurIPS ICML ML JMLR ArXiv:cs.LG