Saya tidak yakin apakah pertanyaan ini ada di sini dan saya minta maaf jika tidak. Apa yang ingin saya lakukan adalah mengembangkan cara terprogram di mana saya bisa menentukan apakah string yang diberikan "milik" dalam sekumpulan string. Sebagai contoh, jika saya memiliki sekantong 10.000 nama kota AS, dan kemudian saya memiliki string "Philadelphia", saya ingin beberapa ukuran kuantitatif tentang seberapa besar kemungkinan 'Philadelphia' adalah nama kota AS berdasarkan nama kota AS yang telah saya ketahui. Meskipun saya tahu saya tidak akan dapat memisahkan nama kota asli dari nama kota palsu dalam konteks ini, saya setidaknya berharap memiliki string seperti "123.75" dan "Rubah merah cepat melompati anjing cokelat malas" tidak termasuk yang diberikan ambang batas.
Untuk memulai, saya telah melihat Levenshtein Distance dan mencari-cari sedikit tentang bagaimana hal itu diterapkan pada masalah setidaknya agak mirip dengan yang saya coba pecahkan. Satu aplikasi menarik yang saya temukan adalah deteksi plagiarisme, dengan satu makalah yang menjelaskan bagaimana jarak Levenshtein digunakan dengan algoritma Smith-Waterman yang dimodifikasi untuk menilai kertas berdasarkan pada seberapa besar kemungkinan mereka adalah versi plagarized dari kertas dasar yang diberikan. Pertanyaan saya adalah apakah ada orang yang bisa mengarahkan saya ke arah yang benar dengan algoritma atau metodologi yang sudah ada yang mungkin membantu saya. Saya merasa ini mungkin masalah yang seseorang pernah coba atasi tetapi sejauh ini Google-fu saya gagal.
Jawaban:
Beberapa statistik yang lebih baik untuk dipikirkan adalah panjang kata dan analisis gram. Untuk panjang kata, Anda dapat mengumpulkan statistik distribusi panjang kata dari nama kota, dan membandingkannya dengan panjang yang Anda dapatkan. analisis gram melihat distribusi urutan huruf dalam teks sampel Anda (katakanlah ). Kedua pendekatan tersebut dapat digabungkan.n n n n = 2
Dengan adanya heuristik, Anda dapat menggunakan kemungkinan untuk mendapatkan skor yang (semoga) lebih tinggi untuk data sampel Anda daripada teks lainnya. Untuk menentukan ambang yang wajar, Anda dapat melakukan validasi silang. Pilih satu set frasa sampel yang bukan nama kota. Bagilah nama kota menjadi dua bagian, sebagian besar (katakanlah 80%) dan sebagian kecil (katakanlah 20%). Latih model Anda pada sebagian besar (yaitu, kumpulkan statistik pada sebagian besar), dan kemudian evaluasi model Anda pada bagian kecil dan pada sampel frasa buruk. Tentukan apakah ada ambang batas yang masuk akal yang melewati sebagian besar nama kota, tetapi hanya sejumlah kecil frasa buruk.
sumber