基于规则与遗传算法的中文地名识别

方玉萍，万荣

(云南师范大学职业技术教育学院，云南昆明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)：

通过实验数据，在正确率和召回率上比传统的规则识别方法有所提高，算法也有很好的效果。