面向社会媒体的开放领域新词发现

2017-07-18张华平商建云

中文信息学报 2017年3期

关键词：互信息分词新词

张华平, 商建云

(1. 北京理工大学计算机学院，北京 100081；2. 北京市海量语言信息处理与云计算应用工程研究中心，北京 100081；3. 北京理工大学软件学院，北京 100081)

面向社会媒体的开放领域新词发现

张华平1，2, 商建云3

(1. 北京理工大学计算机学院，北京 100081；2. 北京市海量语言信息处理与云计算应用工程研究中心，北京 100081；3. 北京理工大学软件学院，北京 100081)

随着互联网的发展，社会媒体已经逐渐发展成为信息交流的重要载体。该文针对社会媒体文本的领域分布广、口语化程度高等特征，提出一种面向社会媒体的开放领域新词发现算法。此算法所有步骤均为线性时间复杂度，并且在分析过程中有效降低了内存的使用，从而能够实时处理社会媒体所产生的大规模数据。在6.6 GB 社会媒体文本语料中的新词发现准确率达到了87.2%，在普通计算机上新词发现速度可达2.6 MB/s。与传统算法相比，该算法在社会媒体领域的大规模语料中速度及精度上均有较好的效果。

社会媒体；新词发现；条件随机场

1 引言

随着以微博、微信为代表的新型互联网社交应用的发展及普及，社会媒体已经逐渐发展成信息传递的重要载体，并且融入到了人们的日常生活之中。但是社会媒体具有领域分布广、口语化程度高等特点，为针对此类文本的分析带来了挑战。社会媒体文本往往伴随着大量未登录词的出现，若未能有效且实时地识别这些未登录词语，会直接影响着以分词为基础的上层分析任务(如情感计算、依存句法)分析的效果。

针对新闻等书面语语料新词发现算法能够处理的数据量小且词法、语法规范、正式，研究者大多采用时间复杂度高的频繁项发现算法，或者采用手工标记的垃圾串模板过滤不正确的新词结果。社交媒体具有口语化、来源广泛和数据量大等特点，上述算法具有一定的局限性。首先，内存占用会随着文本规模呈线性甚至是平方规模增加，因此被计算机硬件资源所限制，不能处理规模过大的语料。其次，大规模的口语化语料会导致垃圾串模板的构建更加复杂，不但需要更多的人工标注，模板精度及召回率也会受到极大的影响。从另外一个角度讲，社会媒体文本涵盖领域比较广，并不是仅限于某些特定的领域，特别是对“神马”等不属于某一特定领域的词语，并不适合于领域相关的新词发现[1]。

本文提出一种使用基于CRF模型的字标注分词算法作为候选词提取。在使用最大熵模型过滤人名等命名实体的基础上，构成候选词集，再将候选词集与二元语法分词模型结合对文本语料重新分词，从而获得候选词在语料中的全局特征，使用统计的方法进行垃圾串过滤和新词发现。这种方法能够将CRF分词高效的未登录词识别与基于全局特征的垃圾串过滤方法结合，所有的步骤均为线性的时间复杂度。

2 相关工作

基于统计的新词发现算法，目前主要分为以下两类。

第一类为基于对语料库的频繁模式的发现。2003年，Huang等人提出了一种使用邻接熵和互信息作为特征进行新词发现的方法[2]。在频繁模式的基础上，计算频繁串在语料库中的左右熵和互信息，通过这两个全局特征进行新词发现。崔世起等人使用自学习方法建立垃圾词典，用垃圾词典和基于词性等统计信息对中文分词结果中提取的候选新词进行过滤的方法实现了基于Internet的在线新词检测系统[3]。此类算法需要涉及频繁项的迭代发现以及上下文信息的获取，时间复杂度和空间复杂度较高，不适合大规模语料的处理。

