基于距離類別的多源興趣點融合算法

徐 爽，張 謙，李 琰，劉嘉勇*

(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融合方案。但本文的數據僅僅是一個城區的數據，下一步研究方向應該是大數據下的數據融合方法。