基于统计概率和机器学习的文本分类技术 —— 社区产品机器审核机制预研报告

基于统计概率和机器学习的文本分类技术

—— 社区产品机器审核机制

一、现状

目前，所在公司社区类产品（论坛、博客、百科）每天都会接收到大量的垃圾、灌水信息，高峰期16小时内（晚6点以后到第二天9点前）可以达到十万量级。大量的人力、时间被浪费在删除、屏蔽这些重复无用信息上，从而导致无法更好地为客户服务。用人工审核的方式去对抗机器发帖，类似于二战时的“长矛战坦克”。如果继续采用这种方式，正在和未来可能面临的问题主要一下几点：

• 未来版本量增加导致人工审核压力的增大。
• 目前负责版本审核的人员约2-3人/天，基本能保证答案在4-5小时内被审核，但该速度不是令大多数用户满意的
• 对于百科wiki类产品，除了判别是否违禁以外，还有一个需求，就是客户答案是否与问题确实相关。wiki的审核大多牵扯到一个多版本问题。由于审核延迟，可能造成部分答案有多个版本，而后面的用户在回答时不能看到前面用户的版本，故不是在原来答案基础上做修改，造成多个版本质量接近或后面的版本质量不高，被退回影响用户通过率和使用体验；
• 特定任务中部分功能的实现遇到问题。任务中的倒计时功能，由于审核有延迟，不能做自动到时结束，必须人工审核完成后人工手动结束

总结目前产品中常见的垃圾广告主要有以下特点：

• 批量垃圾信息是同几拨人发的，只是内容变来变去，感觉像专门的发帖公司。
• 现在大都采取变换不同ID发帖的方式，导致黑名单方式不可用
• 有些会在帖子标题中加很多符号或标点等分隔符隔断内容，所以之前尝试将他们的热线电话的号码加到违禁词里的办法，效果也不佳；另外还有火星文等样式

目前，了解到同行百科类网站审核情况如下

• 百度知道：先发后审，机器过滤+人工检举
• 搜搜问问：机器审核，能够计算出比较准确的审核时间，基本在5分钟以内
• 百度百科：先审后发，机器过滤+人工审核，人工审核为主，所需时间从几分钟到小时不等，且晚上23：00以后没有审核不生成新版本
• 互动百科：先发后审，人工审核，所需时间平均8小时左右

二、背景

在日常生活中，人们往往进行常识推理，而这种推理通常并不是十分准确的。例如，你看见一个头发潮湿的人走进来，你可能会认为外面下雨了，那你也许错了；如果你在公园里看到一男一女走得很近，你可能会认为他们是情侣，你可能也犯了错误。对结果的预测往往是建立在原有经验积累的基础上，并对现有现象各个特征分别属于某一结果的概率加权。

基于贝叶斯定理的进行分类或决策需要一系列特征向量（即某些东西，它们或存在、或不存在、或部分存在于某个分类中）。比如对于一套可以根据照片识别男女性别的系统，它决策所依赖的特征向量可能就是眼睛、鼻梁、脸庞、发型等；用它正确识别张靓颖的成功率就要高于李宇春，因为后者的许多特征向量的没有明显的倾向性。

对文本过滤来说，特征向量就是某段给定文本的各个词语。贝叶斯决策优于常用敏感词库过滤的一个重要原因在于，它考虑到了文本的上下问环境。我们先考虑简单的情况（不考虑中文分词），以英语为例，假设我们需要一个系统来识别一段包含单词python的文本，究竟应该是属于编程类，还是生物类。首先，我们需要模拟人知识积累的过程，给计算机一些已有的样本进行学习，如下表所示。

文本	归类（Bio or Pro）
Pythons are constrictors that feed on birds and mammals	Bio
Python was originally developed as a scripting language	Pro
A 49-ft.-long python was found in China	Bio
Python has dynamic type system	Pro
Python with vivid scales	Bio
An Open source project developed by python	Pro
……	……

我们统计各特征向量（单词）在各类别（编程类或生物类）中出现的频率，得到类似如下的结果：

词	Pro	Bio
dynamic	0.6	0.1
constrictor	0.0	0.6
long	0.1	0.2
source	0.3	0.1
and 0.95	0.95
……	……	……

使用足够多的数据进行训练，上表的结果就很有意思。dynamic相对较常出现在编程类的文本中，而constrictor则相对较常出现在生物类的文本中，而source和long就没有那么强的倾向性。另外，像and这些词，它在各类目中出现的频率几乎一样（因为基本每篇文章中都会用到and），所以对于机器学习来说没有任何价值，这类词我们称为“停用词”（stop word），意味着以后在样本训练之前可以将它们去除，从而减少学习时间。几乎每个搜索引擎都会维护一份“停用词表”（stop word list），后面的章节会讲到如何使用它。

