基于PageRank實(shí)現(xiàn)顧及地理概念圖結(jié)構(gòu)的語義標(biāo)注算法優(yōu)化

梁汝鵬，李宏偉，于美嬌，李文娟

（1.信息工程大學(xué)地理空間信息學(xué)院，河南 鄭州 450052；2.72515部隊(duì)，山東 濟(jì)南 250014；3.61175部隊(duì)，江蘇 南京 210028）

語義標(biāo)注是地理信息服務(wù)語義描述的基礎(chǔ)［1］，其包含了多種模式描述的地理信息語義，如文本、遙感圖像、掃描地圖、矢量數(shù)據(jù)、空間數(shù)據(jù)庫、地理信息服務(wù)等［2］，相關(guān)學(xué)者提出了多模式空間語義標(biāo)注的概念［3，4］。本文以地理信息服務(wù)的語義標(biāo)注為研究對(duì)象，針對(duì)現(xiàn)有手工語義標(biāo)注效率和準(zhǔn)確度均較低且自動(dòng)語義標(biāo)注算法尚不成熟的問題，設(shè)計(jì)了基于地理概念匹配的半自動(dòng)服務(wù)語義標(biāo)注算法，并融合PageRank算法，實(shí)現(xiàn)顧及地理概念圖結(jié)構(gòu)的語義標(biāo)注算法優(yōu)化，建立了人工干預(yù)的服務(wù)標(biāo)注過程，有效提高了語義標(biāo)注的效率和自動(dòng)化程度。

1 基于地理概念匹配的語義標(biāo)注基線算法

語義標(biāo)注構(gòu)建本質(zhì)上是概念匹配過程，其核心是建立服務(wù)模型與領(lǐng)域本體的映射［5］。為此，本文設(shè)計(jì)了基于地理概念匹配的服務(wù)語義標(biāo)注算法（圖1），具體流程如下：1）通過網(wǎng)絡(luò)搜索引擎實(shí)現(xiàn)領(lǐng)域本體的初步訓(xùn)練，即收集與概念術(shù)語包含映射關(guān)系的文檔，通過實(shí)驗(yàn)，本文設(shè)定目標(biāo)訓(xùn)練集包含50個(gè)文檔摘錄。2）將映射文檔轉(zhuǎn)換為BOW模型描述的TF－IDF向量［6］，并標(biāo)記映射的領(lǐng)域本體實(shí)體，該向量組成了目標(biāo)訓(xùn)練集合。3）訓(xùn)練集用于實(shí)現(xiàn)質(zhì)心分類器［7］的訓(xùn)練，計(jì)算得到相應(yīng)TF－IDF向量的L2歸一化和（L2－Normalized Sum）作為質(zhì)心。4）依據(jù)上述方法，計(jì)算服務(wù)查詢映射文檔的TF－IDF向量的質(zhì)心，該TF－IDF向量組成了查詢測(cè)試集（即一組無標(biāo)記的實(shí)例集合）。5）給定一組取自測(cè)試集的TF－IDF向量，引入中心分類器實(shí)現(xiàn)分類分?jǐn)?shù)與目標(biāo)訓(xùn)練集的映射，并合計(jì)查詢向量分?jǐn)?shù)。6）分類器依據(jù)查詢向量分?jǐn)?shù)實(shí)現(xiàn)領(lǐng)域本體概念與三元組的排序，由此，為用戶提供了語義標(biāo)注需要的兩個(gè)重要部件：地理領(lǐng)域本體概念隊(duì)列及三元組隊(duì)列。

圖1 概念術(shù)語匹配基本過程Fig.1 The concept term matching process

2 顧及地理本體概念圖結(jié)構(gòu)的語義標(biāo)注算法優(yōu)化

