張世顯，李平

（長春理工大學 計算機科學與技術學院，長春 130022）

隨著Internet的快速發(fā)展，網(wǎng)絡上的信息每天都以PB級別增長?；ヂ?lián)網(wǎng)雖然給我們的生活帶來了方便，但是信息超載和信息迷航的問題也隨之而來［1-2］。面臨著如此巨大的數(shù)據(jù)，人們怎么樣才能得到自己想要的信息呢？搜索引擎便應運而生，它不僅能夠促進互聯(lián)網(wǎng)的服務質(zhì)量，同時還能減少用戶的搜索耗時，排除掉大量干擾和無關信息［3］。但是當人們在對物品沒有意愿的情況下，它并不能解決人們的需求。為了解決這一問題，個性化推薦系統(tǒng)應運而生，它是一種主動性的信息過濾方式［4-5］。推薦系統(tǒng)可以根據(jù)用戶的歷史信息，在用戶沒有需求的情況下提供精準的個性化推薦，從而引導用戶獲取有用的信息［6］。

協(xié)同過濾算法是目前發(fā)展比較成熟的個性化推薦算法，尤其是在電子商務中取得了非常好的效果。據(jù)悉亞馬遜通過推薦算法，將其銷售額提升了大約30%。但是，傳統(tǒng)的協(xié)同過濾算法在計算相似度和預測評分時太過粗糙，沒有考慮到評分對共現(xiàn)值的影響以及用戶的興趣遷移對評分的影響。針對這樣的情況，本文主要提出兩點改進：首先通過決策樹模型找到評分與共現(xiàn)值之間的關系，實驗中會通過多個模型分別測試，找出最優(yōu)模型；其次引入指數(shù)時間模型來解決用戶興趣遷移問題，提高推薦的時效性。

1 相關研究

1.1 傳統(tǒng)的協(xié)同過濾算法

協(xié)同過濾算法是推薦系統(tǒng)中運用最為成功的信息過濾算法［7］，主要提取用戶產(chǎn)生的歷史行為做出推薦［8］。傳統(tǒng)的協(xié)同過濾算法主要分為基于物品的協(xié)同過濾算法（ItermCF）和基于用戶的協(xié)同過濾算法（UserCF）。本論文以UserCF作為研究對象，對目標用戶首先通過相似度找到K個最近鄰，然后把K個最近鄰產(chǎn)生行為而目標用戶沒有產(chǎn)生行為的物品，通過TOP-N的方式推薦給目標用戶。常見的相似度計算方法有歐氏距離相似度方法（式（1））、余弦相似度方法（式（2））、皮爾遜相似度方法（式（3））、Salton相似度方法（式（4））等。通過TOP-N推薦的預測評分公式如式（5）所示。本論文中采用Salton相似度方法來計算用戶的最近鄰。

其中，U表示用戶集合，I表示用戶u和v共同評分過物品的集合，rui表示用戶u對物品i評分，rvi表示用戶u對物品i的評分表示用戶u的評分均值表示用戶v的評分均值。

1.2 研究現(xiàn)狀

近幾年，有很多學者對這些問題進行了研究和改進，都從不同程度上改善了這個算法的推薦準確性。文獻［9］提出了一種復合指數(shù)函數(shù)作為評分權重的時間模型，在一定程度上改善了最終評分預測的結果，但是這個模型隨著時間的增長下降過快不符合人類的興趣遺忘規(guī)律。文獻［10］提出了一種Logistic時間函數(shù)和用戶特征相結合的方法，改善了推薦的準確度。由于這個函數(shù)值域最小在0.5，最大也不趨近于1，所以用它作為權重也不符合實際。同樣文獻［11］采用線性回歸方式作為時間模型，分別對相似度和預測評分公式進行改進，最終也在推薦效果上有所提升，不過根據(jù)艾賓浩斯遺忘曲線，顯然它也不符合。還有很多忽略用戶興趣遷移的改進［12-14］。

與上述改進方法不同，本文是根據(jù)艾賓浩斯遺忘曲線，提出一個指數(shù)時間模型，并通過權重α來控制這個模型，最后實驗會分組驗證這個超參數(shù)，選取一個最優(yōu)的模型作為用戶評分的權重。其次還會討論選擇怎么樣的規(guī)則方式來映射評分和共現(xiàn)值之間的關系，從而改善Salton相似度，減少預測評分的平均絕對誤差。

