Presentación de técnicas recientes

Método basado en la proximidad y la densidad

La idea de los métodos basados en la proximidad es modelar los valores atípicos como puntos que están aislados de los datos restantes. Este modelado se puede realizar de tres formas: análisis de conglomerados, análisis basado en densidad o análisis del vecino más cercano (KNN). En análisis de conglomerados y otros métodos basados en la densidad, las regiones densas en los datos se identifican directamente y los valores atípicos se definen como aquellos puntos que no se encuentran en dichas regiones. La principal diferencia entre el análisis de conglomerados y los métodos basados en la densidad es que los primeros segmentan puntos, mientras que los otros segmentan el espacio.

Son métodos que proporcionan un alto nivel de interpretabilidad en cuanto que las regiones de datos dispersas se pueden presentar en términos de combinaciones de los atributos originales. Por ejemplo, los conjuntos de restricciones sobre los atributos originales se pueden presentar como criterios específicos para que los puntos de datos particulares se interpreten como valores atípicos.

Vecinos más cercanos (KNN)

Es una técnica de clasificación no supervisada cuya concepto es muy sencillo. Clasifica a un nuevo miembro a una clase o categoría que ya existe. Lo determina según que sus atributos se parezcan a los casos de una categoría u otra. Se entiende vecindad como similitud debido a que se mide la distancia entre los atributos de cada par de casos. De ahí el nombre. Si es vecino de dos o más categorías diferentes, se asigna al grupo que cuente con más miembros similares.

Suponga los grupos que se presentan en la Figura . Se quiere asignar un nuevo punto, en negro. KNN buscará los k puntos más cercanos a éste para encontrar la clase dominante del grupo. Para garantizar la existencia de una clase dominante, $k$ debe ser un número impar.

$\label{KNN}Esquema del KNN$

Esquema del KNN

En el ejemplo de la Figura se utilizaron las cinco observaciones más cercanas ($K = 5$), para determinar a qué grupo asignar al nuevo individuo.

Hay muchas maneras de medir distancias. Cada manera se adapta de mejor o peor manera al tipo de atributos con que cuentan los individuos o casos. En cualquier caso, se recomienda escalar los atributos antes de aplicarles el algoritmo. Escalar una variable significa transformarla de tal modo que se haga comparable a otras, a pesar de que puedan tener escalas muy diferentes. Por ejemplo, el área de un país y su PIB tienen unidades de medida muy diferentes (miles de $km^2$ y miles de dólares). Ambas se pueden tomar como atributos para medir la distancia de un país con respecto a los demás. Si el valor máximo de una medida es mucho más grande que el de la otra en varios órdenes de magnitud, entonces dicha variable dominará. El escalamiento evita que ocurra.

Una desventaja del procedimiento es que si hay datos faltantes para uno o más individuos, esos individuos los descartará para la comparación. Obliga a asignarle un valor a dichos valores faltantes. Técnicamente se denomina imputarle valores a los datos faltantes.

Local Outlier Factor

El algoritmo LOF usa una idea similar al KNN, pero orientado a detectar datos anómalos. Calcula una puntuación (denominada factor de valor atípico local) que refleja el grado de anomalía de las observaciones. Mide la desviación de la densidad local de un punto con respecto a sus vecinos. La idea es detectar las muestras que tienen una densidad sustancialmente menor que sus vecinas.

En la práctica, la densidad local se obtiene de los k vecinos más cercanos. La puntuación LOF de una observación es igual a la relación entre la densidad local promedio de sus k vecinos más cercanos y su propia densidad local. Se espera que un caso normal tenga una densidad local similar a la de sus vecinos, mientras que los casos anómalos se espera que tengan una densidad local mucho menor.

La fortaleza del algoritmo LOF es que se enfoca en qué tan aislada está la muestra respecto a su vecindario circundante.

Explicación Local Outlier Factor

La distancia alcanzable (reacheable distance en inglés(RD)) entre el punto $A$ y $B$ se calcula como el máximo entre la tercera mayor distancia a $B$ y la distancia $AB$.

