24  Clustering spectral

Le clustering cherche à regrouper en K groupes G_k, k=1,\dots, K des exemples non étiquetés S = \{\boldsymbol{x}_1, \dots, \boldsymbol{x}_m\} Contrairement aux méthodes basées sur une représentation explicite des groupes, comme K-means avec des centres, les méthodes de clustering spectrales s’appuient sur la connectivité entre exemples d’un même groupe, indépendamment de la forme du groupe. Cette connectivité est représentée par un graphe.

24.1 Construction du graphe

Dans un premier temps, il s’agit de contruire un graphe dans lequel

  • chaque sommet correspond à un exemple \boldsymbol{x}_i,
  • chaque arête représente un lien de similarité entre les deux points \boldsymbol{x}_i et \boldsymbol{x}_j connectés et la pondération du l’arête mesure le niveau de ce lien.

Tous les liens peuvent être représentés au travers de la matrice d’adjacence \boldsymbol{A}\in\mathbb{R}^{m\times m} où A_{ij} mesure l’affinité entre \boldsymbol{x}_i et \boldsymbol{x}_j et respecte A_{ij} = A_{ji}, A_{ij}\geq 0 et A_{ii}=0.

Différents types de graphes peuvent être considérés avec différentes mesures d’affinité/similarité :

  • kppv : A_{ij} = 1 si \boldsymbol{x}_j est un des plus proches voisins de \boldsymbol{x}_i ou l’inverse, 0 sinon ;
  • Kppv-bis : A_{ij} = 1 si \boldsymbol{x}_j est un des plus proches voisins de \boldsymbol{x}_i et l’inverse, 0 sinon ;
  • \epsilon-graphe : A_{ij} = 1 si \|\boldsymbol{x}_i - \boldsymbol{x}_j\|\leq \epsilon, 0 sinon ;
  • RBF gaussien : A_{ij} = \exp\left(\frac{-\|\boldsymbol{x}_i-\boldsymbol{x}_j\|^2}{2\sigma^2}\right).

Une fois le graphe construit, le but est de détecter les composantes connectées du graphe.


def plot_graph(X, A, title):
    m = len(X)
    plt.figure()
    plt.plot(X[:,0], X[:,1], "ok")
    for i in range(m):
        for j in range(i):
            if A[i,j] > 0:
                plt.plot(X[[i,j],0], X[[i,j],1], "-b", linewidth=2*A[i,j])
    plt.title(title + " graphe des données ")
m=200
X = np.random.randn(m,2) 
y = np.random.rand(m) > 0.5
X[y,:] *= np.tile(3 / np.linalg.norm(X[y,:], axis=1), (2, 1)).T
X[~y,:] *= np.tile(1 / np.linalg.norm(X[~y,:], axis=1), (2, 1)).T

eps = 1
A = np.zeros((m,m))
for i in range(m):
    for j in range(i):
        if np.linalg.norm(X[i,:]-X[j,:]) < eps:
            A[i,j] = 1
            A[j,i] = 1
            
plot_graph(X, A, "epsilon")

Dans ce graphe, on peut identifier 2 composantes connectées correspondant aux deux groupes de données recherchées. À noter que tous les points d’un groupe ne sont pas forcément tous liés directement, mais simplement connectés par un chemin qui ne parcourt que des points du même groupe.

24.2 Algorithme

Après la construction du graphe, l’algorithme de clustering spectral va projeter les données dans un nouvel espace de représentation de petite dimension où les groupes apparaîtront de manière évidente.

  1. Construire la matrice de similarité \boldsymbol{A} (matrice d’adjacence du graphe) (voir ci-dessus).
  2. Calculer la matrice des degrés1 : \boldsymbol{D} = diag(\boldsymbol{A}\boldsymbol{1}), D_{ii} = \sum_{j=1}^m A_{ij}.
  3. Calculer le laplacien du graphe : \boldsymbol{L} = \boldsymbol{D} - \boldsymbol{A}.2
  4. Calculer les K vecteurs propres \boldsymbol{u}_k de \boldsymbol{L} avec les plus petites valeurs propres.
  5. Considérer les lignes \boldsymbol{v}_i^{T} de la matrice \boldsymbol{U} = [\boldsymbol{u}_1,\dots , \boldsymbol{u}_K]= \begin{bmatrix}\boldsymbol{v}_1^T\\\vdots\\\boldsymbol{v}_m^T\end{bmatrix}\in\mathbb{R}^{m\times K}
  6. Appliquer K-means (par exemple) aux points \boldsymbol{v}_i dans la nouvelle représentation.
