Detección de anomalías con Isolation Forest y python

Joaquín Amat Rodrigo
Diciembre, 2020

Introducción


Isolation Forest es un método no supervisado para identificar anomalías (outliers) cuando los datos no están etiquetados, es decir, no se conoce la clasificación real (anomalía - no anomalía) de las observaciones.

Su funcionamiento está inspirado en el algoritmo de clasificación y regresión Random Forest. Al igual que en Random Forest, un modelo Isolation Forest está formado por la combinación de múltiples árboles llamados isolation trees. Estos árboles se crean de forma similar a los de clasificación-regresión: las observaciones de entrenamiento se van separando de forma recursiva creando las ramas del árbol hasta que cada observación queda aislada en un nodo terminal. Sin embargo, en los isolation tree, la selección de los puntos de división se hace de forma aleatoria. Aquellas observaciones con características distintas al resto, quedarán aisladas a las pocas divisiones, por lo que el número de nodos necesarios para llegar a estas observación desde el inicio del árbol (profundidad) es menor que para el resto.

Algoritmo Isolation Tree


1) Crear un nodo raíz que contiene las $N$ observaciones de entrenamiento.

2) Seleccionar aleatoriamente un atributo $i$ y un valor aleatorio $a$ dentro del rango observado de $i$.

3) Crear dos nuevos nodos separando las observaciones acorde al criterio $x_i \leq a$ o $x_i > a$.

4) Repetir los pasos 2 y 3 hasta que todas las observaciones queden aisladas de forma individual en nodos terminales.


Algoritmo Isolation Forest

Eĺ modelo Isolation Forest se obtiene al combinar múltiples isolation tree, cada uno entrenado con una muestra distinta generada por bootstrapping a partir de los datos originales. El valor predicho para cada observación es el número de divisiones promedio que se han necesitado para aislar dicha observación en el conjunto de árboles. Cuanto menor es este valor, mayor es la probabilidad de que se trate de una anomalía. Con frecuencia, se utiliza el término distancia para hacer referencia al número de divisiones promedio.

Consideraciones prácticas

Al ser un método no supervisado, no hay forma de conocer el valor óptimo a partir del cual se debe de considerar que se trata de una anomalía. La puntuación asignada a cada observación es una medida relativa respecto al resto de observaciones. En la práctica, suelen considerarse como potenciales outliers aquellas observaciones cuya distancia predicha está por debajo de un determinado cuantil. Por ejemplo, si se considera que hay un 1% de anomalías, se utiliza como límite de decisión el cuantil 0.01 de todas las distancias calculadas.

Cuando se dispone de muchas observaciones, aislarlas todas en nodos terminales requiere de árboles con muchas ramificaciones, lo que se traduce en un coste computacional muy elevado. Una forma de aliviar este problema es determinar una profundidad máxima hasta la que se puede crecer el árbol. A aquellas observaciones que, una vez alcanzado el criterio de parada, no han llegado a nodos terminales individuales, se les suma el número de divisiones teóricas promedio $c(r)$ que se necesita para aislar mediante particiones binarias un nodo de $r$ observaciones.

$$c(r) = \log(r-1) - \frac{2(r - 1)}{r} + 0.5772$$



Isolation Forest en Python

Dos de las principales implementaciones de Isolation Forest están disponibles en Scikit Learn y en H2O. Si bien las dos están muy optimizadas, existen pequeñas diferencias a la hora de utilizarlas.

  • En la implementación de Scikit Learn, al entrenar el modelo, se tiene que especificar el porcentaje de anomalías que se espera en los datos de entrenamiento (contamination). Con este valor, el modelo aprende el valor a partir del cual una observación se considera anomalía. Al aplicar el método predict() se obtiene -1 si es anomalía (outlier) o 1 si es un dato normal (inliers). Para recuperar la métrica de anomalía en lugar de la clasificación, hay que emplear el método score_samples(). Este último devuelve el valor negativo de la distancia de aislamiento, normalizada tal como se propone en el paper original.

  • En la implementación de H2O, el modelo sí devuelve la distancia de aislamiento como resultado del método predict(). Para determinar si una observación es una anomalía o no, es necesario identificar el valor límite a partir de los cuantiles de las distancias predichas para las observaciones de entrenamiento.