在基于地理概念匹配的語義標(biāo)注基線算法中，未考慮本體實(shí)體間的相互關(guān)聯(lián)。針對(duì)該問題，為提高算法效率，可將領(lǐng)域本體描述為概念圖結(jié)構(gòu)，圖的頂點(diǎn)代表概念，圖的邊描述概念之間的關(guān)系。本文將顧及地理概念圖結(jié)構(gòu)的語義標(biāo)注算法與PageR－ank［8］算法結(jié)合，實(shí)現(xiàn)語義標(biāo)注算法優(yōu)化。為引入PageRank算法，地理領(lǐng)域本體需要通過概念圖的方式描述。下面將分別討論地理概念和概念關(guān)系（三元組）轉(zhuǎn)化為圖結(jié)構(gòu)表達(dá)的方法。

2.1 地理領(lǐng)域本體中概念的圖結(jié)構(gòu)轉(zhuǎn)換

本過程將地理領(lǐng)域本體概念描述為頂點(diǎn)，如果兩個(gè)概念之間存在至少一組語義關(guān)系，則相應(yīng)的地理概念頂點(diǎn)通過無向邊關(guān)聯(lián)（圖2），從地理領(lǐng)域本體構(gòu)建圖結(jié)構(gòu)的算法如下：

（1）每個(gè)概念均通過頂點(diǎn)描述。對(duì)于每對(duì)地理概念GC1、GC2，如果至少存在諸如c1－r－c2∈T或c2－r－c1∈T關(guān)系r（其中T表示地理領(lǐng)域本體三元組的集合），則建立對(duì)應(yīng)概念兩個(gè)頂點(diǎn)c1、c2之間的無向邊，并依據(jù)如下方程定義邊的權(quán)重：

（2）將每個(gè)代表查詢測(cè)試集 Q＝｛q1，q2，q3，…，qn｝的BOW向量qi以一個(gè)頂點(diǎn)表達(dá)，此時(shí)測(cè)試集描述了服務(wù)查詢；對(duì)于代表查詢的各個(gè)BOW向量qi及各個(gè)地理領(lǐng)域本體中的概念cj，如果GC（qi，cj）＞0，將代表qi的頂點(diǎn)與代表cj頂點(diǎn)之間連線，并依據(jù)GC（qi，cj）確定權(quán)重。如圖2所示，權(quán)重w1－w8可分別通過如下公式計(jì)算：

圖2 實(shí)現(xiàn)地理領(lǐng)域本體中概念的圖結(jié)構(gòu)轉(zhuǎn)換過程Fig.2 Process of constructing concepts graph from geographical domain ontology

2.2 地理領(lǐng)域本體中三元組的圖結(jié)構(gòu)轉(zhuǎn)換

通過上述過程，僅將地理概念描述為頂點(diǎn)形式，無法確定概念關(guān)系重要性（如圖3，未將權(quán)重w1、w2、w3區(qū)別對(duì)待，僅利用了三者的和），即不能實(shí)現(xiàn)三元組的排序。因此，需要對(duì)地理概念圖結(jié)構(gòu)做出修改，由此實(shí)現(xiàn)概念間語義關(guān)系重要性的測(cè)度。

圖3 包含三元組的概念圖構(gòu)建過程Fig.3 Process of constructing triples graph from geographical domain ontology

