高勇 孟浩瀚 葉超

北京大學(xué)學(xué)報(bào)(自然科學(xué)版) 第59卷 第3期 2023年5月

Acta Scientiarum Naturalium Universitatis Pekinensis, Vol. 59, No. 3 (May 2023)

10.13209/j.0479-8023.2023.002

國(guó)家自然科學(xué)基金(41971331)資助

2022–04–28;

2022–05–11

基于空間約束的地理知識(shí)圖譜嵌入表示的負(fù)樣本生成方法

高勇?孟浩瀚 葉超

北京大學(xué)地球與空間科學(xué)學(xué)院遙感與地理信息系統(tǒng)研究所, 北京 100871;?E-mail: gaoyong@pku.edu.cn

地理知識(shí)圖譜的表示學(xué)習(xí)需要根據(jù)正樣本生成對(duì)應(yīng)的負(fù)樣本, 然而傳統(tǒng)的負(fù)樣本生成算法存在錯(cuò)誤率高、地理知識(shí)圖譜適配性差的問(wèn)題。針對(duì)這一問(wèn)題, 調(diào)整空間關(guān)系在地理知識(shí)圖譜中的表達(dá)方式, 提出基于空間約束的負(fù)樣本生成方法, 并將該方法應(yīng)用至不同的知識(shí)圖譜表示學(xué)習(xí)模型, 探討其在地理知識(shí)圖譜表示學(xué)習(xí)中的適配性。結(jié)果表明, 該算法具有較低的錯(cuò)誤率, 同時(shí)適用于常見(jiàn)的兩類知識(shí)圖譜表示模型, 能夠提高地理知識(shí)圖譜表示學(xué)習(xí)的精度, 有助于地理知識(shí)圖譜在地理研究中發(fā)揮更重要的作用。

地理知識(shí)圖譜; 表示學(xué)習(xí); 空間約束; 空間關(guān)系; 場(chǎng)所

空間(space)和場(chǎng)所(place)是表達(dá)和理解地理知識(shí)的基礎(chǔ), 其中被賦予含義的空間稱為場(chǎng)所[1–2]。場(chǎng)所知識(shí)是人們?cè)谛袨榛顒?dòng)中產(chǎn)生的, 并不斷精化的常識(shí)性認(rèn)知, 是關(guān)聯(lián)個(gè)體行為與地理空間的橋梁[3]。在地理信息科學(xué)中, 地理知識(shí)通常基于場(chǎng)所的特征和場(chǎng)所間的關(guān)系來(lái)表示。符號(hào)邏輯、地名辭典和地理本體等方法一度在地理知識(shí)表示中發(fā)揮重要作用[3–5], 但隨著大數(shù)據(jù)和地理智能的發(fā)展, 海量時(shí)空信息的產(chǎn)生伴隨著更高程度的復(fù)雜性和多樣性, 進(jìn)而導(dǎo)致地理知識(shí)的稀疏性和不完整性, 對(duì)場(chǎng)所表示提出新的挑戰(zhàn)。

作為一種新興的大規(guī)模結(jié)構(gòu)化知識(shí)建模方法, 知識(shí)圖譜(knowledge graph)[6]為形式化地組織地理知識(shí)提供了新途徑。知識(shí)圖譜是一個(gè)表示為=(,)的有向圖模型, 其中為實(shí)體集合,為邊集合。中的一條事實(shí)表示為一個(gè)三元組(,,), 其中∈和∈分別為頭實(shí)體和尾實(shí)體,∈表示與之間的關(guān)系。在知識(shí)圖譜中加入空間信息表達(dá)地理知識(shí)后, 產(chǎn)生地理知識(shí)圖譜(geographic know-ledge graph), 其中的和表示地理實(shí)體[7–10]。盡管地理知識(shí)圖譜還處于起步階段, 但在地理知識(shí)組織[8]、地理問(wèn)答[10]和地理知識(shí)推理[9,11]等方面已發(fā)揮明顯的作用。

為了從知識(shí)圖譜中推斷新知識(shí), 解決知識(shí)的稀疏性和不完整性等問(wèn)題, 知識(shí)圖譜表示學(xué)習(xí)方法被提出來(lái), 用于學(xué)習(xí)實(shí)體和關(guān)系在連續(xù)向量空間中的嵌入表達(dá)[12]。知識(shí)圖譜的嵌入表示模型主要分為平移距離模型(translational distance models)和語(yǔ)義匹配模型(semantics matching models)兩類, 前者包括 TransE[13]、 TransH[14]、TransR[15]、TransD[16]和TransG[17]等系列模型, 后者包括 RESCAL[18]、Dis-Mult[19]和 ComplEx[20]等模型。這些方法也在地理知識(shí)圖譜的嵌入表示中得到廣泛應(yīng)用。例如, Yan等[9]和 Qiu 等[11]均采用平移距離模型進(jìn)行地理知識(shí)圖譜的嵌入表示, 張雪英等[8]和 Mai 等[10]則采用語(yǔ)義匹配模型。

在知識(shí)圖譜表示學(xué)習(xí)過(guò)程中, 生成負(fù)樣本(ne-gative samples)是一個(gè)重要部分。知識(shí)圖譜僅基于已知的事實(shí), 以三元組的形式組織而成, 即數(shù)據(jù)集中只包含正樣本, 因此需要生成每個(gè)正樣本對(duì)應(yīng)的負(fù)樣本, 以便衡量知識(shí)圖譜表示學(xué)習(xí)訓(xùn)練中的模型損失。損失函數(shù)的一般形式為

