基于云填充和混合相似性的協(xié)同過濾推薦算法的研究

成韻姿　陳曦　傅明

摘要：針對傳統(tǒng)推薦算法的相似性度量準(zhǔn)確性不高及數(shù)據(jù)極端稀疏性等問題，提出一種基于云填充和混合相似性的協(xié)同過濾推薦算法。首先通過云模型填充用戶-項(xiàng)目評分矩陣，然后對相似性度量方法進(jìn)行改進(jìn)，將基于時(shí)間序列的用戶間影響力融合到基于Jaccard系數(shù)的相似性度量方法中。在MovieLens數(shù)據(jù)集上的驗(yàn)證結(jié)果表明，改進(jìn)后的算法提高了推薦精度同時(shí)在一定程度上克服了數(shù)據(jù)稀疏性的影響。

關(guān)鍵詞：協(xié)同過濾推薦算法；云填充；時(shí)序行為影響力；Jaccard系數(shù)

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

Abstract：A collaborative filtering recommendation algorithm based on cloud model filling and hybrid similarity was proposed to measure the similarity of the traditional recommendation algorithm with low accuracy and extreme sparsity of data. First， the useritem rating matrix was filled by the cloud model， and then the similarity measure method was improved， and the influence of the user based on time series was fused to the similarity measure method based on the Jaccard coefficient. The validation results on MovieLens data sets show that the improved algorithm can improve the recommendation accuracy and overcome the influence of data sparsity to a certain extent.

Key words：collaborative filtering recommendation algorithm； cloud model filling； temporal behavior influence； Jaccard coefficients

1引言

隨著信息技術(shù)和互聯(lián)網(wǎng)的發(fā)展，信息的產(chǎn)生、加工、傳播變得越來越容易，人們每天都接觸大量的信息，進(jìn)入了信息過載的時(shí)代。在這個(gè)時(shí)代，無論是消費(fèi)者還是商家都遇到了很大挑戰(zhàn)：一方面，對于消費(fèi)者來說，面對如此海量的數(shù)據(jù)信息，要從中剔除冗余信息、挑選出自己真正需要的信息，猶如大海撈針；另一方面，對于商家來說，要有針對性地推送商品信息，讓自己的商品受到廣大消費(fèi)者的關(guān)注，也是一件非常困難的事情。在此背景下，電子商務(wù)推薦系統(tǒng)應(yīng)運(yùn)而生。

協(xié)同過濾推薦算法[1-2]是目前電子商務(wù)推薦系統(tǒng)中應(yīng)用最廣泛最成功的推薦技術(shù)。它的主要思想是利用已有用戶群過去的行為或意見預(yù)測當(dāng)前用戶最可能喜歡哪些東西或?qū)δ男〇|西感興趣[3]。那么，整個(gè)推薦算法的關(guān)鍵是找出目標(biāo)用戶的最近鄰居集合。然而，其歸根結(jié)底在于用戶或項(xiàng)目間相似性的度量[4-7]。因此，用戶或項(xiàng)目間的相似性度量是否準(zhǔn)確，直接關(guān)系到整個(gè)推薦系統(tǒng)的推薦質(zhì)量。傳統(tǒng)的相似性度量方法主要有：余弦相似性、相關(guān)相似性和修正的余弦相似都有其不足之處。在現(xiàn)實(shí)的數(shù)據(jù)中，由于用戶評分?jǐn)?shù)據(jù)的極端稀疏性，導(dǎo)致用戶間相似性的度量不夠準(zhǔn)確，推薦精度較低。而且，大部分的推薦算法并沒有考慮用戶相互之間的影響關(guān)系，導(dǎo)致推薦系統(tǒng)的推薦質(zhì)量下降。

與上述相關(guān)工作不同，本文利用云模型填充用戶-項(xiàng)目評分矩陣，在分析基于時(shí)序行為的用戶影響力和基于Jaccard系數(shù)的相似性度量方法的基礎(chǔ)上，對用戶間相似性的計(jì)算方法進(jìn)行改進(jìn)。將改進(jìn)后的算法在MovieLens數(shù)據(jù)集上進(jìn)行了相應(yīng)的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法提高了推薦精度，同時(shí)在一定程度上克服了數(shù)據(jù)稀疏性的影響。

