regroupement de chaînes par similarité hachage/mesure

Question

Je voudrais résumer des chaînes de taille moyenne (10-20 caractères) à des groupes. Cela signifie que si deux chaînes sont très similaires, par ex. "football" et "socer", le hachage pour les deux devrait être similaire. Similaire en termes d'un nombre entier, ou par une mesure de similarité retournant 0 ou 1 pour "très similaire". Y at-il un point de référence ou une évaluation liée aux méthodes de regroupement?

En ce moment, je suis au courant de

• Histogramme et certains histogram intersection kernel.
• Le Levenstein Distance measure

Ou est-ce problème est résolu pour un temps très long et il n'y a que des « normes »?

Merci beaucoup d'avance!

Answer 1

L'état des techniques de l'art de regarder en sont probablement MinHash, LSH, hash WTA, etc.

Ce que vous recherchez est pas le clustering, mais la détection quasi-double.

De telles méthodes seraient utilisées par Google Actualités, par exemple, pour détecter les actualités quasi dupliquées (et elles sont nombreuses). Ici, vous devriez essayer les mêmes approches sur les caractères et peut-être n-grammes.