在協(xié)同過(guò)濾中結(jié)合奇異值分解與最近鄰方法

摘要：協(xié)同過(guò)濾是一種減小信息過(guò)載的常用方法，但是它有三方面的限制，即準(zhǔn)確性、數(shù)據(jù)稀疏性和可擴(kuò)展性。提出一種新的協(xié)同過(guò)濾算法來(lái)解決數(shù)據(jù)稀疏性的問(wèn)題，利用奇異值分解法的結(jié)果來(lái)進(jìn)行鄰居選擇，然后采用最近鄰方法來(lái)得到未打分項(xiàng)目的預(yù)測(cè)值。在EachMovie 數(shù)據(jù)庫(kù)集上的試驗(yàn)結(jié)果表明該算法在數(shù)據(jù)稀疏時(shí)算法的準(zhǔn)確性超過(guò)普通的Pearson算法和奇異值分解算法。

關(guān)鍵詞：奇異值分解；協(xié)同過(guò)濾；推薦系統(tǒng)

中圖法分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1001－3695(2006)09－0206－03

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，網(wǎng)上已出現(xiàn)信息過(guò)載問(wèn)題。協(xié)同過(guò)濾技術(shù)是減小信息過(guò)載的一種常用方法，它根據(jù)一個(gè)用戶對(duì)其他項(xiàng)目的評(píng)分以及整個(gè)用戶群過(guò)去的評(píng)分記錄來(lái)預(yù)測(cè)該用戶對(duì)未評(píng)分項(xiàng)目的評(píng)分［6］。

協(xié)同過(guò)濾中使用得最廣泛的算法是最近鄰方法［6］。最近鄰方法根據(jù)用戶評(píng)分的相似性來(lái)得到活動(dòng)用戶的若干最近鄰居，然后用最近鄰居對(duì)項(xiàng)目評(píng)分的加權(quán)值來(lái)預(yù)測(cè)活動(dòng)用戶對(duì)項(xiàng)目的評(píng)分。其他算法包括Bayesian網(wǎng)絡(luò)、降維方法、歸納規(guī)則學(xué)習(xí)法、最近鄰與加權(quán)多數(shù)投票方法的結(jié)合、基于主分量分析的聚類方法和潛在分類模型方法等［11，13］。

最近鄰方法有三個(gè)方面的限制，即準(zhǔn)確性、數(shù)據(jù)稀疏性和可擴(kuò)展性［11］。因?yàn)樽罱彿椒ㄐ枰蟛煌脩糁g的相似程度，如果兩個(gè)用戶之間沒(méi)有都打過(guò)分的項(xiàng)目，則他們之間的相似系數(shù)無(wú)法求取，這就產(chǎn)生了稀疏性，從而影響系統(tǒng)的準(zhǔn)確性。由于一個(gè)典型的基于Web的推薦系統(tǒng)可能有數(shù)百甚至數(shù)千萬(wàn)用戶和項(xiàng)目，現(xiàn)有的算法不可避免地存在可擴(kuò)展性問(wèn)題。

1相關(guān)問(wèn)題和工作

1．1推薦系統(tǒng)描述

協(xié)同過(guò)濾就是根據(jù)一個(gè)用戶對(duì)其他項(xiàng)目的評(píng)分以及整個(gè)用戶群過(guò)去的評(píng)分記錄來(lái)預(yù)測(cè)該用戶對(duì)某一未評(píng)分項(xiàng)目的評(píng)分。假設(shè)某一個(gè)推薦系統(tǒng)有m個(gè)用戶和n個(gè)項(xiàng)目，則這個(gè)系統(tǒng)可以表示為一個(gè)m×n矩陣。我們定義用戶i對(duì)項(xiàng)目j的評(píng)分為Ri，j。協(xié)同過(guò)濾問(wèn)題可以看成是預(yù)測(cè)用戶—項(xiàng)目評(píng)分矩陣中缺失值的問(wèn)題［6］。如果推薦系統(tǒng)正在預(yù)測(cè)某一用戶對(duì)某一項(xiàng)目的評(píng)分，則我們稱該用戶為活動(dòng)用戶。

1．2奇異值分解

