# Sur l'apprentissage d'une matrice d'affinité bistochastique en clustering*

Julien Ah-Pine¹,²,³

¹ Université de Lyon, Lyon 2, ERIC UR 3083

² Université Clermont Auvergne, LMBP CNRS, UMR 6620

³ Université Clermont Auvergne, CERDI CNRS IRD, UMR 6587

julien.ah-pine@univ-lyon2.fr

## Résumé

Nous nous intéressons à la tâche de clustering du point de vue graphe à l'instar du partionnement spectral (spectral clustering). Dans ce cas, la matrice d'affinité qui mesure l'intensité du lien (arête du graphe) pour chaque paire d'éléments (sommets du graphe) joue un rôle crucial. Plussieurs travaux antécédents ont montré l'intérêt de transformer une matrice d'affinité initiale de sorte à satisfaire certaines propriétés. La bistochasticité est une condition pertinente à cet égard. Dans ce travail, nous mettons en avant une autre condition : l'idempotence. Par la suite, En utilisant les propriétés existantes entre les matrices bistochastiques et idempotentes d'une part, et leurs matrices Laplaciennes associées d'autre part, nous proposons une nouvelle méthode d'apprentissage non-supervisé de matrice d'affinité. Notre procédure d'optimisation repose sur la méthode des multiplicateurs de Lagrange avec directions alternées (ADMM). Des résultats expérimentaux montrent l'intérêt pratique de notre approche.

## Mots-clés

Clustering, Matrice d'affinité, Bistochasticité, Idempotence, ADMM.

## Abstract

We are interested in graph based clustering such as spectral clustering. In this context, the affinity matrix that provides the strength of the similarity between each pair of elements plays a crucial role. Several previous works have showed that transforming a given affinity matrix so that it becomes double stochastic was beneficial. In this work, we highlight another property : idempotency. By leveraging the relationships between double stochastic and idempotent matrices on the one hand, and their related Laplacian matrices on the other hand, we introduce a new unsupervised learning method for affinity matrices. Our learning algorithm is based on ADMM. Some experimental results are provided in order to demonstrate the interest of our proposal.

## Keywords

Clustering, Affinity matrix, doubly stochasticity, Idempot

tence, ADMM.

## 1 Contexte et travaux antérieurs

La tâche de clustering consiste à partitionner un ensemble d'éléments en des sous-ensembles homogènes appelés clusters. Soit un ensemble de $n$ vecteurs $\{\mathbf{x}_i\}_{i=1,...,n}$ appartenant à $\mathbb{R}^p$, que nous cherchons à analyser. Nous nous intéressons à la partition en $k$ clusters $C = \{C_1, ..., C_k\}$ qui minimise le critère SSE (Sum of Squared Errors) suivant :

$$ \sum_{j=1}^{k} \sum_{\mathbf{x}_i \in C_j} \| \phi(\mathbf{x}_i) - \mathbf{c}_j \|^2 \quad (1) $$

où $\phi : \mathbb{R}^p \to \mathbb{F}$ est une projection des $\{\mathbf{x}_i\}$ dans un espace de grande dimension $\mathbb{F}$, $\mathbf{c}_j = \sum_{\mathbf{x}_i \in C_j} \phi(\mathbf{x}_i)/n_j$ est le vector moyen du cluster $C_j$ qui est de cardinal $n_j$ et $\|\cdot\|$ est la norme Euclidienne dans $\mathbb{F}$.

Le critère SSE peut être formalisé à l'aide de la matrice de noyau $\mathbf{K}$ de terme général $\mathbf{K}_{ii'} = \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_{i'}) \rangle = \kappa(\mathbf{x}_i, \mathbf{x}_{i'})$ où $\kappa : \mathbb{R}^p \times \mathbb{R}^p \to \mathbb{R}$ est une fonction noyau. Il s'agit dans ce cas de déterminer $\mathbf{X}$, la matrice de $\mathbb{R}^{n \times n}$ qui minimise la fonction objectif suivante :

$$ \mathrm{Tr}(\mathbf{K}(\mathbf{I}_n - \mathbf{X})) \quad (2) $$

où $\mathrm{Tr}$ est l'application trace dans $\mathbb{R}^{n \times n}$, $\mathbf{I}_n$ est la matrice identité d'ordre $n$, et $\mathbf{X}$ est de terme général :

$$ \mathbf{X}_{ii'} = \begin{cases} 1/n_j & \text{si } \mathbf{x}_i \text{ et } \mathbf{x}_{i'} \text{ sont dans } C_j, \\ 0 & \text{sinon.} \end{cases} \quad (3) $$

