基于空間短文本對象的檢索策略

顧彥慧 王道勝 王永根 龍云飛 蔣鎖良 周俊生 曲維光

?

基于空間短文本對象的檢索策略

顧彥慧1,2,?王道勝3王永根1,2龍云飛4蔣鎖良1,2周俊生1,2曲維光1,2

1.南京師范大學計算機科學與技術學院, 南京 210023; 2.江蘇省信息安全保密技術工程研究中心, 南京 210023; 3.南京師范大學文學院, 南京 210097; 4.香港理工大學電子計算學系, 香港; ? E-mail: gu@njnu.edu.cn

針對傳統空間文本檢索策略中的效率和有效性問題, 對如何從給定的空間文本對象集合中快速有效地檢索出top-個近似結果進行研究?；谝粋€空間檢索的通用框架, 提出一種基于空間文本對象的快速策略, 用于滿足用戶對效率與有效性的要求。實驗結果證明該策略優于現有方法。

空間文本對象; 語義相似; top-

在基于位置的應用中, 檢索相似的空間文本對象是一個重要的研究課題, 如街旁、Foursquare服務等, 這里與位置信息有關的內容得到利用。在某個地圖上, 對于一個查詢, 檢索系統需要找到與之最相關的空間文本對象集合, 對于集合中的每一個元素, 要同時考慮空間最相近并且語義最相似。在最近的研究中, 有很多研究致力于檢索空間文本對象。總的說來, 空間對象的索引方式可以歸納為以下幾類: 1)基于R-tree的策略[1-4]; 2)基于網格的策略[5]; 3)基于空間填充曲線的策略[6-7]。對于文本信息, 主要使用基于倒排文件的策略[1-2]和基于簽名文件的策略[8]。為了檢索相似的空間文本對象, 一種直接的方法就是融合空間索引以及文本索引。根據融合策略的不同, 大體上可以分為面向空間索引的策略[6]和面向文本索引的策略[9]。然而, 這些策略是一種松散的策略, 只是把空間索引和文本索引簡單地融合在一起, 空間消耗比較大, 檢索的效率也不高。為了克服松散融合的不足, 文獻[1,2,7] 提出緊密融合的策略。

由于緊密融合策略能夠無縫地將兩種不同的索引(空間索引和文本索引)組合到一個統一的框架中, 因此在這個框架中, 每個頂點是兩種相似度的組合(空間相似度與文本相似度)。文獻[2]中引入一個新型的索引結構, 稱為IR-tree, 每個R-tree的頂點與的子樹對象內容的概要相關聯。然而, 對于空間文本對象來說, 這種文本描述往往很短, 并且有時幾乎沒有相同詞存在。對于空間文本對象來說, 文本信息比較短, 若使用傳統的詞頻計算的方式來計算文本之間的相似度, 不能得到精確的結果[1-2], 因此傳統的基于詞頻計算策略[10-13]不大適用于計算文本之間的相似度。考慮到空間文本對象的實際情況, 本文提出一種基于語義相似的文本相似度計算策略來融合相應的空間信息, 從而得到比較精確的檢索結果。

本文提出一種快速有效地檢索相似空間文本對象的策略, 其中心思想在于建立一個完整的結構, 能無縫地融合空間索引和文本索引。實驗結果表明, 由于考慮了空間文本對象文本的屬性, 本文提出的策略能有效地提高空間文本對象的檢索精度, 并且能保持較高的速度。

1 問題的提出

1.1 準備知識

假設為一空間文本數據集合。每個空間對象∈被定義為一個對象對(.,.), 其中.是一個二維的地理位置(可以用經度和維度表示),.是一個文本描述, 也就是用戶在某個地理位置的文本表達。算法要解決的問題是, 檢索出與查詢最相似的top-個空間文本對象。對于一個查詢=〈.,.,〉, 在給定的空間文本對象集合中尋找個對象, 這些對象按照相似度進行排序(這里的相似度同時考慮了空間相似度和文本相似度), 即

具體地, 對于某查詢, 對象的排序值可以用下式計算:

,

其中,S(.,.)是對象.與.之間的歐氏 距離,T(.,.)是這兩個對象之間的文本距離,。

1.2 空間臨近與文本相似

