一种中文领域概念词自动提取方法研究

董丽丽，李欢，张翔，刘闫锋

1.西安建筑科技大学信息与控制工程学院，西安 710055

2.陕西学前师范学院，西安 710100

一种中文领域概念词自动提取方法研究

董丽丽1，李欢1，张翔1，刘闫锋2

1.西安建筑科技大学信息与控制工程学院，西安 710055

2.陕西学前师范学院，西安 710100

针对统计学方法在领域概念获取时缺少词语语义信息的问题，提出了一种结合语义相似度和改进近邻传播算法的领域概念自动获取方法。该方法通过互信息进行合成词提取，使用对数似然比避免对低频词的遗漏，利用HowNet和余弦相似度识别术语间同义词，采用改进的近邻传播算法获取领域概念集合。实验结果表明，该方法在准确率、召回率和困惑度变化率上比传统的方法都有较大提高。

领域概念获取；改进近邻传播算法；对数似然比；语义相似度；互信息

领域本体在知识组织和语义网体系中具有核心地位，该领域已成为自然语言处理技术的研究热点。本体的构建主要包括领域概念获取、概念间关系获取以及公理获取三个部分。领域概念获取是本体构建的基础研究，其获取方法大致上可以分为三类：基于语言学的方法、基于统计学的方法和混合方法[1-3]。基于统计学的方法由于不局限于某一特定领域，并可识别未登录词所以成为目前概念获取的主流技术，其缺点是术语间缺乏必要的语义逻辑以及对低频词识别效果不佳。

为了克服统计学方法在概念获取时语义信息上的缺失，本文给出一种新的组合式领域概念获取算法，该算法结合语义相似度和统计学方法，并利用改进的近邻传播聚类算法（Affinity Propagation Cluster，APC）。首先在提取候选合成词语过程中，引入对数似然比统计量来度量两个元素出现的相关性；采用余弦公式和基于HowNet词语相似度计算方法计算出术语间的语义相似度，在相似度矩阵的基础上利用改进的近邻传播聚类得到领域概念词集合（Exemplar）。本文的方法有两个特点：第一是在传统候选合成词提取的技术上（互信息）融入似然比和语义相似度，提高了低频词识别的准确率并增强了概念的语义信息；第二是采用改进的近邻传播聚类算法，提高聚类算法的运行效率。

1 组合式领域概念获取新方法

本文的组合式领域概念获取方法主要步骤包括：首先将文本语料切分成一系列词串，然后进行粗降维；由于领域专业术语由合成词组成的概率较大，而分词后的术语常常被切分为散串，因此利用互信息值获取合成词，并引入似然比识别低频词；概念并不等同于术语，同一个概念语义可以由多个不同术语表达，因此直接将获取的术语作为概念并不完全正确[4]，例如术语“电脑”和“计算机”，它们互为同义词，本文通过AP算法来识别术语中的同义词，以获取概念集合。领域概念获取过程如图1所示。

图1 概念获取框架图

1.1 预处理中文文本预处理包括文本分词和粗降维。本文采用中科院的ICTCLAS作为分词工具，经过ICTCLAS分词后的文本可以表示为C=c1c2…cn，其中ci为一个单独词。粗降维就是从文本中去掉停用词，从而将文本切分为一系列的词串。切分后的文本表示为C=c1c2…ci/

ci+1…cj/cj+1…/…/cn。

1.2 候选术语提取

在获得文本词串的基础上，利用互信息对词串进行第一次筛选，并结合对数似然比获取候选术语集合。由于领域概念词以组合词出现的概率较大，可以通过计算字串间的互信息值（Mutual Information）确定字串是否是一个完整词。但是对于领域文本中专业低频词汇，采用互信息作为抽取参数是不行的。由于对数似然比对专业低频合成词的识别有较好鲁棒性，因此本文引入了对数似然比进行低频词的识别。

1.2.1 合成词抽取

互信息是评价两个字串之间关联程度的重要指标，其基本原理是若字串s=ab，其中a，b为分词后的词，则s的互信息MIs表示为公式（1）：

