基于词信息量加权的地理POI数据融合新方法研究

王逍翔 杜庆治 赵继东

摘要：

伴随着网络电子地图与位置服务（LBS）的快速发展，为了提高移动地图POI点的数据质量，融合不同地图服务提供商提供的数据内容存在不一致信息。为提高数据的复用性和完善性，提出了词信息量加权的地理POI数据融合方法，通过对地址信息中的词进行统计，计算其所包含的信息量，筛选、匹配不同来源的数据，并统一不同地图经纬度坐标以校验结果，实现了地理数据的融合。实验得到了完善的POI数据集合，证明该方法具有应用价值。

关键词：

POI；信息量；地理数据；数据融合

DOIDOI：10.11907/rjdk.172625

中图分类号：TP 301

文献标识码：A文章编号文章编号：16727800（2018）003004104

英文摘要Abstract：With the rapid development of Internetbased electronic map and Location Based Service， for improving the quality of mobile map POI（Point of Interest） data，fusing the inconsistent information from different map service providers will improve reusability of data to make data rich and integrated. This paper proposes the weighted word information data fusion for geographical POI. With the words statistics of address information， we calculate information content in order to screen and match different source data and unify different maps longitude and latitude for verified results. As a result， we achieve geographical data fusion， also acquire thorough POI data gather. It proves that our work is practical and valuable.

英文關键词Key Words：POI；information content；geographical data；data fusion

0引言

近年来，随着Web技术的迅速发展，电子地图被广泛使用，随之出现的基于电子地图的地理信息服务也迅速增长，各种提供电子地图服务的网站大量出现，这类网站在短时间里积累了大量用户。与传统地图提供路线查询不同，电子地图中提供的点是与人们日常生活相关的位置信息点，对人们生活中的需求有了更详尽的描述。POI（Point of Interest，兴趣点） 通常包括名称、地址、类型和经纬度等方面信息[1]，作为生活信息服务的基础，其应用也越来越广，如位置搜索服务、地理位置信息搜索等。

同时，由于提供电子地图服务的网站不同，不同数据源之间的数据会存在不同程度差异，这些差异会使POI数据的利用受到一定限制。消除可识别的差异，将数据统一整合到一起，将构建出一个内容更完整、数据更规范的数据库，实现数据充分有效利用。

POI 融合的研究包括非空间属性方法和空间位置方法[2]。对于非空间属性方法，1998年Cobb等[3]在进行矢量数据标准格式文件与VPF之间的融合技术中，提出了基于知识的属性数据匹配策略；2010年Alhwarin和Faraj[45]提出了一种快速筛选功能匹配方法；空间属性方法结合了空间位置信息，有更好的准确性，但通用性较差，代表有C Beeri等[6]在2004年提出了一种基于空间位置的地理数据融合技术。本文针对不同数据源提供的POI数据，运用名称地址加权相似度判断重复数据的非空间属性方法进行研究，并以空间位置信息验证实验结果。

1实验流程及方法

1.1POI数据词信息量统计

POI数据包含名称和地址两部分，其中两部分都描述了实体的特征和地理方位，通过两部分的综合比较可以确定POI表述是否为同一实体，例如：“宏发饭店，云鹤路上段310号”、“宏发饭店（云鹤路），云鹤路310-312号”，两个实体的POI信息都包含名称和地址，忽略其人为命名出现的局部差异，在一定时空范围内可以判定这两个信息表达了同一实体。名称和地址是由长度不一的词构成的，其中词出现的频率体现了其所包含的信息量，研究范围不同，词语所包含的信息量也有差异。譬如，在中国，“中国云南省昆明市宏发饭店”中的“中国”包含信息量极低，而“云南省昆明市”信息量则较高，所以统计研究对象的词频，可以有效界定本范围中词所具有的信息量，定量表示词语在信息中的重要程度。

词频统计分为两个部分：名字包含词的词频统计和地址包含词的词频统计，统计对象是不同源数据简单合并后的数据库。设名字和地址包含的词分别为Wni（i=1，2，3，…，N）、Waj（j=1，2，3，…，L），N为名字包含词的总数，L是地址包含词的总数，通过统计得到相应的词频分别为Pn（Wni）、Pa（Wai），就可以计算出词的信息量：

