基于遗传算法的中文地名识别1

基于遗传算法的中文地名识别1

方玉萍万荣方达

（云南师范大学职业技术教育学院云南昆明6500000）

摘要：中文地名识别是中文未登录词范畴，也是命名实体识别中的重要研究内容之一。传统的中文地名识别主要基于词性或地名要素特征进行挖掘，其识别率不高。基于遗传算法的中文地名识别方法，充分利用了遗传算法特有的优胜劣汰机制对中文地名进行筛选寻优，最终得到中文地名，试验表明该算法在中文地名识别中的正确率和准确率都有所提高。

关键词：地名识别；算子；遗传算法；函数

Abstract:ChineseplacenamerecognitionisacategoryofChineseunregisteredwords,anditisalsooneoftheimportantresearchcontentsintheidentificationofnamedentities.TraditionalChineseplacenamerecognitionismainlybasedonthepartofspeechorthecharacteristicsofgeographicalnames,anditsrecognitionrateisnothigh.Basedonthegeneticalgorithm,themethodofChineseplacenamerecognitionmakesfulluseoftheuniquemechanismofgeneticalgorithmtoselectandsearchforChineseplacenames.Finally,theChineseplacenamesareobtained.TheexperimentshowsthattherateofcorrectandaccuracyinChineseplacenamerecognitionareimproved.

Keywords:placenameidentification;Operator;Geneticalgorithms;Functions;

1.引言

中文地名识别隶属于未登录词范畴，在Web上有许多包含中文地名的文本，如何从文本中将地名识别出来，挖掘其隐含的空间信息，不仅能够方便快捷用户进行文本的查找和浏览，丰富地理信息的数据来源，有利于地理信息的检索及定位服务等领域的发展。中文地名在登录词中占有很大的比重，而中文地名的长度没有统一的长度，所以中文地名的识别研究工作也是未登录词识别的难点之一。

国内研究中文地名识别的工作主要从以下几个方面进行：（1）采用了统计的模型，利用属性矩阵的频级进行筛选，达到了较高的召回率，但精确率偏低；（2）采用基于语料库的方法，根据地名词典统计分析地名用字的信息以及这些字在真空文本中的使用频度进行地名的用字信息分析，对地名识别取得了一定的效果；（3）通过规则识别的方法，规则相对复杂；（4）基于交换的地名识别，通过上下文分析，进行地名出现规律再进行筛选，这种方法提高了系统的精确率。

而通过遗传算法进行中文地名识别的工作几乎未开展，遗传算法是参照生物世界中的遗传与进化过程，遵循“物竞天择，适者生存”的原则，根据某种策略生成的一定数量的初始可行解组成的群体开始，经过基因复制、交叉重组、突变等遗传操作，将这些可行解逐渐逼近所研究问题的最佳可行解。

2.基于遗传算法的中文地名识别算法

遗传算法起源于自然界中的繁殖杂交和变异过程中的“优胜劣汰”，它是从一个种群开始搜索，在进化过程中需要进行适应值来定义是否符合群体发展，所以应用遗传算法，需要解决5个方面的基本问题：适应值函数定义，初始种群的确定，染色体表示，遗传算子定义，终止条件选择。

2.1适应值函数

适应值函数是使算法得到最优解的途径之一，如果一个个体的适应值不符合适应值函数则会加大淘汰的概率，反之保留的概率加大。一般是将问题的目标函数设置为适应值函数，但比较复杂的问题中设置适应度函数都是根据阈值或加上惩罚因子来进行调整使用。一般的个体适应值函数评价过程为：

（1）个体群体编码，得到个体的遗传基因。

（2）计算出个体的目标函数值。

（3）根据问题求出个体适应值。

Fit(f(x))=aF+b

2.2初始种群的确定

遗传算法执行前要先确定初始种群及其编码方式，而算法中最常见的编码有二进制编码和实数编码。二进制编码简单方便，但每次都要在每代染色体中进行编码和解码的工作，根据问题的复杂和处理数据的多少会提高误差。实数虽然复杂，但它能提高算法的收敛速度，而减少运行的计算时间。