當(dāng)一個(gè)推薦系統(tǒng)搭建好后，需要解決的首要問題是如何判斷推薦系統(tǒng)的好壞。然而，推薦系統(tǒng)擁有多種評價(jià)標(biāo)準(zhǔn)，這些評價(jià)標(biāo)準(zhǔn)可用于評價(jià)推薦系統(tǒng)各方面的性能。由于不同的系統(tǒng)在不同的應(yīng)用背景下表現(xiàn)不同，研究者們很難選取恰當(dāng)?shù)脑u價(jià)標(biāo)準(zhǔn)對系統(tǒng)的表現(xiàn)進(jìn)行評估。大多數(shù)研究者選擇采用準(zhǔn)確度來評價(jià)推薦算法的好壞。預(yù)測準(zhǔn)確度是度量一個(gè)推薦算法的預(yù)測打分與用戶實(shí)際打分的相似程度，其中一個(gè)經(jīng)典方法是度量預(yù)測打分與實(shí)際打分的平均絕對誤差。然而，標(biāo)準(zhǔn)平均絕對誤差[8]（Normalized Mean Absolute Error，簡稱NMAE）是平均絕對誤差在打分值區(qū)間內(nèi)作標(biāo)準(zhǔn)化，從而方便在不同的數(shù)據(jù)集上對算法的效果進(jìn)行比較。因此，標(biāo)準(zhǔn)平均絕對誤差的值越小表示該算法對用戶行為的預(yù)測越準(zhǔn)確。本文選用標(biāo)準(zhǔn)平均絕對誤差的方法來評估推薦算法的優(yōu)劣性。

2相關(guān)工作

2.1云填充

在實(shí)際生活中，用戶對商品的評分記錄是很少的，從而評分矩陣相當(dāng)稀疏，導(dǎo)致推薦效果大大降低。為解決該問題，本文采用云填充[9-10]的方法解決稀疏問題。云模型[11]是李德毅院士提出的一種定性定量不確定性轉(zhuǎn)換模型，能夠?qū)崿F(xiàn)定性概念與定量數(shù)值之間的不確定性轉(zhuǎn)換。云填充的基本思想是：先找出未評分的項(xiàng)目，采用云模型計(jì)算項(xiàng)目之間的相似性，找出該項(xiàng)目的相似項(xiàng)目， 利用用戶對相似項(xiàng)目的評分來預(yù)測未評分項(xiàng)目的評分，從而填充用戶項(xiàng)目矩陣。

對于用戶-項(xiàng)目評分矩陣R，用戶有未評分項(xiàng)目c，其評分頻度向量I=[I0，I1，I2，I3，I4，I5]，其中I0～I(xiàn)5表示6個(gè)評分等級出現(xiàn)的次數(shù)。通過逆向云發(fā)生器，即實(shí)現(xiàn)從定量值到定性概念的轉(zhuǎn)換，可以得到該項(xiàng)目的評分特征向量V=[Ex，En，He]，其中Ex、En、He分別為期望、熵、超熵。兩個(gè)項(xiàng)目之間的相似性由評分特征向量的夾角余弦來表示，如公式（1）。

sim（c，d）=VcVd‖Vc‖‖Vd‖ （1）

由此，找出用戶未評分項(xiàng)目的相似項(xiàng)目集D，未評分項(xiàng)目c的預(yù)測評分如公式（2），以此來填充用戶-項(xiàng)目評分矩陣R。

R（i，c）=∑d∈Dsim（c，d）×R（i，d）∑d∈D（sim（c，d）） （2）

其中，d表示未評分項(xiàng)目c的相似項(xiàng)目，sim（c，d）表示項(xiàng)目c和項(xiàng)目d的相似性，R（i，d）表示用戶i對項(xiàng)目d評分。

2.2時(shí)序行為影響力

