Bosque de aislamiento

Algoritmo para la detección de anomalías

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.

Historia

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]

Árboles de aislamiento

Un 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 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.

Un ejemplo de aislamiento de un punto anómalo en una distribución gaussiana 2D.

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. ${\displaystyle x_{i}}$ ${\displaystyle 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},\dots ,x_{n}\}}$ ${\displaystyle X'\subset 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 ) ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle T_{l}}$ ${\displaystyle 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 . ${\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 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. ${\displaystyle X}$ ${\displaystyle h(x_{i})}$ ${\displaystyle x_{i}\in X}$ ${\displaystyle x_{i}}$

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

Detección de anomalías

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

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 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] ${\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 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 . ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle 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: ${\displaystyle c(m)}$ ${\displaystyle h(x)}$ ${\displaystyle m}$ ${\displaystyle 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 : ${\displaystyle E(h(x))}$ ${\displaystyle h(x)}$ ${\displaystyle x}$

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

Propiedades

• 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 usar 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.

Bosque de SCi

SCiForest (Isolation Forest with Split-selection Criterion) es una extensión del algoritmo Isolation Forest original. Se enfoca específicamente en anomalías agrupadas mediante la selección de un criterio de división y la búsqueda de hiperplanos que tengan más probabilidades de producir buenos resultados. SCiForest introduce hiperplanos aleatorios que no son paralelos al eje de los atributos originales. Dado que no es necesario tener el hiperplano óptimo en cada nodo, con suficientes ensayos de hiperplanos generados aleatoriamente surgirá un hiperplano lo suficientemente bueno. Por lo tanto, el modelo resultante es considerablemente efectivo debido a la potencia agregada del aprendiz de conjunto ^[4] .

Bosque de aislamiento extendido

El bosque de aislamiento extendido (IF extendida o EIF) es otra extensión del algoritmo de bosque de aislamiento original. El IF extendido utiliza árboles rotados en diferentes planos, de manera similar a SCiForest, y se seleccionan valores aleatorios para dividir los datos, como una pendiente o intersección aleatoria.

El Bosque de Aislamiento estándar requiere dos piezas de información, que son 1) una característica o coordenada aleatoria y 2) un valor aleatorio para la característica del rango de valores disponibles en los datos. El IF Extendido también requiere solo dos piezas de información, que esta vez son 1) una característica o coordenada aleatoria y 2) un valor aleatorio para la característica del rango de valores disponibles en los datos. Esto hace que el IF Extendido sea más simple que el uso de árboles de rotación ^[7] .

Comparación entre un mapa de puntuación para un bosque de aislamiento regular (a la izquierda) y un mapa de puntuación para un bosque de aislamiento extendido (a la derecha). Esta imagen es una recreación del código proporcionado por el artículo original de EIF, utilizando la biblioteca matplotlib de Python ^[7] .

La figura muestra un mapa de puntuaciones de un bosque de aislamiento regular en comparación con un bosque de aislamiento extendido para un conjunto de datos con forma sinusoidal. Esta imagen nos permite observar claramente la mejora lograda por el bosque de aislamiento extendido al evaluar las puntuaciones con mucha más precisión en comparación con la forma de los datos. La publicación original de EIF también incluye esta comparación con un conjunto de datos con forma de un solo blob y un conjunto de datos con forma de dos blobs, y también compara los resultados de EIF con el bosque de aislamiento utilizando árboles de rotación ^[7] .

Implementaciones de código abierto

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.
• Isolation Forest: una implementación distribuida de Spark/Scala con exportación de Open Neural Network Exchange (ONNX) para una fácil inferencia multiplataforma. ^[8]
• 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. ^[7]

• 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]

Implementación de Python con Scikit-learn

Los científicos de datos suelen utilizar el algoritmo de bosque de aislamiento a través de la versión disponible en la biblioteca scikit-learn . El fragmento que aparece a continuación muestra una breve implementación de un bosque de aislamiento:

‎

importar  pandas  como  pdDesde  sklearn.ensemble  importa  IsolationForest# Considere que 'data.csv' es un archivo que contiene muestras como filas y características como columnas, y una columna denominada 'Clase' con una clasificación binaria de sus muestras.df  =  pd . read_csv ( 'datos.csv' )X  =  df . drop ( columnas = [ 'Clase' ])y  =  df [ 'Clase' ]# Determinar cuántas muestras serán valores atípicos según la clasificaciónfracción_atípica  =  len ( df [ df [ 'Clase' ] == 1 ]) / float ( len ( df [ df [ 'Clase' ] == 0 ]))# Crear y ajustar el modelo, los parámetros se pueden optimizarmodelo  =  IsolationForest ( n_estimadores = 100 ,  contaminación = fracción_atípica ,  estado_aleatorio = 42 )modelo . ajuste ( df )‎

Este fragmento es una versión adaptada y abreviada de una implementación explorada por GeeksforGeeks, a la que se puede acceder para exploraciones más profundas. ^[10]

Véase 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". Octava Conferencia Internacional IEEE sobre Minería de Datos de 2008. págs. 413–422. doi :10.1109/ICDM.2008.17. ISBN 978-0-7695-3502-9.S2CID6505449  .​
3. Liu, Fei Tony; Ting, Kai Ming; Zhou, Zhi-Hua (diciembre de 2008). "Detección de anomalías basada en aislamiento". ACM Transactions on Knowledge Discovery from Data . 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 conocimiento en bases de datos - ECML PKDD 2010: aprendizaje automático y descubrimiento de conocimiento en bases de datos . Notas de clase en informática. 6322 : 274–290. doi : 10.1007/978-3-642-15883-4_18 . ISBN . 978-3-642-15882-7.
5. Shaffer, Clifford A. (2011). Estructuras de datos y análisis de algoritmos en Java (3.ª edición de Dover). Mineola, NY: Dover Publications. ISBN 9780486485812.OCLC 721884651  .
6. 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].
7. Hariri, Sahand; Kind, Matias Carrasco; Brunner, Robert J. (abril de 2021). "Bosque de aislamiento extendido". IEEE Transactions on Knowledge and Data Engineering . 33 (4): 1479–1489. arXiv : 1811.02141 . doi :10.1109/TKDE.2019.2947676. ISSN  1558-2191. S2CID  53236735.
8. 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 .
9. Cortes, David (2019). "Aproximación de distancias mediante bosques de aislamiento". arXiv : 1910.12362 [stat.ML].
10. GeeksforGeeks, ¿Qué es Isolation Forest?, consultado el 19 de noviembre de 2024.