基于詞信息量加權(quán)的地理POI數(shù)據(jù)融合新方法研究

王逍翔 杜慶治 趙繼東

摘要：

伴隨著網(wǎng)絡(luò)電子地圖與位置服務(wù)（LBS）的快速發(fā)展，為了提高移動(dòng)地圖POI點(diǎn)的數(shù)據(jù)質(zhì)量，融合不同地圖服務(wù)提供商提供的數(shù)據(jù)內(nèi)容存在不一致信息。為提高數(shù)據(jù)的復(fù)用性和完善性，提出了詞信息量加權(quán)的地理POI數(shù)據(jù)融合方法，通過對(duì)地址信息中的詞進(jìn)行統(tǒng)計(jì)，計(jì)算其所包含的信息量，篩選、匹配不同來(lái)源的數(shù)據(jù)，并統(tǒng)一不同地圖經(jīng)緯度坐標(biāo)以校驗(yàn)結(jié)果，實(shí)現(xiàn)了地理數(shù)據(jù)的融合。實(shí)驗(yàn)得到了完善的POI數(shù)據(jù)集合，證明該方法具有應(yīng)用價(jià)值。

關(guān)鍵詞：

POI；信息量；地理數(shù)據(jù)；數(shù)據(jù)融合

DOIDOI：10.11907/rjdk.172625

中圖分類號(hào)：TP 301

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：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.

英文關(guān)鍵詞Key Words：POI；information content；geographical data；data fusion

0引言

近年來(lái)，隨著Web技術(shù)的迅速發(fā)展，電子地圖被廣泛使用，隨之出現(xiàn)的基于電子地圖的地理信息服務(wù)也迅速增長(zhǎng)，各種提供電子地圖服務(wù)的網(wǎng)站大量出現(xiàn)，這類網(wǎng)站在短時(shí)間里積累了大量用戶。與傳統(tǒng)地圖提供路線查詢不同，電子地圖中提供的點(diǎn)是與人們?nèi)粘Ｉ钕嚓P(guān)的位置信息點(diǎn)，對(duì)人們生活中的需求有了更詳盡的描述。POI（Point of Interest，興趣點(diǎn)） 通常包括名稱、地址、類型和經(jīng)緯度等方面信息[1]，作為生活信息服務(wù)的基礎(chǔ)，其應(yīng)用也越來(lái)越廣，如位置搜索服務(wù)、地理位置信息搜索等。

同時(shí)，由于提供電子地圖服務(wù)的網(wǎng)站不同，不同數(shù)據(jù)源之間的數(shù)據(jù)會(huì)存在不同程度差異，這些差異會(huì)使POI數(shù)據(jù)的利用受到一定限制。消除可識(shí)別的差異，將數(shù)據(jù)統(tǒng)一整合到一起，將構(gòu)建出一個(gè)內(nèi)容更完整、數(shù)據(jù)更規(guī)范的數(shù)據(jù)庫(kù)，實(shí)現(xiàn)數(shù)據(jù)充分有效利用。

POI 融合的研究包括非空間屬性方法和空間位置方法[2]。對(duì)于非空間屬性方法，1998年Cobb等[3]在進(jìn)行矢量數(shù)據(jù)標(biāo)準(zhǔn)格式文件與VPF之間的融合技術(shù)中，提出了基于知識(shí)的屬性數(shù)據(jù)匹配策略；2010年Alhwarin和Faraj[45]提出了一種快速篩選功能匹配方法；空間屬性方法結(jié)合了空間位置信息，有更好的準(zhǔn)確性，但通用性較差，代表有C Beeri等[6]在2004年提出了一種基于空間位置的地理數(shù)據(jù)融合技術(shù)。本文針對(duì)不同數(shù)據(jù)源提供的POI數(shù)據(jù)，運(yùn)用名稱地址加權(quán)相似度判斷重復(fù)數(shù)據(jù)的非空間屬性方法進(jìn)行研究，并以空間位置信息驗(yàn)證實(shí)驗(yàn)結(jié)果。

1實(shí)驗(yàn)流程及方法

1.1POI數(shù)據(jù)詞信息量統(tǒng)計(jì)

