Propagation d'affinité - Affinity propagation

Dans les statistiques et l'exploration de données , la propagation d'affinité (AP) est un algorithme de clustering basé sur le concept de « passage de messages » entre les points de données. Contrairement aux algorithmes de clustering tels que k -means ou k -medoids , la propagation par affinité ne nécessite pas de déterminer ou d'estimer le nombre de clusters avant d'exécuter l'algorithme. Semblable à k -medoids, la propagation par affinité trouve des « exemplaires », des membres de l'ensemble d'entrée qui sont représentatifs des clusters.

Algorithme

Soit x ₁ à x _n un ensemble de points de données, sans hypothèse sur leur structure interne, et soit s une fonction qui quantifie la similitude entre deux points quelconques, telle que s ( i , j ) > s ( i , k ) ssi x _i ressemble plus à x _j qu'à x _k . Pour cet exemple, la distance carrée négative de deux points de données a été utilisée, c'est-à-dire pour les points x _i et x _k ,${\displaystyle s(i,k)=-\left\|x_{i}-x_{k}\right\|^{2}}$

La diagonale de s (c'est-à-dire ) est particulièrement importante, car elle représente la préférence d'instance, c'est-à-dire la probabilité qu'une instance particulière devienne un exemplaire. Lorsqu'il est défini sur la même valeur pour toutes les entrées, il contrôle le nombre de classes produites par l'algorithme. Une valeur proche de la similarité minimale possible produit moins de classes, tandis qu'une valeur proche ou supérieure à la similarité maximale possible produit de nombreuses classes. Il est généralement initialisé à la similarité médiane de toutes les paires d'entrées. ${\style d'affichage s(i,i)}$

L'algorithme procède par alternance entre deux étapes de passage de message, qui mettent à jour deux matrices :

• La matrice de « responsabilité » R a des valeurs r ( i , k ) qui quantifient à quel point x _k est bien adapté pour servir d'exemplaire pour x _i , par rapport à d'autres exemplaires candidats pour x _i .
• La matrice de "disponibilité" A contient des valeurs a ( i , k ) qui représentent à quel point il serait "approprié" pour x _i de choisir x _k comme exemplaire, en tenant compte de la préférence des autres points pour x _k comme exemplaire.

Les deux matrices sont initialisées à tous les zéros et peuvent être vues comme des tables de probabilité logarithmique . L'algorithme effectue ensuite les mises à jour suivantes de manière itérative :

• Tout d'abord, des mises à jour de responsabilité sont envoyées : ${\displaystyle r(i,k)\leftarrow s(i,k)-\max _{k'\neq k}\left\{a(i,k')+s(i,k')\right\ }}$
• Ensuite, la disponibilité est mise à jour par

${\displaystyle a(i,k)\leftarrow \min \left(0,r(k,k)+\sum _{i'\not \in \{i,k\}}\max(0,r( je',k))\droit)}$pour et${\style d'affichage i\neq k}$

${\displaystyle a(k,k)\leftarrow \sum _{i'\neq k}\max(0,r(i',k))}$.

Les itérations sont effectuées jusqu'à ce que les limites du cluster restent inchangées sur un certain nombre d'itérations ou qu'un nombre prédéterminé (d'itérations) soit atteint. Les exemplaires sont extraits des matrices finales comme ceux dont la « responsabilité + disponibilité » pour eux-mêmes est positive (ie ). ${\style d'affichage (r(i,i)+a(i,i))>0}$

Applications

Les inventeurs de la propagation par affinité ont montré qu'elle est meilleure pour certaines tâches de vision par ordinateur et de biologie computationnelle , par exemple le regroupement d'images de visages humains et l'identification de transcrits régulés, que k- means, même lorsque k- means a été autorisé à de nombreux redémarrages aléatoires et initialisé à l'aide de PCA . Une étude comparant la propagation par affinité et le clustering de Markov sur le partitionnement de graphe d'interaction protéique a révélé que le clustering de Markov fonctionnait mieux pour ce problème. Une variante semi-supervisée a été proposée pour les applications de text mining . Une autre application récente était en économie, lorsque la propagation par affinité a été utilisée pour trouver des modèles temporels dans les multiplicateurs de production de l'économie américaine entre 1997 et 2017.

Logiciel

• Une implémentation Java est incluse dans le framework d' exploration de données ELKI .
• Une implémentation Julia de la propagation par affinité est contenue dans le package Clustering.jl de Julia Statistics.
• Une version Python fait partie de la bibliothèque scikit-learn .
• Une implémentation R est disponible dans le package "apcluster".

Les références