APP下载

基于统计的中文地址位置语义解析方法研究

2017-11-02谢婷婷严柯

软件导刊 2017年10期
关键词:互信息字符串词频

谢婷婷 严柯

摘要:为获取中文自然地址描述语句中的位置信息,提出一种不依赖于词典的中文地址分词方法。首先根据地址语料库中字串共现的统计规律统计词频,然后对地名地址串进行正则表达式预处理,再对地址串进行全切分处理。通过互信息和信息熵得到最优粗分结果,通过置信度对粗分结果进行过滤得到最优分词结果。实验结果表明,该方法在不依赖词典的情况下能有效实现对地名地址串的拆分,正确率和召回率分别达到了80.03%和89.28%。

关键词:中文分词;地名地址分词;互信息;信息熵

DOIDOI:10.11907/rjdk.172069

中图分类号:TP301文献标识码:A文章编号:16727800(2017)010001903

0引言

互联网是信息传播交流的重要平台。网络空间中存在海量的中文地址数据,蕴含着丰富的空间信息。但是与传统的地理信息或数据相比,文本中的地理信息是非结构化的,只有在形式化处理后才能进行分析和挖掘。文本中的空间信息形式包括中文地址分词、空间关系提取、事件提取等。地名地址分词作为空间信息形式化最基础的工作,其准确性将直接影响到后续工作的有效性和准确性。地名地址分词是中文分词在地名地址中的应用,它将地名地址串拆分成若干地理要素[1]。中文分词算法大体分为3类:基于词库的分词算法、基于统计的分词算法、基于理解的分词算法[2]。基于词库的方法将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配,若在词典中找到某个字符串则匹配成功。这类方法简单、分词效率较高。但汉语语言现象复杂丰富,词典的完备性、规则的一致性等问题使其难以适应开放的大规模文本分词处理。基于统计的方法将相邻字间的信息、词频及相应的共现信息等应用于分词。由于这些信息是通过真实语料取得的,因而基于统计的分词方法具有较好的实用性。基于理解的方法是试图通过计算机模拟人对文字的理解过程来进行分词,但目前尚不成熟,实际应用中无法直接使用该算法。

中文地址解析方面,文献[3]首先创建一个符合地址分级模型的地名库,并在此基础上通过地址串的拆分和匹配完成地址标准化编码工作,这种方法的困难在于需要人工维护基础地址库。文献[4]在中文地址编码研究中采用分段、组合、优先规则,对中文地址进行分段匹配。这些规则在一定程度上减少了地址要素的匹配次数,但由于采用数据库查询方式,使算法总体匹配速率不佳。文献[5]应用自然语言处理中的中文分词和语义推理原理(HMM模型)对非结构化中文地址进行处理,该方法缺点是依赖于训练语料,前期需要进行大量的地址训练操作。

由于我国地址名称多而杂乱,而且地址名称不断在更新,人工构建一个标准的涵盖各级地址的工作量非常大。因此,本文针对地名地址串,提出一种基于统计的中文地址分词方法:首先统计语料库词频,然后对地名地址串进行正则表达式预处理,再对地址串进行全切分处理,通过互信息和信息熵得到最优粗分结果,最后通过置信度对粗分结果进行过滤,得到最优结果。该方法地址识别率高,对原始地址结构和部分地址元素缺失不敏感,不需要人工构建一个海量地址库。

1基于统计的中文地址解析方法

本文提出了基于无词典的中文地址分词方法。首先对互联网上爬取的30万条地址数据构成的语料库词频、相邻词语之间的互信息、词语的信息熵进行统计,然后对地名地址串进行正则表达式预处理,提取出“数字+号”这类描述方式以及一些标点符号;再对剩下的地址串进行全切分处理,得到所有的分词方案,然后通过互信息和信息熵计算选择弧度花费最小的分词方案;最后通过置信度对该分词方案进行过滤得到最优结果。步骤如图1所示。

1.1统计词频

