段艷會(huì)，李曉林*，黃爽

1.智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室（武漢工程大學(xué)），湖北 武漢 430205；2.武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，湖北 武漢 430205

基于條件隨機(jī)場(chǎng)的中文地址行政區(qū)劃提取方法

段艷會(huì)1，2，李曉林1，2*，黃爽1，2

1.智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室（武漢工程大學(xué)），湖北 武漢 430205；2.武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，湖北 武漢 430205

為了在非規(guī)范中文地址中有效的提取行政區(qū)劃信息，提出了一種基于條件隨機(jī)場(chǎng)的方法.該方法根據(jù)中文地址中行政區(qū)劃的表達(dá)特點(diǎn)和特征，采用判別式概率模型，在觀(guān)測(cè)序列已知的基礎(chǔ)上對(duì)目標(biāo)序列建模，通過(guò)構(gòu)建語(yǔ)料訓(xùn)練集和建立相應(yīng)的特征模板，得到行政區(qū)劃的表達(dá)模型，然后使用該模型對(duì)測(cè)試集進(jìn)行測(cè)試，并與標(biāo)注好的測(cè)試數(shù)據(jù)進(jìn)行比對(duì)，驗(yàn)證模型的性能.實(shí)驗(yàn)表明，與最大熵模型相比，條件隨機(jī)場(chǎng)模型總的性能指標(biāo)在其之上，地址信息解析的準(zhǔn)確率能達(dá)到89．93%.

位置信息解析；條件隨機(jī)場(chǎng)；訓(xùn)練語(yǔ)料

0 引言

一直以來(lái)，語(yǔ)言是人們交流與傳播知識(shí)最重要的工具，而理解語(yǔ)言中包含的信息對(duì)人類(lèi)的交流也起到了重要作用.隨著信息技術(shù)的發(fā)展，能使人與計(jì)算機(jī)更好的實(shí)現(xiàn)人機(jī)交互，是人們長(zhǎng)期以來(lái)追求的目標(biāo).本文研究對(duì)地址信息的解析，在過(guò)去很多學(xué)者也提出過(guò)許多方法去提高地址信息解析［1］的正確度.于20世紀(jì)70年代，Lawrence提出的作為一種統(tǒng)計(jì)分析的隱馬爾科夫模型［2］，存在著一種假設(shè)，即假設(shè)每個(gè)元素之間都是彼此獨(dú)立的，不管何時(shí)觀(guān)察結(jié)果僅僅依賴(lài)于此時(shí)此刻所處的狀態(tài).而這個(gè)模型假設(shè)的前提只適合較小規(guī)模的數(shù)據(jù)集［3］，在現(xiàn)實(shí)生活中，很多真實(shí)語(yǔ)料的觀(guān)察序列大部分的表現(xiàn)形式是以多重交互特征表現(xiàn)，觀(guān)察元素間通常有較長(zhǎng)的相關(guān)性，即不止與前一個(gè)狀態(tài)相關(guān)，可能與多個(gè)狀態(tài)以前的狀態(tài)有關(guān).在位置信息解析任務(wù)中，因?yàn)榈刂沸畔⒆陨斫Y(jié)構(gòu)具有一定的復(fù)雜性，單一的特征函數(shù)難以涵蓋它的所有特征，這種情況下，隱馬爾科夫模型所提出的假設(shè)就使得它使用復(fù)雜特征時(shí)無(wú)能為力，此時(shí)它在信息解析中的弊端就顯現(xiàn)出來(lái)了.而后由Jaynes提出的最大熵模型［4－5］，它記錄特征是否出現(xiàn)，并不能了解所需特征的強(qiáng)度，因此在信息的分類(lèi)中并不是最優(yōu)的.其次，采用最大似然方法訓(xùn)練出的最大熵模型，其算法存在較慢的收斂速度，所以就致使最大熵模型的計(jì)算量大，而且，有很?chē)?yán)重的數(shù)據(jù)稀疏問(wèn)題，再次由于最大熵對(duì)每個(gè)詞單獨(dú)進(jìn)行分類(lèi)，難以很充足的利用標(biāo)記之間的關(guān)系.由Pearl提出的貝葉斯模型［6］可以任意使用復(fù)雜的相關(guān)特征，并且能靈便地對(duì)約束條件進(jìn)行設(shè)置，模型在未知參數(shù)的適應(yīng)度、已知數(shù)據(jù)的擬合度方面就是通過(guò)約束條件進(jìn)行調(diào)節(jié)的，并且能自然地解決模型中參數(shù)平滑問(wèn)題，但其在決策時(shí)很容易延誤決策的最佳時(shí)間導(dǎo)致影響效果.本文提出的條件隨機(jī)場(chǎng)模型［7］，克服了其它幾種模型在信息解析上的缺陷，采用鏈結(jié)式結(jié)構(gòu)，結(jié)合了最大熵模型和馬爾科夫模型的特點(diǎn)，使用概率圖模型，在長(zhǎng)距離依賴(lài)和交疊性特征方面能力較強(qiáng)，能很好的處理最大熵馬爾科夫模型［8］具有的標(biāo)注偏置等問(wèn)題，而且與最大熵不同的是它能對(duì)所有的特征進(jìn)行全局歸一化［9－11］，從而求得全局最優(yōu)解.