POI數(shù)據(jù)包含名稱和地址兩部分，其中兩部分都描述了實(shí)體的特征和地理方位，通過兩部分的綜合比較可以確定POI表述是否為同一實(shí)體，例如：“宏發(fā)飯店，云鶴路上段310號(hào)”、“宏發(fā)飯店（云鶴路），云鶴路310-312號(hào)”，兩個(gè)實(shí)體的POI信息都包含名稱和地址，忽略其人為命名出現(xiàn)的局部差異，在一定時(shí)空范圍內(nèi)可以判定這兩個(gè)信息表達(dá)了同一實(shí)體。名稱和地址是由長(zhǎng)度不一的詞構(gòu)成的，其中詞出現(xiàn)的頻率體現(xiàn)了其所包含的信息量，研究范圍不同，詞語(yǔ)所包含的信息量也有差異。譬如，在中國(guó)，“中國(guó)云南省昆明市宏發(fā)飯店”中的“中國(guó)”包含信息量極低，而“云南省昆明市”信息量則較高，所以統(tǒng)計(jì)研究對(duì)象的詞頻，可以有效界定本范圍中詞所具有的信息量，定量表示詞語(yǔ)在信息中的重要程度。

詞頻統(tǒng)計(jì)分為兩個(gè)部分：名字包含詞的詞頻統(tǒng)計(jì)和地址包含詞的詞頻統(tǒng)計(jì)，統(tǒng)計(jì)對(duì)象是不同源數(shù)據(jù)簡(jiǎn)單合并后的數(shù)據(jù)庫(kù)。設(shè)名字和地址包含的詞分別為Wni（i=1，2，3，…，N）、Waj（j=1，2，3，…，L），N為名字包含詞的總數(shù)，L是地址包含詞的總數(shù)，通過統(tǒng)計(jì)得到相應(yīng)的詞頻分別為Pn（Wni）、Pa（Wai），就可以計(jì)算出詞的信息量：

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

由于命名不規(guī)范，可能會(huì)出現(xiàn)名字中包含地理信息、大小寫不分和錯(cuò)誤符號(hào)的情況，所以需要對(duì)地址信息進(jìn)行預(yù)處理，以提高結(jié)果的正確率。具體地，名稱中包含地理信息的情況對(duì)結(jié)果影響最大，如“享客來(lái)西餐廳（建設(shè)路店）”、“瑞余烤魚堂（福文路店）”等，處理方法是將其中的地理信息移動(dòng)至位置描述中，之后再進(jìn)行關(guān)鍵詞統(tǒng)計(jì)，能很好地修正統(tǒng)計(jì)結(jié)果。

1.2相似度計(jì)算

1.2.1經(jīng)典相似度計(jì)算方法

用S和T 分別表示待比較的兩個(gè)字符串，文本S的長(zhǎng)度為 p，文本T的長(zhǎng)度為q。

（1）基于編輯距離的相似度。編輯距離是指兩個(gè)字串之間，由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個(gè)字符替換成另一個(gè)字符、插入一個(gè)字符、刪除一個(gè)字符。定義S、T之間的編輯距離為edit（S，T），其相似度可以表示為：

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

（2）基于最長(zhǎng)公共字符串的相似度。如果字符串G包含于兩個(gè)或兩個(gè)以上文本中，且在這些文本的共同字符串中長(zhǎng)度最長(zhǎng)，則稱之為最長(zhǎng)公共字符串（Longest Common Substring）。將最長(zhǎng)公共字符串長(zhǎng)度表示為mst（S，T），基于最長(zhǎng)公共字符串的相似度為：

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

（3）基于最長(zhǎng)公共子序列的相似度。一個(gè)數(shù)列S，若分別是兩個(gè)或多個(gè)已知序列的子序列，且是所有符合條件序列中最長(zhǎng)的，則S稱為已知序列的最長(zhǎng)公共子序列（Longest Common Subsequence，LCS）。定義最長(zhǎng)公共子序列長(zhǎng)度為mse（S，T），序列共有N個(gè)元素，li表示第i個(gè)元素的長(zhǎng)度，有：

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

則基于最長(zhǎng)公共子序列的相似度為：

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

1.2.2基于詞的信息量相似度

POI數(shù)據(jù)包含名字和地址兩個(gè)部分，設(shè)兩個(gè)POI數(shù)據(jù)分別為Ps、Pt，Ps={NWs，AWs}、Pt={NWt，AWt}，譬如{“泰咖小餐廳”， “大理市其它文華路310號(hào)”}、{“泰咖小餐廳”， “文華路310號(hào)（近火車站）”}就構(gòu)成了一對(duì)POI數(shù)據(jù)對(duì)，NWs表示Ps的名字部分，AWs表示Ps的地址部分，NWt表示Pt的名字部分，AWt表示Pt的地址部分。

