一種中文領(lǐng)域概念詞自動提取方法研究

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

1.西安建筑科技大學(xué)信息與控制工程學(xué)院，西安 710055

2.陜西學(xué)前師范學(xué)院，西安 710100

一種中文領(lǐng)域概念詞自動提取方法研究

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

1.西安建筑科技大學(xué)信息與控制工程學(xué)院，西安 710055

2.陜西學(xué)前師范學(xué)院，西安 710100

針對統(tǒng)計學(xué)方法在領(lǐng)域概念獲取時缺少詞語語義信息的問題，提出了一種結(jié)合語義相似度和改進(jìn)近鄰傳播算法的領(lǐng)域概念自動獲取方法。該方法通過互信息進(jìn)行合成詞提取，使用對數(shù)似然比避免對低頻詞的遺漏，利用HowNet和余弦相似度識別術(shù)語間同義詞，采用改進(jìn)的近鄰傳播算法獲取領(lǐng)域概念集合。實驗結(jié)果表明，該方法在準(zhǔn)確率、召回率和困惑度變化率上比傳統(tǒng)的方法都有較大提高。

領(lǐng)域概念獲??；改進(jìn)近鄰傳播算法；對數(shù)似然比；語義相似度；互信息

領(lǐng)域本體在知識組織和語義網(wǎng)體系中具有核心地位，該領(lǐng)域已成為自然語言處理技術(shù)的研究熱點。本體的構(gòu)建主要包括領(lǐng)域概念獲取、概念間關(guān)系獲取以及公理獲取三個部分。領(lǐng)域概念獲取是本體構(gòu)建的基礎(chǔ)研究，其獲取方法大致上可以分為三類：基于語言學(xué)的方法、基于統(tǒng)計學(xué)的方法和混合方法[1-3]?；诮y(tǒng)計學(xué)的方法由于不局限于某一特定領(lǐng)域，并可識別未登錄詞所以成為目前概念獲取的主流技術(shù)，其缺點是術(shù)語間缺乏必要的語義邏輯以及對低頻詞識別效果不佳。

為了克服統(tǒng)計學(xué)方法在概念獲取時語義信息上的缺失，本文給出一種新的組合式領(lǐng)域概念獲取算法，該算法結(jié)合語義相似度和統(tǒng)計學(xué)方法，并利用改進(jìn)的近鄰傳播聚類算法（Affinity Propagation Cluster，APC）。首先在提取候選合成詞語過程中，引入對數(shù)似然比統(tǒng)計量來度量兩個元素出現(xiàn)的相關(guān)性；采用余弦公式和基于HowNet詞語相似度計算方法計算出術(shù)語間的語義相似度，在相似度矩陣的基礎(chǔ)上利用改進(jìn)的近鄰傳播聚類得到領(lǐng)域概念詞集合（Exemplar）。本文的方法有兩個特點：第一是在傳統(tǒng)候選合成詞提取的技術(shù)上（互信息）融入似然比和語義相似度，提高了低頻詞識別的準(zhǔn)確率并增強了概念的語義信息；第二是采用改進(jìn)的近鄰傳播聚類算法，提高聚類算法的運行效率。

1 組合式領(lǐng)域概念獲取新方法

本文的組合式領(lǐng)域概念獲取方法主要步驟包括：首先將文本語料切分成一系列詞串，然后進(jìn)行粗降維；由于領(lǐng)域?qū)I(yè)術(shù)語由合成詞組成的概率較大，而分詞后的術(shù)語常常被切分為散串，因此利用互信息值獲取合成詞，并引入似然比識別低頻詞；概念并不等同于術(shù)語，同一個概念語義可以由多個不同術(shù)語表達(dá)，因此直接將獲取的術(shù)語作為概念并不完全正確[4]，例如術(shù)語“電腦”和“計算機”，它們互為同義詞，本文通過AP算法來識別術(shù)語中的同義詞，以獲取概念集合。領(lǐng)域概念獲取過程如圖1所示。

圖1 概念獲取框架圖

1.1 預(yù)處理中文文本預(yù)處理包括文本分詞和粗降維。本文采用中科院的ICTCLAS作為分詞工具，經(jīng)過ICTCLAS分詞后的文本可以表示為C=c1c2…cn，其中ci為一個單獨詞。粗降維就是從文本中去掉停用詞，從而將文本切分為一系列的詞串。切分后的文本表示為C=c1c2…ci/

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

1.2 候選術(shù)語提取