奇異值分解（SingularValueDecomposition，SVD）是一種矩陣分解技術(shù)，它深刻揭露了矩陣的內(nèi)部結(jié)構(gòu)［4，5］，奇異值分解在圖像壓縮、最小二乘法等方面有著廣泛的應(yīng)用［3］。它可將一個(gè)m×n(假設(shè)m≥n)的矩陣R分解為三個(gè)矩陣U，S，V［1］：

R=U×S×VT

其中U是一個(gè)m×m的正交矩陣(UUT=I)，V是一個(gè)n×n的正交矩陣(VVT=I)，S是一個(gè)m×n矩陣，其非對(duì)角線上的元素全為0，而對(duì)角線上的元素滿足

σ1≥σ2≥…≥σn≥0

所有的σn大于0并按照從大到小順序排列，稱為奇異值(SingularValue)，奇異值可以表示一個(gè)給定矩陣與比其秩低的矩陣的接近程度［5］。

2Pear_After_SVD算法

在最近鄰方法中，根據(jù)與活動(dòng)用戶的相似程度，一個(gè)用戶子集被選擇出來(lái)作為該活動(dòng)用戶的最近鄰，然后這些最近鄰對(duì)項(xiàng)目的評(píng)分被加權(quán)來(lái)作為該活動(dòng)用戶對(duì)此項(xiàng)目評(píng)分的預(yù)測(cè)值。GroupLens［10］首先使用了最近鄰方法來(lái)進(jìn)行協(xié)同過(guò)濾，該系統(tǒng)為Usenet用戶提供對(duì)新聞的個(gè)性化推薦。最初的GroupLens系統(tǒng)使用Pearson系數(shù)來(lái)定義用戶之間的相似性，然后利用所有的相關(guān)用戶的評(píng)分值以及這些用戶所對(duì)應(yīng)的權(quán)值來(lái)計(jì)算最終的預(yù)測(cè)值。

在Pearson算法中，活動(dòng)用戶對(duì)項(xiàng)目j的評(píng)分的預(yù)測(cè)值Pa，j是其他用戶對(duì)該項(xiàng)目評(píng)分的加權(quán)和［2］:

Pa，j=Ra+κnu=1wa，u(Ru，j-Ru)(1)

wa，u=mi=1(Ra，i-Ra)(Ru，i-Ru)mi=1(Ra，i-Ra)2mi=1(Ru，i-Ru)2(2)

其中，κ是一個(gè)使權(quán)值的絕對(duì)值之和為1的規(guī)范化因子，Ra，i表示活動(dòng)用戶對(duì)項(xiàng)目i的評(píng)分，Ra是活動(dòng)用戶在所有他已打分項(xiàng)目上的評(píng)分的平均值，wa，u表示當(dāng)前用戶與鄰居u之間的Pearson系數(shù)，m是重合的評(píng)分?jǐn)?shù)目，n指最近鄰居的個(gè)數(shù)。

根據(jù)文獻(xiàn)［9，11］，活動(dòng)用戶在項(xiàng)目i上的預(yù)測(cè)得分為

Pa，i=Ra+Uk×Sk′(a)×SkV′k(i)(3)

其中，Ra是活動(dòng)用戶在所有他已打分項(xiàng)目上的評(píng)分的平均值，U，S，V為評(píng)分矩陣R經(jīng)過(guò)SVD分解后得到的三個(gè)矩陣。Uk，Sk和Vk分別為對(duì)U，S，V進(jìn)行約減后的矩陣，k為SVD分解后保留的維數(shù)。

Sarwar等人的試驗(yàn)結(jié)果表明奇異值分解方法應(yīng)用于協(xié)同過(guò)濾時(shí)對(duì)于稀疏的評(píng)分矩陣效果比較好。最近鄰方法需要求不同用戶之間的相似程度，如果兩個(gè)用戶之間沒(méi)有都打過(guò)分的項(xiàng)目，則他們之間的相似系數(shù)無(wú)法求取。所以我們綜合這兩種方法的優(yōu)點(diǎn)，首先采用SVD方法來(lái)預(yù)測(cè)未打分項(xiàng)的預(yù)測(cè)值，得到一個(gè)無(wú)缺失值的評(píng)分矩陣；然后用這個(gè)無(wú)缺失值的評(píng)分矩陣來(lái)計(jì)算用戶之間的Pearson系數(shù)，采用最近鄰方法來(lái)求取實(shí)際未評(píng)分項(xiàng)目的預(yù)測(cè)值。算法如下：

