Matrice di similarità coseno di cluster

Question

Alcune domande su StackOverflow menzionano questo problema, ma non ho trovato una soluzione concreta.

devo una matrice quadrata che consiste di somiglianze coseno (valori tra 0 e 1), per esempio:

| A | B | C | D 
A | 1.0 | 0.1 | 0.6 | 0.4 
B | 0.1 | 1.0 | 0.1 | 0.2 
C | 0.6 | 0.1 | 1.0 | 0.7 
D | 0.4 | 0.2 | 0.7 | 1.0 

La matrice quadrata può essere di qualsiasi dimensione. Voglio ottenere cluster (non so quanti) che massimizzano i valori tra gli elementi nel cluster. Cioè per l'esempio precedente devo ottenere due gruppi:

1. B
2. A, C, D

Il motivo è perché C & D hanno il più alto valore tra di loro, e A & C anche avere il valore più alto tra di loro.

Un articolo può trovarsi in un solo cluster.

Il richiamo non è importante per questo problema, ma la precisione è molto importante. È accettabile produrre tre cluster: 1) B, 2) A, 3) C, D. Ma non è accettabile produrre alcuna soluzione in cui B si trova in un cluster con un altro elemento.

Penso che la diagonale (1.0) mi confonda. I miei dati sono garantiti per avere almeno un cluster di 2+ elementi, e voglio trovare il maggior numero possibile di cluster senza sacrificare la precisione.

Dovrò implementarlo in Python.

Answer 1

È possibile farlo facilmente utilizzando il clustering spettrale. Puoi usare le implementazioni pronte come quella in sklearn o implementarla tu stesso. È piuttosto facile un algoritmo facile.

Ecco un pezzo di codice farlo in Python usando sklearn:

import numpy as np 
from sklearn.cluster import SpectralClustering 
mat = np.matrix([[1.,.1,.6,.4],[.1,1.,.1,.2],[.6,.1,1.,.7],[.4,.2,.7,1.]]) 
SpectralClustering(2).fit_predict(mat) 
>>> array([0, 1, 0, 0], dtype=int32) 

Come si può vedere restituisce il raggruppamento che hai citato.

L'algoritmo acquisisce i migliori autovettori k della matrice di input corrispondente agli autovalori più grandi, quindi esegue l'algoritmo della media k sulla nuova matrice. Ecco un semplice codice che fa questo per la vostra matrice:

from sklearn.cluster import KMeans 
eigen_values, eigen_vectors = np.linalg.eigh(mat) 
KMeans(n_clusters=2, init='k-means++').fit_predict(eigen_vectors[:, 2:4]) 
>>> array([0, 1, 0, 0], dtype=int32) 

Si noti che l'implementazione dell'algoritmo nella biblioteca sklearn può differire dalla mia. L'esempio che ho dato è il modo più semplice per farlo. Ci sono alcuni buoni tutorial disponibili online che descrivono in profondità l'algoritmo di cluster spettrale.

Per i casi che si desidera l'algoritmo per capire il numero di cluster di per sé, è possibile utilizzare Density Based Clustering Algoritmi come DBSCAN:

from sklearn.cluster import DBSCAN 
DBSCAN(min_samples=1).fit_predict(mat) 
array([0, 1, 2, 2])