基于 AC 自动机和贝叶斯方法的垃圾内容识别

lazyrabbit 发布于8天前 阅读31次
0 条评论

基于 AC 自动机和贝叶斯方法的垃圾内容识别

背景

作为一个开放领域的知识社交平台,知乎为大家提供了「友善」、「理性」、「专业」的讨论氛围,吸引了大量用户参与,产生了很多优质内容。但同时也吸引了一些垃圾制造者,在知乎上生产了不少的垃圾内容,如「违法」、「广告」、「淫秽色情」、「人身攻击」等,严重影响了知乎用户的正常讨论交流,极大地影响了用户体验,同时也对社区管理造成了较大的干扰。

我们先来看看都有哪些真实的垃圾:

非法内容 ,比如:1)传播、寻求或买卖情色,如「xxx 宾馆酒店小姐」、「xxx 一夜情小姐」、「xxx 全套小姐」、「xxx 红灯区小姐」;2)传播赌博,如 「澳*新*天地 xxx xxx 博人真钱赌 连赢 100 万」、「*博 xxx xx 玩法多」、「xxx xx zzz」等等。这类内容违反了现行法律,危及了国家安全和社会和谐。

不友善内容 ,比如:1)辱骂他人,如「你这个智障」、「艹你妈」;2)用侮辱、夸张的手法嘲讽他人,如「脑残」、「智商欠费」等等。这类内容表现为不尊重他人,用恶毒的言语刺激对方,使得讨论无法正常有效进行。

还有一些垃圾广告,如微商、代开发票。

这些垃圾内容严重影响了知乎用户的正常交流。此前我们的工程师们也尝试了一些方法去识别处理它们。如文本分类模型,准确率达到了 96%, 每天识别 300+ 条;利用 DFA 根据关键词大量召回。这些尝试虽然都取得了一定的效果,但是召回不够、或召回过多非垃圾内容、或者存在不少的误伤。为此我们引入人工审核,但不能快速处理,容易造成内容堆积,而且对管理员也是很大压力,平均每周要消耗 1 个人力。

前期的尝试虽然效果不是很理想,但积累了比较多的数据。对这些数据的分析,我们发现这些垃圾内容是有套路的。基于此,我们利用 Aho-Corasick 自动机实现多模匹配,在其基础上增加了过滤机制,实现了第一版的垃圾内容分析系统,取得了不错的效果。

Aho-Corasick 自动机

AC 自动机算法于 1975 年产生于贝尔实验室。该算法巧妙地将多模式串建成一个确定性有限状态机 (DFA),以待匹配字符串作为该 DFA 的输入,使状态机进行状态转移,当到达某些特定的状态时,完成模式匹配, 能 基于 AC 自动机和贝叶斯方法的垃圾内容识别 时间内完成多模式匹配(其中 n 为待匹配字符串的长度)。下面以模式串「 he / she / his / hers 」构建一个 AC 自动机举例说明(如图一所示)

基于 AC 自动机和贝叶斯方法的垃圾内容识别

当输入一个字符串时「ushers」,该自动机从状态 0 开始进行状态转换,完整的状态转移路径如图二所示

基于 AC 自动机和贝叶斯方法的垃圾内容识别

当遇到 AC 中的红色节点时,说明发生了模式匹配,匹配到的模式有:「he」、「she」、「hers」。

具体可以用 Double Array Trie 实现 AC 自动机,在保持高效多模匹配的基础,进一步节省空间。

贝叶斯方法

虽然 AC 自动机能快速的从字符串中找到存在于词典中的关键词,但这仅仅能满足一小部分需求,即不顾准确率的大量召回,很显然会造成误伤,这对知友也是很不友好。肯定有知乎用户会问,直接用「贝叶斯」方法不就可以搞定吗?你看人家做 spam 邮件过滤,不也做得还不错,还用什么 AC ?对对对,你说的都是正确的。但是实验发现,单纯地用 「贝叶斯」方法直接进行过滤时,准确率和召回率都不是很理想。究其原因呀,有 1)知友们知识面广、思维发散,2)长尾,很多词语出现频次相对较低。

AC + 贝叶斯 > max { AC, 贝叶斯 }

考虑到上述问题,我们提出了利用 AC 自动机,根据设定的类别关键词圈定相应类别的内容,然后在每个类别里利用「贝叶斯」方法的思想准确过滤出垃圾内容。现在我们有了解决问题的思想(思想很重要),来看看我们具体是怎么利用 AC 和「贝叶斯」这两个神器,打造垃圾内容过滤的。直接上图,一图胜千言。

