基于混合HMM的文獻元數據地名抽取方法研究*

杜秋霞 王洪國 邵增珍 付 鑫 劉衍民

(1.山東師范大學信息科學與工程學院 濟南 250014)(2.山東省物流優化與預測工程技術研究中心 濟南 250014) (3.遵義師范學院數學與計算科學學院 遵義 563002)

?

基于混合HMM的文獻元數據地名抽取方法研究*

杜秋霞1,2王洪國1,2邵增珍1,2付 鑫1,2劉衍民3

(1.山東師范大學信息科學與工程學院 濟南 250014)(2.山東省物流優化與預測工程技術研究中心 濟南 250014) (3.遵義師范學院數學與計算科學學院 遵義 563002)

論文從保護地名文化遺產的角度出發,提出了一種基于混合隱馬爾科夫模型的地名抽取方法,從文獻元數據中快速準確的提取地名?？紤]到文本中上下文對狀態的影響,并用傳統Viterbi算法進行正序和逆序解碼,通過兩次解碼使顆粒度較小的地名得到較好的識別和抽取。實驗結果表明這種對于元數據的信息抽取模型能達到較好的效果。

信息抽取; 元數據; 地名抽取; 隱馬爾科夫模型

Class Number TP391.1

1 引言

隨著新型城鎮化、信息化的快速發展,每年都有數以萬記的新地名產生,同時有許多老地名不斷消亡,近30年來,我國就有6萬多個鄉鎮名稱和40多萬個村名稱被廢棄。據專家統計,人們日常使用的信息中約有80%與地理位置和空間分布有關,這些信息主要通過地名來量現。文獻資料作為記錄知識的一切載體,它可以記載歷史地理的演變過程。文獻資料中蘊含著豐富的地理空間信息,從中獲取地理信息,已成為傳統地理信息采集方式的有效補充。與一般電子文本不同,文獻具有格式多樣化、內容動態化等特點,計算機從海量的文本中發現少數的地名會浪費很多時間。故如何從非結構化的文獻資料中將地名快速的自動化識別和提取,來反映自然環境和社會環境的地理空間信息,并確保信息真實可靠,具有重要的現實意義。

文獻資料中蘊含的地理信息的抽取[1],屬于自然語言處理中描述的命名實體識別的范疇。是通過分析地理名詞之間的語義關聯,通過模型建立,發現和填充與地理實體相關的空間位置、屬性信息等。國內外對于地名提取方法的研究主要集中在規范化地名的自動識別[2],已達到較高的識別準確率,但是對那些粒度小的鄉鎮名和村名的識別和抽取研究成果較少。對于文獻元數據[3～5]的研究則主要集中在對元數據的整體的抽取上,而對于元數據內部的信息研究關注較少。文獻[6]利用本體的方法,對于每一個概念或關系的本體通過集合學習的模式從文本中抽取信息;文獻[7]使用線程和同步將多個文件輸入進行批處理,通過對句子進行語義分析,從原始文檔中提取句子的關鍵詞。文獻[8]提出一種改進遺傳退火(Hidden Markov Model,HMM)的Web抽取算法,并利用雙序Viterbi解碼,取得了較好的效果;文獻[9]提出了基于改進二階隱馬爾科夫模型的文本信息抽取模型,并對Viterbi算法進行了改進,取得較好的識別效果;文獻[10]通過分析文獻中上下文和內容在文檔中的關系,對文獻中的關鍵詞進行了抽取以方便文獻的查找和。提出一種改進頭腦風暴優化算法的隱馬爾科夫模型。隱馬爾科夫模型(Hidden Markov Model,HMM)是一種重要的文本信息抽取方法,由于其易于建立、適應性強等特點而備受研究者的關注。傳統HMM模型及其衍生模型,雖然具有很好的抽取效果,但它們的共同點是只考慮某時刻的轉移概率對前一個狀態的依賴性,即前向依賴,較少考慮后向依賴,而現實情況是有些地名抽取時后詞對前詞的影響更大?；诖?本文提出一種基于混合HMM(Hybrid Hidden Markov Model,HHMM)的文本信息抽取方法,同時考慮當前狀態受它前詞和后詞的雙向混合影響,并利用Viterbi算法進行了驗證。實驗結果表明,混合隱馬爾科夫模型可有效提高元數據中地名信息抽取的準確率,表現出了良好的性能。

