點(diǎn)狀地名信息的加權(quán)泰森多邊形檢索法

張 宇，王 琦，吳文周，蘇奮振

1.中國科學(xué)院地理科學(xué)與資源研究所，北京 100101；2.中國科學(xué)院大學(xué)，北京 100049；3.北京師范大學(xué)，北京 100875

點(diǎn)狀地名信息的加權(quán)泰森多邊形檢索法

張 宇1,2,3，王 琦1,2,3，吳文周1，蘇奮振1

1.中國科學(xué)院地理科學(xué)與資源研究所，北京 100101；2.中國科學(xué)院大學(xué)，北京 100049；3.北京師范大學(xué)，北京 100875

鑒于地名庫中多數(shù)地名僅以中心點(diǎn)坐標(biāo)形式記錄其空間位置信息，缺乏其空間范圍的具體描述，造成地名檢索中的片面性和局限性，本文在深入分析地名及其空間屬性、空間關(guān)系的基礎(chǔ)上，考慮同類型地名的不同性質(zhì)在檢索中的重要作用，利用泰森多邊形在地名邊界近似中的優(yōu)勢，提出了針對點(diǎn)狀地名信息的加權(quán)泰森多邊形檢索法，依據(jù)同類型地名的面積屬性作為權(quán)重指標(biāo)構(gòu)建泰森多邊形，以近似表達(dá)地名的空間范圍，進(jìn)而描述地名間的各類空間關(guān)系；并從拓?fù)潢P(guān)系、方位關(guān)系與距離關(guān)系3個(gè)方面給出了具體公式以計(jì)算地名間的空間相似性；最后以行政區(qū)劃邊界近似與檢索為例驗(yàn)證該方法。試驗(yàn)結(jié)果表明，該方法可較好地近似表達(dá)地名空間范圍及空間關(guān)系，增強(qiáng)了檢索詞與地理信息資源在空間位置上的相似性度量，檢索結(jié)果優(yōu)于傳統(tǒng)方法。

加權(quán)泰森多邊形；地名信息檢索；地名；邊界近似；空間關(guān)系相似性

隨著地理信息技術(shù)的不斷發(fā)展及應(yīng)用的深入，每天都有大量具有地理標(biāo)記的信息資源產(chǎn)生，并借助于網(wǎng)絡(luò)傳播到全球各地供不同用戶檢索使用[1]。為快速獲取網(wǎng)絡(luò)中的地理信息資源，地名信息檢索技術(shù)正日益受到重視[2-7]。地名信息檢索一般依據(jù)檢索詞中的主題、地名和空間關(guān)系[2]，與網(wǎng)絡(luò)中具有地理標(biāo)記的各類資源描述進(jìn)行相似性匹配，進(jìn)而獲取滿足條件的資源。地名作為地名信息檢索中的重要組成部分，通常利用地名詞典或地名庫將地名解析為空間坐標(biāo)形式，然后計(jì)算空間相似性。對于具有實(shí)際邊界的面狀地名，最小外包矩形為空間范圍計(jì)算中的常見方式，且通常利用二者間的重疊面積或者Hausdorff距離[8]計(jì)算空間相似性。然而多數(shù)地名僅以中心點(diǎn)坐標(biāo)形式表達(dá)其空間位置，難以具體描述空間范圍，進(jìn)而發(fā)現(xiàn)潛在的地理信息資源，造成檢索中的片面性和局限性。

在地名信息檢索研究中，地名本體[9-10]或地名詞典[11-12]的構(gòu)建通常是地理信息資源描述中地名識別、消歧及空間關(guān)系表達(dá)的基礎(chǔ)[2，4]：地名本體是依據(jù)專家知識將地名、地名所表達(dá)的地理實(shí)體類型及空間關(guān)系等數(shù)據(jù)組織成統(tǒng)一的地名描述體系，然而本體構(gòu)建過程較為繁瑣，需要大量領(lǐng)域?qū)＜业膮⑴c，且不同組織機(jī)構(gòu)間難以形成統(tǒng)一的標(biāo)準(zhǔn)體系，不易于進(jìn)行大規(guī)模實(shí)施[5]；地名詞典是存儲具有地理坐標(biāo)屬性的地名目錄[12]，一般包括3個(gè)基本要素，即地名、要素類型及空間范圍(位置)，通常利用地理要素中心點(diǎn)表達(dá)其空間位置[13]?；谳^為成熟的地名詞典GeoNames(http:∥www.geonames.org/)，Getty Thesaurus of Geographic Names(http:∥www.getty.edu /research/tools/vocabularies/tgn/)，以及Alexandria Digital Library(http:∥legacy.alexandria.ucsb.edu/)等，當(dāng)前在地名信息集成[14-15]、地名語義增強(qiáng)[16]，以及空間相似性匹配[17-18]等方面取得眾多成就。然而在地名本體或地名詞典中，多數(shù)地名同樣存在空間范圍描述的缺失，僅以地名中心點(diǎn)坐標(biāo)形式表達(dá)其空間位置，限制了地理信息資源檢索的準(zhǔn)確性。

