基于相似度模型的可融合兴趣点分类研究

张 巍，李瑞姗，高新院

（中国海洋大学信息科学与工程学院，山东 青岛266100）

POI（Point of Interest）即兴趣点，泛指一切可以抽象为点的地理对象，尤其是与人们生活紧密相关的地理实体，如政府部门、景点、学校、医院、银行、商业区、标志性建筑等。每个POI包含这个实体4个方面的信息：名称、地址、类型、经纬度，同时还可能有电话、评价等信息［1］。最近几年，由于基于位置的服务快速发展，尤其是对网络电子地图、移动位置服务（LBS）、便携式自动导航（PND）的使用，使得原有的POI很难继续支撑这类服务。能否获取高质量的POI信息，成为提高此类服务质量的关键所在。

然而多数基于位置服务的提供商并没有自己完整、有效的数据采集和维护机制，他们的数据仍然是由专门的数据提供商供给。大多数POI信息数据生产厂家的数据采集方式主要依靠人海战术，雇用大量的调绘、调查人员，对城市进行地毯式作业［2］。这样的作业方式效率低，成本高，并且无法及时更新，因此部分厂家根据自己的经验，创造性地将数据采集工作转移到了室内。文献［2］运用基于GPS技术与实景影像相结合开发建立POI快速采集系统平台，可实现POI的快速采集和更新；专业POI生产厂商卡贝斯对互联网数据做了实时监测，分类抓取互联网上同POI相关的信息。大多远程采集机制可以充分把握住新出现的POI信息，但忽略了那些原有POI信息变化，使得数据的准确度降低。以餐饮业为例，餐馆的节假日活动可能会频繁的变化，按照卡贝斯的机制这部分信息就不能在POI中被更新，甚至当餐馆因为迁址导致地址这一关键字段发生的变化时，POI也不会被更新，造成这个POI价值骤减。还有些餐馆因经营不善而关门倒闭，但是它的POI信息仍然出现在数据库里，成为无用的“死点”，久而久之便会出现大量的冗余。

本文使用机器学习领域中的分类方法［3－4］初步解决了以上POI数据冗余、精确度低的问题。在互联网上抽取数据，筛选出POI中字段的信息，根据这些信息与原有POI的关系进行分类处理。

本文通过分析POI中各特征字段的形式、特点，提出了POI特征相似度［5］用以表示一个POI与原有POI集的关系，利用这种形式化的关系在机器学习方法中分类，最终区分出可融合与不可融合的POI。相似度的形式化表示主要由名称、地理信息相似度两部分组成，其中的地理信息包括POI中的地址和经纬度。名称部分是指2个不同POI名称字段间的相似度，通过几种经典字符串匹配方法［6］计算得出，过程中考虑到因为词语的存在使得不同汉字具有不同的关联性，本文假设中文字符串匹配的最小单位是词，打破了传统中最小单位是单个汉字的假设。美国是地理编码［7］应用最早、最广泛的国家，早在1970年代就建立了全国的地理编码标准，根据经纬度便可确定出一个唯一的英文地址，其地址匹配可达到较好的效果，因此很容易就可以得到地理位置信息相似程度的准确的结果。但是我国尚且没有成熟的地理编码，既不完整也不精确，利用经纬度并不能确定2个地址匹配、相似与否。对于地理位置信息的相似程度，国内主要根据地址信息计算［8］，过程中对地址中各特征字段进行匹配，综合各字段的情况得出地址相似度。本文在考虑地址相似度的同时，还结合了根据地理空间信息得出的不同POI之间的距离，弥补了同一POI具有多种中文地址描述所导致的问题。

1 字符串匹配方法

POI中名称字段大多比较精短、无明显规则，同时也缺乏语义上的特征，是一类普通的中文字符串。目前这种中文字符串相似度［9］的计算在中文信息检索、中文文本校对等领域中已有广泛的应用。衡量2个字符串的相似度，常用的方法有3种，即莱文史特距离算法、Jaccard相似方法和Jaro距离算法。

根据已有资料的分析，现有的这些计算字符串相似度的算法大多基于一个假设：中文字符串匹配的最小单位是单个汉字，这样并没有考虑到汉字中词语对相似度的影响，所以将匹配的最小单位假设为词。

1.1 莱文史特距离算法

莱文史特距离算法（Levenstein edit distance algorithm）是一种字符串编辑距离算法，指一个字符串通过多少次操作（增、删、改）得到另外一个字符串。例如，字符串S1为“aaabc”，S2为“aabb”，S1通过‘a’变为‘b’，删除‘c’两步可以得到S2，所以编辑距离等于2。在这里，定义字符串相似度为：

