转载自 https://www.cnblogs.com/caoer/p/14803744.html 参考自 《新词发现”算法探讨与优化-SmoothNLP》
一、什么样的字符组合可以称为一个“词”？
- 词语的左右邻字要足够丰富
如果一个字符组合可以成词，它应当出现在丰富的语境中，也就是说，拥有丰富的左右邻字。信息熵是对信息量多少的度量，信息熵越高，表示信息量越丰富、不确定性越大。因此字符组合左右邻字的丰富程度，可以用信息熵(Entropy)来表示：
其中
为字符组合左/右邻字的集合。 举个例子，同样是在文本中出现6000+次的“副总裁”和“人工智”，字符组合的左熵都在6左右，但“副总裁”的右邻字包括 { 张,王,说, …… } 等147个词，而“人工智”的右邻字只有 { 能,障 } 两种，显然“人工智”不能称作一个词。
- 词语的内部凝聚程度要足够高
如果某些字符经常出现在一起，我们会认为这些字符可以成词，这并不意味着我们可以用字符组合出现的频数作为判断标准。
如上图所示，在1900万字的新闻中，如果单纯地以字符的共现为标准判断，由于”的”,”在”这些常用字的存在，会产生大量噪声词。这些噪声词(如”你的”,”亚马逊的”)虽然为文本中十分常见，我们并不会把它们判定为合理的中文词汇。因为”的”,”在”的出现太过频繁，就像日常出门营业的social王，它可能和任何人出现在同一场合。只有两个社恐手拉手一起出门，我们才能做出二人是真爱的判断。
和人与人之间的关系类似，我们可以对字符有类似的内部凝聚程度的定义。如果字符中的”社恐”同时出现，我们可以认为这样的字符组合就是一个合理的词汇。比如“演唱者”出现117次，“的演唱”出现275次，从出现频数来看，“的演唱”更像是一个词。但是如果把字符的共现看作随机事件的话，“演唱”和“者”在文本中分别出现2502,32272次，二者恰好拼在一起的概率
， “演唱者”__的实际出现概率为它的27倍。而“的”与“演唱”随机拼在一起的概率
，“的演唱”实际出现概率为它的4.7倍。因此我们有理由相信，“的演唱”这一词语的出现，是常用字“的”日常出门营业，而与一个动词意外拼在一起的结果，“演唱者”才是组成成分之间凝聚程度高的合理中文词汇。
为了量化字符组合的凝聚程度，我们用字符组合出现的概率除以每一个组成成分出现的概率。这听起来很像互信息(mutual information)的形式：
互信息 (MI) 表示知道了随机变量X之后对另一个随机变量Y不确定性的减少，但由于这里随机变量的取值唯一，我们使用点间互信息(point-wise mutual information)作为衡量这一特征的指标：
上面提到的“演唱者”，内部凝聚程度可以表示为： 
- 综合考虑
我们要判断一个字符组合是一个“词”，对于左右邻字丰富程度和内部凝聚程度的考虑，二者缺一不可。如果只看内部凝聚程度的话，无法将“人工智”，“工智能”这样的词删去；而只保留左右邻字丰富的词，会出现“公司的”，“在北京”这样的词汇。并且，左右邻字丰富程度，会受到字符组合出现频数的影响。例如显然无意义的词“己的”，因为在文本中出现1万次以上，RE高达8.7。因此我们在度量一个字符组合的左右邻字丰富程度时，也要注意到 LE(left entropy) 和RE的差距。比如取二者的最小值，或者将LE与RE差的绝对值(|LE-RE|)纳入考虑范围。
二、一些基本概念介绍
- 【未登录词】
没有被收录在分词词表中但必须被切分出来的词， 包括各种专有名词（人名、地名、企业名、机构名等）、 缩写词、网络新词以及新增词汇等。（参考：张剑锋.规则和统计相结合的中文分词方法研究.[硕士学位论文].太原：山西大学，2008.）
- 【频数（Frequency）及概率（Probavility）】
一个文本片段在文本中出现的频率。文本片段出现的概率：eg. 在24万字的数据中，“电影”一共出现了2774次，出现的概率为
；“院”字出现了4797次，出现的概率为
- 【凝固度】
也叫做点间互信息（Pointwise Mutual Information），表示一个文本片段的凝合程度，其中P(x)表示文本片段x在整个语料中出现的概率，因此凝固程度的计算公式为：
如果x和y的出现完全随机，那么PMI=1；如果x和y同时出现的概率，大于完全随机，那么PMI>1。PMI越大，说明这两个词经常出现在一起，意味着两个词的凝固程度越大，其组成一个新词的可能性也就越大。
由于点间互信息的值会受到候选词长度的影响（候选词越长，互信息取值偏大），可使用平均互信息(AMI)作为词语内聚程度的度量。AMI的公式如下：
- 【信息熵（Information Entropy）】
- 【自由度（Freedom）】
也叫做左右信息熵（Information Entropy），指文本片段的自由运用程度：左邻字信息熵和右邻字信息熵中的较小值。
例如“被子”，可以在前面加上一个字成为“进被子”、“盖被子”、“好被子”、“这被子”、“掀被子”等等，其左邻词的熵很大；但“辈子”搭配较为固定，除了“一辈子”、 “这辈子”、“上辈子”、“下辈子”，基本就不能加上其他字了，其左邻词的熵较小。文本的运用程度是判断文本片段是否成词的重要标志。如果一个文本片段能够成词，一定具有非常丰富的左邻字集合和右邻字集合，其成为一个独立的词的可能性也就越大。
- 【网络经验公式】
（30M文本，字母n表示n-gram即相关新词包含的字数）：词频>200，凝固度>10 ( n − 1 ) 10^{(n-1)}10 (n−1) ，自由度>1.5；词频>30, 凝固度>2 0 ( n − 1 ) 20^{(n-1)}20 (n−1)也能发现很多低频的词汇。
三、苏神系列
苏剑林. (Oct. 26, 2015). 《新词发现的信息熵方法与实现 》[Blog post]. Retrieved from https://kexue.fm/archives/3491
算法思想来源：Matrix67.com. (Oct. 26, 2015). 《互联网时代的社会语言学：基于SNS的文本数据挖掘》[Blog Post]. Retrieved from http://www.matrix67.com/blog/archives/5044
参考Code1：https://github.com/fzibin/New_word_discovery，包含反作弊新词发现和短语提取。 参考Code2：https://github.com/actank/new_words_find，新词发现/未登录词识别。
算法流程：把语料文本视作一整个字符串，并对该字符串的所有后缀按字典序排序，在内存中存储这些后缀的前d+1个字或者只存储它们在语料中的起始位置提高效率，对文本进行字频和字数统计后，根据候选词语的最大字数min_sep生成所有可能的候选词，随后统计候选词频进行过滤，再计算凝固度，根据最小凝固度min_support进行过滤。接下来， 从头到尾扫描一遍算出各个候选词的频数和右邻字信息熵，将整个语料逆序后重新排列所有的后缀，再扫描一遍后统计出每个候选词的左邻字信息熵，从而进行自由度 计算并根据min_s过滤产生较大信息熵的候选词，最后输出排序并且长度大于n字的新词。
总结：采用频数、凝固度、自由度进行筛选，效率O(nlogn)。
苏剑林. (Aug. 18, 2016). 《【中文分词系列】 2. 基于切分的新词发现 》[Blog post]. Retrieved from https://kexue.fm/archives/3913
算法流程：由于文本片段的凝固度大于一定程度时，片段的可能成词，然后考虑自由度，那么如果文本片段的凝固度低于一定值，则该文本片段不成词，则可以进行分词。设a、b是语料中哄相邻两字，统计(a, b)成对出现的次数#(a, b)，继而估计它的频率P(a, b)，分别统计a，b出现的次数#a、#b，然后估计它们的频率P(a)、P(b),判断 P(a, b) / [P(a)*P(b)] < α（α是给定的大于1的阈值），则在语料中将这两个字断开，实施对原始语料初步的分词，完成分词后统计词频，根据词频进行筛选。（只用了频数和凝固度，去掉了计算量最大的自由度，计算凝固度时只需要计算二字片段的凝固度，但理论上能够得到任意长度的词语。但凝固度不高的词语在α太大时会导致切错。）
优缺点：速度快，但词很粗糙，只用了频数和凝固度，去掉了计算量最大的边界熵，计算凝固度时只需要计算二字片段的凝固度，但理论上能够得到任意长度的词语，但凝固度不高的词语在α太大时会导致切错。
苏剑林. (Sep. 12, 2016). 《【中文分词系列】 5. 基于语言模型的无监督分词 》[Blog post]. Retrieved from https://kexue.fm/archives/3956
总结：结合语言模型和贝叶斯概率，强大但受到viterbi等限制。
苏剑林. (Mar. 06, 2017). 《【中文分词系列】 7. 深度学习分词？只需一个词典！ 》[Blog post]. Retrieved from https://kexue.fm/archives/4245
总结：带词频的词表根据规则生成句子进行预标注作为训练数据，使用LSTM模型结合viterbi算法，通过动态规化来输出最后的结果。最终的模型在backoff2005的评测集上达到85%左右的准确率（backoff2005提供的score脚本算出的准确率）。
苏剑林. (Mar. 11, 2017). 《【中文分词系列】 8. 更好的新词发现算法 》[Blog post]. Retrieved from https://kexue.fm/archives/4256 苏剑林. (Sep. 09, 2019). 《重新写了之前的新词发现算法：更快更好的新词发现 》[Blog post]. Retrieved from https://kexue.fm/archives/6920
Github地址：https://github.com/bojone/word-discovery 优化代码：https://github.com/Chuanyunux/Chinese-NewWordRecognition Kenlm预训练及使用方法：https://github.com/mattzheng/py-kenlm-model
算法流程：
- Step1.统计，选取某个固定的n，统计2grams、3grams、…、ngrams，计算他们的内部凝固度，只保留高于某个阈值的片段，构成一个集合G；这一步，可以为2grams、3grams、…、ngrams设置不同的阈值，不一定要相同，因为字数越大，一般来说统计就越不充分，越有可能相同，所以字数越大，阈值要越高。
- Step2.切分，用上述grams对语料进行切分（粗糙的分词），并统计频率即统计分词结果，跟第一步的凝固度集合筛选没有交集，筛选出高频部分。切分的规则是，只要一个片段出现在前一步得到的集合G中，这个片段就不切分，比如“各项目”，只要“各项”和“项目”都在G中，这个时候就算“各项目”不在G中，那么“各项目”还是不切分，保留下来。
- Step3.回溯，例如因为“各项”和“项目”都出现在高凝固度的片段中，所以第二步中不会把“各项目”切开，但并不希望“各项目”成词，因为“各”跟“项目”的凝固度不高，所以通过回溯，把“各项目”移除。
苏剑林. (Apr. 10, 2019). 《分享一次专业领域词汇的无监督挖掘 》[Blog post]. Retrieved from https://kexue.fm/archives/6540 苏剑林. 最小熵原理（二）：“当机立断”之词库构建
算法流程：
- 一、利用最小熵原理，在train的基础上（统计字频和字对频率），计算互信息，通过互信息找出强相关的邻字，然后通过这些邻字实现粗糙的分词，从粗糙的分词结果中筛选出可能的词语。
- 统计：从大量的语料中统计每个字的频率（pa,pb），以及统计相邻两字的共现频率(pab)；
- 切分：分别设定出现频率的阈值min_prob和互信息的阈值min_pmi，然后在语料中将 pab<min_prob 或 PMI(a,b)<min_pmi 的邻字切开（“当机立断”，相当于一次粗糙的分词）；
- 截断：经过第2步的切分后，统计各个“准词语”的频率pw′，仅保留pw′>min_prob部分；
- 去冗：将词典的候选词按字数从多到少排列，然后依次将每个候选词在词库中删除掉，用剩下的词和词频将这个候选词分词，计算原词与子词之间的互信息PMI，如果互信息大于1，则恢复这个词，否则保持删除，并且更新切分出来的子词的词频。
- 二、基于最小熵原理的NLP库：nlp zero 中的新词识别/词库构建工具。给定两份语料，一份是目标语料，一份是公开较大规模的通用语料，分别对两份语料进行新词发现/词库构建。对比两份语料词频，即可得到非常用词库的特征词。
- 三、按照上述方法导出来的词表，顶多算是“语料特征词”，但是还不完全是“专业领域词汇”，还需进行语义筛选！而领域词判断，作者采用的是通过语料训练词向量，再由种子词来扩展领域词，也不失为一个好思路。
- 用上一步导出来的词表对比赛语料进行分词，然后训练一个Word2Vec模型
- 根据Word2Vec得到的词向量来对词进行聚类。具体来说，给定若干个种子词，然后找到一批相似词来，放入队列中（类似广度优先遍历）
总结：电力专业领域词汇挖掘竞赛数据的无监督挖掘，主要与基准做对比得到差集再聚类后处理。
四、工具
- SmoothNLP：https://github.com/smoothnlp/SmoothNLP。
- HarvestText：包括 底层 分词、文本清洗、实体链接、实体识别、新词发现、拼音纠错、别名识别， 上层任务：情感分析、文本摘要、事实抽取、问答。github 链接：https://github.com/blmoistawinde/HarvestText
- jiagu自然语言处理工具：包含多种NLP下游任务，包括中文分词、词性标注、命名实体识别、知识图谱关系抽取、关键词提取、文本摘要、新词发现、情感分析、文本聚类：https://github.com/ownthink/Jiagu，可直接调包。
Transformer：
基于C++的新词发现，速度更快：https://github.com/Lapis-Hong/fast-xinci。
若有收获，就点个赞吧
0 人点赞
