Determinar la cantidad de clústeres en un conjunto de datos

Determinar el número de agrupaciones en un conjunto de datos , una cantidad a menudo etiquetada como k como en el algoritmo de k- medias , es un problema frecuente en la agrupación de datos y es un tema distinto del proceso de resolver realmente el problema de agrupación.

Para una cierta clase de algoritmos de agrupamiento (en particular k -medias, k -medoides y algoritmo de maximización de expectativas ), existe un parámetro comúnmente denominado k que especifica el número de grupos a detectar. Otros algoritmos como el algoritmo DBSCAN y OPTICS no requieren la especificación de este parámetro; la agrupación jerárquica evita el problema por completo.

La elección correcta de k suele ser ambigua, con interpretaciones que dependen de la forma y escala de la distribución de puntos en un conjunto de datos y la resolución de agrupación deseada por el usuario. Además, aumentar k sin penalización siempre reducirá la cantidad de error en el agrupamiento resultante, hasta el caso extremo de error cero si cada punto de datos se considera su propio grupo (es decir, cuando k es igual al número de puntos de datos, n ). Entonces, intuitivamente, la elección óptima de k logrará un equilibrio entre la máxima compresión de los datos utilizando un solo grupo y la máxima precisión al asignar cada punto de datos a su propio grupo . Si un valor apropiado de kno es evidente a partir del conocimiento previo de las propiedades del conjunto de datos, debe elegirse de alguna manera. Hay varias categorías de métodos para tomar esta decisión.

El método del codo

Artículo principal: método del codo (agrupamiento)

Varianza explicada. El "codo" está indicado por el círculo rojo. Por tanto, el número de conglomerados elegidos debería ser 4.

El método del codo analiza el porcentaje de varianza explicado como una función del número de conglomerados: se debe elegir un número de conglomerados para que la adición de otro conglomerado no proporcione un modelo mucho mejor de los datos. Más precisamente, si se grafica el porcentaje de varianza explicado por los conglomerados contra el número de conglomerados, los primeros conglomerados agregarán mucha información (explican mucha varianza), pero en algún punto la ganancia marginal caerá, dando un ángulo en el grafico. El número de grupos se elige en este punto, de ahí el "criterio del codo". Este "codo" no siempre se puede identificar sin ambigüedades, ^[1] haciendo que este método sea muy subjetivo y poco confiable. El porcentaje de varianza explicada es la relación entre la varianza entre grupos y la varianza total,también conocido comoF-test . Una ligera variación de este método traza la curvatura de la varianza dentro del grupo. ^[2]

El método se remonta a la especulación de Robert L. Thorndike en 1953. ^[3]

Agrupación X-significa

En estadística y minería de datos , la agrupación de X-medias es una variación de la agrupación de k-medias que refina las asignaciones de agrupaciones al intentar repetidamente la subdivisión y mantener las mejores divisiones resultantes, hasta un criterio como el criterio de información de Akaike (AIC) o el criterio de información bayesiano. (BIC) se alcanza. ^[4]

Enfoque basado en criterios de información

Otro conjunto de métodos para determinar el número de conglomerados son los criterios de información, como el criterio de información de Akaike (AIC), el criterio de información bayesiano (BIC) o el criterio de información de desviación (DIC), si es posible hacer una función de verosimilitud para el modelo de agrupamiento. Por ejemplo: el modelo de k- medias es "casi" un modelo de mezcla gaussiana y se puede construir una probabilidad para el modelo de mezcla gaussiana y así también determinar valores de criterio de información. ^[5]

Un enfoque teórico de la información

La teoría de la distorsión de la tasa se ha aplicado a la elección de k denominado método de "salto", que determina el número de grupos que maximiza la eficiencia y minimiza el error según los estándares de la teoría de la información . ^[6] La estrategia del algoritmo es generar una curva de distorsión para los datos de entrada ejecutando un algoritmo de agrupamiento estándar como k-medias para todos los valores de k entre 1 y n , y calculando la distorsión (descrita a continuación) del resultado agrupamiento. Luego, la curva de distorsión se transforma mediante una potencia negativa elegida en función de la dimensionalidad de los datos. Los saltos en los valores resultantes significan elecciones razonables para k, donde el salto más grande representa la mejor opción.

