改進(jìn)物品相似度計(jì)算的協(xié)同過濾算法

方 惠，李 民，鄧秀輝，余開朝

（昆明理工大學(xué)機(jī)電工程學(xué)院，云南昆明 650500）

0 引言

在信息爆炸的時(shí)代，用戶難以從大量數(shù)據(jù)信息中快速精確地獲取所需信息，容易產(chǎn)生信息超載（Information Overload）問題［1］。為幫助用戶快速找到感興趣的產(chǎn)品，推薦系統(tǒng)應(yīng)運(yùn)而生。近年來，推薦系統(tǒng)在電影、新聞、電子商務(wù)等諸多領(lǐng)域中起到了重要作用，有效減輕了信息超載現(xiàn)象。作為推薦系統(tǒng)的核心部分，推薦算法成為人們研究的熱門對象［2］。目前協(xié)同過濾（Collaborative Filtering，CF）算法已經(jīng)應(yīng)用于互聯(lián)網(wǎng)的眾多領(lǐng)域［3-6］，其實(shí)現(xiàn)原理是根據(jù)用戶以往在網(wǎng)絡(luò)中搜索產(chǎn)生的數(shù)據(jù)發(fā)掘其可能喜歡的東西，根據(jù)喜好內(nèi)容不同將用戶分成小組，推薦與其愛好相近的商品［7］。但該算法存在一些不足，如沒有考慮到用戶興趣會隨時(shí)間推移而發(fā)生變化，熱門物品也可能會影響相似度計(jì)算。以上問題均會導(dǎo)致推薦系統(tǒng)的精確度出現(xiàn)偏差，從而使用戶得不到滿意的推薦結(jié)果。

CF 算法是目前使用最廣泛、最有效的算法之一［8］，但存在推薦精確度不高等問題，許多學(xué)者對此進(jìn)行了研究。董立巖等［9］在相似度矩陣的計(jì)算過程中融入時(shí)間衰減因子，使推薦結(jié)果更具時(shí)效性；尹毫等［10］提出在物品相似度計(jì)算中融入物品懲罰因子以修正物品相似度矩陣的計(jì)算，在推薦精確度方面顯著提高；熊麗榮等［11］考慮到用戶興趣會隨著時(shí)間發(fā)生變化，故采用時(shí)間效應(yīng)模型函數(shù)處理用戶歷史評分?jǐn)?shù)據(jù)，推薦效果明顯優(yōu)于傳統(tǒng)算法；鄧華平［12］提出在CF 算法中加入項(xiàng)目聚類和時(shí)間衰減函數(shù)，加快了最近鄰居集合的尋找速度，提升了推薦精確度；崔國琪等［13］提出在物品相似度計(jì)算中融入物品懲罰因子，加入懲罰因子的CF 推薦算法在保持算法精確度的同時(shí)，可在一定程度上降低推薦結(jié)果流行度；Chen 等［14］從用戶評分角度出發(fā)，將平衡因子引入傳統(tǒng)的余弦相似度算法中，用于計(jì)算不同用戶間的項(xiàng)目評級尺度差異，提出了一種改進(jìn)的基于優(yōu)化用戶相似度的CF 算法，推薦精確度顯著提高；Lee 等［15］提出將偏好模型的概念應(yīng)用于CF 算法中，修正用戶—物品評分舉證，有效提高了該算法的精確度和召回率。

以上改進(jìn)算法僅提高了商品推薦的精確度，但未考慮到用戶興趣會隨時(shí)間推移而發(fā)生變化，亦未考慮將時(shí)間衰減函數(shù)與物品懲罰因子融合到一起。針對以上問題，本文在原有研究成果的基礎(chǔ)上，在傳統(tǒng)相似度矩陣計(jì)算中引入時(shí)間衰減函數(shù)和物品懲罰因子，得到改進(jìn)相似度矩陣的推薦算法在精確度、召回率和F1 值上均比傳統(tǒng)CF 推薦算法明顯提高，更有利于推薦出使用戶滿意的結(jié)果。

1 理論基礎(chǔ)

1.1 傳統(tǒng)CF 算法

