地理范围确定和地名词典改进策略

the tweet is coming from, one may use a gazetteer such as GeoN-ames [31] to map those coordinates to an actual location entity.There is an increasing number of different devices that record GPScoordinates (e.g. phones, cars, cameras, etc.), and mapping the GPScoordinates to a an administrative location or a populated placecan be a useful service, for example, in dispatching services suchas ambulance, police, etc. The literature also reports numerous do-mains where gazetteers are used, including toponym resolution intext [15], geotagging tweets [35], documents [6] and entities [33],etc. To support many of these applications, one needs to both ef-fectively and efficiently join a gazetteer with other geo-coded data.GeoNames reports serving over 150 million web service requestsper day (as of October 2017), and many of those services can benefitfrom more accurate information about places and their boundaries.However, there are a few challenges that hinder progress in thisarea: (1) most public gazetteers either do not have bounding boxesfor many of their locations (e.g. GeoNames) or their bounding boxesare not accurate (e.g. OSMNames1, see Section 5.1 for details). In theabsence of a bounding box, there is no direct way of checking if anentity falls inside or outside a region boundary2, and applicationshave to implement their own ad-hoc solutions; (2) data in a gazetteeris prepared by public and is not necessarily accurate especiallyfor less populated places [1]; (3) there are inconsistencies withingazetteers and in relationship with other sources (see Fig. 1).Our approach to address those challenges is through maintain-ing bounding boxes for places. Attaching a bounding box to eachplace has a number of benefits, including more efficient support forreverse geo-coding queries and better monitoring and enforcementof consistency constraints in the form of relationships betweenbounding boxes. Since boundaries change due to growths, splitsand mergers, maintaining bounding boxes is a continuous process.The problem to be studied in this paper is if a bounding boxcan be accurately constructed for each place based on incompleteand sometimes erroneous information that is available, and if thosebounding boxes improve the quality of a gazetteer. We take, as abounding box, the minimum bounding rectangle (MBR) that satisfyall stated constraints in a gazetteer including the parent-child re-lationships. Despite their imprecision in some cases, for example,compared to polygons, MBRs provide a simple abstraction thatis more efficient for querying [3] and enforcing constraints [22].Sometimes the stated constraints cannot all be satisfied when cre-ating MBRs. We formalize the search for an MBR as a probabilisticoptimization, which tries to find the most likely MBR by droppingthe least likely constraints.Our contributions can be summarized as: (1) We provide a sys-tematic study of the problem of improving and enriching a gazetteerTrack: Web Search and MiningWWW 2018, April 23-27, 2018, Lyon, France16630地理范围确定和地名词典改进策略0阿尔伯塔大学SanketKumar Singhsanketku@ualberta.ca0阿尔伯塔大学Davood Rafieidrafiei@ualberta.ca0摘要0许多使用地理数据库（也称为地名词典）的应用程序依赖于数据库中信息的准确性。然而，当从具有不同质量约束的多个来源集成数据时，数据质量差是一个问题，有时对于来源的信息了解甚少。这个问题的一个主要后果是位置的地理范围和/或位置可能未知或不准确。在本文中，我们研究了在地理数据库中检测位置范围的问题及其在识别不一致性和改进地名词典质量方面的应用。我们开发了新的策略，包括基于地名词典的空间层次结构以及可能可用的其他公共信息（如区域）的概率和几何方法，以准确地推导出地点的地理范围。我们展示了这里推导出的边界信息在识别不一致性、增强位置层次结构和改进依赖于地名词典的应用程序方面的有用性。我们对两个公共领域地名词典进行的实验评估表明，所提出的方法在地理边界框的准确性方面明显优于基于地名词典的父子关系的基线。在应用程序中，我们展示了这里推导出的边界信息可以将公共地名词典中超过20%的位置移动到层次结构中更好的位置，并且这些移动的准确性超过90%。0CCS概念0• 信息系统 → 地理信息系统；概率检索模型；全球定位系统；0关键词0地理范围确定，地名词典改进，地理标记0ACM参考格式：Sanket Kumar Singh和DavoodRafiei。2018年。地理范围确定和地名词典改进策略。在WWW2018：2018年万维网会议上，2018年4月23日至27日，法国里昂。ACM，美国纽约，第4篇文章，10页。https://doi.org/10.1145/3178876.318607801 引言0本文发表在知识共享署名4.0国际许可证（CC BY4.0）下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW2018，2018年4月23日至27日，法国里昂，© 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可证发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.318607801 http://osmnames.org 2反向地理编码API来自Google和其他搜索引擎，将地图上的点的坐标转换为可读的位置或地址，但其专有解决方案的细节通常不公开。16640（a）存在异常值0（b）覆盖不足0（c）中心不准确0图1：地名词典与其他来源之间的不一致性示例。（a）由于异常值，美国马里兰州的MBR被高估，（b）所罗门群岛的一个省Malaita的MBR由于数据覆盖不足而被低估，（c）给定的中心与MBR的中心相距甚远。（childrenMBR是引用地点在Geonames中列出的子地点的边界框，googleMBR是GoogleMaps返回的MBR；每个地点的子地点计数都有标示，中心和子地点分别用蓝色和粉色的点表示。）0使用地点的边界框；据我们所知，这是第一次对数百万个地点进行这样的研究。（2）我们提出了检测和解决地名词典中不一致性的策略。（3）我们评估了我们的策略，并报告了它们在检测地点边界和改进地点层次结构方面的准确性。（4）我们报告了我们的边界框在改进地点层次结构和增加包括YFCC100M[30]在内的其他数据源的效果。本文的其余部分组织如下：第2节回顾相关工作，第3节介绍了我们提出的构建地点最小边界矩形的策略。第4节列举了一些应用领域和设置。我们的算法在第5节进行了评估。第6节总结了本文。02 相关工作0与我们的工作相关的文献可以分为以下几类：（1）地理实体的空间范围估计，（2）冲突解决和数据清洗技术，以及（3）自动地名词典扩展和丰富。地理实体的空间范围估计可以使用地理标记实体（如照片[14]、视频和在线文档）来估计地点的地理边界。Chen等人[8]开发了一种方法来找到具有模糊边界的地点的空间范围。他们使用Flickr照片映射到一个区域的密度来定义地点的地理边界。作者们使用核密度估计来插值照片稀疏的区域的边界。Parker和Downs[19]在形成最小凸包之前对点进行聚类，以包围每个聚类。这两种方法的一个缺点是，如果一个地点分布广泛并且有不相连的区域（例如包含夏威夷等岛屿的地点），那么每个区域都会形成自己的边界，而不是形成一个特定级别（如国家、省或区）的边界。对于地点的多边形边界，可以使用Voronoi图来近似地点的范围[2]。Somodevilla等人[28]引入了模糊MBR的概念来模拟地理位置的空间范围，但没有提供关于质量或准确性的评估。0冲突解决和数据清洗冲突解决可以被视为在不同版本的数据之间做出决策，以确定一个黄金记录。在这个领域有大量的研究成果（例如，参见Bleiholder和Naumann的调查[4]和Dong和Naumann的教程笔记[10]）。在最近的一项工作中，Prokoshyna等人[23]结合了逻辑推理和定量方法来开发一种数据清洗方法。该工作中的定量方法涉及根据属性值的统计特性设置一些约束，并在违反这些约束时标记不一致性。作者们提出了一种最小集修复算法，以找到最小化统计失真的属性值。Volha等人[5]在dbpedia的背景下使用融合函数解决冲突，这些函数是从标记数据中学习得到的。融合函数集合是由领域专家事先手动定义的。作为一种通用的清洗技术，异常值检测可以用于过滤不符合一般预期基础分布的对象。在空间领域中常用的两种技术是箱线图[13]和袋图[25]，它们作为我们提出的启发式方法的一部分进行了评估。自动地名词典扩展和丰富自动地名词典的创建或丰富涉及添加新的记录或属性，以形成一个新的地点或一个现有地点的缺失特征。Popescu等人[20]使用多样的信息源和不同的实体提取、分类、坐标发现和排序算法创建了一个地名词典。最近，Oliveira等人[18]试图通过众包收集的地理信息来丰富GeoSEn[7]地名词典。作者通过在地名词典中添加在区和街道粒度上出现的地点来增加地名词典的空间层次结构。这些工作可以看作是与我们的工作无关的。03 地理范围0给定一个地名词典中地点的包含关系和约束集合，我们希望构建每个地点的边界框，以便理想情况下满足所有已知约束。我们将地点的边界框定义为与纬度和经度轴平行的任何最小边界矩形（MBR）。0会议：Web搜索和挖掘WWW 2018，2018年4月23日至27日，法国里昂16650并满足约束条件。这不一定能给出最准确的边界框，特别是当真实边界框不是凸多边形时；然而，与任意多边形相比，MBR在检查包含关系和约束条件方面更高效。检测地点的空间范围的一个挑战是通常对地点的信息不足，而且关系可能存在冲突或矛盾。例如，GeoNames中夏威夷的记录中心（如图1(c)所示）与其MBR的中心相距很远。此外，如图1(b)所示，googleMBR的北部地区没有子位置，仅根据父子关系构建此MBR是困难的。03.1 分层方法0构建MBR的一种策略是强制执行包含关系，即每个父MBR必须包含其子MBR。地名词典很擅长描述地点之间的包含关系。例如，GeoNames将每个位置分为国家或州等行政级别，并允许查询检索行政级别内的子位置。可以通过自底向上的方法计算地点的MBR的边界，方法是取所有子位置的南西坐标的最小值和北东坐标的最大值。这种策略的一个主要问题是不同地点的子位置数量可能差异很大。例如，人口更多的地方往往比农村城镇、水体、自然区域等拥有更多的子位置。另一个问题是子位置的分布倾斜以及子位置不总是分布在整个区域边界上（如图1(b)和1(c)所示）。03.2 几何方法0分层方法的一个主要缺点是对于在地名词典中具有非常少或没有子位置的地点，无法获得良好的地理范围。例如，从GeoNames中的点构建的马莱塔省的MBR的面积（如图1(b)所示）约为从GoogleMaps获得的边界框的19倍小。我们的几何方法旨在解决这个问题。给定地点的中心点c和面积a，可以构造无限多个以c为中心、面积为a的矩形，但在没有额外信息的情况下，很难预测哪个矩形更有可能。尽管如此，我们的下一个陈述提供了一些证据，表明正方形可能是更好的选择。0猜想3.1. 设R为具有中心点c和面积a的所有矩形的集合，r ∈R。假设所有矩形的可能性相等，则R和r之间的重叠面积的期望在r为正方形时达到最大。0我们的几何方法将以C为中心、面积为A的正方形构造为地点的MBR。MBR的边界可以通过以下方式获得：通过将中心的纬度向北和向南移动因子F来获得东北（NE lat）和西南（SWlat）点的纬度，F的计算公式为0NE lat = C lat + F，SW lat = C lat - F0A )/( 2  �  L ) , L是两个连续纬度之间的距离（≈ 111 km），C lat和Clonд是中心C的纬度和经度。通过类似的方式获得端点的经度，只是随着向极地移动，两个连续经度之间的距离会缩小。因此，在将中心的经度移动F ne和F sw之前，我们首先获得给定纬度Dlat上两个经度之间的距离，F ne和F sw的定义如下：0Fne=(√0A)/(2*Dnelat)和Fsw=(√0A)/(2*Dswlat)0其中Dnelat=L*cosine((NElat*π)/180)（详见[29]），而Dswlat=L*cosine((SWlat*π)/180)。因此0NElong=Clonд+Fne and SWlong=Clonд−Fsw.0请注意，端点坐标的准确性取决于L的准确性和给定中心C的准确性。当子位置均匀分布在给定中心周围时，使用这种方法估计的边界框预计是准确的。然而，如果子位置包括异常值或给定中心远离子位置的集中区域，这种方法可能表现不佳。03.3概率方法0地理信息在地名词典中可能既不完整也不准确，这可能导致不一致性。一些这些不一致性可以通过基于规则的方法检测出来，但仍然存在的主要挑战是如何处理空间数据的不确定性。如果地名词典中的每个事实或陈述都可以被赋予一个它为真的概率，那么检测一个地点的边界框可以被视为一个约束优化问题。03.3.1模型。地名词典中的位置由纬度和经度描述；公共地名词典通常不提供有关如何获取坐标以及给定坐标是否实际上靠近地点MBR中心点的详细信息。为了测试这一点，我们随机选择了来自GeoNames和OSMNames的每个1000个地点。这些地点的坐标与从不同来源获得的边界框的中心点（在我们的例子中是从GoogleMaps获得的MBR，称为googleMBR）进行了检查。我们发现，GeoNames中只有63%的地点和OSMNames中约97%的地点的坐标与从googleMBR获得的中心点相距不超过10公里。建模中心点：设dc表示给定地点c的中心与其真实MBR中心之间的距离。如果我们假设dc服从参数为µ和σ的正态分布，则0Pr(dc|µ,σ)=10σ√02πe-(dc-µ)²/2σ² (1)0其中µ和σ分别是dc的均值和标准差。可以很容易地从数据中估计分布的参数。在我们的1000个地点的随机样本中，GeoNames的µ和σ分别为88.894和408.760，OSMNames的µ和σ分别为2.057和7.09。建模子节点：设q是一个任意位置被放置在地名词典中正确父节点下的概率。可以通过检查样本中每个地点的子节点是否被分配了正确的父节点来估计q的值。在我们的1000个地点的样本中，GeoNames的q值计算为0.968，OSMNames的q值计算为0.882。可以观察到，任意位置被放置在正确父节点下的概率相对较高；因此，基于这个经验结果，并且没有太多关于哪些地点可能是正确或不正确的子节点的额外知识，任意选择的子节点更有可能是正确的而不是不正确的，因此最好将其包含在父节点的MBR中。换句话说，对于一个具有n个子节点和一个包含i（i≤n）个子节点的MBR的父地点，一个随机子节点位置被包含在MBR中的概率可以写成0Track: Web Search and Mining WWW 2018, April 23-27, 2018, Lyon, Francefor OSMNames respectively. One may observe that the probabilitythat an arbitrary location is placed under a correct parent is rela-tively high; hence based on this empirical result and without muchadditional knowledge of which places may be correct or incorrectchildren, an arbitrarily chosen child is more likely to be correctthan incorrect hence better be included in the parent MBR. In otherwords, for a parent place with n children and an MBR that includesi (i ≤ n) of its children, the probability that a random child locationof the parent is enclosed in the MBR can be written asTrack: Web Search and MiningWWW 2018, April 23-27, 2018, Lyon, France16660P(children=i0n.(2)0将其放在一起：假设在方程1和方程2中两个事件是独立的，我们可以将这两个概率组合成一个目标函数。给定一个中心为c、MBR面积为A和子集S的地点，我们希望找到一个子集S'�S，使得0argmax S ′ � S ( P children  ∙  P0满足 area ( MBR ( S ′ )) ≤  A（3）0其中 area(MBR( S ′ )) 指的是由S′中的位置形成的MBR的面积。其他条件相同，模型选择一个中心点与给定中心c最接近的MBR。方程3提供了一种对MBR中位置的包含和排除以及对MBR中心的高确定性估计的建模方法。03.3.2优化。优化方程3可能需要大量计算，因为MBR的可能数量仅受S的幂集大小的限制。问题可以分为两种情况：（1）存在一个包含S中所有点和矩形且MBR的面积不大于A的MBR，（2）存在一个包含S中所有点和矩形且面积大于A的MBR。对于情况（1），包含S中所有点且面积不超过A的MBR将最大化Pchildren。正如我们在1000个地点的样本中所注意到的，找到正确的中心比包含正确的子节点更不确定，因此可以在最大化Pcenter之前最大化Pchildren。这意味着包含S中所有点的MBR可以简单地扩展（如果需要），将MBR的中心移动到给定的中心，并最大化目标函数，而不违反面积约束。现在考虑一种情况，即不存在一个包含所有子节点且面积小于等于A的MBR。根据同样的推理，我们可以在插入Pcenter之前优化Pchildren。朴素算法：执行此优化的一种朴素方法是枚举所有可能的MBR，并选择最大化方程3中目标函数的MBR。对于n个数据点，对于MBR的每条边，有n个可能的选择；因此有O(n^4)个MBR可供选择。在这些MBR中，算法选择最大化目标函数的MBR。对于n较大的值，这是一个昂贵的过程。我们的下一个算法在不影响结果正确性的情况下剪枝搜索空间。改进的算法：为了进一步剪枝搜索空间，可以只考虑不违反面积约束的MBR。我们的改进算法首先通过从每个方向逐个删除极端点，直到满足面积约束，找到一个初始解。然后，算法尝试在满足面积约束的前提下改进初始解。设m为找到初始解时被删除的点的数量。这设置了一个限制0算法1：当子节点都是点时，找到一个最优的MBR（根据方程3）0输入：（1）P的MBR的面积A，（2）P的中心C，（3）S - P下的n个唯一位置集合{ p 1 ... p n }01  bestMBR  ←02 maxProbability  ←  003  从每个方向逐个删除最远的点04 在每次删除后，为剩余的点形成一个MBR。当面积 ≤ A时停止，并将此时的MBR记为M’05  设 m 为严格在M’之外的点的数量06 对于 i = 0 到07 对于 j = 0 到 m-i，执行以下操作08 对于 k = 0 到 m-i-j，执行以下操作09 对于 l = 0 到 m-i-j-k，执行以下操作010 currentMBR  ←从S中的北、东、西和南方向删除i、j、k、l个点后形成的MBR011 如果 area(currentMBR)  >  A，则012 继续013 x  ←  (i+j+k+l)  // 排除的位置数014 C’  ←  当前MBR的中心015 使用方程1中的C和C’计算P center016 P children  = (n-x)/n（如方程2所示）017 currProb  ←  P children  ∙  P center018 如果 currProb > maxProbability，则019 maxProbability ← currProb020 bestMBR ← currentMBR021 return bestMBR0MBR可以通过每个边通过的点数的数量来限制。这样的MBR有O(m^4)个。地名数据库中的错误条目数量预计只占很小一部分，因此 m预计要远小于 n。在我们对GeoNames和OSMNames的实验中，m的最大值分别为62和78，而 n的最大值分别为74765和708。在运行时间方面，改进的算法对于 n <100，比原始算法快了6个数量级，并且随着具有更多子项的地点，差距越来越大，以至于无法在运行频率为2.7GHz，内存为8GB的IntelCorei5机器上运行原始算法。在选择MBR的最后一边时，还可以进行二分搜索，将原始算法的复杂度降低到 O(n^3log(n))，改进的算法的复杂度降低到 O(m^3log(m))。改进算法的详细信息在算法1中给出。我们的概率优化模型（在我们的实验中也称为POM）的一个限制是，除非子项MBR的面积大于或等于地点的已知面积，否则优化不会发生。这个问题在我们的下一个方法中得到解决。03.4 启发式方法0由于子项（如第3.1节所述）的MBR可能因分布不均匀或缺少足够的子项位置而在形状和大小上变化很大。为了构建s =(a/lw).16670在这种情况下，可以使用启发式方法。我们的第一个启发式方法是基于检测异常值的。异常值是指错误放置的地点，地名数据库中的地点有时会被错误地放置。特别是如果错误的地点与同一父节点下的其他地点相距很远，这种错误放置可能会显示为异常值。因此，在构建MBR之前，可以使用异常值检测方法来识别和删除此类地点。在地理上使用的两种方法是箱线图[32]和袋图[25]。由于箱线图是一种单变量方法，因此可以独立地应用于纬度和经度维度。如果在任何一个维度中被分类为异常值，则可以将该点视为异常值。袋图是箱线图的双变量扩展，它生成一个凸包，其中包含50％的点（称为“袋”）和一个外环（称为“围栏”），其大小可以根据要包含的点的数量而变化。我们扩展外环，直到由封闭点形成的MBR的面积最接近或等于给定的地点面积。所有在外环之外的点都被排除在MBR之外。混合MBR可以使用其中心点和面积获得地点的MBR；也可以根据列出的子项获得地点的MBR。如果将每个MBR视为一个随机变量，对于在MBR内的点，其值为1，对于落在MBR之外的点，其值为0，则两个MBR重叠的区域是两个随机变量都取值为1的区域。由两个MBR的交集标记的矩形预计将给出边界的更可靠描述。但是，重叠区域可能比实际MBR要小得多。接下来我们讨论如何扩展此交集区域，使其面积与给定的面积相匹配。（1）具有均匀扩大的混合MBR（H-enlarge）让 l 和w 分别表示MBR的长度和宽度。扩大MBR的一种方法是通过常数 s扩大 l 和 w。给定一个面积 a，我们希望 (l + s)(w + s) 接近a。换句话说，可以通过解以下二次方程获得 s 的值0s^2 + (l + w)s + (lw - a) = 0，其中 s >0通过将东北角和西南角的纬度和经度分别向每个方向移动 s / 2度（如第3.2节中所述），可以获得扩展MBR的坐标。（2）缩放的混合MBR（H-scale）可以通过将交集区域的边缩放 s倍，使扩展MBR的面积变为 a来获得。因此，可以通过以下方式获得 s 的值0值得注意的是，在执行上述扩展之前，可能会删除异常值。此外，当两个MBR之间没有交集时，可以将扩展应用于预计更准确的MBR（在这些情况下，我们的实验使用子MBR）。例如，图2描述了使用本节讨论的不同方法获得的匈牙利布达佩斯的MBR。04改进地名词典0在地名词典中保持地点的空间范围既可以提高数据库的质量，也可以为使用它的其他应用程序带来好处。我们研究了三个这样的改进领域（有关我们的实验评估，请参见第4.1节、第4.2节和第5.2节）。0图2：使用不同方法获得的匈牙利布达佩斯的MBR（蓝色和青色点分别表示给定中心和使用POM方法获得的中心。H-enlarge的MBR与H-scale的MBR重叠，因此不可见，而使用几何方法获得的黄色MBR预计应为正方形，但由于在地球的球面上计算端点坐标和经度之间的变化距离的方式，它看起来不像一个正方形，如3.2节所讨论的。）04.1地名词典细化0地名词典的层次结构可以根据地点的空间范围进行细化，以提高其整体准确性。以下是我们尝试过的两种细化方法。更改父节点地名词典中每个父节点的最小外包矩形（MBR）应该包含其子节点的MBR。如果在地名词典中的父节点p下列出的子节点c的MBR不包含在p的MBR中，则可以考虑将c的父节点更改为其他可能的父节点。在这种情况下，可能有多个位置可以包含c的MBR，它们可能是真正的父地点，也可能不是。减少选择错误父节点的可能性的一种方法是设置一些约束条件。例如，可以将父节点从p更改为p'0如果p'是唯一可以包含c的地点。重组子节点有时候，地点没有放置在正确的层次或粒度上；理想情况下，我们希望将每个子节点放置在层次结构的最低层次。重组可以检查层次l中的每个地点c，如果c的MBR完全包含在同一层次中另一个地点p的MBR中，则可能c是p的子节点，最好将其放置在p下面。此过程可以继续进行，直到无法再进行移动为止。04.2地名词典通过地理标记进行丰富0地名词典可以通过包含或整合有关地理位置的信息（如标签、推文、新闻、照片等）来丰富。由于网络上的许多资源没有地理标记，一个相关的问题是使用地点的地理范围是否可以提高地理标记的准确性；我们在Flickr的照片和视频的地理标记上研究了这个问题。一种地理标记的方法是将地球表面划分为一组大小相等的网格单元[16, 26,27]，并预测给定照片或视频的最可能的单元格。固定大小的单元格的问题是，一个地点的空间范围可能分布在多个单元格中（当单元格太小时），或者多个地理边界可能被合并到一个单元格中（当单元格太大时），从而影响准确性。另一种方法是使用MBR来更好地维护地点之间的局部关系和边界。使用MBR进行地理标记可以分为以下两个步骤：（1）MBR预测根据一个假设，即在一个地点的边界内的不同用户可能使用相似的标签来描述该地点，可以首先使用附加的文本注释来预测照片/视频的MBR。标签t与MBR的相关性可以用用户在MBR mj内使用t来标记他/她的照片的概率来表示，即0会议：Web搜索和挖掘WWW 2018，2018年4月23日至27日，法国里昂nADM120000.27560.14510.5140.613ADM220000.18190.16550.4540.566ADM320000.16340.14620.4030.50316680对于给定的照片或视频，可以预测一个MBR。使用固定大小的单元格的问题是，一个地点的空间范围可能分布在多个单元格中（当单元格太小时），或者多个地理边界可能被合并到一个单元格中（当单元格太大时），从而影响准确性。另一种方法是使用MBR来更好地维护地点之间的局部关系和边界。使用MBR进行地理标记可以分为以下两个步骤：（1）MBR预测根据一个假设，即在一个地点的边界内的不同用户可能使用相似的标签来描述该地点，可以首先使用附加的文本注释来预测照片/视频的MBR。标签t与MBR的相关性可以用用户在MBR mj内使用t来标记他/她的照片的概率来表示，即0p(ti|Mj) = 在MBR mj 中使用标签ti的用户数0在MBR mj 中的用户数，其中Mj是MBR mj的模型。为了避免在标签在mj中未出现时将得分置零，可以使用平滑函数。使用Jelinek-Mercer平滑[34]，我们有：0p(ti|mj) = αp(ti|Mj) + (1 − α)p(ti|Mmbrs)0其中α是平滑因子，取值范围为（0，1），p(ti|Mmbrs)是所有MBRs的模型，定义为：0p(ti|Mmbrs) =使用标签ti的用户数/所0所有MBRs上的用户数。0在我们的实验中，我们将α的值设为0.8。一般来说，可以使用验证集来设置α的值，尝试不同的平滑因子的值，并选择在验证集上给出最佳MBR预测的值。假设MBR内的标签之间相互独立，具有标签t1，...，tn的测试实例T的相关性评分为：0p(T|mj) =0i = 10在我们的实验中，我们使用log(p(T|mj))作为我们的评分函数，以确保数值稳定性。需要注意的是，相关性评分可能会偏向于特定用户的标签，这些标签通常不包含任何位置信息（例如人名）。为了避免这种歧义，我们删除了只被单个用户使用的所有标签。此外，为了允许标签的局部性，将同一用户在不同单元格或MBR中视为一个新用户。最后，选择得分最高的MBR。如果找不到MBR（如果测试实例的标签在训练过程中没有出现），可以预测分配了最多照片或视频的MBR。（2）坐标估计给定照片或视频的MBR，可以基于与在网格单元格内找到坐标的相同技术来预测MBR内的实际坐标[27]。04.3 强制执行拓扑约束0通过利用MBR之间的包含关系、不相交关系、重叠关系等，可以保证地名词典的准确性和正确性。这样的约束可以分为硬约束（不可违反的约束）和软约束（可以违反但违反很少）。例如，以MBR为基础的前者的一个示例是“如果地点A的MBR不包含地点B的MBR，则地点A不是地点B的一部分或不包含地点B。”0可以违反，但违反的情况很少）。以MBR为基础的前者的一个示例是“如果地点A的MBR不包含地点B的MBR，则地点A不是地点B的一部分或不包含地点B。”0级别 地点数量 µ σ 阈值0α = 0.05 α = 0.010表1：每个级别（ADM1 =省，ADM2 =区或大城市，ADM3=地方或小镇）的MBR之间预期重叠面积及各级别显著性水平的阈值。0软约束可以根据诸如MBR之间预期重叠面积等参数进行强制执行，这可以从数据中进行估计。例如，表1显示了不同行政级别的MBR的标准化重叠面积的一些统计数据，每个统计数据都基于来自GeoNames的2000个地点的随机样本。其中，µ和σ是地点的标准化重叠面积的均值和标准差，阈值列给出了一个地点的平均标准化重叠面积的上限，该上限是使用不同显著性水平的单尾z分数的临界值（Z =1.645和2.326，分别对应于α =0.05和0.01）计算得出的，并将样本大小'n'设置为1。基于表1的软约束的示例包括：（SC1）“对于ADM2级别的任何位置，其与所有其他位置的平均标准化重叠面积不能远低于或高于平均标准化重叠面积（0.1819）”，以及（SC2）“如果ADM3级别的更新使得一个地点的平均标准化重叠面积大于0.403，则可以在α =0.05的显著性水平上拒绝更新遵循数据分布的零假设。”05 实验评估0我们根据构建的边界框的准确性和有效性来评估所提出的方法。05.1 MBR的准确性0地点边界框的准确性可以根据政府机构和国际组织等权威来源的发布数据进行衡量。我们知道的其中一个官方数据集是美国人口普查数据集3，该数据集为美国地点提供了地理边界文件。可以通过找到给定坐标的最大值和最小值来获取边界数据中地点的最小外包矩形（MBR）。我们不知道是否有类似的全面的地点边界区域列表适用于美国以外的地点，但有一些源提供尽力而为的数据。作为这样一个源，我们使用Google Reverse Geocoding API4来获取位置的“真实”边界框。GoogleMaps在文献中也被用于类似的上下文[12，17]。在我们的实验中，我们使