第二类为使用标注模型进行新词发现。2003年，薛念文将中文分词问题转换成使用LMR标注集对汉字的标注问题[4]，实验证明基于字标注的方法能够大幅度提高未登录词识别的效果。其后随着条件随机场的提出和在自然语言处理领域的应用，2004年，Peng使用CRF模型计算汉语片段的置信度在分词的同时提取新词[5]。这一类的算法基于一个词上下文的局部特征，由于局部特征相对于词在所有文档中的全局特征来说所包含的信息较少，作为新词发现方法，它的准确率并不高。

2013年，陈飞等人使用CRF模型及数据离散化方法综合词边界的特征实现开放领域的新词抽取算法[1]，并将以上两种方法进行结合。苏其龙整理和提出了一种微博新词发现的方法，将频繁项与CRF模型结合。但是以上两种算法都仅在小规模数据集上进行测试，对于大规模的语料未有相关的研究。

在新词发现的特征选择方面，Huang 提出了一种使用邻接熵作为候选词外部特征，选择互信息作为候选词内部成词概率的算法，在其后的新词发现和汉语分词论文中被多次使用[1，6]。Luo 比较了九种常见的词内部特征计算方法，实验表明使用互信息的效果最好[7]。

3 新词发现

本文提出的算法将上述两类统计新词发现方法相结合。使用CRF模型进行候选词提取，相比于频繁模式的提取，可以加快候选词提取速度以及降低内存占用。其后使用二元语法模型重新扫描语料，进行左右熵和互信息两个特征的抽取，弥补第二类方法在仅使用局部特征中的不足。

新词发现分为四个步骤，分别是候选词提取、命名实体过滤，新词特征选择，特征计算与候选排序。

3.1 候选词提取

本文使用基于CRF的字标注模型(以下简称CRF模型)对语料进行分词，提取频数超过一定阈值的词作为候选词。

其中，CRF模型是将中文分词的过程看成是一个汉字边界的序列标注问题[4]，通常使用BMES标注集，即一个词语的首字标注为B，尾字标注成E，中间的字标注成M，单个字组成词的标注成S。使用此模型进行分词时，词本身以及上下文等特征都成为一个片段是否构成词的影响因素，因此对于词典中不存在的未登录词具有较高的召回率。但是受限于特征选取的窗口大小，一个片段成词的概率仅仅由这个片段特征窗口大小的上下文所决定。根据文献[8]的实验结果，使用CRF模型进行中文分词的未登录词召回率大约为0.73。

CRF模型中的未登录词的正确切分依赖于其自身组成以及上下文特征，在某些上下文环境中的切分错误，切换到不同上下文中就可能正确切分，且错误的分词结果极大的与上下文相关，即在语料库足够大的情况下，大多数未登录词正确的切分词频总是大于错误切分。实验表明，CRF模型中92%以上错误切分产生字串的词频在三次以下。因此，使用CRF分词作为新词提取是可行的，即将CRF模型的分词结果以(词, 词频)的方式保存成词表。在词表中选择词频大于某一阈值的未登录词作为候选词即可。这种算法的时间复杂度是线性的，需要在内存中存储的仅仅是词表。

阈值根据待发现新词语料的大小变化而变化，呈正相关关系。本文选择arctan函数根据语料库大小选择相应的阈值。

3.2 命名实体过滤

在实验结果中发现，由CRF分词结果构成的候选词集中大约有1/4左右的新词为命名实体，新闻语料中这一比例甚至达到了1/2。目前对于命名实体识别已经取得了较好的效果[9]，不需要单独为命名实体构建词表。同时为了降低在后续处理中的内存使用，需要在候选词集中对命名实体进行过滤。

在组织以及机构名过滤方面，在训练CRF模型中使用细粒度切分的语料即可将此类命名实体切分成细粒度的词语，从而过滤“北京理工大学”“中国科学院计算技术研究所”等组织以及机构名。

在中文人名过滤方面，因为中文人名的规律性非常强，无论是作为首字符的姓氏，还是“玲”、“雯”等常作为名字出现的汉字，识别人名相对于其他词语或者命名实体要简单。

