前段时间和团队的同学在梳理站内品牌词，恶意营销相关的问题。目前站内大部分的恶意营销都是出于 seo 的目的，利用知乎的 pagerank 来提升搜索引擎的关键词权重。因此这类内容的特点就是大量的关键词（品牌相关，品类属性相关的词汇）会被提及。由于都是一些小众品牌和新品牌，这类关键词一般都未被切词词库收录，就是我们所谓的未登录词 (unknown words), 于是我们从词汇的左右信息熵和互信息入手，去挖掘未登录词, 并取得了比较好的效果。
首先解释下这里涉及到的两个概念，信息熵和互信息。这两个指标分别对应了未登录词成词的两个标准。
成词标准一： 所处语境的丰富程度 - 熵 (Entropy)
通常我们认为两个片段可以成词的一个条件就是这个词语会在很多的语境中被提到。熵就是一个用来衡量这个维度的指标。
熵是一种表示信息量的指标，熵越高就意味着信息含量越大，不确定性越高，越难以预测。通常对于一个随机变量 X, 它的熵可以被表示成：
p(x) 表示的是事件 x 出现的概率，在新词挖掘的时候就是一个词出现的概率。信息论里面通常会用二进制位数去衡量信息量，所以上面的公式可以被理解成，如果用某种编码方式去表示，平均所需的二进制位数。
举个例子，假设现在有 8 个球，分别被抽到的概率是 1/2, 1/4, 1/8, 1/16, 1/64, 1/64, 1/64, 1/64。现在如果采用霍夫曼编码对每个球进行编号，这几个球的编码分别是：0, 10, 110, 1110, 111100, 111101, 111110, 111111。
所以平均编码长度为：
信息熵为：
因此信息熵可以反映出信息量。我们将通过计算一个候选词左边和右边的信息熵来反映了一个词是否有丰富的左右搭配，如果达到一定阈值则我们认为两个片段可以成为一个新词。
成词标准二：内部聚合程度 - 互信息 (mutual information) & 点间互信息 (pointwise mutual information)
上面讲到熵表示了信息量的大小。如下图所示，互信息 (MI) 表示了两个随机变量 X, Y 共享的信息量。也可以说，互信息代表着知道了任意一个变量之后对另一个变量不确定性的减少。
互信息的定义如下：
可以看出来，互信息是针对随机变量计算一个平均值。在计算机领域，更常用的是点间互信息，点间互信息计算了两个具体事件之间的互信息。点间互信息的定义如下：
当 x, y 相互独立时，x 跟 y 不相关，则 p(x , y) = p(x)p(y), PMI 则为0。二者相关性越大，则 p(x , y) 就相比于 p(x)p(y) 越大, 那 PMI 也就越大。因此后面的式子比较容易理解，可以说是表示内部凝聚力。拿 “知”、“乎” 这两个字来说，假设在 5000 万字的样本中, “知” 出现了 150 万次， “乎” 出现了 4 万次。那 “知” 出现的概率为 0.03, “乎” 出现的概率为 0.0008。如果两个字符出现是个独立事件的话，”知”、“乎” 一起出现的期望概率是 0.03 * 0.0008 = 2.4e-05. 如果实际上 “知乎” 出现了 3 万次, 则实际上”知”、“乎” 一起出现的概率是 6e-03, 是期望概率的 250 倍。 这通常被成为凝合度，数值越大表示两个片段一起出现的概率越大。正如之前提到的，以 2 求 log 的原因来自信息论，可以简单理解为，取 log 之后就将一个概率转换为了信息量，以 2 为底时可以简单理解为用多少个 bits 可以表示这个变量。
那我们是如何结合这两个指标来实现新词挖掘的呢？让我们结合例子捋一遍流程。
现在有这么一段关于淘宝客的文本：
每天都有网友问我：2017年做淘宝客还赚钱吗？我：2017年做淘宝客还可以继续好好做。各大门户虽然也跟我们小站长共分一杯羹，但是毕竟我们可以推广的商品太多了，现在网民购物的也越来越多了，所以淘宝客依然还有很大的发展空间。至少未来两三年内淘宝客大格局估计不会有太大变化。所以就淘宝客赚钱的这一话题，谈谈自己的一些看法。纵观这两年的所有网上兼职的工作，淘宝客算的上是最给力的，是最适合个人站长操作的项目，它实现了淘宝、网店商家、个人站长（淘宝客）三方共赢的良好局面，就连各大门户现在也在操作淘宝客。但很多人都在说淘客赚不到钱了，为什么做了那么多淘宝客的网站，最后赚钱的就一个呢？让我来跟大家分析一下原因。
首先需要对输入文本进行清洗和分词，如果没有任何分词词库的情况下，直接将文本按照字符分割也是可以的，这个例子我们演示在无词库的情况下，如何挖掘这段本文的新词。在这一步直接将示例文本分割成一个单字符集合即可。将字符两两组合作为候选词，因为需要前缀和后缀来计算信息熵，因此我们需要存储长度为 3 的片段。由于后续涉及到前后缀的查找和词频的统计，最终我们选定了 Trie 树 来存储数据。用 3-gram 序列构建前缀 Trie 树和后缀 Trie 树，Trie 树以单个字符为节点，每个节点记录从根节点到当前节点构成词汇出现的频次。查询 Trie 树，获取前缀和后缀的频次列表，计算候选词的左右信息熵以及候选词构成片段的左右信息熵。因为涉及到的信息熵比较多，我们对每个信息熵作如下区分标记（Candidate 为候选词，left 为左边构成的片段，right 为右边构成的片段）：
查询 Trie 树，获取候选词的词频以及左右片段的词频。有了词频之后便可以很方便的得到实际出现概率 p(x,y) 和期望出现概率 p(x)p(y)，从而计算出凝合度和互信息。为了防止冷启动前出现过高的概率 p，我们预先跑了一些基础词汇的词频，在词频库的基础上，可以保证刚开始的时候就能拿到比较正确的概率 p。为了增加准确率，可以设定词频和互信息的阈值，排除一些低词频和低凝合度的词汇。所有满足条件的词汇，通过调用 jieba 的 suggest_freq 函数来使其能被分出来。在这个例子中我们限制了词频大于 2, PMI 大于等于 24.针对新词成词的特点, 在实际应用中，我们为每一个备选单词计算了一个分数，表示在当前上下文成为新词的可能性。分数计算公式如下：
分数由三个对应部分组成：1）点间互信息：点间互信息越高，内部聚合程度越高2）两个单词片段信息熵 h_r_l 和 h_l_r 的最小值：这个数值越大，则意味着两个单词一起出现的可能性越小3）单词左右信息熵的最小值：这个数值越大就表示着候选词出现的语境越多，越有可能成词因此，分数越高表示成词的可能性越大。
对于单词左右信息熵 ( h_l, h_r ) 为 0 的情况，迭代一轮，确认是否可能与左右的片段组成新词。 比如 “淘宝客” 这个词，先被分成了 “淘”、“宝”、“客”，在检测 “淘宝” 的时候，会发现它的右信息熵为 0，因此 “淘宝” 在当前上下文可能是另一个词的片段，所以通过下一轮迭代，检测 “淘宝” 和 “客” 能否成词。最后根据词频和score的乘积排序，筛选出 top 5 的词汇作为新词。淘宝客这个例子中筛选出来的 top 5 新词结果如下：
实际效果：在没有使用任何词库的情况下，上述算法针对不同文本表现如何呢，下面我们使用算法从四大名著中筛选出来的新词 top 25.
西游记：行者，行者道，八戒，师父，三藏，一个，唐僧，沙僧，大圣，菩萨，怎么，不知，长老，八戒道，那里，只见，和尚，等我，原来，妖精，什么，三藏道，徒弟，老孙红楼梦：宝玉，什么，黛玉，如今，怎么，你们，说着，只见，老太，太太，贾琏，他们，告诉，咱们，听见，薛姨妈，探春，鸳鸯，所以，紫鹃，二爷，凤姐儿，晴雯，宝玉道，刘姥姥水浒传：宋江，只见，两个，武松，李逵，一个，如何，卢俊，哥哥，兄弟，吴用，说道，林冲，众人，卢俊义，戴宗，梁山泊，梁山，军马，次日，宋江道，晁盖，鲁智，这个，正是三国演义：玄德，将军，曹躁，关公，云长，天下，夏侯，张飞，荆州，商议，曰吾，玄德曰，大怒，次日，刘备，诸葛，司马懿，袁绍，夫人，左右，魏延，姜维，陛下，只见，曰此实际应用中，词库实际上是不断被完善的，因此词库越完善，后续满足条件的未登录词会越少。我们对新词的挖掘也是基于内部的词库。试着跑一段时间内被反作弊系统悟空删除的内容，最后出来的前几个基本上都是站内被提及比较多的营销关键词了。
作者：周奥特，陈磊
出处:https://zhuanlan.zhihu.com/p/25499358
Reference:
[1] http://net.pku.edu.cn/~course/cs220/reading/chbb.pdf
[2] Mutual information
[3] 点互信息（PMI，Pointwise Mutual Information）
[4] http://www3.cs.stonybrook.edu/~ychoi/cse628/lecture/03-ngram.pdf
[5] https://svn.spraakdata.gu.se/repos/gerlof/pub/www/Docs/npmi-pfd.pdf
[6] 基于大规模语料的新词发现算法-CSDN.NET
