Maschinelles Lernen zum Parsen von Strings?

30

Ich habe viele Adresszeichenfolgen:

1600 Pennsylvania Ave, Washington, DC 20500 USA

Ich möchte sie in ihre Bestandteile zerlegen:

street: 1600 Pennsylvania Ave
city: Washington
province: DC
postcode: 20500
country: USA

Aber natürlich sind die Daten schmutzig: Sie stammen aus vielen Ländern in vielen Sprachen, sind unterschiedlich geschrieben, enthalten Rechtschreibfehler, fehlen, enthalten zusätzlichen Müll usw.

Gegenwärtig besteht unser Ansatz darin, Regeln in Kombination mit dem Fuzzy-Gazetteer-Matching zu verwenden. Wir möchten jedoch die Techniken des maschinellen Lernens untersuchen. Wir haben Trainingsdaten für betreutes Lernen gekennzeichnet. Die Frage ist, was für ein maschinelles Lernproblem ist das? Es scheint nicht wirklich ein Clustering, eine Klassifizierung oder eine Regression zu sein.

Am ehesten könnte ich mir vorstellen, jedes Token zu klassifizieren, aber dann möchten Sie wirklich alle gleichzeitig klassifizieren, um Bedingungen wie "Es sollte höchstens ein Land geben" zu erfüllen. Tatsächlich gibt es viele Möglichkeiten, einen String zu tokenisieren, und Sie möchten jeden ausprobieren und den besten auswählen.

Also: Welche maschinellen Lerntechniken könnte ich zum Parsen von Adressen ausprobieren?

machine-learning text-mining Jay Hacker
quelle
Ich bin kein Experte für Ihr Problem auf hoher Ebene, wenn es darum geht, eine Antwort zu veröffentlichen, aber ich denke, der erste Schritt zum maschinellen Lernen besteht darin, informative Funktionen zu erstellen und dann die Methode zu wählen, die angesichts ihrer Struktur richtig ist. Sie haben viel Struktur; Alnum vs Non-Alnum-Zeichen, numerische vs Alpha-Token, Token zählt zwischen ',' Splits, numerische Token-Längen. ZB auf ',' aufteilen und zählen, wie viele Token in jeder Aufteilung enthalten sind (Straße, Adresse, Stadt / Bundesland, geospezifische Informationen); Berechnen Sie die Anzahl der numerischen Token (Straße und Postleitzahl). Diese bieten Ihnen Funktionen, auf denen Sie Cluster erstellen können.
Muratoa
Sehen Sie sich Text-Chunking an .
Alt
2
Schauen Sie sich auch die Erkennung benannter Entitäten und die allgemeinere Aufgabe der Informationsextraktion an
Yuval F,
@YuvalF Ich schlage vor, dies zu einer Antwort zu machen. Können Sie etwas näher darauf eingehen, vielleicht ein Beispielpapier, in dem eine ML-Methode angewendet wurde?
Steffen
Ich interessiere mich auch sehr für dieses spezielle Problem, das darin besteht, eine Postanschrift in ihre Bestandteile zu gliedern. Wir versuchen dies auf einem mobilen Gerät ohne Vermutungen über die Konnektivität zu einem Reverse Geo-Coding-Dienst wie Google zu tun. Es ist in Ordnung anzunehmen, dass wir eine Quelle für verknüpfte Daten zu Stadt, Staat, Land und Postleitzahl an Bord haben. Jede Hilfe - egal ob Zeiger - oder die Bereitschaft, sich mit einem verrückten Start-up-Team auf dieses Problem einzulassen, ist herzlich und offen willkommen.

Antworten:

10

Dies kann als Sequenzbeschriftungsproblem angesehen werden , bei dem Sie eine Sequenz von Token haben und für jeden eine Klassifizierung angeben möchten. Sie können versteckte Markov-Modelle (HMM) oder bedingte Zufallsfelder (CRF) verwenden, um das Problem zu lösen. Es gibt gute Implementierungen von HMM und CRF in einem Open-Source-Paket namens Mallet .

In Ihrem Beispiel sollten Sie die Eingabe in das folgende Format konvertieren. Darüber hinaus sollten Sie zusätzliche Funktionen generieren.

