【中文分词系列】 8. 更好的新词发现算法
By 苏剑林 | 2017-03-11 | 228856位读者 |如果依次阅读该系列文章的读者,就会发现这个系列共提供了两种从0到1的无监督分词方案,第一种就是《【中文分词系列】 2. 基于切分的新词发现》,利用相邻字凝固度(互信息)来做构建词库(有了词库,就可以用词典法分词);另外一种是《【中文分词系列】 5. 基于语言模型的无监督分词》,后者基本上可以说是提供了一种完整的独立于其它文献的无监督分词方法。
但总的来看,总感觉前面一种很快很爽,却又显得粗糙;后面一种很好很强大,却又显得太过复杂(viterbi是瓶颈之一)。有没有可能在两者之间折中一下?这就导致了本文的结果,达到了速度与效果的平衡。至于为什么说“更好”?因为笔者研究词库构建也有一段时间了,以往构建的词库总不能让人(让自己)满意,生成的词库一眼看上去,都能够扫到不少不合理的地方,真的要用得需要经过较多的人工筛选。而这一次,一次性生成的词库,一眼扫过去,不合理的地方少了很多,如果不细看,可能就发现不了了。
分词的目的 #
分词一般作为文本挖掘的第一步,仿佛是很自然的,但事实上也应该问个为什么:为什么要分词?人本来就是按照字来书写和理解的呀?
当模型的记忆和拟合能力足够强(或者简单点,足够智能)的时候,我们完全可以不用分词的,直接基于字的模型就可以做,比如基于字的文本分类、问答系统等,早已有人在研究。但是,即便这些模型能够成功,也会因为模型复杂而导致效率下降,因此,很多时候(尤其是生产环境中),我们会寻求更简单、更高效的方案。
什么方案最高效?以文本分类为例,估计最简单高效的方案就是“朴素贝叶斯分类器”了,类似的,比较现代的是FastText,它可以看作是“朴素贝叶斯”的“神经网络版”。要注意,朴素贝叶斯基于一个朴素的假设:特征之间相互独立。这个假设越成立,朴素贝叶斯的效果就越好。然而,对于文本来说,显然上下文紧密联系,这个假设还成立吗?
注意到,当特征之间明显不独立的时候,可以考虑将特征组合之后,使得特征之间的相关性减弱,再用朴素贝叶斯。比如,对于文本,如果以字为特征,则朴素假设显然不成立,如“我喜欢数学”中的“喜”和“欢”、“数”和“学”都明显相关,这时候我们可以考虑将特征进行组合,得到“我/喜欢/数学”,这样三个片段之间的相关性就没有那么强了,因此可以考虑用上述结果。可以发现,这个过程很像分词,或者反过来说,分词的主要目的之一,就是将句子分为若干个相关性比较弱的部分,便于进一步处理。从这个角度来看,分的可能不一定是“词”,也可能是短语、常用搭配等。
说白了,分词就是为了削弱相关性,降低对词序的依赖,这一点,哪怕在深度学习模型中,都是相当重要的。有些模型,不分词但是用CNN,也就是把若干个字组合作为特征来看,这也是通过字的组合来减弱特征间的相关性的体现。
算法大意 #
既然分词是为了削弱相关性,那么我们分词,就是在相关性弱的地方切断了。文章《【中文分词系列】 2. 基于切分的新词发现》其实就是这个意思,只是那里认为,文本的相关性仅由相邻两字(2grams)来决定,这在很多时候都是不合理的,比如“林心如”中的“心如”、“共和国”中的“和国”,凝固度(相关性)都不是很强,容易错切。因此,本文就是在前文的基础上改进,那里只考虑了相邻字的凝固度,这里同时考虑多字的内部的凝固度(ngrams),比如,定义三字的字符串内部凝固度为:
$$\min\left\{\frac{P(abc)}{P(ab)P(c)},\frac{P(abc)}{P(a)P(bc)}\right\}$$
这个定义其实也就是说,要枚举所有可能的切法,因为一个词应该是处处都很“结实”的,4字或以上的字符串凝固度类似定义。一般地,我们只需要考虑到4字(4grams)就好(但是注意,我们依旧是可以切出4字以上的词来的)。
考虑了多字后,我们可以设置比较高的凝固度阈值,同时防止诸如“共和国”之类的词不会被切错,因为考虑三字凝固度,“共和国”就显得相当结实了,所以,这一步就是“宁放过,勿切错”的原则。
但是,“各项”和“项目”这两个词,它们的内部凝固度都很大,因为前面一步是“宁放过,勿切错”,因此这样会导致“各项目”也成词,类似的例子还有“支撑着”、“球队员”、“珠海港”等很多例子。但这些案例在3grams中来看,凝固度是很低的,所以,我们要有一个“回溯”的过程,在前述步骤得到词表后,再过滤一遍词表,过滤的规则就是,如果里边的n字词,不在原来的高凝固度的ngrams中,那么就得“出局”。
所以,考虑ngrams的好处就是,可以较大的互信息阈值情况下,不错切词,同时又排除模凌两可的词。就比如“共和国”,三字互信息很强,两字就很弱了(主要还是因为“和国”不够结实),但是又能保证像“的情况”这种不会被切出来,因为阈值大一点,“的情”和“的情况”都不结实了。
详细的算法 #
完整的算法步骤如下:
第一步,统计:选取某个固定的$n$,统计2grams、3grams、…、ngrams,计算它们的内部凝固度,只保留高于某个阈值的片段,构成一个集合$G$;这一步,可以为2grams、3grams、…、ngrams设置不同的阈值,不一定要相同,因为字数越大,一般来说统计就越不充分,越有可能偏高,所以字数越大,阈值要越高;
第二步,切分:用上述grams对语料进行切分(粗糙的分词),并统计频率。切分的规则是,只要一个片段出现在前一步得到的集合$G$中,这个片段就不切分,比如“各项目”,只要“各项”和“项目”都在$G$中,这时候就算“各项目”不在$G$中,那么“各项目”还是不切分,保留下来;
第三步,回溯:经过第二步,“各项目”会被切出来(因为第二步保证宁放过,不切错)。回溯就是检查,如果它是一个小于等于$n$字的词,那么检测它在不在$G$中,不在就出局;如果它是一个大于$n$字的词,那个检测它每个$n$字片段是不是在$G$中,只要有一个片段不在,就出局。还是以“各项目”为例,回溯就是看看,“各项目”在不在3gram中,不在的话,就得出局。
每一步的补充说明:
1、使用较高的凝固度,但综合考虑多字,是为了更准,比如两字的“共和”不会出现在高凝固度集合中,所以会切开(比如“我一共和三个人去玩”,“共和”就切开了),但三字“共和国”出现在高凝固度集合中,所以“中华人民共和国”的“共和”不会切开;
2、第二步就是根据第一步筛选出来的集合,对句子进行切分(你可以理解为粗糙的分词),然后把“粗糙的分词结果”做统计,注意现在是统计分词结果,跟第一步的凝固度集合筛选没有交集,我们认为虽然这样的分词比较粗糙,但高频的部分还是靠谱的,所以筛选出高频部分;
3、第三步,例如因为“各项”和“项目”都出现高凝固度的片段中,所以第二步我们也不会把“各项目”切开,但我们不希望“各项目”成词,因为“各”跟“项目”的凝固度不高(“各”跟“项”的凝固度高,不代表“各”跟“项目”的凝固度高),所以通过回溯,把“各项目”移除(只需要看一下“各项目”在不在原来统计的高凝固度集合中即可,所以这步计算量是很小的)
代码实现 #
下面给出一个参考的代码实现。首先,为了节约内存,写一个迭代器来逐篇输出文章:
import re
import pymongo
from tqdm import tqdm
import hashlib
db = pymongo.MongoClient().weixin.text_articles
md5 = lambda s: hashlib.md5(s).hexdigest()
def texts():
texts_set = set()
for a in tqdm(db.find(no_cursor_timeout=True).limit(3000000)):
if md5(a['text'].encode('utf-8')) in texts_set:
continue
else:
texts_set.add(md5(a['text'].encode('utf-8')))
for t in re.split(u'[^\u4e00-\u9fa50-9a-zA-Z]+', a['text']):
if t:
yield t
print u'最终计算了%s篇文章' % len(texts_set)
需要解释的是:我的文章存在mongodb中,所以用pymongo读,如果文章存在文件中,做法是类似的。当然,内存足够,而文章不多的话,直接把文章以列表的形式加载到内存中也没有问题;引入hashlib是为了对文章去重;引入正则表达式re是为了预先去掉无意义字符(非中文、非英文、非数字);引入tqdm是为了显示进度。
接着,直接计数:
from collections import defaultdict
import numpy as np
n = 4
min_count = 128
ngrams = defaultdict(int)
for t in texts():
for i in range(len(t)):
for j in range(1, n+1):
if i+j <= len(t):
ngrams[t[i:i+j]] += 1
ngrams = {i:j for i,j in ngrams.iteritems() if j >= min_count}
total = 1.*sum([j for i,j in ngrams.iteritems() if len(i) == 1])
这里的$n$就是需要考虑的最长片段的字数(前面说的ngrams),建议至少设为3,min_count看需求而设。接着就是凝固度的筛选了:
min_proba = {2:5, 3:25, 4:125}
def is_keep(s, min_proba):
if len(s) >= 2:
score = min([total*ngrams[s]/(ngrams[s[:i+1]]*ngrams[s[i+1:]]) for i in range(len(s)-1)])
if score > min_proba[len(s)]:
return True
else:
return False
ngrams_ = set(i for i,j in ngrams.iteritems() if is_keep(i, min_proba))
前文已经说了,可以为不同长度的gram设置不同的阈值,因此用了个字典来制定阈值。个人感觉,阈值成5倍的等比数列比较好,当然,这个还有看数据大小。接着,定义切分函数,并进行切分统计:
def cut(s):
r = np.array([0]*(len(s)-1))
for i in range(len(s)-1):
for j in range(2, n+1):
if s[i:i+j] in ngrams_:
r[i:i+j-1] += 1
w = [s[0]]
for i in range(1, len(s)):
if r[i-1] > 0:
w[-1] += s[i]
else:
w.append(s[i])
return w
words = defaultdict(int)
for t in texts():
for i in cut(t):
words[i] += 1
words = {i:j for i,j in words.iteritems() if j >= min_count}
最后,回溯:
def is_real(s):
if len(s) >= 3:
for i in range(3, n+1):
for j in range(len(s)-i+1):
if s[j:j+i] not in ngrams_:
return False
return True
else:
return True
w = {i:j for i,j in words.iteritems() if is_real(i)}
算法的主要时间花在ngrams的统计,以及最后文本的切分上。
词典共享 #
最后分享从300万微信文章中,用上述算法构建的词库,没有经过任何人工后期处理,既分享给广大网友使用(里边包含了一些微信相关的词语,很多流行的分词工具并没有,还是挺有价值的),也供网友验证效果。
资源下载:300w微信文章做新词发现的词库.zip
转载到请包括本文地址:https://www.kexue.fm/archives/4256
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Mar. 11, 2017). 《【中文分词系列】 8. 更好的新词发现算法 》[Blog post]. Retrieved from https://www.kexue.fm/archives/4256
@online{kexuefm-4256,
title={【中文分词系列】 8. 更好的新词发现算法},
author={苏剑林},
year={2017},
month={Mar},
url={\url{https://www.kexue.fm/archives/4256}},
}
September 4th, 2021
你好,
参阅了代码后,以下部分存在一些疑惑
====================================
total * ngrams[s] / (ngrams[s[:i + 1]] * ngrams[s[i + 1:]])
====================================
对于以上代码
N(x,y)
------
P(x,y) N N * N(x,y)
--------- = ----------- = -----------
p(x) p(y) N(x) N(y) N(x) * N(y)
---- ----
N N
这是我的理解,但问题在于N私以为应该是词总数,而非字总数。
======================================================
total = 1. * sum([j for i, j in ngrams.items() if len(i) == 1])
======================================================
但上述代码应该是在统计字数,也就是文章的总长度,想问下我的理解是否正确,如果不正确还望指出。如果正确的话,希望告知原因?
2.这里为啥特地用1.*,转换为浮点数的意图是?
======================================================
total = 1. * sum([j for i, j in ngrams.items() if len(i) == 1])
======================================================
我的猜测是为了避免C中5/2==2这种现象,所以进行类型转换?使5.0/2=2.5?但python中5/2=2.5,因此这里不是很懂
根据wikipedia en 的PMI定义https://en.wikipedia.org/wiki/Pointwise_mutual_information
$$\operatorname{pmi}(x;y) \equiv \log\frac{p(x,y)}{p(x)p(y)} = \log\frac{p(x|y)}{p(x)} = \log\frac{p(y|x)}{p(y)}.$$
据此我猜测您这边只是省略了log,但仍然是想想通过PMI的等价形式来表达粘合。下面的公式是我对您代码中
$$total * ngrams[s]\ /\ (ngrams[s[:i + 1]]\ * \ ngrams[s[i + 1:]]) $$
理解如下
$$\frac{P(x,y)}{P(x)\cdot P(y)} = \frac{\frac{N(x,y)}{N}}{\frac{N(x)}{N}\cdot \frac{N(y)}{N}}=N\cdot \frac{N(x,y)}{N(x)\cdot N(y)}$$
但关于$total$,也就是$N$我认为应该是词的频词累加和,没理解您这里为什么写成字的频次累加和?
$$total = 1. * sum([j\ for\ i,\ j\ in \ ngrams.items()\ if\ len(i)\ == \ 1])$$
别忘了某个句子的全体ngram是
[text[i:i + n] for i in range(len(text) - n + 1)]
所以总ngram数约等于总字数。
您好,因为评论区不能贴图,所以我贴在了在相关仓库中提了issue
https://github.com/bojone/word-discovery/issues/10#issue-989684251
算总数是要每种长度的ngram单独算的,而不是所有2gram、3gram、4gram混合起来算的。
你的统计结果恰好就说明,ngram总数约等于总字数(3倍,因为你把3种ngram混合在一起了)。
事实上,根据(对于某个固定的n)ngram的计算方式: [text[i:i + n] for i in range(len(text) - n + 1)] ,就知道每种ngram的总数约等于字数是显然成立的。
September 13th, 2021
博主你好,关于is_real函数有一些疑惑,希望您能解答一下。
就是最开始的时候设置了N元组的最大长度为4,也就是说四元组的凝固度已经保存在词典当中了。但是在is_real函数中,由于i的取值是从3到n+1,所以如果len(s) == 4,即输入的s是一个四元组时,还需要查看它内部的三元组片段是否满足凝固度要求。此时为什么不直接查词典来看这个四元组的凝固度是否满足要求呢?
如果len(s)==5呢
如果len(s) == 5,此时当然可以通过查看它里面的2个四元组是否均满足凝固度的要求,来判断s是否符合要求,因为我们没有直接计算5元组的凝固度。但
我这里的疑问是,如果len(s) == 4,是否可以直接查词典来获取s的凝固度,而不需要看它里面的两个三元组是否均满足凝固度要求。除了计算繁琐之外,这样做也可能会存在类似“共和国”那种情况,整体的凝固度满足要求,却由于里面的某个片段的凝固度较低,比如“和国”,导致“共和国”整体被过滤掉。
你说的也有道理,但其实吧,不管怎么处理,也各有各的问题,无监督终究有个上限~
February 11th, 2022
您好 看了您的文章受益匪浅,关于回溯您是回头检查,我有个想法不知合不合理,向您请教:我要做(2,n)的词库,当n=2时,如果ngram大于阈值,则将两个字都加入LIST,当n=3时,如果组成三个字词的所有词组(以abc为例,a与bc以及ab与c)都在LIST中,则计算abc的ngram,如果大于阈值则将其加入LIST,以此类推,计算出所有的ngram。
可以的~