在使用贝叶斯分类器之前，让我们先来看看以下定义：
1.Pr(Category)：属于某一特定分类的概率，先验概率
2.Pr(Document)：某一文本的概率，先验概率，对任一文本，其值均为常量，故此值可以忽略
3.Pr(Category|Document)：已知文本A，它属于某一分类的概率，就是我们要求的结果，条件概率、后验概率
4.Pr(Document | Category)：某一分类下，文本A可能出现的概率，条件概率、非后验概率

一般的， Pr(Document | Category) = Pr(Word1 | Category) × Pr(Word2 | Category) × ……，例如“Python is a dynamic language”去除停用词 （is、a）后属于编程类的概率即为Pr(python | Pro) × Pr(dynamic | Pro) × Pr(language | Pro)， 其中各Pr(Word | Category)的值取自前表。事实上，由于Pr(Word | Category) < 1，文本所包含的单词越多，Pr(Document | Category)的结果就越小。但这并非会影响最后的结果，因为我们使用的是各分类的相对值，例如，判断某一段文字是属于编程类还是生物类，计算的是Pr(Document | Pro)/ Pr(Document | Bio)。

使用贝叶斯分类器本质上就是根据先验概率、条件概率求后验概率的过程，描述为
Pr(Category|Document) = Pr(Document | Category) × Pr(Category) / Pr(Document)

事实上，正如前面所说的，Pr(Document)对所有待测文本都是相同的，而我们又只关心相对值，因此该公式可进一步简化为
Pr(Category|Document) = Pr(Document | Category) × Pr(Category)

计算Pr(Category|Document)所需的两个参数搜可以通过类似的方法训练历史数据得到，并且每次计算机决策、运营手工订正后以及错判投诉的结果又都会被加入到样本库中进行修正和再学习，这就是“有监督的机器学习”。

MicroSoft的工程师在Outlook中就使用了这种机制，并在
http://www.gfi.com/whitepapers/why-bayesian-filtering.pdf
阐述了为什么贝叶斯分类器是最有效的文本过滤算法，同时宣称合理的参数设置和足够丰富的样本能保证99.7%的审核正确率。

它的优点：
1、贝叶斯分类器识别整段代词文本内容。它在检索某些常用垃圾词的同时，也会兼顾那些在正常邮件中出现的词语。例如，并不是每封包含“free”和“cash”的邮件都是垃圾邮件，事实上，如果贝叶斯分类器在文本的其它地方发现了商业术语、公司合同等，还是可能会将它归为正常邮件。贝叶斯分类器考虑了上下文的语境，并智能化地使用概率、词频来权衡各词语，这是它与关键词\敏感词算法相比的最大优势。

2、贝叶斯分类器是完全自适应的 —— 它会从垃圾邮件和正常邮件不断地学习、抽取知识，甚至会在对抗中成长 —— 随着新出现的垃圾邮件而进化。比如专业的spammer使用“f-r-e-e”来代替“free”，或是使用“5ex”来代替“sex”，来逃避敏感词库的过滤。对于贝叶斯分类器来说，刚开始它从未见过这个单词，因此可能会将其归为“unknown”；但随着人工审核的复查，它会很快学习到这是个垃圾词。以后，spammer在垃圾帖中使用“f-r-e-e”的效果甚至还不如使用“free”，因为“f-r-e-e”几乎不会出现在正常邮件中，因此分类器更有自信将其归为垃圾邮件（useful/spam的比率更高）。

3、贝叶斯分类会分析用户的行为，更适合与定制化需求。例如对于一家经营五金的公司来说，“mortgage“ 几乎以为着垃圾邮件，但对于一家金融服务公司来说，它很有肯能是正常邮件（起码是”unknown”的） 。

4、贝叶斯分类器与敏感词相比，更适合国际化\多语言。事实上，要维护一份敏感词库十分困难，需要专业人士的参与。贝叶斯分类器采用自然语言分类的方式，某个词语属于垃圾邮件/正常邮件的概率完全由日常的行为所决定，即使是中英文混合的内容，也照常处理。

5、基于贝叶斯分类器的文本过滤机制较难被绕过 。一位高级的 spammer 想要绕过它，无非两种方法，较少采用强垃圾邮件倾向的词（比如free, Viagra等），或是较多采用强正常邮件倾向的词语。一般来说，采用后者较为困难，因为需要了解收件方公司的详细业务，而采用一些中性词（比如public等）对最后的结果有影响甚微。

6、不需要维护、下载、更新敏感词库，贝叶斯分类器是完全可以自循环的

它的缺点：

1、唯一的缺点是需要原始数据的进行学习/训练，或是需要运行一段时间才能看出效果。随着时间的推移，不同于其它静态技术，贝叶斯分类器会越来越有效，因此之前花一段时间等待是完全值得的，正如《基督山伯爵》结语，“人类最伟大的智慧，在于等待和希望”……

