Más sobre ciencia de datos en cienciadedatos.net

Versión PDF

Introducción

Isolation Forest es una 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 crea 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

Crear un nodo raíz que contiene las $N$ observaciones de entrenamiento.
Seleccionar aleatoriamente un atributo $i$ y un valor aleatorio $a$ dentro del rango observado de $i$
Crear dos nuevos nodos separando las observaciones acorde al criterio $x_i \leq a$ o $x_i > a$
Repetir los pasos 2 y 3 hasta que todas las observaciones quedan 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 de originales. El valor predicho para cada observacion es el número de divisiones promedio que se han necesitado para aislar dicha observacion en el conjunto de árboles. Cuanto menor es este valor, mayor es la probabilidad de que se trate de una anomalía.

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.

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

Este documento pertenece a una serie en la que se muestran diferentes métodos no supervisados para la detección de anomalías: Detección de anomalías: Autoencoders y PCA y Detección de anomalías: trimmed k-means

Packages

Dos implementaciones de isolation forest en R pueden encontrarse en los paquetes h2o y solitude.

library(R.matlab)   # Lectura de archivos .mat
library(h2o)        # Modelo isolation forest
library(solitude)   # Modelo isolation forest
library(tidyverse)  # Preparación de datos y gráficos

Data sets

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

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.
Speech dataset link:
- Número de observaciones: 3686
- Número de variables: 400
- Número de outliers: 61 (1.65%)
- y: 1 = outliers, 0 = inliers
- Referencia: Learing Outlier Ensembles: The Best of Both Worlds – Supervised and Unsupervised. Barbora Micenkova, Brian McWilliams, and Ira Assent, KDD ODD2 Workshop, 2014.
Shuttle dataset link:
- Número de observaciones: 49097
- Número de variables: 9
- Número de outliers: 3511 (7%)
- y: 1 = outliers, 0 = inliers
- Referencia: Abe, Naoki, Bianca Zadrozny, and John Langford. “Outlier detection by active learning.” Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2006.

Todos estos data sets 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.

Los datos están disponibles en formato matlab (.mat). Para leer su contenido se emplea la función readMat() del paquete R.matlab v3.6.2.

cardio_mat  <- readMat("./datos/cardio.mat")
df_cardio   <- as.data.frame(cardio_mat$X)
df_cardio$y <- as.character(cardio_mat$y)

speech_mat  <- readMat("./datos/speech.mat")
df_speech   <- as.data.frame(speech_mat$X)
df_speech$y <- as.character(speech_mat$y)

shuttle_mat  <- readMat("./datos/shuttle.mat")
df_shuttle   <- as.data.frame(shuttle_mat$X)
df_shuttle$y <- as.character(shuttle_mat$y)

datos <- df_cardio

Isolation forest H2O

Se emplea el paquete h2o para entrenar un modelo isolation forest con el que detectar anomalías.

Modelo

datos <- df_cardio

# Se inicializa el cluster H2O
h2o.init(ip = "localhost",
         # Todos los cores disponibles.
         nthreads = -1,
         # Máxima memoria disponible para el cluster.
         max_mem_size = "4g")

h2o.removeAll()
h2o.no_progress()

# Carga de datos en el cluster H2O
datos_h2o <- as.h2o(x = datos)

# Modelo isolation forest
isoforest <- h2o.isolationForest(
                model_id = "isoforest",
                training_frame = datos_h2o,
                x              = colnames(datos_h2o)[-22],
                max_depth      = 350, # Profundidad máxima de los árboles
                ntrees         = 500, # Número de los árboles
                sample_rate    = 0.9 # Ratio de observaciones empleadas en cada árbol
             )
isoforest

## Model Details:
## ==============
## 
## H2OAnomalyDetectionModel: isolationforest
## Model ID:  isoforest 
## Model Summary: 
##   number_of_trees number_of_internal_trees model_size_in_bytes min_depth
## 1             500                      500             9625638        23
##   max_depth mean_depth min_leaves max_leaves mean_leaves
## 1        41   30.03400       1472       1576  1522.80000
## 
## 
## H2OAnomalyDetectionMetrics: isolationforest
## ** Reported on training data. **
## ** Metrics reported on Out-Of-Bag training samples **