然而, 傳統(tǒng)的隨機(jī)替換法未考慮地理實(shí)體間的空間關(guān)系, 導(dǎo)致負(fù)樣本生成的正確率偏低。例如, 相鄰的實(shí)體間不會(huì)存在包含關(guān)系, 距離越近的實(shí)體間具有相離關(guān)系的概率越小。引入這些空間約束, 可以明顯地提升地理知識(shí)圖譜負(fù)樣本生成的正確率, 從而提高地理知識(shí)圖譜表示學(xué)習(xí)的精度。同時(shí), 現(xiàn)有的眾多空間關(guān)系表達(dá)模型較為復(fù)雜, 需要對(duì)其進(jìn)行對(duì)比分析和改進(jìn), 以期簡(jiǎn)化地理知識(shí)圖譜的復(fù)雜度。因此, 本研究通過(guò)調(diào)整空間關(guān)系表達(dá)模型, 提出基于空間約束的負(fù)樣本生成方法, 并探究該方法在地理知識(shí)圖譜嵌入表示中的適配性, 促使地理知識(shí)圖譜在地理研究中發(fā)揮更重要的作用。

1 知識(shí)圖譜嵌入表示方法

知識(shí)圖譜嵌入表示是將知識(shí)圖譜中的實(shí)體表示為向量, 關(guān)系主要被表示為向量空間中的操作。常用的知識(shí)圖譜表示學(xué)習(xí)模型包括平移距離模型和語(yǔ)義匹配模型, 表 1 總結(jié)和對(duì)比這兩類模型。

最早被提出的平移距離模型是TransE[13], 它將關(guān)系視為實(shí)體在嵌入空間中的平移:

+=, (1)

其中,為頭實(shí)體向量,為尾實(shí)體向量,為頭實(shí)體與尾實(shí)體的關(guān)系向量。TransE 模型的評(píng)分函數(shù)定義如下:

f(,)=?||+–||1/2。 (2)

表1 知識(shí)圖譜嵌入表示模型對(duì)比

其中,表示單位矩陣。TransD 使用組合的投影矩陣, 分別對(duì)頭尾實(shí)體進(jìn)行投影, 使得在投影空間中滿足平移關(guān)系。然而, 矩陣乘法帶來(lái)巨大的運(yùn)算量, 不利于表示學(xué)習(xí)的訓(xùn)練。

相較于平移距離模型將事實(shí)表示為平移關(guān)系, 語(yǔ)義匹配模型使用了基于相似度的評(píng)分函數(shù)。最早提出的語(yǔ)義匹配模型 RESCAL[18]將實(shí)體分布式表示為向量, 關(guān)系表示為矩陣, 將三元組的評(píng)分函數(shù)定義為

2 地理知識(shí)圖譜的負(fù)樣本生成方法

2.1 空間約束表達(dá)

針對(duì)傳統(tǒng)知識(shí)圖譜表示學(xué)習(xí)不考慮空間約束、負(fù)樣本生成的正確率低的問(wèn)題, 本研究將空間關(guān)系模型引入地理知識(shí)圖譜?，F(xiàn)有的空間關(guān)系模型, 雖然精確度較高, 但往往過(guò)于復(fù)雜。為使空間關(guān)系模型與地理知識(shí)圖譜更好地結(jié)合, 本文分別探討空間拓?fù)潢P(guān)系、方位關(guān)系和度量關(guān)系在地理知識(shí)圖譜中的改動(dòng)和表達(dá)。

空間拓?fù)潢P(guān)系描述的是空間點(diǎn)、線、面之間的鄰接、關(guān)聯(lián)和包含關(guān)系, 常用的空間拓?fù)潢P(guān)系表示模型有交集模型和 RCC 模型。常見(jiàn)的交集模型為四交模型(4-IM)[22–23]和九交模型(9-IM)。四交模型是將空間實(shí)體劃分為內(nèi)部和邊界, 用 2×2 的矩陣表示。九交模型在四交模型的基礎(chǔ)上擴(kuò)充, 將空間實(shí)體的外部也納入空間拓?fù)潢P(guān)系的范圍, 用 3×3 的矩陣表示。RCC 模型包括 RCC8 和 RCC5[24]。RCC8 模型將空間拓?fù)潢P(guān)系分為 8 種: PO (partial overlap-ping)、TPP (tangential proper part)、NTPP (nontan-gential proper part)、EQ (equal)、NTPP?1(nontan-gential proper part?1)、TPP?1(tangential proper part?1)、EC (external connected)和 DC (disconnected)。RCC5在 RCC8 的基礎(chǔ)上將空間拓?fù)潢P(guān)系簡(jiǎn)化, 不區(qū)分TPP 與 NTPP, 只用 PP (proper part)表示包含關(guān)系; 不區(qū)分 TPP?1與 NTPP?1, 只用PP?1(proper part?1)表示被包含關(guān)系; 不區(qū)分 EC 與 DC, 只用 DR(discrete)表示。因此, RCC5 包括 PO, PP, EQ, PP?1和 DR 這5 種空間拓?fù)潢P(guān)系。由于 DC 關(guān)系無(wú)法構(gòu)成地理知識(shí)圖譜中的三元組, 本文將 RCC5 中的 DR 關(guān)系細(xì)分為 EC 和 DC, 改動(dòng)后的模型稱為 RCC5+, 包括相鄰關(guān)系(EC)、包含關(guān)系(PP)、被包含關(guān)系(PP?1)、重疊關(guān)系(PO)、相等關(guān)系(EQ)和相離關(guān)系(DC)。這6 種關(guān)系具有互斥性, 即任意兩個(gè)空間實(shí)體之間只能存在一種拓?fù)潢P(guān)系。前 5 種拓?fù)潢P(guān)系都源于連接關(guān)系 C, 表明具有該拓?fù)潢P(guān)系的實(shí)體在空間上是相近的。

