基于PageRank實現顧及地理概念圖結構的語義標注算法優化

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

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

語義標注是地理信息服務語義描述的基礎［1］，其包含了多種模式描述的地理信息語義，如文本、遙感圖像、掃描地圖、矢量數據、空間數據庫、地理信息服務等［2］，相關學者提出了多模式空間語義標注的概念［3，4］。本文以地理信息服務的語義標注為研究對象，針對現有手工語義標注效率和準確度均較低且自動語義標注算法尚不成熟的問題，設計了基于地理概念匹配的半自動服務語義標注算法，并融合PageRank算法，實現顧及地理概念圖結構的語義標注算法優化，建立了人工干預的服務標注過程，有效提高了語義標注的效率和自動化程度。

1 基于地理概念匹配的語義標注基線算法

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

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

2 顧及地理本體概念圖結構的語義標注算法優化

在基于地理概念匹配的語義標注基線算法中，未考慮本體實體間的相互關聯。針對該問題，為提高算法效率，可將領域本體描述為概念圖結構，圖的頂點代表概念，圖的邊描述概念之間的關系。本文將顧及地理概念圖結構的語義標注算法與PageR－ank［8］算法結合，實現語義標注算法優化。為引入PageRank算法，地理領域本體需要通過概念圖的方式描述。下面將分別討論地理概念和概念關系（三元組）轉化為圖結構表達的方法。

2.1 地理領域本體中概念的圖結構轉換

本過程將地理領域本體概念描述為頂點，如果兩個概念之間存在至少一組語義關系，則相應的地理概念頂點通過無向邊關聯（圖2），從地理領域本體構建圖結構的算法如下：

（1）每個概念均通過頂點描述。對于每對地理概念GC1、GC2，如果至少存在諸如c1－r－c2∈T或c2－r－c1∈T關系r（其中T表示地理領域本體三元組的集合），則建立對應概念兩個頂點c1、c2之間的無向邊，并依據如下方程定義邊的權重：

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

圖2 實現地理領域本體中概念的圖結構轉換過程Fig.2 Process of constructing concepts graph from geographical domain ontology

2.2 地理領域本體中三元組的圖結構轉換

通過上述過程，僅將地理概念描述為頂點形式，無法確定概念關系重要性（如圖3，未將權重w1、w2、w3區別對待，僅利用了三者的和），即不能實現三元組的排序。因此，需要對地理概念圖結構做出修改，由此實現概念間語義關系重要性的測度。

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

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

2.3 基于PageRank的半自動語義標注算法實現

實現地理領域本體的概念圖結構轉換后，可以運行PageRank算法，將查詢頂點作為PageRank算法的源頂點，依據與查詢源頂點的相關性實現本體概念的排序。PageRank隨機游走過程可以獲得相應PR排序分數，此時概念關系三元組c1－r－c2∈T“積累”了兩個不同頂點的排序分數：概念關系c1－r－c2及其逆關系c2－r－1－c1，因此需要計算兩個頂點PR分數的和，由此獲取三元組c1－r－c2∈T的排序分數。當每個地理概念及每個三元組均通過PageRank算法計算得到排序等級后，需要根據這些等級生成用于實現服務標記的兩個列表：地理本體概念隊列與本體三元組隊列，并將查詢結果作為語義標注的候選提交給用戶，從而輔助用戶實現標注決策。

3 半自動語義標注算法評價

3.1 實驗數據集與金標準

本實驗中，選取明斯特大學語義交互實驗室（Muenster Semantic Interoperability Lab，MUSIL）（http：／／semanticweb.org／wiki／musil）發布的包含手工語義標注信息的WFS服務集，其中獲取了實驗需要的地理領域本體和包含語義標注的WFS服務測試集合。同時，每個WFS服務均關聯一組查詢集合，這些查詢可以作為實驗中符合金標準（Golden Standard）的WFS服務資源獲取短語。該地理領域本體包含332個概念、141個關系以及4 362個領域－關系－范圍三元組

為實現算法評價，選用了該測試集中符合金標準并與查詢語義關聯的114個概念及96個三元組。由于獲取的金標準中包含3個部分：服務查詢、地理概念隊列、三元組隊列，因此，給定查詢集合，可以通過對比利用半自動語義標注算法在地理領域本體中獲取的與用戶查詢相關的地理概念和三元組隊列中符合金標準的數據，對算法的效果進行“度量”，并通過ROC曲線實現算法生成的推薦隊列效果的評價。

3.2 實驗評價指標

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

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

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

3.3 算法比較及分析

通過測量在服務語義標注算法返回的地理領域本體中概念隊列和三元組隊列包含金標準構建部件的數量“度量”標注算法的質量，在測量區域中基于ROC曲線評價半自動語義標注算法效果。

針對經典的概念術語匹配基線算法，首先確定其算法參數設定。通過實驗，基于經典的概念匹配基線算法中，概念排序獲得了91.47%的AUC值，三元組排序AUC值為93.16%，此時，并未考慮地理領域本體的圖結構屬性。

進一步針對顧及地理本體概念圖結構的語義標注優化算法，其中PageRank最重要的調準參數是阻尼因數（Damping Factor），本文實驗了阻尼因數值為0.2、0.4、0.6、0.8及0.9時的情況（圖5），得出以下結論：通過AUC值的分析，說明為取得更好排序效果，針對地理概念阻尼因數應設置為0.6，而針對三元組阻尼因數應設置為0.8，這意味著可能需要運行兩次PageRank算法，或將阻尼因子設置為0.7，從而保證兩方面在較小的質量損失的代價下提高處理的速度。

圖5 地理領域本體實體列表評價結果Fig.5 Evaluation results for the two lists of proposed ontology entities

通過分析圖5，可以發現顧及地理本體概念圖結構的語義標注算法成功地實現了對傳統的經典概念匹配基線算法的優化，平均AUC值在地理概念排序上提高了5.48%，在三元組排序上提高了3.18%，這在應用中意味著很大的不同。通常，基于圖結構的算法效率是概念匹配基線算法的兩倍，同時支持用戶與圖形化語義標注工具交互并重建查詢，獲得更好的查詢結果。

4 結論

本文設計了半自動化的語義標注算法，支持用戶實現自然語言方法的本體元素檢索，為語義標注服務。通過引入典型的文本挖掘方法建立了語義標注基線算法，并訓練了一組TF－IDF向量作為分類器，同時，通過融合PageRank算法，設計了顧及本體概念圖結構的算法優化方案，實現了語義標注算法優化，有效提高了語義標注效率。

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

［2］ 鄭亮，李德仁.空間服務語義模式的地理信息服務發現［J］.測繪科學，2011，36（2）：127－129.

［3］ 崔巍.用本體實現地理信息系統語義集成和互操作［D］.武漢大學，2004.

［4］ 鄭茂輝，馮學智，蔣瑩瀅，等.基于描述邏輯本體的GIS多重表達［J］.測繪學報，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.