《武汉工程大学学报》 2015年11期
47-51
出版日期：2015-12-30
ISSN:1674-2869
CN:42-1779/TQ
基于条件随机场的中文地址行政区划提取方法
０ 引 言 一直以来，语言是人们交流与传播知识最重要的工具，而理解语言中包含的信息对人类的交流也起到了重要作用. 随着信息技术的发展，能使人与计算机更好的实现人机交互，是人们长期以来追求的目标. 本文研究对地址信息的解析，在过去很多学者也提出过许多方法去提高地址信息解析［１］的正确度. 于２０世纪７０年代，Ｌａｗｒｅｎｃｅ提出的作为一种统计分析的隐马尔科夫模型［２］，存在着一种假设，即假设每个元素之间都是彼此独立的，不管何时观察结果仅仅依赖于此时此刻所处的状态. 而这个模型假设的前提只适合较小规模的数据集［３］，在现实生活中，很多真实语料的观察序列大部分的表现形式是以多重交互特征表现，观察元素间通常有较长的相关性，即不止与前一个状态相关，可能与多个状态以前的状态有关. 在位置信息解析任务中，因为地址信息自身结构具有一定的复杂性，单一的特征函数难以涵盖它的所有特征，这种情况下，隐马尔科夫模型所提出的假设就使得它使用复杂特征时无能为力，此时它在信息解析中的弊端就显现出来了. 而后由Ｊａｙｎｅｓ提出的最大熵模型［４－５］，它记录特征是否出现，并不能了解所需特征的强度，因此在信息的分类中并不是最优的. 其次，采用最大似然方法训练出的最大熵模型，其算法存在较慢的收敛速度，所以就致使最大熵模型的计算量大，而且，有很严重的数据稀疏问题，再次由于最大熵对每个词单独进行分类，难以很充足的利用标记之间的关系. 由Ｐｅａｒｌ提出的贝叶斯模型［６］可以任意使用复杂的相关特征，并且能灵便地对约束条件进行设置，模型在未知参数的适应度、已知数据的拟合度方面就是通过约束条件进行调节的，并且能自然地解决模型中参数平滑问题，但其在决策时很容易延误决策的最佳时间导致影响效果. 本文提出的条件随机场模型［７］，克服了其它几种模型在信息解析上的缺陷，采用链结式结构，结合了最大熵模型和马尔科夫模型的特点，使用概率图模型，在长距离依赖和交叠性特征方面能力较强，能很好的处理最大熵马尔科夫模型［８］具有的标注偏置等问题，而且与最大熵不同的是它能对所有的特征进行全局归一化［９－１１］，从而求得全局最优解.１ 模型描述１．１ 位置信息解析实现步骤位置信息解析具体步骤如图1所示.图１ 信息解析流程图Ｆｉｇ．１ Ｆｌｏｗｃｈａｒｔ ｏｆ ｉｎｆｏｒｍａｔｉｏｎ ａｎａｌｙｓｉｓ（１）收集数据：利用网络爬虫等数据挖掘方式，从互联网上提取大量地理位置信息，例如：…｜省…｜市…｜（区）县…｜镇…｜路…类的地址，之后进行整理，保留至少有一个行政区划名的地址作为研究所需要使用的数据. （２）分析数据：将数据集里的一部分数据分离出作为训练语料，参考条件随机场特殊文本格式进行人工标注以便生成模型，剩下的一部分作测试语料，并人工对其进行标注，以便测试模型性能. （３）构建模型：通过对地址信息的特殊结构进行研究制定特征模板，并与测试语料一起生成条件随机场模型. （４）输出结果：用测试语料检测条件随机场模型，输出ｏｕｔｐｕｔ文件，并将文本格式规范为ｃｒｆ＋＋特殊文本定义的格式，从而为数据比对提供方便. （５）测试数据：查看测试结果，对模型性能进行测评. １．２ 条件随机场描述由于最大熵模型会产生标记偏置问题，无法好好的对信息进行序列标注，针对这个问题，后期提出最大熵马尔科夫模型，是在相邻的变量值之间使用最大熵模型，但这样做会使得得到的结果仅仅是局部的最优解，对整体来说未必是最优的，针对这个问题，提出的条件随机场方法，引出归一化因子，对全局进行归一化，解决了最大熵隐马尔科夫模型存在的不足之处. 条件随机场也是一种判别式模型，所谓判别式模型，学习的是一种条件概率ｐ（ｙ｜ｘ），利用正负例和分类标签，关注在判别模型的边缘分布. 条件随机场是一种无向图性模型，变量Ｘ，Ｙ分别代表的是观察序列、对应联合分布的随机变量，则以Ｘ为条件的无向图模型Ｇ（Ｖ，Ｅ）就是条件随机场. 其中Ｖ表示无向图Ｇ中节点的集合，Ｅ代表节点Ｖ之间的无向边集合. 设Ｇ＝（Ｖ，Ｅ）是一个无向图，Ｙ＝｛Ｙｖ｜ｖ∈Ｖ｝是以无向图中每个随机变量Ｙｖ为节点构成的集合，在给定观察序列的条件下，若是随机变量Ｙｖ都遵循马尔科夫属性，即如公式（１）所示［６］. Ｐ（Ｙv|X,Yu,u≠v）=Ｐ（Ｙv|X,Yu,u~v）（１）那么（Ｘ，Ｙ）就构成一个条件随机场，其中ｕ～ｖ表示ｕ和ｖ是相邻的边. 根据Ｈａｍｍｅｒｓｌｅｙ?鄄Ｃｌｉｆｆｏｒｄ定理得到条件随机场分布用公式（２）表示如下［７］. p(y|x)=■■?追Vc(vc)（２）这里的ｃ为Ｇ中所有的最大势团的集合，?追Ｖｃ（ｖｃ）为势函数（下一节介绍），通常为了方便计算，?追Ｖｃ（ｖｃ）的形式表示在Ｚ的归一化因子中，用式（３）表示. Z=■■?追Vc(vc)（３）条件随机场最常用的模型为线性链结构，如图２所示. 图２ 线性结构条件随机场Ｆｉｇ．２ Cｏｎｄｉｔｉｏｎ rａｎｄｏｍ ｆｉｅｌｄ ｏｆ ｌｉｎｅａｒ ｓｔｒｕｃｔｕｒａｌ condition另外观察序列之间并不一定存在某种联系，它只是一个条件，不存在其它任何假设，所以还可以用图３表示该模型.图３ 模型的另一种表示方法Ｆｉｇ．３ Ａｎｏｔｈｅｒ ｅｘｐｒｅｓｓｉｏｎ ｏｆ ｔｈｅ ｍｏｄｅｌ 该表示方法与线性条件随机场模型的表示方法无异. １．３ 势函数势函数在条件随机场中是针对每个最大势团做出的定义，如图４所示，每个势函数定义如公式（４）［６］. ?追ｃ（ｙｃ）＝ｅｘｐ■?姿ｋ ｆｋ（ｙｃ，ｘｃ）（４）图４ 势函数团示意图Ｆｉｇ．４ Ｓｃｈｅｍａｔｉｃ ｄｉａｇｒａｍ ｏｆ ｐｏｔｅｎｔｉａｌ ｆｕｎｃｔｉｏｎ 在图４中，Ｇ中的所有最大势团已标出，且?追c(yc)是一个在图Ｇ中最大势团上严格的势函数，因此，在观察序列Ｘ的条件下，标记序列Ｙ的形式如公式（５）所示［８］. ｐ（ｙ｜ｘ）＝■ｅｘｐ■■?姿ｋ ｆｋ（ｙｃ，ｘｃ）（５）在线性条件随机场中，Ｇ中最大势团即是相邻的两个随机变量组成的，则公式（４）可以扩写成如下. ?追c（ｙｃ）＝ｅｘｐ■?姿ｋ ｆｋ（ｙi=1，ｙi，ｘ）+■uｋ gｋ（ｙi，ｘ）（6）其中ｆｋ（ｙi=1，ｙi，ｘ）是表示相邻的观察序列的标记位置之间的特征转移函数，而gｋ（ｙi，ｘ）表示当前观察位置的状态特征函数. １．４ 特征模板如果仅仅依靠地理信息本身结构和对字符串的分析，很难取得好的效果. 因此，地理信息中，上下文环境与特征词对提高地理信息的识别效果有比较明显的作用. 而条件随机场有个非常明显的优点，即它可以很轻松的将观察序列里面的特征加入到模型中，表达长距离上下文的依赖关系. 上下文环境，是指包括当前词ｖ０在内，以及其前后几个词组成的一个“观察窗口”（ｖ－ｎ，ｖ－（ｎ－１），…ｖ０，…，ｖｎ－１，ｖｎ）. 从理论上看，窗口越大，前后词关联越多，可依赖的信息就越多，但窗口过大又会导致效率降低，窗口过小又会导致不能充分利用特征，从而丢失掉一些重要信息. 所以，根据大量数据分析，一般选取的窗口大小为２，即（ｖ－２，ｖ－１，ｖ０，ｖ１，ｖ２）. 在选取使用地址位置的特征时，考虑到地址都有很明显的行政区划特征词例如省、市、区、县等，所以可以将该特征应用到特征模板中，如表１所示. 表1 特征模板的选取Table 1 Selection of feature template以上的各个特征模板要有四个位置偏移，即－２、－１、１、２. 而当特征函数取得特定值，特征模板就会变成一个实例，便会有具体特征出现. 比如当前词后面第二个词ｖ２出现在地址特征词表，可表示为：ｆｉ（ｘ，ｙ）＝0 else1 if feature(v2)=1 & y=location（７）２ 性能评估对于一般的分词算法研究，大多数都是以Ｂ、Ｉ、Ｅ、Ｏ做标注，即以一个词的开始、中间、结束来标记，没有很明显的在标注中加入词性特征，这使在建立模型时，不能很好的利用所研究领域的一些特殊结构与特征来进行更加精准的信息区分，利用条件随机场进行信息的解析，在标注语料时，同时结合地理领域的词结构进行标注，如表２所示. 表2 训练语料标注示例Table 2 Training corpus tagging examples 选取省、市、县、区等行政区划关键词作为特征词，给每个特征词一个特殊的标记，并结合Ｂ、Ｍ、Ｅ作为标注语料的标记，实验表明，加入特征词标记语料之后，利用语义解析去标注，比纯粹的开始、结束标记的正确率增加５％左右. 条件随机场对信息结果好坏的评估，将与最大熵模型和隐马尔科夫模型作比较，比较性能的指标有如下几个方面：正确率=■×100%召回率=■×100% Ｆ=■３ 实验结果及分析３．１ 定性分析在标注语料时，有一些特殊的语句存在歧义，导致标注时模糊不清从而使得正确率下降，影响地址解析的效果. 在输出ｏｕｔｐｕｔ文件中，有如表３所示例子. 表3 输出示例Table 3 Sample output 从表３可以看到，在测试时，由于训练语料中有些市区的名字带有“嘉”，再通过与模板结合，所以将嘉定区中的“嘉”作为了市级的地名，从而使地址识别出现一些错误. 此时，通过最大移动窗口匹配算法，对于一些不确定的地名进行消歧处理. 移动窗口匹配算法，即首先准备行政区划表，将地址与行政区划表对应进行匹配，得到准确的行政区划信息，实验表明，加入了该算法后，对歧义的消除起到了一定的作用，比对的正确率提升了４％左右. 当然对于最大移动窗口匹配算法只能进行部分消歧，并不能消除所有歧义，对于未消除歧义里的词，将在后续进行研究. ３．2 定量分析通过分析地址解析的各种算法，将最大熵分词算法与本文算法相比较，由于最大熵算法知识表达能力较强，具有易于理解、简单、可重用性等优点，被广泛用于分词研究中，但其也具有耗资源、速度训练慢等缺点. 本文算法虽然全局归一化代价高，训练工作量大，但其能将各个新特征进行融合，能兼顾长距离表达，灵活性好，且分词精度高. 选取２千条地址进行解析，两者对比结果如表4所示：表4 结果对比 Table 4 Comparison of results (%)４ 结 语信息解析一直为各个领域研究的热点，本文研究地理领域的信息解析，采用条件随机场的方法，在已知观测序列的条件下学习，从而对目标数据建模，通过学习训练数据并与特征模板结合，得到能解析地址数据的模型，解决了最大熵模型遗留的标注偏置问题，以及最大熵马尔科夫模型的局部优化问题. 它能表达长距离依赖性和交叠性，以序列化形式对全局的参数进行优化. 人工标注训练语料，并利用条件随机场工具ｃｒｆ＋＋进行语料训练，该模型的信息解析总的性能指标比其它模型优异，取得较满意的结果. 致 谢感谢武汉工程大学研究生处的资助！