Detección de anomalías: trimmed k-means


Más sobre ciencia de datos en cienciadedatos.net

Versión PDF

Introducción


Los métodos de clustering son una de las estrategias no supervisadas que se emplean con frecuencia para la detección de anomalías (outliers). Estos algoritmos tratan de identificar regiones homogéneas separadas entre ellas por regiones heterogéneas, agrupando las observaciones de forma que, aquellas que forman parte del mismo cluster, son similares entre ellas y distintas a las de otros clusters.

Para que un método de clustering pueda emplearse como detector de anomalías, idealmente debe cumplir alguna de estas dos características:

  • No obligar a que todas las observaciones formen parte de uno de los clusters.

  • Calcular la probabilidad que tiene cada observación de pertenecer a cada uno de los clusters.

En el primer caso, se consideran anomalías aquellas observaciones que no han sido asignadas a ningún cluster. En el segundo caso, aquellas cuya probabilidad de pertenecer a alguno de los clusters está por debajo de un valor mínimo.

El requisito de permitir dejar observaciones “libres” es consecuencia de que los métodos de clustering se vean muy influenciados por observaciones anómalas. Por ejemplo:

  • Dos o más clusters pueden unirse de forma artificial debido únicamente a observaciones atípicas que se encuentran entre ellos.

  • Se pueden crear clusters artificiales compuestos únicamente por unas pocas observaciones atípicas

Una forma de minimizar estos problemas es emplear adaptaciones robustas de los algoritmos. Por ejemplo, incorporando un proceso de trimming para eliminar una fracción \(\alpha\) de los valores más extremos.

Trimmed K-means


El paquete tclust incorpora algoritmos de clustering no jerárquico que han sido adaptados para aumentar su robustez mediante el uso de trimming. En concreto, la función tkmeans() emplea una modificación robusta de K-means en la que no todas las observaciones tienen necesariamente que formar parte de un cluster. Los principales argumentos de esta función son:

  • equal.weights: si su valor es TRUE, el algoritmo trata de que todos los clusters tengan el mismo número de observaciones.

  • restr.fact: controla el grado de restricción impuesta sobre el ajuste. Cuanto mayor es su valor, menor es la restricción y mayor es la heterogeneidad permitida en los clusters creados. Valores próximos a 1 generan clusters con una dispersión similar.

  • restr: tipo de restricción impuesta a las matrices de covarianza de los clusters.

    • "eigen": controla el ratio entre el mayor y menor eigenvalue de las matrices de covarianza. Este tipo de restricción controla el tamaño relativo de los ejes de los elipsoides que definen los clusters, es decir, cuánto se desvían respecto a una forma esférica.
    • "deter": controla el ratio entre el mayor y menor determinante de las matriz de covarianzas. Este tipo de restricción controla el volumen relativo de los elipsoides que forman los clusters pero no su forma.
    • "sigma": obliga a que la matriz de covarianza de todos los clusters sea la misma.

Ejemplo


El set de datos M5data, disponible en el paquete tclust, contiene observaciones simuladas a partir de tres distribuciones gaussianas bivariante de distinta media y dispersión, dos de ellas con solapamiento. Además, se ha introducido un 10% de anomalías en la región que rodea a las componentes gaussianas Este set de datos es útil para evaluar la capacidad que tienen distintos algoritmos para detectar anomalías en entornos de pocas dimensiones.

library(tidyverse)
library(tclust)
data("M5data")
datos <- as.data.frame(M5data)
head(datos)

La columna cluster contiene la asignación verdadera de cada observación. Aquellas observaciones con el valor cero se corresponden con anomalías.

# Número de observaciones por cluster y anomalías
table(datos$cluster)
## 
##   0   1   2   3 
## 200 360 720 720
ggplot(data = datos, aes(x = x, y = y, color = as.factor(cluster))) +
geom_point() +
theme_bw() +
scale_color_manual(
  breaks = c(0,1,2,3),
  values = c("0"="gray", "1"="steelblue", "2"="orange", "3"="darkgreen")
) +
theme(legend.position = "none")

Se aplica el algoritmo de clustering asumiendo que hay 3 componentes.

clustering <- tclust(
                x = scale(datos[, 1:2], center = TRUE, scale = TRUE),
                k = 3, 
                alpha = 0.1,
                restr = "eigen", 
                restr.fact = 20,
                nstart = 50,
                iter.max = 1000
              )
