Determinar la cantidad de clústeres en un conjunto de datos , una cantidad a menudo denominada k como en el algoritmo k -medias , es un problema frecuente en la agrupación de datos y es una cuestión distinta del proceso de resolver realmente el problema de agrupación.
Para una determinada clase de algoritmos de agrupamiento (en particular, k -medias, k -medoides y algoritmo de expectativa-maximización ), existe un parámetro comúnmente denominado k que especifica la cantidad de clústeres que se deben detectar. Otros algoritmos, como DBSCAN y OPTICS, no requieren la especificación de este parámetro; el agrupamiento jerárquico evita el problema por completo.
La elección correcta de k es a menudo ambigua, con interpretaciones que dependen de la forma y la 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 ). Intuitivamente, entonces, 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 asignando 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, debe elegirse 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 añadir 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 añadirán mucha información (explicarán mucha varianza), pero en algún punto la ganancia marginal caerá, dando un ángulo en el gráfico. El número de conglomerados 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 fiable. 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 fiable. [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 suena simple y directa, otros métodos (como se detalla a continuación) dan mejores resultados.
En estadística y minería de datos , la agrupación en clústeres de X-medias es una variación de la agrupación en clústeres de k-medias que refina las asignaciones de clústeres al intentar repetidamente la subdivisión y mantener 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). [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 verosimilitud para el modelo de agrupamiento. Por ejemplo: el modelo k -medias es "casi" un modelo de mezcla gaussiana y se puede construir una verosimilitud para el modelo de mezcla gaussiana y, por lo tanto, también determinar los valores del criterio de información. [6]
La teoría de distorsión de la tasa se ha aplicado a la elección de k , llamada el método de "salto", que determina el número de clústeres 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-means, para todos los valores de k entre 1 y n , y calculando la distorsión (descrita a continuación) del agrupamiento resultante. 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 entonces opciones razonables para k , y el salto más grande representa la mejor opción.
La distorsión de una agrupación 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 de mezcla de G componentes con covarianza común , Γ . Si sea un conjunto de K centros de agrupación, 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 de Mahalanobis promedio por dimensión entre X y el centro del grupo más cercano . Debido a que la minimización sobre todos los conjuntos posibles de centros de grupos es prohibitivamente compleja, la distorsión se calcula en la práctica generando un conjunto de centros de grupos 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) Inicialice una lista D, de tamaño n+1 Sea D[0] = 0 Para k = 1 ... n: Clúster X con k clústeres (por ejemplo, con k-medias) Sea d = Distorsión del agrupamiento resultante D[k] = d^(-Y) Define J(i) = D[i] - D[i-1] Devuelve el 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 la distorsión de la velocidad. Sea que los datos X tengan una distribución gaussiana única, arbitrariamente p -dimensional , y sea fijo , para algún α mayor que cero. Entonces la distorsión de una agrupación de K agrupamientos en el límite cuando p tiende a infinito es . Se puede ver que asintóticamente, la distorsión de una agrupación a la potencia es proporcional a , que por definición es aproximadamente el número de agrupamientos K . En otras palabras, para una única distribución gaussiana, aumentar K más allá del número real de agrupamientos, 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 G distribuciones gaussianas p -dimensionales con covarianza común. Entonces, para cualquier K fija menor que G , la distorsión de una agrupación cuando p tiende a 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 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 tiende a infinito siendo igual a . Correspondientemente, existe la misma relación proporcional entre la distorsión transformada y el número de agrupaciones, K .
Al combinar 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 hace uso de estos comportamientos para identificar el valor más probable para el número real de clústeres.
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 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, conocido como el método de línea discontinua. El método de línea discontinua identifica el punto de salto en el gráfico 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 discontinua es más robusto que el método de salto en 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 de mezcla generales.
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 cuán cercana está a los datos dentro de su conglomerado y cuán vagamente está a los datos del conglomerado vecino, es decir, el conglomerado cuya distancia promedio desde el dato es más baja. [8] Una silueta cercana a 1 implica que el dato está en un conglomerado apropiado, mientras que una silueta cercana a -1 implica que el dato está en el conglomerado incorrecto. Las técnicas de optimización como los algoritmos genéticos son útiles para determinar el número de conglomerados que da lugar a la silueta más grande. [9] También es posible volver a escalar los datos de tal manera que la silueta tenga más probabilidades de maximizarse en el número correcto de conglomerados. [10]
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. Cada una de las partes se reserva a su vez como conjunto de prueba, se calcula un modelo de agrupamiento en los otros v − 1 conjuntos de entrenamiento y se calcula el valor de la función objetivo (por ejemplo, la suma de las distancias al cuadrado a los centroides para k -medias) para el conjunto de prueba. Estos valores v se calculan y promedian para cada número alternativo de clústeres, y el número de clúster seleccionado de modo que un mayor aumento en el número de clústeres conduzca solo a una pequeña reducción en la función objetivo. [ cita requerida ]
Al agrupar bases de datos de texto con el coeficiente de cobertura en una colección de documentos definida por una matriz de documentos por términos D (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 agrupaciones se puede estimar aproximadamente mediante la fórmula donde t es el número de entradas distintas de cero en D. Nótese que en D cada fila y cada columna debe contener al menos un elemento distinto de cero. [11]
La matriz de 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 mayor dimensión, 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 esta manera, la matriz kernel puede analizarse para encontrar el número óptimo de clústeres. [12] El método procede mediante la descomposición en valores propios de la matriz kernel. 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 clústeres 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 el número de clústeres a partir de los datos.
Robert Tibshirani , Guenther Walther y Trevor Hastie propusieron estimar el número de conglomerados en un conjunto de datos a través de la estadística de brecha. [13] La estadística de brecha, basada en fundamentos teóricos, mide qué tan lejos está la suma de cuadrados dentro del conglomerado agrupada alrededor de los centros del conglomerado de la suma de cuadrados esperada bajo la distribución de referencia nula de datos. El valor esperado se estima simulando datos de referencia nulos de características de los datos originales, pero sin ningún conglomerado en ellos. El número óptimo de conglomerados se estima entonces 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 indicarnos que no existe ningún valor de k para el cual exista una buena agrupación, pero la confiabilidad depende de cuán 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 conjuntos de datos difíciles con, por ejemplo, atributos no 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 cluster [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}}: CS1 maint: varios nombres: lista de autores ( enlace ){{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )Véase especialmente la Figura 14 y el apéndice.