def spectralclustering(X, A, K):
    m = len(X)
    D = np.diag(np.sum(A, axis=1))
    L = D - A
    lambdas, U = np.linalg.eigh(L)
    U = U[:,:K]
    y = kmeans(U, K)
    return y, U

# application aux données de l'exemple précédent 
y, U = spectralclustering(X, A, 2)

plt.figure()
plt.imshow(A, cmap="gray")
plt.title("Matrice d'adjacence A")

plt.figure()
plt.plot(U[y==0,0], U[y==0,1], "ob")
plt.plot(U[y==1,0], U[y==1,1], "or")
plt.title("Données projetées dans l'espace des vecteurs propres") 

plt.figure()
plt.plot(X[y==0,0], X[y==0,1], "ob")
plt.plot(X[y==1,0], X[y==1,1], "or")
t=plt.title("Résultat du clustering spectral")

24.3 Justification théorique

Pour comprendre pourquoi le clustering spectral fonctionne, plaçons-nous dans un cas idéal où (pour y_i l’indice du groupe de \boldsymbol{x}_i) :

  • l’affinité de deux points est strictement nulle s’ils n’appertiennent pas au même groupe : A_{ij}=0 si y_i\neq y_j ;
  • il existe un chemin entre chaque paire de points \boldsymbol{x}_i et \boldsymbol{x}_j appartenant au même groupe qui ne parcourt que des sommets du graphe affectés au même groupe : si y_i=y_j, alors il existe n\geq 0,\ (\boldsymbol{x}_k)_{1\leq k\leq n}, tels que y_k = y_i = y_j,\ \boldsymbol{x}_0 = \boldsymbol{x}_j,\ \boldsymbol{x}_n=\boldsymbol{x}_j,\ et\ A_{k, k+1} > 0,\ k=0,\dots, n-1

Dans ce cas, nous pouvons démontrer que \lambda_1 = \dots = \lambda_K = 0 (la multiplicité de la valeur propre 0 est égale au nombre de composantes connectées K du graphe), et les vecteurs propres correspondant sont les indicatrices des groupes G_k : (\boldsymbol{u}_k)_i = \mathbf{1}(\boldsymbol{x}_i\in G_k).

Ainsi, chaque vecteur \boldsymbol{v}_i représentant \boldsymbol{x}_i dans l’espace des vecteurs propres ne peut prendre qu’une valeur parmi K : le vecteur binaire avec un unique 1 en position y_i.3 Et donc, tous les points du groupe G_k sont projetés sur le même point : \boldsymbol{v}_i = \boldsymbol{v}_j si y_i=y_j et le clustering devient évident.

Pour le démontrer, nous pouvons utiliser le résultat intermédiaire suivant :

Si un graphe est connecté (il existe un chemin entre toute paire de sommets), alors son laplacien \boldsymbol{L} possède \lambda=0 comme valeur propre de multiplicité 1 associée à un vecteur propre constant, \boldsymbol{u}=\boldsymbol{1}.

Pour tout vecteur \boldsymbol{u}\in\mathbb{R}^m,
\boldsymbol{u}^\top \boldsymbol{L}\boldsymbol{u} = \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m A_{ij}(u_i - u_j)^2 car \begin{align*} \boldsymbol{u}^\top \boldsymbol{L}\boldsymbol{u} & = \boldsymbol{u}^\top \boldsymbol{D}\boldsymbol{u} - \boldsymbol{u}^\top \boldsymbol{A}\boldsymbol{u} = \sum_{i=1}^m D_{ii} u_i^2 - \sum_{i=1}^m\sum_{j=1}^m A_{ij} u_i u_j\qquad (car\ \boldsymbol{L} = \boldsymbol{D} -\boldsymbol{A}) \\ &= \frac{1}{2}\sum_{i=1}^m D_{ii} u_i^2 - \sum_{i=1}^m\sum_{j=1}^m A_{ij} u_i u_j + \frac{1}{2}\sum_{j=1}^m D_{jj} u_j^2\\ &= \frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m A_{ij} u_i^2 - \sum_{i=1}^m\sum_{j=1}^m A_{ij} u_i u_j + \frac{1}{2}\sum_{j=1}^m \sum_{i=1}^m A_{ji} u_j^2\qquad (car\ D_{ii} = \sum_{j=1}^m A_{ij} )\\ &= \frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m A_{ij} u_i^2 - \sum_{i=1}^m\sum_{j=1}^m A_{ij} u_i u_j + \frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m A_{ij} u_j^2\qquad (car\ A_{ji} = A_{ij} )\\ &= \frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m A_{ij} (u_i^2 - 2u_i u_j + u_j^2) =\frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m A_{ij} (u_i - u_j)^2 \end{align*}