當(dāng)前主要存在兩種類型的地名點(diǎn)，即感興趣點(diǎn)和城市(村鎮(zhèn))點(diǎn)：前者可用于城市邊界的近似表達(dá)，而后者可用于更大行政邊界的近似表達(dá)[19]。地名點(diǎn)的信息檢索一般簡化為計(jì)算參考點(diǎn)與目標(biāo)點(diǎn)對應(yīng)的空間關(guān)系相似性[6，20]。為了實(shí)現(xiàn)點(diǎn)狀地名空間范圍的近似表達(dá)，文獻(xiàn)[1，19]研究采用基于點(diǎn)集的方法構(gòu)建地名的模糊邊界，進(jìn)而判斷目標(biāo)地名點(diǎn)與該范圍的關(guān)系。文獻(xiàn)[21—22]研究利用泰森多邊形描述同類地名點(diǎn)間的模糊空間關(guān)系，但將地名點(diǎn)視為均一性質(zhì)，忽略了地名點(diǎn)間的差異性，難以突出地名在檢索中的不同重要程度。文獻(xiàn)[23]研究基于密度表面方法描述地名點(diǎn)集的模糊邊界范圍，考慮了源地名點(diǎn)與目標(biāo)地名點(diǎn)間距離因素對檢索結(jié)果的影響，但通常難以準(zhǔn)確描述地名間的空間關(guān)系。

為解決當(dāng)前點(diǎn)狀地名信息檢索研究中的不足，本文在深入分析地名及其空間屬性、空間關(guān)系的基礎(chǔ)上，利用泰森多邊形在空間關(guān)系表達(dá)與空間范圍近似中的優(yōu)勢，且考慮同類型地名點(diǎn)性質(zhì)上的差異對檢索結(jié)果的影響，提出了針對點(diǎn)狀地名信息的加權(quán)泰森多邊形檢索法。該方法選取同類型地名所具有的面積屬性作為權(quán)重指標(biāo)構(gòu)建泰森多邊形，以形成對地名邊界的近似表達(dá)，進(jìn)而判斷各待匹配點(diǎn)與檢索點(diǎn)間所對應(yīng)的空間關(guān)系。在此基礎(chǔ)上實(shí)現(xiàn)空間關(guān)系的相似性度量，并依據(jù)空間相似性對檢索結(jié)果進(jìn)行排序。

1 點(diǎn)狀地名信息的加權(quán)泰森多邊形檢索法

由于當(dāng)前缺乏有效方法實(shí)現(xiàn)地名點(diǎn)空間范圍的近似表達(dá)，因而難以準(zhǔn)確描述地名點(diǎn)間的各類空間關(guān)系；且同類型地名點(diǎn)通常存在性質(zhì)上的差異，會影響到地名信息檢索結(jié)果的準(zhǔn)確性。鑒于以地名中心點(diǎn)表達(dá)空間位置的方式在地名信息檢索中的局限性，本文利用加權(quán)泰森多邊形實(shí)現(xiàn)地名邊界近似，由此建立地名間的近似空間關(guān)系，空間關(guān)系相似性度量也即轉(zhuǎn)換為地名面間的相似性度量，從而提高地名信息檢索效率。以下將詳細(xì)論述該方法。

1.1 加權(quán)泰森多邊形

泰森多邊形是對空間平面的一種剖分，其特點(diǎn)是多邊形內(nèi)的任何位置離該多邊形的樣點(diǎn)的距離最近，離相鄰多邊形內(nèi)樣點(diǎn)的距離遠(yuǎn)，且每個(gè)多邊形內(nèi)含且僅包含一個(gè)樣點(diǎn)，可較好地解決空間鄰接及最鄰近問題(圖1(a))：如果泰森多邊形中的任意兩點(diǎn)擁有共同的邊界，則此兩點(diǎn)的空間關(guān)系可視為相鄰關(guān)系，由此通過多邊形的包含關(guān)系查詢?nèi)我馕恢锰幍淖钹徑c(diǎn)[22]。而加權(quán)泰森多邊形則是選取空間要素的某種屬性特征賦予相應(yīng)的權(quán)重，并依據(jù)權(quán)重因子實(shí)現(xiàn)空間區(qū)域的劃分，劃分的區(qū)域大小在一定程度上代表該區(qū)域中要素在所選屬性特征上的重要性(圖1(b))[24]。鑒于同類型地名點(diǎn)間性質(zhì)上的差異，一般難以采用統(tǒng)一標(biāo)準(zhǔn)近似表達(dá)地名邊界，應(yīng)選取適當(dāng)?shù)臋?quán)重因子作為衡量地名重要性的指標(biāo)，并參與到地名邊界表達(dá)中[25]，以提高地名邊界近似的準(zhǔn)確性。

圖1 泰森多邊形示例Fig.1 Examples of Voronoi diagrams

對于平面中的任意點(diǎn)集P={P1，P2，…，Pn}(n≥3)，λi(i≥1)為各點(diǎn)所對應(yīng)的屬性因子，則區(qū)域

Vn(Pi，λi)=

(1)

將平面分為n部分，由Vn(Pi，λi)(i≥ 1)確定的平面分割方法稱為點(diǎn)的加權(quán)泰森多邊形，λi稱為點(diǎn)Pi的權(quán)重，且各分割區(qū)域中的每個(gè)點(diǎn)到該區(qū)域中心的距離與該點(diǎn)到相鄰區(qū)域中心的距離之比小于兩中心點(diǎn)的權(quán)重之比[26]。泰森多邊形可看作加權(quán)泰森多邊形在權(quán)重值相等時(shí)的一個(gè)特例。