其中，f(.)为频率，P(.)为概率，F为字串总和。预先给定阈值t，若MIs＞t，a、b之间的关联度越高，则判定s是一个完整词。

1.2.2 低频领域术语提取

为了克服互信息对低频词语估计不准确的缺点，本文通过统计术语在领域文本语料（D）和背景语料中出现的文档数，建立假设检验来计算术语的领域相关度，从而获取低频术语。假设H1表示术语C出现在领域语料和背景语料的概率相同。假设H2表示术语C出现在领域语料和背景语料的概率不同[5]。H1和H2的定义分别为公式（2）、（3）：

似然比是一种假设检验的方法，对数似然比定义为公式（4）：

L(H1)和L(H2)分别表示H1和H2发生的可能性，由式（4）可以清晰地看出似然比越小，H2发生的可能性越大，为了更加准确获取领域相关术语，就需要得到高L(H2)和低L(H1)，因此在这里用公式（5）计算对数似然比，可以证明如果λ是似然比，那么-2lgλ逼近卡方分布。

为了统计概念c出现的文档，定义S(c，D)为概念c在领域语料中出现的集合，|S|为集合S的基数（元素个数）。定义如公式（6）：

其中，ND为领域文档总数，ND′为背景语料文档总数。最后，运用二项式分布假设求出L(H1)和L(H2)，各个术语的对数似然比值可由公式（8）进行计算，本文通过设置最小似然比筛选出最后的候选术语集合。

算法1候选术语提取

输入分词后的文本C=c1c2…ci/ci+1…cj/cj+1…/…/cn，其中C是预处理的输出；最小对数似然值t1，互信息阈值t2。

输出候选术语集合CT（Candidate Term）。

（1）将C中的词序列分割成MaxL-gram，（MaxL-1）-gram，…，1-gram，得到候选词集合CL（Candidate List）。

（2）若CL≡φ，转（7）。

（3）取s，其中s∈CL，CL=CL-s。

（4）计算互信息MIs，若MIs＜t2，转（2）。

（5）计算-2lgλS，若-2lgλS

（6）s是候选组合词，加入候选术语集CT=CT∪s。

（7）输出CT。

通过算法1完成候选合成术语的抽取，但是术语并不等同于概念，为了得到候选概念集合必须识别术语之间的同义词，从而得到领域概念集合。

1.3 概念提取

1.3.1 候选领域概念相似度计算

根据公式（6）得到的候选术语在领域语料中出现的次数(ncD)，构建“术语-文档”矩阵N[m][n]，其中，m为候选术语的数目，n为领域文档总数，N[i][j]表示候选术语i在文档j中出现的次数。衡量术语相似度最常用的方法就是余弦相似度，如公式（9）：

余弦系数法没有考虑词语的上下文语义环境[6]，但在实际生活中，所处的语境不同词语的具体语义也会有一定的差异，因此计算词语的相似度不应该忽略词语的上下文信息。本文引入HowNet词语相似度计算方法进行补充，如公式（10）：

新疆是温带大陆性气候，昼夜温差大，属典型的大陆性干燥气候。尤其是处于塔克拉玛干边缘的南疆部分地区，气候异常干燥，年降雨量较小，缺水严重，而当地土壤沙化现象严重，土壤保水能力差，缺水与土壤保水能力差的现状无疑增加当地棉花种植成本，成为制约当地经济快速发展的一个瓶颈。

其中，ε取经验值0.5；sim(Ti，Tj)表示HowNet中词语的相似度，根据反复实验设置HowNet的参数α=1.6，β1= 0.8，β2=0.18，β3=β4=0.01。表1给出部分候选领域术语之间的相似度计算结果。

表1 术语相似度

1.3.2 改进的近邻传播算法

