Bosque aislado

El bosque de aislamiento es un algoritmo de aprendizaje no supervisado para la detección de anomalías que funciona según el principio de aislar anomalías, ^{[ 1 ]} en lugar de las técnicas más comunes de perfilado de puntos normales. ^{[ 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 que genera sospechas de que fue generado por una media 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 mes. Es evidente, con solo mirar la imagen, que algunos puntos (marcados con un círculo rojo) son inusualmente altos, hasta el punto de generar sospechas de que el servidor web podría haber estado bajo ataque en ese momento. Por otro lado, el segmento plano indicado por la flecha roja también parece inusual y podría ser una señal de que el servidor estuvo inactivo durante ese período.

Las anomalías en un conjunto de datos extenso pueden seguir patrones muy complejos, difíciles de detectar a simple vista en la gran mayoría de los casos. Por ello, el campo de la detección de anomalías se presta perfectamente a la aplicación de técnicas de aprendizaje automático .

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 reportan 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 los puntos anómalos en el conjunto de datos. La principal ventaja de este enfoque es la posibilidad de explotar técnicas de muestreo en una medida que no está permitida para los métodos basados ​​en perfiles, creando un algoritmo muy rápido con un bajo requerimiento de memoria. ^{[ 1 ] [ 3 ] [ 4 ]}

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 los puntos de datos anómalos en una muestra, a saber:

1. son la minoría que consta de menos casos y
2. Tienen valores de atributos que son muy diferentes de los de las instancias normales.

Dado que las anomalías suelen ser escasas y muy diferentes de los demás puntos de la muestra, deben ser más fáciles de "aislar" que los puntos normales. Basándose en este principio, Isolation Forest crea un conjunto de "árboles de aislamiento" (iTrees) para el conjunto de datos y marca como anomalías los puntos que tienen longitudes de trayectoria promedio cortas en los iTrees.

En un artículo posterior, publicado en 2012 ^{[ 2 ],} los mismos autores describieron un conjunto de experimentos para demostrar que iForest:

• tiene una baja complejidad temporal lineal y requiere poca memoria.
• es capaz de manejar datos de alta 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 reentrenamiento.

En 2013, Zhiguo Ding y Minrui Fei propusieron un marco basado en iForest para resolver el problema de la detección de anomalías en datos en tiempo real. ^{[ 5 ]} Más aplicaciones de iForest a datos en tiempo real se describen en artículos de Swee Chuan Tan et al., ^{[ 4 ]} GA Susto et al. ^{[ 6 ]} y Yu Weng et al. ^{[ 7 ]}

Uno de los principales problemas de la aplicación de iForest a la detección de anomalías no radicaba en el modelo en sí, sino en la forma en que se calculaba 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 ]} donde propusieron un modelo iForest mejorado llamado Extended Isolation Forest (EIF). En el mismo artículo, los autores describen las mejoras realizadas al modelo original y cómo logran aumentar la consistencia y confiabilidad de la puntuación de anomalía producida para un punto de datos dado.

El algoritmo Isolation Forest se basa en la tendencia de las instancias anómalas de un conjunto de datos a separarse (aislarse) más fácilmente del resto de la muestra que los puntos normales. Para aislar un punto de datos, el algoritmo genera particiones de forma recursiva en la muestra, seleccionando aleatoriamente un atributo y, a continuación, un valor de división para dicho atributo, entre los valores mínimo y máximo permitidos.

En la figura 2 se muestra un ejemplo de partición aleatoria en un conjunto de datos bidimensional de puntos con distribución normal para un punto no anómalo, y en la figura 3 para un punto con mayor probabilidad de ser una anomalía. En las imágenes se observa que las anomalías requieren menos particiones aleatorias para ser aisladas, 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 , donde 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 partiendo de la raíz. Por ejemplo, la longitud del camino del punto x _i en la figura 2 es mayor que la longitud del camino del punto x _j en la figura 3.

De forma más formal, sea X = { x ₁ , ..., x _n } un conjunto de puntos d-dimensionales y X' ⊂ X un subconjunto de 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 hijos, o un nodo interno con una "prueba" y exactamente dos nodos hijos (T _l , T _r ).
2. Una prueba en el nodo T consiste en un atributo q y un valor de división p tal que la prueba q < p determina el recorrido de un punto de datos hacia T _l o T _r .

Para construir un iTree, el algoritmo divide recursivamente X' seleccionando aleatoriamente un atributo q y un valor de división p, hasta que (i) el nodo tenga solo una instancia o (ii) todos los datos en el nodo tengan los mismos valores.

Cuando el iTree está completamente desarrollado, cada punto en X 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 de camino en el árbol, donde la longitud de camino h(x _i ) del punto${\displaystyle x_{i}\in X}$se define como el número de aristas x _i que recorre desde el nodo raíz para llegar a un nodo externo.

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

