基于用戶行為分析的個人信息檢索研究

蔣在帆，王 斌

(1. 中國科學(xué)院 計算技術(shù)研究所，北京 100190; 2. 中國科學(xué)院 研究生院， 北京 100049)

1 引言

世界范圍的WWW應(yīng)用飛速發(fā)展，信息量呈幾何級數(shù)逐年遞增。利用Web搜索引擎，人們可以從海量信息中找到他們所真正需要的信息。除了Web上的信息不斷增加外，個人計算機硬盤上存儲的信息量也不斷增大。隨著時間的流逝，用戶計算機上的信息越來越多，這使得人們經(jīng)常花費大量時間進行個人信息檢索，即在自己計算機上搜尋文檔資料、演示文稿、表格或電子郵件，然而，在實現(xiàn)這些查找需求時，當(dāng)前操作系統(tǒng)中所提供的搜索服務(wù)在查找效率和效果方面并不令人滿意。

桌面搜索工具的出現(xiàn)，幫助用戶解決了一些搜索相關(guān)的問題。Google、百度、雅虎、微軟都開發(fā)了自己的桌面搜索工具。除了業(yè)界之外，學(xué)術(shù)界也對桌面搜索表現(xiàn)出極大的興趣，開發(fā)出包括Stuff I’ve seen[1]、Connections[2]和Confluence[3]等在內(nèi)的一些原型系統(tǒng)。

然而，和互聯(lián)網(wǎng)檢索可以利用網(wǎng)頁內(nèi)容、鏈接、錨文本、大量用戶訪問歷史等信息所不同的是，個人信息檢索能夠利用的信息卻非常有限。另外，互聯(lián)網(wǎng)檢索中重復(fù)的信息很多，有很多相關(guān)信息符合用戶需求，而在個人信息檢索中，數(shù)據(jù)重復(fù)性較少，對查全率和查準率要求更高。因此，個人信息檢索中的結(jié)果排序是一個非常困難的問題。為了解決這個問題，學(xué)術(shù)界進行了一系列的研究，業(yè)界也開發(fā)了一些個人信息檢索工具(如前面提到的桌面搜索工具)。但是總的來說，一方面，目前有關(guān)個人信息檢索排序的研究很少；另一方面，現(xiàn)有研究或工具中結(jié)果排序的效果仍然不盡如人意。

本文將基于用戶行為對個人信息檢索的排序進行深入研究，其中用戶行為包括查詢行為和文件訪問行為，前者記錄在檢索系統(tǒng)的查詢?nèi)罩局?，而后者記錄在文件訪問日志中。本文利用查詢?nèi)罩精@取訓(xùn)練數(shù)據(jù)，利用文件訪問日志獲取文件自身的權(quán)重，最后使用Ranking SVM[4]學(xué)習(xí)排序函數(shù)。實驗結(jié)果表明，本文方法好于傳統(tǒng)的TFIDF方法。

本文后續(xù)內(nèi)容組織如下： 第2節(jié)介紹相關(guān)工作；第3節(jié)介紹本文工作；第4節(jié)給出實驗和結(jié)論；第5節(jié)對全文進行總結(jié)。

2 相關(guān)工作

Stuff I’ve Seen(SIS)[1]是微軟研究院開發(fā)的一個桌面搜索工具。它主要的設(shè)計目標是幫助用戶重新使用(re-use)用戶之前使用過的信息。然而，有關(guān)該工具的具體技術(shù)細節(jié)還不得而知。

Haystack[5]主要的思想是個性化，即每個人都會以自己的方式來使用信息。Haystack自動創(chuàng)建文件之間的聯(lián)系，并利用行為分析來擴大搜索結(jié)果。另外Haystack使用Resource Description Framework(RDF)來描述各種信息。

Connections[2]是一個利用文件訪問信息輔助排序的搜索工具。在Connections中，Craig A.N. Soules和Gregory R.Ganger實現(xiàn)了系統(tǒng)層的文件系統(tǒng)檢測模塊，對用戶open，read/write等文件操作進行監(jiān)控。利用文件監(jiān)控信息，他們設(shè)計算法來得到文件之間的鏈接關(guān)系和鏈接的權(quán)重。Connections的評測結(jié)果顯示，在搜索的前10個結(jié)果中，它提高了召回率(13%～22%)和準確率(23%～29%)。