經(jīng)過名稱和地址的分詞后，可得到：

NWs={nsh|0

AWs={asi|0

NWt={ntj|0

AWt={atk|0

其中，nsh、asi、ntj、atk分別表示NWs、AWs、NWt、AWt分詞后包含的詞，H、I、J、K表示各自包含詞的個(gè)數(shù)。

計(jì)算相似度之前，先要獲得NWs和NWt、AWs和AWt的最長(zhǎng)公共序列，得到公共序列：

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

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

式（7）中：nf表示名字部分中的相同詞，總數(shù)為F；ag表示地址部分中的相同詞，總數(shù)為G。獲得公共序列采用動(dòng)態(tài)規(guī)劃法[7]。用一個(gè)二維數(shù)組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）

構(gòu)建c[x，y]矩陣，這個(gè)矩陣中的每個(gè)數(shù)字代表了該行和該列之前LCS的長(zhǎng)度，現(xiàn)在以兩個(gè)名字說(shuō)明：“云南天發(fā)商務(wù)酒店總店”、“云南大理天發(fā)國(guó)際商務(wù)酒店”，經(jīng)過分詞后得到兩個(gè)序列為{“云南”，“天發(fā)”，“商務(wù)”，“酒店”，“總店”}和{“云南”，“大理”，“天發(fā)”，“國(guó)際”，“商務(wù)”，“酒店”}，過程如圖1所示。通過回溯，得到兩名字的最長(zhǎng)公共序列為{“云南”，“天發(fā)”，“商務(wù)”，“酒店”}。

在詞的比對(duì)中可能會(huì)遇到相近但不完全相同的詞，例如，“大理”和“大理市”、“賓館”和“旅館”、“XX路”和“XX街”等，建立一個(gè)近義詞庫(kù)將有效識(shí)別這些相近的詞，使結(jié)果更加合理。將近義詞識(shí)別加入到動(dòng)態(tài)規(guī)劃過程中，得到改進(jìn)的模糊匹配最長(zhǎng)公共序列，使得處理結(jié)果變?yōu)椋?/p>

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）表示名字中的一組近義詞，總數(shù)為R；（a1z，a2z）表示地址中的一組近義詞，總數(shù)為Z。這樣就可以計(jì)算名稱和地址的相似度：

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）

總相似度由名字和地址的相似度加權(quán)相加獲得，名字相似度權(quán)值為λn，地址相似度權(quán)值為λa。

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

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

1.3處理流程

1.3.1處理結(jié)果分類

POI數(shù)據(jù)融合中存在不同處理結(jié)果，所以本文將其分為3類。

類型1：與另一數(shù)據(jù)源有對(duì)應(yīng)的重復(fù)數(shù)據(jù)，例如“錦香蓉，大理市其他興國(guó)路59號(hào)（近人民北路）”和“錦香蓉，興國(guó)路59號(hào)（興國(guó)店）”兩條信息，名字與地址都可以很好地匹配，也就確定為重復(fù)數(shù)據(jù)，將兩條信息都定義為此類。

類型2：無(wú)法確定是否與另一數(shù)據(jù)源的數(shù)據(jù)對(duì)應(yīng)，但很可能有相對(duì)應(yīng)的數(shù)據(jù)，例如“德化碑名勝園，大理白族自治州大理市”和“德化碑名勝園，214國(guó)道東50米”，名字高度相似，但地址信息不足以判斷是否為同一數(shù)據(jù)，將兩條信息都定義為此類。

類型3：與另一數(shù)據(jù)源沒有對(duì)應(yīng)的數(shù)據(jù)，除掉上述兩種類型，剩余信息都?xì)w作此類。

經(jīng)過處理，將數(shù)據(jù)源中的數(shù)據(jù)分為3種類型，有利于后續(xù)處理和結(jié)果校驗(yàn)。這里定義重復(fù)數(shù)據(jù)對(duì)（Clone Pair）為滿足判定條件的相互重復(fù)的兩條數(shù)據(jù)，它包含兩個(gè)數(shù)據(jù)來(lái)自不同數(shù)據(jù)源：類型1數(shù)據(jù)，由于重復(fù)數(shù)據(jù)對(duì)不是一一映射，如圖2所示（這里假定A相似于B，B相似于C，那么A相似于C），所以定義重復(fù)數(shù)據(jù)簇（Clone Cluster）為滿足判定條件兩兩重復(fù)的一組數(shù)據(jù)，它由重復(fù)數(shù)據(jù)對(duì)合并得到，數(shù)據(jù)個(gè)數(shù)大于等于2，至少有兩個(gè)數(shù)據(jù)來(lái)自不同數(shù)據(jù)源；同時(shí)，類型2數(shù)據(jù)也可以組成存疑重復(fù)數(shù)據(jù)對(duì)（Dubious Clone Pair），表示滿足判定條件疑似相互重復(fù)的兩條數(shù)據(jù)，包含兩個(gè)數(shù)據(jù)來(lái)自不同數(shù)據(jù)源。這是本文主要要識(shí)別和驗(yàn)證的部分，關(guān)系到重復(fù)信息消除的效率和準(zhǔn)確性，篩選出這些信息方便使用其它方法判別其是否確實(shí)重復(fù)。

1.3.2具體流程

基于信息量的信息相似度判別分為名字和地址兩個(gè)部分，所以處理過程相似度的計(jì)算是分步進(jìn)行的。首先，列出所有名字中含有相同字符串的數(shù)據(jù)對(duì)，每對(duì)數(shù)據(jù)中的數(shù)據(jù)都來(lái)自不同數(shù)據(jù)源。然后，計(jì)算名字相似度、地址相似度和總相似度，大于閾值的信息對(duì)即為重復(fù)信息對(duì)，名字相似度達(dá)到一定門限但總體相似度達(dá)不到閾值的信息對(duì)將作為暫存數(shù)據(jù)；如果其地址信息包含信息量低于一定閾值，名字相似度達(dá)到一定門限，則將暫存數(shù)據(jù)中的該部分作為存疑重復(fù)數(shù)據(jù)對(duì)。重復(fù)數(shù)據(jù)對(duì)之間可能存在交叉，將交叉的地址合并后就可以得到重復(fù)數(shù)據(jù)簇，其中每個(gè)簇都表明了一組重復(fù)的數(shù)據(jù)，也就可以標(biāo)明數(shù)據(jù)源各自的類型1地址；通過存疑重復(fù)數(shù)據(jù)對(duì)也可將數(shù)據(jù)源各自的類型2地址標(biāo)明；在數(shù)據(jù)源中排除類型1、類型2數(shù)據(jù)，剩余部分就劃分為類型3數(shù)據(jù)。

依據(jù)上述方法，數(shù)據(jù)處理流程如圖3所示。

2實(shí)驗(yàn)結(jié)果及分析

2.1處理結(jié)果

本文采用從高德地圖上統(tǒng)計(jì)的2 823條和百度地圖上統(tǒng)計(jì)的6 264條環(huán)洱海餐館、旅館數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，對(duì)其進(jìn)行了處理。對(duì)數(shù)據(jù)正確率的測(cè)定，采用POI數(shù)據(jù)中的經(jīng)緯度數(shù)據(jù)結(jié)合人工判斷方法實(shí)現(xiàn)。首先，對(duì)名字和位置描述權(quán)值分配測(cè)定，通過不同權(quán)值獲得的結(jié)果對(duì)其測(cè)定正確率，得到如圖4所示的結(jié)果。同時(shí)，測(cè)定了名字權(quán)值與匹配地址對(duì)數(shù)量的關(guān)系，如圖5所示。

可以看到，名字權(quán)值λn在0.72以下時(shí)正確率基本維持不變，大于0.72時(shí)有明顯減??；同時(shí)，隨著名字權(quán)值增加，得到的匹配結(jié)果數(shù)量也不斷增加。所以，在保證正確率的前提下，為了盡量獲得足夠多的匹配結(jié)果，λn取值為0.72，λa取值為0.28。

經(jīng)過處理得到結(jié)果如表1所示，其中兩地圖匹配數(shù)不相同，是由于地址信息不是一對(duì)一匹配，可能存在交叉的情況。其中重復(fù)數(shù)據(jù)對(duì)的數(shù)目為751個(gè)，重復(fù)數(shù)據(jù)簇?cái)?shù)目為747個(gè)，存疑數(shù)據(jù)對(duì)的數(shù)目為493。消除重復(fù)信息后將數(shù)據(jù)合并后的總數(shù)據(jù)條數(shù)為7 995。