方位關(guān)系指兩個(gè)空間實(shí)體之間方向與位置的相對(duì)關(guān)系。通常以一個(gè)空間實(shí)體為中心, 描述另一個(gè)空間實(shí)體位于它的哪個(gè)方位。方位關(guān)系的表達(dá)分為主方位關(guān)系(cardinal direction relations)和內(nèi)方位關(guān)系(internal direction relations)兩種, 主方位關(guān)系包括投影法[25–26]、錐形法[27]和 MBR 法[28–29]等, 內(nèi)方位關(guān)系包括 ICD 系列模型[30]等。然而, 投影法難以得到東西南北這些正方位關(guān)系, MBR 法的方位關(guān)系矩陣難以轉(zhuǎn)化成知識(shí)圖譜中的三元組, 因此錐形法更適合表達(dá)地理知識(shí)圖譜中的空間關(guān)系。

空間對(duì)象的度量屬性包括面積和周長(zhǎng)等一元度量屬性以及距離等二元度量屬性。在知識(shí)圖譜表示學(xué)習(xí)中, 實(shí)體的一元屬性通常效果不佳, 因此很少使用[12], 因此本研究主要關(guān)注空間對(duì)象的距離這一二元屬性。為便于構(gòu)建地理知識(shí)圖譜的三元組, 空間關(guān)系中的距離需要用定性的方式表達(dá), 例如遠(yuǎn)和近。然而, 定性距離與確定遠(yuǎn)近的距離閾值以及空間實(shí)體的尺寸等因素緊密相關(guān)。因此, 本研究采用TopN 鄰近關(guān)系, 即給定距離的空間實(shí)體中, 最鄰近的個(gè)空間實(shí)體具有鄰近關(guān)系。在空間實(shí)體稀疏的區(qū)域, 為防止過(guò)度識(shí)別距離較遠(yuǎn)的實(shí)體, 需要引入距離閾值來(lái)限制鄰近關(guān)系的范圍。

在地理知識(shí)圖譜構(gòu)建及其嵌入表示的過(guò)程中, 需要區(qū)分上述 3 類空間關(guān)系的重要程度, 尤其是考慮遠(yuǎn)距離空間對(duì)象之間的空間關(guān)系表達(dá), 防止地理知識(shí)圖譜的復(fù)雜度過(guò)高。從空間拓?fù)潢P(guān)系的角度看, 相離關(guān)系(DC)是大部分遠(yuǎn)距離空間實(shí)體對(duì)應(yīng)的拓?fù)潢P(guān)系, 對(duì)于地理知識(shí)圖譜, 其中大多數(shù)是無(wú)意義的, 因此 DC 不構(gòu)成空間三元組。對(duì)于方位關(guān)系, 距離較遠(yuǎn)的實(shí)體間的方位是不重要的, 因此只需表示空間距離較近的空間實(shí)體的方位關(guān)系。對(duì)于度量關(guān)系, 距離較遠(yuǎn)的實(shí)體間不應(yīng)具有鄰近關(guān)系, 因此需設(shè)置鄰近關(guān)系的距離閾值。綜上所述, 地理知識(shí)圖譜中的空間約束關(guān)系表達(dá)應(yīng)以空間拓?fù)潢P(guān)系為主,方位關(guān)系和度量關(guān)系作為補(bǔ)充, 并且, 空間約束關(guān)系的表達(dá)應(yīng)集中在距離較近的空間實(shí)體間, 遠(yuǎn)距離的空間實(shí)體一般不構(gòu)成三元組。

2.2 負(fù)樣本生成算法

與通用知識(shí)圖譜的一般關(guān)系相比, 地理知識(shí)圖譜中的空間關(guān)系具有更明顯的關(guān)聯(lián)。利用這些空間約束, 可以顯著地提升地理知識(shí)圖譜負(fù)樣本生成的正確率?；谇懊嫣岢龅目臻g約束表達(dá)方式, 本文在生成地理知識(shí)圖譜負(fù)樣本過(guò)程中引入拓?fù)潢P(guān)系的互斥性和空間鄰近性。

替換三元組的頭實(shí)體或尾實(shí)體, 可以生成負(fù)樣本。以頭實(shí)體為例, 將(,,)中的頭實(shí)體替換為′。如圖 1 所示, 首先需要找到與尾實(shí)體存在′關(guān)系的三元組(′,′,)集合, 其中′指除去關(guān)系的剩余拓?fù)潢P(guān)系。如果集合不為空, 那么(′,′,)三元組集合中所有′與尾實(shí)體構(gòu)成的(′,,)都為正確的負(fù)三元組。若集合為空, 則考慮空間鄰近性。

如圖 1 所示, 黑色區(qū)域?yàn)樵M尾實(shí)體, 左上方灰色區(qū)域?yàn)樵M頭實(shí)體, 剩余區(qū)域?yàn)榇鎿Q空間實(shí)體, 關(guān)系為= EC。圖 1 中灰色區(qū)域, 已知與原三元組尾實(shí)體存在 EC 關(guān)系; 圖 1 中條紋區(qū)域, 地理知識(shí)圖譜中沒(méi)有存儲(chǔ)它們與的關(guān)系, 最可能與不存在 EC 關(guān)系的實(shí)體是與不連接的實(shí)體, 因此可將與存在 RCC5+拓?fù)潢P(guān)系的實(shí)體排除在外。與原三元組尾實(shí)體直接存在 RCC5+拓?fù)潢P(guān)系的實(shí)體稱為 1 階鄰近實(shí)體, 與 1 階鄰近實(shí)體存在RCC5+拓?fù)潢P(guān)系的實(shí)體稱為 2 階鄰近實(shí)體。鄰近階數(shù)越大, 排除在外的實(shí)體越多, 與不連接的概率越大。圖 1 中,=1 將去除周圍 6 個(gè)空間實(shí)體,=2將去除周圍 7 個(gè)空間實(shí)體, 待選′則為最外層的 3 個(gè), 這些′與構(gòu)成的(′, EC,)則為正確負(fù)三元組。當(dāng)采用的空間鄰近性備選′集合為空時(shí), 則采用傳統(tǒng)的負(fù)三元組生成算法。

