基于隱式反饋的ＬＳＩ個性化信息過濾方法的研究

摘要：本文針對當前傳統潛在語義索引（LSI——latent semantic indexing）技術在提供信息過濾服務時已經不能滿足用戶個性化需求這一實際情況，提出利用隱式反饋技術來解決如何提供給不同用戶以不同信息結果這一問題。在傳統的LSI技術上提出了一種基于隱式反饋的LSI個性化信息過濾方法，該方法通過引入隱式反饋技術，將其應用于信息過濾中，從而可以為不同用戶提供更多更有針對性的信息結果。本文給出了該方法的公式和具體算法，為其應用的實現提供了理論基礎。

關鍵詞：信息過濾；潛在語義檢索；隱式反饋；奇異值分解

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)12-2pppp-0c

Method of LSI Personal Information Filtering Based on Implicit Feedback

ZHANG Hong，XU Qun-yi，SU Chen

(School of Computer Science Technology，China University of Mining and Technology，Xuzhou 221008，China)

Abstract:Technology of traditional latent semantic indexing (LSI)has not been satisfactory for user's personalized need. On the basis of traditional technology LSI，the paper propose to use the technology of LSI personalized information filtering to solver the problem that how to determine the user’s personalized information. Based on the technology of traditional LSI，the paper proposes a method of LSI personalized information filtering based on implicit feedback. Because the technology of implicit feedback is introduced in this method and applied in information filter， the method will provide more targeted information results for different peoples.A particular arithmetic and formula of the method is presented in this paper to offer the theoretical basis of the application.

Key words:Information Filtering;Latent Semantic Indexing;Implicit Feedback;Singlar Value Decomposition

1 引言

信息過濾技術的基本思想是從動態信息源中過濾掉比較固定的非需求信息，方法是通過在代理服務器中加入內容過濾功能，使其對內可以消除通過網頁機密造成的泄漏;對外可以過濾掉網頁中的無用信息。為最大限度將垃圾信息排除在系統之外，該技術要求過濾的內容性和實時性[1]， 因此需從過濾精度和過濾速度這兩個角度考慮完善該技術。

自然語言文本中的詞匯(術語)具有一詞多義(polysemy)和一義多詞(synonymy)的特征。由于一詞多義， 基于精確匹配的檢索算法會報告許多用戶不需要的東西; 由于一義多詞， 基于精確匹配的檢索算法又會遺漏許多用戶想要的東西。如果能基于自然語言理解來做這件事，那一切問題就都將解決。將面臨的 問題是:(1) 自然語言理解的水平目前還是有限度的；(2) 即使用自然語言理解， 效率也會很低。Bellcore以Dumais為首的研究小組試圖繞過自然語言理解，用統計的辦法達到同樣的目標，提出了一種稱為\"潛在語義索引\"的方法。\"潛在語義索引\"的英文名稱為\"Latent Semantic Indexing\"， 簡稱LSI。

傳統LSI方法的優點是（1）反映術語之間內在的相關性，（2）具有較高的效率。但是隨著科技的發展，需求的多元化，LSI在提供個性化信息過濾時就力不從心了。本文提出了基于隱式反饋的LSI個性化信息過濾方法，其目的是克服傳統的LSI在提供個性化服務時的不足，并且提高過濾精度。

2 潛在語義索引（LSI）

潛在語義索引（Latent Semantic Indexing），通過分析不同文檔中相同主題的共享詞匯，找到構成它們共同的根，用這個公共的根代替所有詞匯，以此來減少維空間。例如：“informing”、“information”、“informer”、“informed”可以用他們的根“inform”來表示，這樣可以減少屬性集合的規模。

LSI技術的工作原理是：首先將一個文本庫表示為 的術語(terms)-文本(documents)矩陣A，其中m表示文本庫中術語的個數，n表示文本庫中文件的數量。因此A可以表示A=[aij]m×n。

其中aij為非負值，表示第i術語在第j個文本中出現的頻度。由于術語和文件數量都很大，而單個文本中出現的數量又十分有限，因此A一般為稀疏矩陣。然后將該矩陣進行奇異值分解[2] (singlar value decomposition，簡稱SVD)，較小的奇異值被剔除。結果奇異向量以及奇異值矩陣用于將文本向量和查詢向量映射到一個子空間中，在該空間中，來自術語-文本矩陣的語義關系被保留，同時術語用法的變異被抑制。最后，可以通過標準化內積計算來計算向量之間的夾角余弦相似度，再將文檔與查詢的向相似度降序排列。

