基于距离类别的多源兴趣点融合算法

徐 爽，张 谦，李 琰，刘嘉勇*

(1．四川大学电子信息学院，成都610042; 2．中国电子科技集团第二十九研究所，成都610036)

(*通信作者电子邮箱ljy@scu．edu．cn)

0 引言

兴趣点(Point of Interest，POI)是一种代表真实地理实体的点状数据，通常包含多种信息:名称、类别、经纬度等，它可以代表人们感兴趣的地理实体，如商店、景点等。近年来基于位置的社交网络(Location-Based Social Network，LBSN)，如Foursquare、Gowalla、Facebook Places 等 发展迅 速［1］，基 于LBSN的 POI应用的需求和POI数据的规模不断增加［2－3］。来源于不同网站的POI信息存在位置信息、地址描述及分类属性等方面的不一致，如何实现多源POI的有效集成和深度融合，成为空间信息技术面临的一大挑战［4］。

国内外对POI融合方法提出了三种方案:基于空间位置的方法［4－6］、基于非空间属性的方法［7－9］和基于本体的方法［10］。基于空间位置的方法是一种较为简单实用的方法，仅仅根据经纬度位置信息就可以找到对应对象，但来源不同的POI数据的经纬度都普遍存在误差与坐标系不统一的问题;基于非空间属性方法是仅利用非空间属性信息相似度来寻找融合集，该方法不需要考虑经纬度误差，但要求不同来源的POI之间必须有比较统一的存储模式而且非空间特征属性有可能存在信息缺失与标注错误问题;基于本体的方法可以为每个POI对象创建一个类似结构化数据的全局标识符，从而使融合过程变得非常容易，但目前并没有比较成熟的本体库可以使用，因此不考虑基于本体的方法。

单独使用以上方法都不能取得令人满意的结果，文献［11－12］提出了一种空间位置和非空间属性相结合的方法。该算法准确率和召回率优于单独使用空间和非空间算法。但该算法的空间算法只使用经纬度属性，非空间算法只使用名称特征属性，融合结果的质量还有提升空间。

为了解决POI融合问题，提高融合结果质量，本文提出了一种基于距离和类别约束的POI融合算法。首先通过空间算法初步筛选出融合集;然后利用非空间算法对融合集中类别一致的对象使用低阈值排除，对类别不一致的使用高阈值排除;最后使用距离约束，类别一致约束和非空间算法高阈值找出空间算法遗漏的可融合对象。经实验验证，本文算法的准确率、召回率等各项指标较之文献［11］有明显的提升。

1 POI融合基本方法

定义1 数据融合。通过对多个数据源里的信息进行校正与整合，得到一个全面的信息，这个信息比任何一个单一数据源提供的信息都多［13］。

定义2 可融合POI对象。假设有两个待融合的POI数据集合分别为 A={a1，a2，…，an} 和 B={b1，b2，…，bn}。记ab∈A，ba∈B。如果ab和ba实际上是一个POI地理实体，就是可融合POI对象。

定义3 POI融合。来源不同的POI数据通过POI融合技术生成信息量更为丰富与完整的 POI数据，从而实现了POI信息的复用与更新，这样就可以节约大量的人力、物力，进而降低 POI数据更新成本［13］。

1．1 空间属性算法

空间属性算法是仅利用POI的空间位置信息来寻找可融合POI对象的算法。

最简单的空间属性算法是通过经纬度计算两个POI之间的球面空间距离，距离越小，两点可融合可能性越大。假设点P1的经纬度为(Lon1，Lat1)，P2的经纬度为(Lon2，Lat2)，R为地球的平均半径，根据三角推导可以得到P1和P2之间球面距离的计算公式［14］:

其中:C = sin(Lat1)*sin(Lat2)*cos(Lon1－Lon2) +cos(Lat1)*cos(Lat2)，设地球半径 R=6371．004 km。

除了这种简单的空间算法，Beeri等［6］总结了几种地理位置融合算法:片面最邻近、相互最邻近、概率方法和归一化权重算法。