利用加權(quán)泰森多邊形對地名邊界的近似表達(dá)，可近似計(jì)算各地名點(diǎn)對應(yīng)的空間區(qū)域面積，并判斷兩地名點(diǎn)對應(yīng)的共同邊界長度；依據(jù)地名邊界的連續(xù)性表達(dá)，近似建立地名間的各類空間關(guān)系，以支持地名信息檢索。其中，方位關(guān)系、距離關(guān)系和拓?fù)潢P(guān)系是空間關(guān)系的重要組成部分，是判斷地名間相互關(guān)系的前提，也是地名信息檢索的重要基礎(chǔ)。地名信息檢索一般可表達(dá)為地名+空間關(guān)系+屬性的形式[5]。鑒于空間關(guān)系在檢索中的重要作用，下文中將分別針對拓?fù)潢P(guān)系、方位關(guān)系和距離關(guān)系計(jì)算展開論述。

1.2 空間關(guān)系相似性計(jì)算

在地名信息檢索中，一般通過計(jì)算源地名與目標(biāo)地名在拓?fù)潢P(guān)系、方位關(guān)系或距離關(guān)系中的相似性獲取符合條件的地名信息，并依據(jù)相似度對計(jì)算結(jié)果進(jìn)行排序。本文選取地名點(diǎn)的面積作為權(quán)重指標(biāo)生成加權(quán)泰森多邊形，實(shí)現(xiàn)對地名邊界的近似表達(dá)，從而將離散地名點(diǎn)間的空間關(guān)系計(jì)算轉(zhuǎn)換為連續(xù)的地名面間的空間關(guān)系計(jì)算。鑒于地名類型及其隸屬層次關(guān)系間的差異影響地名邊界的近似性[27]，本文針對同類型且處于同一層次中的地名點(diǎn)實(shí)現(xiàn)地名邊界的近似，以減少計(jì)算中的誤差。地名間的空間關(guān)系可由拓?fù)潢P(guān)系、方位關(guān)系和距離關(guān)系中的一種或多種進(jìn)行描述，因而空間關(guān)系的相似性計(jì)算可采用以下公式

(2)

式中，sim是地名空間關(guān)系的總體相似度；simi是地名拓?fù)潢P(guān)系、方位關(guān)系或距離關(guān)系的相似度。依據(jù)此公式計(jì)算獲取各地名點(diǎn)的相似性。

1.2.1 拓?fù)潢P(guān)系

拓?fù)潢P(guān)系是空間中任意兩地理對象在連續(xù)形變后還能保持不變的相互關(guān)系，而拓?fù)潢P(guān)系模型主要有區(qū)域連接演算模型與9交模型[19]，可用于描述點(diǎn)、線、面要素間各種相互關(guān)系。本文利用加權(quán)泰森多邊形實(shí)現(xiàn)地名邊界的近似表達(dá)，因此地名點(diǎn)間拓?fù)潢P(guān)系的判斷將轉(zhuǎn)換為對地名面間拓?fù)潢P(guān)系的判斷，而面要素的拓?fù)潢P(guān)系主要有包含、被包含、相等、相交、鄰接和疊加6種。鑒于4交模型[28]在兩個(gè)面要素內(nèi)部交集、邊界交集以及相互間差集的基礎(chǔ)上建立拓?fù)潢P(guān)系描述，并利用拓?fù)渚嚯x描述拓?fù)潢P(guān)系間的關(guān)聯(lián)性，因而可方便計(jì)算任意兩地名點(diǎn)間的拓?fù)潢P(guān)系相似性。本文選取6種主要拓?fù)潢P(guān)系以評價(jià)其相似性，各拓?fù)潢P(guān)系間的拓?fù)渚嚯x度量如下表所示(表1)。

基于拓?fù)渚嚯x度量，本文構(gòu)建以下公式計(jì)算兩個(gè)拓?fù)潢P(guān)系的相似性

(3)

式中，topo_dist(x，y)是兩個(gè)拓?fù)潢P(guān)系間的拓?fù)渚嚯x；n是調(diào)節(jié)因子(本文選取n=2)，用于調(diào)節(jié)公式在拓?fù)渚嚯x變化中的收斂速度。拓?fù)潢P(guān)系相似性反比于拓?fù)渚嚯x：拓?fù)渚嚯x越大，其拓?fù)潢P(guān)系相似性越低。

表1 6種面/面關(guān)系之間的拓?fù)渚嚯x[28]Tab.1 Topological distance of area/ area relations[28]

1.2.2 方位關(guān)系

空間中任意兩個(gè)地名點(diǎn)間相對方位關(guān)系表達(dá)一般采用錐形模型[29-30]，即以源地名點(diǎn)為中心，8等分整個(gè)空間范圍(東、南、西、北、東北、東南、西南和西北)，判斷目標(biāo)地名點(diǎn)所處的空間區(qū)域，即為源地名點(diǎn)與目標(biāo)地名點(diǎn)間的相對方位關(guān)系。本文方位關(guān)系判斷針對于地名面，由于面要素可分為外部區(qū)域和內(nèi)部區(qū)域，其方位關(guān)系也應(yīng)分為外方位關(guān)系和內(nèi)方位關(guān)系，但錐形模型通常難以直接用于面要素方位關(guān)系判斷。為此當(dāng)前研究改進(jìn)錐形模型，利用面要素的最小外包矩形劃分內(nèi)外空間方位(圖2)[30-31]，以分別計(jì)算地名間的方位相似性。

面要素外方位相似性主要依據(jù)檢索詞中的方位條件，判斷目標(biāo)要素所對應(yīng)的源要素8方位區(qū)域(圖2(a))。由于目標(biāo)要素可能不完全位于源要素的一個(gè)方位區(qū)域中，存在與多個(gè)區(qū)域相交的情況，因此本文采用式(4)判斷目標(biāo)要素與源要素間方位關(guān)系