在文选用的编码是实数编码，通过实验中选择的种群规模取值为60个。

2.3选择算子

也称复制算子，相比适应值的可行解它具有较高的适应度，这样更有机会继承优良基因。选择算子一般有比例选择算子、排序选择算子和最优保存策略等算子。本算法中采用最优保存策略算子，这样能保证全局的收敛性。

2.4交叉算子

利用双亲的基因进行某种形式的交叉，交叉算子有单点交叉、多点交叉和算术交叉。交叉算子一般按下面的步骤进行：

(1)从待交配的种群中，根据某种形式选出要进行交配的一对个体；

(2)选择一个或多个对应点作为交叉位置；

(3)在交叉点按照一定的策略进行基因互换，交换完后生成新的一对个体。

本文算法采取均匀算术交叉算子进行交叉选择，X1n+1=aX2n+(1-a)X1n，X2n+1=aX1n+(1-a)X2n，其中a为常数。

2.5变异算子

变异算子有基本位变异、均匀变异和高斯变异等，它会产生与原个体性状差异较小的新个体。本文选用均匀变异算子，首先指定个体编码串的变异点，再根据变异概率从对应的基因取一随机数来替代原有值。

2.6终止条件

设置遗传算法停止运行的条件有两种，一种是设置算法终止运行的代数，另外一种是设定适应值的取值，若连续几代都小于值就终止运行。

3.算法描述

（1）初始化群体：设置进化迭代次数的最大值，迭代计数器清零，初始化群体；

（2）评估个体：根据设计的适应度计算方法评估第t代群体Fit（f(t)）中所有个体的适应度值；

（3）交叉算子：随机匹配一对双亲，对它们相应基因执行基于适应度比例的交叉重组，如果交叉后生成的个体比双亲更加优良，则替换相应的某个双亲，否则不替换。

（4）变异算子：对个体执行基于适应强度的变异进化，如果变异后的个体比变异前的个体更优秀，则做相应的替换，否则不作替换。

（5）评估函数：假如个体的优良种群达到了阈值，并符合约束条件，若优良子群中没有新的个体，那么将其放置到符合约束条件的优良子群中；反之，将其放置于不符合约束条件的子群中。

（6）新个体：新个体都应与优良子种群所有个体保持一定距离，这样能保证算法的搜索范围更加广泛。

（7）结束条件：如果算法已满足停止条件，否则重复3、4、5、6。

算法过程：

（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）

否则输出结果，结束程序。

4.实验测试

本文运用Matlab软件中的遗传算法进行地名的测试，在遗传算法中对参数进行预设，初始种群InitialPopulation为60，最大代数为100，变量Numberofvariable为2，运行结果显示，利用遗传算法进行中文地名识别在正确率和精准率都有所提高，并且算法的收敛性比较强。

参考文献

[1]魏勇.一种基于复合特征的中文地名识别方法[J],武汉大学学报,第43卷第1期2018年1月:17-23.

[2]占斌斌.归类识别地名匹配算法[J]，北京测绘，第32卷第4期，2018年4月:484-488.

[3]杜萍.基于本体的中文地名识别[J]，西北师范大学学报(自然科学版),第47卷2011年第6期:87~94.

[4]俞鸿魁.基于层叠隐马尔可夫模型的中文命名实体识别[J],通信学报,第27卷第2期,2006年2月:87~95.

[5]谭红叶.中国地名自动识别系统的设计与实现[J],计算机工程,第28卷第8期:128~130.

[6]李诺.利用地名用字分析的中文地名识别处理[J],计算机工程与应用,2009，45(28):230~232.

[7]汪世义.支持向量机和遗传算法的人脸识别方法[J],计算机工程与应用,2009，45(12):164~166.

[8]杨美妮.不规则文本中商品名称识别的特征选择[J],计算机工程与科学,第38卷第10期2016年10月:2153~2158.

课题：云南省教育科学规划教师教育专项课题，立项编号：GJZ1418