基于矩陣填充的SVD協(xié)同過(guò)濾算法研究*

王祥德，雷玉霞，閆昱姝

(曲阜師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 日照 276800)

基于矩陣填充的SVD協(xié)同過(guò)濾算法研究*

王祥德，雷玉霞，閆昱姝

(曲阜師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 日照 276800)

對(duì)協(xié)同過(guò)濾推薦算法中數(shù)據(jù)稀疏問(wèn)題，提出矩陣填充策略，分析矩陣填充技術(shù)的優(yōu)劣，選擇非精確拉格朗日乘子法對(duì)稀疏矩陣填充，對(duì)填充的矩陣使用SVD協(xié)同過(guò)濾算法進(jìn)行推薦，對(duì)推薦結(jié)果分別用平均絕對(duì)誤差、均方根誤差和標(biāo)準(zhǔn)平均絕對(duì)誤差方法進(jìn)行評(píng)估。實(shí)驗(yàn)結(jié)果表明，運(yùn)用矩陣填充的推薦算法提高了推薦的質(zhì)量。

協(xié)同過(guò)濾；SVD協(xié)同過(guò)濾；矩陣填充

0 引言

隨著互聯(lián)網(wǎng)規(guī)模的擴(kuò)大，數(shù)據(jù)呈現(xiàn)爆炸式增長(zhǎng)，傳統(tǒng)的信息搜索方法搜索到的符合要求的結(jié)果變得越來(lái)越多，這就增加了用戶獲取有價(jià)值信息的難度。彌補(bǔ)信息檢索存在的這些缺陷，個(gè)性化推薦系統(tǒng)應(yīng)運(yùn)而生。

個(gè)性化推薦系統(tǒng)從2000年開始得到廣泛應(yīng)用，明尼蘇達(dá)大學(xué)的Sarwar教授的文章[1]詳細(xì)地介紹了基于項(xiàng)目的協(xié)同過(guò)濾算法，是學(xué)者們研究協(xié)同過(guò)濾推薦算法常引用的文章。2004年以后，推薦算法開始融合基于內(nèi)容和基于模型的推薦，之后Sarwar等人[2]將SVD引入到協(xié)同過(guò)濾推薦算法中。在推薦數(shù)據(jù)中，有些信息是涉及用戶隱私的數(shù)據(jù)，這一部分?jǐn)?shù)據(jù)有可能影響推薦的準(zhǔn)確性。Polat等人[3]給出了帶有隱私的SVD協(xié)同過(guò)濾算法，優(yōu)化了這一問(wèn)題。針對(duì)現(xiàn)有協(xié)同過(guò)濾算法具有的可擴(kuò)展性較低、數(shù)據(jù)稀疏和計(jì)算量較大的缺點(diǎn)，劉洋等人[4]提出一種基于SVD矩陣分解技術(shù)和RkNN算法的協(xié)同過(guò)濾推薦算法。陳清浩等人[5]提出了梯度下降法改進(jìn)的SVD協(xié)同過(guò)濾算法。本文在SVD協(xié)同過(guò)濾算法的基礎(chǔ)上，將矩陣填充技術(shù)引入其算法中。

1 相關(guān)定義及推薦算法

1.1協(xié)同過(guò)濾算法

協(xié)同過(guò)濾推薦算法[6-8]包括基于內(nèi)存的協(xié)同過(guò)濾算法和基于模型的協(xié)同過(guò)濾算法，常用的推薦算法有基于用戶的協(xié)同過(guò)濾算法(UBCF)、基于項(xiàng)目的協(xié)同過(guò)濾算法(IBCF)[9]、基于SVD的協(xié)同過(guò)濾算法。協(xié)同過(guò)濾推薦算法的基本原理是通過(guò)“用戶-項(xiàng)目”評(píng)分矩陣計(jì)算相似度，用計(jì)算出來(lái)的相似度對(duì)目標(biāo)用戶做推薦。用戶對(duì)項(xiàng)目的評(píng)分矩陣可以表示成m×n維的矩陣，其中，m和n分別是推薦系統(tǒng)中用戶和項(xiàng)目的數(shù)目，每一個(gè)元素ru,i表示用戶u對(duì)項(xiàng)目i的評(píng)分。

