基于查詢空間的分布式文檔集合劃分算法

1、基于查詢空間的分布式文檔集合劃分算法    摘要：合理的文檔集合劃分能夠有效的提高分布式信息檢索的效果，本文針對分布式信息檢索中的集合劃分問題，提出了一種基于查詢空間的文檔集合劃分算法。與傳統(tǒng)的基于文檔空間的劃分算法相比，該算法從一種全新的角度看待和理解文檔集合劃分問題，給出了一種針對大規(guī)模海量信息的文檔集合劃分解決方案。實(shí)驗(yàn)表明該算法在算法效果和算法效率方面都有很大的提高。關(guān)鍵詞：計(jì)算機(jī)應(yīng)用；中文信息處理；分布式信息檢索；文檔集合劃分；聚類1前言集合劃分是影響分布式信息檢索效果的一個(gè)重要問題。在分布式WEB信息檢索中，開展集合劃分的目的是希望通過集合劃

2、分操作，繼而在后面的檢索過程中可以通過檢索更少的文檔而獲取更好的檢索結(jié)果。對于集合劃分問題，直觀的想法是為了讓一個(gè)查詢的相關(guān)文檔都集中在一個(gè)或少數(shù)的集合中，但不同查詢的相關(guān)文檔可能是相同的，因此要實(shí)現(xiàn)將一個(gè)查詢的相關(guān)文檔都集中在一個(gè)或少數(shù)幾個(gè)集合中的想法，常常會(huì)出現(xiàn)矛盾和沖突的情況。在以往的工作中，Claudine Badue等人研究了對索引劃分的兩種策略：一是把文檔分布在多臺(tái)處理機(jī)上，并行的建立索引并進(jìn)行檢索，在檢索時(shí)采用并行檢索的方式，每個(gè)搜索引擎同時(shí)檢索；另一種策略是，將建立好的倒排索引，按照關(guān)鍵詞的順序分布在不同的機(jī)器上，每個(gè)引擎負(fù)責(zé)處理一部分關(guān)鍵詞的倒排索引，在檢索時(shí)，只有含有查詢中

3、關(guān)鍵詞的機(jī)器，參與到本次檢索中。在這個(gè)工作中，對于第一種策略文檔的分布是隨機(jī)的，沒有根據(jù)一定的原則來進(jìn)行處理，在檢索時(shí)采用的是并行的處理辦法，由于對所有文檔集合都要檢索，沒有降低檢索的計(jì)算開銷。Jeong通過研究對索引的劃分來提高檢索的效率，但這種對于索引的劃分主要考慮的是提高檢索的效率，沒有對檢索的效果進(jìn)行充分的考慮。1999年SigIR上Xu和W.Bruce Croft等人采用的基于語言模型聚類的方法，把數(shù)據(jù)按照聚類結(jié)果進(jìn)行劃分，取得比較好的實(shí)驗(yàn)結(jié)果。該工作主要特點(diǎn)是從文檔的聚類出發(fā)來實(shí)現(xiàn)對文檔集合的劃分。通過文檔的聚類，有利于把相關(guān)的文檔聚集在一個(gè)類中，從而改善檢索結(jié)果的質(zhì)量，由于文檔集

4、合劃分是為了進(jìn)一步檢索服務(wù)的，因此必須考慮用戶查詢對于文檔集合劃分的影響，而該方法主要從文檔內(nèi)容角度出發(fā)來實(shí)現(xiàn)對于文檔集合的劃分，沒有考慮查詢對于文檔集合劃分的影響，該方法在效率方面也難以面對海量的信息處理。本文將嘗試從查詢空間角度實(shí)現(xiàn)對文檔集合的劃分，該算法將在劃分的效率與劃分的效果方面具有明顯的改善與提高。2算法基本思想集合劃分問題，就是要將文檔集合劃分成若干個(gè)子集合，使得進(jìn)一步的檢索能夠取得更好的檢索結(jié)果。文檔集合的劃分問題，雖然是對文檔集合的劃分，但絕不能簡單的從文檔角度看待這個(gè)問題，因?yàn)槲臋n集合劃分的目的是為了更好更方便的查找信息，因此文檔集合的劃分必須和信息的需求緊密聯(lián)系起來，而信

5、息需求又是通過查詢來體現(xiàn)的。一般的，對于信息檢索問題，存在著以下幾個(gè)相互關(guān)聯(lián)的空間：用戶空間、查詢空間、文檔空間、作者空間，如圖1所示。傳統(tǒng)的文檔集合劃分算法都是基于文檔空間的，也就是說從文檔本身角度實(shí)現(xiàn)對文檔集合的劃分，基于文檔空間的劃分方法是建立在“Closely as-sociated document tend to be relevant to the same requests”這個(gè)假設(shè)基礎(chǔ)之上的。但文檔集合的劃分最終目標(biāo)是為查詢服務(wù)的，如果只關(guān)注文檔空間而忽略查詢空間顯然是不合理的。文檔集合的劃分應(yīng)該是以有利于查詢?yōu)閷?dǎo)向的劃分，其劃分的目的是為了更好的實(shí)現(xiàn)查詢，即：同一個(gè)查詢的相