3 隱式反饋的LSI個性化信息過濾

3.1 用戶profile

對于個性化過濾系統來說最重要的是用戶的參與，因此我們需要對每一個用戶建立一個用戶興趣模型，用來跟蹤用戶的行為，進而對其行為進行判斷，從中可以了解到用戶的偏好，據此對不同用戶提供不同的過濾服務。

產生用戶profile的方法主要有兩種：

(1)由用戶自己提供自己的興趣，這種方法比較費時，而且有時用戶對自己的興趣表達不清楚。

(2)由Agent跟蹤檢測用戶的行為，自動產生并不斷地修改用戶的profile。

3.2 隱式反饋

定制好用戶profile后，應當根據用戶當前的行為，調整用戶興趣的權值。反饋的方法有兩種：顯式反饋和隱式反饋。顯示反饋需要用戶對信息進行評價，進而達到學習的目的。但是這種做法的效率不高。隱式反饋不要求用戶對反饋的信息做任何評價，而是由系統自動完成。像點擊鼠標之類的簡單動作不能有效的揭示用戶的興趣[3]；而像用戶閱讀頁面時間、用戶查詢、標記書簽這類動作能夠有效的揭示用戶的興趣[4]。

Rocchio等在Smart系統中提出了幾種相關的反饋方法[5]，將特征項重新加權和查詢相結合，并基于VSM模型（Vector Space Model）[6]定義了查詢修改方法：

zh01.tif （1）

其中Q為原始查詢的特征向量，Ri為相關文獻的特征向量，Si為不相關文獻i的特征向量，n1為相關文獻數，n2為不相關文獻數，?、β為相關文獻和不相關文獻對查詢向量的貢獻因子。因此，Q’是原始查詢、相關文獻和不相關文獻的特征向量的向量和。

3.3 索引項的加權方法

通常使用局部加權策略和全局加權策略分別評價某一文檔中的和整個文檔集中索引項的相對重要性。將詞加權策略應用到矩陣A中，其元素aij的值將由索引項i在文檔j中出現的次數變為aij=L(I，j)*G(i)，其中L(i，j)表示索引項i在文檔中j中的局部加權函數，G(i)表示索引項i在文檔集中的全局加權函數，在諸多加權方案中選取一個一個比較實用的索引項重評價函數：zh02.tif（2）

文檔i向量表示為：Wi=(wi1，wi1，…，wik，…，win)

其中tfik是文檔i中術語Tk出現的頻率，nk為術語Tk在文檔集中出現的頻數，nk、N是在用戶使用中由動態統計得出。

3.4 隱式反饋的LSI個性化信息過濾

首先，用戶profille包含多個興趣，每個興趣q可以用向量形式表示為：

Wq=(wq1，wq2，…， wqk，…，wqk)，其中wqk為第k個術語Tk的權值，n為用戶profile中術語的個數[7]。文檔i與用戶profile的興趣q的相關度計算公式如下：

zh03.tif（3），

其次，在文檔過濾的過程中，須考慮到用戶幾個動作：閱讀時間(rt)，加入標簽(bm)，拖動滾動條(sc)，復制當前文檔(cp)，跟蹤超鏈接(fl)，在當前文檔內搜索(fd)。反饋計算公式為zh04.tif（4），其中0≤fb(i)≤1，B={rt，bm，sc，cp，fl，fd}，cb是分配給每一個動作的權值。

再次，用文檔的的反饋信息來更新用戶profile， 學習規則如下：wqk=wqk+?Si.wik（5），?為學習因子。修改原則為：如果文檔中的的某個術語的權重很高，超過給定的最高闕值，那么相應的這個術語的權重會增加；如果文檔中的的某個術語的權重在給定的闕值之間，那么就不修改這個術語的權重；如果文檔中的的某個術語的權重低于給定的最低闕值，那么就將這個術語的權重降低。

最后，假設術語—文檔矩陣A有m行（每行表示每個術語在文檔中出現的頻率）n列（每列表示集合中的每個文檔），SVD(A) =T0S0D0T（6），T0是一個m×l的術語—概念矩陣，它的標準正交列稱為左奇異向量；S0是一個l×l的術語-概念正奇異按降序排列的對角矩陣，D0是一個l×n的術語—概念矩陣，它的標準正交列稱為右奇異向量。l是矩陣A的秩。

