摘要：提出了一種概念自動(dòng)抽取算法，該算法的目的是從英文文本中抽取出由多個(gè)單詞組成的概念。文中首先證明了概念的抽取過程是一個(gè)多個(gè)狀態(tài)的齊次Markov鏈，然后給出了具體的抽取過程，即，如果多步轉(zhuǎn)移概率達(dá)到所給定的閾值，則將這多個(gè)狀態(tài)，即多個(gè)單詞，看作是一個(gè)概念。為了對(duì)算法進(jìn)行性能測(cè)試，借助網(wǎng)絡(luò)爬蟲，從網(wǎng)絡(luò)中獲取有關(guān)計(jì)算機(jī)領(lǐng)域的文本文檔，采用本文算法進(jìn)行概念抽取，結(jié)果顯示該算法優(yōu)于其他算法。

關(guān)鍵詞：馬爾克夫；概念；轉(zhuǎn)移概率；概念抽?。灰?guī)則

中圖分類號(hào)：TP391.1 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言

概念在本體中處于重要位置。隨著社會(huì)的發(fā)展，新的概念，尤其是多個(gè)單詞組成的概念層出不窮，從領(lǐng)域文檔、互聯(lián)網(wǎng)中抽取出這些概念來豐富領(lǐng)域知識(shí)庫(kù)是一項(xiàng)有意義的工作。人工獲取概念是效率低，費(fèi)時(shí)費(fèi)力，而概念的自動(dòng)抽取在信息處理等應(yīng)用中扮演著重要角色。目前主要的抽取方法都是基于統(tǒng)計(jì)、規(guī)則和二者混合的方法，筆者于本文中提出Markov的概念抽取方法，該方法可以從英文文本中抽取出包含多個(gè)英文單詞的概念。

2 相關(guān)工作

本節(jié)將對(duì)目前采用的概念自動(dòng)抽取算法進(jìn)行討論，分析其優(yōu)缺點(diǎn)，在此基礎(chǔ)上闡述本文算法。

基于規(guī)則的方法是建立一系列的模板，和模板相匹配的概念即為領(lǐng)域概念，如N（其中A為形容詞，N為名詞，P表示介詞）[1]，符合這個(gè)形式則作為一個(gè)概念。還有一種改進(jìn)的空間概念抽取算法，算法中通過一定的規(guī)則去獲取兩個(gè)義素之間的語(yǔ)義關(guān)系，通過兩義素的相似度值來獲取空間概念間的相似度，從而抽取出空間概念[2]。從金融領(lǐng)域資源中抽取出相關(guān)概念的方法，其中也用到規(guī)則模板的制定[3]?？傊?，該類方法中均根據(jù)一定的規(guī)則制定相應(yīng)的模板，但是模板是人工建立，畢竟人們的知識(shí)有限，不可能制定出面向全部語(yǔ)法規(guī)則的模板，有必要建立一種適用某個(gè)領(lǐng)域概念抽取的完善的模板，但是這是一項(xiàng)非常困難的工作。

基于統(tǒng)計(jì)的方法有基于頻率，基于統(tǒng)計(jì)，基于互信息（Mutual Information MI）或信息熵等技術(shù)，Damerau提出的是一種基于互信息的方法，要抽取的概念中包含了兩個(gè)單詞和，Damerau認(rèn)為如果兩個(gè)單詞和的MI值大于某給定閾值，則該兩單詞可以被看作為一個(gè)概念。但是MI方法會(huì)把與看作是一個(gè)概念，這將影響到概念抽取的準(zhǔn)確率。一種基于最大熵模型的本體概念獲取方法，通過對(duì)領(lǐng)域文本進(jìn)行挖掘得到名詞性短語(yǔ)，再使用改進(jìn)的TF-IDF公式從中抽取具有領(lǐng)域性的短語(yǔ)[4]。Dinh等人[5]在抽取生物醫(yī)學(xué)概念時(shí)采用了純統(tǒng)計(jì)向量空間模型，借助詞袋概念以及單詞在文本中的位置特征抽取相關(guān)概念。

統(tǒng)計(jì)和規(guī)則二者相結(jié)合的方法稱之為混合法，該方法是通過制定規(guī)則，實(shí)現(xiàn)篩選，然后對(duì)篩選的數(shù)據(jù)進(jìn)行統(tǒng)計(jì)，并從中抽取概念，對(duì)概念賦值并統(tǒng)計(jì)大小，根據(jù)值的大小，證明是否是領(lǐng)域概念。一種與領(lǐng)域無關(guān)，并且是半自動(dòng)的概念抽取方法是Frantzi提出的[6]，在這個(gè)方法中對(duì)C-value和NC-value分別進(jìn)行抽取，其中C-value的抽取用到了語(yǔ)言學(xué)知識(shí)（其中包含詞性標(biāo)注，語(yǔ)法過濾等），也用到了統(tǒng)計(jì)學(xué)知識(shí)，如表達(dá)式（1）：