2.2結(jié)果評(píng)價(jià)

基于詞信息量的地理POI數(shù)據(jù)融合方法中，最重要部分就是重復(fù)地址的匹配，對(duì)此，采用基于最長(zhǎng)公共字符串的相似度匹配法、基于最長(zhǎng)公共子序列的相似度匹配法和基于單字信息量匹配進(jìn)行結(jié)果精確度對(duì)比。其中，基于單字信息量匹配，即不進(jìn)行分詞處理，將單個(gè)字計(jì)算信息量，其它操作與基于詞信息量的匹配相同。對(duì)比結(jié)果如圖6所示。

其中，方法1表示本文最終采用基于信息量的匹配方法，方法2表示基于最長(zhǎng)公共字符串的相似度匹配法，方法3表示基于最長(zhǎng)公共子序列的相似度匹配法，方法4表示基于單字信息量匹配。可以看到采用基于關(guān)鍵詞信息量的地址匹配方法，在匹配數(shù)目相同的情況下可以達(dá)到精度最高。

上述結(jié)果表明，本文對(duì)地址重復(fù)數(shù)據(jù)的篩選精度可達(dá)到96%，有效識(shí)別了不同數(shù)據(jù)源中包含的重復(fù)信息。對(duì)由于信息缺失而無(wú)法判斷的信息采取了歸類方法，獲得了不確定信息對(duì)，校驗(yàn)后得到其中70%為重復(fù)數(shù)據(jù)，可見其中的確包含了大量需要再處理的重復(fù)數(shù)據(jù)。經(jīng)過不確定信息處理，后續(xù)進(jìn)一步篩選重復(fù)數(shù)據(jù)的效率將會(huì)大大提高。