2 改進的基于用戶的協(xié)同過濾算法的研究

2.1 算法的提出

2.1.1 改進Salton相似度方法

傳統(tǒng)的協(xié)同過濾算法用式（4）所示的Salton相似度來計算目標用戶的最近鄰，在計算最近鄰時需要構建用戶u到用戶v的共現(xiàn)矩陣。假如數(shù)據(jù)庫中存有一張用戶看電影的評分，如表1所示。

表1 不同用戶對看過電影的評分（單位為分）

對于表1這份數(shù)據(jù)，其中數(shù)字表示用戶對電影的評分，NA表示用戶對某電影沒做評分通過Salton相似度計算各個用戶之間的相似度時，將會得到如表2所示的用戶之間的共現(xiàn)矩陣。

表2 不同用戶之間的共現(xiàn)矩陣（單位為個）

表2中數(shù)字表示的是用戶之間的共現(xiàn)值大小，NA表示相同用戶不做比較即共現(xiàn)值為空。從表1和表2之間的映射關系就可以得出：兩個用戶對某個電影無論評分多少，其共現(xiàn)值就為1。因此，這五個用戶通過Salton相似度計算得出的相似度是一樣的，也就是說用戶u5就可以把movieC推薦給用戶u1-u4。但是根據(jù)表1可以看出u1和u5根本不存在相似性，所以用傳統(tǒng)的Salton相似度直接計算用戶之間的相似性很粗糙。為了解決這種忽略用戶態(tài)度因素來計算共現(xiàn)值的方法，本文提出了一種決策樹模型來解決上述問題。首先分析一下表1，從表1可以看出當|rui-rvi|＜=1，其共現(xiàn)值可以為1；當時|rui-rvi|=2，可以分三種情況：當rui=5、rvi=3時，其共現(xiàn)值為δ∈{0.6，0.7，0.8}；當rui=4、rvi=2時，其共現(xiàn)值為μ∈{0.1，0.2，0.3}，當rui=3、rvi=1時，其共現(xiàn)值為0；當|rui-rvi|＞2時，此時這兩個用戶對某個電影的態(tài)度相差太大，其共現(xiàn)值可以認為為0。根據(jù)上述分析，首先可以統(tǒng)計分析用戶對電影的評分值構建簡單的決策樹，其次在每一條從根節(jié)點到葉節(jié)點的路徑上創(chuàng)建一個規(guī)則。對每一條路徑，從根節(jié)點到葉節(jié)點的父節(jié)點的所有條件用AND邏輯運算連接起來形成規(guī)則的條件部分（IF部分）。存放類預測的葉節(jié)點形成規(guī)則的后件（THEN部分）。本論文以用戶對電影的評分為例，可以抽取IF-THEN規(guī)則如下：

Rule1：IF|u-v|＜=1 THEN C=1

Rule2：IFu=5||v=3 THEN C=δ

Rule3：IFu=4||v=2 THEN C=μ

Rule4：IF 其他THEN C=0

根據(jù)上述的IF-THEN規(guī)則，可以構造出如圖1所示的決策樹。

圖1 用戶評分和共現(xiàn)值關系決策樹

2.1.2 改進的時間加權的預測評分模型

傳統(tǒng)的協(xié)同過濾算法在計算用戶的預測評分時并沒有對已產(chǎn)生行為物品的歷史評分做相應權重處理，也就是說沒有考慮時間對用戶興趣的影響。只有當用戶在同段時間或相近時間，才能有效的找鄰居，進行預測評分推薦，保持推薦的時效性。舉個簡單的例子，假如一個人在童年時期特別喜歡看兒童類電影，在成長過程中又很少看電影，有一天他去豆瓣看電影，豆瓣會給他推薦什么電影呢？毫無疑問大部分集中在兒童類電影，顯然這樣是不合理的。為了解決這個問題，必須把時間較久的歷史行為權重調(diào)低，通過一個動態(tài)的時間權重格式化歷史行為，使推薦結果的更能反映用戶的近期興趣，達到推薦的時效性。

