【中文分词系列】 8. 更好的新词发现算法
By 苏剑林 | 2017-03-11 | 227007位读者 |如果依次阅读该系列文章的读者,就会发现这个系列共提供了两种从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://kexue.fm/archives/4256
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Mar. 11, 2017). 《【中文分词系列】 8. 更好的新词发现算法 》[Blog post]. Retrieved from https://kexue.fm/archives/4256
@online{kexuefm-4256,
title={【中文分词系列】 8. 更好的新词发现算法},
author={苏剑林},
year={2017},
month={Mar},
url={\url{https://kexue.fm/archives/4256}},
}
October 22nd, 2019
问个比较愚蠢的问题,如果基于互信息和信息熵做的新词发现(单词和短语), 我能将这些词放进TFIDF中作为语料,进而某个频道文章的提取关键词吗?
可以呀,你提取出来的新词跟普通词没什么差别。
May 27th, 2020
请问,计算权重,是根据一个n_gram只能被切成两个词来计算的吧?是不是可以将所有切分可能都遍历
计算量剧增而且没必要。
July 6th, 2020
剑林兄,受益良多,可否提供一份原始数据?
不可以。
如果你没场景,那就别无端端弄新词发现;如果你有场景,自然就不会缺数据。
August 15th, 2020
预处理的正则表达式估计是有bug,因为如果已经去掉了数字,为什么发现的词典里还有数字呢?
哦我错了。。是保留了中文、数字和字母。。。
January 20th, 2021
读完分词系列的最后一篇 有两处疑问想请苏神指点 :
1. "切分:用上述grams对语料进行切分(粗糙的分词),并统计频率。切分的规则是,只有一个片段出现在前一步得到的集合G中,这个片段就不切分,比如“各项目”,只要“各项”和“项目”都在G中,这时候就算“各项目”不在G中,那么“各项目”还是不切分,保留下来;" ------ 请问这段话我是否可以理解为 "对于一个片段 , 如果片段中的每个字都曾经在前面(更短)的某个片段中出现过 , 那么这个片段就不切分"? 感觉结合代码来看是这个意思 , 但是和苏神的表达"只有一个片段出现在前一步得到的集合G中,这个片段就不切分"有出入 , 不知道是否是我理解错了?
2."第三步,回溯:经过第二步,“各项目”会被切出来(因为第二步保证宁放过,不切错)。回溯就是检查,如果它是一个小于等于n字的词,那么检测它在不在G中,不在就出局;如果它是一个大于n字的词,那个检测它每个n字片段是不是在G中,只要有一个片段不在,就出局。还是以“各项目”为例,回溯就是看看,“各项目”在不在3gram中,不在的话,就得出局" ---- 举例一个demo来看 : 假如切出的一个词为 : "各项目组成员" , 结合本例n = 4 , 那么就要遍历"各项目组成员"中的所有4-gram : "各项目组" "项目组成" "目组成员" ... "目组成员" , 只要有一个不在之前的G中 , 就被放弃 ; 请问苏神我的这个理解正确吗?
第一个问题,你说了那么长,我还是没看懂你要表达什么意思。。。
第二个问题,答案是正确。
首先谢谢苏神的回复
对于第一个问题我重新组织下语言 : 就是我对"详细的算法"中的"第二步"有疑惑, 我觉得您的表述"只有一个片段出现在前一步得到的集合G中,这个片段就不切分" 这个表述和代码有出入 , 按照代码我的理解是 : 只要一个片段(abcde)中的每个字(a,b,c,d,e)都曾经作为其他片段中的某个部分出现过 , 那么即使这个片段本身(abcde)并没有出现过 , 那么这个片段(abcde)也不会被切分" 我不知道是自己理解代码有问题 还是确实是苏神的表述有问题 这里请苏神指点一下
我感觉我说的意思跟你说的意思一样啊,字符串是abcde,只要它的片段abc在G中,那么abc就不切开,只要cd、de在G中,那么cd、de就不切开,合起来就是abcde都不切开。
可能是因为我用语不严谨,“只有”改为“只要”,似乎更合理一些?
hhhh , 我就是这个意思 , 如果苏神的意思是"只要" , 那就没问题了 , 感谢苏神!
January 25th, 2021
苏神好,这篇博客花了比较长的时间理解,每一步是理解的,合起来感觉有点疑惑,有两个小问题
1.用分词再筛选的方式和ngrams词典的词汇量区别大吗,从词的过滤上看貌似很严格,比如一个5字词,所有位置的3字和4字词都要在ngrams
2.本文的主要目的是无监督的方式获取一个词典,能否用第一步计算的凝固度作为词典的频数,感觉上通过分词的方式会有一些损失,比如说“各项目”的分词最后少计算了一个频数(各项或者项目)
1. 筛选规则是我自己定的,如果你觉得不合理也可以改,这点无所谓;
2. 没看明白你说啥。对于基于字典的分词模型,其实对词的精细词频不是特别敏感,只要相对数量级对了,基本上都问题不大了。
January 25th, 2021
苏神好,还有个问题3
3.本文的思路是否可以理解为用凝固度+频数计算,凝固度作为一个比较核心的判断相关性的高低,这样好像更能理解一些
通过凝固度获取凝固的片段,通过凝固片段的自由扩展获得词的边界,而不需要另外通过边界熵来确定边界,使得长度可以任意长。
好的,谢谢苏神的解释,理解了
June 4th, 2021
苏神,无论是基于凝聚度的还是基于凝聚度加自由度的,空间度复杂度好高啊,除了基于分布式改写(我用了hive+hadoop streaming),还有好的改善方案吗?
你可以分层次做(本质上就是分成一个个相对比较小的文件,然后每个文件单独新词发现,然后把结果合并后再做一次筛选)
June 7th, 2021
苏神,医学领域词汇长度比较长。n-gram不大适用,HMM之类的效果也不好,您有什么好的思路么?
我不理解“医学专业词汇比较长,ngram不大适用”这个逻辑。
August 30th, 2021
所以,这里省去了左右熵的计算吗
是