dir_sim(x,y)=

(4)

式中，x和y分別表示檢索中的目標(biāo)要素與源要素；dir_region(y)表示依據(jù)檢索詞中方位關(guān)系判斷的所需方位區(qū)域；intersection_area表示目標(biāo)要素在所需方位區(qū)域的對應(yīng)面積。面要素外方位關(guān)系的相似性計(jì)算就是計(jì)算目標(biāo)要素在所需方位區(qū)域的對應(yīng)面積與目標(biāo)要素本身面積之比，比值越大意味著相似性程度越高。當(dāng)目標(biāo)要素完全位于所需方位區(qū)域時(shí)，其相似性為1。面要素內(nèi)方位相似性計(jì)算則依據(jù)內(nèi)方位錐形模型[32]進(jìn)行相應(yīng)判斷：依據(jù)面要素的最小外包矩形9等分整個(gè)矩形區(qū)域(圖2(b))，進(jìn)而獲取9種內(nèi)方位關(guān)系，由此判斷目標(biāo)要素與源要素的內(nèi)方位關(guān)系相似性，其計(jì)算仍采用式(4)進(jìn)行。

1.2.3 距離關(guān)系

地名點(diǎn)間的距離關(guān)系一般包括定性關(guān)系和定量關(guān)系：定性關(guān)系是從認(rèn)知角度衡量源地名與目標(biāo)地名間的相對距離，其中最常見的定性關(guān)系為“周邊(附近)”關(guān)系，但由于缺乏統(tǒng)一標(biāo)準(zhǔn)實(shí)現(xiàn)定性關(guān)系的定量化，并且地名關(guān)系的定性表達(dá)具有較大模糊性，因而通常難以準(zhǔn)確計(jì)算二者定性關(guān)系的相似性；而定量關(guān)系主要依據(jù)源地名與目標(biāo)地名所處的空間位置計(jì)算二者間的相對距離，主要分為點(diǎn)-點(diǎn)、點(diǎn)-面，以及面與面的距離，而距離計(jì)算通常采用歐拉公式進(jìn)行(式(5))

(5)

式中，a(x1，y1)和b(x2，y2)分別表示源地名與目標(biāo)地名點(diǎn)的空間位置。定量距離關(guān)系的相似性可依據(jù)以下公式進(jìn)行計(jì)算

(6)

式中，a和b分別表示源地名與目標(biāo)地名的空間位置；query_dist表示檢索距離。定量距離關(guān)系的相似性計(jì)算就是計(jì)算兩地名點(diǎn)間的相對距離與檢索距離間的相近程度，目標(biāo)地名與源地名間的距離越接近相似性程度越高，當(dāng)兩地名點(diǎn)間距離大于檢索距離時(shí)，相似性程度減少為0。

定性距離關(guān)系的相似性計(jì)算，主要依據(jù)對距離遠(yuǎn)近的經(jīng)驗(yàn)性認(rèn)知，將定性距離描述轉(zhuǎn)換為定量的距離數(shù)值表達(dá)，進(jìn)而實(shí)現(xiàn)定性距離關(guān)系的定量化計(jì)算。對于空間區(qū)域內(nèi)源地名點(diǎn)與各目標(biāo)地名點(diǎn)間相鄰關(guān)系判斷，主要依據(jù)在生成的泰森多邊形中兩個(gè)相鄰地名間有且僅有一個(gè)共同邊界[22]。因此通過判斷源地名點(diǎn)與目標(biāo)地名點(diǎn)所在泰森多邊形間的相鄰關(guān)系，獲取符合條件的相鄰地名點(diǎn)。為進(jìn)一步實(shí)現(xiàn)相鄰地名距離關(guān)系相似性的排序，采用式(7)，距離越近表明兩點(diǎn)間的相似性越大

dist_sim(a,bi)=

(7)

式中，a和bi分別表示源地名點(diǎn)與第i個(gè)目標(biāo)地名點(diǎn)，而dist表示兩地名點(diǎn)間的相對距離。

另外，對于其他定性距離關(guān)系，如近、中等、遠(yuǎn)和很遠(yuǎn)等距離描述詞匯的度量，則從經(jīng)驗(yàn)性認(rèn)知的角度經(jīng)多次試驗(yàn)評估設(shè)定，主要以目標(biāo)地名點(diǎn)所在多邊形與源地名點(diǎn)所在多邊形間相隔的最少多邊形個(gè)數(shù)為基礎(chǔ)，形成兩地名點(diǎn)間定性關(guān)系定量化計(jì)算標(biāo)準(zhǔn)，以實(shí)現(xiàn)相似性計(jì)算

(8)

式中，VN表示兩地名點(diǎn)間相隔最少多邊形數(shù)目，最終定性距離的相似性計(jì)算公式如下

(9)

式中，max(dist)和min(dist)分別表示源地名點(diǎn)與目標(biāo)地名點(diǎn)間的最大、最小距離，距離越近意味著相似性越大。由于對距離遠(yuǎn)近的經(jīng)驗(yàn)性認(rèn)知依據(jù)用戶的不同而有所差異，本文制定的定量化指標(biāo)難以滿足所有人的檢索需求，但為定性關(guān)系的定量化表達(dá)提供一種解決方案。未來考慮利用專家打分法、層次分析法等確定取值范圍，以提高本文方法的有效性與準(zhǔn)確性。

