基于C-F模型的中文地址行政區(qū)劃辨識方法

李曉林，張 懿+，周華兵，李 霖

(1.武漢工程大學 計算機科學與工程學院，湖北 武漢 430205；2.武漢工程大學 智能機器人湖北省重點實驗室，湖北 武漢 430205；3.武漢大學 資源與環(huán)境科學學院，湖北 武漢 430079)

0 引 言

隨著城市現(xiàn)代化建設的發(fā)展，城市命名方式不斷變化，故急需更新和完善現(xiàn)有地理位置信息庫。而伴隨著人們出行、交流等對互聯(lián)網(wǎng)的不斷依賴，使互聯(lián)網(wǎng)中積累了大量蘊含地理位置信息的中文地址，故可通過提取其中的有用信息來獲取人們普遍使用的地理位置信息表示方式。但由于人們網(wǎng)絡交流的隨意性，導致互聯(lián)網(wǎng)中大部分中文地址表達方式紛繁復雜、形式各異[1]。且中國地域廣闊，地理位置信息的雜亂與不規(guī)范，同時具有極強的區(qū)域特色，往往會增加辨識的難度或引發(fā)辨識的歧義。

中文詞語之間無明顯的分割符號，相同詞在不同語境中存在不同含義[2]。對于一條地址字符串，如果省略區(qū)劃特征字，其中可能包含多個行政區(qū)劃信息，如“江蘇鼓樓廣場”，其中“江蘇”匹配行政區(qū)劃“江蘇省”，“鼓樓”匹配“江蘇省南京市鼓樓區(qū)”和“江蘇省徐州市鼓樓區(qū)”；又如“湖北省洪山”，其中“洪山”匹配“湖北省武漢市洪山區(qū)”和“湖北省隨州市洪山鎮(zhèn)”。類似行政區(qū)劃匹配結果的多樣性與歧義性對地址信息的準確辨識均產生影響。

為了更好地構建地理位置信息庫，就需首先解決地理文本信息中的中文地址行政區(qū)劃信息提取問題。

1 相關工作

針對中文地址識別國內已有大量研究，特別是對行政區(qū)劃特征完整且無歧義的中文地址的識別已達到較好的效果。目前主要采用的方法可分為3個方面：基于特征詞的地址分詞算法、基于機器學習模型的地址識別以及基于自然語言理解的地址要素識別。

文獻[3]采用特征詞匹配的思想，提出了一種前后綴與特征詞相結合的地名地址識別提取方法。首先利用HMM訓練進行分詞，接著通過地名地址前后綴詞庫進行候選地名切分與預提取，最后根據(jù)特征詞進行匹配過濾，實現(xiàn)對地名地址的準確提取[3]。該算法具有較高的運行效率，但分詞結果的正確率十分依賴于地址信息中是否存在特征字，當特征字缺失時，會嚴重影響分詞的準確率。目前較為熟知的機器學習模型主要有隱馬爾科夫模型(HMM)、最大熵模型(MEMM)和條件隨機場(CRF)模型等，其中CRF模型具有特征選擇靈活和擬合程度較好的優(yōu)點[4]。文獻[5]利用條件隨機場模型，根據(jù)中文地址行政區(qū)劃的表達特點，結合判別式概率模型和四詞位標注法，首先對觀測序列進行標注以對目標序列建模，通過構建語料訓練集和特征模板，得到行政區(qū)劃的表達模型[5]。雖然該方法的識別準確率能夠到達近90%，但需要對語料進行人工標注，工作量太大，同時模型訓練的效果過于依賴所選取語料的規(guī)范性。基于機器學習的方法可以通過對中文語義進行標注，有效獲取語句結構中的語義信息，但存在設計復雜、條件要求過強等缺陷[6]。文獻[7]和文獻[8]在自然語言理解的基礎上對中文地址進行識別。文獻[7]通過建立空間關系地址模型和地址庫邏輯模型以解決中文地址抽象問題和地址信息空間知識表達問題，依據(jù)中文分詞和語義推理原理，在結合自然語言理解方法和地址匹配方法的基礎上，建立基于自然語言理解的中文地址識別算法；文獻[8]從人類理解地址的角度出發(fā)，通過互聯(lián)網(wǎng)中蘊含的地名信息建立一個地址知識庫，從而對地址進行解析、更新等操作。雖然文獻[7]和文獻[8]的實驗結果準確率較高，但文獻[7]僅對河南省濮陽市人口庫1000條居民地址數(shù)據(jù)進行測試，測試數(shù)據(jù)集太小且區(qū)域性太強，缺乏足夠的說服力，文獻[8]主要針對電力系統(tǒng)業(yè)務部門中的地址數(shù)據(jù)進行識別，同樣缺乏通用性。

