如何判断字符序列是英文单词还是噪音

数据挖掘 机器学习 nlp 文本挖掘 算法
2021-09-27 05:17:05

您将尝试从单词列表中提取什么样的特征以供将来预测,是现有的单词还是只是一堆乱七八糟的字符?

有我在那里找到的任务的描述。

你必须编写一个程序来回答给定的单词是否是英语。这很容易——你只需要在字典中查找这个词——但是有一个重要的限制:你的程序不能大于 64 KiB。

所以,我认为可以使用逻辑回归来解决问题。我在数据挖掘方面没有太多经验,但这项任务对我来说很有趣。

谢谢。

1个回答

在 NLP 和文本分析期间,可以从单词文档中提取多种特征以用于预测建模。其中包括以下内容。

ngram

从words.txt中随机抽取单词样本对于样本中的每个单词,提取每个可能的双元字母。例如,单词强度由这些二元组组成:{ st , tr , re , en , ng , gt , th }。按二元组分组并计算语料库中每个二元组的频率。现在对 tri-grams 做同样的事情,......一直到 n-grams。至此,您对罗马字母组合生成英文单词的频率分布有了大致的了解。

ngram + 单词边界

要进行正确的分析,您可能应该在单词的开头和结尾创建标签来指示 n-gram,( dog -> { ^d , do , og , g^ }) - 这将允许您捕获语音/正字法否则可能会被遗漏的约束(例如,序列ng永远不会出现在母语英语单词的开头,因此序列^ng是不允许的 - 像Nguyễn这样的越南名字很难为英语使用者发音的原因之一) .

将此克集合称为word_set如果您按频率反向排序,您最常见的克将位于列表顶部 - 这些将反映英语单词中最常见的序列。下面我展示了一些(丑陋的)代码,使用包{ngram}从单词中提取字母 ngrams 然后计算 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 

您的程序只会将传入的字符序列作为输入,将其分解为前面讨论的克,并与顶级克列表进行比较。显然,您将不得不减少您的 top n 选择以适应程序大小的要求

辅音和元音

另一个可能的特征或方法是查看辅音元音序列。基本上转换辅音元音字符串中的所有单词(例如pancake -> CVCCVCV)并遵循之前讨论的相同策略。这个程序可能要小得多,但它会受到准确性的影响,因为它将电话抽象为高阶单元。

nchar

另一个有用的特性是字符串长度,因为合法英语单词的可能性随着字符数的增加而减少。

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"))

词长分布

错误分析

这种类型的机器产生的错误类型应该是无意义的单词——看起来应该是英语单词但实际上不是的单词(例如,ghjrtg会被正确拒绝(真否定)但barkle会被错误地归类为英语单词(假阳性))。

有趣的是,zyzzyvas会被错误地拒绝(假阴性),因为zyzzyvas是一个真正的英文单词(至少根据words.txt),但它的 gram 序列非常罕见,因此不太可能提供太多的区分能力。