Implementación de k-means con matriz de distancia personalizada en la entrada

14

¿Alguien puede señalarme una implementación de k-means (sería mejor si en matlab) que puede tomar la matriz de distancia en la entrada? La implementación estándar de matlab necesita la matriz de observación en la entrada y no es posible cambiar a medida la medida de similitud.

clustering matlab k-means Eugenio
fuente
2
Podría intentar generar datos sin procesar correspondientes a su matriz de distancias euclidianas e ingresarlos en K-Means. Un enfoque alternativo fácil podría ser utilizar el método Ward de agrupamiento jerárquico de la matriz: K-Means y Ward comparten una ideología similar de lo que es un grupo.
ttnphns
además de ttnphns y Not Durrett, puede encontrar ¿Está bien usar la distancia de Manhattan con el enlace entre grupos de Ward en la agrupación jerárquica? interesante
steffen
No es Matlab, pero la página de python bajo es-es-posible-especificar-su-propia-distancia-función-usando-scikits-learn-k-means puede usar cualquiera de las 20 métricas impares en scipy.spatial. distancia.
denis

Respuestas:

13

Dado que k-means necesita poder encontrar los medios de diferentes subconjuntos de los puntos que desea agrupar, no tiene sentido pedir una versión de k-means que tome una matriz de distancia como entrada.

Podrías probar k-medoides en su lugar. Hay algunas implementaciones de matlab disponibles.

NF
fuente
1
Hola gracias por la respuesta en lugar de dar directamente la matriz de distancia, ¿sería posible dar como entrada una métrica de distancia personalizada? El punto es que tengo que comparar dos métodos de agrupamiento y, dado que en el segundo uso una matriz de similitud personalizada, quiero usar el mismo enfoque con kmeans para obtener una comparación justa.
Eugenio
2
ELKI le permite usar funciones de distancia arbitrarias con k-means. Tenga en cuenta que el algoritmo puede no converger. K-means está realmente diseñado para la distancia euclidiana al cuadrado (suma de cuadrados). Con otras distancias, es posible que la media ya no se optimice y, auge, el algoritmo finalmente no convergerá. En serio, considera usar k-medoides. En realidad, fue escrito para permitir el uso de la idea de k-means con distancias arbitrarias .
HA SALIDO - Anony-Mousse
También hay pyclustering una biblioteca python / C ++ que le permite proporcionar una función métrica personalizada: github.com/annoviko/pyclustering/issues/417
CpILL
7

Puede convertir su matriz de distancias en datos sin procesar e ingresarlos a la agrupación de K-Means. Los pasos serían los siguientes:

1) Las distancias entre tus N puntos deben ser cuadradas euclidianas. Realice el " doble centrado " de la matriz: reste la media de la fila de cada elemento; en el resultado, resta la media de la columna de cada elemento; en el resultado, agregue la media de la matriz a cada elemento; divide entre menos 2. La matriz que tienes ahora es la matriz SSCP (suma de cuadrados y productos cruzados) entre tus puntos en donde el origen se coloca en el centro geométrico de la nube de N puntos. (Lea la explicación del doble centrado aquí .)

2) Realice PCA (análisis de componentes principales) en esa matriz y obtenga la matriz de carga de componentes NxN . Es probable que algunas de las últimas columnas sean todas 0, así que córtelas. Con lo que se queda ahora es en realidad los puntajes de los componentes principales, las coordenadas de sus N puntos sobre los componentes principales que pasan, como ejes, a través de su nube. Estos datos pueden tratarse como datos sin procesar adecuados para la entrada K-Means.

PD: si sus distancias no son geométricamente correctas al cuadrado euclidianas, puede encontrar problemas: la matriz SSCP puede no ser positiva (semi) definida. Este problema se puede resolver de varias maneras pero con pérdida de precisión.

ttnphns
fuente
¡Gracias por tu respuesta! En realidad, no tengo una matriz de distancias reales, sino una matriz de similitud (0 ... 1) entre objetos, y las similitudes no se calculan exactamente utilizando distancias euclidianas, sino con un algoritmo personalizado que tiene en cuenta los datos en bruto, pero no en el forma estándar Supongo que en este caso no puedo aplicar su procedimiento, ¿estoy en lo cierto?
Eugenio
Aún puede, después de convertir similitudes en distancias. Esto último probablemente no sea verdadero euclidiano (y, por lo tanto, el SSCP tendrá algunos valores propios negativos); luego intente agregar una pequeña constante a las distancias hasta que el SSCP pierda neg. Eig. También existen otras formas de solucionar el problema. Y recuerde que duplica la matriz central de distancias cuadradas .
ttnphns 01 de
PD Y por cierto. Si su matriz tiene similitudes, entonces, bueno, es aún mejor. Simplemente lo trata como la matriz SSCP de la que estaba hablando y hace PCA con él. Aún así, el problema de los posibles valores propios negativos sigue siendo.
ttnphns 01 de
@ttnphns, siento que me falta su explicación para el paso 1. La matriz de distancia X(digamos N * N) va a ser simétrica, de modo colMeans(X) =rowMeans(X) y una vez que se resta medios de fila o col: Y=X-rowMeans(X), mean(Y)es 0.
Zhubarb
1
@Zhubarb, cuando digo You could turn your matrix of distances into raw data(puntos 1 y 2) me refiero, esencialmente, al escalamiento multidimensional (MDS) de Torgerson , en el que el doble centrado es el paso inicial. Busque en este sitio (y también en Google) sobre ese procedimiento. "Doble centrado" es la conversión de distancias (al cuadrado) en la matriz de producto escalar correspondiente definida sobre el origen puesto en el centroide de la nube de los puntos.
ttnphns
3

Consulte este artículo, escrito por uno de mis conocidos;)

http://arxiv.org/abs/1304.6899

Se trata de una implementación generalizada de k-means, que toma una matriz de distancia arbitraria como entrada. Puede ser cualquier matriz simétrica no negativa con una diagonal cero. Tenga en cuenta que puede no dar resultados razonables para matrices de distancia extrañas. El programa está escrito en C #.

El código fuente se puede obtener visitando el enlace de arriba, luego haciendo clic en Otros formatos, luego haciendo clic en Descargar fuente. Entonces obtendrá un .tar.gz que contiene Program.cs. Alternativamente, el código fuente también se puede copiar del PDF.

szali
fuente
3

Puede usar la Biblioteca de Java Machine Learning. Tienen una implementación de K-Means. Uno de los constructores acepta tres argumentos.

  1. Valor K.
  2. Un objeto de eso es una instancia de la clase DistanceMeasure .
  3. Número de iteraciones.

Uno puede extender fácilmente la clase DistanceMeasure para lograr el resultado deseado. La idea es devolver valores de una matriz de distancia personalizada en el método de medida (Instancia x, Instancia y) de esta clase.

K-Means está garantizado para converger asumiendo ciertas propiedades de la métrica de distancia. La distancia euclidiana, la distancia de Manhattan u otras métricas estándar satisfacen estos supuestos. Dado que una métrica de distancia personalizada puede no satisfacer estos supuestos, el constructor tiene un tercer parámetro que especifica el número de iteraciones que se ejecutarán para construir el clúster.

Chaitanya Shivade
fuente