基于Levenshtein-Jaro距离的POI判重处理与实现.pdf

浙江测绘 2023 年第 3 期1 引言POI作为天地图的重要组成部分袁 在促进地理信息资源共享和高效利用袁改进测绘地理信息成果的服务方式袁更好地满足城市信息化建设等方面发挥着重要作用1遥当前袁根据叶浙江省地理信息公共服务平台渊天地图冤POI数据更新技术要求渊2022冤曳2和叶浙江省天地图省尧 市渊县冤 级数据融合技术方案渊2020冤曳3渊以下统称野融合方案冶冤相关要求袁POI在经过融合判重尧分词处理尧唯一码编制尧分级显示等处理后上传至浙江政务地理信息资源采集共享平台遥 目前袁POI融合判重处理主要是野软件处理冶和野目视判别冶相结合的方式遥 其中袁野软件处理冶主要是根据现有工具进行遥但在使用中发现袁 现有工具仅能对名称存在包含关系的POI进行识别渊如野宁波市镇海区冶和野镇海区冶可以进行识别袁野宁波市镇海区冶和野宁波镇海冶无法识别冤袁 且忽略了POI的类别属性和POI合理重复存在的情况渊如公交站尧停车场等冤袁使得判定的结果存在一定的野漏判冶和野误判冶袁因此此项工作主要还是依靠人工在二维地图上 野目视判别冶遥 而野目视判别冶不仅工作量极大袁同样容易造成POI漏判遥 因此袁 为提高POI融合判重处理效率袁 本文将结合融合方案中的相关要求袁 在综合考虑POI判重处理效率和程序实现难易程度的基础上袁分析归纳Levenshtein-Jaro距离的POI判重处理原理袁并基于Python开发出操作软件袁实现POI融合判重遥2 材料与方法2.1 数据来源在本文中袁POI数据来源于2021年镇海区地理信息公共服务平台袁 包括省节点POI和商业POI遥 其中袁省节点POI数据由省自然资源相关部门下发袁商业POI数据由宁波市自然资源相关部门下发袁两者坐标系均为2000国家大地坐标系遥2.2 POI 融合判重由融合技术方案可知袁POI融合判重是以省节点POI为本底袁 商业POI为更新源进行融合袁并将省节点尧商业POI中重复的POI仅保留现势性高的POI袁现势性低的POI予以舍弃遥 同时袁后续POI分级处理等内容均在此基础上进行袁因此袁POI融合判重是POI更新融合的关键遥根据汉典中对于野重复冶的定义院同样的东西再次出现遥 引申至本文中袁结合POI的类别属性和空间特征袁野重复POI冶则可以定义为院一定空间范围内同样的POI再次出现遥 即袁近距离内具有相同的名称和类别属性的POI可以称之为野重复POI冶遥 图1为野疑似重复POI冶示例遥基于 Levenshtein-Jaro 距离的 POI 判重处理与实现梅杨袁朱若愚袁范攀峰渊宁波市镇海规划勘测设计研究院袁宁波315202冤摘要院 为解决天地图 窑 POI 融合过程中 POI 融合判重问题袁本文依据天地图数据融合技术方案要求袁给出了野重复 POI冶定义遥 同时袁基于 Levenshtein-Jaro 距离袁详细阐述了 POI 模糊判重实现流程,并基于 Python 开发相关计算软件遥 最后袁以镇海区骆驼街道 2021 年 POI 数据作为示例数据进行分析和优化袁同步对比现有工具检测结果袁证明了处理流程的有效性和处理结果的可靠性遥关键字院 POI曰融合判重曰Levenshtein-Jaro 距离技术交流ZHEJIANGCEHUI23窑窑浙江测绘 2023 年第 3 期在图1中袁图a的野吾悦广场冶因类别不同袁因此判定不属于野重复POI冶遥 图b名称尧类别虽一致袁 但分别位于两条不同的街道 渊直线距离348米冤袁也不属于野重复POI冶遥 图c名称尧类别一致袁且空间邻近渊直线距离10米冤袁属于野重复POI冶遥根据野重复POI冶定义袁判定两个POI属于野重复POI冶的依据是名称尧类别属性和空间距离遥 其中袁对于类别属性袁待判定的POI属性必须满足一致曰对于空间距离袁可根据生活中野重复POI冶渊如ATM尧品牌连锁店等冤之间的空间关系进行估算遥 而相较于类别属性和空间距离袁判定两个名称是否相同一般需要用野相似度冶来衡量院野相似度冶越高袁则越有可能是同一个POI曰野相似度冶越低袁越有可能不是同一个POI遥 在本文中用Leven-shtein距离来衡量野相似度冶袁其计算过程如下:渊1冤Levenshtein距离Levenshtein距离作为评价文字识别匹配程度的标准之一袁 又称之为编辑距离袁 由VladimirLevenshtein于1965年首次提出袁 是指一个字符串袁通过插入尧删除和替换操作后转换为另外一个字符串的最小步数4袁其相似度计算公式如下院Sim=渊Len-Levnshtein冤/Len上式中袁Len为较长字符串的字符串长度袁Levenshtein为两个字符串的编辑距离遥 如图1c所示中袁野镇海区电子商务产业园冶可以通过4次插入操作后转换为野镇海区(跨境)电子商务产业园冶袁因此野镇海区电子商务产业园冶与野镇海区(跨境)电子商务产业园冶的Levenshtein距离为4袁其对应的相似度为0.71遥 一般来说袁距离越小尧两个字符串的相似度越大袁判定为野重复POI冶概率也越大曰距离越大尧文本的相似度越低袁判定为野重复POI冶概率也越小遥渊2冤Levenshtein-Jaro距离标准Levenshtein距离虽然能够通过记录两个字符串之间的转换次数来衡量文本之间的相似度袁但因其忽略了字符串本身特征渊如字符串中字符的位置冤 且计算效率低袁Matthew在1989年提出了改进Levenshtein-Jaro距离5袁其计算方式如下院Sim013渊ms1+ms2+m-tm冤扇墒设设设设缮设设设设上式中袁s1尧s2表示两个字符串的长度袁m为两个字符串重复的字符数量袁t表示换位数目的一半遥 如图1c中袁s1为14袁s2为10袁m为10袁t为0渊不存在换位字符冤袁计算得到两个字符串的相似度为0.90遥3 结果分析与优化为验证和分析上述方法的有效性袁本文以镇海区骆驼街道2021年天地图POI数据作为示例数据渊共6458个冤袁在Python中开发出相关计算程序袁完成POI判重处理遥 同时袁将计算结果与现有工具检查结果进行对比分析遥3.1 现有工具检查结果运用现有工具渊如图2所示冤袁对镇海区骆驼图 1 野疑似重复 POI冶示例abcm0m0渊2冤渊1冤技术交流ZHEJIANGCEHUI24窑窑浙江测绘 2023 年第 3 期由表2可知袁两种计算后相似度为1的点对数量相当袁共计均为152对左右袁进一步目视判别后发现袁可以判定为野重复POI冶为46个曰对相似度小于1的POI点对袁Levenshtein共计筛选出15060对袁经目视判别后可以判定的野重复POI冶数量为111个遥Levenshtein-Jaro共计筛选出12247对袁经目视判别后可以判定的野重复POI冶数量为155对遥街道POI数据分别进行野重复点检查冶和野重复点检查渊精确冤冶遥渊1冤野重复点检查渊精确冤冶运用野重复点检查渊精确冤冶工具袁初步检查出136对POI存在重复遥 在对136对POI进行目视判别后发现袁 现有工具所检测的最大距离为110米左右 渊根据检查的结果进行手动量测得到袁存在一定误差冤袁判定为野重复POI冶数量为46个袁其原因在于停车场尧公交站尧公共厕所尧垃圾收集点等合理存在且需要显示的POI被检测出来渊如表1所示冤遥渊2冤野重复点检查冶运用野重复点检查冶工具袁初步检查出455对POI存在重复遥 在对455对POI进行目视判别后发现袁现有工具所检测的最大距离同样为110米左右渊根据检查的结果进行手动量测得到袁存在一定误差冤袁判定为野重复POI冶数量为13个遥综合袁运用现有工具共计检查出野重复POI冶点59个遥3.2 Levenshtein 两种方法检查结果根据现有工具检测距离袁 设定判定距离为110米袁对镇海区骆驼街道POI数据进行计算袁得到结果如表2所示遥图 2 POI 现有检查工具表 1 现有工具检查结果类别POI 数量渊对冤停车场/车库26公交站38公共厕所16垃圾收集点10其他 POI46表 2 Levenshtein 两种方法检查结果相似度LevenshteinLevenshtein-JaroPOI 数量渊对冤目视判别后重复POI 数量渊对冤目视判别后重复Sim=10.95 Sim10.90 Sim0.950.85 Sim0.900.75 Sim0.85Sim0.75合计1510111371187137251521146010165827157152336491143560848141239946227534177201技术交流ZHEJIANGCEHUI25窑窑浙江测绘 2023 年第 3 期优化完成后袁设定判定距离为110米袁对镇海区骆驼街道POI数据进行计算遥渊1冤现有工具现有工具检查结果如表5所示遥无效点对的POI被检测出的原因在于部分POI的名称具有相同的辅助名称标识袁如野(银泰百货宁波镇海店)冶尧野(吾悦广场店)冶等遥 因此为减少后续目视判读工作量袁需对POI的辅助名称标识进一步优化遥3.3 算法优化根据上一步分析结果袁忽略POI中合理存在且需要显示的POI袁包括公交车站尧公共厕所尧垃圾收集点和停车场袁得到镇海区骆驼街道POI数量为5932个遥 同时袁针对辅助名称标识渊购物商场尧医院等冤袁在进行相似度计算时袁对POI的名称进行优化处理院在现有的名称中减去辅助名称标识渊如表4所示冤袁使得优化后的名称更简洁也更具有识别性渊此优化仅针对计算过程袁不改变POI原始名称冤遥整体上袁相较于Levenshtein袁Levenshtein-Jaro计算的点对数量少袁目视判别后野重复POI冶数量多且对应的相似度更大袁说明Levenshtein-Jaro结算结果较优遥通过Levenshtein-Jaro工具检查结果进一步分析发现袁在相似度为1的点对中袁同样存在停车场尧公交站尧公共厕所尧垃圾收集点等合理存在且需要显示的POI均被检测出来遥 在相似度小于1的点对中袁医院尧综合性购物商场被检测出大量的无效点对袁如表3所示遥序号 1名称 1序号 2名称 2相似度距离0000000表 3 无效点对示例161161162162365936593659巴邑火锅(银泰百货宁波镇海店)巴邑火锅(银泰百货宁波镇海店)六福珠宝(银泰百货宁波镇海店)六福珠宝(银泰百货宁波镇海店)镇海区人民医院-总务科镇海区人民医院-总务科镇海区人民医院-总务科289313313482366936813705周大福(银泰百货宁波镇海店)潮宏基(银泰百货宁波镇海店)潮宏基(银泰百货宁波镇海店)雅戈尔(银泰百货宁波镇海店)镇海区人民医院-医务科镇海区人民医院-财务科镇海区人民医院-医务科83.97%83.97%83.97%83.97%93.94%93.94%93.94%表 4 POI 名称辅助名称标识优化示例类型优化前名称辅助名称标识优化后名称购物商场医院李宁(银泰百货宁波镇海店)苏宁易购(吾悦广场店)苏宁易购吾悦广场店镇海区人民医院-口腔科镇海区人民医院-超声科(银泰百货宁波镇海店)(吾悦广场店)吾悦广场店镇海区人民医院-镇海区人民医院-李宁苏宁易购苏宁易购口腔科超声科技术交流ZHEJIANGCEHUI26窑窑浙江测绘 2023 年第 3 期技术交流ZHEJIANGCEHUI进一步分析优化前后的计算结果发现袁优化后判定数量明显提升的原因在于更多的点对被识别出遥 如图3所示点对袁优化前无法识别袁优化后可以识别遥由表5可知袁 优化后共计检查出重复点对353对袁目视判别后重复点位105个遥渊2冤Levenshtein两种方法Levenshtein优化后计算结果如表6所示遥 有表6可知袁 在优化后袁Levenshtein共计检查出13399对袁目视判别后野重复POI冶点数量为为174个遥Levenshtein-Jaro共计检查出900点对袁目视判别后判定为野重复POI冶有282个遥显然袁优化后Levenshtein-Jaro计算结果更优遥表 5 现有工具优化后检查结果检查方法POI 数渊对冤目视判别后重复重复点检查渊精确冤14546重复点检查2085959353105相似度LevenshteinLevenshtein-JaroPOI 数量渊对冤目视判别后重复POI 数量渊对冤目视判别后重复Sim=10.95 Sim10.90 Sim0.950.85 Sim0.900.75 Sim0.85Sim0.75合计表 6 Levenshtein 两种方法优化后检查结果460272510913192133994601811455417446261231473242349004624795766102823.4 对比分析对比分析优化前后袁 三种判定工具结果袁如表7所示遥由表7可知袁从处理的方法来看袁现有工具计算的点对数量少袁目视判别后野重复POI冶数量也少曰Levenshtein两种方法查找出的重复点对数量多袁视判别后野重复POI冶数量也多袁且Leven-shtein-Jaro结果均优于Levenshtein曰 从优化处理前后来看袁优化后三种方法在计算的点对数量上均有下降袁在目视判别后野重复POI冶个数均有提升袁且Levenshtein-Jaro提升效果最为明显遥表 7 优化前后判定结果对比现有工具LevenshteinLevenshtein-Jaro计算重复点对目视判定重复个数判定比例计算重复点对目视判定重复个数判定比例计算重复点对目视判定重复个数判定比例优化前591599.98%152111571.03%123992011.62%优化后35310529.75%133991741.3%90028231.33%提升比例40.27%64.06%/11.91%10.82%/92.74%40.30%/27窑窑浙江测绘 2023 年第 3 期4 结论与展望4.1 结论本文基于POI融合判重过程袁给出了野重复POI冶定义袁阐述了Levenshtein-Jaro算法的融合判重原理袁并基于Python开发相关计算软件遥最后袁以镇海区骆驼街道2021年POI数据作为示例数据进行处理分析尧优化和验证袁同步对比现有工具计算结果袁结果表明院渊1冤本文提出的POI融合判重切实可行袁处理结果可靠遥 同时袁相较于下发工具袁本文所述方法判读结果更优遥渊2冤对POI名称进行优化处理后渊包括忽略合理存在的重复POI和辅助名称标识处理冤袁能够过滤大量的无效重复点袁提高POI融合判重效率和计算精度袁证明了此优化过程的合理性和有效性遥 此外袁Levenshtein-Jaro提升最为明显遥渊3冤本文所述方法虽同样需进行目视判读袁但对比以往的二维地图判读袁Levenshtein-Jaro算法能够筛选出无关POI袁保留疑似重复的POI遥 同时袁将二维地图判读降至一维表格判读袁极大的减少了判读的工作量袁提高了工作效率遥4.2 展望本文虽基于Levenshtein两种算法在Python中开发实现POI融合判重处理袁但在使用和调试的过程中袁也发现了一些不足和需要完善改进的地方遥 因此在下一步的工作中袁需要从如下两个方面进行更加深入的研究院渊1冤本文忽略了停车场尧公交站尧公共厕所尧垃圾收集点等合理存在且需要显示的POI的判重处理遥 此外袁对所有的POI按照统一的判读距离进行处理袁忽略了POI的空间分布特征遥 因此袁在下一工作中袁还需结合不同类型POI的属性特征和空间分布特征袁设置不同的判读距离和相似度计算方式袁从而提高计算精度遥渊2冤通过Levenshtein-Jaro算法能够通过相似度来检查出部分重复的POI袁 但能否详尽的检查出所有的重复POI还有待进一步验证遥 因此袁在下一步工作中袁还需结合POI数据对算法做进一步的测试与改进袁提高检查的准确度遥参考文献院1 梅杨袁范攀峰袁王大鹏袁等.浅谈天地图 窑 镇海中 POI 数据的分级显示的自动化处理与实现J.浙江测绘袁2021渊1冤院5.2 浙江省地理信息公共服务平台渊天地图冤POI 数据更新技术要求R.浙江省自然资源厅袁2022.3 浙江省天地图省尧市渊县冤级数据融合技术方案R.浙江省自然资源厅袁2020.4 Levenshtein V I.Binary codes capable of correctingdeletions袁insertions and reversalsJ.Dokl.Akad.Nauk SSSR袁1965袁1966.5 Jaro袁Matthew A.Advances in Record-LinkageMethodology as Applied to Matching the 1985 Censusof Tampa,FloridaJ.Publications of the AmericanStatistical Association袁1989袁84渊406冤院414-420.作者简介院梅杨渊1991-冤袁男袁湖北武汉人袁工程师袁资源环境信息工程专业硕士研究生袁主要从事于地理信息系统开发及数据处理等工作遥Email院遥图 3 优化后重复点判读示例技术交流ZHEJIANGCEHUI28窑窑