圖1 基于空間鄰近性生成負(fù)三元組

形式化的空間負(fù)三元組頭實(shí)體算法如下。

數(shù)據(jù)及參數(shù): 輸入三元組(,,), 輸出三元組(′,,), 實(shí)體集合, 空間關(guān)系集合,階鄰近

1. 判斷是否為空間關(guān)系, 是則進(jìn)入 2, 否則使用隨機(jī)替換, 返回(′,,)

3. 若′為空則轉(zhuǎn) 4, 否則隨機(jī)返回(′,,), 其中′∈H′

4. 設(shè)置鄰近集合={,},=0

5. 將包含中元素的三元組另一實(shí)體放入中,=+1, 若=則轉(zhuǎn) 6, 否則轉(zhuǎn) 5

類似地, 空間負(fù)三元組尾實(shí)體算法如下。

數(shù)據(jù)及參數(shù): 輸入三元組(,,), 輸出三元組(,,′), 實(shí)體集合, 空間關(guān)系集合,階鄰近

1. 判斷是否為空間關(guān)系, 是則進(jìn)入 2, 否則使用隨機(jī)替換, 返回(,,′)

4. 設(shè)置鄰近集合={,},=0

5. 將包含中元素的三元組另一實(shí)體放入中,=+1, 若=則轉(zhuǎn) 6, 否則轉(zhuǎn) 5

空間負(fù)三元組關(guān)系算法較為簡(jiǎn)單, 采用拓?fù)潢P(guān)系的互斥性替換不同的拓?fù)潢P(guān)系即可, 算法如下。

數(shù)據(jù)及參數(shù): 輸入三元組(,,), 輸出三元組(,′,), 空間關(guān)系集合

1. 判斷是否為空間關(guān)系, 是則進(jìn)入 2, 否則使用隨機(jī)替換, 返回(,′,)

2.3 精度評(píng)價(jià)

與一般機(jī)器學(xué)習(xí)或深度學(xué)習(xí)的評(píng)價(jià)任務(wù)及指標(biāo)不同, 地理知識(shí)圖譜表示學(xué)習(xí)使用以下兩個(gè)任務(wù)進(jìn)行精度評(píng)價(jià)。1)鏈接預(yù)測(cè): 給定缺失頭實(shí)體或尾實(shí)體的三元組, 讓模型去檢測(cè)知識(shí)圖譜中所有實(shí)體最符合這個(gè)缺失實(shí)體的得分, 并排序(表 2); 2)三元組分類: 判斷測(cè)試三元組是不是正確的三元組, 即二分類的準(zhǔn)確率。

平均序的計(jì)算公式如下:

平均相互序的計(jì)算公式如下:

MRR≤1, 其值越大說(shuō)明預(yù)測(cè)精度越高, 效果越好。

命中率的計(jì)算公式如下:

式(9)中, Triplet 表示鏈接預(yù)測(cè)中的三元組, 分子為預(yù)測(cè)實(shí)體排列順序小于等于的集合的元素個(gè)數(shù), Hit@越大說(shuō)明預(yù)測(cè)精度越高, 效果越好。

表2 鏈接預(yù)測(cè)任務(wù)精度評(píng)價(jià)指標(biāo)

3 實(shí)驗(yàn)與結(jié)果

3.1 數(shù)據(jù)

為構(gòu)建地理知識(shí)圖譜, 本文使用中國(guó)省級(jí)行政區(qū)劃數(shù)據(jù)、北京城市區(qū)劃數(shù)據(jù)、北京市五環(huán)內(nèi)商圈數(shù)據(jù)[31]、北京五環(huán)內(nèi)交通小區(qū)數(shù)據(jù)、北京市 250m×250m 格網(wǎng)數(shù)據(jù)和北京市興趣點(diǎn)數(shù)據(jù)(圖 2)。其中, 商圈單元是基于北京市興趣點(diǎn)數(shù)據(jù), 用模糊集方法[31]得到的。針對(duì)每個(gè)商圈包含的興趣點(diǎn)及其簽到量進(jìn)行核密度估計(jì), 利用等值線截取的方法劃定各個(gè)商圈的范圍。地理知識(shí)圖譜中的實(shí)體信息如表 3 所示, 其中的空間關(guān)系信息如表 4 所示。

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

3.2.1負(fù)樣本生成算法實(shí)驗(yàn)結(jié)果

為了檢驗(yàn)負(fù)樣本生成算法的效果, 按照不同比例, 將構(gòu)建的地理知識(shí)圖譜劃分成多個(gè)數(shù)據(jù)集(表5)進(jìn)行負(fù)樣本生成實(shí)驗(yàn)。