相互最邻近(Mutually-Nearest，MN)算法对两个 POI数据集合的重合度不敏感［12］，更适合复杂的实际环境，因此本文空间算法选择相互最邻近算法。

假设有两个待融合的POI数据集合A={a1，a2，…，an}和 B={b1，b2，…，bn}。记ab∈A为b在数据集A中的最近邻对象，ba∈B为a在数据集B中的最近邻对象，那么a和b成为对应对象的置信度为:

其中 diatance(a，b)= ［(Lona－ Lonb)2+(Lata－ Latb)2］1/2。

如果置信度confidence(a，b)大于一定阈值则可以认为a和b是彼此数据集中的相互最近邻，可以把a、b标为可融合POI对象。

文献［4］提出了一种基于格网化纠正的多源 POI位置信息一致性处理方法，通过空间上划分地理格网，对各个地理格网单元实现局部一致化处理，来进行多源POI融合。

1．2 非空间属性算法

非空间属性算法是利用POI的非空间属性信息之间的相似度来寻找可融合POI对象的算法。

POI信息中的非空间属性是名称、地址、类别等字符串文本，不同来源的可融合POI对象通常都具有极高相似性，可以利用文本相似性算法来分辨。Jaro-Winkler距离是一种计算字符串之间相似度的方法［15］，它是Jaro距离的一个扩展。假设有两个字符串S1和S2，那么它们之间的Jaro距离可以定义为:

式(3)中:m是匹配的字符数，t是换位的数目。

Jaro-Winkler距离:

其中:djaro(S1，S2)是S1和S2的Jaro距离，是前缀匹配的长度，p是前缀匹配的权重。

Jaro-Winkler距离结果是一个大于0小于1的数，越接近1，文本越相似。如果a和b非空间属性信息的Jaro-Winkler距离大于一定阈值则可以认为a和b是可融合对象。

1．3 结合空间和非空间的算法

文献［11］提出了一种空间和非空间相结合的算法，可以找出不同来源数据集合中可融合的POI对象。其思路是初步筛选阶段使用空间算法找出初步融合集，排除阶段用低阈值的非空间算法计算排除初步融合集中错误的对应对象到单集中，补充阶段使用高阈值的名称相似性方法寻找单集遗漏的对应对象并添加到融合集。但是这种算法有不准确的地方，它并未考虑到同名分店的情况，在补充阶段会将其误认为是融合对象;也没有考虑到相近位置相似店名的不同类型POI点，在排除阶段无法将其识别，因此其融合结果在这些对象上表现不好。

2 基于距离类别的POI融合算法

为了更精确地找出可融合对象，本文提出了一种基于距离类别的POI融合算法。

文献［11］提出的传统的POI融合算法初步筛选阶段采用了文献［6］中的标准化权重算法计算待融合对象的空间相似度。排除阶段和补充阶段使用Jaro-Winkler距离计算待融合对象的名称相似度。本文提出的改进算法中在初步筛选阶段使用了对重合度不敏感、更适合真实环境的相互最邻近算法［12］，排除阶段除了使用Jaro-Winkler距离计算待融合对象的名称相似度，还对融合集加入类别判断。补充阶段除了使用Jaro-Winkler算法还引用了式(1)的球面距离约束，防止误判。

算法流程如图1。算法有三个步骤。

第一步 初步筛选阶段。对预处理后的数据集A，B使用相互最邻近(MN)算法，将置信度大于阈值λ的对应对象放入融合集ab，低于阈值的放入单集AA，BB。

第二步 排除阶段。对初步筛选后的融合集ab的对应数据AmBm使用Jaro-Winkler算法计算名称相似度。将类别一致时名称相似度低于低阈值γ和类别不同时名称相似度低于高阈值δ的对应对象排除到单集。

第三步 补充阶段。对初始单集数据AA，BB进行使用Jaro-Winkler算法和球面距离算法，将其中名称相似度高于阈值τ且类别一致、空间距离低于距离阈值φ的对象补充到融合集内，得到单集和融合集。