(1)利用式（3）得到各個(gè)活動(dòng)用戶在每個(gè)項(xiàng)目i上的預(yù)測(cè)得分。

(2)由式（2）求出活動(dòng)用戶與其他用戶之間的相似系數(shù)。

(3)將其他用戶與活動(dòng)用戶之間的相似系數(shù)從大到小排序，選擇相似系數(shù)最大的n個(gè)用戶作為最近鄰居。

(4)根據(jù)式（1）求出活動(dòng)用戶對(duì)項(xiàng)目j的評(píng)分的預(yù)測(cè)值Pa，j。

為方便起見(jiàn)，以下稱我們的算法為Pear_After_SVD算法。Pear_After_SVD算法利用用戶與項(xiàng)目之間的潛在關(guān)系克服了稀疏性問(wèn)題，同時(shí)保留了最近鄰方法的優(yōu)點(diǎn)。

3試驗(yàn)

3．1數(shù)據(jù)集

為了評(píng)估提出的算法的效果，我們使用EachMovie［8］數(shù)據(jù)庫(kù)。EachMovie是一個(gè)公開(kāi)的電影評(píng)分?jǐn)?shù)據(jù)庫(kù)，約有72916個(gè)用戶為1628部不同的電影提供了總共2811983個(gè)評(píng)分。用戶評(píng)分值在0和1之間，分為六個(gè)等級(jí)，0表示最不喜歡。為了使結(jié)果便于理解，我們將評(píng)分值轉(zhuǎn)換為整數(shù)值0~5。預(yù)測(cè)的任務(wù)就是為以前從未觀看過(guò)的電影提供一個(gè)估計(jì)的評(píng)分值。

為了評(píng)價(jià)不同算法的運(yùn)行結(jié)果，我們從EachMovie數(shù)據(jù)庫(kù)中選擇了一個(gè)子數(shù)據(jù)集，即前1000個(gè)用戶中打分項(xiàng)目數(shù)小于20的用戶，然后將該子數(shù)據(jù)集分為一個(gè)訓(xùn)練集和一個(gè)測(cè)試集，訓(xùn)練集與測(cè)試集中的評(píng)分?jǐn)?shù)目之比約為0.8∶0.2。

3.2評(píng)價(jià)指標(biāo)

對(duì)一種協(xié)同過(guò)濾算法的評(píng)價(jià)往往集中在其準(zhǔn)確性方面，我們考慮兩種評(píng)價(jià)預(yù)測(cè)結(jié)果的指標(biāo)。首先，我們使用一種常用的統(tǒng)計(jì)準(zhǔn)確性指標(biāo)，平均絕對(duì)誤差(MAE)［11］來(lái)評(píng)估我們算法的準(zhǔn)確性，一個(gè)推薦系統(tǒng)的平均絕對(duì)誤差采用下式得

E=1NNi=1｜Pi-Ti｜(4)

其中，N是推薦系統(tǒng)中所有未打分的用戶-項(xiàng)目Entries的數(shù)目；Pi是系統(tǒng)對(duì)用戶-項(xiàng)目Entry的評(píng)分預(yù)測(cè)值；Ti是用戶-項(xiàng)目Entry的評(píng)分的目標(biāo)值。平均絕對(duì)誤差越小，該推薦系統(tǒng)引擎預(yù)測(cè)用戶評(píng)分值越準(zhǔn)確。

然后我們使用受試者操作特性曲線(ROC)［7］來(lái)評(píng)估推薦系統(tǒng)的準(zhǔn)確性。ROC曲線是反映系統(tǒng)敏感性和特異性連續(xù)變化的綜合指標(biāo)。ROC曲線下面的面積是預(yù)測(cè)準(zhǔn)確性的一個(gè)度量。ROC曲線下面的面積越大，該推薦系統(tǒng)越準(zhǔn)確。

3．3結(jié)果與討論

在奇異值分解中，保留的維數(shù)k很重要，如果k太小，則不能得到原始評(píng)分矩陣中的重要結(jié)構(gòu)；如果k太大，則失去了降維的意義，所以我們要先確定保留的維數(shù)k。

