Introducción al algoritmo de bosque de aislamiento

El algoritmo Isolation Forest es un método de detección de anomalías no supervisado adecuado para datos continuos. Fue propuesto originalmente por el profesor Zhou Zhihua de la Universidad de Nanjing en 2008, y luego se propuso una versión mejorada en 2012. A diferencia de otros algoritmos de detección de anomalías que describen la distancia entre muestras mediante indicadores cuantitativos como la distancia y la densidad, el algoritmo de bosque de aislamiento detecta valores atípicos aislando puntos de muestra. Específicamente, el algoritmo utiliza una estructura de árbol de búsqueda binaria llamada árbol de aislamiento para aislar muestras. Dado que el número de valores atípicos es pequeño y está alejado de la mayoría de las muestras, los valores atípicos se aislarán temprano, es decir, los valores atípicos estarán más cerca del nodo raíz, mientras que los valores normales estarán más lejos del nodo raíz. Además, en comparación con algoritmos tradicionales como LOF y K-means, el algoritmo de bosque de aislamiento es más robusto para datos de alta latitud.

Primero, damos la definición de árbol de aislamiento y la longitud de la ruta de los puntos de muestra en el árbol de aislamiento.

Árbol aislado: Si es un nodo de un árbol aislado, se dan dos situaciones: el nodo externo no tiene nodos secundarios y el nodo interno tiene dos nodos secundarios y uno de prueba. Una prueba consta de una propiedad y un punto de división al que pertenece el punto y viceversa.

La longitud de la ruta del punto de muestra en el árbol aislado: el número de bordes desde el nodo raíz hasta el nodo hoja del punto de muestra.

En la figura siguiente, podemos ver intuitivamente que los puntos relativamente anormales solo se separan del todo después de 4 cortes, mientras que los puntos relativamente normales se separan del todo después de 11 divisiones. Esto también refleja la idea básica del algoritmo de bosque de aislamiento. (ps: la imagen es del artículo original)

A continuación, presentemos en detalle el algoritmo del bosque de aislamiento. El algoritmo se puede dividir aproximadamente en dos etapas. En la primera etapa, necesitamos entrenar un árbol aislado para formar un bosque aislado. Luego llevamos cada punto de muestra a cada árbol aislado en el bosque, calculamos la altura promedio y luego calculamos la puntuación atípica para cada punto de muestra.

Paso 1: para el conjunto de datos dado, seleccione aleatoriamente un subconjunto de puntos de muestra y colóquelo en el nodo raíz.

Paso 2: Especifique aleatoriamente una dimensión de las dimensiones y genere aleatoriamente un punto de corte en los datos actuales.

Paso 3: este punto de corte genera un hiperplano, que divide el espacio de datos actual en dos subespacios: los puntos de muestra con una dimensión especificada menor que p se colocan en el nodo secundario izquierdo y las muestras con una dimensión mayor Se colocan valores iguales o iguales a p. Haga clic en el nodo secundario derecho.

Paso 4: realice los pasos 2 y 3 de forma recursiva hasta que todos los nodos de hoja tengan solo un punto de muestra o el árbol aislado haya alcanzado la altura especificada.

Paso 5: recorra del paso 1 al paso 4 hasta que se genere un árbol aislado.

Segunda etapa:

Paso 1: para cada punto de datos, recorra cada árbol aislado, calcule la altura promedio del punto en el bosque y normalice todos los puntos con la altura promedio. La fórmula de cálculo de la puntuación atípica es la siguiente:

Entre ellos,

Referencia: https://dl.acm.org/citation.cfm?did = 213360.26665436366