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, .
Catégorie:Intelligence artificielle Catégorie:Algorithme de partitionnement de données