基于用戶興趣的局部上下文分析方法

摘要:針對根據目前網絡信息檢索存在的查全率和查準率低的特點，提出一種個性化的局部上下文分析方法，以提高Web信息檢索的性能#65377;該方法通過設計一種客戶端的用戶興趣挖掘模型，同時將用戶興趣模型與局部上下文分析方法相結合，克服了局部上下文分析的缺陷#65377;實驗結果顯示該方法能有效提高Web信息檢索的查全率與查準率#65377;

關鍵詞:信息檢索;查詢擴展;局部上下文分析;用戶興趣

中圖分類號:TP311; F270文獻標志碼:A

文章編號:1001-3695(2007)04-0261-04

隨著Internet的發展，網絡信息量急劇增長，同時Web信息檢索技術也日趨成熟，功能日益完善#65377;但是其檢索結果仍然不能令用戶十分滿意，甚至隨著信息量的指數級增長，其檢索性能也日益下降#65377;搜索引擎的出現在一定程度上緩解了人們在Web尋找信息的困難，但是卻不能從根本上得到令用戶滿意的檢索結果#65377;原因是目前大部分搜索引擎只提供基于關鍵字(Terms)的搜索，用戶在檢索信息時，用戶查詢表示(User’s Stated Query)與實際的檢索意圖(Actual Intent of Search)往往存在較大差異#65377;其根本原因在于自然語言的歧義性導致了信息檢索時出現詞的不匹配#65377;據統計，兩個人使用同樣的關鍵詞描述同一對象的概率小于20%，這就是當前信息檢索領域所謂的“詞典問題”^[1]#65377;在當前搜索引擎的使用過程中，當查詢中所包含的詞匯較少時，查詢效果則更差#65377;如果用戶使用足夠多的詞描述查詢內容， 詞典問題則在一定程度上會得到緩解#65377;但是大部分用戶進行信息檢索時，一般僅僅使用一至二個關鍵詞描述他們的查詢意圖#65377;在使用短查詢進行檢索時，大部分關鍵詞都具有歧義性(Ambiguity)，使得傳統的基于關鍵詞的向量空間模型所得到的檢索效果不是令人很滿意#65377;同時，在許多情況下，即使用戶使用的查詢詞在文檔中出現，也未必在該文檔中具有足夠的權重#65377;因此，僅僅依靠用戶提交的短查詢很難提供足夠的信息檢索出用戶需要的文檔#65377;

目前搜索引擎提供的服務質量低#65380;檢索結果相對較差的另一個主要原因是每個用戶心中都有自己的興趣和要求，而系統卻沒有考慮到用戶的這些個人因素#65377;大部分搜索引擎僅僅采用基于一般意圖的索引方法，其檢索模式也是面向大眾化的，即對每個用戶均提供統一的模式——onesizefitall模式#65377;然而，由于不同用戶對信息的需求往往存在很大的差異，即使是同一用戶對信息的需求在不同時刻也不同#65377;為了向用戶提供高質量的服務，信息檢索系統應能通過觀察用戶與系統之間的交互動作獲取用戶的個人興趣，根據不同用戶的興趣主題進行個性化的信息檢索#65377;

1查詢擴展方法

目前的查詢擴展方法具體包括全局分析#65380;局部分析#65380;局部上下文分析#65380;基于日志的查詢擴展等#65377;

全局分析^[2]主要包括聚類算法#65380;潛在語義索引(LSI)^[3]#65380;相似性詞典^[4]等#65377;對于這三種技術，均是建立在對全部文檔分析的技術上#65377;在全局分析中，利用詞的同現概率模型抽取表達文檔主題的關鍵字，稱之為主題詞#65377;利用這些主題詞表達文章的主要觀點，從一個側面反映用戶的檢索興趣信息#65377;因此，全局分析雖然能夠根據詞的共現信息收集關鍵詞作為查詢擴展詞，在一定程度上解決了詞的歧義性，但是，在查詢擴展中引入的關鍵詞，同時也增加了整個查詢的歧義性#65377;