雖然協(xié)同過濾推薦算法跟其他推薦算法相比取得了巨大的成功，但是其仍存在著諸多問題，其中很重要的一點(diǎn)是傳統(tǒng)的協(xié)同過濾推薦算法經(jīng)常忽略興趣漂移問題。所謂興趣漂移，是指用戶對商品的興趣偏好會(huì)隨著時(shí)間的推移而變化。Koren等人[12]提出的TimeSVD++算法將時(shí)間信息加入到用戶（產(chǎn)品）的特征向量中，有效解決了興趣漂移問題，取得了良好的結(jié)果。

超市購物籃數(shù)據(jù)常常包含關(guān)于商品何時(shí)被用戶購買的時(shí)間信息，可以按照購買時(shí)間的先后次序，將用戶在一段時(shí)間內(nèi)的購物事件拼接形成一個(gè)時(shí)間序列[13]。用戶或商品的消費(fèi)時(shí)間信息可能會(huì)隱藏著一部分規(guī)律，利用這些規(guī)律可以在一定程度上識(shí)別系統(tǒng)的重要特征，或者預(yù)測特定事件的未來發(fā)生?；跁r(shí)序信息的推薦算法通過將時(shí)序信息加入到現(xiàn)有的推薦模型中，使得模型能夠?qū)W習(xí)到數(shù)據(jù)的動(dòng)態(tài)變化，從而優(yōu)化推薦效果[14]。

社會(huì)網(wǎng)絡(luò)中的結(jié)點(diǎn)對應(yīng)的對象之間存在著各種各樣的關(guān)系，通過這些關(guān)系，對象之間也相互影響[15-16]。以用戶的關(guān)系為例，用戶在消費(fèi)某些商品時(shí)經(jīng)常受到朋友關(guān)系的影響，研究表明，通過朋友購買的商品向目標(biāo)用戶推薦商品，往往比簡單的利用相似度來推薦商品的方法更可靠[17-19]。

由于傳統(tǒng)的協(xié)同過濾推薦算法經(jīng)常忽略了用戶之間的關(guān)系，基于用戶社會(huì)化關(guān)系挖掘的推薦算法是將用戶關(guān)系融入到現(xiàn)有的協(xié)同過濾算法中，以提高算法的準(zhǔn)確度。

孫光福等人[14]提出了一種基于用戶間的時(shí)序消費(fèi)行為建模的方法，只需要利用用戶的消費(fèi)時(shí)間先后信息來挖掘用戶之間的相互隱含影響關(guān)系，就可以發(fā)現(xiàn)對當(dāng)前用戶影響最大的鄰居集合。

在下面的例子中，形象地說明用戶間的影響關(guān)系，如圖1所示。

假設(shè)在一定時(shí)間段內(nèi)，用戶甲消費(fèi)了25個(gè)商品，用戶乙消費(fèi)了85個(gè)商品，用戶甲與用戶乙消費(fèi)商品的并集的個(gè)數(shù)是100個(gè)。根據(jù)用戶甲與用戶乙的消費(fèi)時(shí)間先后信息形成序列，在用戶甲與用戶乙共同消費(fèi)的商品中，有10件商品用戶甲的消費(fèi)時(shí)間比用戶乙要早，即用戶甲先消費(fèi)然后用戶乙才消費(fèi)，說明用戶甲對用戶乙有一定的影響力。由此可得用戶甲對用戶乙的影響力為10/100=0.1，同理可得用戶乙對用戶甲的影響力為23/100=0.23。由圖可知，甲與丁、丁與丙、乙與丙以及丙與甲之間的影響關(guān)系是單向的，也就是說兩用戶之間的影響關(guān)系是不對稱的。那么用戶之間的影響力如公式（3）。

effect（i，j）=wijunionij （3）

其中，對于用戶i與用戶j共同消費(fèi)過的商品，wij表示用戶i比用戶j先消費(fèi)的商品數(shù)，unionij為用戶i和用戶j所消費(fèi)商品的并集，effect（i，j）為用戶i對用戶j的有向影響力。根據(jù)計(jì)算出的影響力大小，可以找出影響力最大的k個(gè)鄰居用戶。

2.3Jaccard系數(shù)

Jaccard相似性系數(shù)也可以用作度量用戶相似性，如公式（4）。

sim（i，j）=Itemi∩ItemjItemi∪Itemj （4）

其中，Itemi、Itemj分別表示用戶i和用戶j評分過的項(xiàng)目集合。

