基于Markov的概念自動抽取算法

摘要：提出了一種概念自動抽取算法，該算法的目的是從英文文本中抽取出由多個單詞組成的概念。文中首先證明了概念的抽取過程是一個多個狀態的齊次Markov鏈，然后給出了具體的抽取過程，即，如果多步轉移概率達到所給定的閾值，則將這多個狀態，即多個單詞，看作是一個概念。為了對算法進行性能測試，借助網絡爬蟲，從網絡中獲取有關計算機領域的文本文檔，采用本文算法進行概念抽取，結果顯示該算法優于其他算法。

關鍵詞：馬爾克夫；概念；轉移概率；概念抽取；規則

中圖分類號：TP391.1 文獻標識碼：A

1 引言

概念在本體中處于重要位置。隨著社會的發展，新的概念，尤其是多個單詞組成的概念層出不窮，從領域文檔、互聯網中抽取出這些概念來豐富領域知識庫是一項有意義的工作。人工獲取概念是效率低，費時費力，而概念的自動抽取在信息處理等應用中扮演著重要角色。目前主要的抽取方法都是基于統計、規則和二者混合的方法，筆者于本文中提出Markov的概念抽取方法，該方法可以從英文文本中抽取出包含多個英文單詞的概念。

2 相關工作

本節將對目前采用的概念自動抽取算法進行討論，分析其優缺點，在此基礎上闡述本文算法。

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

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

統計和規則二者相結合的方法稱之為混合法，該方法是通過制定規則，實現篩選，然后對篩選的數據進行統計，并從中抽取概念，對概念賦值并統計大小，根據值的大小，證明是否是領域概念。一種與領域無關，并且是半自動的概念抽取方法是Frantzi提出的[6]，在這個方法中對C-value和NC-value分別進行抽取，其中C-value的抽取用到了語言學知識（其中包含詞性標注，語法過濾等），也用到了統計學知識，如表達式（1）：

這時C-value的表達式，其中，是概念頻率，是包含的待抽取的概念集合；是集合中概念個數。因為C-value方法因為語法過濾器的選擇會影響該算法的召回率和準確度。而將表達式（1）納入概念抽取，就會形成C-value的擴展，也就是NC-value，如表達式（2）：

是待抽取概念，是作為的上下位單詞所出現的頻率，是單詞的權值，是集合的單詞，是單詞的直接上下位單詞的集合。

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

3 基于Markov的概念抽取算法

該算法是針對多個單詞組成的概念，如campus violence，French riots，911 terrorist attack等。這就好比是馬爾可夫鏈，多個單詞的概念抽取可看作是多態的，并設定一個多步轉移率的閾值，如果超過該閾值，就把這個多態鏈稱為一個概念，這種方法從模型上看計算簡單，準確率也高，相應的抽取概念的效率自然也會提高。[8]

3.1 概念的Markov性

要把領域文檔看作一個概念集合，而且是自動抽取概念的過程，就必須以信息學的角度進行分析。這里的概念集合設為，其中，是概念集合當中的元素，而是元素的個數，也就是單詞的個數，那么多個單詞的抽取，就是從集合中抽取多個元素的概念。

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

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

3.2 概念的抽取過程

在抽取單詞的過程中，設在時間n時，Markov鏈的狀態是，即，在下一個時間n+1內，抽取單詞，則。此時從抽取單詞到的轉移概念就可以計算出來了，其表達式為，，或者用表示，1表示△T，就是抽取第一個單詞和第二個單詞的時間間隔。只和，和△T有關，可以看出是穩定值，可以證明單詞抽取是齊次Markov鏈。

在上述的過程中可以說Markov鏈是從一個狀態轉化到另外一個狀態，其表達式為（3）所示：

其中，表示從狀態到狀態的一步轉移概率。

概念抽取的步驟總結如下：

這里要有一個前提，就是假設我們已經具有了一個領域文檔，那么具體的抽取過程分為四步：

（1）用空格將文檔中的所有標點符號替換下來。

（2）計算兩次抽取單詞的一步轉移概率，并建立一個對應的矩陣，如轉移矩陣P。

（3）如果轉移概率大于給定閾值，則將看作是一個待定概念。

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

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

4 性能比較

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

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

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

由表1可看出，采用C-value和NC-value算法，由于其采用語法過濾器，結果導致將有些本來是所需概念被濾掉，因此具有較低的召回率。基于頻率和互信息的召回率和準確率相差不大是因為MI均基于頻率。在這些數據中召回率最高的是基于Markov的算法，其根本原因在于：前面四種算法都是基于概念，而Markov是因為轉移概率，也就是說出現頻率低的概念也會被作為待定概念被抽取。另外該算法準確率也較高，這是因為該算法將單詞的排列順序考慮在內。另外，該算法模型簡單，構建效率較高。

5 結束語

因為隨著社會的發展，一些領域，尤其發展速度較快的領域，新的概念層出不窮，這些概念中的多數概念是由多個單詞構成，所以本文提出了一種基于Markov的概念抽取方法。該方法可以從英文文獻中抽取出來含有多個單詞的概念，并且具有領域無關性。整個抽取過程基于多個狀態的Markov鏈，可以通過每個概念中所包含單詞的多步轉移概率來判斷，如果轉移概率達到一個所設定的閾值，則將概念從資料中抽取出來。該方法計算簡單，易于實現，效率高，通過與其它算法比較具有較好的性能。

參考文獻：

[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].計算機工程，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] 張新，黨延忠.基于規則與統計的本體概念自動獲取方法研究[J].情報學報， 2007，26（6）：813-820.

[8] 周子力.基于WordNet的本體構建及其在安全領域應用關鍵技術研究[J].華東師范大學，2009.

作者簡介：

宋元海，男，高校講師，兗州礦區職工大學計算機系任

教，擅長計算機軟件設計.