一種基于語義相關(guān)度的XML關(guān)鍵字查詢排序方法

李瑞霞,蘇守寶,周先存

(皖西學(xué)院 信息工程學(xué)院,安徽 六安 237012)

隨著XML數(shù)據(jù)表示和信息交換的廣泛應(yīng)用,在信息檢索中利用XML關(guān)鍵字查詢已成為本領(lǐng)域目前研究的熱點.傳統(tǒng)檢索方法通常利用結(jié)構(gòu)查詢語言XPath和XQuery進行XML數(shù)據(jù)檢索,可表示復(fù)雜的語義,因此能獲得較理想的結(jié)果,但這種方法要求用戶理解XML的結(jié)構(gòu)且掌握其語法.XML關(guān)鍵字檢索只需用戶輸入部分關(guān)鍵信息即可獲得需要的內(nèi)容,但卻通常因為查詢結(jié)果排序的不合理性,可能會提供相關(guān)度較小的結(jié)果給用戶,而忽略相關(guān)度較大的重要信息.

與普通文檔的關(guān)鍵字查詢不同,XML數(shù)據(jù)上關(guān)鍵字查詢的目標(biāo)通常不是整個XML文檔,而是滿足包含給定關(guān)鍵字的最緊致XML片段,文獻[1]將該問題歸結(jié)為最小樹根節(jié)點問題(smallest lowest common ancestor,SLCA).SLCA是關(guān)鍵字查詢的一種經(jīng)典方法,但其未考慮節(jié)點的語義,從而影響了查詢結(jié)果與用戶需求的相關(guān)度.文獻[2]把文檔中的元素劃分為實體節(jié)點、屬性節(jié)點和連接節(jié)點,利用推斷方法猜測返回的節(jié)點類型,也可視為SLCA算法的變體,未考慮查詢關(guān)鍵詞的關(guān)聯(lián);文獻[3]利用XRANK方法分別對關(guān)鍵字出現(xiàn)在中間節(jié)點和葉子節(jié)點兩種情況進行了相關(guān)度的排序研究;文獻[4]在XRANK的基礎(chǔ)上考慮了關(guān)鍵字出現(xiàn)的位置和層次信息,進而推斷用戶需要的目標(biāo);文獻[5]提出了目標(biāo)節(jié)點和條件節(jié)點的概念,并提出了兩種不同類型節(jié)點的識別算法;文獻[6]通過考慮不同類型XML節(jié)點出現(xiàn)的頻率及查詢關(guān)鍵字所在不同位置等對目標(biāo)節(jié)點類型的影響，進行目標(biāo)節(jié)點推斷，提高了查詢的準(zhǔn)確率;文獻[7]用自動推斷關(guān)鍵詞查詢條件節(jié)點和目標(biāo)節(jié)點類型的算法，并結(jié)合XML文檔集的模式和統(tǒng)計信息及關(guān)鍵詞出現(xiàn)的上下文及其關(guān)聯(lián)關(guān)系等推斷用戶的查詢意圖;文獻[8]通過對路徑進行約束實現(xiàn)搜索和排序XML文檔.本文提出一種考慮節(jié)點語義相關(guān)度的排序方法,該方法通過節(jié)點對XML文檔的區(qū)分程度、節(jié)點描述XML文檔的直接程度及對XML文檔概括的精確程度三方面設(shè)置其權(quán)重,進而利用向量空間模型VSM[9]實現(xiàn)語義相關(guān)度的排序.

1 XML文檔的表示及信息檢索

本文將XML文檔以樹結(jié)構(gòu)的形式表示.

定義1一個XML文檔可由T=(r,E,NE,NV)表示,其中:r表示文檔樹的根節(jié)點；E表示文檔樹中所有邊的集合；NE對應(yīng)XML文檔的元素和屬性節(jié)點；NV對應(yīng)XML文檔的文本節(jié)點,即葉子節(jié)點.

當(dāng)用戶提交查詢請求時,系統(tǒng)通過大量的文檔集合檢索用戶需要的文檔,然后對結(jié)果集根據(jù)其相關(guān)度進行排序.在信息檢索領(lǐng)域,通常利用向量空間模型計算查詢請求和被檢索文檔間的相關(guān)度.將被檢索文檔和查詢關(guān)鍵字設(shè)置成由若干權(quán)重組成的向量形式.向量間的相似度即關(guān)鍵字和文檔間的相關(guān)度.不同的權(quán)重利用tf-idf方法獲得[10].