事實上，人類的遺忘規(guī)律和用戶興趣偏移規(guī)律是相似的［15］，因此時間模型可以參考遺忘函數(shù)給出。德國的著名心理學家艾賓浩斯對記憶的遺忘規(guī)律做了深入研究，并且繪制出了著名的“艾賓浩斯遺忘曲線”。該曲線展示了人類記憶保留的非線性遞減的規(guī)律，本文受其啟發(fā)提出一個指數(shù)的時間模型，來反映用戶的興趣變化，此時間模型定義如下：

其中，t代表當前時刻，tumin表示用戶u對其評價過物品的最小時間，tumax表示用戶u對其評價過物品的最大時間，（7）式中減去1是為了避免評分權重為1，α∈（0，1］表示時間權重因子，α越大說明項目評分衰減速度越快，可以通過實驗擬定一個合適的值。

將這個時間模型引入到式（5）中，以提高推薦的時效性，使推薦結果更傾向于當前用戶的興趣。改進后的式子如下所示：

2.2 算法的過程描述

根據(jù)上述對Salton相似度的改進和利用時間加權對預測評分的改進，可以總結出改進的基于用戶的協(xié)同過濾算法（R_UserCF）過程如下：

算法 R_UserCF；

輸入 用戶集合U，物品集合I，鄰居個數(shù)K，推薦個數(shù)N，歷史行為Info；

輸出 預測評分矩陣M(U,I)。

Step1 根據(jù)Info信息得出用戶-項目的評分矩陣R(U,I)，再根據(jù)R(U,I)通過改進的Salton相似度計算出用戶u和U中其他用戶的共現(xiàn)值，最后根據(jù)用戶彼此之間的共現(xiàn)值就得到了用戶-用戶的共現(xiàn)矩陣Q(U,U)；

Step2 對每一個u∈U，通過Q(U,U)和改進的Salton相似度計算用戶u和U中其他用戶的相似度并寫入用戶相似度矩陣similar(u,v)；

Step3 對每一個u∈U，選取出與u相似度最高的K個用戶，組成最近鄰Neighbors(u,v,K)；

Step4 選出Neighbors(u,v,K)中所有產(chǎn)生行為的物品集合Iterms(i)，并在Iterms(i)中刪除目標用戶已經(jīng)產(chǎn)生行為物品；

Step5 對每個i∈Iterms(i)，通過最近鄰集合中的用戶i的評分，運用公式（9）計算預測值rui，并將rui更新到M(U,I)；

Step6 返回M(U,I)，算法完成。

3 實驗數(shù)據(jù)和結果分析

3.1 實驗數(shù)據(jù)和評價指標

本實驗使用由Grouplens提供的100K的MovieLens數(shù)據(jù)集。數(shù)據(jù)集包含了10萬條記錄，共943名用戶對1682部電影進行5個等級的評分，評分數(shù)值為1-5。其中1代表“poor”，5表示“perfect”，其他數(shù)據(jù)則表示中間值，他們代表了用戶對電影興趣的不同程度。在試驗中該數(shù)據(jù)集80%作為訓練數(shù)據(jù)集20%作為測試數(shù)據(jù)集。

預測準確度是用來衡量一個推薦系統(tǒng)推薦能力的重要指標，本論文采用平均絕對誤差（MSE）.假設原始評分集合為M={r1,r2,…,rn}，預測評分集合為N={p1,p2,…,pn}，則MAE的計算公式如下所示：

其中，N表示測試集中電影的總數(shù)。MAE的值越小，說明預測的準確率越高，產(chǎn)生的推薦效果越好，即推薦結果越準確。

3.2 實驗參數(shù)設定

3.2.1 選取最優(yōu)決策樹規(guī)則

根據(jù)前面的分析，需要對三個決策樹模型分別測試其平均絕對誤差，來選取最優(yōu)模型，此次試驗選取N=20，K=10，試驗結果如表3所示。

表3 不同模型及其MAE

其中A，B，C，D分別圖1中的根節(jié)點值，從上述表中數(shù)據(jù)MAE值可以得出第二個模型是最優(yōu)模型。

3.2.2 時間模型中的超參α

此試驗主要驗證時間權重因子在取何值時推薦效果達到最優(yōu)，此模型選取上述模型，試驗結果如圖2所示。

圖2 不同α所對應的平均絕對誤差