6、關(guān)文檔盡量集中在一個(gè)或少數(shù)幾個(gè)文檔集合中。從查詢空間出發(fā)，要實(shí)現(xiàn)對文檔空間的劃分，必須建立起查詢空間與文檔空間的聯(lián)系，這種聯(lián)系就是查詢與文檔的相關(guān)關(guān)系。通過搜索引擎記錄的查詢?nèi)罩緛斫⒉樵兣c文檔之間的相關(guān)關(guān)系是一種有效的方法，當(dāng)用戶向搜索引擎發(fā)出一個(gè)檢索請求時(shí)，整個(gè)檢索過程包括用戶點(diǎn)擊的檢索結(jié)果都會(huì)被搜索引擎記錄下來，形成查詢?nèi)罩?。查詢?nèi)罩疽话阌涗浟擞脩羲樵兊牟樵冊~、點(diǎn)擊查看的文檔等。例如“搜狗”搜索引擎的查詢?nèi)罩救鐖D2所示。該日志每一行是一個(gè)用戶訪問行為的記錄，包括了用戶Session ID、查詢詞、URL(文檔)、該URL在檢索結(jié)果中的排序和用戶點(diǎn)擊該URL的順序等信息。用戶查詢?nèi)罩居涗?/p>

7、了用戶一系列重要的行為，因此常常被用來幫助提高檢索結(jié)果的質(zhì)量。如果假設(shè)用戶通過搜索引擎返回的文檔摘要(Snippet)可以判斷該文檔是否是查詢的相關(guān)文檔，那么可以認(rèn)為用戶點(diǎn)擊過的文檔都是查詢的相關(guān)文檔，也就是查詢?nèi)罩局忻織l記錄的URL都是其查詢詞的相關(guān)文檔，這樣利用查詢?nèi)罩揪徒⑵鹆宋臋n和查詢之間的相關(guān)關(guān)系，當(dāng)然這相關(guān)關(guān)系的建立與實(shí)際的相關(guān)情況有一定的偏差，但總的來說用戶的點(diǎn)擊行為可以刻畫查詢與文檔的相關(guān)關(guān)系。如圖3所示，利用查詢?nèi)罩緲?gòu)建的文檔和查詢之間的關(guān)系可以被看作一個(gè)二部圖，文檔和查詢之間的相關(guān)關(guān)系是二部圖中的邊。下一步本文需要解決的問題是利用構(gòu)建的查詢與文檔的關(guān)系圖，實(shí)現(xiàn)對文檔集合的劃

8、分。針對查找時(shí)間和空間開銷隨聚類進(jìn)行不斷增長的現(xiàn)實(shí)，本文提出采用BloomFilter算法來解決這個(gè)問題。BloomFilter算法可以使查找時(shí)間為一個(gè)常數(shù)，不隨被查找集合的大小而發(fā)生變化，BloomFilter的另外一個(gè)優(yōu)點(diǎn)是，空間開銷固定不變，不會(huì)隨處理的進(jìn)行而不斷增大，它是一種綜合平衡時(shí)間、空間代價(jià)，允許存在查找錯(cuò)誤的有效查找算法。雖然可能存在查找的錯(cuò)誤，但在理論和實(shí)踐方面，都可以把查找的錯(cuò)誤控制在可以接受的范圍內(nèi)。另外，在查詢?nèi)罩局?，相同的查詢可能被用戶多次查詢，重?fù)出現(xiàn)的查詢在計(jì)算相關(guān)度時(shí)是被重復(fù)計(jì)算的，這樣的計(jì)算是有實(shí)際意義的，因?yàn)槿绻臋nd1和文檔d2是查詢qi的相關(guān)文檔，而查詢

9、qi被查詢了很多次，雖然不能說因?yàn)椴樵僸i重復(fù)出現(xiàn)了多次，就能增加文檔d1和文檔d2的相關(guān)性，但是從聚類角度認(rèn)為d1和d2更相關(guān)是合理的，因?yàn)閷1和d2放入到一個(gè)集合中將有利于qi的查詢，而qi的被查詢次數(shù)多，有利于qi，就有利于降低查詢的整體開銷，這顯然是合理的。4實(shí)驗(yàn)與分析為了驗(yàn)證基于查詢空間的文檔集合劃分算法的                    有效性，本文使用的實(shí)驗(yàn)數(shù)據(jù)是“搜狗”搜索