1.2相似度及預(yù)測(cè)評(píng)分

相似度是指兩個(gè)用戶對(duì)同一個(gè)項(xiàng)目的喜好程度或者兩個(gè)項(xiàng)目被同一個(gè)用戶喜好的相似程度。常用的相似度模型有余弦相似性、修正的余弦相似性、Pearson相關(guān)相似性和受約束的Pearson相關(guān)相似性[10]等。Pearson相關(guān)相似性在同等情況下具有更加有效的性能，計(jì)算用戶相似度的Pearson相關(guān)相似性表達(dá)式為：

(1)

其中Iuv表示用戶u、v共同評(píng)分的項(xiàng)目集合。計(jì)算項(xiàng)目的相似度的Pearson相關(guān)相似性表達(dá)式為:

(2)

其中Uij表示對(duì)項(xiàng)目i、j共同評(píng)分的用戶集合。

預(yù)測(cè)函數(shù)有均值函數(shù)、權(quán)重函數(shù)和改進(jìn)型權(quán)重函數(shù)。最常用的改進(jìn)型權(quán)重函數(shù)表達(dá)式如下：

(3)

1.3SVD協(xié)同過(guò)濾算法

奇異值分解(Singular Value Decomposition，SVD)[11]是線性代數(shù)中的矩陣分解方法，可以將高維矩陣降維成低維矩陣。Sarwar等人將SVD引入到協(xié)同過(guò)濾推薦算法中，用SVD方法對(duì)評(píng)分矩陣進(jìn)行分解，并用評(píng)分矩陣的奇異值提取特征，用這些特征進(jìn)行推薦。

SVD算法原理:

(4)

它表示前k個(gè)奇異值的平方和與所有奇異值平方和的比值，一般地，前1%左右的奇異值就能表示99%原矩陣的信息，所以在此取α值為99%，以此求得k的值。從Σ中取得前k大的奇異值組成新的對(duì)角陣Σk，從U、V中選取前k個(gè)左右奇異向量，組成新的Uk和Vk，降維后的評(píng)分矩陣為：

其中k遠(yuǎn)小于m,n。

1.4現(xiàn)有算法的不足

數(shù)據(jù)稀疏是當(dāng)前推薦系統(tǒng)面臨的最主要的問(wèn)題，數(shù)據(jù)稀疏也導(dǎo)致了推薦精確度的降低。目前網(wǎng)絡(luò)系統(tǒng)中各種數(shù)據(jù)激增，然而用戶對(duì)這些項(xiàng)目的評(píng)分卻不足，這使得評(píng)分矩陣缺失嚴(yán)重，用戶項(xiàng)目之間的相似度計(jì)算愈加困難，以Netflix Prize 為例，其數(shù)據(jù)缺失達(dá)98%以上。因此，本文提出了一種解決數(shù)據(jù)稀疏問(wèn)題的算法。

2 矩陣填充算法

矩陣填充(Matrix Completion,MC)可以看作特殊的矩陣恢復(fù)問(wèn)題，是Candes等人[13]在2009年提出的方法，主要研究數(shù)據(jù)不完整情況下缺失數(shù)據(jù)的填充問(wèn)題。矩陣填充的前提是矩陣的低秩性，推薦系統(tǒng)中，用戶的評(píng)分矩陣是低秩的，可以用矩陣填充的辦法解決數(shù)據(jù)稀疏問(wèn)題。

在比較矩陣填充技術(shù)的優(yōu)勢(shì)上，選擇Lin等人[14]提出的非精確拉格朗日乘子法進(jìn)行填充，矩陣填充可描述為以下優(yōu)化問(wèn)題：