Affinity Propagation（AP）算法[7]是根据数据集中各个点构成的相似度矩阵S找出领域概念集合，本文的相似度计算方法参见1.3.1节。AP算法要预先设定每个数据点k的偏向参数s(i，i)（Preference），也可将记为p(i)，p(i)作为点xi能否成为聚类中心的评判标准，该值越大，相应的点xi越有可能成为聚类中心，同时聚类的数量也受到p的影响。AP算法引入两种消息传递参数，分别为吸引度（responsibility），其表示为公式（11）和归属度（availability）其表示为公式（12）。其中，a(i，j)用来描述点xi选择点xj作为其聚类中心的适合程度；r(i，j)用来描述点xj适合作为点xi的聚类中心的程度。AP算法的核心就是不断迭代更新数据对间的消息值直到算法收敛为止，其迭代公式如式（13）和式（14），因此传统AP算法最大的问题是运算速度较长[8]，尤其是面对大规模的数据集合。

为了解决这个问题，Yangqing Jia等人提出了快速AP聚类算法（Fast Sparse Affinity Propagation，FSAP）[9]，改善了传统AP算法的运算时间，但是该算法是以牺牲准确率来提高运行效率，其聚类结果与传统AP算法聚类结果不同，为此本文采用的快速AP聚类算法，不仅保证与传统AP算法得到同样的聚类结果，同时减少算法迭代所花费的时间。AP算法的主要运算量就是不断更新数据点间传递的消息值[10]，为了改善算法的运行时间本文通过构建稀疏图G=[V，E]来存放数据点间的消息迭代，算法核心在于并非所有数据点间的吸引度和归属度的收敛值都需要通过迭代计算获得，本文运用上界/下界消息值来剪掉不必要的消息迭代计算，图G只包含需要迭代计算的消息传递。上界/下界消息值如定义1。

稀疏图G=[V,E]，V表示数据点集中的各个点，E表示数据点xi和xj间的消息传递，如定义2。

定义2（稀疏图）v是数据集中的所有点，当且仅当数据点xi和xj满足以下条件时才会连接一条边：

算法2快速AP聚类

输入候选术语集合CT（Candidate Term）

输出领域概念集合DC（Domain Concept）

（1）运用公式（10）计算sim(i ，j)，i，j ∈CT。

（4）运用公式（11）～（14）更新r(i,j)和a(i ,j)，i,j∈Eij。

（5）运用公式（11）、（12）计算ri=r(i，j)，ai=a(i，j)，i，j∉Eij。

（6）结合公式cj=argmax1≤j≤N[r(i，j)+a(i，j)]找出领域概念xi,xj∈DC。

2 实验结果与分析

实验领域文本语料集采用从万维网选取，包括计算机、经济、军事、机械等4个领域，并将“机械”作为目标领域，其他几类作为背景语料。为了便于比较，实验采用准确率（Precision）和召回率（Recall）作为评估标准，如式（19）和式（20）所示：

通过反复实验，发现当判定阈值逐渐增加时，准确率随之增加，但召回率下降，这是由于语料规模过小，造成了有些概念出现频率较低。为了显示语料规模对概念获取的影响，本文分别采用200篇、400篇、600篇、800篇、1 000篇文本语料进行概念抽取实验，结果如表2所示，可以看出准确率和召回率都随着语料规模的增大而增大。

表2 概念获取实验结果

为了便于比较，本文对k-means算法、传统AP算法和Yangqing Jia的FSAP算法作了实验，实验证明本文提出的快速AP算法与传统AP算法结果一致，与k-means和FSAP算法相比，快速AP算法在准确率和召回率上都有了明显的提高，如表3和表4所示。

表3 k-means算法实验结果

表4 FSAP算法实验结果

快速AP算法与k-means方法、FSAP算法准确率和召回率的对比图见图2和图3。

图2 准确率对比图

图3 召回率对比图

为了比较本文提出的快速AP聚类算法与传统AP算法的运行效率，图4显示了各方法在不同文档数上的运行时间，结果表明快速聚类在运行时间上有了明显的提高。

图4 算法运行时间对比图

基于准确率和召回率的评估标准需要人工在领域语料库中抽取概念，这导致评估的不可扩展性和主观性。本文利用困惑度变化率作为新的评估方法[11]，困惑度是衡量语言模型优劣的重要指标，它表示单个词后可能拼接词的平均数，困惑度越小，表明语言模型对上下文的约束力越强，本实验计算不同算法的困惑度变化率，值越大表明对领域语料有更好的预测能力。从表5可以看出，本文提出的组合式领域概念获取方法（称为A方法）比基于单一互信息的方法（称为B方法）的困惑度变化率大。

