Cara menentukan apakah urutan karakter adalah kata bahasa Inggris atau noise

Jenis fitur apa yang akan Anda coba ekstrak dari daftar kata untuk diprediksi di masa depan, apakah itu kata yang ada atau hanya karakter yang berantakan?

Ada deskripsi tugas yang saya temukan di sana .

Anda harus menulis sebuah program yang dapat menjawab apakah kata yang diberikan adalah bahasa Inggris. Ini akan mudah - Anda hanya perlu mencari kata di kamus - tetapi ada batasan penting: program Anda tidak boleh lebih besar dari 64 KiB.

Jadi, saya pikir mungkin untuk menggunakan regresi logistik untuk menyelesaikan masalah. Saya tidak memiliki banyak pengalaman dengan penambangan data tetapi tugas ini menarik bagi saya.

Terima kasih.

Selama NLP dan analisis teks, beberapa varietas fitur dapat diekstraksi dari dokumen kata yang digunakan untuk pemodelan prediktif. Ini termasuk yang berikut ini.

ngram

Ambil sampel acak kata-kata dari words.txt . Untuk setiap kata dalam sampel, ekstrak setiap bi-gram surat yang mungkin. Misalnya, kata strength terdiri dari dua gram ini: { st , tr , re , en , ng , gt , th }. Kelompokkan dengan bi-gram dan hitung frekuensi masing-masing bi-gram dalam korpus Anda. Sekarang lakukan hal yang sama untuk tri-gram, ... sampai n-gram. Pada titik ini Anda memiliki gambaran kasar tentang distribusi frekuensi bagaimana huruf Romawi digabungkan untuk membuat kata-kata bahasa Inggris.

ngram + batas kata

Untuk melakukan analisis yang tepat, Anda mungkin harus membuat tag untuk menunjukkan n-gram pada awal dan akhir kata, ( anjing -> { ^ d , do , og , g ^ }) - ini memungkinkan Anda untuk menangkap fonologis / ortografi kendala yang mungkin terlewatkan (misalnya, urutan ng tidak pernah terjadi pada awal kata asli Inggris, sehingga urutan ^ ng tidak diizinkan - salah satu alasan mengapa nama Vietnam seperti Nguy Ngn sulit diucapkan untuk penutur bahasa Inggris) .

Sebut koleksi gram ini word_set . Jika Anda membalikkan urutkan berdasarkan frekuensi, gram paling sering Anda akan berada di bagian atas daftar - ini akan mencerminkan urutan paling umum di kata-kata bahasa Inggris. Di bawah ini saya menunjukkan beberapa kode (jelek) menggunakan paket {ngram} untuk mengekstrak huruf ngram dari kata-kata lalu menghitung frekuensi gram:

#' Return orthographic n-grams for word
#' @param w character vector of length 1
#' @param n integer type of n-gram
#' @return character vector
#' 
getGrams <- function(w, n = 2) {
  require(ngram)
  (w <- gsub("(^[A-Za-z])", "^\\1", w))
  (w <- gsub("([A-Za-z]$)", "\\1^", w))


  # for ngram processing must add spaces between letters
  (ww <- gsub("([A-Za-z^'])", "\\1 \\2", w))
  w <- gsub("[ ]$", "", ww)

  ng <- ngram(w, n = n)
  grams <- get.ngrams(ng)
  out_grams <- sapply(grams, function(gram){return(gsub(" ", "", gram))}) #remove spaces
  return(out_grams)
}

words <- list("dog", "log", "bog", "frog")
res <- sapply(words, FUN = getGrams)
grams <- unlist(as.vector(res))
table(grams)

## ^b ^d ^f ^l bo do fr g^ lo og ro 
##  1  1  1  1  1  1  1  4  1  4  1 

Program Anda hanya akan mengambil urutan karakter yang masuk sebagai input, memecahnya menjadi gram seperti yang dibahas sebelumnya dan membandingkannya dengan daftar gram teratas. Jelas Anda harus mengurangi top picks Anda agar sesuai dengan persyaratan ukuran program .

konsonan & vokal

Fitur atau pendekatan lain yang mungkin adalah melihat urutan vokal konsonan. Konversi pada dasarnya semua kata dalam string konsonan vokal (misalnya, pancake -> CVCCVCV ) dan ikuti strategi yang sama yang telah dibahas sebelumnya. Program ini mungkin bisa jauh lebih kecil tetapi akan menderita dari akurasi karena itu mengabstraksi telepon menjadi unit tingkat tinggi.

nchar

Fitur lain yang bermanfaat adalah panjang string, karena kemungkinan kata-kata bahasa Inggris yang sah berkurang ketika jumlah karakter meningkat.

library(dplyr)
library(ggplot2)

file_name <- "words.txt"
df <- read.csv(file_name, header = FALSE, stringsAsFactors = FALSE)
names(df) <- c("word")

df$nchar <- sapply(df$word, nchar)
grouped <- dplyr::group_by(df, nchar)
res <- dplyr::summarize(grouped, count = n())
qplot(res$nchar, res$count, geom="path", 
      xlab = "Number of characters", 
      ylab = "Frequency", 
      main = "Distribution of English word lengths in words.txt",
      col=I("red"))

Analisis Kesalahan

Jenis kesalahan yang dihasilkan oleh jenis mesin ini harus berupa kata-kata yang tidak masuk akal - kata-kata yang terlihat seperti kata-kata bahasa Inggris tetapi tidak (misalnya, ghjrtg akan ditolak dengan benar (benar negatif) tetapi barkle akan secara keliru diklasifikasikan sebagai kata bahasa Inggris (false positive)).

Menariknya, zyzzyvas akan ditolak secara keliru (false negative), karena zyzzyvas adalah kata bahasa Inggris yang nyata (setidaknya menurut words.txt ), tetapi urutan gramnya sangat langka dan dengan demikian tidak mungkin berkontribusi banyak kekuatan diskriminatif.