¿Cómo saber si los datos están "agrupados" lo suficiente como para que los algoritmos de agrupamiento produzcan resultados significativos?

¿Cómo podría saber si sus datos (de alta dimensión) exhiben suficiente agrupación para que los resultados de kmeans u otro algoritmo de agrupación sean realmente significativos?

Para el algoritmo k-means en particular, ¿qué grado de reducción en la varianza dentro del clúster debería haber para que los resultados de la agrupación sean significativos (y no espurios)?

¿Debería ser evidente la agrupación cuando se traza una forma de datos dimensionalmente reducida, y los resultados de kmeans (u otros métodos) no tienen sentido si la agrupación no se puede visualizar?

Acerca de k-means específicamente, puede usar las estadísticas Gap. Básicamente, la idea es calcular una bondad de medida de agrupación basada en la dispersión promedio en comparación con una distribución de referencia para un número creciente de agrupaciones. Se puede encontrar más información en el documento original:

Tibshirani, R., Walther, G. y Hastie, T. (2001). Estimación del número de clústeres en un conjunto de datos a través de la estadística de brecha . JR Statist. Soc. B, 63 (2): 411-423.

La respuesta que proporcioné a una pregunta relacionada destaca otros índices de validez generales que podrían usarse para verificar si un conjunto de datos dado exhibe algún tipo de estructura.

Cuando no tiene idea de lo que esperaría encontrar si solo hubiera ruido, un buen enfoque es utilizar un nuevo muestreo y estudiar la estabilidad de los clústeres. En otras palabras, vuelva a muestrear sus datos (mediante bootstrap o agregando un pequeño ruido) y calcule la "cercanía" de las particiones resultantes, según lo medido por las similitudes de Jaccard . En resumen, permite estimar la frecuencia con la que se recuperaron grupos similares en los datos. Este método está fácilmente disponible en el paquete fpc R como clusterboot(). Toma como entrada datos sin procesar o una matriz de distancia, y permite aplicar una amplia gama de métodos de agrupamiento (métodos jerárquicos, k-medios, difusos). El método se discute en las referencias vinculadas:

Hennig, C. (2007) Evaluación basada en el clúster de la estabilidad del clúster . Estadística computacional y análisis de datos , 52, 258-271.

Hennig, C. (2008) Punto de disolución y solidez del aislamiento: criterios de solidez para los métodos generales de análisis de conglomerados . Journal of Multivariate Analysis , 99, 1154-1176.

A continuación se muestra una pequeña demostración con el algoritmo k-means.

sim.xy <- function(n, mean, sd) cbind(rnorm(n, mean[1], sd[1]),
rnorm(n, mean[2],sd[2]))
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)))
library(fpc)
km.boot <- clusterboot(xy, B=20, bootmethod="boot",
                       clustermethod=kmeansCBI,
                       krange=3, seed=15555)

Los resultados son bastante positivos en este conjunto de datos artificial (y bien estructurado) ya que ninguno de los tres grupos ( krange) se disolvió en las muestras, y la similitud promedio de Jaccard clúster es> 0.95 para todos los grupos.

A continuación se muestran los resultados de las 20 muestras de bootstrap. Como puede verse, las unidades estadísticas tienden a permanecer agrupadas en el mismo grupo, con pocas excepciones para las observaciones intermedias.

Puede extender esta idea a cualquier índice de validez, por supuesto: elija una nueva serie de observaciones por bootstrap (con reemplazo), calcule su estadística (por ejemplo, ancho de silueta, correlación cophenetic, gamma de Hubert, dentro de la suma de cuadrados) para un rango de números de clúster (p. ej., 2 a 10), repita 100 o 500 veces y observe el diagrama de caja de su estadística en función del número de clúster.

Esto es lo que obtengo con el mismo conjunto de datos simulado, pero usando el agrupamiento jerárquico de Ward y considerando la correlación cophenetic (que evalúa qué tan bien se reproduce la información de distancia en las particiones resultantes) y el ancho de la silueta (una medida combinada que evalúa la homogeneidad intra-cluster e inter separación de racimos).

La correlación cophenetic varía de 0.6267 a 0.7511 con un valor medio de 0.7031 (500 muestras de bootstrap). El ancho de la silueta parece ser máximo cuando consideramos 3 grupos (mediana 0.8408, rango 0.7371-0.8769).

Una forma de visualizar rápidamente si los datos de alta dimensión exhiben suficiente agrupación es usar la incrustación de vecinos estocásticos distribuidos en t ( SNE ). Proyecta los datos en un espacio de baja dimensión (por ejemplo, 2D, 3D) y hace un trabajo bastante bueno para mantener la estructura del clúster, si lo hay.

Por ejemplo, conjunto de datos MNIST :

Olivetti enfrenta el conjunto de datos:

Seguramente, la capacidad de discernir visualmente los grupos en un número de dimensiones gravable es un criterio dudoso para la utilidad de un algoritmo de agrupación, especialmente si esta reducción de la dimensión se realiza independientemente del agrupamiento en sí (es decir, en un vano intento de averiguar si la agrupación funcionará).

De hecho, los métodos de agrupación tienen su mayor valor para encontrar los grupos donde el ojo / mente humano no puede ver los grupos.

La respuesta simple es: agrupe, luego averigüe si funcionó (con cualquiera de los criterios que le interesan, consulte también la respuesta de @ Jeff).

¿Cuándo son los resultados significativos de todos modos? En particular k-significa resultados?

El hecho es que k-means optimiza una cierta estadística matemática. No hay "significativo" asociado con esto.

En particular, en datos de alta dimensión, la primera pregunta debería ser: ¿la distancia euclidiana sigue siendo significativa ? Si no, no use k-means. La distancia euclidiana es significativa en el mundo físico, pero rápidamente pierde significado cuando tienes otros datos. En particular, cuando transforma artificialmente datos en un espacio vectorial, ¿hay alguna razón por la que deba ser euclidiana?

Si toma el conjunto de datos clásico "antiguo fiel" y ejecuta k-means en él sin normalización, pero con una distancia euclidiana pura, ya no tiene sentido. EM, que de hecho utiliza alguna forma de distancia de Mahalanobis "cluster local", funcionará mucho mejor. En particular, se adapta a los ejes que tienen escalas muy diferentes.

Por cierto, una fortaleza clave de k-means es que en realidad solo dividirá los datos, sin importar cómo se vean. Puede usar k-means para dividir el ruido uniforme en k grupos . Se puede afirmar que, obviamente, los clústeres k-means no son significativos. O uno puede aceptar esto como: el usuario quería particionar los datos para minimizar las distancias al cuadrado euclidianas, sin tener que exigir que los grupos sean "significativos".

Acabo de comenzar a usar algoritmos de agrupamiento recientemente, por lo que espero que alguien más conocedor pueda proporcionar una respuesta más completa, pero aquí hay algunas ideas:

'Significativo', como estoy seguro de que es consciente, es muy subjetivo. Por lo tanto, si la agrupación es lo suficientemente buena depende completamente de por qué necesita agruparse en primer lugar. Si está tratando de predecir la pertenencia al grupo, es probable que cualquier agrupación sea mejor que el azar (y no peor), por lo que los resultados deberían ser significativos hasta cierto punto.

Si desea saber qué tan confiable es este agrupamiento, necesita alguna métrica para compararlo. Si tiene un conjunto de entidades con membresías conocidas, puede usar un análisis discriminante para ver qué tan buenas fueron las predicciones. Si no tiene un conjunto de entidades con membresías conocidas, tendrá que saber qué variación es típica de los grupos en su campo. Es probable que los atributos físicos de las entidades con categorías rígidas tengan una varianza en el grupo mucho más baja que los datos psicométricos en humanos, pero eso no necesariamente hace que el agrupamiento sea "peor".

Su segunda pregunta alude a '¿Qué valor de k debería elegir?' Nuevamente, no hay una respuesta difícil aquí. En ausencia de un conjunto de categorías a priori, es probable que desee minimizar el número de clústeres y al mismo tiempo minimizar la varianza promedio del clúster. Un enfoque simple podría ser graficar 'número de grupos' versus 'varianza promedio de grupo' y buscar el "codo", donde agregar más grupos no tiene un impacto significativo en la variación de su grupo.

No diría que los resultados de k-means no tienen sentido si no se pueden visualizar, pero ciertamente es atractivo cuando los grupos son visualmente aparentes. Esto, nuevamente, solo lleva a la pregunta: ¿por qué necesita hacer clustering y qué tan confiable debe ser? En última instancia, esta es una pregunta que debe responder en función de cómo utilizará los datos.

Para saber si una agrupación es significativa, puede ejecutar un algoritmo para contar la cantidad de agrupaciones y ver si genera algo mayor que 1.

Como dijo chl, un algoritmo de conteo de conglomerados es el algoritmo de estadística de brecha. Aproximadamente, esto calcula la varianza total del clúster dados sus datos reales, y lo compara con la varianza total del clúster de datos que no deberían tener ningún clúster (por ejemplo, un conjunto de datos formado al muestrear uniformemente dentro de los mismos límites que sus datos reales). El número de grupos entonces se elige para ser el que da el mayor "espacio" entre estas dos variaciones de grupo.$k$$k$

Otro algoritmo es el algoritmo de fuerza de predicción (que es similar al resto de la respuesta de chl). Aproximadamente, esto realiza un grupo de agrupaciones de k-medias y calcula la proporción de puntos que permanecen en el mismo grupo. se elige entonces como el más pequeño que da una proporción más alta que algún umbral (por ejemplo, un umbral de 0.8).$k$$k$