在獲得文本詞串的基礎(chǔ)上，利用互信息對詞串進(jìn)行第一次篩選，并結(jié)合對數(shù)似然比獲取候選術(shù)語集合。由于領(lǐng)域概念詞以組合詞出現(xiàn)的概率較大，可以通過計算字串間的互信息值（Mutual Information）確定字串是否是一個完整詞。但是對于領(lǐng)域文本中專業(yè)低頻詞匯，采用互信息作為抽取參數(shù)是不行的。由于對數(shù)似然比對專業(yè)低頻合成詞的識別有較好魯棒性，因此本文引入了對數(shù)似然比進(jìn)行低頻詞的識別。

1.2.1 合成詞抽取

互信息是評價兩個字串之間關(guān)聯(lián)程度的重要指標(biāo)，其基本原理是若字串s=ab，其中a，b為分詞后的詞，則s的互信息MIs表示為公式（1）：

其中，f(.)為頻率，P(.)為概率，F(xiàn)為字串總和。預(yù)先給定閾值t，若MIs＞t，a、b之間的關(guān)聯(lián)度越高，則判定s是一個完整詞。

1.2.2 低頻領(lǐng)域術(shù)語提取

為了克服互信息對低頻詞語估計不準(zhǔn)確的缺點，本文通過統(tǒng)計術(shù)語在領(lǐng)域文本語料（D）和背景語料中出現(xiàn)的文檔數(shù)，建立假設(shè)檢驗來計算術(shù)語的領(lǐng)域相關(guān)度，從而獲取低頻術(shù)語。假設(shè)H1表示術(shù)語C出現(xiàn)在領(lǐng)域語料和背景語料的概率相同。假設(shè)H2表示術(shù)語C出現(xiàn)在領(lǐng)域語料和背景語料的概率不同[5]。H1和H2的定義分別為公式（2）、（3）：

似然比是一種假設(shè)檢驗的方法，對數(shù)似然比定義為公式（4）：

L(H1)和L(H2)分別表示H1和H2發(fā)生的可能性，由式（4）可以清晰地看出似然比越小，H2發(fā)生的可能性越大，為了更加準(zhǔn)確獲取領(lǐng)域相關(guān)術(shù)語，就需要得到高L(H2)和低L(H1)，因此在這里用公式（5）計算對數(shù)似然比，可以證明如果λ是似然比，那么-2lgλ逼近卡方分布。

為了統(tǒng)計概念c出現(xiàn)的文檔，定義S(c，D)為概念c在領(lǐng)域語料中出現(xiàn)的集合，|S|為集合S的基數(shù)（元素個數(shù)）。定義如公式（6）：

其中，ND為領(lǐng)域文檔總數(shù)，ND′為背景語料文檔總數(shù)。最后，運用二項式分布假設(shè)求出L(H1)和L(H2)，各個術(shù)語的對數(shù)似然比值可由公式（8）進(jìn)行計算，本文通過設(shè)置最小似然比篩選出最后的候選術(shù)語集合。

算法1候選術(shù)語提取

輸入分詞后的文本C=c1c2…ci/ci+1…cj/cj+1…/…/cn，其中C是預(yù)處理的輸出；最小對數(shù)似然值t1，互信息閾值t2。

輸出候選術(shù)語集合CT（Candidate Term）。

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

（2）若CL≡φ，轉(zhuǎn)（7）。

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

（4）計算互信息MIs，若MIs＜t2，轉(zhuǎn)（2）。

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

（6）s是候選組合詞，加入候選術(shù)語集CT=CT∪s。

（7）輸出CT。

通過算法1完成候選合成術(shù)語的抽取，但是術(shù)語并不等同于概念，為了得到候選概念集合必須識別術(shù)語之間的同義詞，從而得到領(lǐng)域概念集合。

1.3 概念提取

1.3.1 候選領(lǐng)域概念相似度計算

根據(jù)公式（6）得到的候選術(shù)語在領(lǐng)域語料中出現(xiàn)的次數(shù)(ncD)，構(gòu)建“術(shù)語-文檔”矩陣N[m][n]，其中，m為候選術(shù)語的數(shù)目，n為領(lǐng)域文檔總數(shù)，N[i][j]表示候選術(shù)語i在文檔j中出現(xiàn)的次數(shù)。衡量術(shù)語相似度最常用的方法就是余弦相似度，如公式（9）：