最大熵模型适合于这一类基于特征的分类任务，特征选择为“B: 首字符”“E: 尾字符”“M: 中间字符”。样本使用中文人名库中频率最高的63 704个姓名作为正例，使用《人民日报》语料词表中的 85 144个词(已过滤掉人名)作为反例。从这148 848个样本中随机选择90%作为训练集，剩余10%作为测试集，实验结果准确率为94.7%。

在这一步骤中因为仅仅需要针对候选词集进行分类，运算时间相比于其他步骤可以忽略不计(词表的大小远远小于语料库的大小)。

3.3 新词特征选择

社会网络文本相比于传统的新闻预料，特点是以口语为主，并且常常夹带错词、方言或者其他语言以及符号。如果通过手工标记模板方式过滤垃圾串，需要投入巨大的人力资源，且错误率较大。因此本文使用基于统计的方法对候选词按照成词的可能性从高到低进行排序。

CRF模型将字作为分词的处理单元，对字进行边界标注而成为词语，因此这种分词模型主要会产生两类对新词发现结果造成影响的分词错误。第一类为分离型分词错误，比如错误的切分结果“思乱想(对应于‘胡思乱想’)”等，第二类为组合型分词错误，即将两个连续的词语未能正确切分开来，比如“吃火锅(对应于‘吃/火锅’)”。

特征选择的整体思路是找到两类特征分别能够过滤掉以上两类主要分词错误。针对第一类错误的切分，本文使用邻接熵特征进行过滤；针对第二类的错误切分，本文选择语言模型计算互信息特征进行过滤。

3.3.1 邻接熵

邻接熵是一种计算候选词上下文丰富程度的特征。候选词上下文越丰富代表它成词的概率越高[1]，这时它的邻接熵也就越高。邻接熵HADJ计算如式(2)所示。

选择左侧和右侧信息熵的最小值作为候选词的邻接熵，可以有效过滤CRF模型分词中词语内部的分离式错误切分，比如错误的切分结果“思乱想(对应于‘胡思乱想’)”，在语料中它左边只可能出现“胡”字，因此左信息熵为0，从而实现过滤。

3.3.2 语言模型

区别于邻接熵，互信息反映候选词内部特征，值越大代表候选词内部凝固程度越高，因此成词的概率也就越大。使用互信息能够有效地过滤类似于“吃火锅(对应于‘吃/火锅’)”的CRF模型组合式分词错误。

此时可以将二元语法模型引入互信息的计算，从而使得其过滤组合错分的候选词能力更强。文献[1]中，互信息计算方式为

其中，w1、w2为w的组成部分，P(w)表示词w在语料中出现的概率。这种计算方法有一定的缺陷。首先，类似于“排山倒海”等成语，很多词语并不仅仅由两部分组成。其次，对于一些频繁共同出现但不构成词的序列，比如“了一”等，上述互信息计算方法过滤的效果不佳。本文将二元语法模型与上述公式结合，提出一种改进后的类互信息的计算方法，即：

3.4 特征计算与候选排序

在获得候选词集之后，需要对语料进行第二遍的扫描，用以计算候选词集中各词的邻接熵及互信息的值。本文选择二元语法模型，将候选词集中的各词以(候选词, 词频)的形式，加入到二元语法模型分词程序的用户词典中，对于语料重新切分。

N元语法模型分词对字符Cn序列组成的文本T=C1C2C3C4…Cn，寻找到词语序列w1w2w3…wn

与上文相同P(wn|wn-1)利用Jelinek-Mercer平滑方法计算。

w1,w2…，wn序列可以使用Beam Search等动态规划方法以O(n)的时间复杂度获得。

本文选择使用二元语法模型进行重新扫描而非在CRF模型的分词结果中计算特征。首先，使用后者会造成额外的磁盘空间的消耗且二元语法模型分词的速度已经足够快。其次，CRF模型中对于未登录词的切分主要依赖于上下文的边界信息，因此语料中的候选词不一定在所有位置都正确切分，需要使用基于词表和语言模型的分词算法重新分词和计算特征。

在二元语法模型分词的过程中，分别记录每个候选词左右两侧出现的词及其频率，以及这个词本身的频率，前者用于邻接熵的计算，后者用于互信息的计算。

