bosque de aislamiento

Algoritmo de detección de anomalías.

Isolation Forest es un algoritmo para la detección de anomalías en los datos desarrollado inicialmente por Fei Tony Liu en 2008. ^[1] Isolation Forest detecta anomalías utilizando árboles binarios . El algoritmo tiene una complejidad de tiempo lineal y un bajo requisito de memoria, lo que funciona bien con grandes volúmenes de datos. ^{[2] [3]} En esencia, el algoritmo se basa en las características de las anomalías, es decir, que sean pocas y diferentes, para detectar anomalías. No se realiza ninguna estimación de densidad en el algoritmo. El algoritmo se diferencia de los algoritmos de árbol de decisión en que solo se utiliza la medida o aproximación de la longitud del camino para generar la puntuación de anomalía, no se necesitan estadísticas de nodo hoja sobre la distribución de clases o el valor objetivo.

Isolation Forest es rápido porque divide el espacio de datos de forma aleatoria, utilizando atributos seleccionados al azar y puntos de división seleccionados al azar. La puntuación de anomalía está asociada inversamente con la longitud del camino, ya que las anomalías necesitan menos divisiones para aislarse, debido al hecho de que son pocas y diferentes.

Historia

El algoritmo Isolation Forest (iForest) fue propuesto inicialmente por Fei Tony Liu, Kai Ming Ting y Zhi-Hua Zhou en 2008. ^[2] En 2010, se desarrolló una extensión del algoritmo, SCiforest ^[4] para abordar los grupos agrupados y de ejes. anomalías paralelas. En 2012 ^[3], los mismos autores demostraron que iForest tiene una complejidad de tiempo lineal, un pequeño requisito de memoria y es aplicable a datos de alta dimensión.

Algoritmo

Fig. 2: un ejemplo de cómo aislar un punto no anómalo en una distribución gaussiana 2D.

La premisa del algoritmo Isolation Forest es que los puntos de datos anómalos son más fáciles de separar del resto de la muestra. Para aislar un punto de datos, el algoritmo genera particiones de forma recursiva en la muestra seleccionando aleatoriamente un atributo y luego seleccionando aleatoriamente un valor dividido entre los valores mínimo y máximo permitidos para ese atributo.

Fig. 3: un ejemplo de cómo aislar un punto anómalo en una distribución gaussiana 2D.

En la Fig. 2 se muestra un ejemplo de partición aleatoria en un conjunto de datos 2D de puntos normalmente distribuidos para un punto no anómalo y en la Fig. 3 para un punto que es más probable que sea una anomalía. De las imágenes se desprende claramente cómo las anomalías requieren que se aíslen menos particiones aleatorias, en comparación con los puntos normales.

La partición recursiva se puede representar mediante una estructura de árbol llamada Isolation Tree , mientras que el número de particiones necesarias para aislar un punto se puede interpretar como la longitud del camino, dentro del árbol, para llegar a un nodo final comenzando desde la raíz. Por ejemplo, la longitud del camino del punto en la Fig. 2 es mayor que la longitud del camino en la Fig. 3. ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$

Sea un conjunto de puntos d-dimensionales y . Un árbol de aislamiento (iTree) se define como una estructura de datos con las siguientes propiedades: ${\displaystyle X=\{x_{1},\dots ,x_{n}\}}$ ${\displaystyle X'\subset X}$

1. para cada nodo en el árbol, es un nodo externo sin ningún hijo o un nodo interno con una "prueba" y exactamente dos nodos hijos ( y ) ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle T_{l}}$ ${\displaystyle T_{r}}$
2. una prueba en el nodo consta de un atributo y un valor dividido de modo que la prueba determina el recorrido de un punto de datos hacia o . ${\displaystyle T}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle q<p}$ ${\displaystyle T_{l}}$ ${\displaystyle T_{r}}$