例如,L={termi}(i=1,2,…,|L|) 表示檢索關(guān)鍵字的集合,D={dj}(j=1,2,…,|D|)表示文檔的集合,通過給文檔dj中各節(jié)點設(shè)置不同的權(quán)重可將其表示為dj=(w1j,w2j,…,w|L|j),查詢關(guān)鍵字可表示為q=(w1q,w2q,…,w|L|q).通過

(1)

可獲得關(guān)鍵字和文檔之間的相似度.

查詢關(guān)鍵字的權(quán)重通常設(shè)置為相等,而文檔中節(jié)點的權(quán)重通過tf-idf方法設(shè)定,但傳統(tǒng)的tf-idf方法并不適合結(jié)構(gòu)化的XML文檔.XML文檔作為一種半結(jié)構(gòu)化數(shù)據(jù),除包含文本內(nèi)容外,還包含文本文檔不具有的結(jié)構(gòu)信息,例如同一節(jié)點包含的內(nèi)容在不同位置出現(xiàn)可能代表不同的語義.

2 語義相關(guān)度排序

2.1 影響節(jié)點語義權(quán)重的因素

通過對現(xiàn)有XML關(guān)鍵字查詢的研究及分析表明,影響節(jié)點語義權(quán)重的因素主要有：節(jié)點對文檔的區(qū)分能力、節(jié)點是否直接描述文檔和節(jié)點是否明確描述文檔.

1) 相同的節(jié)點可能會出現(xiàn)在所有的文檔中,而在不同文檔中因其表示不同的意義而具有不同的權(quán)重,如圖1所示,若查詢關(guān)鍵字是XML,則節(jié)點1和5都包括了該關(guān)鍵字,因此滿足用戶的查詢要求,然而對于節(jié)點5關(guān)鍵字出現(xiàn)在一篇文章的title中,所以認為節(jié)點5更符合用戶的查詢需求.因此,一個節(jié)點對文檔區(qū)分能力越強,則其權(quán)重越大.權(quán)重表示為

圖1 XML文檔的樹形表示Fig.1 A tree of XML document

(2)

其中:di,j表示一個節(jié)點的權(quán)重,即該節(jié)點對文檔的區(qū)分能力;pj表示該節(jié)點j在本文檔i中出現(xiàn)的概率,其出現(xiàn)的次數(shù)越多,則對文檔的貢獻越大,權(quán)重越大；Hj表示節(jié)點的熵.

2) 為了判斷一個關(guān)鍵字是否直接描述該文檔,可通過其所在位置進行衡量.

定義2節(jié)點的距離通過從根節(jié)點到該節(jié)點所經(jīng)過的節(jié)點個數(shù)表示,根節(jié)點距離為1.

如圖1所示,節(jié)點Baum的距離為從articles到Baum經(jīng)過的節(jié)點數(shù)量,通過定義2可得其值為4.

通常認為節(jié)點出現(xiàn)的位置越靠近根節(jié)點,描述文檔越直接,對文檔的貢獻也越大.其權(quán)重表示為

(3)

其中:n=length(j)表示從根節(jié)點到節(jié)點j的距離;mk表示在經(jīng)過的節(jié)點中第k個節(jié)點在該路徑出現(xiàn)的次數(shù)；k表示一個調(diào)節(jié)因子(k<1),本文設(shè)置k=0.8[11].

文檔中節(jié)點經(jīng)過的最大距離也會影響權(quán)重的計算.假設(shè)文檔1中距離最大為3,文檔2為7,則根據(jù)式(3),若一個關(guān)鍵字出現(xiàn)在文檔1中路徑的第3個位置比出現(xiàn)在文檔2中路徑的第4個位置更重要,顯然不合理.為了消除這種影響,本文借鑒文獻[12]的思想對路徑長度進行規(guī)范化:

(4)