從上圖可以明顯的看出α為0.1時其平均絕對誤差最小，即選取此值推薦系統(tǒng)得到的推薦結果達到最優(yōu)。

3.3 實驗對比和實驗結果分析

通過上面對改進基于用戶的協(xié)同過濾算法（R_UserCF）參數(shù)的優(yōu)化，已經(jīng)能夠得出一個最優(yōu)模型，下面將在不同鄰居下用這個模型和傳統(tǒng)算法（UserCF）作對比，如圖3所示。

圖3 UserCF和R_UserCF算法的比較

從圖3可以看出改進的基于用戶的協(xié)同過濾算法在同等條件下平均絕對誤差都小于傳統(tǒng)的算法，可見改進的算法在推薦中更加高效實用。

4 結論

本文在計算相似度時增加了人們的態(tài)度即通過決策樹策略得出了評分和共現(xiàn)值的關系，并且為了應對用戶的興趣遷移問題提出了加權的時間模型，最后通過Movielens數(shù)據(jù)集驗證了改進的算法在整體上都優(yōu)于傳統(tǒng)的算法。但是該算法也有兩點不足之處，首先在整個算法過程中涉及到很多矩陣轉(zhuǎn)換問題以及又增加了一個時間維度，因此加大了內(nèi)存的開銷，增加了計算的時間。其次數(shù)據(jù)集采用的是電影領域，因此該算法在應用場合上有一定的局限性。接下來主要針對這兩點不足之處進行改進，嘗試加入聚類模型以及選取多個領域的數(shù)據(jù)集分別進行測試實驗。

［1］余力，劉魯，羅章華.我國電子商務推薦策略的比較分析［J］.系統(tǒng)工程理論與實踐，2004，24（8）：96-101.

［2］顧洪博，趙萬平.數(shù)據(jù)挖掘算法性能優(yōu)化的研究與應用［J］.長春理工大學學報：自然科學版，2010，33（1）：164-166，163.

［3］Linden G，Smith B，York J.Amazon.com Recommendations：item-to-item collaborativefiltering［J］.IEEE Internet Computing，2003（1）：76-80.

［4］邱寧佳，郭暢，楊華民，等.基于MapReduce編程模型的改進KNN分類算法研究［J］.長春理工大學學報：自然科學版，2017，40（1）：110-114.

［5］劉建國，周濤，王秉宏.個性化推薦系統(tǒng)的研究進展［J］.自然科學進展，2009，19（1）：1-15.

［6］Ricci F，Rokach L，Shapira B，et al.Recommender systems handbook［M］.New York：Springer，2011.

［7］黃武漢，孟祥武，王立才.移動通信網(wǎng)中基于用戶社會化關系挖掘的協(xié)同過濾算法［J］.電子與信息學報，2011，33（12）：3002-3007.

［8］范家兵，王鵬，周渭博，等.在推薦系統(tǒng)中利用時間因素的方法［J］.計算機應用，2015，35（5）：1324-1327.

［9］Lai W，Deng H.An improved collaborative filtering algorithm adapting to user interest changes［C］.Information Science and Service Science and Data Mining.IEEE，2012：598-602.

［10］趙文濤，成亞飛，王春春.基于Logistic時間函數(shù)和用戶特征的協(xié)同過濾算法［J］.計算機應用與軟件，2017，34（2）：285-289，312.

［11］鄭先榮，曹先彬.線性逐步遺忘協(xié)同過濾算法的研究［J］.計算機工程，2007，33（6）：72-73.

［12］Kharrat FB，Elkhleifi A，F(xiàn)aiz R.Improving collaborative filtering algorithms［C］.Proceedings of12th International Conference on Semantics，Knowledge and Grids，2016，36（5）：109-114.

［13］劉江東，梁剛，馮程，等.基于信息熵和時效性的協(xié)同過濾推薦［J］.計算機應用，2016，36（9）：2531-2534.

［14］張佳，林耀進，林夢雷等.基于信息熵的協(xié)同過濾算法［J］.山東大學學報：工學版，2016，46（2）：43-50.

［15］于洪，李轉(zhuǎn)云.基于遺忘曲線的協(xié)同過濾算法［J］.南京大學學報：自然科學版，2010，46（5）：520-527.