Moyen efficace de calculer les scores de ressemblance des chaînes lorsque la taille de l'échantillon est grande?

Question

Supposons que vous disposiez d'une liste de 10 000 adresses électroniques et que vous souhaitiez rechercher les "voisins proches" les plus proches. Les éléments de cette liste sont définis comme des adresses électroniques qui se rapprochent de manière suspecte d’autres adresses électroniques de votre liste.

Je suis conscient de la façon de calculer la distance de Levenshtein entre deux chaînes (grâce à cette question ), qui me donnera un score du nombre d'opérations nécessaires pour transformer une chaîne en une autre.

Supposons que je définisse " soupçonneusement proche d'une autre adresse e-mail " comme deux chaînes ayant un score de Levenshtein inférieur à N.

Existe-t-il un moyen plus efficace de rechercher des paires de chaînes dont le score est inférieur à ce seuil en plus de comparer toutes les chaînes possibles à toutes les autres chaînes possibles de la liste? En d'autres termes, ce type de problème peut-il être résolu plus rapidement que O (n ^ 2) ?

Le score de Levenshtein est-il un mauvais choix d’algorithmes pour résoudre ce problème?

Answer 1

Yup - vous pouvez trouver toutes les chaînes dans un intervalle donné d'une chaîne en un temps O (log n) en utilisant un BK-Tree . Des solutions alternatives impliquant la génération de chaque chaîne avec la distance n peuvent être plus rapides pour une distance de levenshtein de 1, mais la quantité de travail devient rapidement incontrôlable sur des distances plus longues.

Answer 2

Vous pouvez le faire avec Levenshtein dans O (kl) , où k correspond à votre distance maximale et l à votre chaîne maximale.

En gros, quand vous savez calculer le Levenshtein de base, il est facile de comprendre que tout résultat au-delà de k de la diagonale principale doit être supérieur à k . . Donc, si vous calculez la diagonale principale avec la largeur 2k + 1 suffira.

Si vous avez 10 000 adresses électroniques, vous n'aurez pas besoin d'un algorithme plus rapide. L’ordinateur peut calculer avec O (N ^ 2) assez rapidement.

Levenshtein est assez bon pour ce genre de problème.

Vous pouvez également envisager de transformer des courriels avec soundex avant de les comparer. Vous obtiendrez probablement de meilleurs résultats.

Answer 3

Ce problème est appelé clustering . Il fait partie d'un problème plus important de déduplication (vous devez décider quel membre du cluster correspond au membre le plus à droite). ), également appelé fusion-purge .

J'ai déjà lu quelques articles de recherche sur ce sujet (les noms figurent ci-dessous). En gros, les auteurs ont utilisé une fenêtre glissante de taille limitée sur une liste triée de chaînes. Ils ne feraient que comparer (en utilisant un algorithme modifier la distance ) N * N chaînes inside la fenêtre, réduisant ainsi la complexité de calcul. Si deux chaînes semblaient similaires, elles étaient combinées dans un cluster (en insérant un enregistrement dans une table de cluster séparée).

Le premier passage dans la liste a été suivi par un second passage où les chaînes étaient inversées avant d'être triées. De cette façon, les chaînes avec têtes différentes avaient une autre chance de s'approcher suffisamment pour être évaluées dans le même cadre. Lors de cette seconde passe, si une chaîne semblait suffisamment proche de deux (ou plus) chaînes dans la fenêtre et que ces chaînes faisaient déjà partie de leurs propres clusters (trouvés lors du premier passage), les deux clusters seraient alors fusionnés. (en mettant à jour la table du cluster) et la chaîne en cours sera ajoutée au cluster récemment fusionné. Cette approche est appelée algorithme union-find .

Ils ont ensuite amélioré l'algorithme en remplaçant la fenêtre par une liste des X prototypes essentiellement uniques . Chaque nouvelle chaîne serait comparée à chacun des prototypes X supérieurs. Si la chaîne semblait suffisamment proche de l'un des prototypes, elle serait alors ajoutée au cluster du prototype . Si aucun des prototypes ne semblait assez similaire, la chaîne deviendrait un nouveau prototype, en repoussant le prototype le plus ancien de la liste des X premiers. (Il y avait une logique heuristique utilisée pour décider laquelle des chaînes du cluster du prototype devait être utilisée comme nouveau prototype représentant le cluster entier). Encore une fois, si la chaîne ressemblait à plusieurs prototypes, toutes leurs grappes seraient fusionnées.

J’ai une fois implémenté cet algorithme pour la déduplication d’enregistrements de noms / adresses, la taille des listes étant d’environ 10 à 50 millions d’enregistrements. Cela a fonctionné très rapidement (et a également permis de trouver des doublons).