I（Wni）=-log2Pn（Wni），I（Wai）=-log2Pa（Wai）（1）

由于命名不规范，可能会出现名字中包含地理信息、大小写不分和错误符号的情况，所以需要对地址信息进行预处理，以提高结果的正确率。具体地，名称中包含地理信息的情况对结果影响最大，如“享客来西餐厅（建设路店）”、“瑞余烤鱼堂（福文路店）”等，处理方法是将其中的地理信息移动至位置描述中，之后再进行关键词统计，能很好地修正统计结果。

1.2相似度计算

1.2.1经典相似度计算方法

用S和T 分别表示待比较的两个字符串，文本S的长度为 p，文本T的长度为q。

（1）基于编辑距离的相似度。编辑距离是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符、插入一个字符、删除一个字符。定义S、T之间的编辑距离为edit（S，T），其相似度可以表示为：

simedit（S，T）=1-edit（S，T）max（p，q）（2）

（2）基于最长公共字符串的相似度。如果字符串G包含于两个或两个以上文本中，且在这些文本的共同字符串中长度最长，则称之为最长公共字符串（Longest Common Substring）。将最长公共字符串长度表示为mst（S，T），基于最长公共字符串的相似度为：

sims（S，T）=mst（S，T）max（p，q）（3）

（3）基于最长公共子序列的相似度。一个数列S，若分别是两个或多个已知序列的子序列，且是所有符合条件序列中最长的，则S称为已知序列的最长公共子序列（Longest Common Subsequence，LCS）。定义最长公共子序列长度为mse（S，T），序列共有N个元素，li表示第i个元素的长度，有：

mse（S，T）=∑Ni=1li（4）

則基于最长公共子序列的相似度为：

sims（S，T）=mse（S，T）max（p，q）（5）

1.2.2基于词的信息量相似度

POI数据包含名字和地址两个部分，设两个POI数据分别为Ps、Pt，Ps={NWs，AWs}、Pt={NWt，AWt}，譬如{“泰咖小餐厅”， “大理市其它文华路310号”}、{“泰咖小餐厅”， “文华路310号（近火车站）”}就构成了一对POI数据对，NWs表示Ps的名字部分，AWs表示Ps的地址部分，NWt表示Pt的名字部分，AWt表示Pt的地址部分。

经过名称和地址的分词后，可得到：

