Comment faire une correspondance floue des adresses postales?

14

Je voudrais savoir comment faire correspondre les adresses postales lorsque leur format diffère ou lorsque l'une d'elles est mal orthographiée.

Jusqu'à présent, j'ai trouvé différentes solutions mais je pense qu'elles sont assez anciennes et peu efficaces. Je suis sûr qu'il existe de meilleures méthodes, donc si vous avez des références à lire, je suis sûr que c'est un sujet qui peut intéresser plusieurs personnes.

La solution que j'ai trouvée (des exemples sont en R):

  • Distance Levenshtein, qui correspond au nombre de caractères que vous devez insérer, supprimer ou modifier pour transformer un mot en un autre.

    agrep("acusait", c("accusait", "abusait"), max = 2, value = TRUE) ## [1] "accusait" "abusait"

  • La comparaison des phonèmes

    library(RecordLinkage) soundex(x<-c('accusait','acusait','abusait')) ## [1] "A223" "A223" "A123"

  • L'utilisation d'un correcteur orthographique (éventuellement un correcteur bayésien comme celui de Peter Norvig) , mais pas très efficace sur l'adresse je suppose.

  • J'ai pensé à utiliser les suggestions de Google, mais de même, ce n'est pas très efficace sur les adresses postales personnelles.

  • Vous pouvez imaginer utiliser une approche supervisée d'apprentissage automatique, mais vous devez avoir stocké les demandes mal orthographiées des utilisateurs pour ce faire, ce qui n'est pas une option pour moi.

Stéphanie C
la source
Je suggère d'utiliser une vraie base de données qui prend en charge la correspondance de chaînes floues: posgres . Ce sera efficace.
Emre
États-Unis uniquement, canadien, britannique, français, japonais, multi-pays ...? Vraisemblablement pour chacun, vous déterminez / devinez d'abord de quelle langue et de quel pays il s'agit, puis appliquez un classificateur spécifique au pays? Avez-vous un ensemble de formation et si oui quelle est sa répartition des pays?
smci
Où en êtes-vous arrivé là? La solution que nous avons conçue était de frotter et d'enrichir les adresses et les noms de lieux, de frapper le géocodage de Google et de placer des API Web, puis de faire des calculs approximatifs pour déterminer le résultat correct par rapport aux données brutes. C'est un peu maladroit mais fonctionne mais il doit y avoir un moyen plus élégant de normaliser les adresses et les lieux / emplacements.
Chris Smith

Réponses:

9

Lorsque vous utilisez R, vous souhaiterez peut-être examiner le package stringdist et la métrique de distance Jaro-Winkler qui peut être utilisée dans les calculs. Cela a été développé au US Census Bureau pour la liaison.

Voir pour plus d'informations sur la distance Jaro et Jaro-Winkler dans ce journal .

Pour une comparaison des différentes techniques d'appariement, lisez cet article

phiver
la source
4

Il existe de nombreuses façons intelligentes d'étendre la distance Levenshtein pour donner une image plus complète. Une brève introduction à un module assez utile (pour python) appelé ' Fuzzy Wuzzy ' est ici par l'équipe de SeatGeek.

Quelques choses que vous pouvez faire sont la similitude partielle des chaînes (si vous avez des chaînes de longueur différente, disons m & n avec m <n), alors vous ne correspondez qu'à m caractères. Vous pouvez également séparer la chaîne en jetons (mots individuels) et voir comment les ensembles de jetons correspondent ou les organiser par ordre alphabétique et les ordonner.

dmb
la source
4

Une autre technique populaire pour détecter les correspondances de chaînes partielles (bien que généralement au niveau du document) est le bardage . Il s'agit essentiellement d'une approche à fenêtre mobile qui extrait un ensemble de n-grammes pour le mot / doc cible et les compare aux ensembles de n-grammes pour d'autres mots / doc via le coefficient de Jaccard . Manning et ses collègues (2008) discutent des quasi-doublons et du zona dans le contexte de la recherche d'informations.

Brandon Loudermilk
la source
4

J'ai écrit un matcher flou probabaliste générique en Python qui fera un travail raisonnable pour faire correspondre n'importe quel type de données:

https://github.com/robinl/fuzzymatcher

Il est en mémoire, donc vous ne voudrez probablement pas l'utiliser pour faire correspondre des ensembles de données qui dépassent environ 100 000 lignes.

J'ai également écrit un projet similaire spécifique aux adresses britanniques, mais cela suppose que vous avez accès à Addressbase Premium. Celui-ci n'est pas en mémoire, il a donc été utilisé contre les 100 millions d'adresses britanniques. Vois ici:

https://github.com/RobinL/AddressMatcher

Si vous voulez que cela fonctionne rapidement, je vous recommande d'utiliser libpostal pour normaliser vos adresses, puis de les alimenter dans mon fuzzymatcher générique ( pip install fuzzymatcher).

Vous pouvez trouver des exemples d'utilisation ici .

RobinL
la source
Salut Robin, je suis intéressé par votre bibliothèque AddressMatcher. Avez-vous une documentation sur la façon de l'utiliser? J'ai ce problème exact - besoin de faire correspondre 1 ensemble d'adresses (en désordre) à un autre (adresses postales officielles). Merci
SCool
1
malheureusement avec l'adresseur d'adresse ce n'est pas du tout trivial et je n'ai pas une bonne documentation. la principale chose dont vous avez besoin est de charger addressbase premium, un produit commercial, dans postgresql.
RobinL
Ok, merci de me revenir. Je travaille avec je suppose que la version irlandaise d'Adbasebase premium appelée Eircode sera incompatible. Pensez-vous que la correspondance floue serait à la hauteur de la correspondance d'adresses de l'environnement de production? Je veux juste ajouter des codes postaux à des adresses dans mes données qui n'en ont pas, par exemple rechercher la base de données Eircode '1 Main Street, Some Town, County'et si je trouve une correspondance - ramener le code postal.
SCool
1
matcher floue - oui je pense vraiment que ça vaut le coup. cela devrait fonctionner raisonnablement bien pour une petite liste d'adresses à trouver dans une grande liste d'adresses autorisées (c'est-à-dire un eircode) sur une machine costaud. Une autre option est le pacakge fastlink dans R
RobinL