Isolation forest

Isolation Forest (en español Bosque de aislamiento) es un algoritmo para la detección de anomalías en los datos desarrollado inicialmente por Fei Tony Liu en 2008.​ Isolation Forest detecta anomalías utilizando árboles binarios. El algoritmo tiene una complejidad temporal lineal y requiere poca memoria, por lo que funciona bien con grandes volúmenes de datos.​​ En esencia, el algoritmo se basa en las características de las anomalías, es decir, que sean pocas y diferentes, para detectarlas. En el algoritmo no se realiza ninguna estimación de la densidad. El algoritmo se diferencia de los algoritmos de árbol de decisión en que sólo se utiliza la medida o aproximación de la longitud del camino para generar la puntuación de la anomalía, no se necesitan estadísticas de los nodos hoja sobre la distribución de clases o el valor objetivo.

El bosque de aislamiento es rápido porque divide el espacio de datos de forma aleatoria, utilizando un atributo seleccionado al azar y un punto de división seleccionado al azar. La puntuación de la anomalía está inversamente asociada a la longitud del camino, ya que las anomalías necesitan menos divisiones para ser aisladas, debido a 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.​ En 2010, se desarrolló una extensión del algoritmo - SCiforest​ para abordar anomalías agrupadas y paralelas a ejes. 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.

Algoritmo

Fig. 2 - Ejemplo de aislamiento de 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 recursivamente particiones en la muestra seleccionando aleatoriamente un atributo y, a continuación, seleccionando aleatoriamente un valor de partición entre los valores mínimo y máximo permitidos para ese atributo.

En la figura 2 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 figura 3 para un punto que tiene más probabilidades de ser una anomalía. En las imágenes se aprecia cómo las anomalías requieren menos particiones aleatorias para ser aisladas, en comparación con los puntos normales.

La partición recursiva puede representarse mediante una estructura de árbol denominada Árbol de aislamiento, mientras que el número de particiones necesarias para aislar un punto puede interpretarse como la longitud del camino, dentro del árbol, para llegar a un nodo terminal partiendo de la raíz. Por ejemplo, la longitud de la trayectoria del punto $x_{i}$ en la figura 2 es mayor que la longitud del recorrido de $x_{j}$ en la figura 3.

Fig. 3 - Ejemplo de aislamiento de un punto anómalo en una distribución gaussiana 2D.

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

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

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

1. el nodo sólo tiene una instancia, o
2. todos los datos del nodo tienen los mismos valores.

Cuando el iTree está completamente desarrollado, cada punto de $X$ se aísla en uno de los nodos externos. Intuitivamente, los puntos anómalos son aquellos (más fáciles de aislar, por tanto) con la menor longitud de camino en el árbol, donde la longitud de camino $h(x_{i})$ del punto $x_{i}\in X$ se define como el número de aristas $x_{i}$ que atraviesan desde el nodo raíz para llegar a un nodo externo.

En el documento original de iForest se ofrece una explicación probabilística de iTree.​

Propiedades del bosque de aislamiento