En este documento, se muestra cómo utilizar la implementación de Scikit Learn.




Librerías


Las librerías utilizadas en este documento son:

In [116]:
# Tratamiento de datos
# ==============================================================================
import numpy as np
import pandas as pd
from mat4py import loadmat
from sklearn.datasets import make_blobs

# Gráficos
# ==============================================================================
import matplotlib.pyplot as plt
from matplotlib import style
import seaborn as sns
#style.use('ggplot') or plt.style.use('ggplot')

# Preprocesado y modelado
# ==============================================================================
from sklearn.ensemble import IsolationForest
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

# Configuración warnings
# ==============================================================================
import warnings
warnings.filterwarnings('ignore')

Datos


Los datos empleados en este documento se han obtenido de Outlier Detection DataSets (ODDS), un repositorio con datos comúnmente empleados para comparar la capacidad que tienen diferentes algoritmos a la hora de identificar anomalías (outliers). Shebuti Rayana (2016). ODDS Library [http://odds.cs.stonybrook.edu]. Stony Brook, NY: Stony Brook University, Department of Computer Science.

Todos estos conjuntos de datos están etiquetados, se conoce si las observaciones son o no anomalías (variable y). Aunque los métodos que se describen en el documento son no supervisados, es decir, no hacen uso de la variable respuesta, conocer la verdadera clasificación permite evaluar su capacidad para identificar correctamente las anomalías.

  • Cardiotocogrpahy dataset link:
    • Número de observaciones: 1831
    • Número de variables: 21
    • Número de outliers: 176 (9.6%)
    • y: 1 = outliers, 0 = inliers
    • Observaciones: todas las variables están centradas y escaladas (media 0, sd 1).
    • Referencia: C. C. Aggarwal and S. Sathe, “Theoretical foundations and algorithms for outlier ensembles.” ACM SIGKDD Explorations Newsletter, vol. 17, no. 1, pp. 24–47, 2015. Saket Sathe and Charu C. Aggarwal. LODES: Local Density meets Spectral Outlier Detection. SIAM Conference on Data Mining, 2016.

Los datos están disponibles en formato matlab (.mat). Para leer su contenido se emplea la función loadmat() del paquete mat4py 0.1.0.

In [117]:
# Lectura de datos
# ==============================================================================
datos = loadmat(filename='cardio.mat')
datos_X = pd.DataFrame(datos['X'])
datos_X.columns = ["col_" + str(i) for i in datos_X.columns]
datos_y = pd.DataFrame(datos['y'])
datos_y = datos_y.to_numpy().flatten()

Ejemplo

Modelo


La clase sklearn.ensemble.IsolationForest incorpora las principales funcionalidades que se necesitan a la hora de trabajar con modelos Isolation Forest. Los principales argumentos para entrenar este tipo de modelos son:

  • n_estimators: número de árboles que forman el modelo.

  • max_samples: número de observaciones empleadas para entrenar cada árbol.

  • contamination: proporción de anomalías esperadas en los datos de entrenamiento. En base a este valor, se establece el límite acorde al cual se clasifican las observaciones en normales o anómalas.

  • random_state: semilla para garantizar la reproducibilidad de los resultados.

Se procede a entrenar un modelo asumiendo que hay un 1% de observaciones anómalas en el conjunto de entrenamiento.

In [118]:
# Definición y entrenamiento del modelo IsolationForest
# ==============================================================================
modelo_isof = IsolationForest(
                n_estimators  = 1000,
                max_samples   ='auto',
                contamination = 0.01,
                n_jobs        = -1,
                random_state  = 123,
            )

modelo_isof.fit(X=datos_X)
Out[118]:
IsolationForest(contamination=0.01, n_estimators=1000, n_jobs=-1,
                random_state=123)

Predicción


Los modelos IsolationForest tienen dos métodos de predicción con los que se obtiene distinta información.

Con el método predict() se devuelve directamente la clasificación de anomalía (-1) o no anomalía (1) acorde a la proporción de contaminación que se ha indicado en la definición del modelo.

In [119]:
# Predicción clasificación
# ==============================================================================
clasificacion_predicha = modelo_isof.predict(X=datos_X)
clasificacion_predicha
Out[119]:
array([1, 1, 1, ..., 1, 1, 1])

Con el método score_samples(), en lugar de la clasificación, se obtiene el valor de anomalía predicho por el modelo. Es importante destacar que este valor no es la distancia de aislamiento promedio, sino una normalización de la misma propuesta en el paper original.

Como resultado de la normalización, y de multiplicarla por -1, los valores de anomalía quedan acotados en el rango [-1, 0]. Cuanto más próximo a -1 es el valor, mayor evidencia de anomalía. Valores entre -0.5 y 0 son los esperados para observaciones normales.

In [120]:
# Predicción valor anomalía
# ==============================================================================
score_anomalia = modelo_isof.score_samples(X=datos_X)
score_anomalia
Out[120]:
array([-0.41908062, -0.42765109, -0.45293005, ..., -0.47186108,
       -0.46324072, -0.53377418])

¿Qué relación hay entre predict() y score_samples()?

Durante el entrenamiento del modelo, se indicó que la proporción de anomalías (contamination) era del 1%. Esta información se utiliza para identificar cuál es el score de anomalía con el que solo un 1% de las observaciones se considerarían anomalías, es decir, el cuantil 0.01.

In [121]:
cuantil_01 = np.quantile(score_anomalia, q=0.01)
cuantil_01
Out[121]:
-0.5864598467056028

Este es el valor que se almacena automáticamente en el atributo .offset_ en función de la proporción de continuación indicada.

In [122]:
modelo_isof.offset_
Out[122]:
-0.5864598467056028
In [123]:
# Distribución de los valores de anomalía
# ==============================================================================
fig, ax = plt.subplots(nrows=1, ncols=1, figsize=(7, 3.5))
sns.distplot(
    score_anomalia,
    hist    = False,
    rug     = True,
    color   = 'blue',
    kde_kws = {'shade': True, 'linewidth': 1},
    ax      = ax
)

ax.axvline(cuantil_01, c='red', linestyle='--', label='cuantil 0.01')
ax.set_title('Distribución de los valores de anomalía')
ax.set_xlabel('Score de anomalía');

Si se utiliza el valor del cuantil para clasificar las observaciones, los resultados obtenidos son equivalentes a los devueltos por predict().

In [124]:
all(clasificacion_predicha == np.where(score_anomalia < cuantil_01, -1, 1))
Out[124]:
True

Detección de anomalías


Una vez que la distancia de separación ha sido calculada, se puede emplear como criterio para identificar anomalías. Asumiendo que las observaciones con valores atípicos en alguna de sus variables se separan del resto con mayor facilidad, aquellas observaciones con menor distancia promedio deberían ser las más atípicas. Debido a la normalización que se realiza en la implementación de Scikit Learn, esto se traduce en que, cuanto más negativo es el score predicho mayor evidencia de anomalía.

En la práctica, si se está empleando esta estrategia de detección es porque no se dispone de datos etiquetados, es decir, no se conoce qué observaciones son realmente anomalías. Sin embargo, como en este ejemplo se dispone de la clasificación real, se puede verificar si realmente los datos anómalos tienen menores distancias.

In [125]:
# Distribución de los valores de anomalía
# ==============================================================================
df_resultados = pd.DataFrame({
                    'score'    : score_anomalia,
                    'anomalia' : datos_y
                })

fig, ax = plt.subplots(nrows=1, ncols=1, figsize=(5.5, 3.5))
sns.boxplot(
    x     = 'anomalia',
    y     = 'score',
    data  = df_resultados,
    #color = "white",
    palette = 'tab10',
    ax    = ax
)

ax.set_title('Valor de anomalía del modelo Isolation Forest')
ax.set_ylabel('Score anomalía')
ax.set_xlabel('clasificación (0 = normal, 1 = anomalía)');

La distribución de los valores de anomalía (score) en el grupo de las anomalías es claramente inferior (más negativo). Sin embargo, al existir solapamiento, si se clasifican las n observaciones con menor score como anomalías, se incurriría en errores de falsos positivos.

Acorde a la documentación, el set de datos Cardiotocogrpahy contiene 176 anomalías. Véase la matriz de confusión resultante si se clasifican como anomalías las 176 observaciones con menor score predicho.

In [126]:
# Matriz de confusión de la clasificación final
# ==============================================================================
df_resultados = df_resultados \
                .sort_values('score', ascending=True) \
                .reset_index(drop=True)

df_resultados['clasificacion'] = np.where(df_resultados.index <= 176, 1, 0)

pd.crosstab(
    df_resultados.anomalia,
    df_resultados.clasificacion
)
Out[126]:
clasificacion 0 1
anomalia
0.0 1571 84
1.0 83 93

De las 176 observaciones identificadas como anomalías, solo el 53% (93/176) lo son. El porcentaje de falsos positivos (47%) es elevado, el método de isolation forest no consigue resultados notables en este set de datos.

Información de sesión

In [127]:
from sinfo import sinfo
sinfo()
-----
ipykernel   5.3.4
mat4py      0.4.3
matplotlib  3.3.2
numpy       1.19.2
pandas      1.1.3
seaborn     0.11.0
sinfo       0.3.1
sklearn     0.23.2
-----
IPython             7.18.1
jupyter_client      6.1.7
jupyter_core        4.6.3
jupyterlab          2.2.9
notebook            6.1.4
-----
Python 3.7.9 (default, Aug 31 2020, 12:42:55) [GCC 7.3.0]
Linux-5.4.0-1032-aws-x86_64-with-debian-buster-sid
4 logical CPU cores, x86_64
-----
Session information updated at 2020-12-22 22:19

Bibliografía


Outlier Analysis Aggarwal, Charu C. libro

Outlier Ensembles: An Introduction by Charu C. Aggarwal, Saket Sathe libro

https://www.h2o.ai/blog/anomaly-detection-with-isolation-forests-using-h2o/

Liu, Fei Tony, Ting, Kai Ming and Zhou, Zhi-Hua. “Isolation forest.” Data Mining, 2008. ICDM’08. Eighth IEEE International Conference on

Liu, Fei Tony, Ting, Kai Ming and Zhou, Zhi-Hua. “Isolation-based anomaly detection.” ACM Transactions on Knowledge Discovery from Data (TKDD) 6.1 (2012)

Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. 2012. Isolation-Based Anomaly Detection. ACM Trans. Knowl. Discov. Data 6, 1, Article 3 (March 2012), 39 pages. DOI:https://doi.org/10.1145/2133360.2133363

Introduction to Machine Learning with Python: A Guide for Data Scientists libro

Python Data Science Handbook by Jake VanderPlas libro

¿Cómo citar este documento?

Detección de anomalías con Isolation Forest y python by Joaquín Amat Rodrigo, available under a Attribution 4.0 International (CC BY 4.0) at https://www.cienciadedatos.net/documentos/py22-deteccion-anomalias-isolation-forest-python.html


¿Te ha gustado el artículo? Tu ayuda es importante

Mantener un sitio web tiene unos costes elevados, tu contribución me ayudará a seguir generando contenido divulgativo gratuito. ¡Muchísimas gracias! 😊


Creative Commons Licence
This work by Joaquín Amat Rodrigo is licensed under a Creative Commons Attribution 4.0 International License.