一種改進(jìn)的缺失數(shù)據(jù)協(xié)同過濾推薦算法*

周明升，韓冬梅

(1. 上海財(cái)經(jīng)大學(xué) 信息管理與工程學(xué)院，上海 200433；2.上海外高橋保稅區(qū)聯(lián)合發(fā)展有限公司，上海 200131)

?

一種改進(jìn)的缺失數(shù)據(jù)協(xié)同過濾推薦算法*

周明升1,2，韓冬梅1

(1. 上海財(cái)經(jīng)大學(xué) 信息管理與工程學(xué)院，上海 200433；2.上海外高橋保稅區(qū)聯(lián)合發(fā)展有限公司，上海 200131)

協(xié)同過濾推薦算法是推薦系統(tǒng)研究的熱點(diǎn)，近年來，在亞馬遜、淘寶等商業(yè)系統(tǒng)中獲得應(yīng)用。在實(shí)際應(yīng)用過程中，協(xié)同過濾推薦面臨數(shù)據(jù)稀疏和準(zhǔn)確性低的問題。作為推薦基礎(chǔ)的用戶-產(chǎn)品(項(xiàng)目)矩陣通常非常稀疏(存在大量缺失數(shù)據(jù))，從而導(dǎo)致推薦結(jié)果不準(zhǔn)確。文章試圖在缺失數(shù)據(jù)情況下提高協(xié)同過濾推薦的準(zhǔn)確性，聚焦以下兩個(gè)方面：(1)用戶相似度、產(chǎn)品(項(xiàng)目)相似度計(jì)算；(2)缺失數(shù)據(jù)預(yù)測。首先，用增強(qiáng)的皮爾森相關(guān)系數(shù)算法，通過增加參數(shù)，對(duì)相似度進(jìn)行修正，提高用戶、產(chǎn)品(項(xiàng)目)相似度計(jì)算的準(zhǔn)確率。接著，提出一種同時(shí)考慮了用戶和產(chǎn)品(項(xiàng)目)特征的缺失數(shù)據(jù)預(yù)測算法。算法中，對(duì)用戶和產(chǎn)品(項(xiàng)目)分別設(shè)置相似度閾值，只有當(dāng)用戶或產(chǎn)品(項(xiàng)目)相似度達(dá)到閾值時(shí)，才進(jìn)行缺失數(shù)據(jù)預(yù)測。預(yù)測過程中，同時(shí)使用用戶和產(chǎn)品(項(xiàng)目)相似度信息，以提高準(zhǔn)確度。在模型基礎(chǔ)上，用淘寶移動(dòng)客戶端的數(shù)據(jù)集進(jìn)行了驗(yàn)證，實(shí)驗(yàn)結(jié)果表明所提算法比其他推薦算法要優(yōu)異，對(duì)數(shù)據(jù)稀疏性的魯棒性要高。

協(xié)同過濾；推薦系統(tǒng)；缺失數(shù)據(jù)預(yù)測；數(shù)據(jù)稀疏性

引用格式：周明升，韓冬梅. 一種改進(jìn)的缺失數(shù)據(jù)協(xié)同過濾推薦算法[J].微型機(jī)與應(yīng)用，2016,35(17)：17-19.

0　引言

協(xié)同過濾推薦算法(Collaborative Filtering Recommendation Algorithm)，通過收集相似用戶或產(chǎn)品(項(xiàng)目)的評(píng)分信息來預(yù)測用戶興趣，從而進(jìn)行產(chǎn)品(項(xiàng)目)的推薦。對(duì)用戶或產(chǎn)品(項(xiàng)目)的相似性進(jìn)行計(jì)算，通過用戶-產(chǎn)品(項(xiàng)目)矩陣來預(yù)測用戶偏好。根據(jù)角度不同，協(xié)同過濾推薦分為基于用戶的方法和基于產(chǎn)品(項(xiàng)目)的方法。算法中，計(jì)算用戶或產(chǎn)品(項(xiàng)目)之間的相似度是關(guān)鍵步驟，常見的相似度計(jì)算方法有：皮爾森相關(guān)系數(shù)算法(Pearson Correlation Coefficient Algorithm，PCC)[1]和空間向量相似度算法(Vector Space Similarity Algorithm，VSS)[2]。