Paul-Alexandru Chirita和Wolfgang Nejdl在文獻[6]中利用各種方式來建立文件之間的鏈接。在試驗中，他們使用Lucene作為系統(tǒng)，TF×IDF 作為基本的排序方法，并對比了17種算法。最后的結(jié)果顯示他們的技術(shù)可以對平均(加權(quán)的)準確率提高10.67%。

在文獻[7-8]中，Sara Cohen等研究了利用桌面搜索工具的查詢?nèi)罩緛韺W(xué)習(xí)排序函數(shù)的算法。最后的評測結(jié)果表明，基于學(xué)習(xí)的方法顯著好于其他排序方法。但Sara沒有利用用戶的文件訪問信息。

一方面，現(xiàn)有的一些桌面搜索工具并沒有公布其技術(shù)細節(jié)，因此無法作為研究的參考對象；另一方面，現(xiàn)有的研究方法中并沒有對不同用戶行為對個人信息檢索的影響進行深入的研究。鑒于上述原因，本文對用戶行為對個人信息檢索的影響展開深入的研究，并以期作為今后相關(guān)研究的參考對象。

3 本文工作

本文的主要思想是利用用戶行為對個人信息檢索的排序進行研究，其中用戶行為包含查詢行為和文件訪問行為，下面對這些行為進行介紹。

3.1 查詢行為

用戶在使用個人信息檢索系統(tǒng)時，系統(tǒng)會記錄用戶的查詢信息以及返回的相關(guān)文檔和點擊信息，我們將這些信息稱為查詢行為。用戶提交查詢后，檢索系統(tǒng)會將用戶輸入的查詢、選擇的排序函數(shù)、需要檢索的域、過濾的文件類型以及對應(yīng)系統(tǒng)返回的相關(guān)文檔信息寫入查詢?nèi)罩尽榱搜芯坑绊懪判虻囊蛩?，日志會記錄用戶輸入查詢時每個相關(guān)文檔當(dāng)時的信息，比如文件名、所在目錄、最近訪問時間、最近修改時間、最近屬性改變時間等。

用戶輸入查詢后通常會點擊相關(guān)文檔，點擊的文檔通常表示用戶想要查找的文檔，在獲取訓(xùn)練數(shù)據(jù)時，可用于得到用戶對文檔的相關(guān)度評分。我們將點擊信息也記錄在查詢?nèi)罩局小?/p>

對查詢?nèi)罩具M行處理可以得到訓(xùn)練數(shù)據(jù)，基于這些數(shù)據(jù)可以學(xué)習(xí)出排序函數(shù)。

3.2 文件訪問行為

文件訪問行為記錄在文件訪問日志中，為了獲取文件訪問日志，我們對文件系統(tǒng)進行監(jiān)控，并記錄文件的操作信息。這些信息包括文件的路徑，文件操作的時間以及文件的操作方式。

對文件訪問日志進行處理，我們可以計算文件自身的權(quán)重。本文將基于兩種方式計算文件自身的權(quán)重，一種基于文件的訪問時間，另一種基于文件之間的關(guān)聯(lián)?；谖募P(guān)聯(lián)的方法主要思想是在較小時間間隔內(nèi)順序訪問的文件之間建立虛擬鏈接，然后使用鏈接分析的算法計算文件的權(quán)重。算法如圖1 所示。鏈接分析的算法我們使用Web檢索中的PageRank[9]算法。

3.3 Ranking SVM介紹

Ranking SVM[4,10-11]是解決排序問題的典型算法。它的核心思想是將排序問題轉(zhuǎn)化成分類問題進行解決。篇幅所限，本文不再給出Ranking SVM方法的具體實現(xiàn)細節(jié)，感興趣的讀者可以參考相關(guān)文獻。本文實驗中將使用Ranking SVM學(xué)習(xí)排序函數(shù)。

4 實驗和結(jié)論

4.1 實驗準備

我們開發(fā)的個人信息檢索系統(tǒng)LUPINS在真實情況下運行了3個月的時間，共收集到查詢366個，其中每個查詢的平均返回結(jié)果為265.48個，查詢的平均長度為1.79(詞的個數(shù))。在所有查詢中產(chǎn)生點擊動作的查詢有204個，平均點擊的文檔數(shù)為1.19個。該系統(tǒng)中同時實現(xiàn)了Lucene系統(tǒng)中所使用的TFIDF排序方法。

4.2 基于查詢行為的實驗