局部分析的思想可以追溯到Atter 和Fraenkel在1977 年發表的論文^[5]，它利用兩次查詢的方法解決擴展問題#65377;局部分析利用初次檢索得到的與原查詢最相關的n篇文章作為擴展用詞的來源，而并非利用先前計算得到的全局詞的關系詞典#65377;目前流行的局部分析方法主要是局部反饋，它是在相關反饋的基礎上發展起來的#65377;相關反饋根據用戶對初次檢索的結果進行評判后，將用戶認為相關的文章作為擴展用詞的來源，而局部反饋解決了相關反饋必須與用戶交互的問題，它將初次查詢的前n篇文章認為是相關文章，并以此為依據對查詢進行擴展#65377;局部分析的方法是目前應用最廣泛的查詢擴展方法之一，并在一些實際的信息檢索系統中得以使用#65377;但是，當初次查詢后排在前面的文檔與原查詢相關度不大時，局部分析會將大量無關的詞加入查詢，從而嚴重降低查詢精度，甚至低于不做擴展優化的情形#65377;

局部上下文分析(Local Context Analysis，LCA)方法^[6]是由Xu和Croft 提出來的，它在整體上是一種局部分析方法，但利用全局分析的詞共同出現頻率的思想避免了向原查詢加入不相關的詞#65377;局部上下文分析的方法被用于INQUERY系統中，并在TREC標準測試集上取得了良好的效果#65377;實驗表明，該方法的檢索結果明顯優于傳統的全局分析方法和局部分析方法#65377;局部上下文分析的工作流程如下:

(1)使用檢索系統得到與原查詢最相關的n篇文章，一般是初始檢索得到的前n篇文章#65377;

(2)從該n篇文章中選取與原查詢最相關的詞與詞組，相關度計算為

bel(Q，c)=∏ti∈Q[δ+log(af(c，ti)+1)×idfc/log(n)]idfi

af(c，ti)=∑nk=1ftikfck

其中，af(c，ti ) 是文章中出現的詞與查詢用詞共同出現的頻率;bel 表示詞與該查詢之間的相關程度，用于決定與原查詢相關的擴展用詞#65377;

(3)將m個最相關的(即bel值最高的)詞或詞組加入原查詢構成新查詢#65377;

局部上下文分析的應用效果仍然高度依賴于初次檢索的結果，如果初次檢索返回的多數文檔與原查詢無關，該方法仍會將大量無關的詞加入新查詢，從而大大降低最終的檢索精度#65377;因為局部上下文分析僅僅考慮前n篇文檔，假設初次查詢的前n篇文章認為是與用戶查詢意圖最相關的文章，并以此為依據對查詢進行擴展#65377;然而這種假設與實際情況并不是十分吻合，如當某個用戶遞交的查詢中包括關鍵字“bank”時，返回的前n篇文檔既包括與“銀行”“金融”相關的文檔，又包含與“河岸”“河堤”相關的文檔#65377;因此利用前n篇文檔進行查詢擴展時，由于自然語言的歧義性，有可能檢索出比初始化查詢更差的檢索結果#65377;

基于用戶查詢日志的查詢擴展^[7]的目的，是根據用戶日志在新的查詢來臨時選取與該查詢最相關的文章用詞來形成新的查詢#65377;當給出某個查詢的情況下，根據以往大量用戶的日志文件計算查詢中的某個關鍵字出現時，與之相關聯的文章的條件概率#65377;則根據貝葉斯公式，該條件概率表示為

基于用戶日志的查詢擴展方法的特點是首先有大量的用戶日志存在，這需要有一個積累的過程，而且基本上要求大量的用戶有共同的興趣#65377;另外，基于用戶日志的查詢擴展需要在服務器端實現#65377;

通過對傳統查詢擴展方法的比較，局部上下文分析方法的性能相對較好，但其缺陷主要在于事先無法判別初次查詢結果中的前n篇文章是否與用戶查詢意圖相關#65377;因此，為了提高查詢擴展的性能，本文在傳統局部上下文分析方法的基礎上，通過引入用戶興趣模型，選擇初次查詢結果中與用戶查詢意圖最相關的前n篇文章作為查詢擴展詞的來源#65377;以下將分別介紹用戶興趣模型的挖掘過程和基于用戶興趣模型的局部上下文分析方法#65377;

2用戶興趣模型挖掘

用戶興趣模型的挖掘，主要是根據一個分類體系，將用戶的興趣主題依次劃分到分類系統的目錄或子目錄下#65377;因此，用戶興趣模型挖掘的準確性，在很大程度上依賴于分類算法的性能#65377;目前已有的分類算法中，效果比較理想的是支持向量機SVM^[8]，它是由Vapnik提出的一種建立在統計學習理論基礎上的機器學習方法，是一種基于結構風險最小化的新型機器學習技術，也是一種具有很好泛化能力的回歸方法#65377;本文之所以選擇SVM作為分類算法，是由于SVM分類器的目標是尋找最優超平面，而SVM算法能夠處理具有很大特征維數的數據，特別是網頁等具有高維特征向量的分類問題#65377;實踐證明，SVM分類器與其他的分類算法相比具有更好的性能#65377;Dumais在實驗中利用Reuters21828數據集實驗中得出SVM算法比Native Bayes算法#65380;決策數算法#65380;Bayes網絡等具有較大的優勢#65377;

