Problema de coincidencia centróide

Question

Para un conjunto de datos $D$, hemos estándar de oro de los centroides de decir $c_1, c_2, \cdots, c_n$. Ahora si ejecutamos k-means el algoritmo en $D$ con la entrada de $n$, obtenemos k-means centroide $k_1, k_2, \cdots, k_n$.

Yo sólo quería saber, ¿hay algún algoritmo/heurística para que coincida con los centroides entre el $k_i$ $c_j$ donde $i, j= 1, \cdots, n$ (asignación de uno a Uno entre el $k$'s y $c$'s)

Traté de calcular los pares de la distancia entre el $k_p$$c_j,\; j= 1, \cdots, n$, y el partido de $k_p$ $c_r$cuando la distancia entre ellos es mínima. Pero en este caso $k_p$ $k_q$ son asignados a $c_r$, que no es necesario.

Answer 1

Debido a que K-means minimiza las desviaciones, un buen criterio es minimizar la suma de los cuadrados de las distancias entre los pares de puntos.

Esta es una integral (0/1) de programación lineal. Específicamente, la vinculación puede ser especificado por una matriz de $\Lambda = (\lambda_{ij})$ donde $\lambda_{ij} = 1$ si $c_i$ está vinculado con $k_j$ $\lambda_{ij}=0$ lo contrario. Buscamos minimizar

$$\sum_{i,j}\lambda_{ij}|c_i - k_j|^2$$

sujeto a las restricciones (que cumplir el uno-a-uno de emparejamiento)

$$\sum_{j}\lambda_{ij}=1$$ $$\sum_{i}\lambda_{ij}=1$$ $$\lambda_{ij} \in\{0,1\}.$$

Siempre los centroides no más de un par de cientos, esto se resolvió rápidamente. (Las matrices que intervienen en la configuración del problema de la rapidez de escape de RAM con más de un par de cientos de centroides, debido a que la escala de $O(n^3)$, y entonces usted podría tener que ser un poco más fastidioso con la programación.) Por ejemplo, Mathematica 8 `LinearProgramming' función no tiene medibles tiempo con menos de $n=20$ centroides, aumentando a unos 5 segundos con 400 centroides.

Por medio de segmentos de línea para mostrar las vinculaciones, esta cifra representa una solución óptima con $n=20$ normal bivariante de los centroides de $c_i$ e independiente bivariante normal de K-means soluciones de $k_i$.

Answer 2

El problema que está tratando de resolver es un problema de coincidencia de costes mínimos, específicamente el problema de minimizar la funcionalidad

Unesdoc.unesco.org unesdoc.unesco.org

Donde$F(\pi) = \sum_i \|c_i - k_{\pi(i)}\|^2 $ está sobre todas las permutaciones en$\pi$.

Esto puede ser resuelto por el algoritmo húngaro (que es un método primal-dual disfrazado) y toma$S_n$ time.

Answer 3

Suena como que usted puede ser que desee considerar el uso de/escritura de una función de energía. Más aquí: http://en.wikipedia.org/wiki/Optimization_%28mathematics%29#Multi-objective_optimization

Supongo que si el número de k centroides es "pequeño" puede ejecutar una función de distancia para todos los c k emparejamientos y seleccione el conjunto que minimiza la distancia total como la "mejor" solución.
Espero que ayude -
Perry