La matrice $\mathbf{X}$ ainsi définie possède plusieurs propriétés. Plus précisément [6] montre que la minimisation du SSE peut s'exprimer de façon équivalente comme suit :

$$ \min_{\mathbf{X} \in \mathbb{R}^{n \times n}} \mathrm{Tr}(\mathbf{K}(\mathbf{I}_n - \mathbf{X})) \quad (4) $$

$$ \text{s.t. } \mathbf{X} \ge \mathbf{0}_n, \mathbf{X} = \mathbf{X}^{\top}, \mathbf{X} \mathbf{e}_n = \mathbf{e}_n, \mathbf{X} = \mathbf{X}^2, \mathrm{Tr}(\mathbf{X}) = k. $$

où $\mathbf{0}_n$ est la matrice nulle d'ordre $n$, $(\mathbf{X} \ge \mathbf{0}_n) \Leftrightarrow (\mathbf{X}_{ii'} \ge 0, \forall i, i' = 1, ..., n)$, $\mathbf{X}^{\top}$ est la matrice transposée de $\mathbf{X}$ et $\mathbf{e}_n$ est le vecteur rempli de 1 de dimension $n$.

<footnote>*Cette communication est issue de l'article suivant : [1].</footnote>
Le problème DSNI (9) étant bi-convexe, nous pouvons utiliser la méthode ADMM (voir par exemple [3]) comme procédure d'optimisation. Les différentes étapes sont alors les suivantes :

0. Initialisation : $\mathbf{X}^0 \leftarrow \mathbf{K}$ (en ayant au préalable an-nuler les valeurs négatives de $\mathbf{K}$ le cas échéant).

1. Déterminer $\mathbf{L}_{\mathbf{X}}^{t+1}$ avec $\mathbf{X}^t$ fixé :

$$ 
\begin{aligned}
\mathbf{L}_{\mathbf{X}}^{t+1} &\leftarrow \arg \min_{\mathbf{L}_{\mathbf{X}} \in \mathbb{R}^{n \times n}} \frac{1}{2} \|\mathbf{I}_n - \mathbf{K} - \mathbf{L}_{\mathbf{X}}\|_F^2 \\
&\quad + \frac{\mu}{2} \|\mathbf{X}^t \mathbf{L}_{\mathbf{X}}\|_F^2 \\
&\quad + \frac{\rho}{2} \|\mathbf{X}^t + \mathbf{L}_{\mathbf{X}} - \mathbf{I}_n + \mathbf{U}^t\|_F^2 \\
&\text{s.t. } \mathbf{L}_{\mathbf{X}} \le \mathbf{I}_n, \mathbf{L}_{\mathbf{X}} = \mathbf{L}_{\mathbf{X}}^{\top}, \mathbf{L}_{\mathbf{X}} \mathbf{e}_n = \mathbf{n}_n.
\end{aligned}
\quad (10) $$

2. Déterminer $\mathbf{X}^{t+1}$ avec $\mathbf{L}_{\mathbf{X}}^{t+1}$ fixé :

$$ 
\begin{aligned}
\mathbf{X}^{t+1} &\leftarrow \arg \min_{\mathbf{X} \in \mathbb{R}^{n \times n}} \frac{1}{2} \|\mathbf{K} - \mathbf{X}\|_F^2 \\
&\quad + \frac{\mu}{2} \|\mathbf{X} \mathbf{L}_{\mathbf{X}}^{t+1}\|_F^2 \\
&\quad + \frac{\rho}{2} \|\mathbf{X} + \mathbf{L}_{\mathbf{X}}^{t+1} - \mathbf{I}_n + \mathbf{U}^t\|_F^2 \\
&\text{s.t. } \mathbf{X} \ge \mathbf{0}_n, \mathbf{X} = \mathbf{X}^{\top}, \mathbf{X} \mathbf{e}_n = \mathbf{e}_n.
\end{aligned}
\quad (11) $$

3. Déterminer $\mathbf{U}^{t+1}$ :

$$ \mathbf{U}^{t+1} \leftarrow \mathbf{U}^t + \mathbf{X}^{t+1} + \mathbf{L}_{\mathbf{X}}^{t+1} - \mathbf{I}_n \quad (12) $$

4. Répéter 1., 2., 3. tant qu'une condition d'arrêt n'est pas satisfaite.

Les sous-problèmes (10) et (11) peuvent être résolus efficacement par projections successives sur des ensembles convexes (voir par exemple [2]).