傳統(tǒng)CF 算法可分為基于用戶的推薦算法（User CF）和基于商品的推薦算法（Item CF）。User CF 算法的主要思想為尋找與目標(biāo)用戶興趣相似的用戶集合，同時(shí)將該集合中用戶喜歡但沒有聽過的商品推薦給他們。Item CF 算法的主要思想為根據(jù)用戶歷史評分計(jì)算物品之間的相似度，通過物品相似度和用戶歷史行為預(yù)測用戶以往喜歡商品的相似物品［16］。傳統(tǒng)CF 算法的實(shí)現(xiàn)過程為：首先獲取歷史評分?jǐn)?shù)據(jù)，構(gòu)成網(wǎng)絡(luò)用戶—項(xiàng)目評分矩陣；然后計(jì)算網(wǎng)絡(luò)用戶或項(xiàng)目間的評分相似度，按照相似度對網(wǎng)絡(luò)用戶或項(xiàng)目進(jìn)行排列，排列靠前的幾個(gè)用戶或項(xiàng)目可以被看作是鄰居，利用得到的相似度和鄰居用戶歷史評分?jǐn)?shù)據(jù)計(jì)算預(yù)測評分；最后選取預(yù)測排名靠前的若干項(xiàng)作為推薦結(jié)果返回給目標(biāo)用戶或項(xiàng)目，至此完成推薦［17］。

傳統(tǒng)CF 算法存在的不足體現(xiàn)在以下兩個(gè)方面：①生活中，用戶興趣會隨著時(shí)間推移而發(fā)生改變，但傳統(tǒng)CF 算法等同考慮商品不同時(shí)間段的評分，導(dǎo)致尋找近鄰用戶時(shí)推薦精確度降低；②熱門商品評價(jià)人數(shù)多，在相似度計(jì)算中會影響推薦結(jié)果的精確度。

1.2 算法改進(jìn)的相似度計(jì)算

相似度矩陣在計(jì)算時(shí)分為基于用戶的相似度集合與基于商品的相似度集合。定義用戶集合U={u1,u2,…um}，商品集合I={i1,i2,…i3}，可用1 個(gè)n×m 的用戶—商品評分矩陣Hmn對商品相似度進(jìn)行建模，構(gòu)建的用戶—商品評分矩陣Hmn如下：

式（1）中，矩陣Hmn中的n 行代表n 個(gè)用戶，m 列代表m個(gè)商品，第n 行m 列矩陣元素rnm表示第n 個(gè)用戶對第m 個(gè)商品的評分。

項(xiàng)亮［18］引入熱門商品與該商品的幾何平均值以降低熱門商品與其他商品的相似度，公式如下：

式（2）中，|N(i) |表示評價(jià)過商品i的用戶集合，|N(j)|表示評價(jià)過商品j的用戶集合，|N(i) ?N(j) |表示對商品i和商品j都有過評價(jià)的用戶集合。

推薦系統(tǒng)不僅要反映出用戶的近期偏好，還要預(yù)測其長期偏好。Breese 等［19］提出不活躍用戶對商品相似度的影響大于活躍用戶，因此在計(jì)算時(shí)要降低活躍用戶對相似度權(quán)重的影響，即增加項(xiàng)，公式如下：

式（3）中，N(u)表示對商品u有過行為的所有用戶。

近期行為最能反映出用戶的當(dāng)前興趣，因此時(shí)間相隔較短的行為才能更好地反映商品之間的相似度，故在公式（3）中加上時(shí)間衰減衰減因子［20］，公式如下：

式（5）中，α為時(shí)間衰減因子的影響系數(shù)，用戶興趣變化越快，α的值越大，反之越?。?1］。

由式（4）得到用戶的最近行為，由于用戶的最近行為與當(dāng)前行為關(guān)系最大，因此計(jì)算用戶對商品的評分時(shí)還應(yīng)加上時(shí)間衰減函數(shù)最終得到用戶u對商品j的偏好程度為：

式（7）中，t0為當(dāng)前時(shí)間，rui為用戶u對商品i的偏好程度，β為時(shí)間衰減因子。

2 實(shí)驗(yàn)設(shè)計(jì)

對本文提出的算法與傳統(tǒng)CF 算法（余弦相似度）進(jìn)行比較，分別在不同K 值（近鄰用戶數(shù)）和Top N 推薦長度下比較二者的精確度、召回率和F1 值，并對實(shí)驗(yàn)結(jié)果進(jìn)行分析。