實(shí)際應(yīng)用中，因?yàn)橛脩?產(chǎn)品(項(xiàng)目)矩陣的稀疏性(存在大量缺失數(shù)據(jù))，造成推薦結(jié)果不準(zhǔn)確，許多研究試圖解決矩陣的數(shù)據(jù)稀疏性問題。Wang Jun等人構(gòu)建了一種概率框架，通過已有數(shù)據(jù)來預(yù)測用戶-產(chǎn)品(項(xiàng)目)矩陣中的值[3]。XUE G R等人提出了一種同時(shí)基于內(nèi)容和建模的協(xié)同過濾框架，通過平滑算法，預(yù)測用戶-產(chǎn)品(項(xiàng)目)矩陣中的缺失數(shù)據(jù)[4]。MA H等人提出綜合考慮用戶信息和產(chǎn)品(項(xiàng)目)信息來預(yù)測缺失數(shù)據(jù)的方法[5]，對(duì)協(xié)同過濾算法進(jìn)行了改進(jìn)。這些方法可以取得比傳統(tǒng)協(xié)同過濾算法更好的結(jié)果，但基于概率或聚類的平滑算法沒有區(qū)分同一組內(nèi)用戶的差別。同時(shí)，預(yù)測用戶-產(chǎn)品(項(xiàng)目)矩陣中的所有缺失數(shù)據(jù)也可能為當(dāng)前用戶的推薦帶來負(fù)面影響。

為解決上述問題，本文采用增強(qiáng)的皮爾森相關(guān)系數(shù)來衡量用戶間與產(chǎn)品(項(xiàng)目)間的相似性(并進(jìn)行修正)，綜合考慮用戶信息和產(chǎn)品(項(xiàng)目)信息，提出一種改進(jìn)的缺失數(shù)據(jù)預(yù)測算法：當(dāng)且僅當(dāng)預(yù)測缺失數(shù)據(jù)會(huì)為當(dāng)前用戶的推薦帶來積極影響時(shí)(相似度達(dá)到閥值)才進(jìn)行缺失數(shù)據(jù)預(yù)測，否則不進(jìn)行預(yù)測。在完成缺失數(shù)據(jù)預(yù)測后，進(jìn)行協(xié)同過濾推薦。實(shí)驗(yàn)顯示，本文所提方法比傳統(tǒng)方法效果要好。

1　相似度計(jì)算及修正

1.1相似度計(jì)算

RESNICK P等人已經(jīng)證明，基于皮爾森相關(guān)系數(shù)(PCC)的協(xié)同過濾，其效果通常比基于空間向量相似度算法(VSS)等方法要好，因?yàn)樗紤]了不同用戶打分標(biāo)準(zhǔn)不同的因素[1]。在基于用戶的協(xié)同過濾算法[6]中，皮爾森相關(guān)系數(shù)(PCC)被用于定義有相同產(chǎn)品(項(xiàng)目)評(píng)分的不同用戶a和u之間的相似度，如下：

Sim(a,u)=

(1)

其中，Sim(a,u)定義了用戶a與用戶u之間的相似度，產(chǎn)品(項(xiàng)目)i是用戶a和用戶u都評(píng)過分的產(chǎn)品(項(xiàng)目)。ra,i是用戶a對(duì)產(chǎn)品(項(xiàng)目)i的評(píng)分，ra是用戶a的平均評(píng)分?；诋a(chǎn)品(項(xiàng)目)的方法[7]可以類似得出(本文不再贅述)。

1.2相似度修正

MCLAUGHLIN M R等人研究發(fā)現(xiàn)，皮爾森相關(guān)系數(shù)(PCC)有時(shí)會(huì)高估用戶之間的相似性，特別是當(dāng)用戶正好對(duì)一些產(chǎn)品(項(xiàng)目)打分相似，而整體相似度不同時(shí)[8]。為解決這一問題，本文引入相關(guān)性權(quán)重指標(biāo)，對(duì)相似度計(jì)算進(jìn)行修正，如下：

(2)

式(2)在一定程度上解決了數(shù)據(jù)稀疏性問題(僅有少量產(chǎn)品(項(xiàng)目)被用戶評(píng)分)，但當(dāng)|Ia∩Iu|遠(yuǎn)比γ大時(shí)，相似度Sim′(a,u)將大于1，為此，筆者進(jìn)行了變換，改進(jìn)如下：

(3)

其中，|Ia∩Iu|是用戶a和用戶u都評(píng)價(jià)過的產(chǎn)品(項(xiàng)目)集個(gè)數(shù)。

2　缺失數(shù)據(jù)預(yù)測

基于用戶的協(xié)同過濾算法通過相似用戶的評(píng)分來預(yù)測缺失數(shù)據(jù)，根據(jù)不同情況，本文的預(yù)測方法如下：

模型1：當(dāng)S(u)≠φ，且S(i)≠φ時(shí)，即用戶相似度和產(chǎn)品(項(xiàng)目)相似度均達(dá)到閾值(分別為η和θ)時(shí)，缺失數(shù)據(jù)預(yù)測為：