基于表 5 中 8 組數(shù)據(jù)集, 分別使用傳統(tǒng)負(fù)樣本生成算法和基于空間約束的負(fù)樣本生成算法, 隨機(jī)生成 100 萬(wàn)個(gè)負(fù)樣本。通過(guò)檢驗(yàn)生成的負(fù)樣本是否位于本文構(gòu)建的地理知識(shí)圖譜中, 即可判斷生成的負(fù)樣本正確與否(因?yàn)楸疚臉?gòu)建的地理知識(shí)圖譜中包含實(shí)體間所有的拓?fù)潢P(guān)系)。

圖2 知識(shí)圖譜地理數(shù)據(jù)

表3 地理知識(shí)圖譜實(shí)體信息

表4 地理知識(shí)圖譜空間關(guān)系信息

表5 負(fù)樣本生成數(shù)據(jù)集

圖 3 中, 橫坐標(biāo)表示生成負(fù)三元組的數(shù)據(jù)集中訓(xùn)練樣本占總體數(shù)據(jù)集的比例, 縱坐標(biāo)表示生成100 萬(wàn)個(gè)負(fù)三元組所包含的錯(cuò)誤三元組個(gè)數(shù); 圓點(diǎn)標(biāo)識(shí)的折線為傳統(tǒng)負(fù)三元組生成算法對(duì)應(yīng)的錯(cuò)誤負(fù)三元組個(gè)數(shù), 隨著訓(xùn)練集包含的空間關(guān)系增加, 所生成的負(fù)三元組錯(cuò)誤數(shù)量也增加; 三角形標(biāo)識(shí)的折線為空間負(fù)三元組算法對(duì)應(yīng)的錯(cuò)誤負(fù)三元組個(gè)數(shù), 隨著訓(xùn)練集包含的空間關(guān)系增加, 所生成的負(fù)三元組錯(cuò)誤數(shù)量基本上保持在 100 個(gè)的水平。可以發(fā)現(xiàn), 空間負(fù)三元組生成算法的效果遠(yuǎn)優(yōu)于傳統(tǒng)負(fù)三元組生成算法。傳統(tǒng)負(fù)三元組生成算法只是基于開(kāi)放世界假設(shè), 通過(guò)隨機(jī)替換正三元組成分獲得不在知識(shí)圖譜中的三元組來(lái)作為負(fù)三元組; 空間負(fù)三元組生成算法則考慮了空間關(guān)系間的互斥性, 生成負(fù)三元組的錯(cuò)誤率大大降低。地理知識(shí)圖譜中包含的空間關(guān)系越多, 會(huì)使得不包含的空間關(guān)系越少, 導(dǎo)致傳統(tǒng)負(fù)三元組生成算法的錯(cuò)誤率越高。這一結(jié)構(gòu)表明傳統(tǒng)負(fù)三元組生成算法并不適用于地理知識(shí)圖譜表示學(xué)習(xí), 發(fā)展基于空間約束的負(fù)樣本生成算法是必要的。

圖3 傳統(tǒng)負(fù)樣本生成算法與基于空間約束的負(fù)樣本生成算法結(jié)果對(duì)比

空間負(fù)三元組生成算法考慮空間關(guān)系互斥性時(shí), 可能由于所包含的空間關(guān)系數(shù)量不足, 不能找到互斥空間關(guān)系。然而, 拓?fù)潢P(guān)系是 Connect 關(guān)系的導(dǎo)出關(guān)系, 表明地理知識(shí)圖譜中所表示的拓?fù)潢P(guān)系是對(duì)鄰近空間實(shí)體的空間關(guān)系描述。因此, 空間負(fù)三元組生成算法引入階空間關(guān)系來(lái)排除鄰近相關(guān)的空間實(shí)體, 增加負(fù)三元組生成的正確率。為了驗(yàn)證階空間關(guān)系引入對(duì)負(fù)三元組生成的效果, 我們進(jìn)行不引入階空間關(guān)系(=0)和引入 1 階空間關(guān)系(=1)的對(duì)比分析。

圖 4 中, 圓點(diǎn)標(biāo)識(shí)的折線為空間負(fù)三元組算法0 階空間關(guān)系生成結(jié)果, 三角形標(biāo)識(shí)的折線為空間負(fù)三元組算法 1 階空間關(guān)系生成結(jié)果。無(wú)論是否引入階空間關(guān)系, 生成 100 萬(wàn)個(gè)負(fù)三元組的錯(cuò)誤數(shù)量都低于 150 個(gè)。隨著引入空間關(guān)系占比的增加(訓(xùn)練集抽取率上升), 錯(cuò)誤數(shù)量明顯下降。當(dāng)空間關(guān)系占全集的 70%以下時(shí), 引入 1 階空間關(guān)系生成負(fù)三元組的錯(cuò)誤率低于不引入階空間關(guān)系的錯(cuò)誤率; 當(dāng)空間關(guān)系占比大于 70%時(shí), 引入 1 階空間關(guān)系的錯(cuò)誤率略高于不引入階空間關(guān)系。隨著數(shù)據(jù)集空間關(guān)系占比增大, 其補(bǔ)集減小, 引入階空間關(guān)系會(huì)將一部分鄰近空間實(shí)體從補(bǔ)集中去除, 使得雖然補(bǔ)集中錯(cuò)誤候選實(shí)體的數(shù)量降低, 但錯(cuò)誤實(shí)體的占比升高, 最后導(dǎo)致負(fù)三元組生成錯(cuò)誤率增大。

圖4 引入N階空間關(guān)系的負(fù)樣本生成算法結(jié)果

上述兩組對(duì)比實(shí)驗(yàn)的結(jié)果表明, 空間負(fù)三元組生成算法在地理知識(shí)圖譜表示學(xué)習(xí)中的效果遠(yuǎn)優(yōu)于傳統(tǒng)的負(fù)三元組生成算法, 尤其在空間關(guān)系不充足的情況下, 空間負(fù)三元組生成算法引入階空間關(guān)系會(huì)進(jìn)一步提高負(fù)三元組生成的正確率。

