Propagation d'affinité
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En programmation informatique, la propagation d'affinité est un algorithme récent de partitionnement de données, ou clustering, qui permet de trouver les éléments d'un ensemble qui sont les plus représentatifs - un critère de ressemblance étant donné - de l'ensemble.
Description de l'algorithme
C'est un algorithme itératif qui repose sur le partage des « affinités » :
- Chaque élément c repère dans son voisinage un élément qui lui ressemble suffisamment, et augmente son affinité pour cet élément ;
- Les étapes suivantes consistent à « propager » cette affinité :
- Chaque élément c repère celui pour qui il a la plus grande affinité, noté m ;
- Il ajoute à ses propres affinités celles de m ;
- Cette étape est répétée un certain nombre de fois, ou bien jusqu'à ce que le nombre d'éléments passe en dessous d'un certain seuil - ou encore quand cette étape n'apporte plus aucun changement.
Il y a alors trois cas :
- L'élément considéré possède une affinité maximale pour un autre élément : il lui ressemble ;
- L'élément considéré possède une affinité maximale pour lui-même : il est « exemplaire » (exemplar) ;
- L'élément considéré possède une affinité nulle : il est « isolé ».
Le nombre d'éléments exemplaires dépend de nombreux paramètres et ne peut être donné a priori.
On obtient à l'issue de l'algorithme un arbre complet, reliant les éléments semblables qui ont pu être identifiés comme tels.
Références
- Marc Mézard, « Where Are the Exemplars », dans Science, .
Portail de l'informatique théorique