图1 融合算法流程Fig．1 Flow chart of fusion algorithm

算法伪代码如下:

输入:数据集A和B

输出单集A，B和融合集AB

伪代码中conf(Ai，Bi)是式(2)计算得到的置信度，其中categeory(A)，categeory(A)是a的类别，djaro-winkle(Ai，Bj)是使用式(3)和式(4)计算的Jaro-Winkler距离，distance(A，B)是由式(1)计算得来的地球直线距离。

本文针对文献［11］在排除阶段相似名称相近位置POI数据误判问题，对初步筛选阶段后的融合集内位置相近的数据，加入类别判断。考虑到分类结果不可能完全准确，单纯将类别不同的数据排除到单集会造成误判，结合名称相似性方法，将类别不同但名称相似度低于高阈值δ和类别不同名称相似度低于稍低阈值γ的数据对排除到单集。这种改动会降低在排除阶段相似名称、相近位置、不同类别POI数据误判。

在补充阶段使用严格的距离、类别和名称相似度约束，在补充初步筛选阶段遗漏的可融合对象的同时，可以减少同名异地POI数据被错误补充进融合集的可能性。

3 实验与结果

3．1 数据采集与预处理

本文使用爬虫在百度地图、谷歌地图采集眉山市的POI数据，然后对数据进行清洗、去重等预处理操作，将数据的坐标统一转换到百度坐标，并将POI数据中类别缺失的数据按照谷歌分类体系［12］进行分类。

处理后的数据约3万条，每一条POI数据代表一个真实的地体实体，它由7个字段组成，分别是ID、名称、地址，经度、纬度、类别和POI编号。ID是POI标识，名称字段表征POI的名字，类别字段表示POI所属类别，经度、纬度可用来标识POI的地理位置，地址表示POI所在的位置(街道、门牌号等)，POI编号是人工标注的，值是它对应另一个来源的可融合POI对象的ID，如果没有为空。

在预处理后POI数据集中随机抽取70%数据作为训练集，30%作为测试集。在融合实验中，为了验证算法是否容易导致过拟合现象，而且真实环境中，不同数据源之间的重合度不是一个确定值，因此本文在测试集中不同数据源分别随机抽取了重合度不同的7组数据作为测试数据，如表1所示。

表1 不同重合度测试数据集Tab．1 Different coincidence test data sets

其中:正例是在数据集中有对应POI的数据中随机取样得到的，负例是随机抽取的相应数量的没有可融合POI对象的实体，正例比例是正例数占实体总数的比例，实体数代表两个测试集中POI的数量。

3．2 融合结果质量评价指标

本文实验部分采用国际上权威且通用的准确率(Precision)、召回率(Recall)和F1值作为衡量POI融合结果质量的评价指标。

准确率是指结果融合集中正例占融合集比例，它表示算法计算出来的融合对象是真正可融合的对象的概率:

召回率是指结果融合集中正例占样本实际正例的比例，它表示的是样本中的可融合对象有多少被算法正确融合了:

实际应用时，需要平衡准确率和召回率，使用F1值作为算法评价指标。计算方法如下:

3．3 阈值选取

补充阶段的距离使用球面距离式(1)来计算训练集样本中随机选择的200个已经标记的融合对象的距离，结果如图2所示，并对每对可融合POI计算距离后按距离排序。

由图2可以看出90%以上的融合对象都集中分布在30 m以内，为了提高准确率防止误判选取30 m作为距离阈值φ。

本文中初步筛选阶段只使用相互最邻近算法，根据文献［11］选定阈值λ为0。

三个阶段中使用的算法有空间算法:相互最近邻算法和球面距离，非空间算法:Jaro-Winkler算法。其中空间算法阈值都已经确定，Jaro-Winkler算法因为涉及到排除阶段和补充阶段两个阶段，有三个阈值，因此更加难以确定阈值。

图2 可融合对象的距离分布Fig．2 Distance distribution of object to be fused

