Nivel de emisión local

El nivel de valores atípicos locales es un algoritmo en la detección de anomalías propuesto por Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng y Jörg Sander en 2000 para encontrar puntos de datos de valores atípicos midiendo la desviación local de un punto dado dado sus vecinos. [1] .

El nivel de valores atípicos locales comparte conceptos con DBSCAN y OPTICS , como los conceptos de "distancia básica" y "distancia alcanzable" [2] , que se utilizan para estimar la densidad local [3] .

Idea básica

El nivel de valores atípicos locales se basa en el concepto de densidad local, donde la localidad viene dada por los vecinos más cercanos, cuyas distancias se utilizan para estimar la densidad. Al comparar la densidad local de un objeto con la densidad local de sus vecinos, es posible identificar áreas con una densidad similar y puntos que tienen una densidad significativamente menor que sus vecinos. Estos puntos se consideran valores atípicos . $k$

La densidad local se estima por la distancia típica a la que se puede "alcanzar" un punto desde los puntos vecinos. La definición de "distancia alcanzable" utilizada en el algoritmo es una medida adicional para obtener resultados más sólidos dentro de los clústeres.

Descripción formal

Sea la distancia del objeto al k -ésimo vecino más cercano. Tenga en cuenta que el conjunto de k vecinos más cercanos incluye todos los objetos a esa distancia y, en el caso de un "nodo", puede contener más de k objetos. Denotamos el conjunto de k vecinos más cercanos como . ${\mbox{k-distancia}}(A)$ $A$ ${\ Displaystyle N_ {k} (A)}$

Esta distancia se utiliza para determinar la distancia alcanzable ( eng. reachability-distance ):

${\mbox{accesibilidad-distancia}}_{k}(A,B)=\max\{{\mbox{k-distancia}}(B),d(A,B)\}$

En otras palabras, la distancia alcanzable de un objeto es la verdadera distancia de los dos objetos. Las características que pertenecen a los k vecinos más cercanos del punto (los "puntos centrales" del punto , consulte DBSCAN ) se consideran a la misma distancia para obtener resultados más estables. Tenga en cuenta que esta distancia no es una distancia en el sentido matemático, ya que no es simétrica. (Un error común es aplicar siempre, por lo que esto da un método ligeramente diferente, llamado método de valor atípico local simplificado [4] ) $A$ $B$ $B$ $B$ ${\mbox{k-distancia))$

La densidad de accesibilidad local de un objeto se define como $A$

${\mbox{lrd}}_{k}(A):=1/\left({\frac {\sum_B\in N_{k}(A)}{\mbox{accesibilidad-distancia }}_{k}(A,B)}{|N_{k}(A)|}}\right)$ ,

que es el recíproco de la distancia de accesibilidad promedio de un objeto de sus vecinos. Tenga en cuenta que esta no es la distancia de accesibilidad promedio de los vecinos desde el punto (que por definición tendría que ser ), sino la distancia a la que se puede "alcanzar" A desde sus vecinos. Con puntos duplicados, este valor puede llegar a ser infinito. $A$ $A$ ${\mbox{k-distancia}}(A)$

Las densidades de accesibilidad locales se comparan luego con las densidades de accesibilidad locales de los vecinos.

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

que es la densidad de accesibilidad local promedio de los vecinos dividida por la densidad de accesibilidad local del objeto en sí. Un valor aproximadamente igual a , significa que el objeto es comparable a sus vecinos (y entonces no es un valor atípico). Un valor menor que significa una región densa (que puede ser el interior), mientras que valores significativamente mayores que , indican valores atípicos. $una$ $una$ $una$

Beneficios

Debido a la localidad del enfoque, el algoritmo de nivel de valor atípico local puede detectar valores atípicos en el conjunto de datos que podrían no serlo en otras áreas del conjunto de datos. Por ejemplo, un punto a una distancia "pequeña" de cualquier grupo denso es un valor atípico, mientras que un punto dentro de un grupo disperso puede tener distancias similares a sus vecinos.

Si bien la intuición geométrica del algoritmo solo se aplica a espacios vectoriales de baja dimensión, el algoritmo se puede aplicar en cualquier contexto en el que se pueda definir una función de disimilitud. Se ha demostrado experimentalmente que el algoritmo funciona bien en una gran cantidad de situaciones, a menudo superando a sus rivales, por ejemplo, en sistemas de detección de intrusos [5] y en datos de clasificación procesados [6] .