1 模型描述

1.1 位置信息解析實(shí)現(xiàn)步驟

位置信息解析具體步驟如圖1所示.

（1）收集數(shù)據(jù)：利用網(wǎng)絡(luò)爬蟲(chóng)等數(shù)據(jù)挖掘方式，從互聯(lián)網(wǎng)上提取大量地理位置信息，例如：…｜省…｜市…｜（區(qū)）縣…｜鎮(zhèn)…｜路…類(lèi)的地址，之后進(jìn)行整理，保留至少有一個(gè)行政區(qū)劃名的地址作為研究所需要使用的數(shù)據(jù).

圖1 信息解析流程圖Fig.1 Flowchart of information analysis

（2）分析數(shù)據(jù)：將數(shù)據(jù)集里的一部分?jǐn)?shù)據(jù)分離出作為訓(xùn)練語(yǔ)料，參考條件隨機(jī)場(chǎng)特殊文本格式進(jìn)行人工標(biāo)注以便生成模型，剩下的一部分作測(cè)試語(yǔ)料，并人工對(duì)其進(jìn)行標(biāo)注，以便測(cè)試模型性能.

（3）構(gòu)建模型：通過(guò)對(duì)地址信息的特殊結(jié)構(gòu)進(jìn)行研究制定特征模板，并與測(cè)試語(yǔ)料一起生成條件隨機(jī)場(chǎng)模型.

（4）輸出結(jié)果：用測(cè)試語(yǔ)料檢測(cè)條件隨機(jī)場(chǎng)模型，輸出output文件，并將文本格式規(guī)范為crf＋＋特殊文本定義的格式，從而為數(shù)據(jù)比對(duì)提供方便.

（5）測(cè)試數(shù)據(jù)：查看測(cè)試結(jié)果，對(duì)模型性能進(jìn)行測(cè)評(píng).

1.2 條件隨機(jī)場(chǎng)描述

由于最大熵模型會(huì)產(chǎn)生標(biāo)記偏置問(wèn)題，無(wú)法好好的對(duì)信息進(jìn)行序列標(biāo)注，針對(duì)這個(gè)問(wèn)題，后期提出最大熵馬爾科夫模型，是在相鄰的變量值之間使用最大熵模型，但這樣做會(huì)使得得到的結(jié)果僅僅是局部的最優(yōu)解，對(duì)整體來(lái)說(shuō)未必是最優(yōu)的，針對(duì)這個(gè)問(wèn)題，提出的條件隨機(jī)場(chǎng)方法，引出歸一化因子，對(duì)全局進(jìn)行歸一化，解決了最大熵隱馬爾科夫模型存在的不足之處.

條件隨機(jī)場(chǎng)也是一種判別式模型，所謂判別式模型，學(xué)習(xí)的是一種條件概率p（y｜x），利用正負(fù)例和分類(lèi)標(biāo)簽，關(guān)注在判別模型的邊緣分布.

條件隨機(jī)場(chǎng)是一種無(wú)向圖性模型，變量X，Y分別代表的是觀(guān)察序列、對(duì)應(yīng)聯(lián)合分布的隨機(jī)變量，則以X為條件的無(wú)向圖模型G（V，E）就是條件隨機(jī)場(chǎng).其中V表示無(wú)向圖G中節(jié)點(diǎn)的集合，E代表節(jié)點(diǎn)V之間的無(wú)向邊集合.

設(shè)G＝（V，E）是一個(gè)無(wú)向圖，Y＝｛Yv｜v∈V｝是以無(wú)向圖中每個(gè)隨機(jī)變量Yv為節(jié)點(diǎn)構(gòu)成的集合，在給定觀(guān)察序列的條件下，若是隨機(jī)變量Yv都遵循馬爾科夫?qū)傩?，即如公式?）所示［6］.

那么（X，Y）就構(gòu)成一個(gè)條件隨機(jī)場(chǎng)，其中u～v表示u和v是相鄰的邊.