词是最小的能够独立活动的有意义的语言成分[6],是相邻的字与字构成的稳定组合。在语料库中,相邻的字同时出现的频率越高,就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好地反映成词的可信度。本文对互联网上爬取的30多万条地址文本进行统计处理。在没有地名词典的情况下,任意长度的字串都有可能构成一个地理要素。一个最长的地理要素長度为8(如新疆维吾尔自治区),所以将字符串的最大长度设为8,统计语料库中任意长度(最大为8)字符串的词频。在地名地址串比如“武汉市洪山区珞瑜路312号”中,312在计算机中是3个字符,而在人们认知的地址数据中312是一个整体,所以在预处理时将连续的数字认定为一个字符。哈希查找方法是效率较高的查询算法,因此将统计好的词频采用哈希结构存储。

1.2构造切分词图

给定一个中文地址字符串S,对S进行全切分处理,那么就有2l-1种切分方法。其中,l是地址字符串S的长度,S的全切分集合为W={Wi},1≤i≤2l-1,Wi代表一种切分方法。把切分的字符串当作节点,把字符串的切分位置当作弧段,就可以将地址语句的全切分集合表示为图,称为地址语句的切分词图。

1.3设定弧段花费

中文信息处理中,统计方法主要应用于自动抽词或未登录词识别,比如串频、互信息、信息熵、检验值、相关度等统计量可用于定量判断候选词的边界[7],其中最常用的是互信息和信息熵。

互信息度量两个对象之间的相互性。互信息通常用来衡量两个信号的相互依赖程度,并可用来衡量词语的内部结合紧密程度。互信息越大,说明词语的内部结合紧密度越大,它们构成词语的可能性越大。互信息越小,构成词语的可能性越小。其计算公式为:

MI(x,y)=log2p(x,y)p(x)p(y)(1)

其中:p(xy)是字符串xy在语料库中邻接出现的概率,p(x)是x在语料库出现的概率;p(y)是y在语料库中出现的概率。当MI(x,y)大于一定阈值时,表明字符串xy是一个词;当MI(x,y)小于一定阈值时,字符串xy不会结合成词。

信息熵是用来衡量一个随机变量出现的期望值,一个变量的信息熵越大,它出现的各种情况就越多,不确定性就越大,正确估计其值的可能性也越小。字符串左右搭配越丰富,选择越多。在自然语言处理中,分别利用左信息熵和右信息熵来判断字符串的边界。一个字符串的左信息熵指该字符串与它相邻的左邻接字串集合的信息熵之和,用来表示该字符串的左邻接字的不确定性。左信息熵越大,说明该字符串的左邻接字越不确定,该字符串成为某一个词语左边界的可能性越大。相反,左信息熵越小,该字符串的左邻接字越确定,它成为某一个词语左边界的可能性就越小。同理,右信息熵可以确定词语的右边界。endprint

EL(w)=-∑a∈AP(aww)log2P(aww)(2)

ER(w)=-∑b∈BP(wbw)log2p(wbw)(3)

上式中,w表示该字符串,aw表示该字符串和左邻接字的组合形式,wb表示该字符串和右邻接字的组合形式。

本文根据互信息和信息熵原理将其转化为切分词图中弧段的开销。一条弧段相邻字符串之间的互信息越大,越不适合作为词的边界,弧段开销越大;其连接左右字串的信息熵越大,越适合作为词的边界,该弧段开销越小。因此,可以定义如下弧段花费计算公式:

c(A,B)=MI(a,b)ER(A)EL(B)(4)

A、B表示弧段连接的左右字串,a、b表示左字串最右侧的字和右字串最左侧的字。

1.4置信度过滤

在地址语句中,由于地理要素存在层级关系,上述计算方式容易产生数据稀疏问题,不能将两个地理要素切分开,因此引入置信度过滤的计算方法。

已知字符串w1为fre(w1),字符串w2的词频为fre(w2),字符串w=w1+w2的词频为fre(w),则字符串w1相对于字符串w,词的置信度如公式(5)所示。

conf(w1w)=fre(w1)-fre(w)fre(w1)(5)

同样可知字符串w2相对于字符串w的置信度。

