摘要：本文針對(duì)當(dāng)前傳統(tǒng)潛在語(yǔ)義索引（LSI——latent semantic indexing）技術(shù)在提供信息過(guò)濾服務(wù)時(shí)已經(jīng)不能滿足用戶個(gè)性化需求這一實(shí)際情況，提出利用隱式反饋技術(shù)來(lái)解決如何提供給不同用戶以不同信息結(jié)果這一問(wèn)題。在傳統(tǒng)的LSI技術(shù)上提出了一種基于隱式反饋的LSI個(gè)性化信息過(guò)濾方法，該方法通過(guò)引入隱式反饋技術(shù)，將其應(yīng)用于信息過(guò)濾中，從而可以為不同用戶提供更多更有針對(duì)性的信息結(jié)果。本文給出了該方法的公式和具體算法，為其應(yīng)用的實(shí)現(xiàn)提供了理論基礎(chǔ)。

關(guān)鍵詞：信息過(guò)濾；潛在語(yǔ)義檢索；隱式反饋；奇異值分解

中圖分類(lèi)號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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 引言

信息過(guò)濾技術(shù)的基本思想是從動(dòng)態(tài)信息源中過(guò)濾掉比較固定的非需求信息，方法是通過(guò)在代理服務(wù)器中加入內(nèi)容過(guò)濾功能，使其對(duì)內(nèi)可以消除通過(guò)網(wǎng)頁(yè)機(jī)密造成的泄漏;對(duì)外可以過(guò)濾掉網(wǎng)頁(yè)中的無(wú)用信息。為最大限度將垃圾信息排除在系統(tǒng)之外，該技術(shù)要求過(guò)濾的內(nèi)容性和實(shí)時(shí)性[1]， 因此需從過(guò)濾精度和過(guò)濾速度這兩個(gè)角度考慮完善該技術(shù)。

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

傳統(tǒng)LSI方法的優(yōu)點(diǎn)是（1）反映術(shù)語(yǔ)之間內(nèi)在的相關(guān)性，（2）具有較高的效率。但是隨著科技的發(fā)展，需求的多元化，LSI在提供個(gè)性化信息過(guò)濾時(shí)就力不從心了。本文提出了基于隱式反饋的LSI個(gè)性化信息過(guò)濾方法，其目的是克服傳統(tǒng)的LSI在提供個(gè)性化服務(wù)時(shí)的不足，并且提高過(guò)濾精度。

2 潛在語(yǔ)義索引（LSI）

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

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

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

3 隱式反饋的LSI個(gè)性化信息過(guò)濾

3.1 用戶profile

對(duì)于個(gè)性化過(guò)濾系統(tǒng)來(lái)說(shuō)最重要的是用戶的參與，因此我們需要對(duì)每一個(gè)用戶建立一個(gè)用戶興趣模型，用來(lái)跟蹤用戶的行為，進(jìn)而對(duì)其行為進(jìn)行判斷，從中可以了解到用戶的偏好，據(jù)此對(duì)不同用戶提供不同的過(guò)濾服務(wù)。

產(chǎn)生用戶profile的方法主要有兩種：

(1)由用戶自己提供自己的興趣，這種方法比較費(fèi)時(shí)，而且有時(shí)用戶對(duì)自己的興趣表達(dá)不清楚。

(2)由Agent跟蹤檢測(cè)用戶的行為，自動(dòng)產(chǎn)生并不斷地修改用戶的profile。

3.2 隱式反饋

定制好用戶profile后，應(yīng)當(dāng)根據(jù)用戶當(dāng)前的行為，調(diào)整用戶興趣的權(quán)值。反饋的方法有兩種：顯式反饋和隱式反饋。顯示反饋需要用戶對(duì)信息進(jìn)行評(píng)價(jià)，進(jìn)而達(dá)到學(xué)習(xí)的目的。但是這種做法的效率不高。隱式反饋不要求用戶對(duì)反饋的信息做任何評(píng)價(jià)，而是由系統(tǒng)自動(dòng)完成。像點(diǎn)擊鼠標(biāo)之類(lèi)的簡(jiǎn)單動(dòng)作不能有效的揭示用戶的興趣[3]；而像用戶閱讀頁(yè)面時(shí)間、用戶查詢、標(biāo)記書(shū)簽這類(lèi)動(dòng)作能夠有效的揭示用戶的興趣[4]。