三、原型设计
初步写了个原型，想测试一下效果，（无接口、无抽象、单类、命名不规范、无注释，汗），详细过程不说了，有兴趣的可参考附件。
首先给出五个训练样本：

cf.train("Nobody owns the water", "good");
cf.train("the quick rabbit jumps fences", "good");
cf.train("buy pharmaceuticals now", "bad");
cf.train("make quick money at the online casino", "bad");
cf.train("the quick brown fox jumps", "good");

接下来，我们试一下“make quick money at the online casino“的效果
cf.prob("make quick money at the online casino", "good")
cf.prob("make quick money at the online casino", "bad")

输出结果分别是0.0013183593749999999和0.00625，这并没有显示出贝叶斯分词的优势，毕竟这段文本在以前出现过。如果我们将文本修改为“make quick money， visit XXX.htm“
cf.prob("make quick money， visit XXX.htm ", "good")
cf.prob("make quick money， visit XXX.htm ", "bad")

输出结果分别是0.005859375和0.0125。由于分类器从未见过visit、XXX.htm等词语，因此它也不是非常确定这是一条垃圾文本，如果我们通过人工审核将其加入训练库
cf.train("make quick money， visit XXX.htm ", "bad");

下一次，如果接收到文本“make quick money , visit YYY.htm, earn dollars“，分类器将会毫不犹豫地将它划分为垃圾邮件（good：4.1232638888888883E-4；bad：0.004199620627572015）。

前面提过的都是英文文本的识别。对于中文，则要考虑分词器的影响。这里选用MMAnalyzer，建议使用最大正向匹配方式（细粒度为零），因为“人民”和“人民币”是两个不同的概念。对“2008年前三季度，美国次贷危机升级，全球金融持续动荡，世界经济增长全面放缓，全球经济增长动力减弱，世界主要经济体与新兴市场正面临巨大的外部冲击。“ 的分词效果还是比较理想的。
2008] [年前] [三季度] [美国] [次] [贷] [危机] [升级] [全球] [金融] [持续] [动荡] [世界经济] [增长] [全面] [放] [缓] [全球] [经济] [增长] [动力] [减弱] [世界] [主要] [经济] [体] [新兴] [市场] [正] [面临] [巨大] [外部] [冲击]

我们采用生意经中的数据来模拟，锁定“机票“这一关键词

cf.train( " 网上预定了飞机票，请问具体付款流程的怎样的" , "good");
cf.train( "请问高手们，如何开办一家预定销售机票的公司？谢谢" , "good");
cf.train( "中国民航全国统一订票（销售）热线" , "bad");
cf.train( "杭州到上海机票预定热线是多少？" , "bad");
cf.train( "机票预定热线是多少？" , "bad");
cf.train( "特价机票预定方法有哪些？" , "good");
cf.train( "东方航空特价机票:400+6918118" , "bad");
cf.train( "携程机票预定中心:400.6888.932" , "bad");
cf.train( "机票销售代理" , "bad");

假设我们新接收一条文本“广州到青岛机票预定热线是多少？“，贝叶斯分类器将其判定为垃圾文本（bad：0.010416666666666666；good：0.0010363520408163264）

假设我们新接收一条文本“预定国内机票具体应该注意那些问题？“，贝叶斯分类器将其判定为正常文本（bad：0.003348214285714286；good：0.005181760204081632）

考虑大多数的情况下，可以原谅几篇广告文本绕过审核，却无法忍受一篇有效文本被过滤，因此特别维护一个thresholds的HashMap，比如当bad/good > 3时才判定，该文本为垃圾广告。比如“预定国内机票应该怎么做？”，贝叶斯分类器将其判定为unknown（未知）（bad：0.013392857142857144；good：0.012436224489795918），因为3 > bad/good > 1。运营人员在审核unknown的文本时，发觉这是一条正常文本，因此将其加入训练库
cf.train( "预定国内机票应该怎么做？" , "good");

下一次，再接收到类似文本比如“预定国内机票怎么操作？”，分类器将会自动将其归类为正常邮件（bad：0.006054687499999999；good：0.018951416015625）。

四、初步架构



五、展望
1、自然语义（主、谓、宾）的引入
2、将标题、内容、副标题、相关类目的文本内容作为权值引入
3、非文本因素的引入（id、ip、web行为）
4、论坛、博客、百科等词库共享

六、参考文献
1、《垃圾信息相关范例和情况》
2、《每日审核战报》
3、http://www.gfi.com/whitepapers/why-bayesian-filtering.pdf
4、《Programming Collective Intelligence，Building Smart Web 2.0》 Toby Segaran
5、《Collective Intelligence in Action》 Satnam Alag
6、http://nlp.stanford.edu/IR-book/html/htmledition/naive-bayes-text-classification-1.html
7、http://www.emis.de/journals/GM/vol14nr4/pop/pop.pdf
8、http://mathforum.org/~ken/bayes/bayes.html