Con referencia a los puntos de la Figura , las distancias de $B$ a los restantes puntos son:

Distancia de B a los restantes puntos
coordenadas	distancias
BC	1
BE	4.47
BD	5
BF	5.39
BG	5.83
BA	6.08

La tercera menor distancia a $B$ es BD. Se representa en la Figura mediante un círculo verde. Por tanto,

$RD_{AB} = max(\textit{k-ésima dist} (B), dist(A,B))$ = max(5, 6.08) = 6.08, siendo $k = 3$.

Se lee: si el punto cae dentro del radio de la tercera menor distancia al punto $B$ se considera como distancia alcanzable la tercera mayor distancia a $B$, en otro caso se contempla la distancia al punto $B$.

Obsérvese que $RD_{BA}$ es diferente a $RD_{AB}$. No son simétricas. En la Figura se presenta la tercera menor distancia a $A$ mediante un círculo rojo. Se trata de la distancia de $A$ a $C$. En consecuencia, $RD_{BA} = max(\textit{k-ésima dist} (A), dist(B,A))$ = max(6.32, 6.08) = 6.32, siendo $k = 3$.

Distancia de A a los restantes puntos
coordenadas	distancias
AD	5.83
AB	6.08
AC	6.32
AE	6.4
AG	6.71
AF	7.21

$\label{fig:coor}Esquema de la distancia alcanzable de LOF$

Esquema de la distancia alcanzable de LOF

La distancia promedio alcanzable al punto $A$ ($\overline{RD}_A$) es el promedio de las distancias alcanzables de los tres vecinos más cercanos a $A$:

\[\overline{RD}_A=\frac{RD_{AD}+RD_{AB}+RD_{AC}}{3}\]

Si esta medida es muy grande significa que los vecinos de $A$ están muy alejados, en otras palabras hay una baja densidad alrededor de $A$, o en otras palabras es baja la densidad local alcanzable:

\[LRD_A = \frac{1}{\overline{RD}_A}\]

Densidad promedio local. La distancia alcanzable de $A$ también puede calcularse en las vecindades de $A$, es decir, calcular $LRD_D$, $LRD_B$ y $LRD_C$ y calcular la densidad promedio de los vecinos (DPL) de $A$:

\[DPL_A=\frac{LRD_D + LRD_B + LRD_C}{3}\]

El factor de Outlier Local es el cociente entre el promedio de las densidades locales de los vecinos de $A$ sobre la densidad local del punto $A$:

\[LOF_A = \frac{\frac{1}{3}(DPL_D + DPL_B + DPL_C)}{DPL_A}\]

Interpretación LOF: a continuación se muestra algunos valores del índice LOF:

$\label{LOF}Ejemplo resultado de LOF$

Ejemplo resultado de LOF

La costumbre lleva a considerar anómalos a valores de LOF por encima de $1.5$ ó $2$. Cada problema debe definir cuál es su umbral adecuado.

En R de utiliza la librería Rlof.

Se utilizan los datos simulados.

clf <- Rlof::lof(data = X, k = 20)
y_pred <- as.numeric(clf <= 2)
n_errors <- sum(y_pred != etiqueta)

color <- rep('steelblue', dim(X)[1]-n_outliers)
color <- c(color, rep('red', n_outliers))
plot(x = X[,1], y = X[,2], pch = 19, size = 1, col = color, xlab = 'X', ylab = 'Y')
symbols(x = X[clf > 2, 1], y = X[clf > 2, 2], circles = clf[clf > 2], inches = 0.3, ann = F, fg = 'red', add = TRUE)
legend(x = 2, y = 4, legend = c('No outlier', 'Outlier simulado'), fill=c('steelblue', 'red'), cex = 0.6)

$\label{lof}Resultado del LOF sobre la simulación$

Resultado del LOF sobre la simulación

El error de predicción puede ser porque coincidió el número aleatorio outlier con los inliers, o por números aleatorios inliers muy apartados de la media. La matriz de confusión presenta esos errores:

Usualmente, como regla empírica, se considera que los valores con un LOF mayor a 1.5 son casos anómalos aunque esto depende mucho del valor de k (número de vecinos). Se verá un ejemplo sobre el conjunto de datos Iris:

$\label{iris_lof1}Dataset Iris con un puntaje lof > 2, con k = 2$

Dataset Iris con un puntaje lof > 2, con k = 2

$\label{iris_lof2}Dataset Iris con un puntaje lof > 2, con k = 5$

Dataset Iris con un puntaje lof > 2, con k = 5

$\label{iris_lof3}Dataset Iris con un puntaje lof > 2, con k = 15$

Dataset Iris con un puntaje lof > 2, con k = 15

Método basado en árboles de decisión

$\label{fig:arbol}Árbol$

Árbol

Es una técnica previa al Machine Learning. Se utilizaba para estratificar variables en grupos lo más homogéneos posibles. Estratificación entendida en términos de muestreo. Lo que se busca es encontrar valores de corte en una ó mas variables explicativas de tal modo que la variable de interés quede dividida en grupos (estratos) lo más homogéneos posibles.

Es una técnica no supervisada para pronosticar el valor asignándole el promedio de dicho grupo o para clasificar la ubicación de la variable de interés en alguno de los grupos.

Para problemas en que se desea asignar el promedio del grupo, la técnica determina para cada variable una sucesión de puntos que divida la base en dos particiones ($P_1\text{ y }P_2$) y determina en cuál es menor la suma del cuadrado de los errores (SCE): \[SCE = \sum_{i \in P_1}(y_i - \bar{y}_1)^2 + \sum_{i \in P_2}(y_i - \bar{y}_2)^2\]

En la Figura , de los diferentes cortes, probablemente el tercero es el que genere la menor SCE.

$\label{fig:cortes}Puntos de corte para la partición$

Puntos de corte para la partición

Se realiza tal selección para cada una de las variables predictoras y se elige para la primera partición la variable que obtenga el menor valor de SCE. Recursivamente se vuelve a realizar tal algoritmo para cada partición ($P_1\text{ y }P_2$) volviendo a particionar cada rama. Esto quiere decir que vuelve a utilizar variables que ya han sido elegidas para una partición anterior. Se trata de una técnica computacionalmente intensa, pero veloz.

$\label{fig:split}Esquema de funcionamiento de un árbol$

Esquema de funcionamiento de un árbol

La Figura representa el proceso. El primer corte se realizó sobre la variable X1. El segundo corte se realzó sobre la partición de la derecha respecto a la variable x2. El proceso puede continuar hasta que sólo haya un elemento en cada grupo.

A medida se profundiza un árbol se tiende al sobreajuste. Éste se limita fijando criterios acerca del número mínimo de nodos (hojas) por rama o la máxima profundidad.

En general, si no hay demasiadas variables respecto a los recursos computacionales disponibles, se permite crecer al árbol completamente y luego se poda (prune) con el objeto de hacer más sencillo el modelo. La sencillez o parsimonia se denomina, en este contexto, nivel de pureza. Al ser más sencillo es más eficiente, disminuirá el sobreajuste y no perderá eficacia.

En problemas de clasificación lo único que cambia es el criterio con que se subdivide el árbol. Un árbol tiene mayor pureza si cada partición tiene una mayor proporción de nodos de una de las clases o categorías en las que se están clasificando las variables.

La poda de un árbol utiliza la técnica de regularización, consistente en una penalización asociada al costo y/o complejidad del árbol. La complejidad se refiere al número de nodos terminales. A menor número, menos complejo. \[SCE_{\text{Complexity Parameter}} = SCE + (\alpha)(\text{número de nodos terminales})\]

A menor penalización, mayor complejidad, y viceversa.

Para seleccionar la mejor poda se evalúan los datos para una sucesión de diferentes valores del parámetro de complejidad ($\alpha$ ó CP).