2 試 驗(yàn)

為了驗(yàn)證本文所述方法，試驗(yàn)以全國行政區(qū)劃邊界近似與檢索為例，驗(yàn)證加權(quán)泰森多邊形在地名邊界近似與檢索中的可行性與有效性。由于行政區(qū)劃地名間存在較強(qiáng)的隸屬層次關(guān)系，而且地名邊界近似表達(dá)的準(zhǔn)確性與地名點(diǎn)分布情況密切相關(guān)，一般地名點(diǎn)密度越大則由此生成的泰森多邊形對地名邊界近似的精度越高。為獲取較高精度的地名邊界近似結(jié)果，本文以處于底層的地名點(diǎn)為基礎(chǔ)，將地名點(diǎn)的面積屬性作為權(quán)重指標(biāo)生成泰森多邊形，進(jìn)而計(jì)算處于其他各層地名所對應(yīng)的底層多邊形集合，并以此作為該層地名所對應(yīng)的空間范圍，最終實(shí)現(xiàn)各層次地名邊界的近似表達(dá)。

試驗(yàn)選取了全國2408個(gè)縣級的行政區(qū)劃面矢量數(shù)據(jù)為基礎(chǔ)數(shù)據(jù)，同時(shí)選取了全國344個(gè)市級的行政區(qū)劃面矢量數(shù)據(jù)及31個(gè)省級面矢量數(shù)據(jù)。為生成各層次地名的矢量點(diǎn)，試驗(yàn)以縣級地名行政區(qū)中心點(diǎn)為地名坐標(biāo)點(diǎn)對各圖層進(jìn)行處理，并將各地名所對應(yīng)的行政區(qū)面積作為字段值記錄到地名點(diǎn)中，利用ArcGIS中的相應(yīng)工具分別生成山西省地名點(diǎn)的泰森多邊形(圖3(a))與加權(quán)泰森多邊形[25](圖3(b))。在圖3(a)中，每個(gè)地名點(diǎn)間權(quán)重指標(biāo)均為1，因此對于面積較小的地名點(diǎn)其邊界近似的誤差較大；在圖3(b)中，多邊形的生成依賴于地名點(diǎn)所對應(yīng)的面積權(quán)重指標(biāo)，其邊界近似效果要優(yōu)于前者。

圖3 地名邊界近似Fig.3 Approximation of place boundary

為驗(yàn)證加權(quán)泰森多邊形在地名邊界近似中的準(zhǔn)確性，試驗(yàn)任意選取內(nèi)陸中的6省作為目標(biāo)區(qū)域，分別統(tǒng)計(jì)泰森多邊形與加權(quán)泰森多邊形在省級單位面積近似中的準(zhǔn)確性，主要利用以下公式計(jì)算

(10)

式中，A0表示原始地名面積；Ap表示近似地名面積，二者越接近意味著面積近似的準(zhǔn)確性越高。

從表2中可以看出，加權(quán)泰森多邊形與普通泰森多邊形在地名面積近似準(zhǔn)確性上均高于98%，且二者各項(xiàng)地名面積的近似程度接近，但加權(quán)泰森多邊形考慮地名點(diǎn)面積屬性在地名邊界近似中的影響，因而對于具有不同面積屬性的地名點(diǎn)，采用加權(quán)泰森多邊形更能表達(dá)其邊界范圍，進(jìn)而提高地名信息檢索的效率。

表2 近似面積準(zhǔn)確性統(tǒng)計(jì)Tab.2 Statistics of accuracy of approximation area

為驗(yàn)證該方法在地名信息檢索中的有效性，本文以全國縣級點(diǎn)矢量數(shù)據(jù)為基礎(chǔ)構(gòu)建試驗(yàn)原型系統(tǒng)，并與傳統(tǒng)以地名點(diǎn)為核心的檢索方法進(jìn)行比較。當(dāng)檢索詞為“北京以南300 km內(nèi)的城鎮(zhèn)”時(shí)，傳統(tǒng)方法是以北京中心點(diǎn)為核心采用基于錐形模型的方位判別方法，并以距離為限制條件對周邊地名進(jìn)行檢索，以返回各地名的相似性檢索結(jié)果(表3、圖4)。

而本文方法則主要考慮地名邊界的近似表達(dá)，通過建立北京與周邊地名間的外方位關(guān)系，計(jì)算北京與周邊地名空間關(guān)系的相似性(表4，圖5)。

從試驗(yàn)結(jié)果中可以看出，由于地名起算點(diǎn)的不同(后者利用地名邊界對應(yīng)最小外包矩形間的最短距離計(jì)算)，兩種方法所計(jì)算出的地名距離及其空間相似性結(jié)果顯示出較大差異。由于本文充分考慮了地名點(diǎn)的面積因素在地名邊界近似中的重要作用，利用加權(quán)泰森多邊形形成地名邊界的近似表達(dá)，從而建立地名點(diǎn)間更豐富的空間關(guān)系，可更好滿足于點(diǎn)狀地名信息檢索的需求。

圖4 傳統(tǒng)檢索結(jié)果Fig.4 Traditional retrieval result

表4 本文檢索方法Tab.4 Proposed toponym information retrieval

圖5 本文檢索結(jié)果Fig.5 Proposed retrieval result

3 討 論