3一種混合相似性的度量方法

3.1改進(jìn)后的相似性

基于時(shí)序行為的最近鄰建模方法是根據(jù)用戶消費(fèi)時(shí)間先后信息構(gòu)建用戶關(guān)系網(wǎng)絡(luò)圖，計(jì)算出用戶之間的相互影響力，可以找到對目標(biāo)用戶影響最大的鄰居集合。Jaccard系數(shù)相似性是通過兩個(gè)用戶評分分布來度量兩個(gè)用戶之間的相似性，兩用戶共同評分的項(xiàng)目所占的比例越大，相似性越高。以上兩種方法的側(cè)重點(diǎn)不同，都在一定程度上提高了推薦質(zhì)量，筆者希望找到一種融合方法，對上述兩種方法有所發(fā)展。

為了進(jìn)一步提高相似度的準(zhǔn)確性，將時(shí)序行為影響力融入到基于Jaccard的相似性度量中，得到改進(jìn)后的用戶相似性如公式（5）。

simfinal（i，j）=αsim（i，j）+（1-α）effect（i，j） （5）

其中，effect（i，j）表示用戶i對用戶j的影響力，sim（i，j）表示用戶i與用戶j基于Jaccard系數(shù)的用戶相似性。

改進(jìn)后的算法融合了兩種相似性度量方法的優(yōu)點(diǎn)，適用范圍將更廣泛。改進(jìn)后的方法考慮到不同用戶的關(guān)注項(xiàng)目集合的不同對相似性的影響，并且考慮了用戶的消費(fèi)時(shí)間先后信息反映出的用戶間隱含影響關(guān)系，增加了度量用戶相似性的信息量，降低了數(shù)據(jù)稀疏性的影響，提高了相似度的準(zhǔn)確性。但改進(jìn)后的相似性度量方法較基于時(shí)序行為的影響力和基于Jaccard系數(shù)的相似性復(fù)雜，對算法的可擴(kuò)展性造成一定影響。

3.2算法流程

基于云填充和混合相似性的協(xié)同過濾推薦算法的基本思想是：首先利用云模型對用戶-項(xiàng)目評分矩陣進(jìn)行填充，從而降低數(shù)據(jù)稀疏性的影響；其次，建立用戶-項(xiàng)目評分時(shí)間矩陣，根據(jù)用戶對共同評分項(xiàng)目的評分時(shí)間先后順序，計(jì)算用戶之間的影響力；最后， 將時(shí)序行為影響力融入到基于Jaccard系數(shù)的相似性度量中，找出最近鄰居，產(chǎn)生推薦結(jié)果。

具體步驟如下：

步驟1：利用云模型填充用戶-項(xiàng)目評分矩陣R，得到R；

步驟2：由R根據(jù)公式（3）計(jì)算出用戶的影響力矩陣effect；

步驟3：由R根據(jù)公式（4）計(jì)算出基于Jaccard系數(shù)的相似性矩陣sim；

步驟4：根據(jù)公式（5）計(jì)算出改進(jìn)后的用戶相似性矩陣simfinal；

步驟5：由simfinal計(jì)算出用戶k個(gè)最近鄰居，根據(jù)最近鄰居的偏好為目標(biāo)用戶進(jìn)行推薦。

4實(shí)驗(yàn)結(jié)果及分析

4.1數(shù)據(jù)集和推薦質(zhì)量的評價(jià)標(biāo)準(zhǔn)

為了測試改進(jìn)的推薦算法的有效性，本文采用了GroupLens Research網(wǎng)站提供的包含100000個(gè)電影評分?jǐn)?shù)據(jù)的MovieLens數(shù)據(jù)集，涉及943個(gè)用戶和1682部電影。該數(shù)據(jù)集中每個(gè)用戶都至少評價(jià)過20部電影，其評分值是從1到5的整數(shù)，評分?jǐn)?shù)值越高表示用戶對該電影越喜歡。在實(shí)驗(yàn)中，隨機(jī)地將80%的數(shù)據(jù)劃分為訓(xùn)練集，剩余的20%的數(shù)據(jù)作為測試集。