SVM分類器與其他分類器相比具有分類精確度高#65380;速度快的優點，尤其適用于大樣本訓練集和特征集的分類#65377;本文的分類思想如下:首先，由于Yahoo分類目錄是采用人工的分類，對網頁的分門別類比較準確，本文采用Yahoo分類目錄中的網頁作為訓練集，對SVM分類器進行訓練;然后，基于本文的方法是在客戶端實現，采用用戶平時的網頁瀏覽歷史記錄和用戶收藏夾作為測試集，利用已經訓練好的SVM分類器進行測試，從而挖掘用戶的興趣主題#65377;用戶興趣建模主要包括以下幾個步驟，具體流程如圖 1所示#65377;

2.1Yahoo分類目錄網頁下載

為了快速地下載網頁，系統設計了一個基于Yahoo分類目錄的網頁爬蟲程序(Yahoo Spider)對Yahoo分類目錄網頁地址(http://dir.yahoo.com/)進行分類下載#65377;Yahoo Spider采取多線程，即為第一層目錄中的每個目錄分配一個線程，共14個線程#65377;在Yahoo分類目錄中，整個目錄呈樹狀結構，每個樹狀目錄的層數均不一樣，但是每個目錄包含的層數有限#65377;因此，Yahoo Spider不規定具體的搜索層數，而是在程序中一直采用深度優先算法，一直到樹葉再返回上一層#65377;使用一邊下載一邊解析的方式，即Yahoo Spider解析Yahoo網頁目錄，首先為當前目錄創建一個目錄文件夾，然后把該目錄下包含的子目錄和包含的網頁超鏈接地址保存在一個文本文件中，最后根據這些文本文件的內容創建相應的子目錄文件夾并下載相應的URL網頁到該目錄下(圖2)#65377;

2.2網頁數據的預處理

利用Yahoo Spider程序將Yahoo分類目錄中的網頁下載到本地硬盤后，再對這些網頁進行預處理操作，包括去掉網頁標簽(Tag)#65380;停用詞過濾以及詞綴剪枝(Stemming)操作等#65377;其中停用詞過濾只需用Stopwords算法的停用詞列表(Stoplist)即可完成，而詞綴剪枝也可以采用已有的Porter算法操作#65377;經過Stopwords算法進行停用詞過濾與Stemming剪枝算法后，采用傳統的tf#8226;idf算法對網頁中的詞匯賦予不同的權重，解析成以下libSVM的格式#65377;libSVM要求的文件格式是

2.3訓練SVM分類器

本文采用臺灣大學林智仁等開發設計的一個簡單#65380;易于使用和快速有效的SVM模式識別與回歸軟件包——libSVM設計文本自動分類器，對上一步經過預處理的Yahoo分類目錄網頁進行訓練，然后把用戶收藏夾以及IE瀏覽歷史記錄進行測試#65377;

2.4測試用戶信息挖掘用戶興趣模型

SVM分類器經過訓練之后，就可以用來測試用戶的興趣主題#65377;通常用戶的興趣主題包括長期興趣與短期興趣#65377;長期興趣用來揭示用戶的長期興趣和趨勢，需要在分析用戶的整個歷史瀏覽記錄的基礎上，將用戶的興趣主題映射到某一分類模式中特定的分類主題下#65377;通常每個用戶對應于一個或多個興趣主題#65377;具體算法如下:

(1)首先對整個IE瀏覽歷史記錄與用戶收藏夾中的網頁按時間進行分塊，如以一周為單位分塊，形成window 1#65380;window 2#65380;…#65380;window n#65377;

(2)對不同分塊window i中的網頁集合在測試集中賦予不同的權重(Weight)，本文對IE瀏覽歷史錄中的網頁，對最近一個星期的網頁賦予權重為1，然后對剩余的網頁以0.8i遞減(i=1~n，i為星期指數);對IE收藏夾中的網頁，對最近一個星期的網頁賦予權重為2，對剩余的網頁以2×0.8i遞減#65377;

(3)依次將IE瀏覽歷史記錄與用戶收藏夾的網頁逐個放進已訓練好的分類器中進行測試，如果測試得到第i個網頁屬于主題(Topic)類別j，則相應的主題類別的得分Sj=Sj+wi#65377;其中wi為在第i個網頁在測試集中賦予的權重#65377;

(4)最后抽取得分Sj在前k位且得分Sj>λ的主題類別作為用戶的興趣主題#65377;其中k是預先設定的閾值#65377;

短期興趣用來揭示用戶短期的信息需要，通常只需要考察用戶近段時間內的瀏覽習慣或瀏覽記錄，因此短期興趣建模涉及到的算法與長期興趣建模基本上相似#65377;對IE歷史記錄中的網頁，僅僅分析與最近一段時間內(如最近一個星期)所瀏覽的網頁;對于用戶收藏夾中的網頁，采用與長期興趣分析相同的算法實現#65377;通過以上步驟，就建立了用戶興趣模型#65377;

實驗的目的之一是為了驗證該查詢擴展機制對自然語言的消歧效果，而且所采用的查詢關鍵詞均具有很強的歧義性#65377;因此，只能采用模擬實驗來進行，即針對每個帶有歧義性的查詢關鍵詞所代表的各種概念，分別收集一定數量的網頁作為IE歷史瀏覽記錄與用戶的收藏夾#65377;例如對于關鍵詞Python，可以表示三種不同的概念#65377;首先在Google平臺上檢索Python，然后對于Python所表示的每種概念分別選擇10個網頁作為用戶收藏夾1~3#65377;每個收藏夾代表不同用戶的興趣#65377;最終得到一個用戶興趣模型如表 1所示#65377;

3UPLCA模型

信息檢索的實質過程是將信息集合與用戶需求集合相匹配的過程#65377;由于自然語言的歧義性，以往的檢索方法不能從根本上提高Web信息檢索的性能#65377;已有的查詢擴展方法，如全局分析#65380;局部分析#65380;局部上下文分析雖然在一定程度上解決了查詢詞的歧義性，但是查詢擴展時引入的擴展詞又增加了最終查詢詞的歧義性，因此不能從根本上提高Web信息檢索的查全率與查準率#65377;在上述查詢擴展方法中，局部上下文方法的應用效果較好#65377;因此，本文在局部上下文分析方法的基礎上，結合個性化檢索，將用戶興趣與局部上下文分析方法相結合，設計了基于用戶興趣的局部上下文分析(UPLCA模型)模型，具體過程如圖3所示#65377;

通過用戶的收藏夾以及IE歷史瀏覽記錄，學習用戶的興趣模型，將用戶的興趣模型關聯到Yahoo分類目錄的某個目錄下#65377;這種方法本質上是建立在局部上下文分析與相關反饋的基礎上，即首先初始化查詢Q，得到檢索結果D#65377;與局部上下文分析和局部分析不同的是，該方法不是直接對初始化查詢得到的最前面的n篇文檔進行分析和查詢擴展，而是首先利用已經訓練好的SVM分類器，對初始查詢結果中最前面的n篇文檔進行分類#65377;對于每篇文檔，如果該文檔與用戶的興趣主題相關，則將該文檔作為查詢擴展的數據源;反之，則不納入查詢擴展#65377;將與用戶興趣主題相關的的文檔用局部上下文分析方法進行查詢擴展#65377;

4實驗及結果分析

該系統的主要目的是根據用戶在進行信息檢索時，在初始查詢詞的基礎上，幫助用戶形成更加有效的查詢關鍵詞，從而對查詢進行優化#65377;既然目前Web用戶在檢索信息時使用的一般是短查詢，而且自然語言中存在大量具有歧義性的關鍵詞，因此，實驗中本文特意選擇有歧義性的詞匯作為查詢關鍵詞，如最有針對性的查詢是僅僅選擇具有顯著歧義性的單一詞匯作為查詢關鍵詞#65377;為了評估本文的查詢擴展方法的性能，采用查準率(Precision)和查全率(Recall)作為評估標準，t檢驗作為對比實驗的顯著性驗證#65377;

其中，A為信息庫中與查詢相關的文檔，B為用戶該次查詢所獲取的文檔，|A∩B|為用戶該次查詢所獲取的相關文檔#65377;

為了測試本文提供的查詢擴展方法在短查詢和自然語言中的消歧效果，實驗中專門選擇具有顯著歧義性的詞匯作為測試的查詢集，如Bat#65380;Bug#65380;Hardware#65380;Mouse#65380;Python等，如表 2所示#65377;為了比較不同查詢長度對系統檢索性能的影響，分別選擇了不同長度的查詢關鍵詞作為查詢子集#65377;第一類查詢子集僅僅包含一個關鍵詞，如Bat#65380;Bug#65380;Hardware#65380;Mouse#65380;Python等#65377;例如，一個用戶提交一個關鍵詞Bat給檢索系統，假設該用戶感興趣的是買一幅網球拍(Buying a baseball bat)#65377;在這種情況下，與查詢詞Bat以及用戶的興趣Baseball有關的文檔將被作為相關(Signal)文檔處理，而其他的文檔，如與Bat mammal相關的文檔將被作為干擾(Noise)文檔#65377;第二類查詢子集僅僅包含兩個關鍵詞，如Baseball bat#65380;Bat mammal#65380;Bug spy#65380;Hardware computer#65380;Hardware tools#65380;Hardware upgrade#65380;Mouse computer#65380;Python snake等#65377;例如，當用戶用Bug spy作為查詢關鍵詞時，如果用戶的興趣是與Surveillance有關的信息，那么與Software progamming和Insect有關的而包含Bug spy的文檔被認為是干擾文檔#65377;第三類查詢子集僅僅包含三個關鍵詞作為查詢，如Baseball equipment bat#65380;Bat mammal fly#65380;Bug spy security#65380;Computer hardware upgrade#65380;Computer hardware mouse#65380;Home hardware tools#65380;Python snake reptile#65377;隨著查詢關鍵詞數量的增加，自然語言的歧義性也隨之減弱#65377;

在實驗中，本文分別對傳統的基于一個關鍵詞#65380;兩個關鍵詞#65380;三個關鍵詞的簡單查詢，基于局部上下文分析(LCA)的查詢擴展，基于本文UPLCA的方法，計算不同相似度閾值下的平均查準率和平均查全率的曲線圖(圖4~9)#65377;

從圖4~9中可以看出，本文的查詢擴展方法確實獲得了相當好的結果，與基于局部上下文分析方法和傳統的簡單查詢方法相比較，均得到了明顯的提高#65377;本文的方法與其他兩種方法的實驗結果之間在統計上存在顯著性差異#65377;

本文的方法尤其在消除查詢詞的歧義性方面取得了很好的效果#65377;對于一個關鍵詞的查詢中，由于實驗中選擇的查詢詞具有明顯的歧義性，本文的UPLCA方法相對于傳統的方法查準率提高了43.5%，查全率提高了33.7%，在與局部上下文分析的比較中，UPLCA方法的查準率比LCA方法提高了43.5%，查全率提高了19.6%#65377;同理，從曲線圖可以看出，其他情況下的實驗效果也比傳統方法與LCA方法優越，只是效果沒有一個關鍵詞明顯，其原因是隨著查詢詞的增加，查詢詞之間具有相互的消歧效果，詞典問題則在一定程度上會得到緩解#65377;總之，本文的方法明顯高于傳統的方法與基于局部上下文分析的查詢擴展方法#65377;另外，從實驗的曲線圖和表格中可以看出，基于局部上下文分析方法的查詢擴展的檢索性能并不是很理想#65377;其原因是實驗中選擇的查詢集均具有很大的歧義性，尤其是初始化查詢只有一個關鍵詞的情況下#65377;由于初始化的返回結果中有很多不相關的文檔，從而使得在這種情況下局部上下文分析方法并不優越于傳統的簡單查詢，甚至在實驗中的某些興趣主題下比傳統的方法效果更差#65377;

5結束語

本文在分析傳統查詢擴展方法不足的基礎上，吸取了LCA方法的優勢，同時通過建立用戶興趣模型克服了LCA方法的缺陷，提出了基于用戶興趣模型的LCA方法#65377;從用戶的角度考慮，本文的方法從兩個方面提高了信息檢索的性能:①查準率#65377;自從引入查詢擴展機制，具有明顯歧義性的查詢關鍵詞通過擴展詞的消歧作用，與傳統方法和LCA方法相比，其精確度大大提高#65377;②查全率#65377;通過比較本文的查詢擴展方法與傳統的簡單檢索方法，實驗顯示查全率確實得到了較大提高，因為附加的查詢擴展詞能夠檢索出初始化短查詢中所不能檢索的文檔#65377;然而從曲線圖中可以看出，本文的方法與LCA方法相比，查全率提高的效果并不明顯#65377;因此，下一步的工作是進一步引入概念檢索，在提高查準率的條件下，提高查全率#65377;

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。