圖1顯示奇異值分解方法中不同維數(shù)k下的運(yùn)行結(jié)果，從結(jié)果中我們可以看出，當(dāng)k=4時(shí)，平均絕對(duì)誤差(MAE)最小，而ROC曲線下的面積最大，所以對(duì)于這個(gè)數(shù)據(jù)集，維數(shù)k=4是最佳的。在采用Pear_After_SVD算法的試驗(yàn)中我們選取k=4。

圖2顯示Pearson，SVD以及Pear_After_SVD等三種算法的預(yù)測(cè)結(jié)果。從結(jié)果我們可以看出Pear_After_SVD算法的MAE小于其他兩種算法，而該算法的ROC曲線下的面積大于其他兩種算法，所以Pear_After_SVD的準(zhǔn)確性超過(guò)普通的Pearson算法和SVD算法。從以上結(jié)果也可以看出MAE和ROC均能較好地評(píng)價(jià)推薦系統(tǒng)的準(zhǔn)確性。

4結(jié)論

本文中我們提出一種新的協(xié)同過(guò)濾算法來(lái)解決數(shù)據(jù)稀疏性的問(wèn)題，同時(shí)提高預(yù)測(cè)的準(zhǔn)確性。利用奇異值分解法的結(jié)果來(lái)進(jìn)行鄰居選擇，然后采用Pearson方法來(lái)得到未打分項(xiàng)目的預(yù)測(cè)值。試驗(yàn)結(jié)果表明這種算法在數(shù)據(jù)稀疏時(shí)算法的準(zhǔn)確性超過(guò)普通的Pearson算法和奇異值分解算法。

參考文獻(xiàn)：

［1］Berry M W，et al. Using Linear Algebra for Intelligent Information Retrieval［J］.SIAM Review， 1995，37(4):573595.

［2］Breese J S， Heckerman D， et al.Empirical Analysis of Predictive Algorithms for Collaborative Filtering［C］. Proc. of the 14th Conference on Uncertainty in Artificial Intelligence， 1998.4352.

［3］Dan Kalman. A Singularly Valuable Decomposition: The SVD of a Matrix［J］. The College Mathematics Journal， 1996， 27(1):223.

［4］Deerwester S， Dumais S T， Furnas G W， et al. Indexing by Latent Semantic Analysis［J］. Journal of the American Society for Information Science，1990，41(6):391407.

［5］Golub G H， Van Loan C F. Matrix Computations (3rd edition)［M］. Johns Hopkins University Press， 1996.

［6］Herlocker J L， Konstan J A， Borchers A， et al. An Algorithmic Framework for Performing Collaborative Filtering［C］. Proceedings of ACM SIGIR’99， ACM press， 1999.230237

［7］John A Swets. Measuring the Accuracy of Diagnostic System［J］. Scie￣nce， 1988，240(4857):12851289.

［8］McJones P. EachMovie Collaborative Filtering Data Set［DB/OL］. DEC Systems Research Center， 1997.

［9］Michael H Pryor. The Effects of Singular Value Decomposition on Collaborative Filtering［R］. Technical Report PCSTR98338， Dartmouth College， 1998.

［10］Resnick P， Iacovou N， et al. GroupLens: An Open Architecture for Collaborative Filtering of Netnews［C］. Proceedings of CSCW’94， Chapel Hill， NC， 1994.175186.

［11］Sarwar B M， Karypis G， et al. Application of Dimensionality Reduction in Recommender Systems：A Case Study［C］. ACM WebKDD Web Mining for Ecommerce Workshop， 2000.114121.

［12］鄧愛(ài)林，朱揚(yáng)勇，施伯樂(lè).基于項(xiàng)目評(píng)分預(yù)測(cè)的協(xié)同過(guò)濾推薦算法［J］. 軟件學(xué)報(bào)，2002，13(4):18.

［13］冀俊忠，沙志強(qiáng)，劉椿年.一種基于貝葉斯網(wǎng)客戶購(gòu)物模型的商品推薦方法［J］. 計(jì)算機(jī)應(yīng)用研究，2005，22(4):6571.

作者簡(jiǎn)介：

孫小華(1973)，男，江西婺源人，博士研究生，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘；陳洪(1973)，男，浙江天臺(tái)人，碩士，主要研究方向?yàn)閿?shù)據(jù)挖掘、軟件過(guò)程管理；孔繁勝(1946)，男，上海人，教授，博導(dǎo)，主要研究方向?yàn)閿?shù)據(jù)挖掘、地理信息系統(tǒng)。