Para construir un iTree, el algoritmo divide recursivamente seleccionando aleatoriamente un atributo y un valor dividido , hasta que ${\displaystyle X'}$ ${\displaystyle q}$ ${\displaystyle p}$

1. el nodo tiene solo una instancia, o
2. todos los datos en el nodo tienen los mismos valores.

Cuando el iTree crece por completo, cada punto se aísla en uno de los nodos externos. Intuitivamente, los puntos anómalos son aquellos (más fáciles de aislar, por lo tanto) con la longitud de ruta más pequeña en el árbol, donde la longitud de la ruta del punto se define como el número de bordes que atraviesa desde el nodo raíz para llegar a un nodo externo. ${\displaystyle X}$ ${\displaystyle h(x_{i})}$ ${\displaystyle x_{i}\in X}$ ${\displaystyle x_{i}}$

En el artículo original de iForest se proporciona una explicación probabilística de iTree. ^[2]

Propiedades del bosque de aislamiento.

• Submuestreo : como iForest no necesita aislar todas las instancias normales, con frecuencia puede ignorar la mayoría de la muestra de entrenamiento. Como consecuencia, iForest funciona muy bien cuando el tamaño de muestra se mantiene pequeño, propiedad que contrasta con la gran mayoría de los métodos existentes, donde normalmente es deseable un tamaño de muestra grande. ^{[2] [3]}
• Swamping : cuando las instancias normales están demasiado cerca de las anomalías, el número de particiones necesarias para separar las anomalías aumenta, un fenómeno conocido como swamping , que hace que a iForest le resulte más difícil discriminar entre anomalías y puntos normales. Una de las principales razones de la saturación es la presencia de demasiados datos para la detección de anomalías, lo que implica que una posible solución al problema es el submuestreo. Dado que responde muy bien al submuestreo en términos de rendimiento, reducir el número de puntos en la muestra también es una buena forma de reducir el efecto de inundación. ^[2]
• Enmascaramiento : cuando el número de anomalías es alto, es posible que algunas de ellas se agreguen en un grupo denso y grande, lo que hace más difícil separar las anomalías individuales y, a su vez, detectar 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 un submuestreo. ^[2]
• Datos de alta dimensión : una de las principales limitaciones de los métodos estándar basados ​​en distancia es su ineficiencia al tratar con conjuntos de datos de alta dimensión. ^[5] La razón principal de esto es que, en un espacio de alta dimensión, cada punto es igualmente disperso, 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. ^{[2] [4]}
• Solo instancias normales : iForest funciona bien incluso si el conjunto de entrenamiento no contiene ningún punto anómalo, ^[4] la razón es que iForest describe las distribuciones de datos de tal manera que los valores altos de la longitud de la ruta corresponden 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. ${\displaystyle h(x_{i})}$

Detección de anomalías con bosque de aislamiento.

La detección de anomalías con Isolation Forest es un proceso compuesto de dos etapas principales: ^[4]

1. En la primera etapa, se utiliza un conjunto de datos de entrenamiento para construir iTrees.
2. en la segunda etapa, cada instancia del conjunto de pruebas pasa a través de estos iTrees y se asigna una "puntuación de anomalía" adecuada a la instancia.

Una vez que a todas las instancias del conjunto de pruebas se les ha asignado una puntuación de anomalía, es posible marcar como “anomalía” cualquier punto cuya puntuación sea mayor que un umbral predefinido, que depende del dominio al que se aplica 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 los árboles de búsqueda binaria (BST): una terminación en un nodo externo de iTree corresponde a una búsqueda fallida en BST. . ^[4] Como consecuencia, la estimación del promedio para las terminaciones de nodos externos es la misma que la de las búsquedas fallidas en BST, es decir, ^[6] ${\displaystyle h(x)}$

${\displaystyle c(m)={\begin{cases}2H(m-1)-{\frac {2(m-1)}{n}}&{\text{for }}m>2\\1&{\text{for }}m=2\\0&{\text{otherwise}}\end{cases}}}$

donde 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 puede estimarse mediante , donde es la constante de Euler-Mascheroni . ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle H}$ ${\displaystyle H(i)=ln(i)+\gamma }$ ${\displaystyle \gamma =0.5772156649}$

El valor de c(m) anterior representa el promedio de dado , por lo que podemos usarlo para normalizar y obtener una estimación de la puntuación de anomalía para una instancia determinada x: ${\displaystyle h(x)}$ ${\displaystyle m}$ ${\displaystyle h(x)}$