Predicción

Con el modelo entrenado, se predicen las distancias de aislamiento promedio de cada observación. Los resultados devueltos por h2o contiene la distancia promedio mean_length y su valor normalizado predict.

predicciones_h2o <- h2o.predict(
                      object  = isoforest,
                      newdata = datos_h2o
                    )
predicciones <- as.data.frame(predicciones_h2o)
head(predicciones)

ggplot(data = predicciones, aes(x = mean_length)) +
  geom_histogram(color = "gray40") +
  geom_vline(
    xintercept = quantile(predicciones$mean_length, seq(0, 1, 0.1)),
    color      = "red",
    linetype   = "dashed") +
  labs(
    title = "Distribución de las distancias medias del Isolation Forest",
    subtitle = "Cuantiles marcados en rojo"  ) +
  theme_bw() +
  theme(plot.title = element_text(size = 11))

cuantiles <- quantile(x = predicciones$mean_length, probs = seq(0, 1, 0.05))
cuantiles

##     0%     5%    10%    15%    20%    25%    30%    35%    40%    45%    50% 
##  7.816 12.190 13.248 13.901 14.396 14.881 15.260 15.664 16.014 16.389 16.764 
##    55%    60%    65%    70%    75%    80%    85%    90%    95%   100% 
## 17.120 17.412 17.707 18.056 18.393 18.762 19.124 19.542 20.235 22.076

Detección de anomalías

Una vez que la distancia de separación ha sido calculado, se puede emplear como criterio para identificar anomalías. Asumiendo que las observaciones con valores atípicos 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.

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.

datos <- datos %>%
         bind_cols(predicciones)

ggplot(data = datos,
       aes(x = y, y = mean_length)) +
geom_jitter(aes(color = y), width = 0.03, alpha = 0.3) + 
geom_violin(alpha = 0) +
geom_boxplot(width = 0.2, outlier.shape = NA, alpha = 0) +
stat_summary(fun = "mean", colour = "orangered2", size = 3, geom = "point") +
labs(title = "Distancia promedio en el modelo Isolation Forest",
     x = "clasificación (0 = normal, 1 = anomalía)",
     y = "Distancia promedio") +
theme_bw() + 
theme(legend.position = "none",
      plot.title = element_text(size = 11)
)

La distancia promedio en el grupo de las anomalías (1) es claramente inferior. Sin embargo, al existir solapamiento, si se clasifican las n observaciones con menor distancia 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 distancia predicha.

resultados <- datos %>%
              select(y, mean_length) %>%
              arrange(mean_length) %>%
              mutate(clasificacion = if_else(row_number() <= 176, "1", "0"))

mat_confusion <- MLmetrics::ConfusionMatrix(
                    y_pred = resultados$clasificacion,
                    y_true = resultados$y
                 )
mat_confusion

##       y_pred
## y_true    0    1
##      0 1550  105
##      1  105   71

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

Isolation forest Solitude

Se emplea el paquete solitude para entrenar un modelo isolation forest con el que detectar anomalías.

Modelo

datos <- df_cardio

# Modelo isolation forest
isoforest <- isolationForest$new(
                sample_size = as.integer(nrow(datos)/2),
                num_trees   = 500, 
                replace     = TRUE,
                seed        = 123
             )
isoforest$fit(dataset = datos %>% select(-y))

## INFO  [10:21:44.744] dataset has duplicated rows 
## INFO  [10:21:44.777] Building Isolation Forest ...  
## INFO  [10:21:45.921] done 
## INFO  [10:21:45.922] Computing depth of terminal nodes ...  
## INFO  [10:21:46.925] done 
## INFO  [10:21:47.102] Completed growing isolation forest

Predicción