Globalement, pour de tels problèmes, la partie la plus délicate du cours consiste à trouver la bonne valeur du seuil de similarité . L'idée est de capturer toutes les erreurs sans produire trop de faux positifs . Les données présentant des caractéristiques différentes ont tendance à nécessiter des seuils différents. Le choix d’un algorithme de modification de la distance est également important, car certains algorithmes sont meilleurs pour les erreurs de ROC, d’autres pour les fautes de frappe et d’autres pour les erreurs de phonétique (comme lors de l’obtention d’un nom par téléphone).

Une fois l’algorithme de mise en cluster mis en œuvre, un bon moyen de le tester consiste à obtenir une liste d’échantillons uniques et à muter artificiellement chaque échantillon pour produire ses variations, tout en préservant le fait que toutes les variations ont été modifiées. provenir du même parent. Cette liste est ensuite mélangée et transmise à l'algorithme. En comparant la mise en cluster d'origine à la mise en cluster générée par l'algorithme de déduplication, vous obtiendrez le score d'efficacité .

Bibliographie:

Hernandez M. 1995, Le problème de la fusion / purge pour les grandes bases de données.

Monge A. 1997, Un algorithme efficace indépendant du domaine pour détecter approximativement les enregistrements en double dans la base de données.

Answer 4

Je ne pense pas que vous puissiez faire mieux que O (n ^ 2), mais vous pouvez faire quelques optimisations plus petites, qui pourraient suffire à accélérer assez pour rendre votre application utilisable:

• Vous pouvez d’abord trier toutes les adresses e-mail par partie après le @ et ne comparer que les adresses identiques
• Vous pouvez arrêter de calculer la distance entre deux adresses lorsqu'elle devient plus grande que n

EDIT: En fait, vous pouvez faire mieux que O (n ^ 2), regardez simplement la réponse de Nick Johnsons ci-dessous.

Answer 5

10 000 adresses électroniques ne sonnent pas trop. Pour rechercher des similarités dans un espace plus grand, vous pouvez utiliser shingling et min-hashing . Cet algorithme est un peu plus compliqué à mettre en œuvre, mais est beaucoup plus efficace sur un grand espace.

Answer 6

Il est possible de faire mieux, à condition d’inverser le problème.

Je suppose ici que vos adresses 10.000 sont plutôt "fixes", sinon vous devrez ajouter un mécanisme de mise à jour.

L'idée est d'utiliser la distance de Levenshtein, mais en mode "reverse", en Python:

class Addresses:
  def __init__(self,addresses):
    self.rep = dict()
    self.rep[0] = self.generate_base(addresses)
      # simple dictionary which associate an address to itself

    self.rep[1] = self.generate_level(1)
    self.rep[2] = self.generate_level(2)
    # Until N

La méthode generate_level génère toutes les variations possibles par rapport à l'ensemble précédent, moins les variations déjà existantes au niveau précédent. Il conserve l'origine comme la valeur associée à la clé.

Ensuite, il vous suffit de rechercher votre mot dans les différents ensembles:

  def getAddress(self, address):
    list = self.rep.keys()
    list.sort()
    for index in list:
      if address in self.rep[index]:
        return (index, self.rep[index][address]) # Tuple (distance, origin)
    return None

Ce faisant, vous calculez les différents ensembles une fois (cela prend du temps ... mais vous pouvez ensuite les sérialiser et les conserver pour toujours).

Et alors, la recherche est beaucoup plus efficace que O (n ^ 2), bien qu'il soit difficile de la donner, car cela dépend de la taille des ensembles générés.

Pour référence, consultez: http://norvig.com/spell-correct.html

Answer 7

Disons que vous avez 3 chaînes:

1 - "abc " 2 - " bcd " 3 - "cde"

La distance L entre 1 & amp; 2 est 2 (soustrayez 'a', ajoutez 'd'). La distance L entre 2 & amp; 3 est 2 (soustrayez 'b', ajoutez 'e').

Votre question est de savoir si nous pouvons déduire une distance L entre 1 & amp; 3 en utilisant les 2 comparaisons ci-dessus. La réponse est non.

La distance L entre 1 & amp; 3 est 3 (remplacez chaque caractère), cela ne peut en aucun cas être déduit à cause des scores des 2 premiers calculs. Les scores ne révèlent pas si des suppressions, des insertions ou des opérations de substitution ont été effectuées.

Donc, je dirais que Levenshtein est un mauvais choix pour une longue liste.

Answer 8

Si vous comparez réellement les adresses e-mail, une méthode évidente consiste à combiner un algorithme levenshtein avec un mappage de domaine. Je peux penser à des moments où je me suis inscrit à plusieurs reprises en utilisant le même domaine, mais des variantes de la partie nom d'utilisateur de l'adresse e-mail.