方 惠，李 民，鄧秀輝，余開(kāi)朝

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

0 引言

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

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

以上改進(jìn)算法僅提高了商品推薦的精確度，但未考慮到用戶興趣會(huì)隨時(shí)間推移而發(fā)生變化，亦未考慮將時(shí)間衰減函數(shù)與物品懲罰因子融合到一起。針對(duì)以上問(wèn)題，本文在原有研究成果的基礎(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í)將該集合中用戶喜歡但沒(méi)有聽(tīng)過(guò)的商品推薦給他們。Item CF 算法的主要思想為根據(jù)用戶歷史評(píng)分計(jì)算物品之間的相似度，通過(guò)物品相似度和用戶歷史行為預(yù)測(cè)用戶以往喜歡商品的相似物品［16］。傳統(tǒng)CF 算法的實(shí)現(xiàn)過(guò)程為：首先獲取歷史評(píng)分?jǐn)?shù)據(jù)，構(gòu)成網(wǎng)絡(luò)用戶—項(xiàng)目評(píng)分矩陣；然后計(jì)算網(wǎng)絡(luò)用戶或項(xiàng)目間的評(píng)分相似度，按照相似度對(duì)網(wǎng)絡(luò)用戶或項(xiàng)目進(jìn)行排列，排列靠前的幾個(gè)用戶或項(xiàng)目可以被看作是鄰居，利用得到的相似度和鄰居用戶歷史評(píng)分?jǐn)?shù)據(jù)計(jì)算預(yù)測(cè)評(píng)分；最后選取預(yù)測(cè)排名靠前的若干項(xiàng)作為推薦結(jié)果返回給目標(biāo)用戶或項(xiàng)目，至此完成推薦［17］。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸出：用戶推薦列表。

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

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

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

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

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

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

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

以電影評(píng)分作為實(shí)驗(yàn)對(duì)象，選取GroupLens 實(shí)驗(yàn)室成立的MovieLens 站點(diǎn)中的ml-1m 數(shù)據(jù)集。如表1 所示，該數(shù)據(jù)集包含6 040 個(gè)用戶對(duì)3 900 部電影的評(píng)分記錄，其中每個(gè)用戶最少有20 條評(píng)分?jǐn)?shù)據(jù)，共計(jì)1 000 209 條評(píng)分記錄。評(píng)分劃分為5 個(gè)等級(jí)，用1～5 的整數(shù)表示，評(píng)分?jǐn)?shù)值越大表示該用戶對(duì)電影的喜愛(ài)程度越高。該評(píng)分?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)

為評(píng)價(jià)算法性能，將整個(gè)MovieLens 數(shù)據(jù)集進(jìn)一步拆分為不相交的兩個(gè)部分，分別為訓(xùn)練集和測(cè)試集。為此，引入變量x 作為測(cè)試集占整個(gè)數(shù)據(jù)集的百分比，設(shè)定x=0.2，即在整個(gè)數(shù)據(jù)集中，訓(xùn)練集占80%，測(cè)試集占20%，訓(xùn)練集與測(cè)試集比例為8∶2［22］。利用不同K 值和Top N 算法比較精確度（Precision）、召回率（Recall）和F1-Score 的變化，在3 次試驗(yàn)下取評(píng)價(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 算法的推薦長(zhǎng)度，比較算法改進(jìn)前后的精確度和F1-Score?？紤]到加入時(shí)間衰減因子和懲罰因子后推薦商品的精確度，推薦列表不宜太長(zhǎng)，因此本文將推薦列表長(zhǎng)度設(shè)置為5、10、15、20。

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

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

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

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

將改進(jìn)相似度的算法稱(chēng)為New Item CF，傳統(tǒng)的基于商品的CF 算法稱(chēng)為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，通過(guò)設(shè)置不同推薦列表長(zhǎng)度n 測(cè)試改進(jìn)算法的精確度。由圖4 可知，當(dāng)推薦長(zhǎng)度為5時(shí)，New Item CF 算法的精確度大于Item CF 算法。然而，隨著推薦長(zhǎng)度的增加，New Item CF 和Item CF 的精確度均開(kāi)始下降，當(dāng)Top N=10 時(shí)，Item CF 的精確度超過(guò)New Item CF。因此，在使用New Item CF 算法推薦商品時(shí)，推薦列表不宜過(guò)長(zhǎng)。

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

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

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

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

3 結(jié)語(yǔ)

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