La distorsión de un agrupamiento de algunos datos de entrada se define formalmente de la siguiente manera: Sea el conjunto de datos modelado como una variable aleatoria p -dimensional , X , que consiste en una distribución mixta de componentes G con covarianza común , Γ . Si dejamos que sea ​​un conjunto de K centros de conglomerados, con el centro más cercano a una muestra dada de X , entonces la distorsión promedio mínima por dimensión al ajustar los K centros a los datos es:${\displaystyle c_{1}\ldots c_{K}}$${\displaystyle c_{X}}$

${\displaystyle d_{K}={\frac {1}{p}}\min _{c_{1}\ldots c_{K}}{E[(X-c_{X})^{T}\Gamma ^{-1}(X-c_{X})]}}$

Esta es también la media distancia de Mahalanobis por dimensión entre X y el conjunto de centros de los conglomerados C . Debido a que la minimización de todos los conjuntos posibles de centros de conglomerados es prohibitivamente compleja, la distorsión se calcula en la práctica generando un conjunto de centros de conglomerados utilizando un algoritmo de agrupamiento estándar y calculando la distorsión utilizando el resultado. El pseudocódigo para el método de salto con un conjunto de entrada de puntos de datos p- dimensionales X es:

JumpMethod (X): Sea Y = (p / 2) Iniciar una lista D, de tamaño n + 1 Sea D [0] = 0 Para k = 1 ... n: Clúster X con k clústeres (p. Ej., Con k-medias) Sea d = distorsión de la agrupación resultante D [k] = d ^ (- Y) Defina J (i) = D [i] - D [i-1] Devuelve el k entre 1 y n que maximiza J (k)

La elección del poder de transformación está motivada por un razonamiento asintótico que utiliza los resultados de la teoría de la distorsión de la tasa. Sea que los datos X tengan una distribución gaussiana única, arbitrariamente p- dimensional , y sea fija , para algún α mayor que cero. Entonces, la distorsión de una agrupación de K agrupaciones en el límite cuando p llega al infinito es . Se puede observar que asintóticamente, la distorsión de un clustering a la potencia es proporcional a , que por definición es aproximadamente el número de clusters K${\displaystyle Y=(p/2)}$${\displaystyle K=\lfloor \alpha ^{p}\rfloor }$${\displaystyle \alpha ^{-2}}$${\displaystyle (-p/2)}$${\displaystyle \alpha ^{p}}$. En otras palabras, para una sola distribución gaussiana, aumentar K más allá del número real de grupos, que debería ser uno, provoca un crecimiento lineal en la distorsión. Este comportamiento es importante en el caso general de una mezcla de múltiples componentes de distribución.

Sea X una mezcla de distribuciones gaussianas G p -dimensionales con covarianza común. Entonces, para cualquier K fijo menor que G , la distorsión de un agrupamiento cuando p llega al infinito es infinita. Intuitivamente, esto significa que una agrupación de menos del número correcto de agrupaciones no puede describir datos de dimensiones asintóticamente altas, lo que hace que la distorsión aumente sin límite. Si, como se describió anteriormente, K se convierte en una función creciente de p , es decir, se logra el mismo resultado que el anterior, con el valor de la distorsión en el límite cuando p va al infinito siendo igual a${\displaystyle K=\lfloor \alpha ^{p}\rfloor }$${\displaystyle \alpha ^{-2}}$. Correspondientemente, existe la misma relación proporcional entre la distorsión transformado y el número de grupos, K .

Poner los resultados anteriores en conjunto, se puede ver que para valores suficientemente altos de p , la distorsión transformado es aproximadamente cero para K < G , entonces salta de repente y comienza aumentando linealmente para K ≥ G . El algoritmo de salto para elegir K hace uso de estos comportamientos para identificar el valor más probable para el número real de conglomerados.${\displaystyle d_{K}^{-p/2}}$