• Submuestreo: Como iForest no necesita aislar todas las instancias normales, con frecuencia puede ignorar la mayor parte de la muestra de entrenamiento. En consecuencia, iForest funciona muy bien cuando el tamaño del muestreo se mantiene pequeño, una propiedad que contrasta con la gran mayoría de los métodos existentes, en los que suele ser deseable un tamaño de muestreo grande.​​
• Swamping: Cuando las instancias normales están demasiado cerca de las anomalías, aumenta el número de particiones necesarias para separar las anomalías, fenómeno conocido como swamping, que hace más difícil para iForest discriminar entre anomalías y puntos normales. Una de las principales razones del swamping es la presencia de demasiados datos para los fines de la detección de anomalías, lo que implica que una posible solución al problema es el submuestreo. Dado que el submuestreo responde muy bien en términos de rendimiento, la reducción del número de puntos de la muestra también es una buena forma de reducir el efecto del swamping.​
• Enmascaramiento (masking): Cuando el número de anomalías es elevado, es posible que algunas de ellas se agreguen en un conglomerado denso y grande, lo que hace más difícil separar las anomalías individuales y, a su vez, detectar esos puntos como anómalos. De forma similar al swamping, este fenómeno (conocido como «masking») también es más probable cuando el número de puntos de la muestra es grande y puede paliarse mediante submuestreo.​
• Datos de alta dimensión: Una de las principales limitaciones de los métodos estándar basados en la distancia es su ineficacia a la hora de tratar conjuntos de datos de alta dimensión.​ La razón principal es que, en un espacio de alta dimensión, cada punto es igualmente disperso, por lo que utilizar una medida de separación basada en la distancia es bastante ineficaz. Desgraciadamente, los datos de alta dimensionalidad también afectan al rendimiento de detección de iForest, pero el rendimiento puede mejorarse enormemente añadiendo una prueba de selección de características, como Kurtosis, para reducir la dimensionalidad del espacio muestral.​​
• Sólo instancias normales: iForest funciona bien incluso si el conjunto de entrenamiento no contiene ningún punto anómalo,​ la razón es que iForest describe las distribuciones de datos de tal manera que los valores altos de la longitud del camino $h(x_{i})$ corresponden a la presencia de puntos de datos. En 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 compuesto por dos etapas principales:​

1. En la primera etapa, se utiliza un conjunto de datos de entrenamiento para construir iTrees.
2. En la segunda fase, cada instancia del conjunto de pruebas pasa por estos iTrees y se le asigna una «puntuación de anomalía» adecuada.

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 superior a un umbral predefinido, que depende del dominio al que se aplique el análisis.

Puntuación de anomalías

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 binarios de búsqueda Binary Search Trees (BST): una terminación en un nodo externo del iTree corresponde a una búsqueda fallida en el BST.​ En consecuencia, la estimación de la media $h(x)$ para las terminaciones de nodos externos es la misma que la de las búsquedas fallidas en BST, es decir:​

$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 $n$ es el tamaño de los datos de prueba, $m$ es el tamaño de la muestra y $H$ es el número armónico, que puede estimarse mediante $H(i)=ln(i)+\gamma$, donde $\gamma =0.5772156649$ es la constante de Euler-Mascheroni.

El valor de c(m) anterior representa la media de $h(x)$ segun $m$, por lo que podemos utilizarlo para normalizar $h(x)$ y obtener una estimación de la puntuación de anomalía para una instancia x dada:

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

Donde $E(h(x))$ es el valor promedio de $h(x)$ de una colección de iTrees. Es interesante observar que para cualquier instancia dada $x$:

• si $s$ esta cerca de $1$ entonces $x$ es muy probable que sea una anomalía.
• si $s$ es menor de $0.5$ entonces $x$ es probable que sea un valor normal.
• si para una muestra dada se asigna a todas las instancias una puntuación de anomalía de alrededor de $0.5$, entonces es seguro asumir que la muestra no tiene ninguna anomalía.

Aplicaciones de código abierto

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

Otras implementaciones (por orden alfabético):

• ELKI contiene una implementación Java.
• Isolation Forest - Una implementación de Spark/Scala.​
• Bosque de aislamiento por H2O-3 - Una implementación de Python.
• Implementación del paquete solitude en R.
• Implementación en Python con ejemplos en scikit-learn.
• Spark iForest - Una implementación distribuida de Apache Spark en Scala/Python.
• PyOD IForest - Otra implementación en Python de la popular biblioteca Python Outlier Detection (PyOD).

Otras variaciones de las implementaciones del algoritmo Isolation Forest:

• Bosque de aislamiento ampliado: aplicación del bosque de aislamiento ampliado.​
• Extended Isolation Forest by H2O-3 - Una implementación de Extended Isolation Forest.
• (Python, R, C/C++) Isolation Forest and variations - Una implementación de Isolation Forest y sus variaciones.​

Véase también

• Detección de anomalías
  

Referencias

• Datos: Q85770174