其中：distance是S1、S2的编辑距离，maxLen是S1、S2字符串长度中较大的那个值。edit值越大说明相似度越大，0表示没有任何相似度，1则代表完全匹配。

1.2 Jaccard相似方法

这个相似度等于两个字符串中相同词（无重复）的个数与所有词（无重复）个数的比值。也就是说，2个字符串S1、S2的Jaccard相似度可定义为：

和edit一样，jacc越大说明相似度越大。

1.3 Jaro距离

与上边2种算法相比，Jaro distance算法的优点在于其考虑到字符不同位置的问题，如“粥全粥到台东三路店”和“粥全粥到三店”，其中的“三”根据位置的不同可判断为不匹配。首先定义一匹配窗口：

其中：S1、S2是待匹配字符串。S1、S2匹配过程中，若两者中同有字符x，并且这2个x的距离不大于MW ，此时可以认为这2个x是匹配字符。

Jaro相似度定义如下：

其中：S1、S2是待匹配的2个字符串；m是匹配的字符数；t是换位的数目，其值等于不同顺序的匹配字符数目的一半。比如：2个字符串“ABCDE”和“EBCDA”做匹配操作，字符串中仅有B、C、D3个字符是匹配的，即m＝3。虽然A、E都出现在2个字符串中，但是通过公式得出匹配窗口MW 为。而2个字符串中A、E字符的距离均大于1.5，所以不算作匹配。在另一组字符串AxByCDz与AzBDC。匹配的字符为A～B～C～D，但在2个字符串中C～D 2个字符顺序不同，因此t＝1，m＝4。

2 地理信息的相似度

地理信息主要包括2部分，即空间地理信息和非空间地理信息。POI中的经纬度就是一种典型的空间地理信息，而POI中的中文地址则属于地理信息系统中的非空间信息。我国地理信息的相似度主要是根据中文地址的匹配程度得出，但是对于那些具有多种描述情况的地理实体，比如有别名的实体、处于2条路交叉口的实体，这种地址匹配方法就不能得出其真实的相似程度。为解决这个问题，本文借助空间地理信息对这个相似度进行了补充。

2.1 中文地址的相似度

地址是各类服务系统中运用自然语言描述空间位置的最常用手段。中文地址是一种具有一定格式的中文字符串，但又不是标准统一格式，对于其相似度的计算，单靠本文提到的中文字符串匹配方法并不能达到很好的效果。目前我国主流的地址匹配方法就是对地址分词，利用各个地址要素进行匹配。本文基于小词典和特证词对中文地址进行分词，成功分开了中文地址中的各个要素，然后根据设置好的规则，综合所有要素给出其相似程度。

分词过程中用到的小词典是根据行政区划表构造出来的，主要目的是规范地址中省、地、县、乡级行政区名称，如“崂山区松岭路238号”，分词结果为“山东（省）青岛（市）崂山（区）松岭（路）238（号）”，不仅划分出字符串中各个部分，其省略部分也会补充完整。地址字符串中除省、地、县、乡级行政区以外的其它部分，因为信量太大，严重影响分词速度，况且现在没有合适完整资料来源，所以只对其进行特征字分词。得到最终分词结果格式为“X（省）X（地）X（县）X（乡）X（路）X（号）X（建筑）X（号码）X（其它）”，括号内是其对应地址要素的特征词。

对待匹配的2个中文地址，分词处理后对其进行相似度计算，因为分词过程中对乡级及以上行政区字段进行了规范和补充，所以该4级字段中低级字段若相等，较高级字段也一定匹配。对于其它5个字段，先分别计算出相似度，再根据不同权值合算出总的相似度。如果2个中文地址中对应字段不同时存在，就无法进行相似度计算，对于这种情况把相似度计为－1，表示不考虑该字段。若SIM1、SIM2、SIM 分别表示中地址前4个字段、后5个字段以及整体的相似度，计算的具体流程如下：

Step1 初始化SIM1、SIM2、SIM 都为－1。

Step2 若乡级字段匹配，对SIM1赋值为1，转向Step3；若不匹配，则匹配县级字段，县级若相等SIM1为0.8，转向Step3；以同样方法处理地级、省级字段，SIM1分别为0.4、0.3；省级字段也不匹配，SIM1仍为－1。

Step3 若路级字段对应可比，且2个字段字符串相似度t大于0.8，则将路级、号级字符串的相似度记为s1，t小于0.8时s1等于t的一半；路级字段不可比时，s1等于－1。

Step4 和路级、号级字段一样，计算出建筑级、号码级字段相似度记为s2。

Step5 根据2.2.1中提到的一般字符串相似度算法，计算其它字段的相似度记为s3。