空間臨近S被定義為標準化的歐氏距離, 即

dist(.,.)是查詢對象與所有數據集中對象的歐氏距離。文本之間的相似度計算可以使用現有方法, 如語言模型[1], 余弦策略[9]或BM25[1]。因此, 文本之間的距離可以定義為

T= 1 ? Sim(.,.)。

從前面的分析可以得知, 現有的基于詞頻以及共現的模式需要有很多相同的詞出現在相似的文本中, 這種方式不適合計算兩個短文本之間的相似度, 因為兩個短文本之間雖然語義相似, 但往往只有很少的共同的詞[10-13]。為了克服短句的不足, 很多研究致力于解決短文本相似度的計算問題, 總的來說可以分為基于知識的策略[12]、基于語料庫的策 略[10-11]、基于語法的策略[11]以及混合策略[10,13]。

為了計算文本之間的相似度S(.,.), 我們使用最新的短文本相似度計算方法來組合不同的相似度計算策略[10,13]。需要強調的是, 短文本由詞組成, 因此計算短文本間的相似度歸根到底是計算詞與詞之間的相似度[10,13]。

1.3 通用框架模型

有很多工作致力于研究快速檢索top-空間文本對象, 本文在其中選取一個最具代表性的工作[1]作為研究對象。文獻[1]中使用一個混合索引結構IR-tree, 融合了空間信息以及文本信息。IR-tree本質上是一棵R-tree, 每個頂點關聯一個倒排文件索引, 這個索引包含此頂點所有子樹的信息。IR-tree的每個頂點能總結此頂點所有子節點的文本信息, 即此頂點能描述子節點的所有信息。同時, 此頂點能估計出查詢與所有在子樹中對象的相關程度, 并給出邊界。因此, top-檢索的結果使用最佳優先搜索和優先隊列來實現。

2 本文提出的策略

考慮到文本的語義相似性, 本文提出一種快速有效的空間文本對象的檢索方法。在介紹本文的策略之前, 首先討論現有的集中空間文本對象的檢索方法。

2.1 基準策略

若要快速有效地得到top-的空間文本對象, 主要的挑戰在于如何對空間信息以及文本信息進行索引。一種簡單的方法就是利用R-tree來計算對象的空間相近程度, 利用倒排文件的方式來計算文本的相似性[14]。然后, 把兩種索引結合起來, 得到top-的空間文本對象。但是, 計算數據集中所有的候選對象是非常耗時的。另一種解決方法是基于倒排文件和R-tree來計算空間相近度以及文本相似度, 最終生成一個top候選對象的集合。然而, 這種方式也比較耗時, 因為在預先不知道查詢的情況下, 不能在第一步確定需要計算多少個候選對象來滿足最終的top-結果, 即不能保證第一步查找的對象能滿足后面的值。

2.2 基于語義的策略

本文的主要目的是將語義信息融合到索引結構中, 并能很好地融合空間相近性與語義相似性。在文獻[1]中, 由于緊密融合了倒排文件索引以及R-tree, 在文本信息與空間信息的融合上取得較好的效果。對于給定的兩個短文本和, Sim(,)與短文本中代表性的詞對有關。設1,2, …,t和1,2, …,t是和的詞。如果≤, 則相似度值可以表示為

這里Sim表示代表性詞對之間的相似度, 其值可以從代表性的詞對之間獲得。因此, 為文本信息建立的倒排表必須滿足以下條件: 1)所有詞都必須定義; 2)接續列表必須與詞相關。然而, 如果一個查詢包含多個詞1,2, …,t, 如何從中獲取相關詞? 由于本文提出的策略是從倒排表中獲取排序列表, 每個詞與排序列表有關, 因此很容易應用閾值算法[15]來獲得與查詢最相關的文本。文獻[1]中將空間索引與文本索引融合在同一索引結構中。根據索引建立的方式, 本文中融合文本的語義信息。

2.2.1 索引建立