本文所提出的基于加權(quán)泰森多邊形的地名邊界近似方法針對同類型地名點(diǎn)集，選取地名的面積屬性作為權(quán)重因子形成地名邊界的近似表達(dá)，進(jìn)而建立地名間的相對空間關(guān)系。地名邊界的近似精度與地名點(diǎn)分布情況密切相關(guān)，一般地名點(diǎn)分布越集中，地名邊界近似表達(dá)精度越高。另外同類型地名所代表的地理對象間存在隸屬層次關(guān)系，主要體現(xiàn)在兩者空間范圍表達(dá)上的包含性[23]。相對處于較高層次上的地名點(diǎn)，處于底層的地名點(diǎn)具有較細(xì)的空間粒度，因此可由處于底層的地名點(diǎn)近似表達(dá)處于其他層次的地名邊界，進(jìn)而支持地名間空間關(guān)系的建立。

由于泰森多邊形在解決空間鄰接及最鄰近問題上具有巨大優(yōu)勢，因此針對空間上連續(xù)的同類型地名點(diǎn)，可較為準(zhǔn)確的表達(dá)各地名點(diǎn)間的鄰接性，進(jìn)而建立各地名點(diǎn)間的空間關(guān)系。同樣針對空間上離散的同類型地名點(diǎn)，通過選取恰當(dāng)?shù)臋?quán)重指形成各地名點(diǎn)間影響范圍的模擬，將離散的地名點(diǎn)轉(zhuǎn)化為連續(xù)地名空間范圍，可近似表達(dá)各地名點(diǎn)間的鄰接性。另外針對與山峰、山谷等地形特征相關(guān)聯(lián)的地名點(diǎn)，仍可利用同類型地名點(diǎn)所具有的高程值作為權(quán)重指標(biāo)近似表達(dá)空間范圍，以支持空間相似性計(jì)算。

在處理空間關(guān)系相似性時(shí)，由于地名邊界近似表達(dá)中存在模糊性，因而在空間關(guān)系相似性計(jì)算中也存在模糊性。本文所采用的計(jì)算方法未考慮空間范圍及關(guān)系的不確定性，僅依據(jù)地名邊界的近似表達(dá)計(jì)算二者間的空間關(guān)系，從而影響了檢索結(jié)果的準(zhǔn)確性。未來考慮引入不確定場模型描述空間范圍及關(guān)系的不確定性，以表達(dá)地名周邊不同位置處的概率分布情況。依據(jù)地理學(xué)第一定律“任何事物都相關(guān)，只是相近的事物關(guān)聯(lián)更緊密”[33]，地名周邊概率分布應(yīng)與地名點(diǎn)距離成反比關(guān)系。針對空間范圍及關(guān)系的不確定場的定量化表達(dá)，實(shí)現(xiàn)地名信息檢索的不確定性計(jì)算，在一定程度上提高了檢索效率。

4 結(jié) 論

鑒于以中心點(diǎn)記錄地名空間位置的方式難以表達(dá)地名的空間范圍，造成地名信息檢索的局限性，針對點(diǎn)狀地名的邊界近似及檢索問題，本文考慮同類型地名的不同性質(zhì)在檢索中的重要作用，提出了針對點(diǎn)狀地名信息的加權(quán)泰森多邊形檢索法，依據(jù)同類型地名的面積屬性作為權(quán)重指標(biāo)構(gòu)建泰森多邊形，以近似表達(dá)地名的空間范圍，進(jìn)而建立地名間的各類空間關(guān)系，并從拓?fù)潢P(guān)系、方位關(guān)系與距離關(guān)系3個(gè)方面給出具體公式以計(jì)算其空間相似性。最后利用全國行政區(qū)劃數(shù)據(jù)進(jìn)行試驗(yàn)，相比普通泰森多邊形的地名邊界近似效果，該方法更能體現(xiàn)面積屬性差異所造成的邊界近似的差異，且其面積近似精度可達(dá)98%；另外相比通常的點(diǎn)狀地名信息檢索方法，該方法在地名邊界近似的基礎(chǔ)上實(shí)現(xiàn)地名信息檢索，更有利于空間關(guān)系表達(dá)以提高空間相似性計(jì)算效率，從而證明了該方法的有效性。未來可依據(jù)地名信息檢索的側(cè)重點(diǎn)，選擇多種要素(如地名熱度、經(jīng)濟(jì)實(shí)力及道路通達(dá)性)作為權(quán)重指標(biāo)生成加權(quán)泰森多邊形，以綜合評估各地名間的不同影響力，進(jìn)而滿足不同用戶對地名信息的檢索需求。

[1] GAO Yong，JIANG Dan，ZHONG Xiang，et al.A Point-set-based Footprint Model and Spatial Ranking Method for Geographic Information Retrieval[J].ISPRS International Journal of Geo-Information，2016，5(7)：122.

[2] JONES C B，PURVES R S.Geographical Information Retrieval[J].International Journal of Geographical Information Science，2008，22(3)：219-228.

[3] KIM J，VASARDANI M，WINTER S.Similarity Matching for Integrating Spatial Information Extracted from Place Descriptions[J].International Journal of Geographical Information Science，2017，31(1)：56-80.

[4] VASARDANI M，WINTER S，RICHTER K F.Locating Place Names from Place Descriptions[J].International Journal of Geographical Information Science，2013，27(12)：2509-2532.

[5] 周靜，張書亮，張小波.顧及地理實(shí)體的地名信息檢索方法研究[J].地球信息科學(xué)學(xué)報(bào)，2015，17(11)：1362-1369.