一旦获得了每个候选词邻接熵和互信息的值，分别去除邻接熵和互信息最低的10%的候选词，使用线性插值法获得每个候选词的权重，即

4 实验

4.1 实验数据

本文使用爬虫抓取的网易2012—2013年的新闻、体育、科技和教育栏目语料总共约3.2 GB的纯文本，此外使用爬虫抓取了Twitter 4 000万左右的中文微博，去掉重复内容，并将繁体字统一转化为简体字后得到3.4 GB的纯文本(两者编码均为UTF-8)，组成总共6.6 GB的纯文本测试语料。

此外，为了测试新词发现的准确率，将第一步即候选词提取所获得的82 902条候选词及每个候选词的三个例句放于网上以众包的方式进行标注，产生标注集R。标注内容是该候选词是否为词，为了增加标注的一致性，网站定义词的标准为： (1) 拆分后意思不变的不是词，如“专用飞机”。(2) 明显由两个词构成的常见片段不是词，如“的是”。(3) 数字、人名不是词。至撰写本文为止，总共获得12 764条有效标注，其中正例8 365条，反例4 399条(有部分频数较低的词语在后面实验中未能用到)。

4.2 实验结果

实验所用的计算机为2012年产Macbook Air，Core i5，4 GB内存，128 GB固态硬盘。

本文分别测试了排序结果前10%、20%、30%至100%的准确率(见表1)。准确率即所测试的词语集合中，出现标注集正例的个数与出现标注集词语个数的比值，见式(10)。

表1 不同特征对于各区域准确率的影响，α=0.2

此外针对排序结果分成区域，对每个区域的正确率进行测试，如式(11)所示。

表2 不同特征下的权值最高的新词

表3 不同的α取值对准确率的影响

从实验结果(见表1和表3)看，使用互信息作为特征抽取新词的效果好于邻接熵，两种特征结合的效果明显好于单个特征。互信息作为特征时倾向于将由不单独成词的字组成的长词排序靠前，如“邻苯二甲酸酯”“斯坦科维奇杯”，而邻接熵则倾向于将常用的词语筛选出来，如“访民”“堪比”等。这两种特征从不同的角度反映一个候选词成词的可能性，具有互补性。

对于特征结合中线性插值系数α的选择，本文分别使用结果中前30%词语的正确率P30%和前50%词语的正确率P50%测试不同的α值对于实验结果的影响。实验结果(表3)表明，选择α在[0.1, 0.2)区间时效果最好。

表4 不同算法的召回以及精度

不同算法召回权值最高的新词见表5，文献[5](Peng04)的算法与本文算法类似，因为二者都以CRF模型分词为基础，比较倾向于找出细粒度的词语。其差别是本文算法使用全局特征计算权重，而Peng04使用局部上下文的特征，后者局部的噪音对精度影响较大。文献[10]的算法正好相反，比较倾向于召回粗粒度的词语，这个与它基于频繁模式的候选集挖掘算法有关，比较利于找出命名实体或者一些常用短语。从某种程度上讲，本文算法与文献[10]算法可以起到互补的作用。

表5 不同算法召回权值最高的新词

图1 语料库大小与运行时间的关系

对于算法效率的实验，从6.6 GB的测试语料中抽取6份子集，分别为0.5 GB、1 GB、1.5 GB、2 GB、4 GB、6.3 GB，对每份语料使用本文算法进行新词发现，计算运行时间及平均速度，最终结果如图1所示。新词发现运行的时间与语料库的规模成正比且处理速度不随语料库大小的变化而改变，始终稳定在2.6MB/s左右。实验结果映证了本文算法O(n)的时间复杂度。

在线程数与处理速度关系的实验中，选择大小为1 GB的测试语料，分别使用1～4个线程进行新词发现，结果如图2所示。实验结果表明，新词发现的处理速度与线程数呈正相关的关系。此处线程数与处理速度并非呈现线性关系，主要原因是更新词频表和邻接词表的过程中使用到了互斥锁进行同步。线程同步造成的开销可以通过分配多个数据副本或者使用非阻塞的互斥锁机制减轻同步机制对多线程效率的影响。