常用的推薦質(zhì)量評估方法有平均絕對誤差（Mean Absolute Error，簡稱MAE）[17]、平均平方誤差和標(biāo)準(zhǔn)平均絕對誤差NMAE[18-19] 。

對于用戶i，平均絕對誤差MAEi公式如式（6）。

MAEi=∑nic=1pic-ricni （6）

其中，ni表示用戶i在測試集中已經(jīng)評分過的項(xiàng)目的個(gè)數(shù)（ni≤n），pic、ric分別為用戶i對項(xiàng)目c的預(yù)測評分及其對應(yīng)的實(shí)際評分。

對于所有用戶的平均絕對誤差見公式（7），標(biāo)準(zhǔn)平均絕對誤差見公式（8）。

MAE=∑mi=1MAEim （7）

NMAE=MAErmax -rmin （8）

其中，rmax和rmin分別為用戶打分區(qū)間的最大值和最小值。

標(biāo)準(zhǔn)平均絕對誤差（NMAE）就是平均絕對誤差在打分值區(qū)間內(nèi)作歸一化，從而方便在不同的數(shù)據(jù)集上對同一個(gè)算法的表現(xiàn)進(jìn)行比較。NMAE能夠較為直觀地對推薦質(zhì)量進(jìn)行評估，容易理解。如果NMAE的值越小，那么推薦的準(zhǔn)確性就越高。

4.2實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)1 參數(shù)α對算法的影響。

本文中最終相似度由影響力和Jaccard系數(shù)兩部分組成，而參數(shù)α是平衡兩者的權(quán)重。α越大，說明基于Jaccard系數(shù)的相似性在最終相似性中的比重越大。實(shí)驗(yàn)首先比較了本文算法在參數(shù)α的不同取值下的結(jié)果。在實(shí)驗(yàn)中，分別設(shè)定了參數(shù)α的不同取值α=[0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9]，算法的其他參數(shù)均設(shè)置為使算法最優(yōu)時(shí)的相應(yīng)值。

比較不同的α值對NMAE值的影響，實(shí)驗(yàn)結(jié)果如圖2所示。

根據(jù)結(jié)果可以看出，參數(shù)α對算法有較大的影響，隨著α的增加，本文算法的標(biāo)準(zhǔn)平均絕對誤差NMAE不斷增加，說明了引入基于時(shí)序行為的有向影響力對用戶間的相似性有更加重要的影響。同時(shí)發(fā)現(xiàn)，當(dāng)α=0.5時(shí)變化趨于平緩。

實(shí)驗(yàn)2 最近鄰居個(gè)數(shù)對算法的影響。

實(shí)驗(yàn)首先比較最近鄰居個(gè)數(shù)對不同的相似性度量方法的影響。在實(shí)驗(yàn)中，選擇的相似性度量方法分別為本文算法、余弦相似性、修正的余弦相似性、相關(guān)相似性。實(shí)驗(yàn)從不同的最近鄰居個(gè)數(shù)比較算法的推薦質(zhì)量，測試鄰居個(gè)數(shù)分別為5、10、15、20、25、30、35，實(shí)驗(yàn)結(jié)果如圖3所示。

從實(shí)驗(yàn)結(jié)果可以看出：①隨著鄰居個(gè)數(shù)的增加，在一定程度上增加了運(yùn)算的復(fù)雜度，標(biāo)準(zhǔn)平均絕對誤差NMAE有所上升，當(dāng)鄰居個(gè)數(shù)增加到一定的值時(shí)這種變化趨于平緩。②本文中改進(jìn)的相似性度量方法與傳統(tǒng)的相似性度量方法有較大提高，進(jìn)一步說明基于時(shí)序行為的用戶有向影響力與基于Jaccard系數(shù)相似性相結(jié)合的方法能比較有效提高協(xié)同過濾算法的推薦精度。

5結(jié)束語

