65.9K
CodeProject 正在变化。 阅读更多。
Home

贝叶斯 n-gram 集成“垃圾邮件”分类器

ddrogahn
starIconstarIconstarIcon
emptyStarIcon
starIcon
emptyStarIcon

3.67/5 (3投票s)

2018年3月5日

CPOL

4分钟阅读

viewsIcon

4342

downloadIcon

224

一种使用词语和字符 n-gram 以及贝叶斯定理统计分析的弹性文本分类器

引言

没有人喜欢垃圾邮件——机器如何自动标记垃圾邮件？

一条消息如果不包含多少垃圾邮件，它就是垃圾邮件吗？
垃圾邮件需要有多少垃圾邮件词语才能被分类为垃圾邮件、垃圾邮件、垃圾邮件？

文本分类可能很困难，因为人类使用各种语言交流，使用俚语，拼写错误，而且垃圾邮件发送者会不断更新他们的方法。

背景

文本分类方法

  • 关键词和短语：“赢家”、“免费”、“如在…上看到”、“翻倍你的”、“新规则”
    • 不是统计学，只是搜索文本；但垃圾邮件发送者有你难以置信的技巧！
  • 词语统计
    英语中最常见的词是“THE”（其他最高频词是：AND I OF A IS OR AT）...
    • 垃圾邮件发送者可以变得有创意，拼写错误
        “m0rtgage”、“F R E E”、“ca$h”、“\/laGr@”，视觉上相似的 Unicode 字符
    • 垃圾邮件发送者可以粘贴大段文本（例如梅尔维尔或坡的作品）来扰乱统计数据。
    • 一些语言没有单词分隔：中文、日文、泰文
    • 一些语言将单词组合在一起：粘着语
          德语“Rindfleischetikettierungsüberwachungsaufgabenübertragungsgesetz”
    • 减少文本搜索数据的一个常用方法是排除“停用词”
      停用词按定义是最常见的词，移除它们可能会丢失可能有用的上下文。
  • 多词统计（n-gram / shingles）
    多个单词可以为统计提供更多上下文，但需要更多训练数据。
      “你赢了！” vs “赢家是你”
    • 仍然容易受到拼写错误的影响
    • 不同的单词形式会膨胀模型大小
      动词形式/名词-动词一致：单数/复数、性别、时态、正式程度、主语/宾语...
  • 多词+字符统计 <<-- 这是本文将要测试的内容
    • + 多词用于上下文
    • + 回退到较少的词语以处理未训练的短语
    • + 回退到字符以处理未训练的单词
    • + 可以轻松编辑模型，并快速重新运行它
    • - 模型尺寸大
    •   维基百科大小示例
        ~10 种语言，每种语言减少到 ~300k n-gram（每种 n-gram 类型 50k）
        以 GB 为单位下载和解压
        在多核上花费数小时将一种语言文本减少到词频数据
        并使用约 1GB RAM 加载已缩减的模型
        可以有效地识别一个包含几个单词的语言片段（例如，一本书或戏剧的名称）
    • - 运行：大型模型速度不是超快，但优化后也不是很慢...
      * 可调整：预处理、gram 大小/权重、模型大小、多线程
    • 人工神经网络
      * 一个快速发展的领域；有许多，许多选择
      • 可能难以至乎不可能追溯为什么某些东西有效或无效
      • 大规模训练可能耗时且需要大量硬件资源
      • 编辑模型通常需要重新训练

概率与统计

贝叶斯规则：P(A|B) = P(B|A) * P(A) / P(B)

在 B 发生的情况下 A 发生的概率 = 在 A 发生的情况下 B 发生的概率 * 任何时候 A 发生的概率 / 任何时候 B 发生的概率

应用于垃圾邮件
P(垃圾邮件 | 词语) = P(词语 | 垃圾邮件) * P(垃圾邮件) / ( P(词语 | 垃圾邮件) + P(词语 | 非垃圾邮件) )

链式法则：P(A & B) = P(A) * P(B)

优化：乘法比加法慢，而且非常小的数字可能会下溢
所以使用对数
Log(A * B) = Log(A) + Log(B)
Log(A / B) = Log(A) - Log(B)

模糊逻辑：现实世界的状态可能不像我们建模的那样是二元的

如果未知的未知数比假设的要大，或者涉及隐藏变量...
那么假设一个事物排除另一个事物可能不安全：P(A) = 1 - P(B)

一条消息（或网页）可能同时包含垃圾邮件和非垃圾邮件，或者是一门模型无法做出明智决定的外语。

文本预处理：以可重复的方式标准化空格、处理符号、数字等极其重要。

Using the Code