ZHOU Jing，ZHANG Shuliang，ZHANG Xiaobo.A Place Name Information Retrieval Method Considering Geographic Entity[J].Journal of Geo-information Science，2015，17(11)：1362-1369.

[6] 劉家駿，李浩然，鐘翔，等.地理信息檢索中空間相似性度量的一種模糊方法[J].地理與地理信息科學(xué)，2015，31(4)：38-42.

LIU Jiajun，LI Haoran，ZHONG Xiang，et al.A Fuzzy Method to Measure Spatial Similarity in Geographic Information Retrieval[J].Geography and Geo-information Science，2015，31(4)：38-42.

[7] 程鋼，盧小平.顧及通名語義的漢語地名相似度匹配算法[J].測繪學(xué)報(bào)，2014，43(4)：404-410，418.DOI：10.13485/j.cnki.11-2089.2014.0060.

CHENG Gang，LU Xiaoping.Matching Algorithm for Chinese Place Names by Similarity in Consideration of Semantics of General Names for Places[J].Acta Geodaetica et Cartographica Sinica，2014，43(4)：404-410，418.DOI：10.13485/j.cnki.11-2089.2014.0060.

[8] ATALLAH M J.A Linear Time Algorithm for the Hausdorff Distance between Convex Polygons[J].Information Processing Letters，1983，17(4)：207-209.

[9] 梁汝鵬，李淑霞，李文娟.基于地名本體的空間數(shù)據(jù)組織與服務(wù)研究[J].信息工程大學(xué)學(xué)報(bào)，2010，11(2)：175-179.

LIANG Rupeng，LI Shuxia，LI Wenjuan.Research on Data Management and Retrieval Service Based on Toponym Ontology[J].Journal of Information Engineering University，2010，11(2)：175-179.

[10] 王東旭，諸云強(qiáng)，潘鵬，等.地理數(shù)據(jù)空間本體構(gòu)建及其在數(shù)據(jù)檢索中的應(yīng)用[J].地球信息科學(xué)學(xué)報(bào)，2016，18(4)：443-452.

WANG Dongxu，ZHU Yunqiang，PAN Peng，et al.Construction of Geodata Spatial Ontology and Its Application in Data Retrieval[J].Journal of Geo-Information Science，2016，18(4)：443-452.

[11] LAURINI R.Geographic Ontologies，Gazetteers and Multilingualism[J].Future Internet，2015，7(1)：1-23.

[12] CARDOSO S D，AMANQUI F K，SERIQUE K J A，et al.SWI：A Semantic Web Interactive Gazetteer to Support Linked Open Data[J].Future Generation Computer Systems，2016，54(2)：389-398.

[13] GAO Song，LI Linna，LI Wenwen，et al.Constructing Gazetteers from Volunteered Big Geo-data Based on Hadoop[J].Computers，Environment and Urban Systems，2017，61(1)：172-186.

[14] MOURA T H V M，DAVIS JR C A，F(xiàn)ONSECA F T.Reference Data Enhancement for Geographic Information Retrieval Using Linked Data[J].Transactions in GIS，2016，21(4)：683-700.

[15] GRüTTER R，PURVES R S，WOTRUBA L.Evaluating Topological Queries in Linked Data Using DBpedia and GeoNames in Switzerland and Scotland[J].Transactions in GIS，2017，21(1)：114-133.

[16] JANOWICZ K，KEΒLER C.The Role of Ontology in Improving Gazetteer Interaction[J].International Journal of Geographical Information Science，2008，22(10)：1129-1157.

[17] PURVES R S，CLOUGH P，JONES C B，et al.The Design and Implementation of SPIRIT：A Spatially Aware Search Engine for Information Retrieval on the Internet[J].International Journal of Geographical Information Science，2007，21(7)：717-745.

[18] FRONTIERA P，LARSON R，RADKE J.A Comparison of Geometric Approaches to Assessing Spatial Similarity for GIR[J].International Journal of Geographical Information Science，2008，22(3)：337-360.

[19] LIU Yu，YUAN Yihong，XIAO Danqing，et al.A Point-set-based Approximation for Areal Objects：A Case Study of Representing Localities[J].Computers，Environment and Urban Systems，2010，34(1)：28-39.

[20] 張毅，鄔陽，高勇，等.基于空間陳述的定位及不確定性研究[J].地球信息科學(xué)學(xué)報(bào)，2013，15(1)：38-45.

ZHANG Yi，WU Yang，GAO Yong，et al.On the Description-based Spatial Positioning and the Associated Uncertainty[J].Journal of Geo-Information Science，2013，15(1)：38-45.

[21] GONG Yongxi，WU Lun，LIN Yaoyu，et al.Probability Issues in Locality Descriptions Based on Voronoi Neighbor Relationship[J].Journal of Visual Languages & Computing，2012，23(4)：213-222.

[22] ALANI H，JONES C B，TUDHOPE D.Voronoi-based Region Approximation for Geographical Information Retrieval with Gazetteers[J].International Journal of Geographical Information Science，2001，15(4)：287-306.

[23] JONES C B，PURVES R S，CLOUGH P D，et al.Modelling Vague Places with Knowledge from the Web[J].International Journal of Geographical Information Science，2008，22(10)：1045-1065.

[24] CHAKROUN H，BENIE G B，O’NEILL N T，et al.Spatial Analysis Weighting Algorithm Using Voronoi Diagrams[J].International Journal of Geographical Information Science，2000，14(4)：319-336.