2 相關模型和算法

2.1 隱馬爾科夫模型

隱馬爾科夫模型(Hidden Markov Model,HMM)(如圖1)是一個二重馬爾科夫隨機過程,它包括具有狀態轉移概率的馬爾科夫鏈和輸出觀測值的隨機過程。其狀態是不確定或不可見的,只有通過觀測序列的隨機過程才能表現出來。一個HMM包含兩層:一個可觀察層和一個隱藏層?？捎^察層是待識別的觀察序列,隱藏層是一個馬爾科夫過程,即一個有限狀態機,其中每個狀態轉移都帶有轉移概率。

圖1 隱馬爾科夫模型

一個HMM可以看成一個五元組λ={S,K,Π,A,B},其中S={S1,S2,…,SN}表示模型中所有的狀態,N代表狀態的數目;K={K1,K2,…,KM}表示狀態觀察值的集合,M代表觀察值的數目;Π={πi=P(q1=Si),1≤i≤N}為初始狀態的集合。πi表示狀態si作為初始狀態的概率;A={aij=P(qt=Sj|qt-1=Si),1≤i,j≤N}為移概率矩陣,aij表示狀態si轉移到狀態sj的概率;B={bi(k)=P(Ot=Kk|qt=Si),1≤i≤N,1≤k≤M}為發射概率矩陣,bi(k)表示在狀態si下,Kk出現的概率。

2.2 混合隱馬爾科夫模型(Hybrid Hidden Markov Model,HHMM)

傳統隱馬爾科夫模型僅考慮前一個詞對后一個詞的影響,而實際上對于文本而言,對于一個詞的影響不只是前一個詞,甚至一個命名實體和一句話中的其他所有詞都有關系。鑒于這種情況,本文所提出的HHMM考慮了后一個狀態對前一個狀態的影響,因此本文的HHMM是由傳統的HMM和逆序的HMM(Reverse Hidden Markov Model,RHMM)共同構成(如圖2)。

圖2 混合隱馬爾科夫模型

2.3 基于RHMM的改進解碼算法(R-Viterbi)

對于一個特殊的HMM和一個相應的觀察序列,在實際應用中經常希望能找到生成此序列最可能的隱藏序列狀態。在命名實體識別中需要解決的問題就是如何為一個句子找到最合適的標記序列,即解碼。常用的解碼方法是Viterbi[11]算法,它屬于動態規劃算法,其思想是把問題分解,先解決最基本的子問題,再逐步外推尋找更好的子問題的最優解,在有限步后達到整個問題的最優解,即得到最優的命名實體標記序列[12～13]。算法的描述如下:

第一步:利用下式計算初始局部最優函數:

φ1(i)=πibi(y1) 1≤i≤N

θ1(i)=0

第二步:確定求解局部最優的遞歸函數的遞歸:

第三步:計算最后一個觀察值的最佳狀態:

第四步:回退以前觀察值得最佳狀態:

對于觀察序列O=(O1,O2,…,OT),用Viterbi算法解碼時,P(qi+1|q1,q2,…,qi)=P(qi+1|qi),即,O2的狀態由O1的狀態決定。針對逆序隱馬爾科夫模型本文對傳統解碼算法(Viterbi算法)做了如下改進:

對于另一類觀察序列O′=(OT,OT-1,…,O1),t+1時刻的狀態qt+1由時刻t的狀態qt所決定,即O1的狀態由O2的狀態決定。由此可以將觀察序列為O′=(OT,OT-1,…,O1)的解碼過程理解為:對觀察序列O=(O1,O2,…,OT)的逆過程,t時刻的狀態qt由t+1時刻的狀態qt+1所決定,即P(qi|qi+1,qi+2,…,qi+n)=P(qi|qi+1),這體現了觀察序列的后向依賴性。

3 基于HHMM的文獻元數據的地名信息抽取