var bec = new BayesEnsembleClassifier();
bec.Train(files);
bec.TrainPost();

bec.Test(filename_test);

//-Run the test data with increasingly misspelled words
for (int r = 5; r <= 95; r += 5) {
	bec.TestRandom(filename_test, randomness);
}

训练步骤对文本进行分词，去除 HTML，并为垃圾邮件和非垃圾邮件构建 1-3 个单词的 n-gram shingles 和 3、5、7 个字符的频率表。字符 gram 可以跨越单词。n-gram 的权重和大小/长度是可定制的。

类别是动态的（但高效的存储需要更复杂的数据结构来减小尺寸并避免周转）。

例如

  • 前 2 个单词的非垃圾邮件条目是：“. the”、“the .”、“the the”、“and the”...
  • 前 2 个单词的垃圾邮件条目是：“and .”、“to .”、“his .”、“he .”
  • 前垃圾邮件字符 gram 是“ th”、“the”、“ and ”、“ his ”、“ childe”
  • 前非垃圾邮件字符 gram 是“ th”、“the”、“ing”、“ the ”、“ and ”、“ that”、“evermor”

后处理：过滤稀有 n-gram 并预先计算 Log 概率

测试：评估测试文件中的行，并显示 TruePositive/TrueNegative/FalseNegative/FalsePositive & F-Score

TestRandom 在处理前对测试文本进行更改（它会递增随机选择的字符），并显示分数。

关注点

内存使用情况：（提供的训练集）

加载峰值 135MB
加载后 47MB

时序

加载/训练 6809ms（但优化使用会节省缩减和压缩的训练数据）
评估 250ms（提供的测试集：100 条消息，35583 个单词）

弹性

由于模型包含字符 gram，因此即使文本中高达 50% 的字符被更改，它也能成功分类文本。（远超过单个单词可被人眼识别的程度）

% Chars Changed, F-Score, Test Text (partial first line)
 0% 1.00 bust by this expressing at stepped and . my my dreary a and . shaven we spoken
 5% 1.00 bust by this eypressinh at stepped bnd . my my dreary a and . shaven we spoken
10% 1.00 bust by this eypressinh at suepped bnd . my my dreary a and . siaven we spoken
15% 1.00 bust by this eypressinh at suepped bnd . ny my ereary a and . siaven we sppkeo
20% 1.00 bust by this eypressinh at sufpped bnd . ny my ereary a and . siawen we sppkeo
25% 1.00 busu by this eypressinh at sufpped bnd . ny my eseary a and . siawen we sppkeo
30% 1.00 busu by uiis eypressinh at sufpqed bnd . nz my eseary a and . siawen we sppkeo
35% 1.00 busu by uiis eypretsinh at sufpqed bne . nz mz eseary a and . siawen we sppkeo
40% 1.00 busu by uiis eypretsinh at sufpqed boe . nz mz eseary a and . siawen we sppkeo
45% 1.00 busu bz uiis eypretsinh at sufpqed boe . nz mz esfary a and . siawen we sppkeo
50% 0.98 busu bz uijs eypretsinh at sufqqed boe . nz mz esfarz a and . siawen wf sppkeo
55% 0.82 busu bz uijs eypretsinh bt tufqqed boe . nz mz esfarz a and . siawen wf sppkeo
60% 0.49 butu bz uijs eypretsinh bt tufqqed boe . nz mz esfarz a and . siawen wf sppkeo
65% 0.09 butu bz uijt eypretsinh bt tufqqee boe . nz mz esfasz a and . siawfn wf sppkeo
70% 0.00 butu bz uijt eyprftsinh bt tufqqee boe . nz mz esfasz a ane . siawfn wf sppkeo
75% 0.00 butu bz uijt eyprftsinh bt tufqqee boe . nz mz esfbsz a bne . siawfn wf tpplfo
80% 0.00 bvtu bz uijt eyprftsinh bt tufqqee boe . nz nz esfbsz a bne . siawfn wf tpplfo
85% 0.00 cvtu bz uijt eyprfttjnh bt tufqqee boe . nz nz esfbsz a bne . sibwfo wf tqplfo
90% 0.00 cvtu bz uijt eyqrfttjnh bt tufqqee boe . nz nz esfbsz b boe . tibwfo wf tqplfo
95% 0.00 cvtu cz uijt eyqrfttjnh bu tufqqee boe . nz nz esfbsz b boe . tibwfo wf tqplfo

注释

最后的 PredictLine() 有点复杂...
将循环写入多路分组和聚合需要大量的代码。
如果遗漏了什么，LINQ 查询几乎不可能调试。
不知道哪个更糟糕。

历史

  • 2018-03-04：初始帖子
© . All rights reserved.