在實驗中，我們假設(shè)用戶點擊的文檔為相關(guān)文檔，其他為非相關(guān)文檔。這也是相關(guān)工作的普遍做法。對查詢?nèi)罩竞忘c擊日志進行處理可以獲取訓(xùn)練數(shù)據(jù)，然后可使用Ranking SVM學(xué)習(xí)排序函數(shù)。由于傳統(tǒng)的排序函數(shù)使用TFIDF等查詢相關(guān)的屬性進行排序，我們首先使用查詢相關(guān)的TFIDF屬性同傳統(tǒng)的方法進行對比，后面會利用文件訪問日志獲取文件自身的權(quán)重，并加入這些權(quán)重使用Ranking SVM學(xué)習(xí)排序函數(shù)。

訓(xùn)練排序函數(shù)使用的屬性如表1所示。

實驗中我們使用MRR和NDCG作為評價指標，實驗結(jié)果如表2所示。

表1 基本屬性

表2 基本屬性的排序結(jié)果

從表2可以看出在NDCG、MRR評價中，采用TFIDF方法的Lucene系統(tǒng)的結(jié)果最好，并且Lucene的結(jié)果同Ranking SVM的結(jié)果相差不大。Lucene的結(jié)果比Ranking SVM好1%～2%。這說明在目前數(shù)據(jù)規(guī)模下，僅基于TFIDF的查詢相關(guān)屬性，Ranking SVM學(xué)習(xí)的排序函數(shù)可以達到傳統(tǒng)TFIDF排序方法的效果。

4.3 基于文件訪問行為的實驗

文件訪問日志中記錄了用戶訪問文件的信息，這些信息代表了文件自身的權(quán)重。比如最近訪問時間、文件的訪問頻率等。通常越是最近訪問的文件，用戶更傾向于再次訪問，在排序時應(yīng)該排的更前。同樣訪問次數(shù)越頻繁的文件，也應(yīng)該排的更前。利用最近訪問時間，訪問頻率等信息，我們可以計算文件的權(quán)重用于排序。

對文件訪問日志進行處理后，我們使用兩種方式計算文件自身的權(quán)重，一種基于文件訪問的時間，另一種基于鏈接關(guān)系。

基于時間的排序我們使用三種方法，一種基于最近訪問時間，一種基于訪問頻率，另一種基于文件每一次的訪問信息。計算公式如表3所示。

基于鏈接關(guān)系的方法認為在很短時間內(nèi)訪問的文件之間有鏈接關(guān)系，然后并可使用PageRank算法獲取文件的權(quán)重。計算的權(quán)重記作file_link_weight。

表3 基于時間的計算方法

實驗結(jié)果如表4所示。

表4 基于時間的計算方法的實驗結(jié)果

基于last_access和file_access_weight屬性的結(jié)果最好，frequency的結(jié)果次之，file_link_weight的結(jié)果最差。這說明用戶傾向于檢索最近訪問的文件。file_link_weight的結(jié)果并不好可能的原因是數(shù)據(jù)量不夠大，并且鏈接的噪音太多。

上面基于時間和鏈接獲取了文件自身的權(quán)重，這些權(quán)重可以和相關(guān)度進行組合，組合的權(quán)重用于最后的排序。本文中使用相乘的方式組合這些權(quán)重。

相關(guān)度使用lucene_score屬性，基于時間的方法使用last_access屬性，文件關(guān)聯(lián)的權(quán)重使用file_link_weight屬性。組合組合方式如表5表所示。

表5 組合屬性

表6給出了相關(guān)度、時間、鏈接以及它們組合權(quán)重的排序結(jié)果。

表6 組合屬性排序結(jié)果

從表6可以看出，使用lucene_score和last_access屬性相結(jié)合的排序結(jié)果好于其他兩種組合方式，在NDCG評價中，lucene_score_x_last_access的結(jié)果比第二名的組合方式高出7%～8%。在MRR評價中比第二名高出10%左右。實驗說明組合相關(guān)度和文件自身權(quán)重可以提高檢索的效果。另外我們看出，基于文件自身權(quán)重的排序效果普遍好于基于相關(guān)度的排序，原因可能是用戶的查詢包含的相關(guān)文檔較多，特別是加入全文信息后，相關(guān)文檔很多，而且相似度相差不大，但文件自身的權(quán)重更能反映用戶對文件的評分。

4.4 結(jié)合兩種行為的實驗