實(shí)現(xiàn)地理領(lǐng)域本體中包含三元組的概念圖構(gòu)建過程如下（圖3）：1）首先將地理概念映射為圖結(jié)構(gòu)的頂點(diǎn)，具體過程參照2.1節(jié)。2）將各個(gè)三元組c1－r－c2∈T映射為圖結(jié)構(gòu)的兩個(gè)頂點(diǎn)，分別代表關(guān)系c1－r－c2及其對(duì)應(yīng)的逆關(guān)系c2－r－1－c1。3）對(duì)于每一對(duì)地理概念c1、c2以及相應(yīng)的每對(duì)關(guān)系r（諸如c1－r－c2∈T）需進(jìn)行以下處理［9］：①通過有向邊連接地理概念c1與三元組c1－r－c2的頂點(diǎn)，并將其權(quán)重定義為GC（Q，c1－r－c2），Q＝｛q1，q2，q3，…｝表示自然語言查詢集合，即測(cè)試集。關(guān)系權(quán)重計(jì)算方程為：GC（Q，c1－r－c2）＝∑q∈QGC（q，c1－r－c2），其中GC（a，b）代表將地理概念與三元組基礎(chǔ)訓(xùn)練集輸入質(zhì)心分類器［7］訓(xùn)練，計(jì)算得到的質(zhì)心向量a與b之間的余弦相似性（Cosine Similarity）。②通過有向邊連接三元組c1－r－c2與地理概念c2的頂點(diǎn)，并將其權(quán)重定義為1。③通過有向邊連接地理概念c2與描述三元組c2－r－1－c1的頂點(diǎn)，并將其權(quán)重定義為GC（Q，c1－r－c2）。④通過有向邊連接關(guān)系c2－r－1－c1與c1的頂點(diǎn)，并將其權(quán)重定義為1。4）將表示測(cè)試集Q＝｛q1，q2，q3，…｝的BOW 向量qi映射為頂點(diǎn)，測(cè)試集合Q代表服務(wù)查詢。5）對(duì)于代表查詢的BOW向量qi以及地理本體概念，若權(quán)重GC（qi，cj）＞0，那么從qi到cj頂點(diǎn)增加有向邊，權(quán)重定義為GC（qi，cj）。

2.3 基于PageRank的半自動(dòng)語義標(biāo)注算法實(shí)現(xiàn)

實(shí)現(xiàn)地理領(lǐng)域本體的概念圖結(jié)構(gòu)轉(zhuǎn)換后，可以運(yùn)行PageRank算法，將查詢頂點(diǎn)作為PageRank算法的源頂點(diǎn)，依據(jù)與查詢?cè)错旤c(diǎn)的相關(guān)性實(shí)現(xiàn)本體概念的排序。PageRank隨機(jī)游走過程可以獲得相應(yīng)PR排序分?jǐn)?shù)，此時(shí)概念關(guān)系三元組c1－r－c2∈T“積累”了兩個(gè)不同頂點(diǎn)的排序分?jǐn)?shù)：概念關(guān)系c1－r－c2及其逆關(guān)系c2－r－1－c1，因此需要計(jì)算兩個(gè)頂點(diǎn)PR分?jǐn)?shù)的和，由此獲取三元組c1－r－c2∈T的排序分?jǐn)?shù)。當(dāng)每個(gè)地理概念及每個(gè)三元組均通過PageRank算法計(jì)算得到排序等級(jí)后，需要根據(jù)這些等級(jí)生成用于實(shí)現(xiàn)服務(wù)標(biāo)記的兩個(gè)列表：地理本體概念隊(duì)列與本體三元組隊(duì)列，并將查詢結(jié)果作為語義標(biāo)注的候選提交給用戶，從而輔助用戶實(shí)現(xiàn)標(biāo)注決策。

3 半自動(dòng)語義標(biāo)注算法評(píng)價(jià)

3.1 實(shí)驗(yàn)數(shù)據(jù)集與金標(biāo)準(zhǔn)

本實(shí)驗(yàn)中，選取明斯特大學(xué)語義交互實(shí)驗(yàn)室（Muenster Semantic Interoperability Lab，MUSIL）（http：／／semanticweb.org／wiki／musil）發(fā)布的包含手工語義標(biāo)注信息的WFS服務(wù)集，其中獲取了實(shí)驗(yàn)需要的地理領(lǐng)域本體和包含語義標(biāo)注的WFS服務(wù)測(cè)試集合。同時(shí)，每個(gè)WFS服務(wù)均關(guān)聯(lián)一組查詢集合，這些查詢可以作為實(shí)驗(yàn)中符合金標(biāo)準(zhǔn)（Golden Standard）的WFS服務(wù)資源獲取短語。該地理領(lǐng)域本體包含332個(gè)概念、141個(gè)關(guān)系以及4 362個(gè)領(lǐng)域－關(guān)系－范圍三元組