3結(jié)語(yǔ)

本文提出了詞信息量地理POI數(shù)據(jù)融合的流程和算法，并著重對(duì)其匹配算法進(jìn)行了對(duì)比，對(duì)比結(jié)果顯示，本文采用的相似度算法綜合了基于最長(zhǎng)公共字符串的相似度匹配法、基于最長(zhǎng)公共子序列的相似度匹配法和基于單字信息量匹配的優(yōu)點(diǎn)，達(dá)到了96%的精確度，有效識(shí)別了數(shù)據(jù)中的重復(fù)信息。進(jìn)一步，對(duì)那些無(wú)法在沒有其它數(shù)據(jù)驗(yàn)證情況下進(jìn)行準(zhǔn)確判別的數(shù)據(jù)進(jìn)行了保留分類處理，有利于后續(xù)對(duì)這部分?jǐn)?shù)據(jù)的校驗(yàn)。本方法很好地將POI數(shù)據(jù)分為3類，消除了數(shù)據(jù)冗余，進(jìn)行了數(shù)據(jù)融合，使數(shù)據(jù)形式更加規(guī)范。由于算法中并未將經(jīng)緯度作為判別數(shù)據(jù)類型的依據(jù)，僅將其作為驗(yàn)證手段之一，所以此算法可以應(yīng)用于丟失經(jīng)緯度信息的POI數(shù)據(jù)和一般形式地理數(shù)據(jù)的融合。

參考文獻(xiàn)參考文獻(xiàn)：

[1]張玲.POI 的分類標(biāo)準(zhǔn)研究[J].測(cè)繪通報(bào)，2012（10）：8284.

[2]王婷婷.基于位置與屬性的多源POI數(shù)據(jù)融合的研究[D].青島：中國(guó)海洋大學(xué)，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]劉維，陳崚.最長(zhǎng)公共子序列的快速算法及其并行實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用， 2006，26（6）：14221424.

[8]趙作鵬，尹志民，王潛平，等.一種改進(jìn)的編輯距離算法及其在數(shù)據(jù)處理中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用，2009，29：424426.

[9]鄧鵬，李霖，陳功，等.基于用戶情境的POI個(gè)性化推薦模型[J].測(cè)繪地理信息，2015，40（3）：5256.

[10]池嬌，焦利民，董婷，等.基于POI數(shù)據(jù)的城市功能區(qū)定量識(shí)別及其可視化[J].測(cè)繪地理信息，2016，41（2）：6873.

[11]龍軍.基于角色標(biāo)注的中文POI名稱匹配的研究及原型系統(tǒng)實(shí)現(xiàn)[D].重慶： 西南大學(xué)，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.

責(zé)任編輯（責(zé)任編輯：何麗）