[25] DONG Pinliang.Generating and Updating Multiplicatively Weighted Voronoi Diagrams for Point，Line and Polygon Features in GIS[J].Computers & Geosciences，2008，34(4)：411-421.

[26] 郭麗敏，周廷剛，蘇迎春.基于加權(quán)Voronoi圖的城市腹地界定方法研究——以成渝經(jīng)濟(jì)圈為例[J].地球信息科學(xué)學(xué)報(bào)，2014，16(3)：411-417.

GUO Limin，ZHOU Tinggang，SU Yingchun.Definition of Urban Hinterlands of Chengdu-Chongqing Economic Circle Based on Weighted Voronoi Diagram[J].Journal of Geo-Information Science，2014，16(3)：411-417.

[27] HWANG S，THILL J C.Modeling Localities with Fuzzy Sets and GIS[M]∥PETRY F E，ROBINSON V B，COBB M A.Fuzzy Modeling with Spatial Information for Geographic Problems.Berlin：Springer，2005：480-492.

[28] 鄧敏，劉文寶，馮學(xué)智.GIS面目標(biāo)間拓?fù)潢P(guān)系的形式化模型[J].測繪學(xué)報(bào)，2005，34(1)：85-90.

DENG Min，LIU Wenbao，F(xiàn)ENG Xuezhi.A Generic Model Describing Topological Relations among Area Objects in GIS[J].Acta Geodaetica et Cartographica Sinica，2005，34(1)：85-90.

[29] DU Shihong，WANG Qiao，YANG Yipeng.Fuzzy Description of Fuzzy Direction Relations and Their Similarities[C]∥Proceedings of the 12th International Conference on Geoinformatics：Geospatial Information Research：Bridging the Pacific and Atlantic.Berlin：Springer，2004：496-502.

[30] LIU Y，GUO Q H，WIECZOREK J，et al.Positioning Localities Based on Spatial Assertions[J].International Journal of Geographical Information Science，2009，23(11)：1471-1501.

[31] SKIADOPOULOS S，GIANNOUKOS C，VASSILIADIS P，et al.Computing and Handling Cardinal Direction Information[C]∥BERTINO E，CHRISTODOULAKIS S，PLEXOUSAKIS D，et al.Proceedings of the 9th International Conference on Extending Database Technology.Heraklion，Crete，Greece：Springer，2004：329-347.

[32] LIU Yu，WANG Xiaoming，JIN Xin，et al.On Internal Cardinal Direction Relations[C]∥COHN A G，MARK D M.Proceedings of International Conference COSIT.Ellicottville：Springer，2005：283-299.

[33] TOBLER W R.A Computer Movie Simulating Urban Growth in the Detroit Region[J].Economic Geography，1970，46(S1)：234-240.

A Weighted Voronoi Diagram-based Retrieval Approach for Point-like Toponym Information

ZHANG Yu1,2,3,WANG Qi1,2,3,WU Wenzhou1,SU Fenzhen1

1.State Key Laboratory of Resources and Environmental Information System，Institute of Geographic Sciences and Natural Resources Research，CAS，Beijing 100101，China；2.University of Chinese Academy of Sciences，Beijing 100049，China；3.Beijing Normal University，Beijing 100875，China

Considering the fact that most of the place names in the gazetteer record the spatial information only in the form of center coordinates，which lacks the description of the specific spatial extent of the place name，one-sidedness and limitations exist in the toponym information retrieval.Based on the fully analysis of the place names，spatial attributes and spatial relations，the paper proposes a weighted Voronoi diagram-based retrieval approach for point-like toponym information，which considers the importance of different properties of the place names belonging to the same type in the information retrieval，and takes advantage of the weighted Voronoi diagram in the boundary approximation of the place.The approach constructed weighted Voronoi diagram based on the area properties of the same type place names，and approximated the spatial extent of the place.Then，spatial relation between two places could be described，and the spatial similarity was achieved by the given equations to calculate the similarities of the topological，directional and distance relationship.The approach was verified by approximating boundaries of administrative divisions and retrieving their information.The experiment results show that the approach can be better applied in the approximation of spatial extents and relations of place names，and the spatial similarity matching between query words and geographical information resources can be improved.Finally，the proposed approach is better than the traditional approaches.

weighted Voronoi diagram；toponym information retrieval；place name；boundary approximation；spatial relation similarity

The Foundation for Innovation Research Groups of the National Natural Science Foundation of China (No.41421001)

ZHANG Yu (1987—)，male，PhD candidate，majors in marine geographical information service.

張宇，王琦，吳文周，等.點(diǎn)狀地名信息的加權(quán)泰森多邊形檢索法[J].測繪學(xué)報(bào)，2017,46(11)：1919-1926.

10.11947/j.AGCS.2017.20170125.

ZHANG Yu,WANG Qi,WU Wenzhou,et al.A Weighted Voronoi Diagram-based Retrieval Approach for Point-like Toponym Information[J].Acta Geodaetica et Cartographica Sinica,2017,46(11):1919-1926.DOI:10.11947/j.AGCS.2017.20170125.

P208

A

1001-1595(2017)11-1919-08

國家自然科學(xué)基金創(chuàng)新研究群體科學(xué)基金(41421001)

(責(zé)任編輯：宋啟凡)

2017-03-16

修回日期：2017-08-20

張宇(1987—)，男，博士生，研究方向?yàn)楹Ｑ蟮乩硇畔⒎?wù)。

E-mail：zhangyu@lreis.ac.cn