(4)

其中λ的取值范圍為[0,1]。

模型2：當(dāng)S(u)=φ，但S(i)≠φ時(shí)，即產(chǎn)品(項(xiàng)目)存在相似產(chǎn)品(項(xiàng)目)，但用戶與其他用戶的相似度小于閾值η時(shí)，缺失數(shù)據(jù)預(yù)測為：

(5)

模型3：當(dāng)S(u)≠φ，但S(i)=φ時(shí)，即用戶存在相似用戶，但產(chǎn)品(項(xiàng)目)與其他產(chǎn)品(項(xiàng)目)的相似度小于閾值θ時(shí)，缺失數(shù)據(jù)預(yù)測為：

(6)

模型4：當(dāng)S(u)=φ，且S(i)=φ時(shí)，即用戶與其他用戶的相似度小于閾值，且產(chǎn)品(項(xiàng)目)與其他產(chǎn)品(項(xiàng)目)之間的相似度小于閾值時(shí)，缺失數(shù)據(jù)預(yù)測為：

P(ru,i)=0

(7)

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

3.1數(shù)據(jù)集

用淘寶移動(dòng)客戶端的數(shù)據(jù)進(jìn)行試驗(yàn)分析，該數(shù)據(jù)集來自阿里巴巴天池大數(shù)據(jù)研究平臺(tái)，為公開數(shù)據(jù)。數(shù)據(jù)集中有超過104萬條記錄，來自723個(gè)用戶對(duì)53 383個(gè)產(chǎn)品(項(xiàng)目)的評(píng)分。用戶-產(chǎn)品(項(xiàng)目)矩陣的稀疏度為：1 048 575/(723×53 383)=2.72%。本文隨機(jī)獲取500個(gè)用戶數(shù)據(jù)，并將其分為兩部分：取300個(gè)作為訓(xùn)練集，剩余的200個(gè)作為測試集(實(shí)際用戶集)。對(duì)不同用戶集，推薦產(chǎn)品(項(xiàng)目)數(shù)分別取10個(gè)、20個(gè)和30個(gè)。

3.2比較方法

用絕對(duì)平均誤差(Mean Absolute Error，MAE)作為衡量指標(biāo)。MAE被定義為：

(8)

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

通過實(shí)驗(yàn)，本文改進(jìn)的缺失數(shù)據(jù)協(xié)同過濾算法(IMDP)與其他推薦算法進(jìn)行比較，包括：基于用戶的皮爾森相關(guān)系數(shù)算法(UPCC)和基于產(chǎn)品(項(xiàng)目)的皮爾森相關(guān)系數(shù)算法(IPCC)、基于平滑和聚類的皮爾森相關(guān)系數(shù)算法(SCBPCC)[4]、相似融合算法(SF)[3]、特征模型算法(AM)[9]。

實(shí)驗(yàn)中，設(shè)定：用戶相似性與產(chǎn)品相似性的權(quán)重系數(shù)λ=0.6，不同用戶間同時(shí)評(píng)論的產(chǎn)品(項(xiàng)目)數(shù)參數(shù)γ=30，不同產(chǎn)品(項(xiàng)目)被同時(shí)評(píng)論的用戶數(shù)參數(shù)δ=30，用戶相似度閾值η=0.5，產(chǎn)品(項(xiàng)目)相似度閾值θ=0.5。

實(shí)驗(yàn)表明(如表1所示)，本文算法綜合考慮了用戶相似度、產(chǎn)品(項(xiàng)目)相似度，對(duì)相似度進(jìn)行了修正，設(shè)置了預(yù)測閾值，更加合理，在不同訓(xùn)練集、不用產(chǎn)品(項(xiàng)目)數(shù)情況下，推薦效果比其他方法要優(yōu)異。本文算法在不同樣本量、產(chǎn)品(項(xiàng)目)數(shù)下，MAE值均比較低，保持了較高的穩(wěn)定性。

表1　本文算法與其他算法的MAE值比較

4　結(jié)論

本文提供了一種改進(jìn)的缺失數(shù)據(jù)協(xié)同過濾方法。通過判斷用戶、產(chǎn)品(項(xiàng)目)是否有相似用戶、產(chǎn)品(項(xiàng)目)，決定是否預(yù)測缺失數(shù)據(jù)。如果需要預(yù)測，則同時(shí)考慮用戶信息和產(chǎn)品(項(xiàng)目)信息，以提高預(yù)測準(zhǔn)確度。用淘寶移動(dòng)客戶端數(shù)據(jù)進(jìn)行了對(duì)比驗(yàn)證，實(shí)驗(yàn)結(jié)果顯示，本文方法比其他推薦方法更加優(yōu)異。

