Bagaimana cara melakukan pencocokan alamat pos fuzzy?

14

Saya ingin tahu cara mencocokkan alamat pos ketika formatnya berbeda atau ketika salah satu dari mereka salah eja.

Sejauh ini saya telah menemukan solusi yang berbeda tetapi saya pikir mereka sudah cukup tua dan tidak terlalu efisien. Saya yakin ada beberapa metode yang lebih baik, jadi jika Anda memiliki referensi untuk saya baca, saya yakin itu adalah subjek yang mungkin menarik minat beberapa orang.

Solusi yang saya temukan (contohnya dalam R):

  • Levenshtein distance, yang sama dengan jumlah karakter yang harus Anda sisipkan, hapus atau ubah untuk mengubah satu kata menjadi yang lain.

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

  • Perbandingan fonem

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

  • Penggunaan koreksi ejaan (akhirnya yang bayesian seperti Peter Norvig) , tapi tidak terlalu efisien pada alamat kurasa.

  • Saya berpikir untuk menggunakan saran dari Google menyarankan, tetapi juga, itu tidak sangat efisien pada alamat pos pribadi.

  • Anda dapat membayangkan menggunakan pendekatan yang diawasi pembelajaran mesin tetapi Anda harus menyimpan permintaan yang salah eja dari pengguna untuk melakukannya yang bukan merupakan pilihan bagi saya.

text-mining data-cleaning Stéphanie C
sumber
Saya sarankan menggunakan database nyata yang mendukung pencocokan string fuzzy: posgres . Itu akan efisien.
Emre
Hanya AS, Kanada, Inggris, Prancis, Jepang, multi-negara ...? Agaknya untuk masing-masing, pertama-tama Anda menentukan / menebak bahasa dan negara apa itu, lalu menerapkan klasifikasi negara tertentu? Apakah Anda memiliki perangkat pelatihan dan jika demikian, apa distribusinya terhadap negara?
smci
Di mana Anda berakhir dengan ini? Solusi yang kami buat adalah untuk menggosok dan memperkaya alamat dan nama tempat dan menekan geocoding google dan menempatkan API web dan kemudian melakukan beberapa perhitungan kasar untuk menentukan hasil yang benar dibandingkan dengan data mentah. Agak kikuk tetapi berfungsi tetapi harus ada cara yang lebih elegan untuk menormalkan alamat dan tempat / lokasi.
Chris Smith

Jawaban:

9

Saat Anda menggunakan R, Anda mungkin ingin melihat ke dalam paket stringdist dan metrik jarak Jaro-Winkler yang dapat digunakan dalam perhitungan. Ini dikembangkan di Biro Sensus AS untuk dihubungkan.

Lihat untuk informasi lebih lanjut tentang jarak Jaro dan Jaro-Winkler di jurnal ini .

Untuk perbandingan berbagai teknik pencocokan, baca makalah ini

Phiver
sumber
4

Ada banyak cara pintar untuk memperluas jarak Levenshtein untuk memberikan gambaran yang lebih lengkap. Pengenalan singkat ke modul yang cukup berguna (untuk python) bernama ' Fuzzy Wuzzy ' ada di sini oleh tim di SeatGeek.

Beberapa hal yang dapat Anda lakukan adalah kesamaan string parsial (jika Anda memiliki string panjang yang berbeda, katakan m & n dengan m <n), maka Anda hanya cocok dengan karakter m. Anda juga dapat memisahkan string menjadi token (kata-kata individual) dan melihat bagaimana set token cocok atau mengaturnya secara alfabet dan memesannya.

dmb
sumber
4

Teknik populer lainnya untuk mendeteksi kecocokan string parsial (meskipun biasanya di tingkat dokumen) adalah shingling . Pada dasarnya ini adalah pendekatan jendela bergerak yang mengekstrak seperangkat n-gram untuk kata target / doc dan membandingkannya dengan set n-gram untuk kata / dokumen lain melalui koefisien Jaccard . Manning dan rekan (2008) membahas duplikat dekat dan shingling dalam konteks pengambilan informasi.

Brandon Loudermilk
sumber
4

Saya telah menulis sebuah pencocokan fuzzy probabalistic generik dengan Python yang akan melakukan pekerjaan yang wajar untuk mencocokkan semua jenis data:

https://github.com/robinl/fuzzymatcher

Ada dalam memori, jadi Anda mungkin tidak ingin menggunakannya untuk mencocokkan dataset yang di atas sekitar 100rb baris.

Saya juga telah menulis proyek serupa untuk alamat Inggris, tetapi ini mengasumsikan Anda memiliki akses ke Addressbase Premium. Yang ini tidak ada dalam memori, jadi telah digunakan terhadap 100m atau lebih alamat UK. Lihat disini:

https://github.com/RobinL/AddressMatcher

Jika Anda ingin menjalankan ini dengan cepat, saya akan merekomendasikan menggunakan libpostal untuk menormalkan alamat Anda dan kemudian memasukkannya ke fuzzymatcher generik saya ( pip install fuzzymatcher).

Anda dapat menemukan contoh penggunaan di sini .

RobinL
sumber
Halo Robin, saya tertarik dengan perpustakaan AddressMatcher Anda. Apakah Anda memiliki dokumentasi tentang cara menggunakannya? Saya memiliki masalah persis ini - harus mencocokkan 1 set alamat (berantakan) dengan yang lain (alamat pos resmi). Terima kasih
SCool
1
sayangnya dengan pencocokan alamat itu sama sekali tidak sepele dan saya tidak memiliki dokumentasi yang baik. hal utama yang Anda butuhkan adalah memuat addressbase premium, produk komersial, ke postgresql.
RobinL
Ok, terima kasih sudah kembali padaku. Saya bekerja dengan saya kira versi Irlandia premium Addressbase disebut Eircode yang tidak akan kompatibel. Apakah Anda pikir pencocokan fuzzy akan sesuai dengan tugas dalam pencocokan alamat lingkungan produksi? Saya hanya ingin menambahkan kode pos ke alamat dalam data saya yang tidak memilikinya, mis. Cari databse Eircode '1 Main Street, Some Town, County'dan jika saya menemukan kecocokan - bawa kembali kode pos.
SCool
1
fuzzy matcher - ya saya pikir layak untuk dicoba. itu harus bekerja dengan cukup baik untuk daftar alamat yang bertubuh kecil untuk ditemukan dalam daftar besar alamat otorisasi (yaitu eircode) pada mesin gemuk. Pilihan lain adalah pacakge fastlink di R
RobinL