Step6 设置决定SIM2各字段的权值，s1、s2、s3分别对应a1、a2、a3，其值分别为4、3、3；若s1、s2、s3值为－1，表示对应字段不可比，则使这个权值为0。后5个字段的相似度为：

其中：s1、s2、s3都等于－1时，SIM2为－1；

Step7 设置SIM1、SIM2字段的权值b1、b2分别为1、3；若SIM1、SIM2值为－1，则使其对应的权值置0。待匹配2个中文地址的相似度为：

如果SIM1、SIM2值都为－1，SIM 的值定为0。

2.2 空间地理信息相似度

经纬度被定义在三度空间的球面上，用来标示地球上的任何一个位置，是一种典型的空间地理信息。POI中的经纬度作用和地址字段相同，都是用来描述一个位置，只是形式不同。通过经纬度来衡量2个POI是否匹配相似，最简单有效的方法就是计算这2点之间的球面距离。该地理坐标相似度［10］定义为：

其中：distance（p1，p2）是匹配的2个POI点p1、p2的球面距离。当LLsim这个相似度大于阀值时，就认为这2个POI相似匹配。

3 POI相似度及机器学习分类模型

3.1 POI相似度

在互联网上抓取感兴趣的网页，筛选出其中与POI相关的字段信息，之后对其进行分类处理，本文将POI分为可融合和不可融合两类。分类的依据则是这个POI信息与数据库中现有POI集的关系这个现有POI集并不是数据库中所有的数据，这个集合是通过在互联网上抽取的POI的名称字段在数据库中模糊搜索的结果。

为了方便构建模型，本文将之前提到的待分类POI与现有POI集的关系转换成为1个向量，该向量中包括这个待分类POI和现有POI集中的各特征字段相似度的最大值，即

其中：p是待分类POI；px是现有POI集合中的某个可以不同，但必须使得其所在的函数值在组内最大分 别表示公式（1）、（2）、（4）提到的2个POI名称字段 Levenstein相似度、Jaccard相似度、Jaro相似度，表示的2个POI的非空间地理信息相似度表示的2个POI的空间地理信息相似度。

图1 机器学习分类模型的训练、分类过程Fig.1 Training and classifying process of machine learning model

3.2 机器学习分类模型

通过大量数据转换得到的向量集，进行特征提取后将作为训练集，依据机器学习的方法构建出分类模型，将待分类的POI实例分为可融合和不可融合两类。具体过程如图1所示。可融合是指该POI信息已经存在，只需对这些信息进行融合，对部分字段进行更新处理；不可融合则是指该POI信息不在现有数据集中，可能是新出现的POI信息，也可能是错误不真实的POI。对这些不可融合信息真伪性的验证，可以像卡贝斯那样通过电话情景脚本的方式实现，也可以运用自然语言处理相关技术实现。对于验证为正确、真实存在的POI，对其进行融合后便可做为一有效信息添加到数据集中。而对那些验证为错误、甚至不存在的POI不作任何处理，是对原有数据集中那些与之相似的POI要经过验证，最终去除其中的“死点”。

在实验中，运用了几个不同的分类器，其中包括贝叶斯分类器、C4.5分类器、Adaboost提升分类器。每个分类器都有各式各样、复杂的标准，利用这些标准构造不同的模型。比如，C4.5采用信息增益比作为选择测试属性的标准，从根节点开始，赋予最好的属性，在将该属性各种取值都生成相应的分支，在每个分支上又生成新的节点，加之一些剪枝方法构造出决策树，使其最大程度地拟合训练集。C4.5产生的分类规则易于理解，准确率较高，但是在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序就无法运行了。

4 实验数据及结果

4.1 数据集

实验中，本文从美团团购网上抽取了1 095个页面，每个页面上有1个POI信息，即之前提到的待分类POI，随后在google地图、mapabc、baidu地图上按照待分类POI中的名称字段进行模糊搜索，将搜索结果集作为现有POI集合。本文对于这些数据进行了人工标注，根据现有POI集合判断其对应的待分类POI是否可被融合，标注结果中744个POI是可融合的，238个是不可融合，其余113个POI模糊搜索没有结果，本文不予以考虑。将以上可融合的和不可融合的（共982个）POI转换成向量集，作为本实验的数据集。

表1 结果关系表Table1The relation of classification result

4.2 测评指标

本节将分析模型分类结果和人工标注结果是否一致，为评测模型的分类效果实验中用到了3个重要指标，即召回率（Recall）、准确率（Precision）和F值。人工标注结果与模型分类结果关系表示（见表1）。

可融合的召回率r1是指模型分类与人工标注结果均为可融合的POI数目占人工标注中可融合总数的百分比，反映分类模型的完备性；可融合的准确率p1是指模型分类与人工标注结果均为可融合的POI数目占模型分类结果中可融合总数的百分比，可反映分类模型的准确程度。可融合的召回率r1可表示为同样不可融合的召回率r0可表示为不可融合的准确率整个分类的准确率p则可表示为F值是召回率和准确率这2个指标的综合值，定义如下：