通過整合用戶和產(chǎn)品(項(xiàng)目)信息，采用基于用戶和產(chǎn)品(項(xiàng)目)的方法，得到了更好的預(yù)測結(jié)果。接下來，將從以下幾個(gè)方面做進(jìn)一步研究：(1)用戶相似性和產(chǎn)品相似性的權(quán)重系數(shù)變化對(duì)預(yù)測結(jié)果的影響；(2)用戶數(shù)、產(chǎn)品(項(xiàng)目)數(shù)參數(shù)變化對(duì)預(yù)測結(jié)果的影響；(3)用戶相似度、產(chǎn)品(項(xiàng)目)相似度閾值的變化對(duì)預(yù)測結(jié)果的影響；(4)用戶信息、產(chǎn)品(項(xiàng)目)信息之間關(guān)系的研究等。

[1] RESNICK P, IACOVOU N, SUCHAK M, et al. Grouplens: an open architecture for collaborative filtering of netnews[C]. Proceedings of ACM Conference on Computer Supported Cooperative Work, 1994:175-186.

[2] BREESE J S, HECKERMAN D, KADIE C. Empirical analysis of predictive algorithms for collaborative filtering[C]. In Proceedings of the 14th Conference on Uncertainty in Articifical Intelligence, 1998:43-52.

[3] Wang Jun, DEVRIES A P, REINDERS M J T. Unifying user-based and item-based collaborative filtering approaches by similarity fusion[A]. Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval[C].USA：Seatole, 2006:501-508.

[4] XUE G R, LIN C, YANG Q, et al. Scalable collaborative filtering using cluster-based smoothing[C]. Proceedings 28th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2005:114-121.

[5] Ma Hao, KING I, LYU M R. Effective missing data prediction for collaborate filtering[C]. SIGIR 2007: Proceedings of the Intermational ACM SIGIR Conference on Research and Development in Information Retrieval, Amsterdam the Netherlands, 2007:39-46.

[6] 黃創(chuàng)光，印鑒，汪靜，等.不確定近鄰的協(xié)同過濾推薦算法[J].計(jì)算機(jī)學(xué)報(bào)，2010，33(8)：1369-1376.

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

[8] MCLAUGHLIN M R， HERLOCKER J L. A collaborative filtering algorithm and evaluation metric that accurately model the user experience[C]. International ACM SIGIR Conference on Reseach and Development in Information Retrieral. ACM, 2004:329-336.

[9] HOFMANN T, HOFMANN T. Latent semantic models for collaborative filtering[J]. ACM Transactions on Information Systems, 2004, 22(1):89-115.

An improved collaborative filtering recommendation algorithm for missing data

Zhou Mingsheng1,2，Han Dongmei1

(1. School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China; 2.Shanghai Waigaoqiao Free Trade Zone United Development CO., LTD., Shanghai 200131, China)

Collaborative filtering recommendation algorithm has been widely studied, and widely applied in recent years in many business systems, such as Amazon, Taobao, etc. In practice, collaborative filtering recommendation algorithm faces the problem of data sparsity and low accuracy. The user-item matrix, which is the basic of collaborative filtering, is usually very sparse (with a large number of missing data), and this leads to inaccurate results. This paper attempts to improve the accuracy of collaborative filtering recommendation from two aspects: (1) the similarity between users and items ; (2) the prediction of missing data.Firstly, we used the enhanced Pearson Correlation Algorithm to improve the accuracy of user, item similarity calculation by increasing parameters. Then we proposed a new method for predicting missing data, which is based on both the information of users and the information of items. In our algorithm, we set similarity threshold respectively for the user and the item, and only when users or items similarity meet or exceed the threshold, the missing data is predicted. In the prediction process, we used both the user and the item similarity information to improve the accuracy of the algorithm. Finally, through the experimental analysis of the data set of Taobao mobile client, we found that our algorithm is superior to other collaborative filtering algorithms, and the robustness of data sparsity is much higher.

collaborative filtering; recommender system; missing data prediction; data sparsity

國家自然科學(xué)基金資助項(xiàng)目(41174007)；上海財(cái)經(jīng)大學(xué)研究生教育創(chuàng)新計(jì)劃項(xiàng)目(CXJJ-2014-440)

TP391

ADOI： 10.19358/j.issn.1674- 7720.2016.17.005

2016-05-03)

周明升(1981-)，通信作者，男，博士研究生，主要研究方向：決策支持、智慧城市。E-mail:simonzhou3000@163.com。

韓冬梅(1961-)，女，博士后出站，教授，博導(dǎo)，主要研究方向：決策支持,經(jīng)濟(jì)分析與預(yù)測。