clustering
## * Results for TCLUST algorithm: *
## trim = 0.1, k = 3
## Classification (trimmed points are indicated by 0 ):
##    [1] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##   [38] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##   [75] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [112] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [149] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [186] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [223] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [260] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [297] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [334] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2
##  [371] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
##  [408] 2 2 2 2 2 2 2 2 2 3 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 1 3 2 2 2 2 2 2 2 2 2 1
##  [445] 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 0 2 2 3 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2
##  [482] 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2
##  [519] 2 2 2 2 1 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 0 2 3 3 2 3 2 2 2 2 2 2 2 2 2 2 2
##  [556] 2 2 2 3 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 0 2 2 2 2 2 2 0 2 2 2 2 2 2 2
##  [593] 1 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2
##  [630] 2 2 2 2 2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 2 2 2 2 2 2 2 2 0 2 2 2
##  [667] 2 2 2 2 2 2 2 2 0 2 2 2 3 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2
##  [704] 2 2 1 2 2 2 2 0 2 2 0 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 2 2 2 1
##  [741] 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 0 2 2 2 3 2 2 2 2 2 2 2 2 2 2 3 2
##  [778] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 0 2 2
##  [815] 2 2 2 2 2 2 2 2 2 0 0 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
##  [852] 2 2 2 2 2 3 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 3 2 2 2 2 2 2 2
##  [889] 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 3 2 2 2 2 0 2 2 2 3
##  [926] 2 2 2 2 2 1 2 3 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 2 0
##  [963] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 1 2 2 2 2 3 2 2 2 2 2 2 2
## [1000] 2 2 2 2 1 2 2 3 2 2 2 2 2 1 2 2 2 2 2 2 2 2 3 2 0 2 2 2 2 2 2 2 2 2 0 2 2
## [1037] 3 2 2 2 2 2 2 2 2 2 2 2 1 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 2 2 2
## [1074] 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [1111] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [1148] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [1185] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [1222] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [1259] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [1296] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [1333] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [1370] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [1407] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [1444] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [1481] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
## [1518] 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [1555] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [1592] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [1629] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [1666] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [1703] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
## [1740] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [1777] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0
## [1814] 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
## [1851] 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0
## [1888] 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0
## [1925] 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0
## [1962] 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
## [1999] 0 0
## Means:
##          C 1       C 2         C 3
## x -0.8533448 0.8035805 -0.06343452
## y -0.7825035 0.1893434  1.17574419
## 
## Trimmed objective function:  -3223.995 
## 100% of iterations converged successfully.

Las observaciones asignadas al cluster 0 son las que han sido excluidas. Se comprueba cuántas de ellas se corresponden con verdaderas anomalías (column cluster es igual a 0).

datos$cluster_asignado <- as.factor(clustering$cluster)
head(datos)
# Número de observaciones identificadas como anomalías
sum(clustering$cluster == 0)
## [1] 200
# Número de anomalías correctamente identificadas
sum(datos$cluster == 0 & datos$cluster_asignado == 0)
## [1] 175
# Número observaciones eroneamente detectadas como anomalías.
sum(datos$cluster != 0 & datos$cluster_asignado == 0)
## [1] 25

De las 200 observaciones identificadas como anomalías, 175 lo son realmente (0.875 %). 25 observaciones han sido detectadas como anomalías cuando realmente no lo son (0.125% de falsos positivos).

ggplot(data = datos, aes(x = x, y = y,
       shape = as.factor(cluster), color = cluster_asignado)) +
geom_point() +
theme_bw() +
scale_color_manual(
  breaks = c(0, 1, 2, 3),
  values = c("0"="gray", "1"="steelblue", "2"="orange", "3"="darkgreen")
) +
labs(title = "Clasificación real vs predicha") +
theme(legend.position = "none")

En la ejecución anterior, se asumió el número de componentes k=3 y de trimming alpha=0.1, gracias a que se conoce cómo se han simulado los datos. En la práctica, esta información se desconoce y, al tratarse de un problema de aprendizaje no supervisado, no hay forma de saberlo con seguridad. Una estrategia que permite orientar en la selección de estos hiperparámetros es ver cómo varía el likelihood para diferentes valores de k y alpha e identificar el punto en el que el incremento se estabiliza. Este proceso se puede automatizar con la función ctlcurves().

grid_search <- ctlcurves(
                  x = scale(datos[, 1:2], center = TRUE, scale = TRUE),
                  k = 1:6,
                  alpha = seq(0, 0.5, 0.05),
                  restr = "eigen", 
                  restr.fact = 12,
                  nstart = 50,
                  iter.max = 1000,
                  trace = 0
                )
grid_search
## Computed 66 solutions (chosen restr.fact = 12).
## 
##    alpha
## k   0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5
##   1                                       *    *  
##   2   *                               *   *    *  
##   3 * *    *   *    *   *    *   *    *   *    *  
##   4 * *    *k  *k   *k  *k   *   *    *   *k   *k 
##   5 * *    *k  *k   *k  *    *k  *k   *k  *k   *k 
##   6 * *k   *k  *k   *k  *k   *k  *k   *k  *k   *k 
## 
## (*) Identified 50 artificially restricted solutions.
## (k) Identified 24 solutions with very small/dropped clusters.
plot(grid_search)

Acorde al gráfico, a partir de k=3 no se consigue una mejora del ajuste. Para el valor de alpha, la mejora en el ajuste es casi constante, con un incremento ligeramente más marcado entorno a 0.5-0.1.

Información sesión


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



Bibliografía


Charu C. Aggarwal. 2016. Outlier Analysis (2nd. ed.). Springer Publishing Company, Incorporated.

Fritz, Heinrich & García-Escudero, Luis & Mayo, Agustin. (2012). tclust: An R Package for a Trimming Approach to Cluster Analysis. Journal of Statistical Software. 47. 10.18637/jss.v047.i12.



¿Cómo citar este documento?

Detección de anomalías: trimmed k-means por Joaquín Amat Rodrigo, disponible con licencia CC BY-NC-SA 4.0 en https://www.cienciadedatos.net/documentos/64_deteccion_anomalias_trimmed_kmeans.html

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

Se permite:

  • Compartir: copiar y redistribuir el material en cualquier medio o formato.

  • Adaptar: remezclar, transformar y crear a partir del material.

Bajo los siguientes términos:

  • Atribución: Debes otorgar el crédito adecuado, proporcionar un enlace a la licencia e indicar si se realizaron cambios. Puedes hacerlo de cualquier manera razonable, pero no de una forma que sugiera que el licenciante te respalda o respalda tu uso.

  • NoComercial: No puedes utilizar el material para fines comerciales.

  • CompartirIgual: Si remezclas, transformas o creas a partir del material, debes distribuir tus contribuciones bajo la misma licencia que el original.