其中:Rnorm-i,j表示規(guī)范化后的節(jié)點權(quán)重,以此替換式(3)中的權(quán)重;length(m)表示文檔中包含關(guān)鍵字的節(jié)點到根節(jié)點的距離.

3) 一個節(jié)點是不是明確描述文檔,可通過節(jié)點包含的字符長度衡量,如對于一篇文章,摘要字數(shù)明顯多于關(guān)鍵詞,實際上摘要也更能使人了解一篇文章的主要內(nèi)容.本文通過Ei,j表示文檔di中節(jié)點j的字符長度.

由于文檔集中文檔大小不同,因此一個很大文檔包含的字符數(shù)顯然比一個很小文檔包含的字符數(shù)多,但對特定關(guān)鍵字,出現(xiàn)在大文檔中并不表明比出現(xiàn)在小文檔中更重要,因此為了消除文檔大小產(chǎn)生的影響,本文借鑒文獻[13]的思想進行規(guī)范化：

(5)

其中：Enorm-i,j表示規(guī)范化后的權(quán)重;tm表示在文檔中包含關(guān)鍵字的節(jié)點.

2.2 相關(guān)度計算模型

基于上述影響關(guān)鍵字語義權(quán)重的幾個因素,將節(jié)點tj在文檔di中的權(quán)重wi,j定義如下：

(6)

3 實驗分析

測試數(shù)據(jù)集使用實際的DBLP數(shù)據(jù)集(127 Mb)[14],實驗平臺為Intel 2.8 GHz Pentium D 處理器,1 GHz RAM,Windows XP操作系統(tǒng).本文提出的語義相關(guān)度查詢排序方法簡稱為SCQR(semantic correlation query and ranking),對比算法選擇文獻[1]提出的關(guān)鍵字檢索方法SLCA.部分測試用例列于表1.選擇100篇文檔進行測試,測試查詢關(guān)鍵字個數(shù)為1～4個.為消除運行時產(chǎn)生的誤差,每個測試用例都進行5次測試,然后取平均時間.由表1可見,SCQR方法的結(jié)果比SLCA方法更精確.圖2給出了SCQR方法和SLCA方法查詢時間的對比.本文在計算前先對各節(jié)點做預(yù)處理,所以由圖2可見,SCQR方法的性能明顯優(yōu)于SLCA方法.

表1 DBLP數(shù)據(jù)集上的測試結(jié)果Table 1 Results on DBLP dataset

查準(zhǔn)率用于度量實驗返回節(jié)點與用戶查詢意圖的相關(guān)程度;查全率用于衡量實驗檢索出的相關(guān)節(jié)點與全部相關(guān)節(jié)點的百分比[15]:

圖2 SCQR方法和SLCA方法執(zhí)行時間的比較Fig.2 Comparison of execution time for SCQR and SLCA

圖3通過10組數(shù)據(jù)的測試給出了SCQR方法和SLCA方法之間查全率與查準(zhǔn)率的對比.由圖3可見,SCQR方法和SLCA方法的平均查準(zhǔn)率分別為0.808和0.628,這是因為SCQR方法在檢索中充分考慮了XML文檔的語義,并在排序檢索結(jié)果過程中考慮了滿足用戶查詢要求的相關(guān)程度.而SLCA方法在檢索過程中只考慮文檔是否包含關(guān)鍵字,因而,無論返回何種節(jié)點類型,最終查詢結(jié)果都只可能是一棵以SLCA作為根節(jié)點的子樹,對于包含關(guān)鍵字的文檔不能通過有效地排序返回給用戶有價值的信息,因此導(dǎo)致了SCQR方法的查準(zhǔn)率高于SLCA方法的查準(zhǔn)率.

圖3 SCQR方法和SLCA方法查詢精度的比較Fig.3 Comparison of precision and recall for SCQR and SLCA

綜上所述,本文以向量空間模型為基礎(chǔ),摒棄了tf-idf的權(quán)重計算方法,利用XML的語義,從節(jié)點的區(qū)分程度、節(jié)點描述文檔的直接程度和節(jié)點描述文檔的明確程度三方面衡量文檔中各節(jié)點的權(quán)重,計算關(guān)鍵字和文檔集合的相似性,實現(xiàn)XML語義的相關(guān)度排序,得到了滿足用戶查詢要求的最相關(guān)結(jié)果.通過DBLP數(shù)據(jù)集實驗驗證了提出的方法在查全率及查準(zhǔn)率上比傳統(tǒng)方法有較大改進.