Los árboles tienen la ventaja de que es entendible el resultado, se pueden identificar las variables más importantes para la clasificación o regresión y maneja sin problemas los missing data. Los ignora, pero utiliza la información de las restantes variables de las que sí se tiene información. Y maneja indistintamente variables numéricas, densas o disgregadas, y categóricas.

Se presenta una ligera desventaja si hay variables muy correlacionadas. Si hay dos predictores muy correlacionados, la selección de uno de estos dos para la partición es como si se realizara al azar ya que la diferencia se deberá a diferencias aleatorias en los datos de entrenamiento. Si se eliminara de la data una de las dos variables, la otra podría ser seleccionada dos veces, en dos ramas distintas, realzando su importancia relativa, lo cual tal vez no ocurriría si están presentes ambas. También puede ser desventajoso el hecho de que variables con mayor cardinalidad en el número de diferentes valores son más favorecidos que aquellas con relativamente pocos valores distintos.

$\label{fig:desventaja}Desventaje del árbol$

Desventaje del árbol

Obsérvese que el espacio de partición de la data es rectangular. Los árboles pueden dar resultados menos óptimos que otras técnicas. Y alterando levemente los datos, el árbol resultante puede llegar a ser sustancialmente diferente. Por esa razón surgieron las técnicas de ensamble de árboles, que promedian los resultados de multitud de árboles con el objeto de obtener resultados estables y que han probado obtener resultados incluso mejores que otras técnicas.

Isolation Forest

Isolation Forest es un modelo basado en árboles que se presta para ser utilizado en datos no etiquetados cuando la tasa de contaminación (la proporción de datos anómalos observados) es conocida o puede estimarse de manera confiable.

$\label{fig:arbol2}Árbol aislado$

Árbol aislado

Para aislar un dato se selecciona aleatoriamente una característica y luego se selecciona aleatoriamente un valor de separación[^Gráfica tomada de “cubonacci”].

$\label{fig:arbol3}Árbol aislado$

Árbol aislado

Dado que la partición se aplica de nuevo a los resultado se puede representar mediante una estructura de árbol. El número de divisiones necesarias para aislar una muestra es equivalente a la longitud de la ruta desde el nodo raíz hasta el nodo de terminación. En el ejemplo de la Figura bastó con dos procesos de división, pero se podría continuar, como en la Figura .

De lo que se trata es de aislar datos en un conjunto de árboles independientemente unos de otros, cada uno a partir de un conjunto de datos diferente y ensamblar un resultado. Por ello se denomina un ensamble de árboles. Para encontrar árboles diferenciados se construyen submuestras de datos mediante la técnica del bootstrap: un muestreo con repetición del tamaño del conjunto original. Si bien no es intuitivo el método de emsamblaje (bagging en inglés), este método propuesto en 1996 funciona muy bien para muchos tipos de modelos. Obtiene mejora en las predicciones y reduce la varianza de éstas. Luego hubo una mejorá que se denominó Random Forest. Es una mejora frente al paradigma del bagging en el sentido que evita que haya correlación entre árboles. ¿Cómo? Además de muestrear con reemplazo individuos, muestrea variables aleatoriamente sin reemplazo. Si bien el método del Isolation Forest no es el mismo, el principio sí, y por ello se denominó de esta manera.

Para determinar la predicción del Isolation Forest se utiliza el voto de la mayoría (la moda) para problemas de clasificación y el promedio para los problemas de regresión. Puede ser un promedio ponderado.

La partición aleatoria produce trayectorias notablemente más cortas para las anomalías, por lo tanto, cuando un bosque de árboles aleatorios produce colectivamente recorridos más cortos para muestras particulares, es muy probable que lo sean.

$\label{fig:ensamble}Ensamble de árboles$

Ensamble de árboles

Se procede a definir el modelo sobre los mismos datos simulados para el modelo LOF:

X <- data.frame(X)
model <- solitude::isolationForest$new(sample_size = as.integer(nrow(X)/2), num_trees = 500, replace = FALSE, seed = 123)
#predict outliers within dataset
model$fit(dataset = X)