文檔向量表示：ATA是n×n矩陣，進分析其元素(ATA)ij表示文檔i與文檔j之間的相似度，即有：

ATA=D0S0T0TT0S0D0T=D0S0(D0S0(D0S0)T（7）

LSI中的關鍵創新在于只保留 S0中的 k個最大的奇異值，而將其他的值置為 0 。k的值是設計時的一個參數，取值通常在 100至200之間。原來的A矩陣可以用A’來近似，A’=TSDT， T是一個含有標準正交列的 m×k矩陣，S是一個正定的k×k對角矩陣，D是一個含有標準正交列的n×k矩陣。

文檔i和文檔j夾角余弦相似度為：zh05.tif（8）過濾結果按上述相似度的計算結果降序排序，選取合適的闕值，將大于該闕值的文檔返還給系統的用戶。

潛在語義索引方法通過對大規模文檔集中索引項同現存信息的統計分析，利用索引項矩陣創建一個信息的多維語義空間，從而揭示出文檔索引項與索引項之間、索引項與文檔之間存在的潛在語義關系。通過對索引項文檔矩陣進行奇異值分解，生成若干個正交因子的降秩空間，該控件與原始的索引項文檔矩陣所體現的特征信息保持一致，它同時還可以體現出整個文檔的語義結構，反映文檔集中詞匯信息的主要相關模式，從而剔除了其中因具體詞匯變化不定而帶來的詞匯噪聲信息。

4 隱式反饋的LSI個性化信息過濾具體算法：

通過上述分析，將基于隱式反饋的LSI個性化信息過濾方法的算法如圖1所示，具體描述如下：

(1)創建用戶profile模型庫，建立基本的用戶profile。

(2)利用分詞技術提取術語，構造術語庫。

(3)對不同的屬性空間對文檔進行分類。

(4)計算術語在用戶文檔中出現的頻率，構建術語-文檔矩陣。

(5)用戶提出搜索信息，將符合用戶興趣的術語作為查詢關鍵詞傳給元搜索。

(6)元搜索向信息檢索系統發出查詢請求，并返回符合條件的URL列表。

(7)元搜索向信息檢索系統發出查詢請求，并返回符合條件的URL列表。

(8)計算用戶profile模型與當前文檔的相關度。

(9)計算出的相關度如果大于所規定的最小相關度，就以當前的URL為起點，對每個文檔進行搜索。

(10)對術語-文檔矩陣進行奇異值分解，剔除小奇異值。

(11)對于每個文檔d，用排出了SVD的術語的新的向量替換原有的向量。

(12)計算文檔之間的相似度，完成文檔之間的匹配。

(13)排序輸出過濾后的結果。

(14)根據用戶行為調整用戶profile模型庫。

5 結束語

本文對隱式反饋技術在信息過濾方面進行了闡述，并提出了具體算法，說明了隱式反饋的LSI個性化信息過濾的優勢及其涉及到的關鍵技術，為實現該方法提供了基礎。本文的創新點在于隱式反饋的LSI個性化信息過濾方法能夠克服傳統的LSI在提供個性化服務時的不足，并且提高過濾精度。文章的由于用戶行為和興趣的不確定性、用戶profile完備性、中文分詞技術不成熟是該方法的基本的問題，因而也是進一步研究的主要方向。

參考文獻：

[1] Papadimitriou C，Raghavan P， Tamaki H et a Latent Semantic Indexing: A Probabilistic Analysis[J].Journal of Computer and System Sciences，2000:61(2):217-235.

[2] Davenport，T，H.，L，Prusak.Working Knowledge:How Organizations Manage What They Know[M].Boston，MAI Harvard Business School Press，1998.

[3] Claypool，Le M，Waseda P，et al.Implicit Interest Indicators.Proceedings of the ACM Intelligent User Interfaces Conference[A].ACM Press[C]，2001:14-17.

[4] 劉維光，陳立偉.一種基于DHT的P2P搜索方法[J].微計算機信息，2006，3-3:131-133.

[5] Rocchio J J，Ide E.The Smart Retrieval System.Prentice Hall，1971.

收稿日期：2008-01-29

作者簡介：徐群益（1982-），男，江蘇南通人，中國礦業大學計算機學院的碩士研究生，主要研究方向：計算機網絡。

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文?！?/p>