• Submuestreo : dado que iForest no necesita aislar todas las instancias normales, puede ignorar con frecuencia la gran mayoría de la muestra de entrenamiento. En 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 se desea un tamaño de muestra grande. ^{[ 1 ] [ 2 ]}
• Desbordamiento : cuando las instancias normales están demasiado cerca de las anomalías, aumenta el número de particiones necesarias para separarlas, un fenómeno conocido como desbordamiento , que dificulta que iForest discrimine entre anomalías y puntos normales. Una de las principales causas del desbordamiento 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 iForest responde muy bien al submuestreo en términos de rendimiento, la reducción del número de puntos en la muestra también es una buena manera de reducir el efecto del desbordamiento. ^{[ 1 ]}
• Enmascaramiento : cuando el número de anomalías es elevado, es posible que algunas de ellas se agrupen en un clúster denso y grande, lo que dificulta la separación de las anomalías individuales y, por consiguiente, la detección de dichos puntos como anómalos. De forma similar al enmascaramiento, 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 mitigarse mediante el submuestreo. ^{[ 1 ]}
• Datos de alta dimensión : una de las principales limitaciones de los métodos estándar basados ​​en distancias es su ineficiencia al tratar con conjuntos de datos de alta dimensión: ^{[ 9 ]} La razón principal 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 distancias es bastante ineficaz. Desafortunadamente, los datos de alta dimensión también afectan el rendimiento de detección de iForest, pero el rendimiento puede mejorarse enormemente agregando una prueba de selección de características como la curtosis para reducir la dimensionalidad del espacio de muestra. ^{[ 1 ] [ 3 ]}
• Solo instancias normales : iForest funciona bien incluso si el conjunto de entrenamiento no contiene ningún punto anómalo, ^{[ 3 ]} debido a que iForest describe las distribuciones de datos de tal manera que los valores altos de la longitud de la ruta 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.

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

1. En la primera etapa, se utiliza un conjunto de datos de entrenamiento para construir los iTrees, tal como se describe en las secciones anteriores.
2. En la segunda etapa, cada instancia del conjunto de prueba se pasa por la construcción de iTrees de la etapa anterior, y se le asigna una "puntuación de anomalía" adecuada utilizando el algoritmo que se describe a continuación.

Una vez que a todas las instancias del conjunto de prueba se les ha asignado una puntuación de anomalía, 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.

Como se describió en las secciones anteriores, el algoritmo Isolation Forest tiene un rendimiento excelente tanto desde el punto de vista computacional como del consumo de memoria. El principal problema del algoritmo original es que la forma en que se ramifican los árboles introduce un sesgo, lo que probablemente reduce la fiabilidad de las puntuaciones de anomalías para la clasificación de 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 modelo original de Isolation Forest presenta este sesgo, los autores proporcionan un ejemplo práctico basado en un conjunto de datos aleatorios extraídos de una distribución normal bidimensional con media cero y covarianza dada por la matriz identidad . En la figura 4 se muestra un ejemplo de dicho conjunto de datos.

Al observar la imagen, resulta fácil comprender que los puntos cercanos a (0, 0) probablemente sean normales, mientras que un punto alejado de (0, 0) probablemente sea anómalo. En consecuencia, la puntuación de anomalía de un punto debería aumentar de forma casi circular y simétrica a medida que se aleja radialmente del "centro" de la distribución. Sin embargo, esto no se cumple en la práctica, como demuestran los autores al generar el mapa de puntuación de anomalía producido para la distribución mediante el algoritmo Isolation Forest. Si bien las puntuaciones de anomalía aumentan correctamente a medida que los puntos se alejan radialmente, también generan regiones rectangulares con puntuaciones de anomalía más bajas en las direcciones x e y, en comparación con otros puntos que se encuentran 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 a que los límites de decisión de Isolation Forest están limitados a ser verticales u horizontales (véanse las figuras 2 y 3). ^{[ 8 ]}

Por este motivo, en su artículo, Hariri et al. proponen mejorar el algoritmo Isolation Forest 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 con una "pendiente" aleatoria. En la figura 5 se muestra un ejemplo de partición aleatoria con EIF.

Los autores demuestran cómo el nuevo enfoque logra superar las limitaciones del modelo original de Isolation Forest, lo que finalmente conduce a un mapa de puntuación de anomalías mejorado.

• Spark iForest : una implementación distribuida en Scala y Python que se ejecuta en Apache Spark . Escrito por Yang, Fangzhou .
• Isolation Forest : una implementación en Spark/Scala, creada por James Verbus del equipo de IA contra el abuso de LinkedIn .
• EIF – Una implementación de Extended Isolation Forest para la detección de anomalías por Sahand Hariri
• Implementación en Python con ejemplos en scikit-learn .

• Detección de anomalías : un enfoque en el análisis de datos. 
• Apache Spark : marco de computación en clúster de análisis de datos de código abierto 
• Bosque aleatorio : métodos de aprendizaje automático de conjunto basados ​​en árboles 
• Control estadístico de procesos – Método de control de calidad