根據(jù)Hammersley-Clifford定理得到條件隨機(jī)場(chǎng)分布用公式（2）表示如下［7］.

這里的c為G中所有的最大勢(shì)團(tuán)的集合，ΨVc（vc）為勢(shì)函數(shù)（下一節(jié)介紹），通常為了方便計(jì)算，ΨVc（vc）的形式表示在Z的歸一化因子中，用式（3）表示.

條件隨機(jī)場(chǎng)最常用的模型為線(xiàn)性鏈結(jié)構(gòu)，如圖2所示.

圖2 線(xiàn)性結(jié)構(gòu)條件隨機(jī)場(chǎng)Fig.2 Condition random field of linear structural condition

另外觀(guān)察序列之間并不一定存在某種聯(lián)系，它只是一個(gè)條件，不存在其它任何假設(shè)，所以還可以用圖3表示該模型.

圖3 模型的另一種表示方法Fig.3 Another expression of the model

該表示方法與線(xiàn)性條件隨機(jī)場(chǎng)模型的表示方法無(wú)異.

1.3 勢(shì)函數(shù)

勢(shì)函數(shù)在條件隨機(jī)場(chǎng)中是針對(duì)每個(gè)最大勢(shì)團(tuán)做出的定義，如圖4所示，每個(gè)勢(shì)函數(shù)定義如公式（4）［6］.

圖4 勢(shì)函數(shù)團(tuán)示意圖Fig.4 Schematic diagram of potential function

在圖4中，G中的所有最大勢(shì)團(tuán)已標(biāo)出，且Ψc(yc)是一個(gè)在圖G中最大勢(shì)團(tuán)上嚴(yán)格的勢(shì)函數(shù)，因此，在觀(guān)察序列X的條件下，標(biāo)記序列Y的形式如公式（5）所示［8］.

在線(xiàn)性條件隨機(jī)場(chǎng)中，G中最大勢(shì)團(tuán)即是相鄰的兩個(gè)隨機(jī)變量組成的，則公式（4）可以擴(kuò)寫(xiě)成如下.

其中fk（yi=1，yi，x）是表示相鄰的觀(guān)察序列的標(biāo)記位置之間的特征轉(zhuǎn)移函數(shù)，而gk（yi，x）表示當(dāng)前觀(guān)察位置的狀態(tài)特征函數(shù).

1.4 特征模板

如果僅僅依靠地理信息本身結(jié)構(gòu)和對(duì)字符串的分析，很難取得好的效果.因此，地理信息中，上下文環(huán)境與特征詞對(duì)提高地理信息的識(shí)別效果有比較明顯的作用.而條件隨機(jī)場(chǎng)有個(gè)非常明顯的優(yōu)點(diǎn)，即它可以很輕松的將觀(guān)察序列里面的特征加入到模型中，表達(dá)長(zhǎng)距離上下文的依賴(lài)關(guān)系.

上下文環(huán)境，是指包括當(dāng)前詞v0在內(nèi)，以及其前后幾個(gè)詞組成的一個(gè)“觀(guān)察窗口”（v－n，v－（n－1），…v0，…，vn－1，vn）.從理論上看，窗口越大，前后詞關(guān)聯(lián)越多，可依賴(lài)的信息就越多，但窗口過(guò)大又會(huì)導(dǎo)致效率降低，窗口過(guò)小又會(huì)導(dǎo)致不能充分利用特征，從而丟失掉一些重要信息.所以，根據(jù)大量數(shù)據(jù)分析，一般選取的窗口大小為2，即（v－2，v－1，v0，v1，v2）.

在選取使用地址位置的特征時(shí)，考慮到地址都有很明顯的行政區(qū)劃特征詞例如省、市、區(qū)、縣等，所以可以將該特征應(yīng)用到特征模板中，如表1所示.

表1 特征模板的選取Table 1 Selection of feature template

以上的各個(gè)特征模板要有四個(gè)位置偏移，即－2、－1、1、2.而當(dāng)特征函數(shù)取得特定值，特征模板就會(huì)變成一個(gè)實(shí)例，便會(huì)有具體特征出現(xiàn).比如當(dāng)前詞后面第二個(gè)詞v2出現(xiàn)在地址特征詞表，可表示為：

2 性能評(píng)估

