detección de valores atípicos en la minería de datos

Question

tengo unas cuantas series de preguntas con respecto a la detección de valores atípicos:

1. Podemos encontrar valores atípicos utilizando k-medias y esto es un buen enfoque?

2. ¿Hay algún algoritmo de agrupamiento que no acepte ninguna entrada del usuario?

3. ¿Se puede utilizar la máquina de vectores de soporte o cualquier otro algoritmo de aprendizaje supervisado para la detección de valores atípicos?

4. ¿Cuáles son los pros y los contras de cada enfoque?

Answer 1

me limito a lo que creo que es esencial para dar algunas pistas sobre todas sus preguntas, ya que este es el tema de una gran cantidad de libros de texto y que probablemente podría abordarse mejor en preguntas separadas.

1. yo no usaría k-medias para detectar valores atípicos en un conjunto de datos multivariados, por la sencilla razón de que el algoritmo k-medias no está construido para tal fin: Siempre va a terminar con una solución que minimice la suma total de cuadrados dentro del clúster (y, por lo tanto, maximiza el SS entre clusters porque la varianza total es fija), y el valor atípico (s) no necesariamente definirá su propio clúster. Consideremos el siguiente ejemplo en I:

   set.seed(123) 
   sim.xy <- function(n, mean, sd) cbind(rnorm(n, mean[1], sd[1]), 
                rnorm(n, mean[2],sd[2])) 
   # generate three clouds of points, well separated in the 2D plane 
   xy <- rbind(sim.xy(100, c(0,0), c(.2,.2)), 
         sim.xy(100, c(2.5,0), c(.4,.2)), 
         sim.xy(100, c(1.25,.5), c(.3,.2))) 
   xy[1,] <- c(0,2)  # convert 1st obs. to an outlying value 
   km3 <- kmeans(xy, 3) # ask for three clusters 
   km4 <- kmeans(xy, 4) # ask for four clusters 
   

   Como puede verse en la siguiente figura, el valor periférica no se recupera como tal: siempre pertenecerá a uno de los otros grupos.

   

   Una posibilidad, sin embargo, sería el uso de un enfoque de dos etapas donde uno de eliminar puntos extremales (define aquí como vector lejos de sus centroides de grupo) de una manera iterativa, tal como se describe en el siguiente papel: Improving K-Means by Outlier Removal (Hautamäki, et al.).

   Esto tiene cierta semejanza con lo que se hace en estudios genéticos para detectar y eliminar individuos que exhiben error de genotipado, o individuos que son hermanos/gemelos (o cuando queremos identificar la subestructura de la población), mientras que solo queremos mantener la relación individuos; en este caso, usamos escalamiento multidimensional (que es equivalente a PCA, hasta una constante para los dos primeros ejes) y eliminamos las observaciones por encima o por debajo de 6 SD en cualquiera de, digamos, los 10 o 20 ejes superiores (consulte, por ejemplo, Population Structure and Eigenanalysis Patterson et al., PLoS Genetics 2006 2 (12)).

   Una alternativa común es utilizar ordenado robustos distancias de Mahalanobis que se pueden representar (en una parcela QQ) contra los cuantiles esperados de una distribución Chi-cuadrado, como se explica en el siguiente documento:

   R.G. Garrett (1989). The chi-square plot: a tools for multivariate outlier recognition. Journal of Geochemical Exploration 32 (1/3): 319-341.

   (Está disponible en el paquete mvoutlier R.)

2. Depende de lo que se llama a la entrada del usuario.Interpreto su pregunta como si algún algoritmo puede procesar automáticamente una matriz de distancia o datos sin procesar y detenerse en una cantidad óptima de conglomerados. Si este es el caso, y para cualquier algoritmo de partición basado en la distancia, entonces puede usar cualquiera de los índices de validez disponibles para el análisis de clúster; una buena descripción se da en

   Handl, J., Knowles, J., and Kell, D.B. (2005). Computational cluster validation in post-genomic data analysis. Bioinformática 21 (15): 3201-3212.

   que discutí en Cross Validated. Por ejemplo, puede ejecutar varias instancias del algoritmo en diferentes muestras aleatorias (usando bootstrap) de los datos, para un rango de números de clúster (por ejemplo, k = 1 a 20) y seleccionar k según los criterios optimizados que se consideraron (promedio ancho de la silueta, correlación cophenetic, etc.); puede ser completamente automatizado, sin necesidad de la intervención del usuario.

   Existen otras formas de agrupación, basadas en la densidad (los conglomerados se consideran regiones donde los objetos son inusualmente comunes) o la distribución (los conglomerados son conjuntos de objetos que siguen una distribución de probabilidad determinada). La creación de clústeres basada en modelos, como se implementa en Mclust, por ejemplo, permite identificar clústeres en un conjunto de datos multivariados al abarcar un rango de forma para la matriz de varianza-covarianza para un número variable de clústeres y elegir el mejor modelo de acuerdo con el BIC criterio.