將以上算法用于文獻元數據的地名信息抽取任務。本文所研究文獻的元數據的基本格式為:{(Reference Type)、(Title)、(Author)、(Author Address)、(Journal)、(Year)、(Issue)、(Pages)、(Keywords)、(Abstract)、(ISBN/ISSN)、(Notes)、(Database Provider)}。

該元數據包括13個部分,其中包含地名的在(Title)、(Keywords)、(Abstract)這三部分中。由于(Keywords)部分的地名不包含語法語義,利用NLPIR漢語分詞系統進行分詞和標注后,對這部分的地名我們根據標注結果進行直接抽取。所以本文的研究重點是(Title)和(Abstract)部分。

3.1 數據預處理

本文分詞工具選用的中科院NLPIR漢語分詞系統(ICTCLAS2014),利用該系統對初始文本進行分詞和標注,并對分詞結果根據詞性標注進行篩選,將每篇文本處理后的詞匯集作為下一步處理的數據源。經過海量分詞和后,元數據中(Keywords)部分的地名大部分可以被準確識別,但是由于(Title)和(Abstract)部分具有文本結構的復雜性,標注結果還存在以下一些問題:音譯地名識別效果一般;顆粒度小的地名,如島砣、寧木特鄉等難以被識別。而這些不能準確標注的地名,對研究已經消失的地名和對地名遺產的保護具有非常重要的意義,因此本文對文獻元數據進行了二次標注(人工標注),以保證得到較好的標注文本。

3.2 地名信息抽取

中文地名自動識別是通過對文本進行標記產生地名識別的結果。對于每個詞模型給出判斷其是或不是一個地名的概率。為了給文本信息抽取建立一個HMM,必須首先決定模型應該包含多少個狀態,以及狀態間如何轉移。一個合理的初始模型是每一類使用一個狀態,并且允許任何一個狀態到另外一個狀態的轉移(一個完全連接模型)。文本中的地名不止與其前一個詞有關系,與其后邊的詞也有關系,因此本文分別用文本的正序列和逆序列建立隱馬爾科夫模型。本文的地名抽取過程分為模型訓練和對測試文本的解碼兩部分,具體如圖3所示。

3.2.1 模型建立

為方便計算和去除噪音數據,本文在人工標注時做了以下修改:在做地名識別二次標注時,除了地名(ns)的其他名詞都標為了n,其他動詞(v)、形容詞(a)等其他詞同樣為簡化計算沒再進行細分;除動詞、名詞、形容詞等之外的其他詞(如擬聲詞、標點符號等)都標為o,根據本文混合HMM模型的訓練過程如下:

第一步:初始化HMM,確定模型的狀態數,初始化模型的參數。本文的狀態集為對每個詞的標記為:n(物名)、ns(地名)、t(時間詞)、v(動詞)、a(形容詞)、r(代詞)、m(數詞)、d(副詞)、p(介詞)、u(助詞)、o(其他詞);

第二步:正序掃描文本,依據排版格式、分隔符等信息將標記好的文獻元數據轉換為由分組構成的序列,每一分組都用上一步的標記符號進行狀態標記;

第三步:訓練模型,以分組為單位,應用ML[14]算法計算HMM參數λ=(A,B,π);

圖3 抽取過程

第四步:初始化RHMM,確定模型的狀態數,初始化模型的參數,這里的狀態集和第一步中的相同;

第五步:逆序掃描文本,方法和第二步相同;

第六步:訓練模型,以分組為單位,應用ML算法計算RHMM參數λ=(A′,B′,π)。

3.2.2 解碼過程

為方便計算,本文假設測試文本中的詞只與詞語所在的一句話有關系。首先對測試文本按標點符號“,”、“?！?、“！”、“？”進行切分,這樣測試文本就變為單個句子;然后給這些句子進行分詞后求出其最佳的標注序列;最后把標為ns(即地名)的詞輸出,完成整個抽取過程。算法描述具體如下:

第一步:訓練樣本預處理。掃描文本,利用逗號、句號、問號、感嘆號(括號、引號內的逗號除外)、三個以上的空格等分隔符信息將文本序列切分成文本分塊序列;

第二步:計算正序文本的最大概率路徑。結合訓練部分輸出的HMM模型參數λ=(A,B,π),利用Viterbi算法計算;