這時(shí)C-value的表達(dá)式，其中，是概念頻率，是包含的待抽取的概念集合；是集合中概念個(gè)數(shù)。因?yàn)镃-value方法因?yàn)檎Z(yǔ)法過濾器的選擇會(huì)影響該算法的召回率和準(zhǔn)確度。而將表達(dá)式（1）納入概念抽取，就會(huì)形成C-value的擴(kuò)展，也就是NC-value，如表達(dá)式（2）：

是待抽取概念，是作為的上下位單詞所出現(xiàn)的頻率，是單詞的權(quán)值，是集合的單詞，是單詞的直接上下位單詞的集合。

張新等人提出了一種基于規(guī)則與統(tǒng)計(jì)的本體概念自動(dòng)共聚方法，從領(lǐng)域文本中通過語(yǔ)義串切分、規(guī)則匹配、領(lǐng)域歸屬度分析和概念約簡(jiǎn)算法自動(dòng)獲取領(lǐng)域概念[7]。但是其中的詞性組合規(guī)則不易把握，如何將規(guī)則定義的完善是該方法需要解決的問題。

3 基于Markov的概念抽取算法

該算法是針對(duì)多個(gè)單詞組成的概念，如campus violence，F(xiàn)rench riots，911 terrorist attack等。這就好比是馬爾可夫鏈，多個(gè)單詞的概念抽取可看作是多態(tài)的，并設(shè)定一個(gè)多步轉(zhuǎn)移率的閾值，如果超過該閾值，就把這個(gè)多態(tài)鏈稱為一個(gè)概念，這種方法從模型上看計(jì)算簡(jiǎn)單，準(zhǔn)確率也高，相應(yīng)的抽取概念的效率自然也會(huì)提高。[8]

3.1 概念的Markov性

要把領(lǐng)域文檔看作一個(gè)概念集合，而且是自動(dòng)抽取概念的過程，就必須以信息學(xué)的角度進(jìn)行分析。這里的概念集合設(shè)為，其中，是概念集合當(dāng)中的元素，而是元素的個(gè)數(shù)，也就是單詞的個(gè)數(shù)，那么多個(gè)單詞的抽取，就是從集合中抽取多個(gè)元素的概念。

下面證明概念抽取過程的Markov性。

證明：假設(shè)多；領(lǐng)域文檔中的一個(gè)變量，這個(gè)變量代表一個(gè)單詞，則就有多種狀態(tài)，可以把它看作是一個(gè)隨機(jī)，此時(shí)，可以把集合C看作是一個(gè)多態(tài)集合。當(dāng)在已知的情況下，的分布概率只與有關(guān)，而和無關(guān)。其中是與相鄰的單詞。由此可以證明是符合抽取概念多態(tài)鏈，即Markov鏈。

3.2 概念的抽取過程

在抽取單詞的過程中，設(shè)在時(shí)間n時(shí)，Markov鏈的狀態(tài)是，即，在下一個(gè)時(shí)間n+1內(nèi)，抽取單詞，則。此時(shí)從抽取單詞到的轉(zhuǎn)移概念就可以計(jì)算出來了，其表達(dá)式為，，或者用表示，1表示△T，就是抽取第一個(gè)單詞和第二個(gè)單詞的時(shí)間間隔。只和，和△T有關(guān)，可以看出是穩(wěn)定值，可以證明單詞抽取是齊次Markov鏈。

在上述的過程中可以說Markov鏈?zhǔn)菑囊粋€(gè)狀態(tài)轉(zhuǎn)化到另外一個(gè)狀態(tài)，其表達(dá)式為（3）所示：

其中，表示從狀態(tài)到狀態(tài)的一步轉(zhuǎn)移概率。

概念抽取的步驟總結(jié)如下：

這里要有一個(gè)前提，就是假設(shè)我們已經(jīng)具有了一個(gè)領(lǐng)域文檔，那么具體的抽取過程分為四步：

（1）用空格將文檔中的所有標(biāo)點(diǎn)符號(hào)替換下來。

（2）計(jì)算兩次抽取單詞的一步轉(zhuǎn)移概率，并建立一個(gè)對(duì)應(yīng)的矩陣，如轉(zhuǎn)移矩陣P。

（3）如果轉(zhuǎn)移概率大于給定閾值，則將看作是一個(gè)待定概念。

（4）檢索待定概念的集合，將形如“we， are”等通用概念從C中清除。

這四個(gè)步驟是抽取兩個(gè)單詞的過程，如果想抽取大于兩個(gè)單詞所形成的概念的話，就需要把第三步中的概率重新計(jì)算，并與閾值進(jìn)行比較，如果大于閾值，就可以進(jìn)行第四步。

