Bosque de aislamientoes el primer algoritmo de detección de anomalías que identifica anomalías mediante el aislamiento, inicialmente fue propuesto y desarrollado por Fei Tony Liu, Kai Ming Ting y Zhi-Hua Zhou en 2008. La importancia de esta investigación radica en su desviación de la filosofía principal que subyace a la anomalía existente detectores en ese momento, donde las instancias normales se perfilan antes de que las anomalías se identifiquen como instancias que no cumplen. El bosque de aislamiento presenta un método fundamentalmente diferente que aísla explícitamente las anomalías mediante árboles binarios, lo que demuestra la nueva posibilidad de un detector de anomalías rápido que se dirige directamente a las anomalías sin el proceso intensivo de recursos del perfil de instancia normal. El algoritmo tiene una complejidad de tiempo lineal con una constante baja y un requisito de memoria bajo, que funciona bien en problemas de alta dimensión que tienen una gran cantidad de atributos irrelevantes y en situaciones en las que el conjunto de entrenamiento no contiene ninguna anomalía.[1] [2]
En estadística , una anomalía (también conocida como valor atípico ) es una observación o evento que se desvía tanto de otros eventos como para despertar sospechas de que se generó por un medio diferente. Por ejemplo, el gráfico de la figura 1 representa el tráfico de entrada a un servidor web, expresado como el número de solicitudes en intervalos de 3 horas, durante un período de un mes. Es bastante evidente, simplemente mirando la imagen, que algunos puntos (marcados con un círculo rojo) son inusualmente altos, hasta el punto de inducir a sospechar que el servidor web podría haber sido atacado en ese momento. Por otro lado, el segmento plano indicado por la flecha roja también parece inusual y posiblemente sea una señal de que el servidor estuvo inactivo durante ese período de tiempo.
Las anomalías en un gran conjunto de datos pueden seguir patrones muy complicados, que son difíciles de detectar "a simple vista" en la gran mayoría de los casos. Esta es la razón por la que el campo de la detección de anomalías se adapta bien a la aplicación de técnicas de Machine Learning .
Las técnicas más comunes empleadas para la detección de anomalías se basan en la construcción de un perfil de lo que es "normal": las anomalías se informan como aquellas instancias en el conjunto de datos que no se ajustan al perfil normal. [2] Isolation Forest utiliza un enfoque diferente: en lugar de intentar construir un modelo de instancias normales, aísla explícitamente puntos anómalos en el conjunto de datos. La principal ventaja de este enfoque es la posibilidad de explotar las técnicas de muestreo en un grado que no está permitido a los métodos basados en perfiles, creando un algoritmo muy rápido con una baja demanda de memoria. [1] [3] [4]
Historia
El algoritmo Isolation Forest (iForest) fue propuesto inicialmente por Fei Tony Liu, Kai Ming Ting y Zhi-Hua Zhou en 2008. [1] Los autores aprovecharon dos propiedades cuantitativas de puntos de datos anómalos en una muestra:
- Pocos: son la minoría que consta de menos instancias y
- Diferente: tienen valores de atributo que son muy diferentes de los de las instancias normales.
Dado que las anomalías son "pocas y diferentes", son más fáciles de "aislar" en comparación con los puntos normales. Isolation Forest crea un conjunto de "árboles de aislamiento" (iTrees) para el conjunto de datos, y las anomalías son los puntos que tienen longitudes de ruta promedio más cortas en los iTrees.
En un artículo posterior, publicado en 2012 [2], los mismos autores describieron una serie de experimentos para demostrar que iForest:
- tiene una baja complejidad de tiempo lineal y un pequeño requisito de memoria
- es capaz de manejar datos de gran dimensión con atributos irrelevantes
- se puede entrenar con o sin anomalías en el conjunto de entrenamiento
- puede proporcionar resultados de detección con diferentes niveles de granularidad sin necesidad de volver a entrenar
En 2013, Zhiguo Ding y Minrui Fei propusieron un marco basado en iForest para resolver el problema de detectar anomalías en la transmisión de datos. [5] Se describen más aplicaciones de iForest a la transmisión de datos en los artículos de Tan et al., [4] Susto et al. [6] y Weng et al. [7]
Uno de los principales problemas de la aplicación de iForest a la detección de anomalías no fue el modelo en sí, sino la forma en que se calculó la “puntuación de anomalía”. Este problema fue destacado por Sahand Hariri, Matias Carrasco Kind y Robert J. Brunner en un artículo de 2018, [8] en el que propusieron un modelo de iForest mejorado llamado Bosque de Aislamiento Extendido (EIF). En el mismo artículo, los autores describen las mejoras realizadas en el modelo original y cómo pueden mejorar la consistencia y confiabilidad de la puntuación de anomalía producida para un punto de datos dado.
Algoritmo
En la base del algoritmo Isolation Forest, existe la tendencia de las instancias anómalas en un conjunto de datos a ser más fáciles de separar del resto de la muestra (aislar), en comparación con los puntos normales. Para aislar un punto de datos, el algoritmo genera de forma recursiva particiones en la muestra seleccionando aleatoriamente un atributo y luego seleccionando aleatoriamente un valor dividido para el atributo, entre los valores mínimo y máximo permitidos para ese atributo.
Un ejemplo de partición aleatoria en un conjunto de datos 2D de puntos distribuidos normalmente se da en la Fig. 2 para un punto no anómalo y en la Fig. 3 para un punto que es más probable que sea una anomalía. Es evidente en las imágenes cómo las anomalías requieren que se aíslen menos particiones aleatorias, en comparación con los puntos normales.
Desde un punto de vista matemático, la partición recursiva se puede representar mediante una estructura de árbol denominada Árbol de aislamiento , mientras que el número de particiones necesarias para aislar un punto se puede interpretar como la longitud de la ruta, dentro del árbol, para llegar a un nodo de terminación comenzando desde la raíz. Por ejemplo, la longitud de la ruta del punto en la Fig.2 es mayor que la longitud de la trayectoria de en la figura 3.
Más formalmente, dejemos ser un conjunto de puntos d-dimensionales y . Un árbol de aislamiento (iTree) se define como una estructura de datos con las siguientes propiedades:
- para cada nodo en el árbol, es un nodo externo sin hijo o un nodo interno con una "prueba" y exactamente dos nodos hijos ( y )
- una prueba en el nodo consta de un atributo y un valor dividido tal que la prueba determina el recorrido de un punto de datos a o .
Para construir un iTree, el algoritmo divide recursivamente seleccionando aleatoriamente un atributo y un valor dividido , hasta que
- el nodo tiene solo una instancia, o
- todos los datos del nodo tienen los mismos valores.
Cuando el iTree está completamente desarrollado, cada punto en está aislado en uno de los nodos externos. Intuitivamente, los puntos anómalos son aquellos (más fáciles de aislar, por lo tanto) con la menor longitud del camino en el árbol, donde la longitud del camino de punto se define como el número de aristas atraviesa desde el nodo raíz para llegar a un nodo externo.
Se proporciona una explicación probabilística de iTree en el documento original de iForest. [1]
Propiedades del bosque de aislamiento
- Submuestreo : desde iForest no necesita aislar todos los casos normales, con frecuencia puede ignorar la gran mayoría de la población de referencia. Como consecuencia, iForest funciona muy bien cuando el tamaño de la muestra se mantiene pequeño, una propiedad que contrasta con la gran mayoría de los métodos existentes, donde generalmente es deseable un tamaño de muestra grande. [1] [2]
- Pantano : cuando las instancias normales están demasiado cerca de las anomalías, aumenta el número de particiones necesarias para separar las anomalías, un fenómeno conocido como pantano , que hace que sea más difícil para iForest discriminar entre anomalías y puntos normales. Una de las principales razones del estancamiento es la presencia de demasiados datos con el fin de detectar anomalías, lo que implica que una posible solución al problema es el submuestreo. Dado que iForest responde muy bien al submuestreo en términos de desempeño, la reducción del número de puntos en la muestra también es una buena manera de reducir el efecto de inundación. [1]
- Enmascaramiento : cuando el número de anomalías es alto, es posible que algunas de ellas se agreguen en un cúmulo denso y grande, lo que dificulta la separación de las anomalías individuales y, a su vez, la detección de puntos como anómalos. De manera similar a la inundación, este fenómeno (conocido como " enmascaramiento ") también es más probable cuando el número de puntos en la muestra es grande y puede aliviarse mediante submuestreo. [1]
- Datos de alta dimensión : una de las principales limitaciones de los métodos estándar basados en la distancia es su ineficacia al tratar con conjuntos de datos de alta dimensión :. [9] La razón principal de esto es que, en un espacio de alta dimensión, cada punto es igualmente escaso, por lo que usar una medida de separación basada en la distancia es bastante ineficaz. Desafortunadamente, los datos de alta dimensión también afectan el rendimiento de detección de iForest, pero el rendimiento se puede mejorar enormemente agregando una prueba de selección de características como Kurtosis para reducir la dimensionalidad del espacio muestral. [1] [3]
- Solo instancias normales : iForest funciona bien incluso si el conjunto de entrenamiento no contiene ningún punto anómalo, [3] la razón es que iForest describe las distribuciones de datos de tal manera que los valores altos de la longitud de la rutacorresponden a la presencia de puntos de datos. Como consecuencia, la presencia de anomalías es bastante irrelevante para el rendimiento de detección de iForest.
Detección de anomalías con bosque de aislamiento
La detección de anomalías con Isolation Forest es un proceso que consta de dos etapas principales: [3]
- En la primera etapa, se utiliza un conjunto de datos de entrenamiento para construir iTrees como se describe en las secciones anteriores.
- En la segunda etapa, cada instancia en el conjunto de prueba se pasa a través de la compilación iTrees en la etapa anterior, y se asigna una "puntuación de anomalía" adecuada a la instancia utilizando el algoritmo que se describe a continuación.
Una vez que se ha asignado una puntuación de anomalía a todas las instancias del conjunto de pruebas, es posible marcar como "anomalía" cualquier punto cuya puntuación sea mayor que un umbral predefinido, que depende del dominio al que se esté aplicando el análisis.
Puntuación de anomalía
El algoritmo para calcular la puntuación de anomalía de un punto de datos se basa en la observación de que la estructura de iTrees es equivalente a la de Binary Search Trees (BST): una terminación en un nodo externo de iTree corresponde a una búsqueda fallida en BST . [3] Como consecuencia, la estimación de la mediapara terminaciones de nodos externos es el mismo que el de las búsquedas fallidas en BST, es decir [10]
dónde es el tamaño de los datos de prueba, es el tamaño del conjunto de muestra y es el número armónico, que se puede estimar mediante , dónde es la constante de Euler-Mascheroni .
El valor de c (m) anterior representa el promedio de dado , para que podamos usarlo para normalizar y obtenga una estimación de la puntuación de anomalía para una instancia dada x:
dónde es el valor medio de de una colección de iTrees. Es interesante notar que para cualquier instancia dada:
- Si esta cerca de luego es muy probable que sea una anomalía
- Si es más pequeña que luego es probable que sea un valor normal
- si para una muestra dada a todas las instancias se les asigna una puntuación de anomalía de alrededor , entonces es seguro asumir que la muestra no tiene ninguna anomalía
Bosque de aislamiento extendido
Como se describe en las secciones anteriores, el algoritmo Isolation Forest funciona muy bien tanto desde el punto de vista computacional como del consumo de memoria. El principal problema con el algoritmo original es que la forma en que tiene lugar la ramificación de los árboles introduce un sesgo, que probablemente reducirá la confiabilidad de las puntuaciones de anomalía para clasificar los datos. Esta es la principal motivación detrás de la introducción del algoritmo Extended Isolation Forest (EIF) por Hariri et al. [8]
Para comprender por qué el bosque de aislamiento original sufre ese sesgo, los autores proporcionan un ejemplo práctico basado en un conjunto de datos aleatorios tomado de una distribución normal 2-D con media cero y covarianza dada por la matriz de identidad. En la figura 4 se muestra un ejemplo de un conjunto de datos de este tipo.
Es fácil de entender al observar la imagen que los puntos que se encuentran cerca de (0, 0) probablemente sean puntos normales, mientras que un punto que se encuentra lejos de (0, 0) probablemente sea anómalo. Como consecuencia, la puntuación de anomalía de un punto debería aumentar con un patrón casi circular y simétrico a medida que el punto se mueve radialmente hacia afuera del "centro" de la distribución. Este no es el caso en la práctica, como demuestran los autores al generar el mapa de puntuación de anomalías producido para la distribución por el algoritmo Isolation Forest. Aunque los puntajes de anomalía aumentan correctamente a medida que los puntos se mueven radialmente hacia afuera, también generan regiones rectangulares de puntaje de anomalía más bajo en las direcciones xey, en comparación con otros puntos que caen aproximadamente a la misma distancia radial del centro.
Es posible demostrar que estas regiones rectangulares inesperadas en el mapa de puntuación de anomalías son de hecho un artefacto introducido por el algoritmo y se deben principalmente al hecho de que los límites de decisión de Isolation Forest están limitados a ser verticales u horizontales (ver Fig.2 y Fig. 3). [8]
Esta es la razón por la que en su artículo, Hariri et al. proponen mejorar el Bosque de Aislamiento original de la siguiente manera: en lugar de seleccionar una característica y un valor aleatorios dentro del rango de datos, seleccionan un corte de rama que tiene una “pendiente” aleatoria. En la figura 5 se muestra un ejemplo de partición aleatoria con EIF.
Los autores muestran cómo el nuevo enfoque es capaz de superar los límites del bosque de aislamiento original, lo que eventualmente conduce a un mapa de puntuación de anomalías mejorado.
Implementaciones de código abierto
Implementación original:
- El aislamiento del bosque , un algoritmo que detecta datos-anomalías mediante árboles binarios escritos en R . Publicado por el primer autor del artículo , Liu, Fei Tony en 2009.
Otras implementaciones (en orden alfabético):
- EIF : una implementación del bosque de aislamiento extendido para la detección de anomalías de Sahand Hariri .
- Isolation Forest : una implementación de Spark / Scala, creada por James Verbus del equipo de inteligencia artificial antiabuso de LinkedIn.
- Implementación de paquete de soledad en R por Srikanth Komala Sheshachala .
- Implementación de Python con ejemplos en scikit-learn .
- Spark iForest : una implementación distribuida en Scala y Python, que se ejecuta en Apache Spark . Escrito por Yang, Fangzhou .
Ver también
- Detección de anomalías
- Bosque aleatorio
Referencias
- ^ a b c d e f g h Liu, Fei Tony; Ting, Kai Ming; Zhou, Zhi-Hua (diciembre de 2008). "Bosque de aislamiento". 2008 Octava Conferencia Internacional IEEE sobre Minería de Datos : 413–422. doi : 10.1109 / ICDM.2008.17 . ISBN 978-0-7695-3502-9. S2CID 6505449 .
- ^ a b c d Chandola, Varun; Banerjee, Arindam; Kumar, Kumar (julio de 2009). "Detección de anomalías: una encuesta" . Encuestas de computación ACM . 41 . doi : 10.1145 / 1541880.1541882 . S2CID 207172599 .
- ^ a b c d e Liu, Fei Tony; Ting, Kai Ming; Zhou, Zhi-Hua (diciembre de 2008). "Detección de anomalías basada en aislamiento" (PDF) . Transacciones de ACM sobre el descubrimiento de conocimientos a partir de datos . 6 : 1–39. doi : 10.1145 / 2133360.2133363 . S2CID 207193045 .
- ^ a b Tan, Swee Chuan; Ting, Kai Ming; Liu, Fei Tony (2011). "Detección rápida de anomalías para transmisión de datos" . Actas de la vigésimo segunda conferencia conjunta internacional sobre inteligencia artificial . 2 . AAAI Press. págs. 1511-1516. doi : 10.5591 / 978-1-57735-516-8 / IJCAI11-254 . ISBN 9781577355144.
- ^ Ding, Zhiguo; Fei, Minrui (septiembre de 2013). "Un enfoque de detección de anomalías basado en el algoritmo de bosque de aislamiento para la transmisión de datos mediante la ventana deslizante" . 3er Congreso Internacional IFAC sobre Ciencia de Automatización y Control Inteligente .
- ^ Susto, Gian Antonio; Beghi, Alessandro; McLoone, Sean (2017). "Detección de anomalías mediante bosque de aislamiento en línea: una aplicación al grabado con plasma" . 2017 28a Conferencia Anual de Fabricación de Semiconductores Avanzados de SEMI (ASMC) (PDF) . págs. 89–94. doi : 10.1109 / ASMC.2017.7969205 . ISBN 978-1-5090-5448-0.
- ^ Weng, Yu; Liu, Lei (15 de abril de 2019). "Un enfoque de detección de anomalías colectivas para flujos multidimensionales en seguridad de servicios móviles" . Acceso IEEE . 7 : 49157–49168. doi : 10.1109 / ACCESS.2019.2909750 .
- ^ a b c Hariri, Sahand; Carrasco Kind, Matias; Brunner, Robert J. (2019). "Bosque de aislamiento extendido". Transacciones IEEE sobre conocimiento e ingeniería de datos : 1. arXiv : 1811.02141 . doi : 10.1109 / TKDE.2019.2947676 . S2CID 53236735 .
- ^ Dilini Talagala, Priyanga; Hyndman, Rob J .; Smith-Miles, Kate (12 de agosto de 2019). "Detección de anomalías en datos de alta dimensión". arXiv : 1908.04000 [ stat.ML ].
- ^ Shaffer, Clifford A. (2011). Estructuras de datos y análisis de algoritmos en Java (3ª ed. Dover). Mineola, NY: Publicaciones de Dover. ISBN 9780486485812. OCLC 721884651 .