余弦系數(shù)法沒有考慮詞語的上下文語義環(huán)境[6]，但在實際生活中，所處的語境不同詞語的具體語義也會有一定的差異，因此計算詞語的相似度不應(yīng)該忽略詞語的上下文信息。本文引入HowNet詞語相似度計算方法進(jìn)行補充，如公式（10）：

新疆是溫帶大陸性氣候，晝夜溫差大，屬典型的大陸性干燥氣候。尤其是處于塔克拉瑪干邊緣的南疆部分地區(qū)，氣候異常干燥，年降雨量較小，缺水嚴(yán)重，而當(dāng)?shù)赝寥郎郴F(xiàn)象嚴(yán)重，土壤保水能力差，缺水與土壤保水能力差的現(xiàn)狀無疑增加當(dāng)?shù)孛藁ǚN植成本，成為制約當(dāng)?shù)亟?jīng)濟快速發(fā)展的一個瓶頸。

其中，ε取經(jīng)驗值0.5；sim(Ti，Tj)表示HowNet中詞語的相似度，根據(jù)反復(fù)實驗設(shè)置HowNet的參數(shù)α=1.6，β1= 0.8，β2=0.18，β3=β4=0.01。表1給出部分候選領(lǐng)域術(shù)語之間的相似度計算結(jié)果。

表1 術(shù)語相似度

1.3.2 改進(jìn)的近鄰傳播算法

Affinity Propagation（AP）算法[7]是根據(jù)數(shù)據(jù)集中各個點構(gòu)成的相似度矩陣S找出領(lǐng)域概念集合，本文的相似度計算方法參見1.3.1節(jié)。AP算法要預(yù)先設(shè)定每個數(shù)據(jù)點k的偏向參數(shù)s(i，i)（Preference），也可將記為p(i)，p(i)作為點xi能否成為聚類中心的評判標(biāo)準(zhǔn)，該值越大，相應(yīng)的點xi越有可能成為聚類中心，同時聚類的數(shù)量也受到p的影響。AP算法引入兩種消息傳遞參數(shù)，分別為吸引度（responsibility），其表示為公式（11）和歸屬度（availability）其表示為公式（12）。其中，a(i，j)用來描述點xi選擇點xj作為其聚類中心的適合程度；r(i，j)用來描述點xj適合作為點xi的聚類中心的程度。AP算法的核心就是不斷迭代更新數(shù)據(jù)對間的消息值直到算法收斂為止，其迭代公式如式（13）和式（14），因此傳統(tǒng)AP算法最大的問題是運算速度較長[8]，尤其是面對大規(guī)模的數(shù)據(jù)集合。

為了解決這個問題，Yangqing Jia等人提出了快速AP聚類算法（Fast Sparse Affinity Propagation，F(xiàn)SAP）[9]，改善了傳統(tǒng)AP算法的運算時間，但是該算法是以犧牲準(zhǔn)確率來提高運行效率，其聚類結(jié)果與傳統(tǒng)AP算法聚類結(jié)果不同，為此本文采用的快速AP聚類算法，不僅保證與傳統(tǒng)AP算法得到同樣的聚類結(jié)果，同時減少算法迭代所花費的時間。AP算法的主要運算量就是不斷更新數(shù)據(jù)點間傳遞的消息值[10]，為了改善算法的運行時間本文通過構(gòu)建稀疏圖G=[V，E]來存放數(shù)據(jù)點間的消息迭代，算法核心在于并非所有數(shù)據(jù)點間的吸引度和歸屬度的收斂值都需要通過迭代計算獲得，本文運用上界/下界消息值來剪掉不必要的消息迭代計算，圖G只包含需要迭代計算的消息傳遞。上界/下界消息值如定義1。

稀疏圖G=[V,E]，V表示數(shù)據(jù)點集中的各個點，E表示數(shù)據(jù)點xi和xj間的消息傳遞，如定義2。

定義2（稀疏圖）v是數(shù)據(jù)集中的所有點，當(dāng)且僅當(dāng)數(shù)據(jù)點xi和xj滿足以下條件時才會連接一條邊：

算法2快速AP聚類

輸入候選術(shù)語集合CT（Candidate Term）

輸出領(lǐng)域概念集合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）結(jié)合公式cj=argmax1≤j≤N[r(i，j)+a(i，j)]找出領(lǐng)域概念xi,xj∈DC。

2 實驗結(jié)果與分析

