Un algorithme où chaque point échange des messages avec les autres pour décider qui le représente le mieux. À la fin, quelques points réels sont élus exemplaires, et chacun des autres se rattache à l'un d'eux. Le nombre de groupes n'est pas fixé : il découle d'un réglage, la préférence.
Une élection sans candidats déclarés. Chacun indique qui le représenterait bien ; chacun évalue s'il ferait un bon représentant au vu des soutiens reçus. Au fil des tours, quelques représentants émergent et les autres se rallient.
Souvent l'opposé de la distance au carré. La diagonale contient la préférence : l'envie de chaque point d'être lui-même exemplaire. Elle règle le nombre de groupes.
La responsabilité dit à quel point un candidat conviendrait comme représentant, comparé aux autres candidats. La disponibilité dit à quel point ce candidat est prêt à représenter, vu les soutiens qu'il reçoit déjà. Les messages sont mis à jour à chaque tour, avec un amortissement.
Quand les messages se stabilisent, les points qui se désignent eux-mêmes deviennent exemplaires. Chaque autre point rejoint l'exemplaire qu'il juge le plus proche.
Des chiffres manuscrits extraits de formulaires, en 8 × 8 pixels. Les faire tous étiqueter à la main coûte cher ; on veut n'en montrer qu'une petite partie aux annotateurs.
Affinity Propagation élit 104 exemplaires, soit 6 % des images, avec au moins 6 exemplaires pour chaque chiffre. Un annotateur étiquette ces 104 images ; chaque autre image hérite de l'étiquette de son exemplaire.
Contrôlée avec les vraies étiquettes, la propagation donne la bonne étiquette à 97,1 % des images. Le reste est à repérer avec une vérification par échantillon. Le coût d'annotation est divisé par plus de 15.
Noms donnés pour R (apcluster) et Python (scikit-learn).
La préférence règle le nombre d'exemplaires. Par défaut, la médiane des similarités, qui donne souvent beaucoup de groupes (104 ici). Une préférence plus basse, comme le minimum, en donne moins. En R, q fixe la préférence par quantile.
L'amortissement des messages, entre 0,5 et 1. 0,9 par défaut dans apcluster, 0,5 dans scikit-learn. Une valeur élevée évite les oscillations et aide à converger.
Le nombre maximal de tours et le nombre de tours stables exigés pour conclure. Vérifiez la convergence : sans convergence, scikit-learn émet un avertissement et peut renvoyer -1 comme étiquette.
# Choisir les images à faire étiqueter : Affinity Propagation en R
library(apcluster)
chiffres <- read.csv("chiffres_manuscrits.csv")
X <- as.matrix(chiffres[, 1:64]) # la vraie étiquette ne sert qu'au contrôle final
# Similarité = moins la distance euclidienne au carré ; préférence = médiane (défaut)
set.seed(42)
modele <- apcluster(negDistMat(r = 2), X, lam = 0.9, maxits = 1000, convits = 100)
exemplaires <- modele@exemplars
cat("Nombre d'exemplaires élus :", length(exemplaires), "sur", nrow(X), "images\n")
# Un humain étiquette seulement les exemplaires ; chaque image hérite de celui de son groupe
etiquette_deduite <- chiffres$chiffre[modele@idx]
cat("Images correctement étiquetées :", round(mean(etiquette_deduite == chiffres$chiffre), 3), "\n")
print(table(chiffre_exemplaire = chiffres$chiffre[exemplaires]))# Choisir les images à faire étiqueter : Affinity Propagation en Python
import pandas as pd
from sklearn.cluster import AffinityPropagation
chiffres = pd.read_csv("chiffres_manuscrits.csv")
X = chiffres.drop(columns="chiffre") # la vraie étiquette ne sert qu'au contrôle final
# Similarité = moins la distance euclidienne au carré ; préférence = médiane (défaut)
modele = AffinityPropagation(damping=0.9, max_iter=1000, random_state=42).fit(X)
exemplaires = modele.cluster_centers_indices_
print("Nombre d'exemplaires élus :", len(exemplaires), "sur", len(X), "images")
print("Convergence en", modele.n_iter_, "itérations")
# Un humain étiquette seulement les exemplaires ; chaque image hérite de l'étiquette du sien
etiquette_exemplaire = chiffres["chiffre"].values[exemplaires]
etiquette_deduite = etiquette_exemplaire[modele.labels_]
print("Images correctement étiquetées :", round((etiquette_deduite == chiffres["chiffre"]).mean(), 3))
print("Exemplaires par chiffre :", pd.Series(etiquette_exemplaire).value_counts().sort_index().to_dict())Il ne le fixe pas directement. Le nombre de groupes découle de la préférence, la valeur placée sur la diagonale de la matrice de similarité. Plus elle est élevée, plus chaque point a envie d'être son propre exemplaire, et plus il y a de groupes.
Les deux représentent chaque groupe par un point réel. K-medoids demande le nombre de groupes et optimise leurs positions par échanges successifs. Affinity Propagation fait émerger les exemplaires par échange de messages entre tous les points, sans fixer leur nombre, mais avec un coût mémoire plus élevé.
Les messages peuvent osciller, surtout avec des doublons ou des similarités identiques. On augmente l'amortissement (0,9), le nombre maximal d'itérations, et on supprime les doublons. apcluster ajoute par défaut un bruit infime aux similarités pour départager les égalités.
Choisit aussi des représentants réels, mais pour un nombre de groupes donné. Plus prévisible et plus facile à régler.
Voir la fiche → pour les gros volumesTrès rapide, mais ses centres sont des moyennes qui ne correspondent à aucune image réelle.
Voir la fiche → autre méthode sans kTrouve seul le nombre de groupes en suivant les sommets de densité, avec une largeur de fenêtre à régler.
Voir la fiche →Dataistudio forme les équipes au machine learning et à l'IA, sur des cas concrets.
Nous utilisons des cookies de mesure d'audience et de suivi publicitaire pour comprendre la fréquentation du site et l'efficacité de nos annonces. Rien n'est déposé sans votre accord. En savoir plus