IRS策略 IRS策略是將語義信息融合到IR-tree中(即使用了語義相似度的IR-tree)。IRS的建立利用了在R-tree中普遍使用的插入操作[16]。此操作包含選擇葉節點和分裂節點, 并保證節點的子節點包含節點中所有的文本信息。每個節點包含一個指向倒排表的指針。在IRS的索引結構中, 葉子節點包含一組實體, 記為(,,.), 這里為數據集中的空間文本對象,為對象的矩形邊界,.是對象的文本描述。在子節點中, 存儲指向倒排表的指針。非葉節點包含一組實體, 記為(,,.), 這里為子節點的地址,為包含所有矩形的最小邊界矩形,.為此矩形的文本描述。本文融合了每個空間文本對象的語義信息, 所以在倒排表中, 每個詞對應一組文本列表對象, 這些對象按照詞語文本之間相似度的倒序排列。在IRS 中, 文本信息總結了所有子節點中的文本內容, 所以能預估與查詢相關的范圍。

DIRS策略 從IRS策略可以看出, 索引建立時只考慮空間信息, 即最小矩形是否與空間位置有關。在實際情況中, 對于一個查詢, 距離查詢最近的不一定是用戶最終想得到的結果, 因此在索引建立時需要同時考慮空間信息和文本信息。與IRS策略相似的是, 非葉節點包含一組實體, 記為(,,.)。與R-tree操作相同, 對于一個新的空間文本對象, 為了選擇合適的插入路徑, DIRS同時考慮了空間信息和文本信息。記每個節點的條目為En1, En2, …, En。令new是新插入的空間文本對象, 在R-tree中, En的面積由于新空間文本對象new的加入而變大。本文使用一個衡量指標EnlargeRec(En)來描述面積的增加值:

EnlargeRec(En) = Rec(Ennew.) ? Rec(En),

其中, Rec(Ennew.)是En融入了新空間文本對象new后的新實體。考慮了文本信息后, 面積增加可以用下式表示:

其中,是調節空間信息與文本信息的參數, Recmax是包含所有空間文本對象的最小邊界矩形。

據報道，我國護理科研在心理護理、人文護理等的研究遠遠落后于發達國家，我國在對照顧者的護理方面與國外相比差距甚遠［4］。因此，重視患者照顧者的早期心理狀況，盡早介入照顧者的心理干預，能有效減輕照顧者的身心壓力，有助于促進患者的康復。

不同于R-tree, 在建立DIR索引的插入操作中, 選取子樹時要考慮文本信息, 使EnlargeRec(En)的值最小。同樣, 在分裂操作中也需要考慮文本的信息, 即在建立索引的整個過程中同時考慮到空間信息與文本信息。

2.2.2 查詢過程

最佳優先遍歷算法[17]和優先隊列用于存儲訪問過的頂點和空間文本對象。我們用min(,)表示查詢與矩形之間的邊界, Simdist(,)表示與每個空間文本對象之間的距離, 詳細說明見表1。需要說明的是, Simdist(,)算法僅計算查詢與算法遍歷過的對象或矩形。我們用一個例子來說明DIRS與IRS策略的不同, 具體過程見表2和3。

表1 查詢Q與對象以及矩形的距離值

表2 基于IRS策略的查詢過程

表3 基于DIRS策略的查詢過程

從表2可以看出, 為了得到top-2對象2,1, IRS策略的檢索過程遍歷5,6,1,2,3,4, 也就是遍歷整棵樹中大部分的節點。這是因為IRS策略在建立索引的時只考慮空間信息, 忽視了文本的語義信息。

從表3可以看出, DIRS策略的檢索過程僅需遍歷5,1,3就能得到最終的top結果。這是因為DIRS在索引建立時考慮了文本的語義信息, 使得索引結構更加準確, 查詢的過程只需要遍歷很少的節點, 即只需要5步, 少于IRS策略的7步。

3 實驗分析

我們通過實驗, 從效率和有效性兩個方面檢驗本文提出的策略。實驗在16-core Intel? Xeon? E5530服務器上進行, 操作系統為Debian 2.6.26-2, 所有程序使用C語言編寫, 利用GNU gcc編譯器編譯。

本文使用文獻[18]中使用的數據集。此數據集共有225098個用戶, 22506721個唯一的空間文本對象(這里的對象既含有空間信息, 又含有文本信息)。為了檢驗本文所提策略的有效性, 將IR-tree沒有融入語義信息作為基準策略, 記為baseline, 將IR-tree使用了語義信息記為IRS, 將文本信息索引加上語義融合記為DIRS。本文所用數據集的統計信息見表4。