3.2.2地理知識(shí)圖譜表示學(xué)習(xí)模型對(duì)比

在進(jìn)行地理知識(shí)圖譜表示學(xué)習(xí)時(shí), 使用的仍然是傳統(tǒng)的平移距離模型和語(yǔ)義匹配模型。為了研究這兩類模型對(duì)空間負(fù)樣本生成算法的適配性, 基于表 5 中的數(shù)據(jù)集 Topo-0.9, 對(duì)兩類模型進(jìn)行表示學(xué)習(xí)。平移距離模型包括 TransE, TransH, TransR 和TransD, 語(yǔ)義匹配模型包括 RESCAL 和 ComplEx。本文基于上述模型, 用空間負(fù)三元組生成算法訓(xùn)練10000 次, 使用的 Linux 服務(wù)器配置 Intel(R) Xeon (R) E5-2680 14 核 CPU, NVIDIA 1080Ti GPU, 訓(xùn)練模型程序均使用 30 個(gè)線程。

從圖 5 可以看出, TransR 和 RESCAL 的訓(xùn)練時(shí)長(zhǎng)遠(yuǎn)高于其他模型。這是由于 TransR 模型引入了關(guān)系空間(關(guān)系投影矩陣), 而 RESCAL 模型同樣用矩陣表示關(guān)系。這兩種模型進(jìn)行大量的矩陣向量乘積操作, 大大地增加了訓(xùn)練時(shí)間。因此, 對(duì)于實(shí)時(shí)性高的應(yīng)用場(chǎng)景, TransR 和 RESCAL 不適用于知識(shí)圖譜的表示學(xué)習(xí)。

圖5 表示學(xué)習(xí)模型的訓(xùn)練時(shí)長(zhǎng)

本文使用精度指標(biāo) MRR, HIT@10, HIT@3 和HIT@1, 分別對(duì)各個(gè)模型的表示學(xué)習(xí)結(jié)果進(jìn)行評(píng)估。圖 6 顯示, 平移距離模型中的 TransE, TransH, TransR 和 TransD 在綜合結(jié)果評(píng)估中具有相似的精度表現(xiàn)。TransD 的精度略高于其他 3 種模型, 可能是由于 TransD 改進(jìn)了 TransR, 將 TransR 中的關(guān)系投影矩陣分解為頭實(shí)體投影向量和尾實(shí)體投影向量, 使得模型能夠區(qū)分頭尾實(shí)體的差別。語(yǔ)義匹配模型的精度則有較大的差異, 其中 RESCAL 模型的精度遠(yuǎn)高于平移距離模型, 而 ComplEx 模型的精度則遠(yuǎn)低于所有其他模型。這可能是由于 ComplEx模型引入了復(fù)數(shù)空間, 訓(xùn)練收斂速度較慢, 訓(xùn)練10000 次仍然存在欠擬合的問(wèn)題。

為了進(jìn)一步分析不同模型對(duì)空間關(guān)系中拓?fù)潢P(guān)系表示的學(xué)習(xí)效果, 對(duì)各拓?fù)潢P(guān)系表示學(xué)習(xí)的精度分別進(jìn)行分析, 結(jié)果如圖 7 所示。

對(duì)于同為:關(guān)系的包含關(guān)系(PP)和被包含關(guān)系(PP?1), 平移距離模型具有較為相似的精度表現(xiàn)。其中, TransR 模型因引入關(guān)系投影矩陣而導(dǎo)致欠擬合, 精度比其他平移距離模型低。各語(yǔ)義匹配模型的精度差異較大: RESCAL 模型優(yōu)于所有平移距離模型; 由于欠擬合, ComplEx 模型的精度遠(yuǎn)低于所有表示學(xué)習(xí)模型。對(duì)于平移距離模型, 在包含關(guān)系中, TransH 和 TransE 的精度略高于 TransD 和TransR; 在被包含關(guān)系中, TransE 和 TransD 的精度略高于 TransH 和 TransD。

對(duì)于鄰接關(guān)系(EC), 所有模型均在 HIT@10 和HIT@3 上有一致的精度。平移距離模型仍有相似的精度, 且 TransD 模型的表示學(xué)習(xí)精度遠(yuǎn)高于其他平移距離模型。對(duì)于語(yǔ)義匹配模型, RESCAL 模型的表示學(xué)習(xí)精度仍然遠(yuǎn)優(yōu)于其他模型, 而 ComplEx模型由于欠擬合, 其表示學(xué)習(xí)精度遠(yuǎn)低于所有其他模型。

對(duì)于重疊關(guān)系(PO), 各模型的表示學(xué)習(xí)精度不同于其他關(guān)系, RESCAL 模型的精度遠(yuǎn)高于所有其他模型。其次, TransD 模型略高于 RESCAL 模型之外的其他模型。這種精度的差異與模型假設(shè)和關(guān)系性質(zhì)有關(guān)。重疊關(guān)系為對(duì)稱關(guān)系, 即(entity1, PO, entity2)→(entity2, PO, entity1)。對(duì)于平移距離模型, 對(duì)稱關(guān)系會(huì)使得關(guān)系表示為零向量, 但平移距離模型卻要求關(guān)系表示不為零向量。語(yǔ)義匹配模型要求極小化損失函數(shù) Loss=, 但該損失函數(shù)的定義要求為對(duì)稱關(guān)系。因模型假設(shè)不同的緣故, 語(yǔ)義匹配模型能更好地表示對(duì)稱關(guān)系。

