Comment construire des clusters basés sur la liaison par paire (identique ou non)

Question

J'ai un ensemble d'images et j'ai demandé à MTurk si deux images appartenaient à la même catégorie ou pas (Il y a plus de nuance spécifique à l'application ici mais nous demandons essentiellement s'ils appartiennent à la même catégorie ou non).

Ma question est de savoir comment construire une affectation de cluster à partir de ces réponses, supposons que toutes les paires possibles dans l'ensemble sont traitées. Idéalement également robuste au bruit (nous avons déjà dupliqué les questions et prévoyons d'utiliser le vote majoritaire).

Un exemple, en supposant qu'il y a trois images ABC D. En supposant que la réponse est la suivante: Un similaire à BC similaire à DA différent de CB différent de CA différent de DB différent de D

La sortie devrait être deux grappes (A, B) et (C, D). Notez que nous ne connaissons pas le nombre de grappes à l'avance et que nous aimerions en déduire les réponses.

J'ai trouvé quelques questions connexes sur SO, mais ils ne sont pas exactement les mêmes. Par exemple, ils peuvent être basés sur la distance au lieu d'une réponse booléenne (oui ou non). Je pourrais être en mesure de réduire ma question à la forme de la distance mais je suppose que ma question est encore plus facile que le réglage de la distance. Des questions connexes ici:

Clustering given pairwise distances with unknown cluster number?

https://stats.stackexchange.com/questions/2717/clustering-with-a-distance-matrix

serait encore plus idéal que les algorithmes ont implémentation de Python déjà (par exemple, sklearn). Mais sinon, ça ne me dérange pas de l'implémenter tout seul.

Merci.

Answer 1

Cela ressemble à ce que vous voulez utiliser la classification hiérarchique. Lorsque vous effectuez, par exemple, un couplage moyen, il fusionne les clusters de sorte que les personnes sont plus susceptibles de les considérer comme "similaires".

Vous devez réfléchir à la manière de traiter les informations manquantes, les informations contradictoires, etc. - par exemple, vous pouvez utiliser similarity (x, y) = (0.5 + # positiveVotes)/(1 + # positiveVotes + # negativeVotes) pour chaque paire. Si la paire n'a pas été évaluée, cela donne 0,5, après un vote positif, il devient 0,75, après un vote négatif 0,25, et des votes supplémentaires vous donneront une similarité plus décidée (à moins qu'ils ne soient en désaccord, bien sûr).

Answer 2

On pourrait voir cela comme un problème dans la théorie des graphes où les nœuds et les bords du graphique sont représentés par les images et la similitude entre eux. On pourrait alors appliquer un community detection algorithm (par exemple, la maximisation de la modularité ou la classification hiérarchique comme déjà suggéré) pour catégoriser les images.

Les deux sklearn et scipy ont une implémentation de la classification hiérarchique et il semble qu'il existe également un python implementation of Louvain method for community detection.