一種中文領域概念詞自動提取方法研究

董麗麗，李歡，張翔，劉閆鋒

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