Aunque el soporte matemático del método se da en términos de resultados asintóticos, se ha verificado empíricamente que el algoritmo funciona bien en una variedad de conjuntos de datos con una dimensionalidad razonable. Además del método de salto localizado descrito anteriormente, existe un segundo algoritmo para elegir K utilizando los mismos valores de distorsión transformados conocidos como método de línea discontinua. El método de línea discontinua identifica el punto de salto en la gráfica de la distorsión transformada haciendo un ajuste de línea de error de mínimos cuadrados simple de dos segmentos de línea, que en teoría caerán a lo largo del eje x para K < G , y a lo largo de la fase linealmente creciente de la gráfica de distorsión transformada paraK ≥ G . El método de línea discontinua es más robusto que el método de salto en el sentido de que su decisión es global en lugar de local, pero también se basa en la suposición de componentes de la mezcla gaussiana, mientras que el método de salto es completamente no paramétrico y se ha demostrado que es viable para distribuciones generales de mezcla.

El método de la silueta

Artículo principal: Silueta (agrupación)

La silueta promedio de los datos es otro criterio útil para evaluar el número natural de conglomerados. La silueta de una instancia de datos es una medida de qué tan estrechamente se corresponde con los datos dentro de su grupo y qué tan poco se corresponde con los datos del grupo vecino, es decir, el grupo cuya distancia promedio desde el datum es más baja. ^[7] Una silueta cercana a 1 implica que el datum está en un grupo apropiado, mientras que una silueta cercana a -1 implica que el datum está en el grupo incorrecto. Las técnicas de optimización, como los algoritmos genéticos, son útiles para determinar el número de grupos que dan lugar a la silueta más grande. ^[8]También es posible volver a escalar los datos de tal manera que es más probable que la silueta se maximice en el número correcto de conglomerados. ^[9]

Validación cruzada

También se puede utilizar el proceso de validación cruzada para analizar el número de clústeres. En este proceso, los datos se dividen en v partes. Luego, cada una de las partes se aparta a su vez como un conjunto de prueba, un modelo de agrupamiento calculado en los otros  conjuntos de entrenamiento v - 1, y el valor de la función objetivo (por ejemplo, la suma de las distancias cuadradas a los centroides para k -medias) calculadas para el conjunto de prueba. Estos valores de v se calculan y promedian para cada número alternativo de conglomerados, y el número de conglomerado se selecciona de tal manera que un aumento adicional en el número de conglomerados conduce solo a una pequeña reducción en la función objetivo. ^[10]

Encontrar el número de agrupaciones en bases de datos de texto

En las bases de datos de texto, una colección de documentos definida por un documento por término D matriz (de tamaño m por n, m: número de documentos, n: número de términos) el número de grupos se puede estimar aproximadamente mediante la siguiente fórmula donde t es el número de entradas distintas de cero en D. Tenga en cuenta que en D cada fila y cada columna deben contener al menos un elemento distinto de cero.^[11]${\displaystyle {\tfrac {mn}{t}}}$

Analizando la matriz del kernel

La matriz del núcleo define la proximidad de la información de entrada. Por ejemplo, en la función de base radial gaussiana, determina el producto escalar de las entradas en un espacio de dimensiones superiores, llamado espacio de características. Se cree que los datos se vuelven más separables linealmente en el espacio de características y, por lo tanto, se pueden aplicar algoritmos lineales a los datos con mayor éxito.

Por tanto, la matriz del núcleo se puede analizar para encontrar el número óptimo de conglomerados. ^[12] El método procede de la descomposición de valores propios de la matriz del núcleo. Luego analizará los autovalores y autovectores para obtener una medida de la compacidad de la distribución de entrada. Finalmente, se dibujará una gráfica, donde el codo de esa gráfica indica el número óptimo de conglomerados en el conjunto de datos. A diferencia de los métodos anteriores, esta técnica no necesita realizar ningún agrupamiento a priori. Encuentra directamente la cantidad de clústeres a partir de los datos.

Referencias

1. Véase, por ejemplo, David J. Ketchen Jr; Christopher L. Shook (1996). "La aplicación del análisis de conglomerados en la investigación de gestión estratégica: un análisis y una crítica" . Revista de Gestión Estratégica . 17 (6): 441–458. doi : 10.1002 / (SICI) 1097-0266 (199606) 17: 6 <441 :: AID-SMJ819> 3.0.CO; 2-G .^{[ enlace muerto ]}
2. Ver, por ejemplo, Figura 6 en
   • Cyril Goutte, Peter Toft, Egill Rostrup, Finn Årup Nielsen, Lars Kai Hansen (marzo de 1999). "Sobre la agrupación de series de tiempo de fMRI". NeuroImage . 9 (3): 298–310. doi : 10.1006 / nimg.1998.0391 . PMID  10075900 .