图2 线程数与新词发现处理速度关系

5 结论

本文系统地研究了面向社会媒体的中文新词发现方法，分析了目前现有新词发现算法不适合处理大规模语料及口语为主文本的原因。提出了一种面向大规模社会媒体语料的快速新词发现算法。该算法结合文献[2，11]的新词发现算法，利用CRF字标注模型对原始语料进行分词后提取新词的候选词集，然后使用二元语法模型根据新词的候选词集重新切分语料，提取候选词集各词的左右熵、互信息特征，实现候选词的排序，成词概率越高的候选词排序越靠前。最终从排序结果中选取一定比例的词语作为发现的新词。该方法有效地避免了传统新词发现算法中后缀树的构建，以及对于全局状态的依赖，从而实现了面向大规模语料的快速新词发现算法。此外本文实验比较了不同特征选择及参数选取对于实验结果的影响，验证了本文算法的新词发现准确性及线性的时间复杂度。

[1] 陈飞, 刘奕群, 魏超, 等. 基于条件随机场方法的开放领域新词发现[J]. 软件学报, 2013, 24(5): 1051-1060.

[2] Huang J H, Powers D. Chinese word segmentation based on contextual entropy[C]//Proceedings of the 17th Asian Pacific Conference on Language, Information and Computation. 2003: 152-158.

[3] 崔世起, 刘群, 孟遥,等. 基于大规模语料库的新词检测[J]. 计算机研究与发展, 2006, 43(5): 927-932.

[4] Xue N, Shen L. Chinese word segmentation as LMR tagging[C]//Proceedings of the 2nd SIGHAN Workshop on Chinese Language Processing-Volume 17. Association for Computational Linguistics, 2003: 176-179.

[5] Feng F, McCallum A. Chinese segmentation and new word detection using conditional random fields[C]// Proceedings of the 20th International Conference on Computational Linguistics (COLING’ 04), Geneva, Switzerland, 2004:562-568.

[6] Zhang H, Gao J, Huang H. Incorporating new words detection with Chinese word segmentation[C]//Proceedings of CIPS-SIGHAN Joint Conference on Chinese Language Processing (CLP 2010). Beijing, China. 2010: 249-251.

[7] Luo S, Sun M. Two-character Chinese word extraction based on hybrid of internal and contextual measures[C]//Proceedings of the 2nd SIGHAN Workshop on Chinese Language Processing-Volume 17. Association for Computational Linguistics, 2003: 24-30.

[8] Tseng H, Chang P, Andrew G, et al. A conditional random field wordsegmenter for SIGHAN bakeoff 2005[C]//Proceedings of the 4th SIGHAN Workshop on Chinese Language Processing. 2005, 171.

[9] 张华平, 刘群. 基于角色标注的中国人名自动识别研究[J]. 计算机学报, 2004, 27(1): 85-91.

[10] 顾森. 基于大规模语料的新词发现算法[N].程序员.2012,07.

[11] 丁溪源. 基于大规模语料的中文新词抽取算法的设计与实现[D]. 南京理工大学硕士学位论文, 2011.

SocialMedia-orientedOpenDomainNewWordDetection

ZHANG Huaping1，2, SHANG Jianyun3

(1. Department of Computer, Beijing Institute of Technology, Beijing 100081, China; 2. Beijing Engineering Research Center of Massive Language Information Processing and Cloud Computing Application, Beijing 100081,China; 3. School of Software Tachnology, Beijing Institute of Technology, Beijing 100081, China)

With the development of Internet, social media has become an important channel for information transmission. Focused on characteristics of the informal language in various domains inherent in social media, this paper proposes a social media-oriented open domain new word detection method. This approach can be executed in linear time complexity with a reduced memory usage, which enables real time processing large size data produced by social media. The experiment on a 6.6GB social media corpus reveal a processing speed of 2.6MB/s in normal PC, as well as 87.2% precision.

social media; Chinese new word extraction; conditional random field