對(duì)于一般的分詞算法研究，大多數(shù)都是以B、I、E、O做標(biāo)注，即以一個(gè)詞的開(kāi)始、中間、結(jié)束來(lái)標(biāo)記，沒(méi)有很明顯的在標(biāo)注中加入詞性特征，這使在建立模型時(shí)，不能很好的利用所研究領(lǐng)域的一些特殊結(jié)構(gòu)與特征來(lái)進(jìn)行更加精準(zhǔn)的信息區(qū)分，利用條件隨機(jī)場(chǎng)進(jìn)行信息的解析，在標(biāo)注語(yǔ)料時(shí)，同時(shí)結(jié)合地理領(lǐng)域的詞結(jié)構(gòu)進(jìn)行標(biāo)注，如表2所示.

表2 訓(xùn)練語(yǔ)料標(biāo)注示例Table 2 Training corpus tagging examples

選取省、市、縣、區(qū)等行政區(qū)劃關(guān)鍵詞作為特征詞，給每個(gè)特征詞一個(gè)特殊的標(biāo)記，并結(jié)合B、M、E作為標(biāo)注語(yǔ)料的標(biāo)記，實(shí)驗(yàn)表明，加入特征詞標(biāo)記語(yǔ)料之后，利用語(yǔ)義解析去標(biāo)注，比純粹的開(kāi)始、結(jié)束標(biāo)記的正確率增加5%左右.條件隨機(jī)場(chǎng)對(duì)信息結(jié)果好壞的評(píng)估，將與最大熵模型和隱馬爾科夫模型作比較，比較性能的指標(biāo)有如下幾個(gè)方面：

3 實(shí)驗(yàn)結(jié)果及分析

3.1 定性分析

在標(biāo)注語(yǔ)料時(shí)，有一些特殊的語(yǔ)句存在歧義，導(dǎo)致標(biāo)注時(shí)模糊不清從而使得正確率下降，影響地址解析的效果.在輸出output文件中，有如表3所示例子.

表3 輸出示例Table 3 Sample output

從表3可以看到，在測(cè)試時(shí)，由于訓(xùn)練語(yǔ)料中有些市區(qū)的名字帶有“嘉”，再通過(guò)與模板結(jié)合，所以將嘉定區(qū)中的“嘉”作為了市級(jí)的地名，從而使地址識(shí)別出現(xiàn)一些錯(cuò)誤.此時(shí)，通過(guò)最大移動(dòng)窗口匹配算法，對(duì)于一些不確定的地名進(jìn)行消歧處理.

移動(dòng)窗口匹配算法，即首先準(zhǔn)備行政區(qū)劃表，將地址與行政區(qū)劃表對(duì)應(yīng)進(jìn)行匹配，得到準(zhǔn)確的行政區(qū)劃信息，實(shí)驗(yàn)表明，加入了該算法后，對(duì)歧義的消除起到了一定的作用，比對(duì)的正確率提升了4%左右.當(dāng)然對(duì)于最大移動(dòng)窗口匹配算法只能進(jìn)行部分消歧，并不能消除所有歧義，對(duì)于未消除歧義里的詞，將在后續(xù)進(jìn)行研究.

3.2 定量分析

通過(guò)分析地址解析的各種算法，將最大熵分詞算法與本文算法相比較，由于最大熵算法知識(shí)表達(dá)能力較強(qiáng)，具有易于理解、簡(jiǎn)單、可重用性等優(yōu)點(diǎn)，被廣泛用于分詞研究中，但其也具有耗資源、速度訓(xùn)練慢等缺點(diǎn).本文算法雖然全局歸一化代價(jià)高，訓(xùn)練工作量大，但其能將各個(gè)新特征進(jìn)行融合，能兼顧長(zhǎng)距離表達(dá)，靈活性好，且分詞精度高.選取2千條地址進(jìn)行解析，兩者對(duì)比結(jié)果如表4所示：

表4 結(jié)果對(duì)比Table 4 Comparison of results (%)

4 結(jié)語(yǔ)

信息解析一直為各個(gè)領(lǐng)域研究的熱點(diǎn)，本文研究地理領(lǐng)域的信息解析，采用條件隨機(jī)場(chǎng)的方法，在已知觀(guān)測(cè)序列的條件下學(xué)習(xí)，從而對(duì)目標(biāo)數(shù)據(jù)建模，通過(guò)學(xué)習(xí)訓(xùn)練數(shù)據(jù)并與特征模板結(jié)合，得到能解析地址數(shù)據(jù)的模型，解決了最大熵模型遺留的標(biāo)注偏置問(wèn)題，以及最大熵馬爾科夫模型的局部?jī)?yōu)化問(wèn)題.它能表達(dá)長(zhǎng)距離依賴(lài)性和交疊性，以序列化形式對(duì)全局的參數(shù)進(jìn)行優(yōu)化.人工標(biāo)注訓(xùn)練語(yǔ)料，并利用條件隨機(jī)場(chǎng)工具crf＋＋進(jìn)行語(yǔ)料訓(xùn)練，該模型的信息解析總的性能指標(biāo)比其它模型優(yōu)異，取得較滿(mǎn)意的結(jié)果.