圖6 地理知識(shí)圖譜表示學(xué)習(xí)模型精度對(duì)比

上述結(jié)果表明, 語(yǔ)義匹配模型中的 RESCAL 模型更適合地理知識(shí)圖譜的表示學(xué)習(xí), 平移距離模型略差于 RESCAL 模型。同時(shí), 考慮到模型訓(xùn)練耗時(shí)問(wèn)題, 由于引入矩陣乘積運(yùn)算, RESCAL 和 TransR模型訓(xùn)練耗時(shí)較長(zhǎng)。綜上所述, 同時(shí)考慮表示學(xué)習(xí)精度和訓(xùn)練耗時(shí), TransD 模型具有僅次于 RESCAL的整體表示學(xué)習(xí)精度, 且模型訓(xùn)練耗時(shí)遠(yuǎn)低于RESCAL 模型, TransD 模型更適用于地理知識(shí)圖譜的表示學(xué)習(xí)研究。

4 結(jié)論

本研究提出基于空間約束的負(fù)樣本生成方法, 并將其應(yīng)用到地理知識(shí)圖譜的表示學(xué)習(xí)中。首先, 對(duì)已有的空間關(guān)系表達(dá)方式進(jìn)行調(diào)整, 使它們可以用于地理知識(shí)圖譜中空間關(guān)系的表達(dá), 同時(shí)保持知識(shí)圖譜的復(fù)雜度不大幅度增加。然后, 根據(jù)調(diào)整后的空間關(guān)系表達(dá)方式, 提出基于空間約束的負(fù)樣本生成算法。最后, 將基于空間約束的負(fù)樣本生成算法應(yīng)用到不同類型的表示學(xué)習(xí)模型中, 評(píng)估負(fù)樣本生成算法的適配性。

本研究使用省份、區(qū)劃、商圈單元、交通小區(qū)、格網(wǎng)單元和興趣點(diǎn)進(jìn)行地理知識(shí)圖譜的構(gòu)建, 其中空間關(guān)系的表達(dá)采用調(diào)整的 RCC5+模型。實(shí)驗(yàn)結(jié)果表明, RCC5+模型有能力表達(dá)常用地理知識(shí)圖譜中的空間關(guān)系, 不會(huì)導(dǎo)致知識(shí)圖譜的復(fù)雜度大幅度增加。與傳統(tǒng)的基于隨機(jī)替換的負(fù)樣本生成算法相比, 基于空間約束的負(fù)樣本生成算法具有更高的正確率, 尤其在空間關(guān)系不充足的情況下, 引入階空間關(guān)系的空間負(fù)樣本生成算法, 可以進(jìn)一步提高負(fù)三元組生成的正確率?；诳臻g約束的負(fù)樣本生成算法適用于平移距離模型以及語(yǔ)義匹配模型這兩大類常見(jiàn)的表示學(xué)習(xí)模型。語(yǔ)義匹配模型中的RESCAL 模型具有最高的精度, 缺點(diǎn)在于訓(xùn)練耗時(shí)較長(zhǎng)。綜合考慮表示學(xué)習(xí)精度和訓(xùn)練耗時(shí), 平移距離模型中的 TransD 模型具有優(yōu)異的表現(xiàn)。

圖7 不同模型的拓?fù)潢P(guān)系表示學(xué)習(xí)精度對(duì)比

本文的研究結(jié)果表明, 地理知識(shí)圖譜能夠?qū)臻g信息進(jìn)行合理的組織和綜合表示, 將在諸多領(lǐng)域產(chǎn)生較大的應(yīng)用價(jià)值。例如, 地理知識(shí)圖譜能夠結(jié)合不同層次的空間分析單元數(shù)據(jù), 對(duì)城市問(wèn)題進(jìn)行更綜合的分析和研究, 也能夠應(yīng)用于地名消歧、地理問(wèn)答和地理知識(shí)推理等領(lǐng)域。如果地理知識(shí)圖譜能夠進(jìn)一步對(duì)模糊性關(guān)系建模, 那么還可以進(jìn)行具有模糊性的空間推理。地理知識(shí)圖譜的構(gòu)建及其嵌入表示的繼續(xù)發(fā)展, 將為上述領(lǐng)域提供更大的應(yīng)用價(jià)值。

[1] Relph E. Place and placelessness. London: Pion Press, 1976

[2] Tuan Y F. Space and place: humanistic perspective. Progress in Human Geography, 1974, 6: 233–246

[3] Purves R S, Winter S, Kuhn W. Places in Information Science. Journal of the Association for Information Science and Technology, 2019, 70(11): 1173–1182

[4] Goodchild M F. Formalizing place in geographic information systems // Burton L, Matthews S, Leung M, et al. Communities, neighborhoods, and health. New York: Springer, 2011: 21–33

[5] Scheider S, Janowicz K. Place reference systems: a constructive activity model of reference to places. Applied Ontology, 2014, 9(2): 97–127

[6] Paulheim H. Knowledge graph refinement: a survey of approaches and evaluation methods. Semantic Web Journal, 2017, 8(3): 489–508

[7] 陸鋒, 余麗, 仇培元. 論地理知識(shí)圖譜. 地球信息科學(xué)學(xué)報(bào), 2017, 19(6): 723–734

[8] 張雪英, 張春菊, 吳明光, 等. 顧及時(shí)空特征的地理知識(shí)圖譜構(gòu)建方法. 中國(guó)科學(xué): 信息科學(xué), 2020, 50(7): 1019–1032