3. Robert L. Thorndike (diciembre de 1953). "¿Quién pertenece a la familia?". Psychometrika . 18 (4): 267–276. doi : 10.1007 / BF02289263 .
4. D. Pelleg; AW Moore. X-means: Ampliación de K-means con una estimación eficiente del número de conglomerados (PDF) . Actas de la Decimoséptima Conferencia Internacional sobre Aprendizaje Automático (ICML 2000) . Consultado el 16 de agosto de 2016 .
5. Cyril Goutte, Lars Kai Hansen , Matthew G. Liptrot y Egill Rostrup (2001). "Agrupación de espacio de características para metaanálisis de resonancia magnética funcional" . Cartografía del cerebro humano . 13 (3): 165–183. doi : 10.1002 / hbm.1031 . PMC 6871985 . PMID 11376501 . Archivado desde el original el 17 de diciembre de 2012.   ver especialmente la Figura 14 y el apéndice.
6. Catherine A. Sugar ; Gareth M. James (2003). "Encontrar el número de conglomerados en un conjunto de datos: un enfoque teórico de la información". Revista de la Asociación Estadounidense de Estadística . 98 (enero): 750–763. doi : 10.1198 / 016214503000000666 .
7. Peter J. Rousseuw (1987). "Siluetas: una ayuda gráfica para la interpretación y validación del análisis de conglomerados" . Matemática Computacional y Aplicada . 20 : 53–65. doi : 10.1016 / 0377-0427 (87) 90125-7 .
8. R. Lleti; MC Ortiz; LA Sarabia; MS Sánchez (2004). "Selección de variables para k -means Cluster Analysis utilizando un algoritmo genético que optimiza las siluetas". Analytica Chimica Acta . 515 : 87-100. doi : 10.1016 / j.aca.2003.12.020 .
9. RC de Amorim y C. Hennig (2015). "Recuperación del número de clústeres en conjuntos de datos con características de ruido utilizando factores de cambio de escala de características". Ciencias de la información . 324 : 126-145. arXiv : 1602.06989 . doi : 10.1016 / j.ins.2015.06.039 .
10. Consulte, por ejemplo, "Encontrar el número correcto de clústeres en k-Means y Clustering EM: v-Fold Cross-Validation" . Libro de texto de estadística electrónica . StatSoft. 2010 . Consultado el 3 de mayo de 2010 .
11. Can, F .; Ozkarahan, EA (1990). "Conceptos y efectividad de la metodología de agrupamiento basado en coeficientes de cobertura para bases de datos de texto". Transacciones ACM en sistemas de bases de datos . 15 (4): 483. doi : 10.1145 / 99935.99938 . hdl : 2374.MIA / 246 . especialmente consulte la Sección 2.7.
12. Honarkhah, M; Caers, J (2010). "Simulación estocástica de patrones utilizando el modelado de patrones basado en la distancia". Geociencias matemáticas . 42 (5): 487–517. doi : 10.1007 / s11004-010-9276-7 .

Lectura adicional

• Ralf Wagner , Sören W. Scholz, Reinhold Decker (2005): El número de clústeres en la segmentación del mercado, en: Daniel Baier, Reinhold Decker; Lars Schmidt-Thieme (Eds.): Análisis de datos y apoyo a la toma de decisiones, Berlín, Springer, 157-176.

Enlaces externos

• Clustergram - gráfica de diagnóstico de clústeres - para diagnóstico visual de elegir el número de ( k ) clústeres ( código R )
• Ocho métodos para determinar un valor óptimo de k para el análisis de k -medias - Respuesta en stackoverflow que contiene el código R para varios métodos de calcular un valor óptimo de k para el análisis de conglomerados de k -medias
• Partición y agrupación en clústeres: ¿cuántas clases? Documento de seminario gratuito disponible en el servidor HAL, id = hal-02124947: se presentan dos métodos no paramétricos (se proporcionan referencias bibliográficas), uno para variables numéricas (funciona con una matriz de distancias, no necesariamente euclidianas), uno para variables categóricas ( partición óptima; funciona también con diferencias firmadas).