## INFO  [23:49:32.500] Building Isolation Forest ...  
## INFO  [23:49:32.608] done 
## INFO  [23:49:32.626] Computing depth of terminal nodes ...  
## INFO  [23:49:35.559] done 
## INFO  [23:49:35.609] Completed growing isolation forest

X$pred <- model$predict(data = X)
X$outlier <- as.factor(ifelse(X$pred$anomaly_score >= 0.6, 0, 1))
matriz_conf <- table(etiqueta, X$outlier)
names(attr(x = matriz_conf, which = 'dimnames')) <- c('Prediction', 'Reference')
ggplotConfusionMatrix(matriz_conf)

Es importante notar que además de la etiqueta entrega un puntaje. El puntaje se calcula según la siguiente fórmula: $2^{-\frac{prof_i}{E[prof_i]}}$, donde $prof_i$ es la profundidad promedio que tomó el aislar el nodo y $E[prof_i]$ es el valor esperado de dicha profundidad.

En el documento original que describe el algoritmo Isolation Forest, se especifica que, puesto que los valores atípicos son los que tardarán un número de divisiones inferior a la media en quedar aislados y el propósito es sólo atrapar los valores atípicos, los árboles se construyen hasta un cierto límite de altura (correspondiente a la altura de un árbol de búsqueda binaria perfectamente equilibrado ($log_2(n)$), y si hay más de 1 observación/fila presente en un árbol que ya ha alcanzado su límite de altura, cuando una observación caiga en ese nodo, se le sumará la longitud de trayectoria esperada para el tamaño de la muestra de ese árbol para obtener la longitud de trayectoria final: $2(H(n) - 1)$, donde $H(n)$ es el número armónico¹ de n.

Sea ahora el análisis multidimensional:

pregnant	glucose	pressure	triceps	insulin	mass	pedigree	age	diabetes
6	148	72	35	NA	33.6	0.627	50	pos
1	85	66	29	NA	26.6	0.351	31	neg
8	183	64	NA	NA	23.3	0.672	32	pos
1	89	66	23	94	28.1	0.167	21	neg
0	137	40	35	168	43.1	2.288	33	pos
5	116	74	NA	NA	25.6	0.201	30	neg

Este conjunto de datos es originalmente del Instituto Nacional de Diabetes y Enfermedades Digestivas y Renales de EEUU. El objetivo del conjunto de datos es predecir de forma diagnóstica si un paciente tiene diabetes o no, basándose en determinadas medidas de diagnóstico incluidas en el conjunto de datos. Se impusieron varias restricciones a la selección de estas instancias de una base de datos más grande. En particular, todos los pacientes aquí son mujeres de al menos 21 años de edad de origen indio Pima.

Se utilizará para detectar un conjunto de individuos anómalos en sus medidas médicas, independientemente de que tengan diabetes o no.

Obsérvese que hay datos con missing values. Infortunadamente, a diferencia de los árboles de decisión, Isolation Forest requiere sólo casos con datos completos.

pregnant	glucose	pressure	triceps	insulin	mass	pedigree	age
1	89	66	23	94	28.1	0.167	21
0	137	40	35	168	43.1	2.288	33
3	78	50	32	88	31.0	0.248	26
2	197	70	45	543	30.5	0.158	53
1	189	60	23	846	30.1	0.398	59
5	166	72	19	175	25.8	0.587	51

Se ajusta el modelo Isolation Forest.

model <- solitude::isolationForest$new(sample_size = as.integer(nrow(X)/2), num_trees = 500, replace = FALSE, seed = 123)
#predict outliers within dataset
model$fit(dataset = X)

## INFO  [23:49:36.249] Building Isolation Forest ...  
## INFO  [23:49:36.447] done 
## INFO  [23:49:36.448] Computing depth of terminal nodes ...  
## INFO  [23:49:38.851] done 
## INFO  [23:49:38.956] Completed growing isolation forest

X$pred <- model$predict(data = X)
X$outlier <- as.factor(ifelse(X$pred$anomaly_score >= 0.6, 0, 1))

Diagnóstico	Cantidad
Anómalo	33
Normal	359

Todas las variables se usan como predictores. Una gran cantidad de individuos tienen medidas diagnósticas no estándar, ya que el método asume que la normalidad reside en el área de alta densidad multidimensional.

Debido a la dificultad de etiquetar como anomalía un conjunto de datos a gran escala, los métodos totalmente supervisados no son prácticos en escenarios del mundo real. La detección no supervisada de anomalías no requiere datos de entrenamiento etiquetados. Sin embargo, los métodos no supervisados se basan en supuestos sobre la distribución de los datos. Por ejemplo, enfoques basados en la distancia y la densidad, como Local Outlier Factor (LOF) e Isolation Forest, asumen que las normalidades residen en el área de alta densidad, mientras que las anomalías están alejadas del conglomerado normal. Los métodos probabilísticos asumen que las normalidades siguen una distribución específica, por ejemplo, ABOD (Detección de valores atípicos basada en ángulos) y COPOD (Detección de valores atípicos basada en cópulas). Esos métodos no logran manejar características complejas debido a características de alta dimensión y relaciones no lineales sofisticadas.

Los codificadores automáticos están ganando popularidad y se están combinando con clasificadores. Este enfoque puede funcionar muy bien cuando el codificador automático puede aprender una representación latente útil de dimensiones inferiores del espacio de características. Esto permite incluso a los clasificadores simples diferenciar entre las clases de manera mucho más efectiva.

Elegir la métrica correcta es muy importante. Las métricas más comunes utilizadas en la detección de anomalías supervisadas son la precisión, la puntuación F1, el área bajo la curva (AUC) de ROC, la curva de recuperación de precisión, el coeficiente de correlación de Matthews (MCC) y otras. Si confía mucho en la puntuación F1 para su problema de clasificación, es mejor darle un vistazo a MCC, ya que es más sólido que la puntuación F1 porque se calcula directamente a partir de la matriz de confusión; mientras que la puntuación F1 es la media armónica de precisión y recall.

El problema del desbalance entre normales y anómalos se puede simplificar reequilibrando mediante submuestreo, sobremuestreo o un enfoque híbrido. Hay técnicas de muestreo populares como ADASYN (Adaptive synthetic sampling approach), SMOTE (Synthetic minority oversampling technique), KMeans SMOTE y otras.

Las redes neuronales basadas en gráfos pueden ofrecer técnicas que utilizan la estructura de los datos. Los enfoques basados en gráfos utilizan con mayor frecuencia la matriz de adyacencia entre entidades en una red, que se pasa al modelo junto con los atributos de nodo y enlace (edge). Como ejemplo, considere un conjunto de datos transaccionales simple donde tenemos tarjetas de crédito, dispositivos, ubicación y monto. Se puede construir un gráfo donde las tarjetas de crédito y los dispositivos son nodos en la red y existen enlaces si se ha producido una transacción entre una tarjeta de crédito y un dispositivo en particular. También se puede incluir la ubicación como un atributo del nodo. Los gráfos permiten modelar las interdependencias y capturar la naturaleza relacional de las transacciones. Las transacciones individuales pueden mostrar poca o ninguna indicación de ser fraudulentas, pero cuando se consideran dentro de un contexto más amplio, los patrones pueden surgir. Cuando se enmarca el problema de esta manera, se pueden considerar anomalías a nivel de un nodo, un enlace o un subgrafo completo. Es una forma poderosa de abordar el problema. Si se tiene actividad fraudulenta en una red, por ejemplo, que un usuario haya obtenido un grupo de tarjetas de crédito robadas y las está probando para comprobar cuáles funcionan. El patrón será difícil de detectar si solo se consideran las transacciones individualmente, pero si se considera la vecindad inmediata del usuario en el gráfo, se observará que este usuario está asociado a una cantidad desproporcionada de tarjetas de crédito, donde la norma puede ser 2- 3 tarjetas por cliente.

$H(n) = \sum_{k = 1}^n\frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{k}$. Este también es igual a n veces el inverso de la media armónica.↩︎

Análisis de Anomalías con R