## 3 Validation empirique de l'approche proposée

Nous avons testé notre approche sur plusieurs jeux de données réels classiques disponibles en ligne<fnref n="1" />. Le protocole expérimental est le suivant : calcul de $\mathbf{K}$ en utilisant un noyau Gaussien ; approximation de $\mathbf{K}$ par une matrice d'af-finité bistochastique $\mathbf{X}$ obtenue par SSK ou DSN ou DSNI (sauf pour la baseline) ; application du spectral clustering [4] sur $\mathbf{X}$ en fixant $k$ au nombre correct de clusters ; comparaison de la partition obtenue et de la vérité terrain en utilisant la mesure NMI (Normalized Mutual Information). Pour le noyau Gaussien, l'hyperparamètre $\sigma^2$ est fixé à $p$ et pour DSNI le paramètre de pénalité $\mu$ est fixé à $\sqrt{n}$. Les résultats obtenus sont donnés dans la Table 1. La co-lonne SC représente la baseline et utilise le spectral clustering directement sur $\mathbf{K}$ la matrice de noyau Gaussien. Sur l'ensemble des jeux de données, nous constatons que DSNI donne de meilleurs résultats que SSK et DSN ce qui valide l'intérêt de notre modèle.

<table><caption>TABLE 1 – Statistiques des jeux de données et mesures NMI des différentes méthodes.</caption><thead><tr><th>Dataset</th><th>n</th><th>p</th><th>k</th><th>SC</th><th>SSK</th><th>DSN</th><th>DSNI</th></tr></thead><tbody><tr><td>Glass</td><td>214</td><td>9</td><td>6</td><td>0.253</td><td>0.276</td><td>0.243</td><td><strong>0.297</strong></td></tr><tr><td>Ionosphere</td><td>351</td><td>34</td><td>2</td><td>0.038</td><td>0.066</td><td>0.076</td><td><strong>0.131</strong></td></tr><tr><td>Breast cancer</td><td>569</td><td>30</td><td>2</td><td>0.010</td><td>0.010</td><td>0.010</td><td><strong>0.670</strong></td></tr><tr><td>Yeast</td><td>1484</td><td>8</td><td>10</td><td>0.070</td><td>0.258</td><td>0.256</td><td><strong>0.263</strong></td></tr><tr><td>Digits</td><td>1797</td><td>64</td><td>10</td><td>0.015</td><td>0.044</td><td>0.743</td><td><strong>0.767</strong></td></tr></tbody></table>

## Références

[1] J. Ah-Pine. Learning doubly stochastic and nearly idempotent affinity matrix for graph-based clustering. *European Journal of Operational Research*, 299(3):1069–1078, 2022.

[2] H. H. Bauschke and J. M. Borwein. On projection algorithms for solving convex feasibility problems. *SIAM review*, 38(3):367–426, 1996.

[3] S. Boyd, N. Parikh, and E. Chu. *Distributed optimization and statistical learning via the alternating direction method of multipliers*. Now Publishers Inc, 2011.

[4] A. Y. Ng, M. I. Jordan, Y. Weiss, et al. On spectral clustering : Analysis and an algorithm. *Advances in neural information processing systems*, 2:849–856, 2002.

[5] J. Peng and Y. Wei. Approximating k-means-type clustering via semidefinite programming. *SIAM journal on optimization*, 18(1):186–205, 2007.

[6] J. Peng and Y. Xia. A new theoretical framework for k-means-type clustering. In *Foundations and advances in data mining*, pages 79–96. Springer, 2005.

[7] R. Sinkhorn. Two results concerning doubly stochastic matrices. *The American Mathematical Monthly*, 75(6):632–634, 1968.

[8] U. Von Luxburg. A tutorial on spectral clustering. *Statistics and computing*, 17(4):395–416, 2007.

[9] F. Wang, P. Li, and A. C. Konig. Learning a bi-stochastic data similarity matrix. In *2010 IEEE International Conference on Computer Vision (ICCV'05) Volume 1*, volume 1, pages 294–301. IEEE, 2005.

[10] R. Zass and A. Shashua. A unifying approach to hard and probabilistic clustering. In *Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1*, volume 1, pages 294–301. IEEE, 2005.

[11] R. Zass and A. Shashua. Doubly stochastic normalization for spectral clustering. In *Advances in neural information processing systems*, pages 1569–1576, 2007.

<footnote n="1">1. https://archive.ics.uci.edu/ml/index.php</footnote>