${\displaystyle s(x,m)=2^{\frac {-E(h(x))}{c(m)}}}$

¿Dónde está el valor promedio de una colección de iTrees? Es interesante observar que para cualquier caso dado : ${\displaystyle E(h(x))}$ ${\displaystyle h(x)}$ ${\displaystyle x}$

• si está cerca de entonces es muy probable que sea una anomalía ${\displaystyle s}$ ${\displaystyle 1}$ ${\displaystyle x}$
• si es menor que entonces es probable que sea un valor normal ${\displaystyle s}$ ${\displaystyle 0.5}$ ${\displaystyle x}$
• Si para una muestra determinada a todas las instancias se les asigna una puntuación de anomalía de alrededor de , entonces es seguro asumir que la muestra no tiene ninguna anomalía. ${\displaystyle 0.5}$

Implementaciones de código abierto

La implementación original de los autores del artículo fue Isolation Forest en R.

Otras implementaciones (en orden alfabético):

• ELKI contiene una implementación de Java.
• Bosque de aislamiento: una implementación de Spark/Scala. ^[7]
• Isolation Forest de H2O-3: una implementación de Python.
• Implementación del paquete de soledad en R.
• Implementación de Python con ejemplos en scikit-learn .
• Spark iForest: una implementación distribuida de Apache Spark en Scala/Python.
• PyOD IForest: otra implementación de Python en la popular biblioteca de detección de valores atípicos de Python (PyOD).

Otras variaciones de las implementaciones del algoritmo Isolation Forest:

• Bosque de aislamiento extendido: una implementación de Bosque de aislamiento extendido. ^[8]

• Bosque de aislamiento extendido por H2O-3: una implementación de Bosque de aislamiento extendido.

• (Python, R, C/C++) Isolation Forest y variaciones: una implementación de Isolation Forest y sus variaciones. ^[9]

Ver también

• Detección de anomalías

Referencias

1. Liu, Fei Tony. "Primera implementación de Isolation Forest en Sourceforge".
2. 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 . págs. 413–422. doi :10.1109/ICDM.2008.17. ISBN 978-0-7695-3502-9. S2CID  6505449.
3. Liu, Fei Tony; Ting, Kai Ming; Zhou, Zhi-Hua (diciembre de 2008). "Detección de anomalías basada en aislamiento". Transacciones ACM sobre descubrimiento de conocimiento a partir de datos . 6 : 3:1–3:39. doi :10.1145/2133360.2133363. S2CID  207193045.
4. Liu, Fei Tony; Ting, Kai Ming; Zhou, Zhi-Hua (septiembre de 2010). "Sobre la detección de anomalías agrupadas mediante SCiForest". Conferencia europea conjunta sobre aprendizaje automático y descubrimiento de conocimientos en bases de datos - ECML PKDD 2010: Aprendizaje automático y descubrimiento de conocimientos en bases de datos . Apuntes de conferencias sobre informática. 6322 : 274–290. doi : 10.1007/978-3-642-15883-4_18 . ISBN 978-3-642-15882-7.
5. 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 [estad.ML].
6. Shaffer, Clifford A. (2011). Estructuras de datos y análisis de algoritmos en Java (3.ª edición de Dover). Mineola, Nueva York: Publicaciones de Dover. ISBN 9780486485812. OCLC  721884651.
7. Verbus, James (13 de agosto de 2019). "Detección y prevención de abusos en LinkedIn mediante bosques de aislamiento". Blog de ingeniería de LinkedIn . Consultado el 2 de julio de 2023 .
8. Hariri, Sahand; Amable, Matías Carrasco; Brunner, Robert J. (abril de 2021). "Bosque de aislamiento extendido". Transacciones IEEE sobre conocimiento e ingeniería de datos . 33 (4): 1479–1489. arXiv : 1811.02141 . doi :10.1109/TKDE.2019.2947676. ISSN  1558-2191. S2CID  53236735.
9. Cortés, David (2019). "Aproximación de distancias mediante bosques de aislamiento". arXiv : 1910.12362 [estad.ML].