基于詞信息量加權的地理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.

責任編輯（責任編輯：何麗）