上述方法均可以解決行政區(qū)劃完整且無歧義的中文地址識別問題，但針對網(wǎng)絡中出現(xiàn)的雜亂無章且行政區(qū)劃存在模糊、缺失的地址的識別則存在如下問題：①建立了標準地址庫以匹配標準地址中的行政區(qū)劃，但對于無特征信息標簽，且會產生歧義的非標準化地址，將產生錯誤的匹配結果。如“南京江寧芙閣路蘭州拉面館”，其中“蘭州拉面館”會錯誤匹配為“蘭州市”；②僅依據(jù)地名詞典進行特征字直接匹配的方法，大多沒有考慮地址的語義信息，導致查找結果多樣，查找的準確性較低，無法較準確的獲取地址中包涵的行政區(qū)劃；③地址標準化工作較為繁重，或字符串匹配次數(shù)較多，或算法迭代次數(shù)多，導致程序計算量太大，系統(tǒng)運行速度慢；④僅依靠行政區(qū)劃完善的地址數(shù)據(jù)作為訓練樣本，雖對類似結構的地址文本具有較好的識別率，但對行政區(qū)劃模糊或缺失的地址信息的識別效果較差，識別方法具有一定的局限性。

為解決上述不確定性問題，本文事先建立一個有限的、輕量級的1-3級標準基址庫[9]。在此基礎上提出一種基于可信度模型的行政區(qū)劃可信度計算方法，利用可信度方法的概念與模型對地址行政區(qū)劃的可信度進行推理計算，從而得到更準確的中文地址行政區(qū)劃。

2 可信度計算方法

可信度方法是一種基本的不確定性推理方法，又稱C-F模型，具體含義請參考文獻[10]。結合此模型，將行政區(qū)劃作為證據(jù)，其對應匹配的行政區(qū)劃結果作為結論，并對多個匹配結論的可信度進行不確定性推理，選擇可信度最高的區(qū)劃結論作為地址的行政區(qū)劃信息。

2.1 名詞解釋

(1)初始信度(initial credibility，IR)表示地址字符串對應行政區(qū)劃結論集中的各區(qū)劃結論作為地址字符串準確定位信息的初始信任程度。

(2)傳遞因子(transfer factor，TF)表示地址字符串中各行政區(qū)劃匹配結論間信度相互傳遞的系數(shù)，即0

(3)傳遞信度(transfer credibility，TR)表示地址字符串中各行政區(qū)劃結論所包含地理信息的關系程度。可表示為

傳遞信度=初始信度×傳遞因子

(4)移動窗口最大匹配算法(maximum moving window match，MMWM)通過動態(tài)調整匹配窗口的大小，截取地址字符串的子串并與標準行政區(qū)劃字典進行匹配，從而得到其中包含的行政區(qū)劃結論集。算法詳細步驟請參考文獻[11]。

2.2 區(qū)劃可信度計算方法

將地址字符串包含的行政區(qū)劃作為不確定性推理的證據(jù)，區(qū)劃匹配的地址結果作為不確定性推理的結論；辨識方法總體流程如圖1所示。

圖1 中文地址行政區(qū)劃信息提取流程

具體計算方法與步驟如下：

(1)利用行政區(qū)劃字典和移動窗口最大匹配算法，匹配得到地址字符串所包含的可能行政區(qū)劃結論集。

(2)對一個待查詢地址字符串，當其中行政區(qū)劃作為推理證據(jù)時，依據(jù)其位置因子(factor position，F(xiàn)P)與匹配模式系數(shù)Mode(i)，計算該證據(jù)行政區(qū)劃的初始信度。

首先根據(jù)行政區(qū)劃表，對待查詢地址字符串進行分詞，得到若干個行政區(qū)劃字符串。

(1)

同時，證據(jù)行政區(qū)劃初始信度如式(2)所示

(2)

式中：Mode(i)為第i個行政區(qū)劃字符串的系數(shù)，如果是完全匹配模式，如地址字符串“湖北省武漢市”匹配行政區(qū)劃“湖北省”、“武漢市”，則Mode(i)=0.9，此處不設Mode(i)=1.0的原因在于，完全匹配的行政區(qū)劃中可能包含命名實體，匹配模式會誤將其識別為地址行政區(qū)劃，例如：“武漢市江夏區(qū)蘭州拉面館”中的“蘭州”即為命名實體；如果是部分匹配模式，如地址字符串“湖北武漢”匹配行政區(qū)劃“湖北省”、“武漢市”等，則必須保證其匹配模式系數(shù)小于完全匹配時的系數(shù)，故Mode(i)=0.7；同理，如果是簡稱匹配模式，則Mode(i)=0.5。