排除阶段和补充阶段使用的Jaro-Winkler算法有三个阈值γ、δ、τ待定。排除阶段Jaro-Winkler算法的两个阈值初始值γ、δ之间是相互影响的，无法单独确定。文献［11］Jaro-Winkler算法选定阈值为0．86，这个阈值是不在类别影响下得到的，因此根据控制变量法原理本文设类别不同时采用的阈值δ等于常量0．86。在训练集上做实验调试阈值，设γ为0．1并依次增加直至1，由式(7)计算排除阶段的F1值。此时可以得到γ的最佳阈值:F1为最大值时的值。将γ设为最佳阈值，设δ为0．1并依次增加直至1，计算排除阶段的F1值。记F1为最大值时的δ为最佳阈值δ。

此时已经得到最佳阈值γ、δ、λ、φ。将其他算法阈值设置为最佳阈值，补充阶段的Jaro-Winkler算法的τ设为0．1并依次增加直至1。综合计算三个阶段算法得到融合结果F1值，观察结果可得最佳阈值τ。

测试结果如图3。

图3 阈值测试结果Fig．3 Results of threshold testing

根据测试结果，Jaro-Winkler距离方法在POI融合过程中各个阶段参数的阈值 γ、δ、τ 分别为 0．7，0．8 和 0．9。

3．4 融合实验

对本文方案和文献［11］、文献［4］进行POI融合对比实验，使用式(5)、式(6)、式(7)评估这些方案在本文测试集实验数据上的性能，方案详情如表2。

表2 POI融合方案所用算法和属性对比Tab．2 Algorithms and attributes used in different POI fusion schemes

其中，空间和非空间算法(Combined Normal Weight and Title-similatity algorithm，COM-NWT)是文献［11］的方案，格网化纠正(简称为“网格化”)是文献［4］的方案，距离类别的兴趣点融合算法(Mutually-Nearest Method considering Distance and Category，MNMDC)是本文提出的距离、类别改进的方案。测试融合方案在不同重合度下的性能，融合结果如图4所示。

图4 三种POI融合方案准确率、召回率、F1值和均值对比Fig．4 Precision，recall，F1 and averagecomparision of three POI fusion schemes

从实验结果中可以看出，当数据集中的正例较少时，MNMDC方法因为引入了距离的判断，能够比COM-NWT方法更有效地排除数据集中的负例，并且MNMDC方法通过对类别的判断，进一步提升了融合过程中的准确率，从而获得了明显优于COM-NWT方法的和格网化方法的融合效果。

随着正例比的增加，数据集中存在类别缺失的数量逐渐增多，由于这些POI的类别来自人工分类，POI分类过程产生的误差会导致融合时类别判断的错误，再加上距离判断中为了提高准确度而选取的严格的距离阈值，会使一些可融合的对应对象被划分到单集，所以MNMDC方法的召回率出现了明显的下降，而COM-NWT方法不受分类的影响，因此表现较为平稳。但是正例比的增加，造成POI密度的增加，格网化方法出现误判，召回率下降。在三个方案中，本文提出的MNMDC方案召回率仍最高。在多组测试集中进行测试，实验结果均表现良好且相差不大，采用公开数据集中百度和谷歌的POI数据做对比实验，准确率为91%，召回率为90．5%，和在自行爬取数据集中相差不大，对比实验证明本文采用的算法具有普适性且不易产生过拟合现象。

4 结语

在数据时代，伴随着网络电子地图与LBSN的快速发展，POI数据的需求与日俱增，单独来源的POI数据已经不能满足这种需求。为了将不同来源的POI数据融合到一起，组成一个更完整的POI库，本文在国内外研究成果基础上，提出的MNMDC方法在COM-NWT的基础上引入了对距离和类别的判断，在POI数据集中可融合对象比例较低的情况下，准确率、召回率和F1值获得了明显的提升，更适用于本文中多个数据源的POI融合方案。但本文的数据仅仅是一个城区的数据，下一步研究方向应该是大数据下的数据融合方法。