表5 困惑度变化率结果

3 总结

本文提出了一种新的领域概念词自动获取方法。算法结合语义相似度和统计方法，并改进传统近邻传播聚类，降低了运行时间。实验结果表明该算法在准确率、困惑度变化率和召回率都得到了明显的提高。从实验结论可以看出，概念的准确率和召回率受语料规模影响较大，因此，后续的工作将是考虑如何减小这种影响。

[1]Buitelaar P，Olejnik D.A protégé plug-in for ontology extraction from text based on linguistic analysis[C]//Proceedings of the International Semantic Web Conference，Miami，2004：31-44.

[2]Yan Gao.The hot keyphrase extraction based on TF*PDF[C]// 2011 International Joint Conference of IEEE TrustCom-11/ IEEE ICESS-11/FCST-11，Changsha，2011：1524-1528.

[3]Yang Qing.An area concept extraction algorithm based on association rule[C]//2010 International Conference of Information Science and Management Engineering，Qinhuangdao，2010：230-232.

[4]史东娜.基于半监督学习的特定领域术语抽取算法的研究[D].北京：北京邮电大学，2009.

[5]Manning C D，Schutze H.Foundations of statistical natural language processing[M].2nd ed.United States：[s.n.]，2000.

[6]何婷婷，张晓鹏.特定领域本体自动构造方法[J].计算机工程，2007，33（22）：235-237.

[7]Frey B J，Dueck D.Clustering by passing messages between data points[J].Science，2007，315（5814）：972-976.

[8]Fujiwara Y，Irie G.Fast algorithm for affinity propagation[C]// Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence，2011：2238-2243.

[9]Jia Yangqing，Wang Jingdong，Zhang Changshui.Finding image exemplars using fast sparse affinity propagation[C]// ACM Multimedia，Canada，2008：639-642.

[10]Qasim I，Jeong J W.Exploiting affinity propagation for automatic acquisition of domain concept in ontology learning[C]//2011 7th International Conference on Emerging Technologies，Islamabad，2011：1-6.

[11]傅继彬，樊孝忠.基于语言特性的中文领域术语抽取算法[J].北京理工大学学报，2010，30（3）：307-310.

DONG Lili1,LI Huan1,ZHANG Xiang1,LIU Yanfeng2

1.College of Information and Control Engineering,Xi’an University of Architecture and Technology,Xi’an 710055,China
2.Shaanxi Xueqian Normal University,Xi’an 710100,China

For statistical method lacks semantic information between words in domain concepts extraction,this paper presents a domain concept automatic extraction method,which combines semantic similarity and improved affinity propagation. The compound words are extracted by using mutual information,and then the log-likelihood is used to avoid the omission of low-frequency words,after that the synonyms between terms are identified by using HowNet and the cosine similarity. The improved affinity propagation algorithm is used to obtain the collection of domain concepts.The experimental results show that the method has higher accuracy,recall rate,and perplexity change ratio than the traditional method.

domain concept extraction;improved affinity propagation;log-likelihood;semantic similarity;mutual information

A

TP311

10.3778/j.issn.1002-8331.1205-0376

DONG Lili,LI Huan,ZHANG Xiang,et al.Method for automatic extraction of Chinese domain concepts.Computer Engineering and Applications,2014,50（6）：127-131.

陕西省自然科学基金（No.2012JM8042）；陕西省教育厅科研专项（No.12JK0940）。

董丽丽（1960—），女，教授，硕士生导师，主要研究方向为分布式系统与计算机网络应用、数据挖掘；李欢（1988—），女，硕士研究生，主要研究方向为分布式系统；张翔（1972—），男，副教授，主要研究方向为计算机可视化技术；刘闫锋（1979—），男，硕士研究生，主要研究方向为数据挖掘技术。E-mail：343239566@qq.com

2012-05-31

2012-08-27

1002-8331（2014）06-0127-05