[1] XU Yu,Papakon Y.Efficient Keyword Search for Smallest LCAs in XML Data Bases [C]//Proceedings of the ACM SIGMOD International Conference on Management of Data.New York:ACM Press,2005:537-538.

[2] LIU Zi-yang,CHEN Yi.Identifying Meaningful Return Information for XML Keyword Search [C]//Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data.New York:ACM Press,2007:329-340.

[3] GUO Lin,SHAO Feng,Botev C,et al.XRANK:Ranked Keyword Search over XML Documents [C]//Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data.New York:ACM Press,2003:16-27.

[4] LI Xia,LI Zhan-huai,CHEN Qun,et al.XObject:An XML Keyword Search Method Based on Structural Retrieval [J].Journal of Northwestern Polytechnical University,2010,28(4):602-608.(李霞,李戰(zhàn)懷,陳群,等.XML關(guān)鍵字檢索中推斷用戶需求信息對象的方法XObject [J].西北工業(yè)大學(xué)學(xué)報,2010,28(4):602-608.)

[5] BAO Zhi-feng,Ling T W,LU Tia-heng.Effective XML Keyword Search with Relevance Oriented Ranking [C]//Proceedings of the 25th International Conference on Data Engineering.Shanghai:IEEE Computer Society,2009:517-528.

[6] GUO Wen-qi,CHEN Qun,LOU Ying.Method for Inferring XML Keyword Search Target Node [J].Computer Engineering,2012，38(8):41-49.(郭文琪,陳群,婁穎.一種推斷XML關(guān)鍵字檢索目標(biāo)節(jié)點的方法 [J].計算機工程,2012,38(8):41-49.)

[7] LI Qiu-shi,WANG Qiu-yue,WANG Shan.Query Understanding for XML Keyword Search [J].Journal of Software,2012,23(8):2002-2017.(李求實,王秋月,王珊.XML關(guān)鍵詞檢索的查詢理解 [J].軟件學(xué)報,2012,23(8):2002-2017.)

[8] WEN Yan-long,ZHANG Ying,LIU Zhong-qi.Searching and Ranking XML Documents via Path Contraints [J].International Journal of Digital Content Technology and Its Application,2012,6(1):462-470.

[9] Christopher D M,Prabhakar R,Hinrich S.Introduction to Information Retrieval [M].New York:Cambridge University Press,2008.

[10] Ricardo B Y,Berthier R N.Modern Information Retrieval:The Concepts and Technology behind Search [M].New York:ACM Press,2011.

[11] GAO Ning,DENG Zhi-hong,JIANG Jia-jian,et al.Combining Strategies for XML Retrieval [C]//Proceedings of INEX Conference.Berlin:Springer-Verlag,2011:319-331.

[12] ZHANG Li-jun,LI Zhan-huai,CHEN Qun,et al.Classifying XML Documents Based on Term Semantics [J].Journal of Jilin University:Engineering and Technology Edition,2012,42(6):1510-1514.(張利軍,李戰(zhàn)懷,陳群,等.基于關(guān)鍵字語義信息的XML文檔分類 [J].吉林大學(xué)學(xué)報:工學(xué)版,2012,42(6):1510-1514.)

[13] LOU Ying,LI Zhan-huai,CHEN Qun,et al.Effective XML Keyword Search with Considering Semantics of Tags [J].Journal of Huazhong University of Science and Technology:Natural Science Edition,2011,39(9):82-86.(婁穎,李戰(zhàn)懷,陳群,等.一種考慮標(biāo)簽語義的XML關(guān)鍵字查詢算法 [J].華中科技大學(xué)學(xué)報:自然科學(xué)版,2011,39(9):82-86.)

[14] UW CSE,UW Database Group,DAN Su-ciu.XML Data Repository [EB/OL].2002-11-21.http://www.cs.washington.edu/research/xmldatasets/.

[15] 花芳.文獻檢索與利用 [M].北京：清華大學(xué)出版社，2009.