Rocchio等在Smart系統(tǒng)中提出了幾種相關(guān)的反饋方法[5]，將特征項(xiàng)重新加權(quán)和查詢相結(jié)合，并基于VSM模型（Vector Space Model）[6]定義了查詢修改方法：

zh01.tif （1）

其中Q為原始查詢的特征向量，Ri為相關(guān)文獻(xiàn)的特征向量，Si為不相關(guān)文獻(xiàn)i的特征向量，n1為相關(guān)文獻(xiàn)數(shù)，n2為不相關(guān)文獻(xiàn)數(shù)，?、β為相關(guān)文獻(xiàn)和不相關(guān)文獻(xiàn)對(duì)查詢向量的貢獻(xiàn)因子。因此，Q’是原始查詢、相關(guān)文獻(xiàn)和不相關(guān)文獻(xiàn)的特征向量的向量和。

3.3 索引項(xiàng)的加權(quán)方法

通常使用局部加權(quán)策略和全局加權(quán)策略分別評(píng)價(jià)某一文檔中的和整個(gè)文檔集中索引項(xiàng)的相對(duì)重要性。將詞加權(quán)策略應(yīng)用到矩陣A中，其元素aij的值將由索引項(xiàng)i在文檔j中出現(xiàn)的次數(shù)變?yōu)閍ij=L(I，j)*G(i)，其中L(i，j)表示索引項(xiàng)i在文檔中j中的局部加權(quán)函數(shù)，G(i)表示索引項(xiàng)i在文檔集中的全局加權(quán)函數(shù)，在諸多加權(quán)方案中選取一個(gè)一個(gè)比較實(shí)用的索引項(xiàng)重評(píng)價(jià)函數(shù)：zh02.tif（2）

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

其中tfik是文檔i中術(shù)語(yǔ)Tk出現(xiàn)的頻率，nk為術(shù)語(yǔ)Tk在文檔集中出現(xiàn)的頻數(shù)，nk、N是在用戶使用中由動(dòng)態(tài)統(tǒng)計(jì)得出。

3.4 隱式反饋的LSI個(gè)性化信息過(guò)濾

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

Wq=(wq1，wq2，…， wqk，…，wqk)，其中wqk為第k個(gè)術(shù)語(yǔ)Tk的權(quán)值，n為用戶profile中術(shù)語(yǔ)的個(gè)數(shù)[7]。文檔i與用戶profile的興趣q的相關(guān)度計(jì)算公式如下：

zh03.tif（3），

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

再次，用文檔的的反饋信息來(lái)更新用戶profile， 學(xué)習(xí)規(guī)則如下：wqk=wqk+?Si.wik（5），?為學(xué)習(xí)因子。修改原則為：如果文檔中的的某個(gè)術(shù)語(yǔ)的權(quán)重很高，超過(guò)給定的最高闕值，那么相應(yīng)的這個(gè)術(shù)語(yǔ)的權(quán)重會(huì)增加；如果文檔中的的某個(gè)術(shù)語(yǔ)的權(quán)重在給定的闕值之間，那么就不修改這個(gè)術(shù)語(yǔ)的權(quán)重；如果文檔中的的某個(gè)術(shù)語(yǔ)的權(quán)重低于給定的最低闕值，那么就將這個(gè)術(shù)語(yǔ)的權(quán)重降低。

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

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

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