4.2節(jié)中我們基于查詢相關(guān)的屬性，使用Ranking SVM學(xué)習(xí)了排序函數(shù)，4.3節(jié)中研究了使用文件訪問日志獲取文件權(quán)重進行排序的算法。本節(jié)中，我們將通過Ranking SVM結(jié)合查詢相關(guān)的屬性和文件自身的權(quán)重學(xué)習(xí)排序函數(shù)。

將文件基本屬性記為A1，訪問時間和頻率屬性記為A2，file_access_weight屬性記為A3，file_link_weight屬性記為A4，將S_A、S_L、S_A_L這三種屬性記為A5(見4.3節(jié))。依次加入這些屬性后Ranking SVM排序?qū)嶒灲Y(jié)果如表7所示。

表7 逐步加入屬性Ranking SVM排序結(jié)果

從圖2中可以看出，逐步加入屬性后，Ranking SVM的評價指標逐步提高(在NDCG@2中，加入file_link_weight后，下降1%)。特別是加入時間和頻率信息后，NDCG、MRR平均提高18%～20%。和之前預(yù)想的結(jié)果一樣，加入文件自身的屬性后，Ranking SVM排序效果逐步提高。而且在目前的訓(xùn)練集上，Ranking SVM的效果最好。這證實了我們方法的有效性。

圖2 加入多種屬性后Ranking SVM排序結(jié)果折線圖

5 總結(jié)和展望

本文中，我們基于用戶行為對個人信息檢索的排序進行了深入研究，其中用戶行為分為檢索系統(tǒng)的查詢行為和計算機上的文件訪問行為，本文通過查詢行為獲取訓(xùn)練數(shù)據(jù)，文件訪問行為獲取文件自身的權(quán)重，并利用統(tǒng)計學(xué)習(xí)的方法結(jié)合這兩類行為學(xué)習(xí)排序函數(shù)，實驗結(jié)果顯示文檔自身的權(quán)重普遍好于基于相關(guān)度的排序，使用Ranking SVM結(jié)合這兩類屬性學(xué)習(xí)的排序函數(shù)結(jié)果最好。

未來的工作包括： 使用更大的數(shù)據(jù)集進行訓(xùn)練，采用其他類型的排序函數(shù)，引入更多的特征用于排序等等。

[1] S.Dumais, E.Cutrel, J.Cadiz, G.Jancke, R.Sarin, and D.Robbins. Stuff I've seen: a system for personal information retrieval and re-use[C]//Proceedings of the 26th Annual International ACM SIGIR Conference. 2003.

[2] Craig A. N. Soules, Gregory R.Ganger. Connections: using context to enhance file search[C]//Proceedings of the Twentyth ACM Symposium on Operating Systems Principles. 2005： 23-26.

[3] Karl. Gyllstrom, Craig. Soules and Alistair. Veitch. Confluence: Enhancing Contextual Desktop Search[C]//Proceedings of the Thirtyth Annual International ACM SIGIR Conference. 2007： 23-27.

[4] JOACHIMS, T. 1999. Making large-scale SVM learning practical. Advances in Kernel Methods-Support Vector Learning[M]. MIT Press, Chapter 11.

[5] D.Karger, K.Bakshi, D.Huynh, D.Quan and V.Sinha. Haystack: A general-purpose information management tool for end users of semistructured data[C]//Proceedings of the Second Conference on Innovative Data Systems Research. 2005.

[6] Paul-Alexandru Chirita and Wolfgang Nejdl. Analyzing User Behavior to Rank Desktop Items[C]//Proceeding of the Second International Conference on Ubiquitous Information Management and Communication. 2008.

[7] Sara Cohen, Carmel Domshlak and Naama Zwerdling. On Ranking Techniques for Desktop Search[J]. ACM Transactions on Information Systems, Vol. 26, No. 2, Article 11, March 2008.

[8] Sara Cohen, Carmel Domshlak and Naama Zwerdling. On Ranking Techniques for Desktop Search[C]//Proceedings of the Sixteenth International World Wide Web Conference, May 8-12, 2007.

[9] L.Page, S.Brin, R.Motwani, and T.Winograd. The pagerank citation ranking: Bringing order to the Web[R]. Technical report, Stanford University, 1998.

[10] Yunbo Cao, Jun Xu, Tie Yan, Liu, Hang Li, yalou Huang and Hsiao-Wuen Hon. Adapting Ranking SVM to document retrieval[C]//Proceeding of the 29th Annual International ACM SIGIR Conference. 2006.

[11] SVMLight, http://svmlight.joachims.org[DB/OL].