s.tA+E=D

πΩ(E)=0

(5)

在πΩ(E)=0的約束下，更新E取得優(yōu)化算式L的最小值。

填充完成后，用戶對(duì)項(xiàng)目的評(píng)分為：

3 基于矩陣填充的SVD協(xié)同過(guò)濾算法(MCSVD)

3.1算法的實(shí)現(xiàn)

輸入：評(píng)分?jǐn)?shù)據(jù)集

輸出：目標(biāo)用戶u對(duì)未評(píng)分項(xiàng)目i的評(píng)分預(yù)測(cè)

矩陣填充的SVD協(xié)同過(guò)濾算法

1. 由矩陣填充算法將矩陣R填充為R1

2.U,Σ,V=linalg.svd(R1)

3. 由式(4)≥99%計(jì)算k的值

4.Σk=diag(Σ)[:k,:k]

5.Uk=U[:,:k],Vk=V[:,:k]

6.Ur=Uk*sqrt(Σk),Vr=sqrt(Σk)Vk.T

7.Rui=Ur(u)*Vr(i)

3.2預(yù)測(cè)準(zhǔn)確度

使用預(yù)測(cè)準(zhǔn)確度評(píng)估算法的優(yōu)越性，預(yù)測(cè)準(zhǔn)確度是指推薦算法的預(yù)測(cè)評(píng)分與用戶的實(shí)際評(píng)分是否接近，在推薦系統(tǒng)中，預(yù)測(cè)準(zhǔn)確度是很重要的參數(shù)，例如，推薦系統(tǒng)給用戶的預(yù)測(cè)評(píng)分?jǐn)?shù)和用戶實(shí)際的評(píng)分?jǐn)?shù)非常接近，可以說(shuō)系統(tǒng)成功地完成了預(yù)測(cè)用戶的興趣。

常用的預(yù)測(cè)評(píng)分準(zhǔn)確度標(biāo)準(zhǔn)有：平均絕對(duì)誤差(Mean Absolute Error, MAE)、均方根誤差(Root Mean Squared Error, RMSE)。

平均絕對(duì)誤差。MAE衡量的是所有用戶準(zhǔn)確度的平均，在推薦系統(tǒng)評(píng)估度量中廣泛應(yīng)用，定義如下：

(6)

均方根誤差。RMSE在求和之前先讓預(yù)測(cè)評(píng)分與實(shí)際評(píng)分的誤差進(jìn)行評(píng)分，該標(biāo)準(zhǔn)加大了對(duì)不準(zhǔn)確評(píng)分預(yù)測(cè)的懲罰力度，對(duì)系統(tǒng)評(píng)分更加苛刻，因此評(píng)分誤差越大，對(duì)RMSE值影響越大，定義如下：

(7)

4 實(shí)驗(yàn)分析

4.1實(shí)驗(yàn)數(shù)據(jù)集

在個(gè)性化推薦算法研究領(lǐng)域，最常用的數(shù)據(jù)集有Movielens電影評(píng)分?jǐn)?shù)據(jù)集、Libimseti網(wǎng)上約會(huì)評(píng)分?jǐn)?shù)據(jù)集、Book-Crossing書籍評(píng)分?jǐn)?shù)據(jù)集和Jester笑話評(píng)分?jǐn)?shù)據(jù)集。這里使用Movielens數(shù)據(jù)集，此數(shù)據(jù)集是由美國(guó)明尼蘇達(dá)大學(xué)Grouplens項(xiàng)目從Movielens站點(diǎn)整理而來(lái)，并廣泛應(yīng)用于個(gè)性化推薦算法研究中，數(shù)據(jù)集中每個(gè)用戶至少對(duì)20部電影進(jìn)行評(píng)分，評(píng)分的范圍從1～5， 評(píng)分值越高表示越滿意。