Con el modelo entrenado, se predicen las distancias de aislamiento promedio de cada observación. Los resultados devueltos por isoforest$predict() contiene la distancia promedio average_depth y una métrica que mide el grado de anomalía anomaly_score. Esta última se calcula siguiendo la propuesta de Liu, Ting and Zhou doi:10.1145/2133360.2133363 . Acorde a los autores, valores próximos a 1 son indicativos de anomalía, mientras que si todos los valores son próximos a 0.5, hay poca evidencia de que el set de datos contiene anomalías. Para este ejemplo, se emplea como criterio de detección la distancia promedio.

predicciones <- isoforest$predict(
                  data = datos %>% select(-y)
                )
head(predicciones)

ggplot(data = predicciones, aes(x = average_depth)) +
  geom_histogram(color = "gray40") +
  geom_vline(
    xintercept = quantile(predicciones$average_depth, seq(0, 1, 0.1)),
    color      = "red",
    linetype   = "dashed") +
  labs(
    title = "Distribución de las distancias medias del Isolation Forest",
    subtitle = "Cuantiles marcados en rojo"  ) +
  theme_bw() +
  theme(plot.title = element_text(size = 11))

cuantiles <- quantile(x = predicciones$average_depth, probs = seq(0, 1, 0.05))
cuantiles

##    0%    5%   10%   15%   20%   25%   30%   35%   40%   45%   50%   55%   60% 
## 7.764 8.926 9.282 9.449 9.548 9.637 9.692 9.746 9.786 9.824 9.854 9.876 9.892 
##   65%   70%   75%   80%   85%   90%   95%  100% 
## 9.912 9.926 9.936 9.948 9.959 9.968 9.980 9.998

Detección de anomalías

Una vez que la distancia de separación ha sido calculado, se puede emplear como criterio para identificar anomalías. Asumiendo que las observaciones con valores atípicos en una o más de sus variables se separan del resto con mayor facilidad, aquellas observaciones con menor distancia promedio deberían ser las más atípicas.

datos <- datos %>%
         bind_cols(predicciones)

ggplot(data = datos,
       aes(x = y, y = average_depth)) +
geom_jitter(aes(color = y), width = 0.03, alpha = 0.3) + 
geom_violin(alpha = 0) +
geom_boxplot(width = 0.2, outlier.shape = NA, alpha = 0) +
stat_summary(fun = "mean", colour = "orangered2", size = 3, geom = "point") +
labs(title = "Distancia promedio en el modelo Isolation Forest",
     x = "clasificación (0 = normal, 1 = anomalía)",
     y = "Distancia promedio") +
theme_bw() + 
theme(legend.position = "none",
      plot.title = element_text(size = 11)
)

resultados <- datos %>%
              select(y, average_depth) %>%
              arrange(average_depth) %>%
              mutate(clasificacion = if_else(row_number() <= 176, "1", "0"))

mat_confusion <- MLmetrics::ConfusionMatrix(
                    y_pred = resultados$clasificacion,
                    y_true = resultados$y
                 )
mat_confusion

##       y_pred
## y_true    0    1
##      0 1550  105
##      1  105   71

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

Información sesión

sesion_info <- devtools::session_info()
dplyr::select(
  tibble::as_tibble(sesion_info$packages),
  c(package, loadedversion, source)
)

Bibliografía

Outlier Analysis Aggarwal, Charu C.

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

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

¿Cómo citar este documento?

Detección de anomalías: Isolation Forest por Joaquín Amat Rodrigo, disponible con licencia CC BY-NC-SA 4.0 en https://www.cienciadedatos.net/documentos/66_deteccion_anomalias_isolationforest.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! 😊

Este material, creado por Joaquín Amat Rodrigo, tiene licencia Attribution-NonCommercial-ShareAlike 4.0 International.

Detección de anomalías: Isolation Forest

Joaquín Amat Rodrigo

Mayo, 2020

Introducción

Packages

Data sets

Isolation forest H2O

Modelo

Predicción

Detección de anomalías

Isolation forest Solitude

Modelo

Predicción

Detección de anomalías

Información sesión

Bibliografía