2.1 實(shí)驗(yàn)算法實(shí)現(xiàn)步驟

改進(jìn)商品相似度算法步驟如下：

輸入：用戶—商品評分矩陣Hmn，近鄰用戶數(shù)K，商品返回?cái)?shù)I，推薦列表長度N。

輸出：用戶推薦列表。

步驟1：在訓(xùn)練集中構(gòu)建用戶—商品評分矩陣Hmn。

步驟2：根據(jù)公式（3）計(jì)算加入物品懲罰因子的商品相似度矩陣wij。

步驟3：根據(jù)公式（4）加入時(shí)間衰減函數(shù)，計(jì)算用戶最近的商品相似度矩陣wij，其中參數(shù)α設(shè)置為0.5。

步驟4：根據(jù)公式（6）得到最終用戶當(dāng)前對商品的相似度矩陣wij，其中參數(shù)β設(shè)置為0.8。

步驟5：遍歷用戶歷史商品集合，從該集合中找出每個(gè)歷史商品最相似的K 個(gè)商品作為候選集。

步驟6：從候選集合中選出指定返回?cái)?shù)為I 的集合作為推薦結(jié)果。

2.2 實(shí)驗(yàn)準(zhǔn)備

以電影評分作為實(shí)驗(yàn)對象，選取GroupLens 實(shí)驗(yàn)室成立的MovieLens 站點(diǎn)中的ml-1m 數(shù)據(jù)集。如表1 所示，該數(shù)據(jù)集包含6 040 個(gè)用戶對3 900 部電影的評分記錄，其中每個(gè)用戶最少有20 條評分?jǐn)?shù)據(jù)，共計(jì)1 000 209 條評分記錄。評分劃分為5 個(gè)等級，用1～5 的整數(shù)表示，評分?jǐn)?shù)值越大表示該用戶對電影的喜愛程度越高。該評分?jǐn)?shù)據(jù)的稀疏度為1-1 000 209/（6 040×3 900）=0.956，兩個(gè)時(shí)間衰減因子α和β分別設(shè)置為0.5 和0.8。數(shù)據(jù)集中還包含了用戶個(gè)人信息和電影標(biāo)簽信息。

Table 1 Partial experimental data set表1 實(shí)驗(yàn)數(shù)據(jù)集部分展示

2.3 推薦指標(biāo)

為評價(jià)算法性能，將整個(gè)MovieLens 數(shù)據(jù)集進(jìn)一步拆分為不相交的兩個(gè)部分，分別為訓(xùn)練集和測試集。為此，引入變量x 作為測試集占整個(gè)數(shù)據(jù)集的百分比，設(shè)定x=0.2，即在整個(gè)數(shù)據(jù)集中，訓(xùn)練集占80%，測試集占20%，訓(xùn)練集與測試集比例為8∶2［22］。利用不同K 值和Top N 算法比較精確度（Precision）、召回率（Recall）和F1-Score 的變化，在3 次試驗(yàn)下取評價(jià)指標(biāo)的平均值作為實(shí)驗(yàn)結(jié)果。其中，N 為推薦列表中的商品總數(shù)，P 為目標(biāo)用戶在前N 項(xiàng)中的商品數(shù)。

其中，精確度定義：

召回率定義：

F1 定義：

2.4 影響因素

影響算法結(jié)果的操作有3 個(gè)：①將兩種不同相似度計(jì)算方法（余弦相似度、改進(jìn)余弦相似度）應(yīng)用到基于商品的CF 算法中；②使用不同K 值（近鄰用戶數(shù)）比較兩種算法在不同K 值下的精確度和召回率；③使用不同Top N 算法的推薦長度，比較算法改進(jìn)前后的精確度和F1-Score。考慮到加入時(shí)間衰減因子和懲罰因子后推薦商品的精確度，推薦列表不宜太長，因此本文將推薦列表長度設(shè)置為5、10、15、20。

2.5 實(shí)驗(yàn)結(jié)果與分析

2.5.1 余弦相似度算法改進(jìn)前后商品偏好得分變化