4 性能比較

本節(jié)將基于Markov的概念抽取算法與基于頻率，互信息，C-value及NC-value四種算法進(jìn)行比較分析。利用五種算法在相同的文檔中對(duì)單詞進(jìn)行抽取形成概念，然后對(duì)每種算法的召回率和準(zhǔn)確率進(jìn)行比較。

具體方法是：取得637個(gè)文檔，這些文檔從http：//en.wikipedia.org/wiki/computer_science上獲取，然后創(chuàng)建一個(gè)小型的文檔，該文檔具有421532個(gè)單詞。從這個(gè)文檔中利用五種算法進(jìn)行單詞的抽取。

在第一種算法中采用基于頻率的算法，閾值為1302，其結(jié)果如表1中所示，第二種算法是互信息的算法，閾值采用9.227，其結(jié)果如表1第三行所示，第三種算法是C-value算法，結(jié)果如表1第四行所示，采用的過濾器是Noun+Noun，第四種與第三種相同，見表第五行。第五種算法就是Markov算法了，其閾值為0.436，結(jié)果見表1第六行。

由表1可看出，采用C-value和NC-value算法，由于其采用語(yǔ)法過濾器，結(jié)果導(dǎo)致將有些本來是所需概念被濾掉，因此具有較低的召回率。基于頻率和互信息的召回率和準(zhǔn)確率相差不大是因?yàn)镸I均基于頻率。在這些數(shù)據(jù)中召回率最高的是基于Markov的算法，其根本原因在于：前面四種算法都是基于概念，而Markov是因?yàn)檗D(zhuǎn)移概率，也就是說出現(xiàn)頻率低的概念也會(huì)被作為待定概念被抽取。另外該算法準(zhǔn)確率也較高，這是因?yàn)樵撍惴▽卧~的排列順序考慮在內(nèi)。另外，該算法模型簡(jiǎn)單，構(gòu)建效率較高。

5 結(jié)束語(yǔ)

因?yàn)殡S著社會(huì)的發(fā)展，一些領(lǐng)域，尤其發(fā)展速度較快的領(lǐng)域，新的概念層出不窮，這些概念中的多數(shù)概念是由多個(gè)單詞構(gòu)成，所以本文提出了一種基于Markov的概念抽取方法。該方法可以從英文文獻(xiàn)中抽取出來含有多個(gè)單詞的概念，并且具有領(lǐng)域無關(guān)性。整個(gè)抽取過程基于多個(gè)狀態(tài)的Markov鏈，可以通過每個(gè)概念中所包含單詞的多步轉(zhuǎn)移概率來判斷，如果轉(zhuǎn)移概率達(dá)到一個(gè)所設(shè)定的閾值，則將概念從資料中抽取出來。該方法計(jì)算簡(jiǎn)單，易于實(shí)現(xiàn)，效率高，通過與其它算法比較具有較好的性能。

參考文獻(xiàn)：

[1] John S. Justeson and Slava M. Katz. Techincal terminology： some linguistic properties and an algorithm for identification in text[J]. Natural Language Engineering，1995，1（1）：9-27.

[2] Qing Yang， Kai-min Cai， Yan Li， Rui-qing Liu An Area Concept Extraction Algorithm Based on Association Rule[C].Proceedings of the 2010 International Conference of Information Science and Management Engineering ISME '10，2010，3：562-564.

[3] Mihaela Vela，Thierry Declerck Concept and relation extraction in the finance domain[C].Proceedings of the Eighth International Conference on Computational Semantics， Tilburg （Netherlands），2009：346-350.

[4] 韋小麗，等.基于最大熵模型的本體概念獲取方法[J].計(jì)算機(jī)工程，2009（24）：114-116.

[5] Dinh，D.and Tamine，L.Biomedical concept extraction based

on combining the content-based and word order similarities[J]. In SAC，2011：1159-1163.

[6] K.Frantzi，S.Ananiadou，and H.Mima.Automatic Recognition of Multi-Word Terms： the C-value/NC-value Method[J].International Journal of Digital Libraries，2000，3（2）：117-132.

[7] 張新，黨延忠.基于規(guī)則與統(tǒng)計(jì)的本體概念自動(dòng)獲取方法研究[J].情報(bào)學(xué)報(bào)， 2007，26（6）：813-820.

[8] 周子力.基于WordNet的本體構(gòu)建及其在安全領(lǐng)域應(yīng)用關(guān)鍵技術(shù)研究[J].華東師范大學(xué)，2009.

作者簡(jiǎn)介：

宋元海，男，高校講師，兗州礦區(qū)職工大學(xué)計(jì)算機(jī)系任

教，擅長(zhǎng)計(jì)算機(jī)軟件設(shè)計(jì).