(3)對于一個地址字符串，當其包含多個行政區(qū)劃證據(jù)時，行政區(qū)劃結論集中的匹配結論會對應多個不同的地理位置信息。但從語義的角度考慮，不同區(qū)劃匹配結論間仍存在一定的位置關系，即會將自身區(qū)劃證據(jù)初始信度傳遞到相關匹配區(qū)劃結論中，以相互支持各區(qū)劃證據(jù)。

傳遞因子主要由兩個不同地址匹配地址結論中的相同區(qū)劃個數(shù)S(i,j)和區(qū)劃位置級差因子FPL(i,j)確定，且傳遞因子與區(qū)劃級差相關因子(factor position level relation，F(xiàn)PLR)密切相關，故需先得出FPLR(i,j)，如式(3)所示

FPLR(i,j)=FPL(i,j)+S(i,j)

(3)

假設有區(qū)劃證據(jù)“南京”和“鼓樓”，證據(jù)“南京”匹配區(qū)劃結論為A1：“江蘇省南京市”，“鼓樓”匹配區(qū)劃結論為A2：“江蘇省南京市鼓樓區(qū)”和A3：“江蘇省徐州市鼓樓區(qū)”，由此可得S(A1,A2)=2，S(A1,A3)=1。

對于包含完整行政區(qū)劃的地址，其區(qū)劃行政級別變化趨勢往往與位置值的變化趨勢保持一致，如當Pos(1)=“省”,Pos(2)=“市”； 而在存在行政區(qū)劃模糊或缺失的地址中，F(xiàn)PL(i,j)的變化趨勢較為復雜多變，但本文主要針對省、市和區(qū)三級行政區(qū)劃，即Lev(i)∈{1,2,3}。 通過對大量實際地址中出現(xiàn)的行政區(qū)劃的級別與位置進行分析，可得區(qū)劃級差相關因子具體表示形式，如式(4)所示

(4)

由式(4)可知，F(xiàn)PL(i,j)≤1且0≤S(i,j)≤3， 同時為滿足0≤TF≤1， 故令傳遞因子TF(i,j)如式(5)所示

(5)

(4)對于某一地址字符串，將其中行政區(qū)劃作為證據(jù)，根據(jù)位置因子和匹配區(qū)劃級別，得到其對應行政區(qū)劃結論的初始信度。雖然不同行政區(qū)劃匹配出各自對應行政區(qū)劃結論，但結論之間存在一定的地理位置關系。故需利用不確定性的信度傳遞概念，對各證據(jù)的初始信度進行轉移，由式(2)和式(5)可知

(6)

依據(jù)式(7)得出各行政區(qū)劃結論間的傳遞信度后，以此計算各行政區(qū)劃傳遞信度的總和，并作為各行政區(qū)劃信度的更新值，記為Credibility(j)，如式(7)所示

(7)

最后，選取行政區(qū)劃結論集中可信度最大的行政區(qū)劃結論作為地址字符串的地理定位區(qū)劃方式，如式(8)所示

(8)

3 實驗設計與分析

本文方法主要針對中文地址行政區(qū)劃信息的辨識與提取，為了充分體現(xiàn)本文方法在解決地址行政區(qū)劃模糊、缺失和歧義等問題上的優(yōu)勢，需對實驗進行一定設計，并在此基礎上對實驗結果進行分析。

3.1 實驗設計

為驗證本文方法的有效性，需準備一個結構規(guī)范，內容較為完整的行政區(qū)劃字典，作為信息匹配的依據(jù)。實驗設計的主要內容包括：測試語料預處理和實驗組合方式。

(1)測試語料預處理

利用網(wǎng)絡爬蟲算法從互聯(lián)中獲取25萬條地址數(shù)據(jù)。然而，這些地址大多包含冗余的信息，其中“路”特征詞等低級區(qū)劃信息會對實驗結果的準確性產生較大干擾，如“上海路”、“南京路”和“武漢大道”等會匹配得到“上海市”、“南京市”和“武漢市”等干擾信息。為了排除此干擾，體現(xiàn)本文方法在針對行政區(qū)劃信息辨識上的優(yōu)越性，本文實驗對于中文地址的預處理方式為省略低級區(qū)劃，只保留三級行政區(qū)劃等有效信息。

(2)實驗組合方式