3. Este es un tema candente en la clasificación, y algunos estudios se centraron en SVM para detectar valores atípicos, especialmente cuando están mal clasificados. Una simple consulta de Google devolverá muchos resultados, p. Support Vector Machine for Outlier Detection in Breast Cancer Survivability Prediction por Thongkam et al. (Notas de conferencia en informática 2008 4977/2008 99-109; este artículo incluye comparación con métodos de conjunto). La idea más básica es usar un SVM de una clase para capturar la estructura principal de los datos ajustando una distribución multivariante (por ejemplo, gaussiana); objetos que en o fuera del límite podrían considerarse como valores atípicos potenciales. (En cierto sentido, la agrupación basada en la densidad funcionaría igual de bien como la definición de un valor atípico es más directa dada una distribución esperada).

   Otros enfoques para el aprendizaje supervisado, supervisado o no supervisado se encuentran fácilmente en Google, por ejemplo

   • Hodge, V.J. y Austin, J. A Survey of Outlier Detection Methodologies.
   • Vinueza, A. y Grudic, G.Z. Unsupervised Outlier Detection and Semi-Supervised Learning.
   • Escalante, H.J. A Comparison of Outlier Detection Algorithms for Machine Learning.

   
   Un tema relacionado es anomaly detection, sobre el que se encuentra una gran cantidad de papeles.

4. que realmente merece una nueva (y probablemente más centrado) pregunta :-)

Answer 2

1. k-medias es bastante sensible al ruido en el conjunto de datos. Funciona mejor cuando elimina los valores atípicos de antemano.

2. No. Cualquier algoritmo de análisis de clúster que afirma estar libre de parámetros suele estar muy restringido y, a menudo, tiene parámetros ocultos; un parámetro común es la función de distancia, por ejemplo.Cualquier algoritmo de análisis de clúster flexible aceptará al menos una función de distancia personalizada.

3. Los clasificadores de una clase son un enfoque popular de aprendizaje automático para la detección de valores atípicos. Sin embargo, los enfoques supervisados ​​no siempre son apropiados para detectar objetos _previously_unseen_. Además, pueden sobredimensionarse cuando los datos ya contienen valores atípicos.

4. Cada enfoque tiene sus pros y sus contras, es por eso que existen. En una configuración real, tendrá que probar la mayoría de ellos para ver qué funciona para sus datos y configuración. Es la razón por la detección de valores atípicos se llama conocimiento descubrimiento - tienes que explorar si quieres descubrir algo nuevo ...

Answer 3

1) ¿Podemos encontrar valores atípicos utilizando k-medias, es una ¿buen enfoque?

Los enfoques basados ​​en clúster son óptimos para encontrar clústeres y se pueden usar para detectar valores atípicos como subproductos. En los procesos de agrupamiento, los valores atípicos pueden afectar las ubicaciones de los centros de clúster, incluso agregándose como un microgrupo. Estas características hacen que los enfoques basados ​​en clúster sean inviables para bases de datos complicadas.

2) ¿Hay algún algoritmo de agrupamiento que no acepte ninguna entrada del usuario?

Tal vez puede obtener algunos conocimientos valiosos sobre este tema: Dirichlet Process Clustering

algoritmo basado en la agrupación de Dirichlet puede determinar de forma adaptativa el número de grupos de acuerdo a la distribución de los datos de observación.

3) ¿Podemos usar la máquina de vectores de soporte o cualquier otro algoritmo de aprendizaje supervisado para la detección de valores atípicos?

Cualquier algoritmo de aprendizaje supervisado necesita suficientes datos de entrenamiento etiquetados para construir clasificadores. Sin embargo, un conjunto de datos de entrenamiento equilibrado no siempre está disponible para problemas del mundo real, como la detección de intrusiones, diagnósticos médicos. De acuerdo con la definición de Hawkins Outlier ("Identificación de valores atípicos", Chapman y Hall, Londres, 1980), el número de datos normales es mucho mayor que el de los valores atípicos. La mayoría de los algoritmos de aprendizaje supervisado no pueden lograr un clasificador eficiente en el conjunto de datos desequilibrado anterior.

4) ¿Cuáles son los pros y los contras de cada enfoque?

En las últimas décadas, la investigación sobre la detección de valores atípicos varía desde el cálculo global hasta el análisis local, y las descripciones de valores atípicos varían desde las interpretaciones binarias hasta las representaciones probabilísticas. Según las hipótesis de los modelos de detección de valores atípicos, los algoritmos de detección de valores atípicos se pueden dividir en cuatro tipos: algoritmos basados ​​en estadística, algoritmos basados ​​en clúster, algoritmos basados ​​en vecindario más cercano y algoritmos basados ​​en clasificador. Hay varios estudios valiosos sobre detección de valores atípicos:

• Hodge, V. y Austin, J. "Un estudio de metodologías de detección de valores atípicos", Journal of Artificial Intelligence Review, 2004.

• Chandola, V . y Banerjee, A. y Kumar, V. "Detección de valores atípicos: una encuesta", Encuestas de informática de ACM, 2007.

Answer 4

Es posible que desee echar un vistazo a ELKI data mining framework. Supuestamente es la colección más grande de algoritmos de minería de datos de detección de valores atípicos. Es un software de código abierto, implementado en Java e incluye más de 20 algoritmos de detección de valores atípicos. Vea el list of available algorithms.

Tenga en cuenta que la mayoría de estos algoritmos son que no se basan en la agrupación. Muchos algoritmos de agrupamiento (en particular, k-means) intentarán clonar instancias "no importa qué". Solo unos pocos algoritmos de agrupación (por ejemplo, DBSCAN) realmente consideran el caso de que tal vez no todas las instancias pertenecen a los conglomerados. Entonces, para algunos algoritmos, los valores atípicos realmente previenen ¡una buena agrupación!