Bosque de aislamiento

Isolation Forest es un algoritmo para la detección de anomalías de datos mediante árboles binarios . Fue desarrollado por Fei Tony Liu en 2008. ^[1] Tiene una complejidad temporal lineal y un uso bajo de memoria, lo que funciona bien para datos de gran volumen. ^{[2] [3]} Se basa en el supuesto de que, debido a que las anomalías son pocas y diferentes de otros datos, se pueden aislar utilizando pocas particiones. Al igual que los algoritmos de árboles de decisión, no realiza una estimación de densidad. A diferencia de los algoritmos de árboles de decisión, solo utiliza la longitud de la ruta para generar una puntuación de anomalía y no utiliza estadísticas de nodos de hoja de distribución de clase o valor objetivo.

El bosque de aislamiento es rápido porque divide el espacio de datos, seleccionando aleatoriamente un atributo y un punto de división. El puntaje de anomalía está inversamente asociado con la longitud de la ruta porque las anomalías necesitan menos divisiones para aislarse, porque son pocas y diferentes.

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

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 de división entre los valores mínimo y máximo permitidos para ese atributo.

En la primera figura se muestra un ejemplo de partición aleatoria en un conjunto de datos 2D de puntos distribuidos normalmente para un punto no anómalo y en la segunda para un punto que tiene más probabilidades de ser una anomalía. En las imágenes se puede apreciar que las anomalías requieren menos particiones aleatorias para aislarse, en comparación con los puntos normales.

La partición recursiva se puede representar mediante una estructura de árbol denominada Árbol de aislamiento , mientras que la cantidad 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 a partir de la raíz. Por ejemplo, la longitud de la ruta del punto en la primera figura es mayor que la longitud de la ruta del en la segunda figura. $Estilo de visualización x_{i}}$$estilo de visualización x_{j}}$

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

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

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

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

Cuando el iTree está completamente desarrollado, 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 ruta del punto se define como la cantidad de aristas que atraviesa desde el nodo raíz para llegar a un nodo externo. ${\estilo de visualización X}$$estilo de visualización h(x_{i})}$${\displaystyle x_{i}\en X}$$Estilo de visualización x_{i}}$

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

La detección de anomalías con Isolation Forest se realiza de la siguiente manera: ^[4]

1. Utilice el conjunto de datos de entrenamiento para crear una cierta cantidad de iTrees
2. Para cada punto de datos en el conjunto de prueba:
   1. Páselo a través de todos los iTrees, contando la longitud del camino para cada árbol.
   2. Asignar una “puntuación de anomalía” a la instancia
   3. Etiquetar el punto como “anomalía” si su puntuación es mayor que un umbral predefinido, que depende del dominio

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 los iTrees es equivalente a la de los árboles de búsqueda binaria (BST): una terminación en un nodo externo del iTree corresponde a una búsqueda fallida en el BST. ^[4] Por lo tanto, la estimación del promedio para las terminaciones de nodos externos es la misma que la de las búsquedas fallidas en el BST, es decir ^[5]${\estilo de visualización h(x)}$

${\displaystyle c(m)={\begin{cases}2H(m-1)-{\frac {2(m-1)}{n}}&{\text{para }}m>2\\1&{\text{para }}m=2\\0&{\text{en caso contrario}}\end{cases}}}$

donde es el tamaño del conjunto de prueba, es el tamaño del conjunto de muestra y es el número armónico, que se puede estimar mediante , donde es la constante de Euler-Mascheroni . ${\estilo de visualización n}$${\estilo de visualización m}$${\estilo de visualización H}$${\displaystyle H(i)=ln(i)+\gamma}$${\displaystyle \gamma =0,5772156649}$

Arriba, se muestra el promedio dado , por lo que podemos usarlo para normalizar y obtener una estimación del puntaje de anomalía para una instancia dada x: ${\estilo de visualización c(m)}$${\estilo de visualización h(x)}$${\estilo de visualización m}$${\estilo de visualización h(x)}$

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

donde es el valor promedio de de una colección de iTrees. Para cualquier punto de datos : ${\estilo de visualización E(h(x))}$${\estilo de visualización h(x)}$${\estilo de visualización x}$

• Si está cerca entonces es muy probable que haya una anomalía.${\estilo de visualización s}$${\estilo de visualización 1}$${\estilo de visualización x}$
• Si es más pequeño, entonces es probable que sea normal.${\estilo de visualización s}$${\estilo de visualización 0.5}$${\estilo de visualización x}$
• Si todos los puntos de la muestra tienen una puntuación cercana a , entonces es probable que todos sean normales.${\estilo de visualización 0.5}$

• Submuestreo : debido a que iForest no necesita aislar instancias normales, a menudo puede ignorar la mayor parte del conjunto de entrenamiento. Por lo tanto, funciona muy bien cuando el tamaño de la muestra se mantiene pequeño, a diferencia de la mayoría de los otros métodos, que se benefician de un tamaño de muestra grande. ^{[2] [3]}
• Swamping : cuando las instancias normales están demasiado cerca de las anomalías, aumenta la cantidad de particiones necesarias para separar las anomalías, un fenómeno conocido como swamping , que hace que sea más difícil para iForest discriminar entre anomalías y puntos normales. Una razón principal para el swamping es la presencia de demasiados datos; por lo tanto, una posible solución es el submuestreo. Debido a que iForest funciona bien con submuestreo, reducir la cantidad de puntos en la muestra también es una buena manera de reducir el efecto del swamping. ^[2]
• Enmascaramiento : cuando hay muchas anomalías, algunas de ellas pueden agruparse en un grupo denso y grande, lo que hace más difícil separar las anomalías individuales y, por lo tanto, identificarlas. Este fenómeno se denomina “ enmascaramiento ” y, al igual que el swamping, es más probable cuando la muestra es grande y se puede aliviar mediante un submuestreo. ^[2]
• Datos de alta dimensión : una limitación principal de los métodos estándar basados ​​en la distancia es su ineficiencia al tratar con datos de alta dimensión. ^[6] La razón principal es que en un espacio de alta dimensión, cada punto es igualmente disperso, por lo que el uso de una medida de separación basada en la distancia es 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 mediante el uso de la selección de características, como la curtosis , para reducir la dimensionalidad de la muestra. ^{[2] [4]}
• Solo instancias normales : iForest funciona bien incluso si el conjunto de entrenamiento no contiene puntos anómalos. ^[4] Esto se debe a que iForest describe distribuciones de datos de manera que las rutas de árboles largas corresponden a puntos de datos normales. Por lo tanto, la presencia de anomalías es irrelevante para el rendimiento de la detección.

La implementación original de Fei Tony Liu es 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]
• Bosque de aislamiento de H2O-3: una implementación de Python.
• Implementación del paquete 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 Python Outlier Detection (PyOD).

Otras variaciones de las implementaciones del algoritmo Isolation Forest:

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

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

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

• Detección de anomalías