NWs={nsh|0

AWs={asi|0

NWt={ntj|0

AWt={atk|0

其中，nsh、asi、ntj、atk分别表示NWs、AWs、NWt、AWt分词后包含的词，H、I、J、K表示各自包含词的个数。

计算相似度之前，先要获得NWs和NWt、AWs和AWt的最长公共序列，得到公共序列：

LSC（NWs，NWt）={nf|0≤f≤F}

LSC（AWs，AWt）={ag|0≤g≤G}（7）

式（7）中：nf表示名字部分中的相同词，总数为F；ag表示地址部分中的相同词，总数为G。获得公共序列采用动态规划法[7]。用一个二维数组c[x，y]记录{nsh|0

c[x，y]=0ifx=0ory=0

c[x-1，y-1]+1ifx，y>0andnsx=ntymax（c[x，y-1]，c[x-1，y]）

ifx，y>0andnsx≠nty （8）

构建c[x，y]矩阵，这个矩阵中的每个数字代表了该行和该列之前LCS的长度，现在以两个名字说明：“云南天发商务酒店总店”、“云南大理天发国际商务酒店”，经过分词后得到两个序列为{“云南”，“天发”，“商务”，“酒店”，“总店”}和{“云南”，“大理”，“天发”，“国际”，“商务”，“酒店”}，过程如图1所示。通过回溯，得到两名字的最长公共序列为{“云南”，“天发”，“商务”，“酒店”}。

在词的比对中可能会遇到相近但不完全相同的词，例如，“大理”和“大理市”、“宾馆”和“旅馆”、“XX路”和“XX街”等，建立一个近义词库将有效识别这些相近的词，使结果更加合理。将近义词识别加入到动态规划过程中，得到改进的模糊匹配最长公共序列，使得处理结果变为：

FLSC（NWs，NWt）={nf|0≤f≤F}∪

{（n1r，n2r）}|0≤r≤R

FLSC（AWs，AWt）={ag|0≤g≤G}∪

{（a1z，a2z）}|0≤z≤Z

（9）

式（9）中：（n1r，n2r）表示名字中的一组近义词，总数为R；（a1z，a2z）表示地址中的一组近义词，总数为Z。这样就可以计算名称和地址的相似度：

simn（NWs，NWt）=∑Ff=0I（nf）+0.8·∑Rr=0I（n1r）+I（n2r）212∑Hh=1nSh+∑Jj=0ntj（10）

sima（AWs，AWMt）=∑Gg=0I（ag）+0.8·∑zz=0I（a1z）+I（a2z）212∑Ii=1aSi+∑Kk=1atk（11）

总相似度由名字和地址的相似度加权相加获得，名字相似度权值为λn，地址相似度权值为λa。

simi（Ps，Pt）=λn·simn（NWs，NWt）+

λa·sima（AWs，AWt）（12）

1.3处理流程

1.3.1处理结果分类

POI数据融合中存在不同处理结果，所以本文将其分为3类。

类型1：与另一数据源有对应的重复数据，例如“锦香蓉，大理市其他兴国路59号（近人民北路）”和“锦香蓉，兴国路59号（兴国店）”两条信息，名字与地址都可以很好地匹配，也就确定为重复数据，将两条信息都定义为此类。

类型2：无法确定是否与另一数据源的数据对应，但很可能有相对应的数据，例如“德化碑名胜园，大理白族自治州大理市”和“德化碑名胜园，214国道东50米”，名字高度相似，但地址信息不足以判断是否为同一数据，将两条信息都定义为此类。

类型3：与另一数据源没有对应的数据，除掉上述两种类型，剩余信息都归作此类。

经过处理，将数据源中的数据分为3种类型，有利于后续处理和结果校验。这里定义重复数据对（Clone Pair）为满足判定条件的相互重复的两条数据，它包含两个数据来自不同数据源：类型1数据，由于重复数据对不是一一映射，如图2所示（这里假定A相似于B，B相似于C，那么A相似于C），所以定义重复数据簇（Clone Cluster）为满足判定条件两两重复的一组数据，它由重复数据对合并得到，数据个数大于等于2，至少有两个数据来自不同数据源；同时，类型2数据也可以组成存疑重复数据对（Dubious Clone Pair），表示满足判定条件疑似相互重复的两条数据，包含两个数据来自不同数据源。这是本文主要要识别和验证的部分，关系到重复信息消除的效率和准确性，筛选出这些信息方便使用其它方法判别其是否确实重复。

1.3.2具体流程

基于信息量的信息相似度判别分为名字和地址两个部分，所以处理过程相似度的计算是分步进行的。首先，列出所有名字中含有相同字符串的数据对，每对数据中的数据都来自不同数据源。然后，计算名字相似度、地址相似度和总相似度，大于阈值的信息对即为重复信息对，名字相似度达到一定门限但总体相似度达不到阈值的信息对将作为暂存数据；如果其地址信息包含信息量低于一定阈值，名字相似度达到一定门限，则将暂存数据中的该部分作为存疑重复数据对。重复数据对之间可能存在交叉，将交叉的地址合并后就可以得到重复数据簇，其中每个簇都表明了一组重复的数据，也就可以标明数据源各自的类型1地址；通过存疑重复数据对也可将数据源各自的类型2地址标明；在数据源中排除类型1、类型2数据，剩余部分就划分为类型3数据。

依据上述方法，数据处理流程如图3所示。

2实验结果及分析

2.1处理结果

本文采用从高德地图上统计的2 823條和百度地图上统计的6 264条环洱海餐馆、旅馆数据作为实验数据，对其进行了处理。对数据正确率的测定，采用POI数据中的经纬度数据结合人工判断方法实现。首先，对名字和位置描述权值分配测定，通过不同权值获得的结果对其测定正确率，得到如图4所示的结果。同时，测定了名字权值与匹配地址对数量的关系，如图5所示。

可以看到，名字权值λn在0.72以下时正确率基本维持不变，大于0.72时有明显减小；同时，随着名字权值增加，得到的匹配结果数量也不断增加。所以，在保证正确率的前提下，为了尽量获得足够多的匹配结果，λn取值为0.72，λa取值为0.28。

经过处理得到结果如表1所示，其中两地图匹配数不相同，是由于地址信息不是一对一匹配，可能存在交叉的情况。其中重复数据对的数目为751个，重复数据簇数目为747个，存疑数据对的数目为493。消除重复信息后将数据合并后的总数据条数为7 995。

2.2结果评价

基于词信息量的地理POI数据融合方法中，最重要部分就是重复地址的匹配，对此，采用基于最长公共字符串的相似度匹配法、基于最长公共子序列的相似度匹配法和基于单字信息量匹配进行结果精确度对比。其中，基于单字信息量匹配，即不进行分词处理，将单个字计算信息量，其它操作与基于词信息量的匹配相同。对比结果如图6所示。

其中，方法1表示本文最终采用基于信息量的匹配方法，方法2表示基于最长公共字符串的相似度匹配法，方法3表示基于最长公共子序列的相似度匹配法，方法4表示基于单字信息量匹配。可以看到采用基于关键词信息量的地址匹配方法，在匹配数目相同的情况下可以达到精度最高。

上述结果表明，本文对地址重复数据的筛选精度可达到96%，有效识别了不同数据源中包含的重复信息。对由于信息缺失而无法判断的信息采取了归类方法，获得了不确定信息对，校验后得到其中70%为重复数据，可见其中的确包含了大量需要再处理的重复数据。经过不确定信息处理，后续进一步筛选重复数据的效率将会大大提高。

3结语

本文提出了词信息量地理POI数据融合的流程和算法，并着重对其匹配算法进行了对比，对比结果显示，本文采用的相似度算法综合了基于最长公共字符串的相似度匹配法、基于最长公共子序列的相似度匹配法和基于单字信息量匹配的优点，达到了96%的精确度，有效识别了数据中的重复信息。进一步，对那些无法在没有其它数据验证情况下进行准确判别的数据进行了保留分类处理，有利于后续对这部分数据的校验。本方法很好地将POI数据分为3类，消除了数据冗余，进行了数据融合，使数据形式更加规范。由于算法中并未将经纬度作为判别数据类型的依据，仅将其作为验证手段之一，所以此算法可以应用于丢失经纬度信息的POI数据和一般形式地理数据的融合。

参考文献参考文献：

[1]张玲.POI 的分类标准研究[J].测绘通报，2012（10）：8284.

[2]王婷婷.基于位置与属性的多源POI数据融合的研究[D].青岛：中国海洋大学，2014：23.

[3]NOLTE R T， WISELY G B，WESTIN S， et al.Ligand binding and coactivator assembly of the peroxi some proliferatoractivated receptorγ[J]. Nature， 1998，395（6698）：137143.

[4]BAYH，TUYTELAARS T，VAN GOOL L.Surf： speeded up robust features[C].Computer VisionECCV 2006.Springer Berlin Heidelbei，2006：404417.

[5]RUBLEE E， RABAUD V， KONOLIGE K， et al. ORB： an efficient alternative to SIFT or SURF[C].ComputerVision （ICCV）， 2011 IEEE International Conference on. IEEE， 2011：25642571.

[6]BEERI C， KANZA Y， SAFRA E， et al. Object fusion in geographic information systems[J].Proceedings of the Thirtieth International Conference on Very Large Data BasesVolume 30，2004：816827.

[7]刘维，陈崚.最长公共子序列的快速算法及其并行实现[J].计算机应用， 2006，26（6）：14221424.

[8]赵作鹏，尹志民，王潜平，等.一种改进的编辑距离算法及其在数据处理中的应用[J].计算机应用，2009，29：424426.

[9]邓鹏，李霖，陈功，等.基于用户情境的POI个性化推荐模型[J].测绘地理信息，2015，40（3）：5256.

[10]池娇，焦利民，董婷，等.基于POI数据的城市功能区定量识别及其可视化[J].测绘地理信息，2016，41（2）：6873.

[11]龙军.基于角色标注的中文POI名称匹配的研究及原型系统实现[D].重庆： 西南大学，2008.

[12]DUBOIS D M. Computational language related to recursion； incursion and fractal[C].Language and Recursion. Springer New York， 2014：149165.

[13]LIU S， FENG J， WU Y. Regionaware Topk similarity search[C]：Qingdao， China， Proceedings of WebAge Information Management15th International Conference， WAIM 2015， 2015.

责任编辑（责任编辑：何丽）