基于規則與遺傳算法的中文地名識別

方玉萍，萬榮

(云南師范大學職業技術教育學院，云南昆明650000)

中文地名識別隸屬于中文識別中的實體命名識別的范疇，而實體命名識別的工作常常利用傳統的基于規則的方式、基于統計的方式或者利用兩者互補原則相結合的方法進行識別工作。基于規則的方法需要大量的人力編寫規則，可移植性差。基于統計的方法則需要大量的語料庫，花費高。

本文運用規則來完成中文地名的粗分，然后再利用調整窗口大小與遺傳算法來進一步優化地名，確定其是否地名。

1 構成中文地名的用字規則

地名的專用名稱(簡稱“專名”)和地方通用名稱一般就組成了中文的地名。中文地名專名是表示同類地理實體中某一個體的詞，地方通用名稱指該地方所處地理位置的實體類型的詞語，如“云南省”“撫仙湖”，其中省、湖是地名通名，云南、撫仙是地名專名。實際上還存在地名通名和專名相互轉化的情況，如柳州的“州”本是通名，卻轉化為了專名的一部分，“黃河”中的河本是專名，在這卻成了河流的通名。

中文地名的用字比較自由、分散，小的就一個單字，如“滇”“貴”等，長的大于10個字，如“那然色布斯臺音布拉格”(位于甘肅省)；通過統計發現，一般較常見的中文地名介于1 到5 個字之間，從人民日報在1998年1月份統計分析的數據來看，大于5個字的地名僅占總數的0.5%。而在《中國地名錄》中的地名用字共有3685個，中文地名的組成大部分來源于普通詞語，一般在文本中能與其他詞組成新的詞語，而地名的用字也會出現在不屬于地名中的文本中，如“云南”的“云”和“南”，經常組成非地名的詞語，比如“云朵”，“南方”等。所以，根據地名在文本中的用字和組詞能力把地名劃分為簡單的地名集和復雜的地名集，簡單地名是由1 到5 個單字構成且用字是普通用字，如“昆明市”“滬”等。而復雜地名一般是長于5 個字符的，一般較多出現少數民族地區的，比如“大理白族自治州”“那然色布斯臺音布拉格”等。

所以中文地名具有以下一些特點：

1)沒有明確規范的命名標準，命名規律難以追溯。有些地名是以人文地物命名，有些與歷史人物或事件有關，并且還不斷有新詞加入；

2)地名用詞比較自由，分散；

3)地名結尾常常伴有一些特征指示詞出現，如“省、市、路、區”等；

4)地名相對其他命名實體具有一定的穩定性，但數量卻很龐大；

5)地名的長度沒有限制，小至單字，如“滇、滬”等，長至10多個字，如“那然色布斯臺音布拉格”(位于甘肅省)；

6)地名可有多個并列或重疊出現的地名，如“云南省昆明市五華區建設路”；

7)地名特征詞的出現會嵌套到詞語內部中，有些地名還會包含有多個特征詞，如“樂山縣”“濱江公園”；

8)有些地名會再次組成新的地名詞，如“湛江市”；

9)地名還會作為機構名的一部分出現，如“昆明市植物研究所”是一個機構名，但內部卻出現了地名“昆明市”；

10)單字詞經常出現在地名中，如“南/朝/門”，“沙/河/口”；

11)地名會和指示詞組成新的詞語一起出現；

12) 地名具有多樣性，如“大理白族自治州”作為地名，但“大理”也可以作為地名出現；

13)同名地名數量也不少，如“北京路”在同一行政區會出現多次。

2 中文地名識別的方法

1)基于規則的方法：基于規則的方法具有代碼小，程序本身的花費不大，所以耗時小，對小文本規模小時，識別的效果好，但會被詞語的更新導致要經常更換規則，所以成本不小。

2)基于統計的方法：統計方法主要有決策樹模型、隱馬爾科夫模型、支持向量機、最大熵、條件隨機場等都被用于地名識別，但統計的方法比較耗時，所以單獨使用的情況不多。

3)規則與統計相結合的方法：一般會利用統計方法對專有名詞進行識別，其后在此基礎上用規則對其進行細化。但統計方法依據概率識別在很大程度上依賴訓練語料的大小；而在此方法中觸發專有名詞來進行識別處理，這樣會忽略掉一些特征詞不是很明顯的地名；如果單字概率大的話，會造成內部成詞的情況，這樣地名很難召回。