La familia de métodos de niveles de valores atípicos locales se puede generalizar fácilmente y luego aplicar a varios otros problemas, como la detección de valores atípicos en datos geográficos, transmisiones de video o redes de crédito [4] .

Desventajas y extensiones

Los valores resultantes son difíciles de interpretar. Un valor de 1 o incluso menor que uno indica que el punto es puramente interno, pero no existe una regla clara de que un punto sea un valor atípico. En un conjunto de datos, un valor de 1,1 ya puede significar un valor atípico, en otro conjunto de datos y parametrización (con fuertes fluctuaciones locales), un valor de 2 aún puede significar un interior. Estas diferencias pueden ocurrir dentro del mismo conjunto de datos debido a la localidad del método. Hay extensiones de método que intentan mejorar el algoritmo:

El empaquetado de características para la detección de características [7] realiza un algoritmo de nivel de valor atípico local en múltiples proyecciones y combina los resultados para mejorar la calidad de detección en grandes dimensiones. Este es el primer enfoque basado en conjuntos para la detección de aislamiento; para otras opciones, consulte Zimek, Campello y Sander [8] .
La probabilidad de valor atípico local ( LOOP) [9] es un método derivado del método de nivel de valor atípico local, pero que utiliza estadísticas locales frugales para hacer que el método sea menos sensible a la elección del parámetro k . Además, los valores resultantes se escalan al valor de . ${\ estilo de visualización [0:1]}$
Interpretar y unificar puntuaciones de valores atípicos [ 10] implica normalizar la estimación de valores atípicos a un intervalo utilizando escalas estadísticas para aumentar la usabilidad y el algoritmo puede considerarse como una versión mejorada de la idea de la probabilidad de valores atípicos locales. ${\ estilo de visualización [0:1]}$
On Evaluation of Outlier Rankings and Outlier Scores [ 11] ofrece un medio para medir la similitud y la diferencia de los métodos para construir un conjunto avanzado de métodos de detección de valores atípicos utilizando variantes del algoritmo local de nivel de valores atípicos y otros algoritmos y mejorando el enfoque de embolsado de características, que fue discutido arriba.
Detección de valores atípicos locales revisada: una vista generalizada de la localidad con aplicaciones para la detección de valores atípicos espaciales, la detección de valores atípicos en redes y videos [4] analiza el marco general en varios métodos de detección de valores atípicos locales (incluido el algoritmo de nivel de valores atípicos locales, su versión simplificada y LLP) y traduce la consideración en principios generales. Luego, estos principios se aplican, por ejemplo, para identificar valores atípicos en datos geográficos, transmisiones de video y la red de atribución.

Notas

↑ Breunig, Kriegel, Ng, Sander, 2000 , pág. 93–104.
↑ En lugar de "distancia alcanzable" en la literatura, también se encuentra el nombre "alcance".
↑ Breunig, Kriegel, Ng, Sander, 1999 , pág. 262.
↑ 1 2 3 Schubert, Zimek, Kriegel, 2012 .
↑ Lazarevic, Ozgur, Ertoz, Srivastava, Kumar, 2003 , pág. 25–36.
↑ Campos, Zimek, Sander, Campello et al., 2016 .
↑ Lazarevic y Kumar 2005 , pág. 157–166.
↑ Zimek, Campello, Sander, 2014 , p. once.
↑ Kriegel, Kröger, Schubert, Zimek, 2009 , pág. 1649-1652
↑ Kriegel, Kröger, Schubert, Zimek, 2011 , pág. 13–24.
↑ Schubert, Wojdanowski, Zimek, Kriegel, 2012 , pág. 1047-1058.

Literatura