實驗領(lǐng)域文本語料集采用從萬維網(wǎng)選取，包括計算機、經(jīng)濟、軍事、機械等4個領(lǐng)域，并將“機械”作為目標(biāo)領(lǐng)域，其他幾類作為背景語料。為了便于比較，實驗采用準(zhǔn)確率（Precision）和召回率（Recall）作為評估標(biāo)準(zhǔn)，如式（19）和式（20）所示：

通過反復(fù)實驗，發(fā)現(xiàn)當(dāng)判定閾值逐漸增加時，準(zhǔn)確率隨之增加，但召回率下降，這是由于語料規(guī)模過小，造成了有些概念出現(xiàn)頻率較低。為了顯示語料規(guī)模對概念獲取的影響，本文分別采用200篇、400篇、600篇、800篇、1 000篇文本語料進(jìn)行概念抽取實驗，結(jié)果如表2所示，可以看出準(zhǔn)確率和召回率都隨著語料規(guī)模的增大而增大。

表2 概念獲取實驗結(jié)果

為了便于比較，本文對k-means算法、傳統(tǒng)AP算法和Yangqing Jia的FSAP算法作了實驗，實驗證明本文提出的快速AP算法與傳統(tǒng)AP算法結(jié)果一致，與k-means和FSAP算法相比，快速AP算法在準(zhǔn)確率和召回率上都有了明顯的提高，如表3和表4所示。

表3 k-means算法實驗結(jié)果

表4 FSAP算法實驗結(jié)果

快速AP算法與k-means方法、FSAP算法準(zhǔn)確率和召回率的對比圖見圖2和圖3。

圖2 準(zhǔn)確率對比圖

圖3 召回率對比圖

為了比較本文提出的快速AP聚類算法與傳統(tǒng)AP算法的運行效率，圖4顯示了各方法在不同文檔數(shù)上的運行時間，結(jié)果表明快速聚類在運行時間上有了明顯的提高。

圖4 算法運行時間對比圖

基于準(zhǔn)確率和召回率的評估標(biāo)準(zhǔn)需要人工在領(lǐng)域語料庫中抽取概念，這導(dǎo)致評估的不可擴展性和主觀性。本文利用困惑度變化率作為新的評估方法[11]，困惑度是衡量語言模型優(yōu)劣的重要指標(biāo)，它表示單個詞后可能拼接詞的平均數(shù)，困惑度越小，表明語言模型對上下文的約束力越強，本實驗計算不同算法的困惑度變化率，值越大表明對領(lǐng)域語料有更好的預(yù)測能力。從表5可以看出，本文提出的組合式領(lǐng)域概念獲取方法（稱為A方法）比基于單一互信息的方法（稱為B方法）的困惑度變化率大。

表5 困惑度變化率結(jié)果

3 總結(jié)

本文提出了一種新的領(lǐng)域概念詞自動獲取方法。算法結(jié)合語義相似度和統(tǒng)計方法，并改進(jìn)傳統(tǒng)近鄰傳播聚類，降低了運行時間。實驗結(jié)果表明該算法在準(zhǔn)確率、困惑度變化率和召回率都得到了明顯的提高。從實驗結(jié)論可以看出，概念的準(zhǔn)確率和召回率受語料規(guī)模影響較大，因此，后續(xù)的工作將是考慮如何減小這種影響。

[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]史東娜.基于半監(jiān)督學(xué)習(xí)的特定領(lǐng)域術(shù)語抽取算法的研究[D].北京：北京郵電大學(xué)，2009.

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

[6]何婷婷，張曉鵬.特定領(lǐng)域本體自動構(gòu)造方法[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]傅繼彬，樊孝忠.基于語言特性的中文領(lǐng)域術(shù)語抽取算法[J].北京理工大學(xué)學(xué)報，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.

陜西省自然科學(xué)基金（No.2012JM8042）；陜西省教育廳科研專項（No.12JK0940）。

董麗麗（1960—），女，教授，碩士生導(dǎo)師，主要研究方向為分布式系統(tǒng)與計算機網(wǎng)絡(luò)應(yīng)用、數(shù)據(jù)挖掘；李歡（1988—），女，碩士研究生，主要研究方向為分布式系統(tǒng)；張翔（1972—），男，副教授，主要研究方向為計算機可視化技術(shù)；劉閆鋒（1979—），男，碩士研究生，主要研究方向為數(shù)據(jù)挖掘技術(shù)。E-mail：343239566@qq.com

2012-05-31

2012-08-27

1002-8331（2014）06-0127-05