式中：P为准确率；R为召回率；β为召回率和准确率相对权重，一般取1；因此F值可以表示为：

4.3 基于规则的分类结果

本文首先分别对POI中的各特征字段的相似度进行线性回归，通过设置不同的阀值进行分类，得到每个特征相似度单独参与分类的表现（见图2）：

图中f1是可融合的F值，f0是不可融合的F值，p为整个分类结果的准确率。从3个图中可以看出，无论是哪个字段，p和f1的变化趋势是一样的，且f1总是处于最上方，f0总是处于最下方。因为可融合的POI占大部分，所以f1会更大程度地影响整体分类结果。图中的峰值并不是说此时的p1或r1是最大值，而是说p1和r1处在一个最佳的平衡点，不至于2个值一个过太一个过小。对于p0、r0也是一样。在图2（a）中，p和f1在［0.85，1］区间内逐渐减小，对应的f0不断增大，但最大值仍旧很小，此时所有POI分类的结果为可融合。在图2（b）中，3个曲线同增减，并在0.36处出现峰值。图2（c）中的3条线变化趋势也相同，且在0.001处出现峰值，同样是这种情况下的平衡点。具体结果（见表2）。

从上述结果分析可知，POI中各字段在区分可融合、不可融合分类过程的表现不同，其分类效果由弱到强分别是名称、经纬度、地址字段。名称字段之所以比较差，主要因为现有POI集中的POI是根据待分类POI的名称进行模糊搜索得到的，它们的名称相似度已经很高，不足以有效区分POI。其中对地址和经纬度字段进行了融合，其结果表现的最佳。

图2 POI不同字段的分类结果Fig.2 Classification results for different POI attributes

4.4 基于机器学习方法的分类结果

在实验中，本文运用了朴素贝叶斯、C4.5、Adaboost 3种分类器对数据集进行了训练、测试，因为数据有限，所以在这里采用了十折交叉验证的方法。分类结果（见表3）中可看出，各分类器效果差不多，对可融合的POI分类较好，但对不可融合部分各指标还是偏低。总体来说，C4.5效果较好，适合应用在这个分类中。

表2 根据不同字段分类的最佳阀值及结果Table 2 The optimal threshold and result

表3 不同分类器的分类结果Table 3 Classification result for different classifier

5 结语

本文分别定义了POI各个特征字段的相似度，根据这些相似度构造出POI相似模型，并对网络上抽取的POI数据进行有效分类。最后实验结果准确率可达到90%左右，验证了根据相似度构建模型的正确性和可行性。同时还说明对POI各字段进行适当的融合，对其分类可以起到一定的积极作用。

对于这些分类为可融合的POI，除名称、地址、经纬度外的其它部分不具有统一的数据结构，并且还存在大量的冗余信息，仍然不能不能直接应用于位置服务中。下一步还需要研究改进POI的融合模型，得更有价值的融合结果。

［1］ Krosche J，Boll S.The xPOI Concept［C］.／／Location and Context Awareness，Oberpfaffenhofen：Germang Springer，2005：113－119.

［2］ 王海波.基于GPS与实景影像的POI快速采集技术 ［J］.中国科技信息，2007（12）：121－122.

［3］ Tom M，Mitchell.Machine Learning［M］.曾华军，译.北京：机械工业出版社，2005：38－56，112－135.

［4］ Ryszard S.Michalshi，Ivan Bratko.Machine Learning and Data Mining：Methods and Applications［M］.朱明，译.北京：电子工业出版社，2004：67－94，114－117.

［5］ Vivek S.Entity Resolution in Geospatial Data Integration ［J］.ACM－GIS，2006，11：10－11.

［6］ 牛永洁，张成.多种字符串相似度算法的比较研究 ［J］.计算机与数字工程，2012，3：14－17.

［7］ 江洲，李琦.地理编码（Geocoding）的应用研究 ［J］.地理与地理信息科学，2003（3）：22－25.

［8］ 孙亚夫，陈文斌.基于分词的地址匹配技术 ［C］.／／中国地理信息系统协会第四次会员代表大会暨第十一届年会论文集.北京：科学出版社，2007：114－125.

［9］ 宋玲，徐白.中文检索系统的相似匹配技术研究和实现 ［J］.计算机科学 A辑，2010，37（12）：46－48.

［10］ Beeri C，Kanza Y，Safra E.Object Fusion in Geographic Information System ［C］.Toronto：Proceeding of the 30th VLDB Conference，2004：816－827.