Breunig MM, Kriegel H.-P., Ng RT, Sander JR LOF: Identificación de valores atípicos locales basados en la densidad // Actas de la Conferencia internacional ACM SIGMOD 2000 sobre gestión de datos . - 2000. - ( SIGMOD ). — ISBN 1-58113-217-4 . -doi : 10.1145/ 335191.335388 .
Breunig MM, Kriegel H.-P., Ng RT, Sander JR OPTICS-OF: Identificación de valores atípicos locales // Principios de minería de datos y descubrimiento de conocimiento . - 1999. - T. 1704. - (Apuntes de cátedra en Informática). - 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. Un estudio comparativo de los esquemas de detección de anomalías en la detección de intrusos en la red // Proc. III Congreso Internacional SIAM de Minería de Datos . — 2003. Archivado el 17 de julio de 2013 en Wayback Machine .
Guilherme Campos, Arthur Zimek, Jörg Sander, Ricardo JGB Campello, Barbora Micenková, Erich Schubert, Ira Assent, Michael E. Houle. Sobre la evaluación de la detección de valores atípicos no supervisados: medidas, conjuntos de datos y un estudio empírico // Minería de datos y descubrimiento de conocimiento. - 2016. - ISSN 1384-5810 . -doi : 10.1007/ s10618-015-0444-8 .
Lazarevic A., Kumar V. Embolsado de características para la detección de valores atípicos // Proc. XI Congreso Internacional ACM SIGKDD sobre Descubrimiento de Conocimiento en Minería de Datos. - 2005. - doi : 10.1145/1081870.1081891 .
Zimek A., Campello RJGB, Sander JR Conjuntos para la detección de valores atípicos no supervisados // ACM SIGKDD Explorations Newsletter. - 2014. - T. 15 . -doi : 10.1145/ 2594473.2594476 .
Kriegel H.-P., Kröger P., Schubert E., Zimek A. LoOP: Probabilidades atípicas locales // Actas de la 18.ª conferencia ACM sobre gestión de la información y el conocimiento. - 2009. - ISBN 978-1-60558-512-3 . -doi : 10.1145/ 1645953.1646195 .
Kriegel H.-P., Kröger P., Schubert E., Zimek A. Interpretación y unificación de puntajes atípicos // Actas de la Conferencia Internacional SIAM 2011 sobre Minería de Datos. - 2011. - ISBN 978-0-89871-992-5 . -doi : 10.1137/ 1.9781611972818.2 .
Schubert E., Wojdanowski R., Zimek A., Kriegel HP Sobre la evaluación de clasificaciones de valores atípicos y puntajes de valores atípicos // Actas de la Conferencia Internacional SIAM 2012 sobre Minería de Datos. - 2012. - ISBN 978-1-61197-232-0 . -doi : 10.1137/ 1.9781611972825.90 .
Schubert E., Zimek A., Kriegel H.-P. Reconsideración de la detección de valores atípicos locales: una visión generalizada de la localidad con aplicaciones para la detección de valores atípicos espaciales, de video y de red // Minería de datos y descubrimiento de conocimientos. - 2012. - doi : 10.1007/s10618-012-0300-z .

Aprendizaje automático y minería de datos
Tareas	Problema de clasificación Aprender sin un maestro Aprendizaje asistido por profesores Análisis de regresión AutoML reglas de asociación Extracción de características entrenamiento de rasgos Entrenamiento de clasificación Derivación gramatical Aprender en línea
Aprendiendo con un maestro	método del k-vecino más cercano Clasificador bayesiano ingenuo árbol de decisión Máquinas de vectores soporte Regresión lineal Regresión logística perceptrón conjuntos de modelos Harpillera impulsar bosque aleatorio Método de vector relevante
análisis de conglomerados	método k-medias método de agrupamiento difuso Agrupación jerárquica algoritmo EM ABEDUL CURAR DBSCAN ÓPTICA Desplazamiento medio
Reducción de dimensionalidad	Análisis factorial Método de componentes principales CCA ICA LDA Expansión de matriz no negativa t-SNE
Pronóstico estructural	Graficar modelo probabilístico red bayesiana Modelo oculto de Markov FRC
Detección de anomalías	método del k-vecino más cercano Nivel de emisión local
Graficar modelos probabilísticos	red bayesiana Red de Markov Modelo oculto de Markov
Redes neuronales	Máquina Boltzmann limitada mapa autoorganizado Función de activación Sigmoideo softmax Funcion de base radial Método de propagación hacia atrás Aprendizaje profundo perceptrón multicapa Red neuronal recurrente memoria a corto plazo Bloque recurrente controlado Red neuronal convolucional U-red Codificador automático
Aprendizaje reforzado	proceso de Markov Ecuación de Bellman Algoritmo codicioso Q-aprendizaje SARAS Diferencia temporal (DT)
Teoría	Teoría de Vapnik-Chervonenkis Dilema de dispersión de sesgo Teoría del aprendizaje computacional Minimización empírica del riesgo El aprendizaje de Occam aprendizaje PAC Teoría del aprendizaje estadístico
revistas y congresos	NeurIPS ICML ML JMLR ArXiv:cs.LG