[9] Yan B, Janowicz K, Mai G, et al. A spatially exp- licit reinforcement learning model for geographic knowledge graph summarization. Transactions in GIS, 2019, 23(3): 620–640

[10] Mai G, Janowicz K, Cai L, et al. SE-KGE: a location-aware knowledge graph embedding model for geogra-phic question answering and spatial semantic lifting. Transactions in GIS, 2020, 24: 623–655

[11] Qiu P, Gao J, Yu L, et al. Knowledge embedding with geospatial distance restriction for geographic knowle-dge graph completion. ISPRS International Journal of Geo-Information, 2019, 8(6): 254–277

[12] Wang Q, Mao Z, Wang B, et al. Knowledge graph embedding: a survey of approaches and applications. IEEE Transactions on Knowledge and Data Enginee-ring, 2017, 29(12): 2724–2743

[13] Bordes A, Usunier N, Garcia-Duran A, et al. Transla-ting embeddings for modeling multi-relational data // Burges C J C, Bottou L, Welling M, et al. Advances in neural information processing systems. Red Hook, NY: Curran Associates, 2013: 2787–2795

[14] Wang Z, Zhang J, Feng J, et al. Knowledge graph embedding by translating on hyperplanes // Procee-dings of the 28th AAAI Conference on Artificial In-telligence. Québec City, 2014: 1112–1119

[15] Lin Y, Liu Z, Sun M, et al. Learning entity and relation embeddings for knowledge graph comple- tion // Proceedings of the 29th AAAI Conference on Artificial Intelligence. Hyatt Regency Austin, 2015: 2181–2187

[16] Ji G, He S, Xu L, et al. Knowledge graph embedding via dynamic mapping matrix // Proceedings of the 53rd Annual Meeting of the Association for Com-putational Linguistics and the 7th International Joint Conference on Natural Language Processing. Beijing, 2015: 687–696

[17] Xiao H, Huang M, Zhu X. TransG: a generative model for knowledge graph embedding // Proceedings of the 54th Annual Meeting of the Association for Computa-tional Linguistics. Brelin, 2016: 2316–2325

[18] Nickel M, Tresp V, Kriegel H P. A three-way model for collective learning on multi-relational data // Pro-ceedings of the 28th International Conference on Ma-chine Learning. Bellevue, 2011: 809–816

[19] Yang B, Yih S W, He X, et al. Embedding entities and relations for learning and inference in knowle- dge bases [C/OL] // Proceedings of the International Conference on Learning Representations. (2015–08– 29) [2022–04–01]. http://arxiv.org/abs/1412.6572

[20] Trouillon T, Welbl J, Riedel S, et al. Complex em-beddings for simple link prediction // Proceedings of the 33rd International Conference on Machine Learning. New York, 2016: 2071–2080

[21] Drumond L, Rendle S, Schmidt-Thieme L. Predicting RDF triples in incomplete knowledge bases with ten-sor factorization // Proceedings of the 27th Annual ACM Symposium on Applied Computing. New York, 2012: 326–331

[22] Egenhofer M J. A formal definition of binary to-pological relationships // International conference on foundations of data organization and algorithms. Pa-ris, 1989: 457–472

[23] Egenhofer M J, Franzosa R D. Point-set topological spatial relations. International Journal of Geographi-cal Information System, 1991, 5(2): 161–174

[24] Randell D A, Cui Z, Cohn A G. A spatial logic based on regions and connection // Principles of Knowledge Representation and Reasoning: Proceedings of the 1st International Conference. Cambridge, 1992: 165–176

[25] Frank A U. Qualitative spatial reasoning: Cardinal directions as an example. International Journal of Geographical Information Science, 1996, 10(3): 269–290

[26] Ligozat G é. Reasoning about cardinal directions. Journal of Visual Languages & Computing, 1998, 9(1): 23–44

[27] Haar R. Computational models of spatial relations [R]. College Park: University of Maryland at College Park, Computer Science Center, 1976

[28] Goyal R K. Similarity assessment for cardinal direc-tions between extended spatial objects [D]. Orono: The University of Maine, 2000

[29] Goyal R K, Egenhofer M J. Similarity of cardinal directions // International Symposium on Spatial and Temporal Databases. Redondo Beach, 2001: 36–55

[30] Liu Y, Wang X, Jin X, et al. On internal cardinal direction relations // International Conference on Spa-tial Information Theory. Ellicottville, 2005: 283–299

[31] 王圣音, 劉瑜, 陳澤東, 等. 大眾點(diǎn)評(píng)數(shù)據(jù)下的城市場(chǎng)所范圍感知方法. 測(cè)繪學(xué)報(bào), 2018, 47(8): 1105–1113

A Spatially Constraint Negative Sample Generation Method for Geographic Knowledge Graph Embedding

GAO Yong?, MENG Haohan, YE Chao

Institute of Remote Sensing and Geographic Information System, School of Earth and Space Sciences, Peking University,Beijing 100871; ? E-mail: gaoyong@pku.edu.cn

Geographic knowledge graph representation learning requires generating the corresponding negative samples based on the positive ones. However, traditional negative sample generation algorithms suffer from high error rate and poor adaption to geographic knowledge graph. Aimming at this problem, a spatially constraint negative sample generation method was proposed by modifying the modeling of spatial relations. Then the method was applied to different knowledge graph representation learning models to explore its suitability in geographic knowledge graph embedding. Results show that the proposed method has a low error rate and is suitable for two common types of knowledge graph representation models. The spatially constraint negative sample generation method will improve the accuracy of geographic knowledge graph representation learning, which helps to advance geographical research.

geographic knowledge graph; representation learning; spatial constraint; spatial relationship; place