LSI中的關(guān)鍵創(chuàng)新在于只保留 S0中的 k個(gè)最大的奇異值，而將其他的值置為 0 。k的值是設(shè)計(jì)時(shí)的一個(gè)參數(shù)，取值通常在 100至200之間。原來(lái)的A矩陣可以用A’來(lái)近似，A’=TSDT， T是一個(gè)含有標(biāo)準(zhǔn)正交列的 m×k矩陣，S是一個(gè)正定的k×k對(duì)角矩陣，D是一個(gè)含有標(biāo)準(zhǔn)正交列的n×k矩陣。

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

潛在語(yǔ)義索引方法通過(guò)對(duì)大規(guī)模文檔集中索引項(xiàng)同現(xiàn)存信息的統(tǒng)計(jì)分析，利用索引項(xiàng)矩陣創(chuàng)建一個(gè)信息的多維語(yǔ)義空間，從而揭示出文檔索引項(xiàng)與索引項(xiàng)之間、索引項(xiàng)與文檔之間存在的潛在語(yǔ)義關(guān)系。通過(guò)對(duì)索引項(xiàng)文檔矩陣進(jìn)行奇異值分解，生成若干個(gè)正交因子的降秩空間，該控件與原始的索引項(xiàng)文檔矩陣所體現(xiàn)的特征信息保持一致，它同時(shí)還可以體現(xiàn)出整個(gè)文檔的語(yǔ)義結(jié)構(gòu)，反映文檔集中詞匯信息的主要相關(guān)模式，從而剔除了其中因具體詞匯變化不定而帶來(lái)的詞匯噪聲信息。

4 隱式反饋的LSI個(gè)性化信息過(guò)濾具體算法：

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

(1)創(chuàng)建用戶profile模型庫(kù)，建立基本的用戶profile。

(2)利用分詞技術(shù)提取術(shù)語(yǔ)，構(gòu)造術(shù)語(yǔ)庫(kù)。

(3)對(duì)不同的屬性空間對(duì)文檔進(jìn)行分類(lèi)。

(4)計(jì)算術(shù)語(yǔ)在用戶文檔中出現(xiàn)的頻率，構(gòu)建術(shù)語(yǔ)-文檔矩陣。

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

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

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

(8)計(jì)算用戶profile模型與當(dāng)前文檔的相關(guān)度。

(9)計(jì)算出的相關(guān)度如果大于所規(guī)定的最小相關(guān)度，就以當(dāng)前的URL為起點(diǎn)，對(duì)每個(gè)文檔進(jìn)行搜索。

(10)對(duì)術(shù)語(yǔ)-文檔矩陣進(jìn)行奇異值分解，剔除小奇異值。

(11)對(duì)于每個(gè)文檔d，用排出了SVD的術(shù)語(yǔ)的新的向量替換原有的向量。

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

(13)排序輸出過(guò)濾后的結(jié)果。

(14)根據(jù)用戶行為調(diào)整用戶profile模型庫(kù)。

5 結(jié)束語(yǔ)

本文對(duì)隱式反饋技術(shù)在信息過(guò)濾方面進(jìn)行了闡述，并提出了具體算法，說(shuō)明了隱式反饋的LSI個(gè)性化信息過(guò)濾的優(yōu)勢(shì)及其涉及到的關(guān)鍵技術(shù)，為實(shí)現(xiàn)該方法提供了基礎(chǔ)。本文的創(chuàng)新點(diǎn)在于隱式反饋的LSI個(gè)性化信息過(guò)濾方法能夠克服傳統(tǒng)的LSI在提供個(gè)性化服務(wù)時(shí)的不足，并且提高過(guò)濾精度。文章的由于用戶行為和興趣的不確定性、用戶profile完備性、中文分詞技術(shù)不成熟是該方法的基本的問(wèn)題，因而也是進(jìn)一步研究的主要方向。

參考文獻(xiàn)：

[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].微計(jì)算機(jī)信息，2006，3-3:131-133.

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

收稿日期：2008-01-29

作者簡(jiǎn)介：徐群益（1982-），男，江蘇南通人，中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)學(xué)院的碩士研究生，主要研究方向：計(jì)算機(jī)網(wǎng)絡(luò)。

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