4.2實(shí)驗(yàn)設(shè)計(jì)和結(jié)果分析

試驗(yàn)中，將數(shù)據(jù)分為訓(xùn)練集和測(cè)試集，在第一個(gè)試驗(yàn)中，選取80%的數(shù)據(jù)作為訓(xùn)練集，分別對(duì)原始評(píng)分矩陣和填充的矩陣在訓(xùn)練集上使用SVD協(xié)同過(guò)濾算法進(jìn)行訓(xùn)練，將訓(xùn)練結(jié)果在測(cè)試集上進(jìn)行測(cè)試，對(duì)得出的結(jié)果使用不同的準(zhǔn)確度評(píng)估方法進(jìn)行評(píng)估，實(shí)驗(yàn)結(jié)果如下表1所示。數(shù)據(jù)顯示，矩陣填充之后精確度提高。

表1 實(shí)驗(yàn)結(jié)果

第二個(gè)實(shí)驗(yàn)中,對(duì)給出的given(預(yù)測(cè)項(xiàng)目數(shù))值，進(jìn)行不同方法的多組比較，實(shí)驗(yàn)結(jié)果如圖1所示。實(shí)驗(yàn)數(shù)據(jù)表明，在不同方法中，基于矩陣填充的奇異值分解方法具有較好的推薦效果，同時(shí)given值對(duì)推薦系統(tǒng)影響很大(取值范圍為0～20)，given值越大，推薦準(zhǔn)確度越高。

圖1 不同預(yù)測(cè)項(xiàng)目數(shù)下精確度曲線

第三個(gè)實(shí)驗(yàn)中，將數(shù)據(jù)集中不同的用戶數(shù)作為訓(xùn)練集，分別在不同的推薦方法中訓(xùn)練預(yù)測(cè)，得到的實(shí)驗(yàn)結(jié)果如圖2所示。實(shí)驗(yàn)結(jié)果表明，基于矩陣填充的奇異值分解方法精確度曲線優(yōu)于其他結(jié)果，同時(shí)，在訓(xùn)練用戶大于等于400時(shí)，曲線趨于平穩(wěn)，這也說(shuō)明在一定的訓(xùn)練/測(cè)試比下，訓(xùn)練/測(cè)試比對(duì)評(píng)分準(zhǔn)確度影響不大，并不是訓(xùn)練集比重越大評(píng)分準(zhǔn)確度越大，因此在實(shí)際過(guò)程中可適當(dāng)降低訓(xùn)練集的比例，減少建立模型所需時(shí)間。

圖2 不同用戶數(shù)下精確度曲線

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

本文分析了協(xié)同過(guò)濾算法及其存在的一些問(wèn)題，并提出了基于矩陣填充的SVD協(xié)同過(guò)濾算法，首先采用矩陣填充技術(shù)對(duì)評(píng)分稀疏矩陣進(jìn)行填充，解決了數(shù)據(jù)稀疏問(wèn)題，然后將填充的評(píng)分矩陣應(yīng)用到SVD協(xié)同過(guò)濾算法中，計(jì)算預(yù)測(cè)結(jié)果的評(píng)分準(zhǔn)確度。實(shí)驗(yàn)結(jié)果表明，基于矩陣填充的SVD協(xié)同過(guò)濾算法在評(píng)分準(zhǔn)確度上有所提高，但是填充的矩陣由于數(shù)據(jù)量過(guò)大，給內(nèi)存和計(jì)算都帶來(lái)挑戰(zhàn)，這是下一步將要解決的問(wèn)題。

[1] SARWAR B, KARYPIS G J. Item-based collaborative filtering recommendation algorithms[C]. Proceedings of the 10th International Conference on World Wide Web, ACM, 2001: 285-295.

[2] SARWAR B, KARYPIS G, KONSTAN J, et al. Application of dimensionality reduction in recommender system-a case study[R]. Minnesota Univ Minneapolis Dept of Computer Science, 2000.