1600 STREET
Pennsylvania STREET
Ave STREET
, OUT
Washington CITY
, OUT
DC PROVINCE
20500 POSTCODE
USA COUNTRY
William Fernandes
quelle
1
Ich glaube nicht, dass ein Standard-Sequenz-Tagger (wie ein HMM von CRF) in dieser Situation sehr gute Ergebnisse liefert. Dies liegt an den Einschränkungen, dass die Tag-Gruppen zusammenhängend sind und jedes Tag nur einmal pro Sequenz vorkommt. Ich denke nicht, dass Sie die Suche einfach ändern können, um diese Informationen einzubeziehen, auch nicht aufgrund der Abhängigkeit von vergangenen / zukünftigen Tags mit willkürlicher Entfernung (ich könnte mich dabei jedoch irren).
Alt
@alto Ich glaube, CRF berücksichtigt den benachbarten Kontext. HMM kann den letzten Zustand nicht sehen, Sie haben Recht, dass es wahrscheinlich nicht sehr gut funktioniert.
JT
1

Ich musste ein sehr ähnliches Problem lösen, um zu überprüfen, ob eine Adresse gültig oder ungültig ist.

Typischerweise hat die Adresse die Struktur "1600 Pennsylvania Ave, Washington DC, 20500".

Eine Zeichenfolge wie

"Ich ging 2000 Stufen hinunter und erreichte die Pennsylvania Ave in Washington DC."

ist keine gültige Adresse.

Dies kann durch Klassifikationstechniken wie SVM, Neuronale Netze usw. gelöst werden.

Die Idee besteht darin, einen Schlüsselsatz von Funktionen zu identifizieren. Einige davon könnten sein:

1) Beginnt der Straßenname mit einer gültigen Blocknummer? Die meisten US-Blocknummern sind entweder Zahlen (z. B. 1200) oder eine Zahl, gefolgt von einem einzelnen Buchstaben (120A) oder einer Zahl, die auf einen einzelnen Buchstaben folgt (z. B. S200).

2) Wenn die Adresse gut formatiert ist, enden die Straßennamen in Suffixen wie Ave für Allee, Dr für Laufwerk, Blvd für Boulevard. Es ist möglich, die US-Straßensuffixliste von der USPS-Site zu beziehen.

3) Die Anzahl der Wörter im Adressfeld kann ebenfalls ein interessantes Merkmal sein. Wenn zu viele Wörter vorhanden sind, handelt es sich wahrscheinlich nicht um eine gültige Adresse. ZB siehe obiges Beispiel.

4) Wie viele Wörter kommen zwischen der Blocknummer und dem Straßensuffix im Adressfeld vor?

Diese können verwendet werden, um einen Lernalgorithmus zu trainieren, und das resultierende Modell kann verwendet werden, um zu validieren, ob eine gegebene Adresse gültig ist oder nicht.


quelle
1

Dies ist ein kleiner Hack, für den keine eigene Lösung erforderlich ist: Reverse Geocoding. Dies kann entweder zu saubereren Daten führen oder die gesamte Arbeit für Sie erledigen.

Hier ist zum Beispiel ein Stata-Code geocode3von SSC, der Google verwendet. Ich denke, das ist ähnlich wie bei Fuzzy Gazetteer . Die erste Adresse ist ziemlich unordentlich, die zweite sauber und die dritte fremd. Auch andere Software kann damit umgehen.

clear
set obs 3
gen address =""
replace address = "Big Foot Museum in Felton CA" in 1
replace address = "1600 Pennsylvania Ave, Washington, DC 20500 USA" in 2 
replace address = "ул. Ильинка, д. 23 103132, Москва, Россия" in 3
geocode3, address(address)
gen coord = string(g_lat) + "," + string(g_lon)
geocode3, reverse coord(coord)

Das funktioniert einigermaßen gut:

. list r_addr , clean noobs

                                                                             r_addr  
                                      121 San Lorenzo Avenue, Felton, CA 95018, USA  
    1600 Pennsylvania Avenue Northwest, President's Park, Washington, DC 20500, USA  
                                         ulitsa Ilyinka, 23, Moscow, Russia, 101000

Der Kreml hat ein ganz anderes Format.

Dimitriy V. Masterov
quelle
0

Dies klingt nach einem Problem, das mit einer bidirektionalen LSTM-Klassifizierung gelöst werden muss. Sie kennzeichnen beispielsweise jedes Zeichen der Stichprobe als eine Kategorie

straße: 1 stadt: 2 provinz: 3 postleitzahl: 4 land: 5

1600 Pennsylvania Ave, Washington, DC 20500 USA
111111111111111111111, 2222222222, 33 44444 555

Trainieren Sie nun Ihren Klassifikator anhand dieser Bezeichnungen. Boom!

Fardin
quelle