4)專家系統方法：系統把切分文本作為樹中的節點，利用知識庫進行搜索匹配。若匹配成功，則該詞把原文本再作為左右分支，又以該詞作為子樹的根，形成一棵新樹。專家系統方法由于要考慮到文本的語義、上下文的聯系等因素，實際實施起來效果不理想。

綜上，中文地名識別基本上都是采用以上的方法加上某個識別方法一起進行識別操作。

3 基于規則的地名識別

本文中，基于規則的中文地名識別是在文本集已經進行了一次粗分詞的基礎上進行的。本文充分研究了在傳統的基于規則的地名識別方法上，嘗試用可調整窗口大小方法，一來彌補傳統規則方法中召回率不佳的情況，二來有效減少規則計算量大的缺陷。

根據地名的常用長度來計算，以文本左側為起始點設置窗口大小為5，然后尋找右側的邊界詞，最后確定出地名集。

規則1：單字若位于地名左右指界詞中時，并且該單字屬于單字地名集，則該字可判斷為地名。如“滇為昆明的簡稱”中的“昆明”為地名，其前為地名指界“為”，所以能判斷出“滇”為地名。

規則2：由表示并列關系的詞或符號連接的詞，并且前后字都在單字地名集中或其中一個判斷出為地名，都可判斷出所有的單字都為地名。如“來自亞、拉、非大洲的人們”中的“亞、拉、非”中間有并列符號“、”且單字都在單字集中，可判斷出它們都是地名。

規則3：若前后出現的詞可搭配，可判斷出中間出現的詞為地名。如“學生沿著南屏街游行”，而“沿著”“游行”前后詞可搭配，所以判斷出“南屏街”為地名。

規則4：連續出現多級地名時，中間有行政特征字時，可判斷出前后各為一個地名，如“在云南省大理市舉行”中，“云南省大理市”有行政特征字“省”，所以“云南省”和“大理市”各為獨立的地名。

規則5：在像“潘長江悲傷至極！”中一般會把“長江”誤識別為地名，根據后面搭配的詞語是與人名常用的詞組“悲傷”，所以排歧時把“長江”排除在地名集外。

規則6：若在地名前有姓氏集出現的詞，可以把地名排除在外。如“王昆明將進入附中學習。”中，地名“昆明”前出現姓氏“王”，所以可判斷出“王昆明”是姓氏。

規則7：地名詞組前后若有單字且單字在地名集時，該字可判斷出單字為單字地名，如“滇為昆明的簡稱”中，“昆明”是地名，其前為地名引導詞“為”，所以可判斷出“滇”為地名。

4 遺傳算法

遺傳算法GA 是一種模擬自然選擇和遺傳機制的尋優程序，它將“優勝劣汰，適者生存”的生物進化論原理引入到優化參數形成的編碼串聯群體中，按所選擇的適應值函數并通過遺傳中的復制、交叉和變異對個體進行篩選，使適應值高的個體保留下來，組成既繼承了上一代信息又優于上一代的新群體。所以遺傳算法特別適用于處理優化研究的工作。

1)地名候選詞篩選。

在上述利用規則方法進行分詞基礎上來完成，對字串String=S1…Si…Sn的首字S1，Si和Sn進行判斷，利用概率值P(S1)、P(Si)、P(Sn)來計算地名的首字、中間字和末字的概率。如果字串String滿足下列條件，則認為它是候選地名。P(S1)>y1,P(Si)>yi,P(Sn)>yn;如果文本集有多字詞d 出現，根據首字中字末字的位置，還應滿足下列條件：C1(d)>0,Ci(d)>0,Cn(d)>0，其中，y1,yi,yn分別是地名首、中、末字所對應的閾值，C1,Ci,Cn是多字詞d在文本中作為首、中、末詞的次數。

2)上下文分析。

對于篩選字串SString=H1…Hn。利用上下文分析來進行識別，如句中的稱謂詞(CW)、指界詞(ZJ)、地名指示詞(DZS)、特征詞(TZ)、標點(PD)等上下文信息來處理。根據候選地名集中是否有相鄰的前后兩個詞，如果是地名，則作標志，以便下步工作細化。

3)利用遺傳算法進一步確定地名。