第三步:回溯查找最大概率路徑上HMM的狀態標記序列,將標記為ns的詞輸出。

第四步:計算逆序文本的最大概率路徑。結合訓練部分輸出的RHMM模型參數λ=(A′,B′,π),利用R-Viterbi算法計算;

第五步:回溯查找最大概率路徑上RHMM的狀態標記序列,將標記為ns的詞輸出;

第六步:取第三步和第五步輸出結果的并集,輸出最終結果。

3.3 算法復雜性分析

本文的算法復雜性分析分為模型的訓練和解碼兩部分,對于HMM的訓練部分的算法復雜度分析,即模型訓練問題,是指給定觀察序列,產生出這些參數的模型λ=(A,B,π)以滿足某種最優化準則,使觀察序列的概率P(O|λ)最大。直接解決方式具有指數級的計算復雜性(2T*NT,T是觀察序列的長度,N是狀態的個數),這樣復雜性特別大,為了有效地解決該問題通常使用后向算法解決。定義后向概率βt(i)=P(O1O2…Ot,qt=Si|λ),后向算法描述如下:

第一步:初始化:

βT(i)=1 1≤i≤N

第二步:歸納計算:

1≤t≤T-1,1≤i≤N

第三步:求最終和:

由以上步驟可以看出:計算某時刻在某個狀態下的后向變量需要看后一時刻的n個狀態,此時,時間復雜度為O(n),每個時刻又有n個狀態,此時時間復雜度為n×O(n)=O(n2),又有T個時刻,所以時間復雜度為T×O(n2)=O(n2×T),因為本文所考慮的為一階隱馬爾科夫模型,所以算法復雜度為O(n2)。

對于解碼過程中,Viterbi算法的第一步初始概率是在訓練模型中已經訓練出的,是個固定的值,所以第一步的算法復雜度是O(1),以后的每一步計算的復雜度都和相鄰兩個狀態si和si+1各自的節點數ni和ni+1的乘積成正比,即O(ni·ni+1)。在隱馬爾科夫模型中節點最多的狀態有n個節點,也就是說在Viterbi算法整個網格的寬度為n,每一步的復雜度不超過O(n2)。所以整個算法的復雜度為O(n2)。

4 實驗及結果分析

本文實驗是在MyEclipse開發環境下用Java語言進行開發。數據集選擇從CNKI文獻庫中搜集到的鳥類研究文獻包含環境科學與資源利用、生物學、蠶蜂與野生動物保護等學科中的文獻元數據信息共2000條。為更好地評估算法的有效性,從2000條數據中選出1000條作為訓練數據。首先用ICTCLAS開源系統進行初次標注,并把關鍵字部分的地名進行輸出,然后對(Title)和(Keywords}部分的內容進行人工標注,最終的標注結果為如下格式:

“(/o Title/o )/o :/o 煙臺/ns 的/u 十一種/m 山東省/ns 鳥類/n 新/a 記錄/n

(/o Abstract/o )/o :/o 煙臺市/ns 鳥類/n 資源/n 普查/v 從/p 1983年/t 5月/t 開始/v ,/o 至/p 1985年/t 6月/t 結束/v 。/o 通過/p 普查/v 共/d 鑒定/v 鳥類/n 標本/n 3000/m 余號/m ,/o 查出/v 煙臺市/ns 鳥類/n 19目/m 、/o 50/m 科/n 、/o 276種/m (/o 含/v 亞種/n 4種/m )/o 。/o 其中/r 發現/v 山東/ns 鳥類/n 新/a 記錄/n 11種/m ,/o 現/t 分述/v 如下/v :/o 1/m 、/o 中/b 白鷺/n 1984年/t 4月/t 2日/t 在/p 長島縣/ns 大黑山/ns 首次/m 采得/v 一只/m 雌鳥/n 。/o ”

統計這1000條文本數據中詞性之間的轉移概率和詞性對應每個詞的發射概率,即HMM模型中的參數A、B。經統計發現文本中轉移概率,任何詞到其他詞(o)所占的比例都較大,而標記為o的這些詞中大部分為標點等,對地名的抽取影響不大,所以本文對除o外的其他十個狀態轉移概率做了歸一化處理,使每個狀態對應的轉移概率之和為1。