Donc, si \boldsymbol{u} est un vecteur propre associé à la valeur propre \lambda=0, alors \boldsymbol{L} \boldsymbol{u} = \lambda \boldsymbol{u}= \boldsymbol{0}\qquad et\qquad \boldsymbol{u}^\top \boldsymbol{L}\boldsymbol{u} = \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m A_{ij}(u_i - u_j)^2 = \lambda \boldsymbol{u}^\top \boldsymbol{u} = 0 Et puisque A_{ij}\geq 0, on a A_{ij}\neq 0 \Rightarrow u_i=u_j.

Donc u_i=u_j si un chemin existe entre \boldsymbol{x}_i et \boldsymbol{x}_j, ce qui implique un vecteur propre constant pour \lambda=0 pour le laplacien d’un graphe connecté.

La deuxième étape consiste à déduire ce qu’il se passe lorsque le graphe contient plusieurs composantes (sous-graphes) connectées. Dans ce cas, puisque A_{ij}=0 si y_i\neq y_j, la matrice \boldsymbol{A} est bloc-diagonale avec des zéros en dehors des blocs correspondant aux groupes recherchés :

Le laplacien \boldsymbol{L} est donc lui aussi bloc-diagonal :

Il est alors possible d’utiliser le résultat suivant :

Les valeurs propres d’une matrce bloc-diagonale sont l’ensemble des valeurs propres des blocs et les vecteurs propres sont les vecteurs propres des blocs étendus avec des zéros.

Si \boldsymbol{L} = \begin{bmatrix} \boldsymbol{L}_1 & & \boldsymbol{0} \\ & \ddots & \\ \boldsymbol{0} & & \boldsymbol{L}_K \end{bmatrix} et \lambda_k\boldsymbol{u}_k = \boldsymbol{L}_k \boldsymbol{u}_k, alors pour \tilde{\boldsymbol{u}}_k= \begin{bmatrix}0\\ \vdots\\ 0\\ \boldsymbol{u}_k\\ 0\\\vdots\end{bmatrix} \quad \Rightarrow\quad \boldsymbol{L}\tilde{\boldsymbol{u}}_k = \begin{bmatrix}0\\ \vdots\\ 0\\ \boldsymbol{L}_k\boldsymbol{u}_k\\ 0\\\vdots\end{bmatrix}= \lambda_k \tilde{\boldsymbol{u}}_k

À noter qu’en pratique, suivant le réglage des paramètres de la construction du graphe, les matrices ne sont plus forcément bloc-diagonales (certaines connexions peuvent se créer entre les groupes), ce qui conduit à des résultats un peu moins nets que ceux-ci.

  1. Le degré d’un sommet du graphe est la somme des pondérations des arêtes connectées à ce sommet. La matrice des degrés est la matrice diagonale où chaque terme sur la diagonale donne le degré d’un sommet.↩︎

  2. Certaines variantes considèrent une version normalisée du laplacien : \boldsymbol{L}_{rw}=\boldsymbol{D}^{-1}\boldsymbol{L} ou \boldsymbol{L}_{sym}=\boldsymbol{D}^{-1/2}\boldsymbol{L} \boldsymbol{D}^{-1/2}.↩︎

  3. La valeur de \boldsymbol{v}_i observée en pratique peut être différente de 1 car les vecteurs propres ne sont définis qu’à un facteur multiplicatif près.↩︎