Determinar el número de clusters en un conjunto de datos , una cantidad a menudo denominada k como en el algoritmo k -means , es un problema frecuente en el clustering de datos y es una cuestión distinta del proceso de resolución real del problema de clustering.
Para una determinada 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 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 es a menudo 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 agrupamiento 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, de manera intuitiva, la elección óptima de k logrará un equilibrio entre la compresión máxima de los datos usando un solo grupo y la máxima precisión al asignar cada punto de datos a su propio grupo . Si un valor apropiado de k no es evidente a partir del conocimiento previo de las propiedades del conjunto de datos, se debe elegir de alguna manera. Hay varias categorías de métodos para tomar esta decisión.
El método del codo analiza el porcentaje de varianza explicada en función del número de conglomerados: se debe elegir un número de conglomerados de modo que agregar otro conglomerado no proporcione un modelado mucho mejor de los datos. Más precisamente, si se grafica el porcentaje de varianza explicada por los conglomerados frente al número de conglomerados, los primeros conglomerados agregarán mucha información (explicarán mucha varianza), pero en algún punto la ganancia marginal disminuirá, dando un ángulo en el grafico. El número de grupos se elige en este punto, de ahí el "criterio del codo". En la mayoría de los conjuntos de datos, este "codo" es ambiguo, [1] lo que hace que este método sea subjetivo y poco confiable. Debido a que la escala de los ejes es arbitraria, el concepto de ángulo no está bien definido, e incluso en datos aleatorios uniformes, la curva produce un "codo", lo que hace que el método sea poco confiable. [2] El porcentaje de varianza explicada es la relación entre la varianza entre grupos y la varianza total, también conocida como prueba F. Una ligera variación de este método traza la curvatura de la varianza dentro del grupo. [3]
El método se remonta a la especulación de Robert L. Thorndike en 1953. [4] Si bien la idea del método del codo parece simple y directa, otros métodos (como se detallan a continuación) dan mejores resultados.
En estadística y minería de datos , la agrupación de medias X es una variación de la agrupación de medias k que refina las asignaciones de grupos intentando repetidamente la subdivisión y manteniendo las mejores divisiones resultantes, hasta que se alcanza un criterio como el criterio de información de Akaike (AIC) o el criterio de información bayesiano. (BIC) se alcanza. [5]
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 crear una función de probabilidad para El modelo de agrupamiento. Por ejemplo: el modelo k -means es "casi" un modelo de mezcla gaussiana y se puede construir una probabilidad para el modelo de mezcla gaussiana y así determinar también los valores de los criterios de información. [6]
La teoría de la distorsión de la tasa se ha aplicado para elegir k, llamado 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 . [7] 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 elección.
La distorsión de una agrupación de algunos datos de entrada se define formalmente de la siguiente manera: modelemos el conjunto de datos como una variable aleatoria p -dimensional , X , que consiste en una distribución mixta de G componentes 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:
Esta es también la distancia promedio de Mahalanobis por dimensión entre X y el centro del cúmulo más cercano . Debido a que la minimización de todos los conjuntos posibles de centros de conglomerados es prohibitivamente compleja, en la práctica la distorsión se calcula 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) Inicie una lista D, de tamaño n+1 Sea D[0] = 0 Para k = 1 ... n: Grupo X con k grupos (p. ej., con k-medias) Sea d = Distorsión del agrupamiento resultante D[k] = d^(-Y) Definir J(i) = D[i] - D[i-1] Devuelve la k entre 1 y n que maximiza J(k)
La elección de la potencia de transformación está motivada por un razonamiento asintótico que utiliza resultados de la teoría de distorsión de velocidad. Sea que los datos X tengan una distribución gaussiana única, arbitrariamente p -dimensional , y sean fijos , para algún α mayor que cero. Entonces, la distorsión de un agrupamiento de K grupos en el límite cuando p llega al infinito es . Se puede ver 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 . En otras palabras, para una distribución gaussiana única, aumentar K más allá del número real de conglomerados, que debería ser uno, provoca un crecimiento lineal de 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 una agrupación cuando p tiende al infinito es infinita. Intuitivamente, esto significa que una agrupación de menos del número correcto de agrupaciones no puede describir datos asintóticamente de alta dimensión, lo que provoca 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 antes, siendo el valor de la distorsión en el límite cuando p llega al infinito igual a . En consecuencia, existe la misma relación proporcional entre la distorsión transformada y el número de grupos , K.
Al juntar los resultados anteriores, se puede ver que para valores suficientemente altos de p , la distorsión transformada es aproximadamente cero para K < G , luego salta repentinamente y comienza a aumentar linealmente para K ≥ G. El algoritmo de salto para elegir K utiliza estos comportamientos para identificar el valor más probable para el número real de grupos.
Aunque el respaldo matemático del método se proporciona 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 usando los mismos valores de distorsión transformados conocido 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. del gráfico de distorsión transformada para K ≥ G . El método de línea quebrada 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 el supuesto de componentes de 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 mezclas.
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 coincide con los datos dentro de su grupo y qué tan vagamente coincide con los datos del grupo vecino, es decir, el grupo cuya distancia promedio desde el dato es menor. [8] 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. [9] También es posible volver a escalar los datos de tal manera que sea más probable que la silueta se maximice en el número correcto de grupos. [10]
También se puede utilizar el proceso de validación cruzada para analizar el número de conglomerados. En este proceso, los datos se dividen en v partes. Luego, cada una de las partes se reserva 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 al cuadrado a los centroides para k -medias) calculado para el conjunto de prueba. Estos valores de v se calculan y se promedian para cada número alternativo de conglomerados, y el número de conglomerados se selecciona de modo que un mayor aumento en el número de conglomerados conduzca sólo a una pequeña reducción en la función objetivo. [ cita necesaria ]
Cuando se agrupan bases de datos de texto con el coeficiente de cobertura en una colección de documentos definida por una matriz D de documento por término (de tamaño m×n, donde m es el número de documentos y n es el número de términos), el número de grupos puede ser aproximadamente estimado mediante la 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 debe contener al menos un elemento distinto de cero. [11]
La matriz kernel 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.
De este modo, la matriz del núcleo se puede analizar para encontrar el número óptimo de conglomerados. [12] El método procede mediante la descomposición de valores propios de la matriz del núcleo. Luego analizará los valores propios y los vectores propios para obtener una medida de la compacidad de la distribución de entrada. Finalmente, se dibujará un gráfico, donde el codo de ese gráfico indica el número óptimo de grupos en el conjunto de datos. A diferencia de los métodos anteriores, esta técnica no necesita realizar ninguna agrupación a priori. Encuentra directamente la cantidad de grupos a partir de los datos.
Robert Tibshirani , Guenther Walther y Trevor Hastie propusieron estimar el número de conglomerados en un conjunto de datos mediante la estadística de brecha. [13] Las estadísticas de brecha, basadas en fundamentos teóricos, miden qué tan lejos está la suma de cuadrados agrupados dentro del grupo alrededor de los centros del grupo de la suma de cuadrados esperada bajo la distribución de datos de referencia nula. El valor esperado se estima simulando datos de referencia nulos de características de los datos originales, pero que carecen de grupos en ellos. Luego, el número óptimo de conglomerados se estima como el valor de k para el cual la suma de cuadrados observada cae más por debajo de la referencia nula.
A diferencia de muchos métodos anteriores, las estadísticas de brecha pueden decirnos que no hay ningún valor de k para el cual exista una buena agrupación, pero la confiabilidad depende de qué tan plausible sea la distribución nula supuesta (por ejemplo, una distribución uniforme) en los datos dados. Esto tiende a funcionar bien en entornos sintéticos, pero no puede manejar bien conjuntos de datos difíciles con, por ejemplo, atributos poco informativos porque supone que todos los atributos son igualmente importantes. [14]
Las estadísticas de brecha se implementan como la función clusGap en el paquete de clúster [15] en R.
![{\displaystyle d_{K}={\frac {1}{p}}\min _{c_{1}\ldots c_{K}}{E[(X-c_{X})^{T}\Gamma ^{-1}(X-c_{X})]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/131448aa992f7a6d18db47af3656cf1db46bcd60)
{{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace ){{cite journal}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )ver especialmente la Figura 14 y el apéndice.