將候選地名作為遺傳算法中的初始群來處理，利用遺傳算子進行最優集篩選。

4.1 適應值函數

4.2 初始種群的確定

遺傳算法執行前要先確定初始種群及其編碼方式，而算法中最常見的編碼有二進制編碼和實數編碼。二進制編碼簡單方便，但每次都要在每代染色體中進行編碼和解碼的工作，根據問題的復雜和處理數據的多少會提高誤差。實數雖然復雜，但它能提高算法的收斂速度，而減少運行的計算時間。

本文選用的編碼是實數編碼，通過實驗中選擇的種群規模取值為60個。

4.3 選擇算子

也稱復制算子，相比適應值的可行解，它具有較高的適應度，這樣更有機會繼承優良基因。選擇算子一般有比例選擇算子、排序選擇算子和最優保存策略等算子。本算法中采用最優保存策略算子，這樣能保證全局的收斂性。

4.4 交叉算子

利用雙親的基因進行某種形式的交叉，交叉算子有單點交叉、多點交叉和算術交叉。交叉算子一般按下面的步驟進行：

1)從待交配的種群中，根據某種形式選出要進行交配的一對個體；

2)選擇一個或多個對應點作為交叉位置；

3)在交叉點按照一定的策略進行基因互換，交換完后生成新的一對個體。

本文算法采取均勻算術交叉算子進行交叉選擇，Xn+11=

4.5 變異算子

變異算子有基本位變異、均勻變異和高斯變異等，它會產生與原個體性狀差異較小的新個體。本文選用均勻變異算子，首先指定個體編碼串的變異點，再根據變異概率從對應的基因取一隨機數來替代原有值。

4.6 終止條件

設置遺傳算法停止運行的條件有兩種，一種是設置算法終止運行的代數，另一種是設定適應值的取值，若連續幾代都小于取值就終止運行。

4.7 算法描述

1)初始化群體：設置進化迭代次數的最大值，迭代計數器清零，初始化群體；

2)適應值的設置：計算適應度值，見公式(1)；

3)交叉算子的計算：隨機匹配一對雙親，根據4.4計算其雙親的交叉值，依據適應度比例交叉重組，如果交叉后的個體優于雙親，則替換，否則下一步；

4)變異算子的計算：根據4.5進行變異個體，如果變異后的個體優于前面的個體，則替換舊個體，否則做下一步；

5)評估函數的計算：根據測試集設置閾值，當優良的個體達到了閾值，并在約束條件范圍內，則將其置換進優良的群中；否則轉換進不符合條件的群中；

6)新個體的產生：當有新個體產生時，應當讓它與優良的群體中的所有個體有所差別，這樣能讓算法的搜索力度更大；

7)終止條件：當算法搜索到滿足的條件時，跳出程序并終止算法；否則跳到以上的第3)步繼續算法。

算法過程：

1)OldPop(n)=Rand(n)，隨機產生種群；

2)Fit(f(n))=OldPop(n),計算種群的適應值；

3)如果是最優種群，則進行最優保存策略計算個體算子，并找到最優個體；

4)進行交叉運算，得出NewPop(n)；

5)Worst_1=最劣個體，Worst_2=次劣個體；

6)Worst_1=最優個體Best_1；

7)添加一個個體Add(n)到OldPop群中;

8)計算Add(n)的適應值Fit(f(add(n));

9)判斷Fit(f(add(n))是否大于Worst_2，如果大，則Worst_2=add(n);

10) 如果循環次數小于最大代數，則OldPod(n) =NewPod(n)，轉2)，否則輸出結果，結束程序。

5 結束語

對于中文地名的識別方法，本文主要研究了如何利用窗口的大小在規則中尋找出基本的地名集，然后再通過遺傳算法的尋優功能確定出真正的地名集，并總結了中文地名的特點及其用字的一般性，綜合利用規則與遺傳算法各自的優缺點，組合進行了地名的識別。實驗數據來自1998 年1 月份的《人民日報》標注語料。全庫約有175萬字，包含地名共27890個。規則識別部分采用C語言編寫，遺傳算法利用Matlab運行。實驗結果采用三大評價指標，即準確率(P)召回率(R)和綜合值(F)：

通過實驗數據，在正確率和召回率上比傳統的規則識別方法有所提高，算法也有很好的效果。