[3] POLAT H, DU W. SVD-based collaborative filtering with privacy[C]. Proceedings of the 2005 ACM symposium on Applied computing. ACM, 2005: 791-795.

[4] 劉洋. 基于 SVD 矩陣分解技術(shù)和 RkNN 算法的協(xié)同過(guò)濾推薦算法[J]. 湖南工程學(xué)院學(xué)報(bào) (自然科學(xué)版), 2015,25(1): 44-47.

[5] 陳清浩. 基于SVD的協(xié)同過(guò)濾推薦算法研究[D]. 成都：西南交通大學(xué), 2015.

[6] BREESE J S, HECKERMAN D, KADIE C. Empirical analysis of predictive algorithms for collaborative filtering[C]. Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, 1998: 43-52.

[7] LIU Q, CHEN T, CAI J, et al. Enlister: baidu’s recommender systems for the biggest Chinese Q&A website[C]. Proceedings of the ACM Conference on Recommender Systems, 2012: 285-288.

[8] Zheng Nan, Li Qiudan, Liao Shengcai, et al. Which photo groups should I choose? a comparative study of recommendation algorithms in flickr[J]. Joumal of Information Science, 2010, 36(6): 732-750.

[9] 鄧愛林, 朱揚(yáng)勇, 施伯樂(lè). 基于項(xiàng)目評(píng)分預(yù)測(cè)的協(xié)同過(guò)濾推薦算法[J]. 軟件學(xué)報(bào), 2003, 14(9): 1621-1628.

[10] 徐翔, 王煦法. 協(xié)同過(guò)濾算法中的相似度優(yōu)化方法[J]. 計(jì)算機(jī)工程, 2010, 36(6): 52-54.

[11] WALL M E, RECHTSTEINER A, ROCHA L M. Singular value decomposition and principal component analysis[M]. A Practical Approach to Microarray Data Analysis. Springer US, 2003: 91-109.

[12] 陳峰峰. 奇異值閾值算法在Netflix問(wèn)題中的應(yīng)用研究[D]. 北京: 清華大學(xué), 2011.

[14] CHEN M, LIN Z, MA Y, et al. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices[J]. Eprint Arxiv, 2010.

Research on singular value decomposition collaborative filtering algorithm based on matrix completion

Wang Xiangde, Lei Yuxia, Yan Yushu

(College of Information Science and Engineering, Qufu Normal University, Rizhao 276800, China)

A matrix completion scenario was proposed to solve the problem of matrix sparsity in collaborative filtering recommendation. After analyzing various technologies of matrix completion, the inexact augmented Lagrange multiplier was selected to recover the matrix. Using singular value decomposition collaborative filtering algorithm on the recovered matrix. Evaluating recommended data utility the measure of Mean Absolute Error, Root Mean Squared Error. The experimental results show that the accuracy is higher when using the recovered matrix.

filtering recommendation; SVD filtering recommendation; matrix completion

TP301.6

A

10.19358/j.issn.1674- 7720.2017.19.016

王祥德，雷玉霞，閆昱姝.基于矩陣填充的SVD協(xié)同過(guò)濾算法研究[J].微型機(jī)與應(yīng)用，2017,36(19)：55-57,61.

國(guó)家自然科學(xué)基金項(xiàng)目(61572284,61502272)；山東省中青年優(yōu)秀科學(xué)家基金項(xiàng)目(BS2014DX004)

2017-03-14)

王祥德(1989-)，通信作者，男，碩士研究生，主要研究方向：數(shù)據(jù)挖掘，大數(shù)據(jù)分析和分布式計(jì)算。E-mail:386345486@qq.com。雷玉霞(1976-)，男，博士，副教授，主要研究方向：知識(shí)表示與獲取，知識(shí)本體。閆昱姝(1991-)，女，碩士研究生，主要研究方向：數(shù)據(jù)挖掘。