¿Hay casos en los que no hay una k óptima en k-medias?

11

Esto ha estado dentro de mi mente durante al menos unas pocas horas. Estaba tratando de encontrar una k óptima para la salida del algoritmo k-means (con una métrica de similitud de coseno ), así que terminé trazando la distorsión en función del número de grupos. Mi conjunto de datos es una colección de 800 documentos en un espacio de 600 dimensiones.

Por lo que entiendo, encontrar el punto de rodilla o el punto de codo en esta curva debería indicarme al menos aproximadamente el número de grupos en los que necesito poner mis datos. Puse el gráfico a continuación. El punto en el que se dibujó la línea vertical roja se obtuvo utilizando la segunda prueba máxima de derivada . Después de hacer todo esto, me quedé atrapado en algo mucho más simple: ¿qué me dice este gráfico sobre el conjunto de datos?

¿Me dice que no vale la pena agruparlos y que mis documentos carecen de estructura o que necesito establecer una k muy alta? Sin embargo, una cosa extraña es que incluso con k baja, veo documentos similares agrupados, así que no estoy seguro de por qué estoy obteniendo esta curva. ¿Alguna idea?

ingrese la descripción de la imagen aquí

machine-learning clustering k-means Leyenda
fuente
2
Lo que honestamente no entiendo es cómo fue capaz de emplear el agrupamiento k-means con entrada de matriz de proximidad (¡y eso es coseno!). La agrupación K-means necesita datos sin procesar (objetos X variables) de entrada y opera internamente a distancia euclidiana.
ttnphns
2
@ttnphns: Espero haber entendido su punto, pero que yo sepa, podemos usar cualquier métrica de distancia con k-means, ¿no? Estoy haciendo esto en Python pero parece que incluso hay una biblioteca disponible para R: cran.r-project.org/web/packages/skmeans/index.html La entrada no fue una matriz de proximidad, sino que se terms x documentobtuvo después de realizar un vector singular. descomposición. Corrígeme si me equivoco.
Leyenda
La agrupación esférica de k-medias , basada en la medida del coseno, es nueva para mí, debo admitirlo. Espero leer más sobre eso algún día.
ttnphns
@ttnphns: Gracias por regresar. Solo quería asegurarme de que no estaba usando manzanas y naranjas juntas :)
Leyenda
K-means no modificado solo es sensible para -Norms. Porque calcula vectores medios y esa no es una estimación ML adecuada para otras funciones de distancia. Lp
HA SALIDO - Anony-Mousse

Respuestas:

12

En la mayoría de las situaciones, habría pensado que tal trama básicamente significa que no hay estructura de clúster en los datos. Sin embargo, la agrupación en dimensiones muy altas como esta es complicada ya que para la métrica de distancia euclidiana todas las distancias tienden a ser iguales a medida que aumenta el número de dimensiones. Vea esta página de Wikipedia para referencias a algunos documentos sobre este tema. En resumen, el problema puede ser la alta dimensionalidad del conjunto de datos.

Esto es esencialmente "la maldición de la dimensionalidad", vea también esta página de Wikipedia.

Un artículo que puede ser de interés es Sanguinetti, G., "Reducción de la dimensionalidad de los conjuntos de datos agrupados", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30 no. 3, págs. 535-540, marzo de 2008 ( www ). Que es un poco como una versión no supervisada de LDA que busca un espacio de baja dimensión que enfatiza la estructura del clúster. ¿Quizás podría usar eso como un método de extracción de características antes de realizar k-means?

Dikran Marsupial
fuente
Ups, lo siento. Debería haber mencionado que estoy usando la similitud de coseno.
Leyenda
Creo que es muy probable que la maldición de la dimensionalidad también se aplique a la similitud del coseno. Básicamente dice que necesita (en el peor de los casos) exponencialmente más patrones para definir una distribución a medida que aumenta el número de dimensiones. Al agrupar, lo que está haciendo efectivamente es identificar distribuciones que representan subpoblaciones, por lo que la agrupación en grandes dimensiones probablemente sea intrínsecamente complicada.
Dikran Marsupial
+1 Gracias por el enlace. Lo revisaré y volveré. Apliqué SVD en mi matriz original antes de aplicar k-means para reducir el número de dimensiones.
Leyenda
3