本文對傳統(tǒng)的協(xié)同過濾算法中度量用戶間相似性的方法進(jìn)行改進(jìn)。首先比較傳統(tǒng)算法中度量用戶間相似性的方法，然后將基于時(shí)間序列的用戶間影響力融合到基于Jaccard系數(shù)的相似性度量方法中。改進(jìn)的方法考慮到了用戶共同評分項(xiàng)目個(gè)數(shù)對相似性的影響，并且考慮了用戶間的隱含影響關(guān)系，增加了時(shí)效性，從而提高了相似度的準(zhǔn)確性，在某種程度上降低了數(shù)據(jù)稀疏性的影響并且提高了推薦結(jié)果的準(zhǔn)確性。接下來將會(huì)對如何更好地選取參數(shù)α以及如何考慮空間、任務(wù)等因素更好地完成推薦進(jìn)行研究。

參考文獻(xiàn)

[1]馬宏偉， 張光衛(wèi)， 李鵬. 協(xié)同過濾推薦算法綜述[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2009， 30（7）： 1282-1288.

[2]LIU Q，CHEN E H，XIONG H，et al.Enhancing collaborative filtering by user interests expansion via personalized ranking[J]. IEEE Trans. on Systems， Man and Cybernetics—B， 2012， 42（1）： 218-233.

[3]JANNACH D，ZANKER M，F(xiàn)ELFERNING A，et al.推薦系統(tǒng)[M]. 蔣凡，譯. 北京：人民郵電出版社， 2013.

[4]SU J H， YEH H H， YU P S， et al. Music recommendation using content and context information mining[J]. IEEE Intelligent Systems， 2010， 25（1）： 16-26.

[5] 冷亞軍， 陸青， 梁昌勇. 協(xié)同過濾推薦技術(shù)綜述[J]. 模式識(shí)別與人工智能， 2014， 27（8）： 720-734.

[6]王立才， 孟祥武， 張玉潔. 上下文感知推薦系統(tǒng)[J]. 軟件學(xué)報(bào)， 2012， 23（1）： 1-20.

[7]孟祥武， 胡勛， 王立才， 等. 移動(dòng)推薦系統(tǒng)及其應(yīng)用[J]. 軟件學(xué)報(bào)， 2013， 24（1）： 91-108.

[8]劉建國， 周濤， 郭強(qiáng)， 等. 個(gè)性化推薦系統(tǒng)評價(jià)方法綜述[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 2009， 6（3）： 1-10.

[9]張光衛(wèi)，李德毅，李鵬，等.基于云模型的協(xié)同過濾推薦算法[J].軟件學(xué)報(bào)，2007，18（10）：2403-2411.

[10]毛志勇，趙盼盼.基于云填充和蟻群聚類的協(xié)同過濾圖書推薦算法[J].現(xiàn)代情報(bào)，2015，35（5）.

[11]李德毅，杜鹢.不確定性人工智能[M].北京：國防工業(yè)出版社，2005，143-144.

[12]KOREN Y. Collaborative filtering with temporal dynamics[C].In： Proc. of the ACM SIGKDD Conf. on Knowledge Discovery and Data Mining. ACM Press， 2009. 89-97.

[13]TAN Pangning，STEINBACH M，kUMAR V.數(shù)據(jù)挖掘?qū)д揫M]. 范明， 范宏建， 等， 譯. 北京：人民郵電出版社， 2011.

[14]孫光福，吳樂，劉淇，等.基于時(shí)序行為的協(xié)同過濾推薦算法[J].軟件學(xué)報(bào)，2013，24（11）：2721-2733.

[15]劉紅巖. 社會(huì)計(jì)算：用戶在線行為分析與挖掘[M]. 北京：清華大學(xué)出版社， 2014.

[16]郭強(qiáng)， 劉建國. 在線社會(huì)系統(tǒng)的用戶行為分析研究進(jìn)展[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 2015， 12（2）： 97-102.

[17]孟祥武， 劉樹棟， 張玉潔， 等. 社會(huì)化推薦系統(tǒng)研究[J]. 軟件學(xué)報(bào)， 2015， 26（6）： 1356-1372.

[18]WANG Z，SUN L F，ZHU W W，et al.Joint social and content recommendation for usergenerated videos in online social network[J]. IEEE Trans. on Multimedia， 2013， 15（3）： 698-710.

[19]QUIJANOSANCHEZ L，RECIOGARCIA J， DIAZAGUDO B. Social factors in group recommender systems[J]. ACM Trans. on Intelligent Systems and Technology， 2013， 4（1）： Article No.8.