利用Viterbi算法對1000條測試數據進行抽取,測試數據為分詞后的文本,利用空格作為間隔符,測試文本格式如下:

“( Title ) : 東港市 白鷺 繁殖群 生境 調查 及 保護

( Abstract ) : 遼寧省 東港市 以 白鷺 為主 的 鷺類 繁殖群 的 數量 、 種類 在 人工 濕地 中 群 居 之 多 在 省內 實屬 罕見 。 對 該 區域 內 白鷺 等 鷺類 的 生境 條件 調查 發現 , 豐富 的 植被 、 水域 、 食物 條件 為 白鷺 提供 了 留存 條件 。 由于 沒有 健全 的 保護 措施 , 保護 力度 不夠 , 造成 因 受 環境 、 人為 等 干擾 使 白鷺 生存 環境 受到 破壞 , 導致 數量 減少 , 因此 建立 東港市 白鷺 自然保護區 是 必要 的 , 經 論證 也 是 可行 的 ?！?/p>

目的為從以上文本中抽取地名,由于對文本元數據進行地名信息抽取算法目前還沒有準確的客觀評價指標,為評價本文算法的有效性,本文通過人工標注從1000篇文獻中共標出地名5775個,然后再用本文的方法進行抽取。抽取結果如表1,這里用三個常用評價標準:召回率(R)、準確率(P)和F1值(召回率和準確率的調和平均數)來進行評價算法的性能,c代表地名總數,m代表抽取到的地名總數,n代表抽取正確的地名,t代表抽取錯誤的地名。則有下式:

表1 抽取結果

由上表可以計算出利用傳統HMM方法的召回率為77.6%,準確率為88.2%,F1值為82.6%。利用HHMM方法的召回率為85.9%,準確率為89.1%,F1值為87.5%。用圖表示如圖4所示。

圖4 基于HMM和HHMM的對比圖

從上圖可以看出,用基于HHMM的方法在召回率和F1值上比傳統HMM有顯著增高,準確率升高幅度不大,但也有所提高。所以整體來看,本文的方法是有效的。但是從表1來看,HHMM中抽取錯誤的地名也有所增加,這是因為HHMM是取傳統HMM和RHMM的并集,所以抽取完成后錯誤的地名會有所增加,同時也說明本文的方法在對抽取正確的地名有較高的有效性和實用性。

5 結語

本文從保護地名文化遺產的角度出發,考慮到文獻所獨具的特點,從文獻元數據中快速的將文獻中所蘊含的地名信息抽取出來。在模型建立上,考慮到文本中地名前詞和后詞對地名的影響,提出了一種基于混合隱馬爾科夫模型的地名抽取方法;在解碼方法上,采用傳統Viterbi算法進行正序和逆序解碼,從文獻元數據中抽取地名;在抽取效果上,通過兩次標注訓練混合隱馬爾科夫模型,使那些顆粒度較小的鎮名和村名得到較好的抽取效果。但是從保護地名遺產的角度來看,本文僅是對元數據中的地名進行了較為細致的抽取,但對于哪些是已經消失或新增的地名哪些是現有的地名沒有準確分類;另外,每個地名都有它的時間特征,這樣便于發現消失和新增地名的變化過程。所以下一步的工作中,將加入地名數據庫,利用地名數據庫來發現消失和新增的地名,并對地名加入時間特征進行抽取。

[1] Piskorski J, Yangarber R. Information extraction: Past, present and future[C]//Multi-source, Multilingual Information Extraction and Summarization. Berlin Heidelberg: Springer-Verlag,2013:23-49.

[2] 張曉艷,王挺,陳火旺.命名實體識別研究[J].計算機科學,2005,4:44-48. ZHANG Xiaoyan, WANG Ting, CHEN Huowang. Named entity recognition[J]. Computer Science,2005,4:44-48.

[3] Chen F, Chiu P, Lim S. Topic Modeling of Document Metadata for Visualizing Collaborations over Time[C]//Proceedings of the 21st International Conference on Intelligent User Interfaces. ACM,2016:108-117.