在相同參數(shù)下，根據(jù)用戶—商品評分矩陣計(jì)算相似度算法改進(jìn)前后的商品偏好得分情況。以1196 號用戶為例，在返回40 個(gè)商品的條件下，運(yùn)用改進(jìn)的余弦相似度算法計(jì)算1196 號用戶對未評價(jià)商品的偏好分?jǐn)?shù)為27.94，比傳統(tǒng)余弦相似度算法得出的商品偏好分?jǐn)?shù)（65.87）下降了37.93，具體如圖1 所示。說明用戶對商品的偏好程度是隨著時(shí)間變化的，比較符合現(xiàn)實(shí)情況。

2.5.2 不同近鄰用戶數(shù)K 下算法的精確度和召回率

將改進(jìn)相似度的算法稱為New Item CF，傳統(tǒng)的基于商品的CF 算法稱為Item CF。在K 值（近鄰用戶個(gè)數(shù)）不同，物品返回?cái)?shù)為40 的條件下，兩種算法的精確度和召回率分別如圖2、圖3 所示。由圖2 可知，New Item CF 的精確度明顯高于Item CF，在K=200 時(shí)，New Item CF 的精確度達(dá)到最大，為0.18，比Item CF 的精確度提高了9%，二者差值也達(dá)到最大。由圖3 可知，在相同條件下，New Item CF 的召回率明顯高于Item CF，在K=200 時(shí)，New Item CF 的召回率達(dá)到最大，為0.17，比Item CF 提高了7.2%，二者差值也達(dá)到最大。

Fig.1 Score of items before and after similarity algorithm improvement圖1 相似度算法改進(jìn)前后物品得分

Fig.2 Precision comparison of recommendation results under different K values圖2 不同K 值下推薦結(jié)果的精確度比較

Fig.3 Changes of recall rate under different K values圖3 不同K 值下召回率的變化

2.5.3 不同Top N 算法下精確度比較

將商品近鄰數(shù)設(shè)置為40，通過設(shè)置不同推薦列表長度n 測試改進(jìn)算法的精確度。由圖4 可知，當(dāng)推薦長度為5時(shí)，New Item CF 算法的精確度大于Item CF 算法。然而，隨著推薦長度的增加，New Item CF 和Item CF 的精確度均開始下降，當(dāng)Top N=10 時(shí)，Item CF 的精確度超過New Item CF。因此，在使用New Item CF 算法推薦商品時(shí)，推薦列表不宜過長。

Fig.4 Precision under different Top-N algorithm圖4 不同Top-N 算法下的精確度

2.5.4 不同Top N 算法下F1 值比較

將商品近鄰數(shù)設(shè)置為40，通過設(shè)置不同推薦列表長度n 測試算法的F1 值。由圖5 可知，當(dāng)推薦長度<15 時(shí)，New Item CF 的F1 值大于Item CF。但隨著推薦列表長度的增加，即當(dāng)推薦長度>15 時(shí)，New Item CF 的F1 值小于Item CF。由此可知，加入時(shí)間衰減函數(shù)和物品懲罰因子后，隨著推薦長度的增加，New Item CF 的推薦效果會差于Item CF。

Fig.5 F1 values for different Top-N algorithm圖5 不同Top-N 算法下的F1 值

3 結(jié)語

在日常生活中，用戶的興趣愛好可能會隨著時(shí)間推移而發(fā)生變化。本文針對用戶的個(gè)性化需求將時(shí)間衰減函數(shù)和物品懲罰因子融入到相似度矩陣計(jì)算中，通過一系列數(shù)據(jù)證明，若實(shí)驗(yàn)參數(shù)設(shè)置得當(dāng)，在一定條件下，改進(jìn)的推薦算法在精確度、召回率和F1 值方面比傳統(tǒng)CF 算法明顯提高，但當(dāng)推薦列表長度不斷增加時(shí)，改進(jìn)算法的精確度和F1 值開始下降，其性能開始弱于傳統(tǒng)CF 算法。下一步研究重點(diǎn)：①在不降低推薦精確度的同時(shí)擴(kuò)大推薦商品的范圍，擴(kuò)展用戶興趣面；②根據(jù)用戶心情變化快慢賦予具體參數(shù)，表示用戶當(dāng)前不同的興趣特點(diǎn)，以更加精確和實(shí)時(shí)地進(jìn)行個(gè)性化推送。