致謝

感謝武漢工程大學(xué)研究生處的資助！

［1］朱?。形臉?biāo)準(zhǔn)地址庫(kù)構(gòu)建關(guān)鍵技術(shù)研究［D］．南京：南京師范大學(xué)，2013．

ZHU Jun．Reasearch on Key Techniques of constructing Chinese standard address database［D］．Nanjing：Nanjing Normal University，2013．（in Chinese）

［2］LAWRENCE R，RABOMER．A tutorial on hidden markov models and selected applications in speech recognition［J］．Proceedings of the IEEE，1989，77（2）：257-286．

［3］申彥．大規(guī)模數(shù)據(jù)集高效數(shù)據(jù)挖掘算法研究［D］．鎮(zhèn)江：江蘇大學(xué)，2013．

SHENG Yan．Research on efficient data mining algorithm for large scale data sets［D］.Zhengjiang：Jiangsu University，2013．（in Chinese）

［4］周鑫．半監(jiān)督算法在自然語(yǔ)言處理中應(yīng)用的研究［D］．哈爾濱：哈爾濱工業(yè)大學(xué)，2014．

ZHOU Xin．Research on Application of semi supervised algorithm in natural language processing［D］．Harbin：Harbin Institute of Technology，2014（in Chinese）

［5］MCCALLUM A，F(xiàn)REITAG D，PEREIRA F．MaximumEntropy Markov Models for Information Extraction and Segmentation［C］//Proc JcML，2000：591－598．

［6］PEARLJ．Probabilistic reasoning in intelligent systems：networks of plausible inference［C］//1th ed，San Mateo，CA：Morgan Kaufmann，1988：117－133．

［7］LAFFERTY J，MCCAI LUMA，PEREIRA F．Conditional Random Fields：Probabilistic Models for Segmenting and Labeling Sequence Data［C］//Proc ICML，2001．

［8］THOMPSON JD，HIGGINS DG，GIBSON TJ，et al.Improving the sensitivity of progre－ssive multiple sequence alignment through sequence weighting，position specific gap penalties and weight matrix choice［J］．Nucleic Acids Research，1994，22（22）：4673－4680．

［9］JIAYI Zhao，XIPENG Qiu，SHU Zhang．Part－of－Speech Tagging for Chinese－English Mixed Texts with Dynamic Features［J］．Journal of Computational Information Systems（JCIS），2012：1379－1388．

［10］田昕輝，李成基．帶有短語(yǔ)切分的中文文本分類(lèi)方法［J］．計(jì)算機(jī)技術(shù)與發(fā)展，2010，20（1）：9－13．

TIAN Xin－h(huán)ui，LI Cheng－ji．Chinese text classification method with phrase segmentation［J］．Computer Technology and Development，2010，20（1）：9－13．（in Chinese）

［11］SUN X L，JIA L M，DONG H H，et al．Urban expressway traffic state forecasting based on multimode maximum entropy model［J］．Science China Technological Sciences，2010，53（10）：2808－2816．

Extraction of administrative division of Chinese address based on conditional random fields

DUAN Yan－h(huán)ui1，2，LI Xiao－lin1，2，HUANG Shuang1，2
1．Hubei Key Laboratory of Intelligent Robot（Wuhan Institute of Technology），Wuhan 430205，China；2．School of Computer Science and Engineering，Wuhan Institute of Technology，Wuhan 430205，China

To extract the information of administrative division effectively from the non－standard Chinese address，a method based on conditional random fields was proposed．According to the characteristics of administrative division，the model of the target sequence was constructed on the basis of the observation sequence by using the discriminative probability model．Then，the expression model of the administrative division was obtained by constructing the corpus training set and the corresponding feature template．Finally，the performance of the model was verified by testing the test set and comparing its results with the marked test data．Experimental results show that the performance of the model is better than that of the maximum entropy model，and the accuracy rate of analysis of address information reaches 89．93%．

location information parsing，condition random fields，training corpus

TP391.41

A

10.3969/j.issn.1674-2869.2015.11.010

1674－2869（2015）11－0047－05

本文編輯：陳小平

2015－10－13

國(guó)家863項(xiàng)目（2013AA12A202）；武漢工程大學(xué)研究生教育創(chuàng)新基金項(xiàng)目（CX2014090）

段艷會(huì)（1993－），女，湖北公安人，碩士研究生．研究方向：數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)．*通信聯(lián)系人