基于 AC 自动机和贝叶斯方法的垃圾内容识别

图三中「主关键词」就是利用 AC 自动机按关键词圈定相应类别的内容。圈定之后,利用「可有可无」这儿所配置的策略在每个类别里进行垃圾内容过滤,策略即是利用「贝叶斯」思想总结出来的。

下面以评论数据为例,介绍如何运用贝叶斯方法来总结策略。

首先,分析样本数据,提取每一个词,计算每个词在正常评论和垃圾评论中出现的频率。比如,我们假定「sb」这个词,在 1000 条垃圾评论中,有 500 条包含该词,那么它的出现频率就是 基于 AC 自动机和贝叶斯方法的垃圾内容识别 ;而在 1000 条正常评论中,只有 2 条包含该词,那么出现频率就是 基于 AC 自动机和贝叶斯方法的垃圾内容识别 。那现在对一条新的评论,发现其中包含「sb」这个词,它是垃圾评论的概率可以通过式一计算。(此处用 基于 AC 自动机和贝叶斯方法的垃圾内容识别基于 AC 自动机和贝叶斯方法的垃圾内容识别 分别表示垃圾评论和正常评论, 基于 AC 自动机和贝叶斯方法的垃圾内容识别 表示词 「sb」, 基于 AC 自动机和贝叶斯方法的垃圾内容识别 表示垃圾评论的概率, 基于 AC 自动机和贝叶斯方法的垃圾内容识别 表示垃圾评论中 出现的频率)

基于 AC 自动机和贝叶斯方法的垃圾内容识别 (式一)

在没有更多先验知识的情况下,我们通常假设 基于 AC 自动机和贝叶斯方法的垃圾内容识别 。那在前文的例子中,很容易计算出 基于 AC 自动机和贝叶斯方法的垃圾内容识别 ,说明「sb」词很容易区分出垃圾评论。通过这样的方式去挖掘出词语,当然也可以从正面角度考虑,比如「我」这个词,在我们的数据中能较好地区分出不是垃圾评论。此外,还可以考虑多个词语联合共现,甚至词之间的空间结构关系。这些在目前的逻辑里都是支持的。

有了具体实现,我们来看看实际的效果,如图四所示。(对于不利于讨论的内容也会被处理)

基于 AC 自动机和贝叶斯方法的垃圾内容识别

线上效果如图五所示。

基于 AC 自动机和贝叶斯方法的垃圾内容识别

这套逻辑已融入到了算法机器人「瓦力」的大脑中,在知乎的诸多场景下,如评论、私信、回答、提问等,以 99% 的准确率处理着每天产生的垃圾内容。 每天处理掉 3000+ 条垃圾评论 ,上线后处理了 站内上万条封建迷信提问 、上千条代为完成个人任务、上千条求医问药等违规提问,帮助知友们维护起了一个「友善」的讨论环境。

此外,这套系统也十分方便运营人员实现一站式自助策略管理。首先通过样本制定策略,然后通过离线版本进行策略验证,评估其准确率和召回率,最后自助上线策略。整个过程均无需工程师的介入,大大提高了运营效率。

总结和展望

为了让知乎用户友善地讨论交流,我们踏出了这一小步,主动识别处理了诸多垃圾内容。但还有很长的路要走,后续我们将为机器人「瓦力」打造更加完善智能的大脑,如自动归纳策略,引入深度学习等,为其建立更加科学高效的识别能力,以全自动的方式准确地识别出所有内容。

虽以识别垃圾内容为出发点,建立了基于 AC 自动机和「贝叶斯」思想的内容识别系统,但这套系统还可以运用到其他场景,比如舆情、其他内容归类等,在这儿就不展开了。

作者:孙先,张瑞,王璐

Reference:

[1] Aho-Corasick Algorithm

[2] Finite State Machine

[3] Deterministic Finite Automaton

[4] AhoCorasickDoubleArrayTrie

[5] Bayesian Inference

我们正在招聘:

-数据挖掘工程师

-算法专家

欢迎投递简历到:jobs@zhihu.com

「知乎技术日志」是知乎工程师运营的一个技术专栏,在这里我们会陆续将知乎在机器学习、人工智能、稳定性和安全管理、反作弊系统、微服务实践、Docker、自动化运维、移动端网络优化等领域的技术思考和实践分享给大家。希望各位大家给予关注,并提出你宝贵的意见和反馈。

查看原文: 基于 AC 自动机和贝叶斯方法的垃圾内容识别

共收到0条回复

需要 登录 后回复方可回复, 如果你还没有账号你可以 注册 一个帐号。