在所選取的測試語料中，有些地址信息十分完整與確切，如“湖北省武漢市”，此時可通過完全匹配的方式獲取其中行政區(qū)劃信息“湖北省”和“武漢市”；但也存在行政區(qū)劃特征字缺失的情況，如“安徽合肥”，此時只能依靠部分匹配的方式，“安徽”部分匹配“安徽省”，“合肥”部分匹配“合肥市”。

為了能夠更加完整的獲取地址行政區(qū)劃信息，并體現(xiàn)本文方法能夠有效解決行政區(qū)劃特征字缺失、歧義等問題，實驗采用完全匹配查詢、完全匹配查詢+部分匹配查詢兩種方式；并將原始語料與經(jīng)過預處理的語料分別與兩種匹配方式進行組合實驗。

3.2 實驗結果與分析

通過可信度計算方法獲取可信度最大的區(qū)劃結果作為地址字符串的地理定位信息。4種實驗組合方式的具體實驗結果見表1。

表1 可信度計算實驗結果

本文通過設計計算方法，對地址行政區(qū)劃信息進行辨識，4種實驗方式的時耗相差不大且均可被接受，故重點討論各組合實驗方法的正確率。

(1)若匹配方式不變

均選擇完全區(qū)劃匹配查詢時，會將原始地址集字符串中所有以行政區(qū)劃命名的路街等信息過濾掉，同時也會忽略地址中省略特征詞的字符串，故是否對數(shù)據(jù)進行預處理，對行政區(qū)劃元素選擇的正確率沒有影響。

均選擇完全+部分區(qū)劃匹配查詢，對原始數(shù)據(jù)而言，由于完全+部分匹配查詢是對關鍵字進行匹配查詢，會匹配得到產生干擾的行政區(qū)劃，比如“南京路”將匹配成“南京市”，對結果的選擇造成影響；而對于經(jīng)過預處理的測試語料，已排除了上述干擾，并綜合考慮了完全匹配、部分匹配及行政區(qū)劃層次結構等因素，故結論具有較大的可確定性，且識別正確率高于單純地選擇最大行政區(qū)劃的結果。

(2)若測試地址集不變

對于原始數(shù)據(jù)而言，因未對其作任何的預處理工作，其中包含較多冗余且易產生歧義的信息，故當采用完全+部分匹配方式時，會將部分命名實體或街道名等錯誤地識別為行政區(qū)劃信息，給計算方法提供了錯誤信息，干擾了地址區(qū)劃信息的識別，故導致識別準確率較低。

對于經(jīng)過預處理，省略了低級區(qū)劃信息的地址而言，排除了“路”特征字產生的干擾后，其所產生的歧義信息大多是由行政區(qū)劃的模糊、缺失和不確定性導致了。當采用完全+部分匹配規(guī)則時，可以獲取更多的行政區(qū)劃信息，即增強了信息間的約束，并通過本文提出的計算方法，能夠正確地識別出其實際指定的行政區(qū)劃信息。

故在對測試語料進行預處理的基礎上，采用完全+部分匹配方法能夠更好地說明本文計算方法在針對解決行政區(qū)劃信息模糊、缺失等問題上的優(yōu)勢。

通過對具體實驗結果觀察分析發(fā)現(xiàn)，在完善區(qū)劃匹配詞典的基礎上，對于較為規(guī)范的地址有非常高的識別正確率，同時針對行政區(qū)劃不完整且存在地址要素殘缺的非規(guī)范地址，本文提出的證據(jù)可信度計算方法，能夠較好地識別一般方法無法確定或識別錯誤的地址字符串中蘊含的地址區(qū)劃信息。比如地址“中山東港新區(qū)金廣東海岸濱城”，其中包含多個相互間存在沖突或關聯(lián)的行政區(qū)劃結論，見表2。

表2 地址行政區(qū)劃結論

顯然一般的地址匹配算法或要素解析規(guī)則是無法確定該地址的行政區(qū)劃。究其原因在于，或地址中出現(xiàn)多個地址要素，或將命名實體錯誤的識別為地址要素。當多個地址要素代表的行政區(qū)劃結論存在較大歧義時，無法確定其準確的信息。本文提出的可信度計算方法，通過公式計算的方法，選取地址中可信度較大地址要素代表的行政區(qū)劃結論作為地址行政區(qū)劃信息。通過本文的計算方法可以正確地確定地址“中山東港新區(qū)金廣東海岸濱城”，指定的是“遼寧省大連市中山區(qū)”，且與實際情況相符。