字符串w1相对于字符串w的置信度,反映了字符串与前缀汉字串或后缀汉字串结合的稳定性,即字符串w2构成词条的可能性。如果字符串w1相对于字符串w的置信度小于阈值α,则认为字符串w是真实字符串的可能性比w1大,则从词频生成的词库中去掉w1字符串。如果字符串w1相对于字符串w的置信度大于阈值β,则认为字符串w1是真实字符串的可能性比w大,从词频生成的词库中去掉w字符串。如果字符串w1相对于字符串w的置信度大于阈值α且小于阈值β,则比较两个词的词频大小,保留词频大的字符串。

通过分析不同取值条件下的实验结果选取α和β的阈值。一般在α=0.3和β=0.8的情况下分词结果更好。

比如w1=“武汉”,w=“武汉市”,fre(w1)=7 096,fre(w)=7 086,则conf(w1w)=(7 096-7 086)/7 096=0.001 9,小于阈值α=0.3,所以从词频生成的词库中去掉“武汉”字符串,保留字符串“武汉市”。

再比如w1=“武汉市”,w=“武汉市武”,fre(w1)=7 082,fre(w)=1 110,则conf(w1w)=(7 083-1 110)/7 082=0.84>β=0.8。所以,应从统计语料库的词频生成词库中去掉“武汉市武”字符串,保留“武汉市”字符串。

2实验结果分析

实验采用完全基于统计特征的分词方法和引入了置信度过滤的分词方法。前者基于统计考虑,说明了统计分词方法的有效性,后者通过引入置信度过滤改进了统计分词效果。从互联网上爬取30万条地址数据构成的语料库中,随机选取2 000条地址语句,采用上述两种方法进行分词实验,统计两种分词方法的正确率、召回率和F值,各指标计算如公式(6)~(8)所示。

通过分析地址解析方法,将最大熵分词方法与本文方法对比。本文方法虽然在正确率上没有前者高,但是在召回率和F值上有了较大提升。而且最大熵方法在前期需要人工标注大量的语料,工作量大,本文方法则不需要标注,实用性更强。两者对比结果如表1所示。

正确率(P)=切分正确的总词数切分出的总词数×100%(6)

召回率(R)=切分正确的总词数标准结果中的总词数×100%(7)

F=2×P×RP+R×100%(8)

3结语

本文提出了一种无词典的中文地址分词方法。在互联网上爬取30多万条地址数据构成语料库,通过统计地址文本中各个字的组合频度,计算待分词文本的各种参数,判断汉字之间的紧密程度,通过置信度过滤最后获得分词结果。实验结果表明,本文方法不需要依靠人工去构建一个地名地址库,且不需要人工去标注训练语料就能实现对地名地址串的切分,且分词效果较好,实用性強。

参考文献参考文献:

[1]赵阳阳,王亮,仇阿根.地址要素识别机制的地名地址分词算法[J].测绘科学,2013,38(5):8183.

[2]于光.中文分词系统的设计与实现[D].成都:电子科技大学,2012.

[3]孙存群,周顺平,杨林.基于分级地名库的中文地理编码[J].计算机应用,2010(7):19531958

[4]唐静.城市地名地址的编码匹配研究[D].昆明:昆明理工大学,2011.

[5]宋子辉.自然语言理解的中文地址匹配算法[J].遥感学报,2013,17(4):788801.

[6]徐飞,孙劲光.中文分词切分技术研究[J].计算机工程与科学,2008,30(5):126128.

[7]李文坤,张仰森,陈若愚.基于词内部结合度和边界自由度的新词发现[J].计算机应用研究,2015,32(8):23022342.

责任编辑(责任编辑:杜能钢)endprint

猜你喜欢

互信息字符串词频
基于词频分析法的社区公园归属感营建要素研究
基于互信息的贝叶斯网络结构学习
联合互信息水下目标特征选择算法
词频,一部隐秘的历史
改进的互信息最小化非线性盲源分离算法
基于增量式互信息的图像快速匹配方法
云存储中支持词频和用户喜好的密文模糊检索
以关键词词频法透视《大学图书馆学报》学术研究特色
一种新的基于对称性的字符串相似性处理算法
依据字符串匹配的中文分词模型研究