¿Cómo se usa exactamente la similitud de coseno? ¿Es esto lo que se conoce como medios K esféricos? Su conjunto de datos es bastante pequeño, por lo que trataría de visualizarlo como una red. Para esto es natural usar una similitud (de hecho, por ejemplo, la similitud del coseno o la correlación de Pearson), aplicar un punto de corte (solo considerar las relaciones por encima de cierta similitud) y ver el resultado como una red en, por ejemplo, Cytoscape o BioLayout . Esto puede ser muy útil para tener una idea de los datos. En segundo lugar, calcularía los valores singulares para su matriz de datos, o los valores propios de una matriz adecuadamente transformada y normalizada (una matriz documento-documento obtenida de alguna forma). La estructura del clúster debería (nuevamente) aparecer como un salto en la lista ordenada de valores propios o valores singulares.

micanos
fuente
+1 Gracias por los consejos. No estaba al tanto de Cytoscape. Probaré eso. Y sí, parece que k-medias con similitud de coseno se conoce como k-medias esféricas. Apliqué este k-means después de aplicar SVD y reducir el número de dimensiones. La forma en que reduje el número de dimensiones fue usar la regla de la varianza (seleccione los valores singulares que contribuyen al 95% de la varianza en los datos originales).
Leyenda
Si no le importa, ¿podría señalar un tutorial que explique cómo hacer esto (o al menos algo como esto)? Una vez que genero la matriz, ¿la exporto y luego la importo a Cytoscape y realizo lo que sugirió? Lo que me interesa es saber si Cytoscape tiene métodos integrados para la similitud de coseno o si tengo que calcular previamente algún formato de datos y darlo como entrada.
Leyenda
Cuando trabajo con esos programas, calculo todas las similitudes de pares externamente, filtro por umbral y produzco un archivo con formato <label1> <label2> <similarity>. Cualquiera de los dos debería poder leer esa entrada. En BioLayout tiene que tener un sufijo .txt, creo; en CytoScape use 'importar de la tabla'.
micans
Entendido. Lo haré y volveré pronto. Gracias otra vez.
Leyenda
Perdón por la pregunta tonta, pero he formateado mis datos como <label1> <label2> <similarity> pero no puedo descubrir cómo importarlos exactamente. Hice Archivo-> Importar-> Red de tabla y seleccioné mis columnas de origen y destino. Dejé la interacción como predeterminada. Pero, ¿cómo se supone que importe pesos de borde junto con los bordes? ¿Tienes alguna sugerencia por favor?
Leyenda
2

En general, sí, k-means podría converger en soluciones muy distintas que podrían considerarse inadecuadas. Esto sucede en particular para grupos con formas irregulares.

Para obtener más intuición, también puede probar otro enfoque de visualización: para k-means puede visualizar varias corridas con k-means usando Graphgrams (consulte el paquete de grafos WEKA, mejor obtenido por el administrador de paquetes o aquí . También puede encontrar una introducción y ejemplos encontrado aquí .

Johannes Schneider
fuente
1

Si entiendo la gráfica correctamente, ¿es una gráfica del número de grupos, K en el eje xy la distancia dentro de los grupos en el eje y?

Debido a que su función objetivo K-means es minimizar el WCSS, este gráfico siempre debe estar disminuyendo monotónicamente. A medida que agrega más grupos, la distancia entre los puntos en el grupo siempre disminuirá. Este es el problema fundamental de la selección del modelo, por lo que debe emplear un poco más de sofisticación.

Quizás pruebe la estadística Gap: www-stat.stanford.edu/~tibs/ftp/gap.ps u otros similares.

Además, es posible que K-means no sea la herramienta adecuada para el trabajo. ¿Cuántos grupos esperas encontrar? Usar la regla de varianza para la reducción de dimensionalidad para el agrupamiento no es apropiado. Consulte este documento para cuando proyectar en las primeras PC K-1 es una medida de preprocesamiento adecuada: http://people.csail.mit.edu/gjw/papers/jcss.ps

Puede ver rápidamente si esto es lo correcto al trazar la proyección en los dos primeros componentes principales. Si hay una separación clara, entonces K-means debería estar bien, de lo contrario, debe buscar otra cosa. Quizás K-subespacios u otros métodos de agrupación de subespacios. Ten en cuenta que estos métodos se aplican para la distancia euclidiana. No estoy seguro de cómo esto cambia para el coseno.

bmc
fuente