本文計算方法雖然可以解析大部分規(guī)則或不規(guī)則的中文地址，但對于少量特殊的地址字符串，識別結果與地址實際位置信息依然存在偏差。針對原始地址語料識別失敗的結果主要分為以下兩種情況：

(1)實際情況中存在單字行政區(qū)劃，其將對地址字符串中行政區(qū)劃信息的提取產生嚴重干擾。如地址：“江南區(qū)沙井大道”，其中“江南區(qū)”匹配行政區(qū)劃“廣西壯族自治區(qū)南寧市江南區(qū)”。但由于匹配詞典中存在單字行政區(qū)劃“南區(qū)”，無論正向匹配算法還是反向匹配算法[9]，均會將“江南區(qū)”識別為“南區(qū)”，匹配行政區(qū)劃“廣東省中山市南區(qū)”等；同時由于地址字符串中無其它地理定位信息，導致無法準確獲取該地址的地理位置信息。具體計算結果見表3。

表3 區(qū)劃可信度計算結果二

(2)由于實驗地址數(shù)據(jù)形式各異，其中存在大量非標準地址，如：“合肥市明光”。當對原始地址進行完全匹配時，得到行政區(qū)劃“安徽省合肥市”；當對原始數(shù)據(jù)進行完全+部分匹配時，得到行政區(qū)劃“安徽省滁州市明光區(qū)”。通過計算得到兩種行政區(qū)劃匹配結果的可信度，具體計算結果見表4。

表4 區(qū)劃可信度計算結果三

由表4可知，本文計算方法將得到錯誤的行政區(qū)劃識別結果。識別錯誤的主要原因在于，地址信息的識別產生歧義且該地址中并無其它區(qū)劃信息以支撐相關結果。

本文計算方法主要解決“省市區(qū)”三級行政區(qū)劃的信息提取，故若地址中包含路街等位置信息時，則可以將其忽略，即對語料進行預處理，以提高地址行政區(qū)劃匹配精確度。由表1實驗結果可知，當對測試地址語料中的“路”特征字進行預處理后，實驗準確率有了顯著提高，當采用完全與部分區(qū)劃匹配方式時準確率達到94.81%。由此可見，當?shù)刂沸姓^(qū)劃信息充足時，本文方法在解決地址行政區(qū)劃信息模糊、缺失和歧義等問題是十分有效的。

3.3 對比實驗

通過分析中文地址解析方法在各種算法中的應用，將本文方法與基于特征字匹配方法、基于條件隨機場方法和基于自然語言理解的地址識別方法進行對比實驗。為了使實驗方法根據(jù)說服力，將上述方法分別對本文經(jīng)過預處理的地址數(shù)據(jù)測試集進行實驗，具體識別結果對比見表5。

表5 識別結果比較表

采用基于特征字匹配方法的分詞結果正確性通常取決于地址信息中是否有特征字符，若地址中沒有出現(xiàn)能夠區(qū)分“省市區(qū)”信息的特征字符，就會影響分詞的正確性，故對于本文從互聯(lián)網(wǎng)中獲取的雜亂無章且存在行政區(qū)劃缺失的地址，該方法無法識別，導致識別準確率很低。采用基于條件隨機場算法，利用地址要素標注集進行人工標注，可以識別地址語料蘊含的位置信息，但識別性能一般，且需要耗費大量的精力對語料進行標注，方法的效率不高。目前采用的基于自然語言理解的方法具有較大的局限性，模型對訓練語料依賴較強，針對互聯(lián)網(wǎng)中大量雜亂無章的地址識別效果較差。本文提出的可信度計算方法，不僅效率高，同時可以通過有效的計算消除地址字符串之間存在的歧義，并完善地址行政區(qū)劃信息。

4 結束語

互聯(lián)網(wǎng)中地址文本錯綜復雜、雜亂無章，難以通過一種方式有效解決所有形式地址的地理位置信息提取問題。本文提出一種基于可信度模型的行政區(qū)劃可信度計算方法，能夠靈活處理不同結構地址的行政區(qū)劃信息。利用移動窗口最大匹配算法對地址字符串進行行政區(qū)劃匹配[12]，在顧及中文地址語義的前提下，根據(jù)中文地址的表達特點，建立行政區(qū)劃匹配規(guī)則和可信度計算方法，能夠有效地處理引發(fā)歧義的行政區(qū)劃信息，提高了中文地址行政區(qū)劃解析的正確率和時效性。

在未來的工作中，可在此研究的基礎上，進一步增加行政區(qū)劃級別識別的級數(shù)，通過處理結構更為復雜的地址獲取更為完善的地理位置信息。