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

李瑞霞,蘇守寶,周先存

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

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

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

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

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

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

當(dāng)用戶提交查詢請(qǐng)求時(shí),系統(tǒng)通過大量的文檔集合檢索用戶需要的文檔,然后對(duì)結(jié)果集根據(jù)其相關(guān)度進(jìn)行排序.在信息檢索領(lǐng)域,通常利用向量空間模型計(jì)算查詢請(qǐ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é)點(diǎn)設(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é)點(diǎn)的權(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é)點(diǎn)包含的內(nèi)容在不同位置出現(xiàn)可能代表不同的語義.

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

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

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

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

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

(2)

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

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

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

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

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

(3)

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

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

(4)

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

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

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

(5)

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

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

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

(6)

3 實(shí)驗(yàn)分析

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

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

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

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

圖3通過10組數(shù)據(jù)的測試給出了SCQR方法和SLCA方法之間查全率與查準(zhǔn)率的對(duì)比.由圖3可見,SCQR方法和SLCA方法的平均查準(zhǔn)率分別為0.808和0.628,這是因?yàn)镾CQR方法在檢索中充分考慮了XML文檔的語義,并在排序檢索結(jié)果過程中考慮了滿足用戶查詢要求的相關(guān)程度.而SLCA方法在檢索過程中只考慮文檔是否包含關(guān)鍵字,因而,無論返回何種節(jié)點(diǎn)類型,最終查詢結(jié)果都只可能是一棵以SLCA作為根節(jié)點(diǎn)的子樹,對(duì)于包含關(guān)鍵字的文檔不能通過有效地排序返回給用戶有價(jià)值的信息,因此導(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)重計(jì)算方法,利用XML的語義,從節(jié)點(diǎn)的區(qū)分程度、節(jié)點(diǎn)描述文檔的直接程度和節(jié)點(diǎn)描述文檔的明確程度三方面衡量文檔中各節(jié)點(diǎn)的權(quán)重,計(jì)算關(guān)鍵字和文檔集合的相似性,實(shí)現(xiàn)XML語義的相關(guān)度排序,得到了滿足用戶查詢要求的最相關(guān)結(jié)果.通過DBLP數(shù)據(jù)集實(shí)驗(yàn)驗(yàn)證了提出的方法在查全率及查準(zhǔn)率上比傳統(tǒng)方法有較大改進(jìn).

[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)鍵字檢索中推斷用戶需求信息對(duì)象的方法XObject [J].西北工業(yè)大學(xué)學(xué)報(bào),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é)點(diǎn)的方法 [J].計(jì)算機(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.(李求實(shí),王秋月,王珊.XML關(guān)鍵詞檢索的查詢理解 [J].軟件學(xué)報(bào),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é)報(bào):工學(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é)報(bào):自然科學(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] 花芳.文獻(xiàn)檢索與利用 [M].北京：清華大學(xué)出版社，2009.