為實(shí)現(xiàn)算法評(píng)價(jià)，選用了該測(cè)試集中符合金標(biāo)準(zhǔn)并與查詢語義關(guān)聯(lián)的114個(gè)概念及96個(gè)三元組。由于獲取的金標(biāo)準(zhǔn)中包含3個(gè)部分：服務(wù)查詢、地理概念隊(duì)列、三元組隊(duì)列，因此，給定查詢集合，可以通過對(duì)比利用半自動(dòng)語義標(biāo)注算法在地理領(lǐng)域本體中獲取的與用戶查詢相關(guān)的地理概念和三元組隊(duì)列中符合金標(biāo)準(zhǔn)的數(shù)據(jù)，對(duì)算法的效果進(jìn)行“度量”，并通過ROC曲線實(shí)現(xiàn)算法生成的推薦隊(duì)列效果的評(píng)價(jià)。

3.2 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

本實(shí)驗(yàn)依據(jù)獲取的金標(biāo)準(zhǔn)，通過計(jì)算ROC曲線下的面積（Area Under the ROC Curve，AUC）（http：／／en.wikipedia.org／wiki／Receiver＿operating＿characteristic）實(shí)現(xiàn)算法效果的評(píng)價(jià)。如圖4所示，從潛在相關(guān)的實(shí)體結(jié)果排序中給定相關(guān)度最高的n個(gè)元素，ROC曲線說明了真陽性率TPR（即金標(biāo)準(zhǔn)元素包含在排序分?jǐn)?shù)最高的n個(gè)元素中的百分比）與假陽性率FPR（即非金標(biāo)準(zhǔn)元素包含在排序分?jǐn)?shù)最高的n個(gè)元素的百分比）的對(duì)比。ROC曲線定義為 ROC（n）＝（TPR，F(xiàn)PR），顯然，ROC（0）＝（0%，0%），ROC（N）＝（100%，100%），其中N代表了所有元素的總數(shù)。如果隊(duì)列是隨機(jī)獲取的，TPR與FPR將是近似相等的，在這種情況下，ROC曲線下的面積將是最佳區(qū)域的50%，如果所有的金標(biāo)準(zhǔn)元素都包含在分?jǐn)?shù)最高的隊(duì)列，在這種情況存在m，0＜m＜N，例如ROC（m）＝ （100%，0%）

圖4 ROC曲線的基本性質(zhì)Fig.4 Basic properties of the ROC curve

為了更好地理解AUC值，可以利用如下示例解釋：假設(shè)AUC值為a，地理領(lǐng)域本體概念列表含有n個(gè)元素，其中一種可能的情況是正確的標(biāo)注概念分布在最初的2（1－a）n個(gè)元素中。例如，如果AUC值為98%，而概念列表包含5 000個(gè)元素，正確的元素將分布在5 000個(gè)元素的最開始的4%元素中（如分?jǐn)?shù)最高的200個(gè)元素）。

3.3 算法比較及分析

通過測(cè)量在服務(wù)語義標(biāo)注算法返回的地理領(lǐng)域本體中概念隊(duì)列和三元組隊(duì)列包含金標(biāo)準(zhǔn)構(gòu)建部件的數(shù)量“度量”標(biāo)注算法的質(zhì)量，在測(cè)量區(qū)域中基于ROC曲線評(píng)價(jià)半自動(dòng)語義標(biāo)注算法效果。

針對(duì)經(jīng)典的概念術(shù)語匹配基線算法，首先確定其算法參數(shù)設(shè)定。通過實(shí)驗(yàn)，基于經(jīng)典的概念匹配基線算法中，概念排序獲得了91.47%的AUC值，三元組排序AUC值為93.16%，此時(shí)，并未考慮地理領(lǐng)域本體的圖結(jié)構(gòu)屬性。