[4] Frank J R, Kornai A. Methods of systems using geographic meta-metadata in information retrieval and document displays: U.S. Patent 9,286,404[P]. 2016-3-15.

[5] Hoenich D A, Hunt D W, Logan W K, et al. Document Processing System And Method For Associating Metadata With A Physical Document While Maintaining The Integrity Of Its Content: U.S. Patent 20,160,063,365[P]. 2016-3-3.

[6] Gutierrez F. A Hybrid Approach for Ontology-based Information Extraction[J]. 2016.

[7] Motwani D, Saxena A S. Multiple Document Summarization Using Text-Based Keyword Extraction[C]//Proceedings of Fifth International Conference on Soft Computing for Problem Solving. Springer Singapore,2016:187-197.

[8] 李榮,馮麗萍,王鴻斌.基于改進遺傳退火HMM的Web信息抽取研究[J].計算機應用與軟件,2014,4:40-44. LI Rong, FENG Liping, WANG Hongbin. Extraction based on improved genetic annealing HMM Web Information[J]. Computer Applications and Software,2014,4:40-44.

[9] Ling L J T J X. Research on Information Extraction Based on Second-Order HMM[J]. 2011.

[10] Kavila S D, Rani D F. Information Extraction from Research Papers Based on Statistical Methods[C]//Proceedings of the Second International Conference on Computer and Communication Technologies. Springer India,2016:573-580.

[11] Viterbi A. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm[J]. IEEE Transactions on Information Theory,1967,13.

[12] 劉芳,趙鐵軍,于浩,等.基于統計的漢語組塊分析[J].中文信息學報,2000,6:28-32,39. LIU Fang, ZHAO Tiejun, YU Hao, et al. Based on statistical analysis of Chinese Chunk[J]. Chinese Information Technology,2000,6:28-32,39.

[13] 白栓虎.基于統計的漢語語料庫詞性自動標注方法的研究與實現[D].北京:清華大學,1992. BAI Shuanhu. Research and implementation of automatic annotation method based on statistics of Chinese speech corpus[D]. Beijing: Tsinghua University,1992.

[14] Seymore K, McCallum A, Rosenfeld R. Learning hidden Markov model structure for information extraction[C]//AAAI-99 Workshop on Machine Learning for Information Extraction,1999:37-42.

Place Name Extraction Method of Literature Metadata Based on the Hybrid HMM

DU Qiuxia1,2WANG Hongguo1,2SHAO Zengzhen1,2FU Xin1,2LIU Yanmin3

(1. School of Information Science and Engineering, Shandong Normal University, Jinan 250014) (2. Shandong Provincial Logistics Optimization and Predictive Engineering Technology Research Center, Jinan 250014) (3. School of Mathematics and Computational Science, Zunyi Normal College, Zunyi 563002)

From the perspective of the protection of the cultural heritage of place names, this paper proposes a method of place name extraction based on the hybrid Hidden Markov Model,fast and accurate place names extraction from literature metadata. Considering the influence of the context on the state in the text, the traditional and reverse Viterbi algorithms are used to decode, and the place names with small particle size can be well recognized and extracted by decoding twice. Experimental results show that the information extraction model of metadata can achieve good results.

information extraction, metadata, place name extraction, HMM

2016年7月11日,

2016年8月29日

國家自然科學基金(編號:71461027);山東省科技發展計劃項目(編號:2014GGH201022);山東省經信委軟科學計劃項目(編號:2015EI010);遵義市創新人才團隊(編號:遵市科合(2015)38號);貴州省優秀青年科技人才培養對象專項資金(編號:黔科合人字[2015]06)資助。

杜秋霞,女,碩士研究生,研究方向:信息抽取。王洪國,男,教授,博士生導師,研究方向:電子政務,物流優化等。邵增珍,男,博士后,副教授,碩士生導師,研究方向:智能計算,智能物流,大數據分析等。付鑫,男,碩士研究生,研究方向:信息抽取。劉衍民,男,博士后,教授,研究方向:優化理論及智能算法。

TP391.1

10.3969/j.issn.1672-9722.2017.01.022