Teknik pembelajaran mesin untuk string parsing?

30

Saya memiliki banyak string alamat:

1600 Pennsylvania Ave, Washington, DC 20500 USA

Saya ingin mengurai mereka menjadi komponen-komponen mereka:

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

Tetapi tentu saja datanya kotor: itu berasal dari banyak negara dalam banyak bahasa, ditulis dengan cara yang berbeda, mengandung kesalahan ejaan, ada bagian yang hilang, memiliki sampah tambahan, dll.

Saat ini pendekatan kami adalah menggunakan aturan yang dikombinasikan dengan fuzzy gazetteer matching, tetapi kami ingin menjelajahi teknik pembelajaran mesin. Kami telah memberi label data pelatihan untuk pembelajaran yang diawasi. Pertanyaannya adalah, seperti apa masalah pembelajaran mesin ini? Tampaknya tidak benar-benar pengelompokan, atau klasifikasi, atau regresi ....

Yang paling dekat yang bisa saya pikirkan adalah mengklasifikasikan setiap token, tetapi kemudian Anda benar-benar ingin mengklasifikasikan semuanya secara bersamaan, memuaskan kendala seperti "paling banyak harus ada satu negara;" dan benar-benar ada banyak cara untuk tokenize string, dan Anda ingin mencoba masing-masing dan memilih yang terbaik .... Saya tahu ada sesuatu yang disebut penguraian statistik, tetapi tidak tahu apa-apa tentang itu.

Jadi: teknik pembelajaran mesin apa yang bisa saya eksplorasi untuk mengurai alamat?

Jay Hacker
sumber
Saya bukan ahli dalam masalah tingkat tinggi Anda untuk mengirim jawaban, tapi saya pikir langkah pertama untuk pembelajaran mesin adalah membangun fitur informatif, lalu memilih metode yang tepat sesuai struktur mereka. Anda memiliki banyak struktur; alnum vs karakter non-alnum, numerik vs alpha token, jumlah token antara ',' split, panjang token numerik. mis. belah pada ',' dan hitung berapa banyak token di setiap pemisahan (alamat jalan vs kota / negara bagian vs info spesifik geografis); calc strlen token numerik (alamat jalan vs kode pos). Ini memberi Anda fitur yang dapat dikelompokkan.
muratoa
Lihatlah chunking teks .
alto
2
Lihat juga pengakuan entitas yang diberi nama , dan tugas yang lebih umum dari Pengambilan Informasi
Yuval F
@YuvalF Saya sarankan untuk membuat ini sebagai jawaban. Bisakah Anda menguraikan sedikit, mungkin kertas contoh di mana metode ML telah digunakan?
steffen
Saya juga sangat tertarik dengan masalah khusus ini - yang menyusun alamat surat menjadi bagian-bagian komponennya. Kami berusaha melakukan ini di perangkat seluler tanpa anggapan tentang konektivitas ke layanan geo-coding terbalik seperti googles. Tidak apa-apa untuk menganggap bahwa kami memiliki sumber data terkait yang terhubung terkait kota, negara bagian, negara, dan zip. Bantuan apa pun - salah satu petunjuk - atau bersedia untuk terlibat dengan tim startup gila tentang masalah ini dengan senang hati dan terbuka.

Jawaban:

10

Ini dapat dilihat sebagai masalah pelabelan urutan , di mana Anda memiliki urutan token dan ingin memberikan klasifikasi untuk masing-masingnya. Anda dapat menggunakan model Markov tersembunyi (HMM) atau bidang acak bersyarat (CRF) untuk menyelesaikan masalah. Ada implementasi HMM dan CRF yang baik dalam paket sumber terbuka yang disebut Mallet .

Dalam contoh Anda, Anda harus mengonversi input ke format di bawah ini. Selain itu, Anda harus menghasilkan fitur tambahan.

1600 STREET
Pennsylvania STREET
Ave STREET
, OUT
Washington CITY
, OUT
DC PROVINCE
20500 POSTCODE
USA COUNTRY
William Fernandes
sumber
1
Saya tidak berpikir urutan tagger standar (seperti HMM CRF) akan menghasilkan hasil yang sangat baik dalam situasi ini. Ini disebabkan oleh pembatasan bahwa grup tag bersebelahan dan bahwa setiap tag hanya muncul satu kali per urutan. Saya tidak berpikir Anda dapat dengan mudah memodifikasi pencarian untuk memasukkan informasi ini baik karena ketergantungan pada tag masa lalu / masa depan dari jarak sewenang-wenang (saya bisa salah tentang ini).
alto
@alto Saya percaya CRF mempertimbangkan konteks tetangga. HMM tidak bisa melihat kondisi masa lalu, Anda benar bahwa itu mungkin tidak akan bekerja dengan baik
JT
1

Saya harus memecahkan masalah yang sangat mirip untuk memvalidasi apakah suatu alamat valid atau tidak.

Biasanya alamat memiliki struktur "1600 Pennsylvania Ave, Washington DC, 20500"

Sebuah string seperti

"Aku turun 2000 langkah dan mencapai Pennsylvania Ave di Washington DC."

bukan alamat yang valid.

Ini dapat diselesaikan dengan teknik klasifikasi seperti SVM, Neural Networks dll.

Idenya adalah untuk mengidentifikasi serangkaian fitur utama. Beberapa di antaranya adalah:

1) Apakah nama jalan dimulai dengan nomor blok yang valid. Sebagian besar nomor blok AS adalah angka (mis. 1200) atau angka yang diikuti oleh satu huruf (120A) atau angka yang mengikuti satu huruf (misalnya S200).

2) Jika alamat diformat dengan baik, nama jalan berakhiran sufiks seperti Ave untuk jalan, Dr untuk Drive, Blvd untuk Boulevard. Dimungkinkan untuk mendapatkan daftar sufiks jalanan AS dari situs USPS.

3) Jumlah kata di bidang alamat jalan juga bisa menjadi fitur yang menarik. Jika ada terlalu banyak kata, mungkin itu bukan alamat yang valid. Misalnya lihat contoh di atas.

4) Berapa banyak kata yang muncul antara nomor blok dan akhiran jalan di bidang alamat?

Ini dapat digunakan untuk melatih algoritma pembelajaran dan model yang dihasilkan dapat digunakan untuk memvalidasi apakah alamat yang diberikan valid atau tidak.


sumber
1

Ini sedikit peretasan yang tidak memerlukan solusi Anda sendiri: membalikkan geocoding. Ini bisa memberi Anda data yang lebih bersih atau benar-benar melakukan semua pekerjaan untuk Anda.

Misalnya, inilah beberapa kode Stata dengan geocode3dari SSC, yang menggunakan Google. Saya kira ini mirip dengan Fuzzy Gazetteer . Alamat pertama cukup berantakan, yang kedua bersih, dan yang ketiga adalah asing. Perangkat lunak lain dapat menangani ini juga.

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)

Ini bekerja dengan cukup baik:

. 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  

Kremlin memang memiliki format yang sangat berbeda.

Dimitriy V. Masterov
sumber
0

Ini terdengar seperti masalah yang harus dipecahkan dengan klasifikasi LSTM dua arah. Anda menandai setiap karakter sampel sebagai satu kategori misalnya

jalan: 1 kota: 2 provinsi: 3 kode pos: 4 negara: 5

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

Sekarang, latih classifier Anda berdasarkan label ini. Ledakan!

Fardin
sumber