進(jìn)一步針對(duì)顧及地理本體概念圖結(jié)構(gòu)的語義標(biāo)注優(yōu)化算法，其中PageRank最重要的調(diào)準(zhǔn)參數(shù)是阻尼因數(shù)（Damping Factor），本文實(shí)驗(yàn)了阻尼因數(shù)值為0.2、0.4、0.6、0.8及0.9時(shí)的情況（圖5），得出以下結(jié)論：通過AUC值的分析，說明為取得更好排序效果，針對(duì)地理概念阻尼因數(shù)應(yīng)設(shè)置為0.6，而針對(duì)三元組阻尼因數(shù)應(yīng)設(shè)置為0.8，這意味著可能需要運(yùn)行兩次PageRank算法，或?qū)⒆枘嵋蜃釉O(shè)置為0.7，從而保證兩方面在較小的質(zhì)量損失的代價(jià)下提高處理的速度。

圖5 地理領(lǐng)域本體實(shí)體列表評(píng)價(jià)結(jié)果Fig.5 Evaluation results for the two lists of proposed ontology entities

通過分析圖5，可以發(fā)現(xiàn)顧及地理本體概念圖結(jié)構(gòu)的語義標(biāo)注算法成功地實(shí)現(xiàn)了對(duì)傳統(tǒng)的經(jīng)典概念匹配基線算法的優(yōu)化，平均AUC值在地理概念排序上提高了5.48%，在三元組排序上提高了3.18%，這在應(yīng)用中意味著很大的不同。通常，基于圖結(jié)構(gòu)的算法效率是概念匹配基線算法的兩倍，同時(shí)支持用戶與圖形化語義標(biāo)注工具交互并重建查詢，獲得更好的查詢結(jié)果。

4 結(jié)論

本文設(shè)計(jì)了半自動(dòng)化的語義標(biāo)注算法，支持用戶實(shí)現(xiàn)自然語言方法的本體元素檢索，為語義標(biāo)注服務(wù)。通過引入典型的文本挖掘方法建立了語義標(biāo)注基線算法，并訓(xùn)練了一組TF－IDF向量作為分類器，同時(shí)，通過融合PageRank算法，設(shè)計(jì)了顧及本體概念圖結(jié)構(gòu)的算法優(yōu)化方案，實(shí)現(xiàn)了語義標(biāo)注算法優(yōu)化，有效提高了語義標(biāo)注效率。

［1］ 梁汝鵬，李宏偉，李文娟.基于知識(shí)標(biāo)注的地理信息語義服務(wù)框架研究［J］.地理與地理信息科學(xué)，2011，28（3）：1－6.

［2］ 鄭亮，李德仁.空間服務(wù)語義模式的地理信息服務(wù)發(fā)現(xiàn)［J］.測(cè)繪科學(xué)，2011，36（2）：127－129.

［3］ 崔巍.用本體實(shí)現(xiàn)地理信息系統(tǒng)語義集成和互操作［D］.武漢大學(xué)，2004.

［4］ 鄭茂輝，馮學(xué)智，蔣瑩瀅，等.基于描述邏輯本體的GIS多重表達(dá)［J］.測(cè)繪學(xué)報(bào)，2006，35（3）：261－266.

［5］ GRCAR M，KLIEN E，NOVAK B.Using term－matching algorithms for the annotation of geoservices［A］.Post－Proceedings of the ECML－PKDD 2007Workshops on"Prior Conceptual Knowledge in Machine Learning and Knowledge Discovery"and"Web Mining 2.0"［C］.Springer，2007.12－20.

［6］ SALTON G.Automatic Text Processing：The Transformation，Analysis，and Retrieval of Information by Computer［M］.Addison－Wesley，1989.1－23.

［7］ CARDOSO－CACHOPO，OLIVEIRA L A.Empirical Evaluation of Centroid－Based Models for Single－Label Text Categorization［R］.INSEC－ID Technical Report，2006.

［8］ PAGE L，BRIN S，MOTWANI R，et al.The PageRank Citation Ranking：Bringing Order to the Web［R］.Stanford InfoLab，1999.

［9］ FRUCHTERMAN T M，REINGOLD E M.Graph drawing by force－directed placement［J］.Software－Practice ＆ Experience，1991，21（11）：1129－1164.