表4 數據集統計信息

說明: “原始”表示從原始的數據集中抽取的文本結果, 沒有經過任何預處理; “處理后”表示去除停用詞以及規則化后的結果。

3.1 有效性實驗結果

在有效性試驗中, 我們隨機選擇5個查詢, 分別計算在基準策略、IRS以及DIRS三種策略下的精度。從前面的分析可以看出, 影響有效性的因素有兩個。一個影響因素是在計算過程中調節融合空間相近程度與文本相近程度的參數, 這個參數的作用主要是調節空間相近與文本相似這兩個因素的權重。這是由于在實際的系統中, 人們對空間相似度與文本相似的關心程度不同, 因此需要調節這個權重來計算出更加精確的結果。另一個影響因素是索引建立時, 用來調節文本加強程度的參數。由于本文所提策略在索引建立初期就考慮文本因素對于整個索引建立的影響, 因此就是為了調節文本因素對索引建立影響程度的參數。我們通過交叉驗證實驗, 選測和的最佳值。

和的取值都在0.1~0.9之間。從實驗結果得到: 對于IRS,=0.68; 對于DIRS,=0.68,=0.2。有效性實驗結果如表5所示, 可以看出, IRS策略和DIRS策略由于考慮了語義信息, 所以明顯優于基準策略。

表5 有效性實驗結果

3.2 不同參數下實驗結果

由于本文的實驗結果與兩個重要的參數和有關, 因此我們分別選取和在0.1~0.9區間, 按照粒度0.1來驗證, 結果如表6和7所示?？梢钥吹? 相比于IRS策略, 由于DIRS策略在索引建立時已經考慮了文本之間的信息, 所以能大幅度減少訪問時間。從表6和7還可以看出, 不同的和值對效率的影響主要表現在節點訪問的順序以及在某個節點訪問的時間長短上, 所以和這兩個參數對基準策略的影響不大, 而對IRS策略和DIRS策略有一定的影響。因此, 為了平衡有效性與效率之間的關系, 如何選取和參數值也是一個重要的研究課題。

表6 不同α下效率實驗結果

表7 不同δ下效率實驗結果

3.3 效率實驗結果

效率的比較使用有效性試驗中最佳的參數配置, 通過以下的實驗來檢驗: 不同的數據集大小以及不同的值。本文從數據集中隨機抽取10個對象作為查詢, 實驗結果包括平均查詢時間, 結果如圖1和2所示?？梢钥闯? 由于DIRS在索引建立時考慮了文本信息, 使得查詢訪問較少的節點就能得到最終的結果, 所以在性能上DIRS比IRS具優勢。

4 總結

本文針對傳統空間文本檢索策略中的有效性問題, 對如何從給定的空間文本對象集合中快速有效地檢索出top-個近似結果進行研究, 主要貢獻如下。

1)以空間文本對象檢索為研究對象, 提出一種基于語義的策略, 在空間文本兌現檢索過程中考慮到語義信息, 通過建立綜合的索引來無縫融合空間索引與文本索引。

2)提出一種快速有效的空間文本對象的檢索算法, 這種算法對于實際應用系統非常重要, 因為用戶更加傾向于找到語義相似的對象。

3)對實際數據的實驗表明, 與現有策略相比較, 本文提出的策略在速度以及有效性方面有較大優勢。

[1]Cong G, Jensen C S, Wu D. Efficient retrieval of the top-most relevant spatial web objects // Proceedings of the VLDB Endowment. Lyon, 2009: 337–348

[2]Li Z, Lee K C K, Zheng B, et al. IR-tree: an efficient index for geographic document search. IEEE Transac-tions on Knowledge and Data Engineering, 2011, 23 (4): 585–599

[3]Zhang D, Chee Y M, Mondal A, et al. Keyword search in spatial databases: towards searching by document // Proceedings of IEEE International Conference on Data Engineering. Shanghai, 2009: 688–699

[4]Zhou Y, Xie X, Wang C, et al. Hybrid index structures for location-based web search // Proceedings of Inter-national Conference on Information and Knowledge Management. Bremen, 2005: 155–162

