Algoritmo de agrupamiento cluster objetos basándose en su relación peso

Question

He a $n$ palabras y su relación peso que me da un $n\times n$ matriz. Yo voy a usar esto para un algoritmo de búsqueda, pero el problema es que necesito clúster de las palabras clave en función de sus pares de la relación. Así que vamos a decir si las palabras clave son {tenis,federer,wimbledon,londres,la policía} y tenemos los siguientes datos de nuestra matriz de pesos:

            tennis  federer  wimbledon  london  police      
tennis        1       0.8       0.6       0.4     0.0
federer       0.8      1        0.65      0.4     0.02
wimbledon     0.6     0.65       1        0.2     0.09
london        0.4     0.4       0.2        1      0.71
police        0.0     0.02      0.09      0.71     1

Necesito un algoritmo para el conjunto de ellos, en 2 grupos : {tenis,federer,wimbledon} {londres,la policía}. ¿Hay algún conocido algoritmo de clústeres de que se puede tratar con tal cosa ? Hice algunas investigaciones, parece que K-means el algoritmo es el más conocido algoritmo se utiliza para la agrupación, pero al parecer K-means no se ajusta a este caso. Les agradecería mucho cualquier ayuda.

Answer 1

Debe alimentar una matriz diferente en k-means clustering, a saber: 1-weights . Algoritmos de agrupamiento requieren palabras similares que corresponden para cerrar puntos en el espacio y su weights son todo lo contrario.

Answer 2

Usted debe utilizar el análisis de componentes principales. He aquí una pequeña demostración en Matlab. Introduce tus pesos de la matriz:

weights =

1.0000    0.8000    0.6000    0.4000         0
0.8000    1.0000    0.6500    0.4000    0.0200
0.6000    0.6500    1.0000    0.2000    0.0900
0.4000    0.4000    0.2000    1.0000    0.7100
     0    0.0200    0.0900    0.7100    1.0000

y tomar su descomposición de valor singular con el comando svd:

>> [u s] = svd(weights);

Ahora las columnas de u contienen información sobre cómo sus palabras se relacionan entre sí y s contiene información sobre la cantidad de información de la tabla subyacente está contenida en cada columna. Ya que todos los pesos son mayores que cero, la primera columna simplemente dice que todos los pesos están relacionados (por ejemplo, si los pesos son las correlaciones en el tráfico de búsqueda, usted puede pensar en esto como diciendo que cada término se aumenta cuando la cantidad total de tráfico de búsqueda aumenta):

>> u(:,1)

ans =

0.5307
0.5419
0.4668
0.4054
0.2064

La segunda columna de u contiene información sobre cómo los términos de búsqueda se agrupan en:

>> u(:,2)

ans =

 0.2396
 0.2380
 0.2475
-0.5478
-0.7243

Esto indica que los tres primeros términos ("tenis", "Federer" y "Wimbledon") están relacionados unos con otros, como lo son el segundo de los dos ("Londres", "policía")

La diagonal de las entradas de la matriz s dirá qué parte de la información está en cada una de las columnas. Más específicamente, si tomamos la suma acumulativa y normalizar por el total, se obtiene un vector cuyos n-esima entrada nos dice la cantidad de información que se conserva si sólo nos fijamos en las primeras n columnas:

>> cumsum(diag(s))/sum(diag(s))

ans =

0.5300
0.8300
0.9315
0.9708
1.0000

Esto nos dice que tenemos que el 83% de la información relevante en los pesos de la matriz si sólo nos fijamos en las dos primeras columnas.