10、引擎發(fā)布的查詢?nèi)罩緮?shù)據(jù)。直觀定性的感覺，一種好的文檔集合劃分結(jié)果應(yīng)該具有這樣的特點(diǎn)：1.一個(gè)查詢的相關(guān)文檔應(yīng)該集中在一個(gè)或盡量少的文檔集合中，這樣在檢索時(shí)，只要檢索少量的文檔集合，就可以得到全部相關(guān)文檔。2.一個(gè)文檔集合中盡量包含一個(gè)查詢的相關(guān)文檔，而不包含其他查詢的相關(guān)文檔，這樣檢索時(shí)處理的無關(guān)文檔減少，有利于檢索。3.文檔集合的數(shù)量應(yīng)該有一定的限制，如果沒有集合數(shù)量上的限制，令每個(gè)文檔集合中只包含一個(gè)文檔，雖然可以很好的滿足上面的兩條要求，但這樣的劃分顯然是不現(xiàn)實(shí)的。但這些直觀的原則不能定量的刻畫一種劃分算法的有效性，本文采用了下面的評價(jià)原則來對劃分結(jié)果進(jìn)行評價(jià)，該原則很好的體現(xiàn)了上面對文

11、檔集合劃分的要求。評價(jià)原則：對于給定的一種文檔集合劃分算法和一個(gè)待查詢的查詢集合，計(jì)算出對于每個(gè)查詢要檢索到其全部相關(guān)文檔所需要處理的平均文檔數(shù)，把這個(gè)平均文檔數(shù)作為評價(jià)原則，需要處理的平均文檔數(shù)越少，說明劃分越合理，劃分方法越好。為了更好的說明實(shí)驗(yàn)所使用數(shù)據(jù)的特點(diǎn)，本文針對日志文件進(jìn)行了分析統(tǒng)計(jì)。該數(shù)據(jù)集合的一些統(tǒng)計(jì)特性如表1所示。我們將用戶查詢?nèi)罩痉譃椤坝?xùn)練集合”和“測試集合”兩個(gè)部分，訓(xùn)練集合用來對文檔集合進(jìn)行劃分，而測試集合用來評價(jià)劃分的結(jié)果。在實(shí)驗(yàn)中，文檔空間與查詢空間的相關(guān)關(guān)系采用前面定義的方法。為了方便比較，采用了隨機(jī)的劃分方法作為參照(隨機(jī)的劃分算法就是隨機(jī)的將文檔歸入某個(gè)類別

12、)，具體的實(shí)驗(yàn)結(jié)果如表2所示。其中avgdoc1表示包括集合選擇在內(nèi)的整體代價(jià)(平均文檔數(shù))，而avgdoc2表示不計(jì)算集合選擇過程的代價(jià)(avgdoc1和avgdoc2的計(jì)算方法，將在文檔集合劃分評價(jià)部分闡述)，由于文檔集合共被劃分為100個(gè)子集合，因此avgdoc1和avgdoc2相差100。從實(shí)驗(yàn)結(jié)果看，如果按照基于查詢的劃分方法，檢索一個(gè)查詢詞需要處理的文檔數(shù)目，大概只是隨機(jī)劃分方法的十分之一，約占整個(gè)文檔集合的2.7，可見基于查詢的文檔集合劃分方法相對于隨機(jī)的劃分方法取得了很好的實(shí)驗(yàn)結(jié)果，這充分體現(xiàn)出了采用該算法對于文檔集合劃分問題的重要意義。從效率角度看，對文檔數(shù)為8 404 35

13、6的整個(gè)文檔集合進(jìn)行劃分大約耗時(shí)57分鐘，劃分算法所消耗的絕對時(shí)間也是一個(gè)可以接受的劃分時(shí)間，由于該算法是一個(gè)線性時(shí)間復(fù)雜度的算法，因此算法的運(yùn)行效率是可以滿足文檔集合劃分要求的。5結(jié)論基于查詢的文檔集合劃分方法從查詢空間這一全新視角實(shí)現(xiàn)對文檔集合的劃分，該方法利用查詢?nèi)罩窘⑵鹞臋n與查詢的關(guān)系圖，并采用本文提出的LIBCA算法實(shí)現(xiàn)了從查詢空間出發(fā)對文檔集合的劃分。基于查詢的文檔集合劃分方法體現(xiàn)了文檔集合劃分的直接目標(biāo)，即：劃分的目的是為查詢服務(wù)。從實(shí)驗(yàn)結(jié)果看，無論是算法的效果還是算法的效率都取得了比較理想的結(jié)果。在基于查詢的文檔集合劃分中，實(shí)現(xiàn)了利用查詢空間對文檔空間的劃分，反過來，利用文檔空間也可以實(shí)現(xiàn)對查詢空間的劃分，或者是在對文檔集合劃分后，會(huì)自然形成每一個(gè)子文檔集合對應(yīng)著一系列的查詢的情況，這些查詢對應(yīng)了該子文檔集