[5]Khodaei A, Shahabi C, Li C. Hybrid indexing and seamless ranking of spatial and textual features of web documents // Proceedings of International Con-ference on Database and Expert Systems Applica-tions. Bilbao, 2010: 450–466

[6]Chen Y Y, Suel T, Markowetz A. Efficient query processing in geographic web search engines // Proceedings of ACM SIGMOD International Con-ference on Management of Data. Chicago, 2006: 277–288

[7]Christoforaki M, He J, Dimopoulos C, et al. Text vs. space: efficient geo-search query processing // Procee-dings of International Conference on Information and Knowledge Management. Glasgow, 2011: 423–432

[8]Felipe I D, Hristidis V, Rishe N. Keyword search on spatial databases // Proceedings of IEEE International Conference on Data Engineering. Cancun, 2008: 656–665

[9]Rocha-Junior J B, Gkorgkas O, Jonassen S, et al. Efficient processing of top-spatial key-word queries // Proceedings of International Symposium on Spatial and Temporal Databases. Minneapolis, 2011: 205–222

[10]Islam A, Inkpen D. Semantic text similarity using corpusbased word similarity and string similarity. ACM Transactions on Knowledge Discovery from Data, 2008, 2(2): 1-25

[11]Li Yuhua, McLean D, Bandar Z, et al. Sentence similarity based on semantic nets and corpus statistics. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(8): 1138-1150

[12]Tsatsaronis G, Varlamis I, Vazirgiannis M. Text relatedness based on a word thesaurus. Journal of Artificial Intelligence Research, 2010, 37(1): 1–40

[13]Gu Yanhui, Yang Zhenglu, Xu Guandong, et al. Exploration on efficient similar sentences extraction. World Wide Web, 2014, 17(4): 595-626

[14]Martins B, Silva M J, Andrade L. Indexing and ranking in GEO-IR systems // Proceedings of the Workshop on Geographic Information Retrieval. Bremen, 2005: 31–34

[15]Fagin R, Lotem A, Naor M. Optimal aggregation algorithms for middleware // Proceedings of ACM Symposium on Principles of Database Systems. Santa Barbara, 2001: 102–113

[16]Guttman A. R-trees: a dynamic index structure for spatial searching // Proceedings of ACM SIGMOD International Conference on Management of Data. Boston, 1984: 47-57

[17]Hjaltason G R, Samet H. Distance browsing in spatial databases. ACM Transactions on Database Systems, 1999, 24(2): 265-318

[18]Cheng Z, Caverlee J, Lee K, et al. Exploring millions of footprints in location sharing services // Procee-dings of International Conference on Web and Social Media. Barcelona, 2011: 81–88

Similar Spatial Textual Objects Retrieval Strategy

GU Yanhui1,2,?, WANG Daosheng3, WANG Yonggen1,2, LONG Yunfei4, JIANG Suoliang1,2, ZHOU Junsheng1,2, QU Weiguang1,2

1. School of Computer Science and Technology, Nanjing Normal University, Nanjing 210023; 2. Jiangsu Research Center of Information Security & Privacy Technology, Nanjing 210023; 3. School of Chinese Language and Culture, Nanjing 210097; 4. Department of Computing, The Hong Kong Polytechnic University, Hong Kong; ? E-mail: gu@njnu.edu.cn

Based on the efficiency and effectiveness issue of traditional simiar spatial textual objects retrieval, a semantic aware strategy which can effectively and efficiently retrieve the top-similar spatial textal objects is proposed. The efficient retrieval strategy which is based on spatial textual objects is built on a common framework of spatial object retrieval, and it can satisfy the efficiency and effectiveness issues of users. Extensive experimental evaluation demonstrates that the performance of the proposed method outperforms the state-of-the-art approach.

spatial textual object; semantic similar; top-

10.13209/j.0479-8023.2016.008

TP391

2015-06-19;

2015-09-03; 網絡出版日期: 2015-09-30

國家自然科學基金(61272221, 61472191)、國家社會科學基金(11CYY030, 10CYY021)、江蘇省社會科學基金(12YYA002)和江蘇省高校自然科學基金(14KJB520022)資助