任靜霞，武志峰

(天津職業(yè)技術師范大學 信息技術工程學院，天津 300222)

0 引 言

推薦系統(tǒng)[1]是大數(shù)據(jù)背景下商品飛速增長、信息爆炸所萌生的個性化定制服務，它在用戶和物品數(shù)量劇增的情況下，根據(jù)歷史數(shù)據(jù)為用戶和物品間建立連接關系，進而預測未來的連接，主要解決評分預測和行為預測問題[2]，即預測連接強度和是否會產(chǎn)生連接問題。推薦系統(tǒng)作為一種信息過濾系統(tǒng)能夠幫助使用者快速、準確地找到有用的信息，發(fā)現(xiàn)自己的潛在興趣和需求，為企業(yè)帶來利益的同時，也為用戶提供便捷的服務，得到了各大電子商務網(wǎng)站的廣泛應用。

從20世紀90年代開始，推薦系統(tǒng)持續(xù)受到社會關注，各種推薦算法層出不窮，卻各有利弊。如協(xié)同過濾推薦算法[3]具有較好的推薦效果，但不適用于稀疏矩陣也無法處理新用戶或新物品出現(xiàn)時的冷啟動問題，而矩陣分解算法[4]能夠解決冷啟動問題，但可解釋性卻較差等，研究者們始終致力于追求更高質(zhì)量、更具擴展性的推薦算法。賈彭慧等人[5]通過用戶之間的交叉性、信任性以及趨同性因子加權來挑選近鄰；原福永等人[6]通過劃分時間序列，考察不同時間段用戶的點擊率來為用戶找到近鄰；劉珊珊[7]通過用戶訪問同一項目的次數(shù)確定用戶偏好并推薦相似項目；孫光福等人[8]通過基于時序行為的消費網(wǎng)絡圖來找到近鄰；肖春景等人[9]采用時序信息通過隨機游走進行近鄰選擇；鄧存彬等人[10]通過改進SVD++算法[11]劃分時間段來考察用戶、物品偏置實現(xiàn)動態(tài)協(xié)同過濾；郝雅嫻等人[12]將用戶近鄰與項目近鄰評分信息融合為一個評分矩陣，挖掘目標用戶對目標項目的評分信息。文中提出了一種基于動態(tài)信任衰減和信息匹配的混合推薦算法，考察共同評分數(shù)和時間因子調(diào)整鄰居選擇機制，引入信任衰減重新定義近鄰影響從而改進傳統(tǒng)協(xié)同過濾算法，根據(jù)算法的初步推薦和歷史信息的不匹配度，將改進后的動態(tài)信任協(xié)同過濾算法與傳統(tǒng)矩陣分解算法按照特定規(guī)則進行混合，采用二次矩陣分解解決冷啟動問題，算法推薦準確度得以提高，可擴展性、可解釋性也得以加強。

1 傳統(tǒng)算法

1.1 基于相似度的協(xié)同過濾算法

基于相似度的協(xié)同過濾算法(collaborative filtering，CF)，其原理是興趣相似的用戶傾向于喜歡相同的物品，同一用戶對同類型物品的喜好程度類似，用戶的行為和打分都是可以體現(xiàn)用戶偏好的有效數(shù)據(jù)。根據(jù)鄰居類型，基于相似度的協(xié)同過濾算法可分為基于用戶的協(xié)同過濾(User-based CF)和基于物品的協(xié)同過濾(Item-based CF)。User-based CF利用已收集到的用戶偏好找到用戶的K近鄰，根據(jù)近鄰用戶的打分權重計算目標用戶的可能打分。Item-based CF利用已收集到的用戶偏好找到物品的K近鄰物品，根據(jù)用戶給近鄰物品的打分權重計算用戶對目標物品的可能打分。

1.2 基于模型的協(xié)同過濾算法

2 DTDIM-CF算法

傳統(tǒng)協(xié)同過濾算法忽略了不同鄰居影響程度和用戶興趣漂移，文中提出的DTDIM-CF算法通過在鄰居選擇前添加最低公共評分限制，并在剩下的備選鄰居中引入時間因子調(diào)整近鄰選擇，再根據(jù)信任衰減重新計算不同鄰居造成的近鄰影響，得到改進后基于用戶的動態(tài)信任衰減的協(xié)同過濾算法(User-DTDCF)和基于物品的動態(tài)信任衰減的協(xié)同過濾算法(Item-DTDCF)。其中考慮到用戶間不同評分習慣造成的評分差異，使用了一種可適用于不同評分區(qū)間的評分規(guī)范化方法計算皮爾遜相關系數(shù)以完成相似度計算，采用矩陣分解算法處理協(xié)同過濾算法中新用戶、新物品出現(xiàn)時存在的冷啟動問題。就傳統(tǒng)單一算法適應性不強但各具優(yōu)勢，DTDIM-CF算法根據(jù)所得預測評分與歷史數(shù)據(jù)的不匹配度將改進后的User-DTDCF、Item-DTDCF和SVD算法進行不同情況下的動態(tài)加權混合。

算法分為四個Part，Part1對User-based CF算法改進，得到User-DTDCF算法，Part2對Item-based CF算法改進，得到Item-DTDCF算法，Part3介紹利用SVD算法特性解決冷啟動問題，Part4介紹算法中User-DTDCF、Item-DTDCF和SVD的動態(tài)加權混合策略。

2.1 User-DTDCF算法

2.1.1 用戶的近鄰選擇

在傳統(tǒng)User-based CF的鄰居選擇中，首先考察目標用戶與用戶備選鄰居的共同評分數(shù)，通過已評分物品挖掘用戶潛在興趣，用戶間公共評分物品越多，二者越可能有共同興趣，則用戶關系越密切。反之，若用戶間公共評分物品數(shù)較少，在根據(jù)已有評分分析用戶時，認為用戶間關聯(lián)較少，關系較疏遠。故在鄰居選擇前添加最低公共評分限制，不滿足公共評分數(shù)num的備選鄰居被淘汰。在剩余的候選鄰居中考察時間因子，選取與該用戶共同評分時間較接近的前Nn位用戶作為其最終近鄰，定義tuv為目標用戶u對物品i的評分時間,tvi為近鄰用戶v對物品i的評分時間,tuivi為目標用戶u和近鄰用戶v對物品i的評分時間間隔，tuv為目標用戶u和近鄰用戶v的近鄰選擇評分時間差，令tuivi=|tui-tvi|，近鄰選擇公式如下：

(1)

選擇tuv值最小的前Nn位用戶作為最終近鄰用戶，得到基于num值近鄰用戶選擇的num-User-based CF算法。

2.1.2 用戶的近鄰影響機制

(2)

(3)

2.1.3 基于用戶的主觀評分規(guī)范化

定義改進后的User-DTDCF算法中，近鄰用戶v對目標用戶u的影響因子為fv，則所得預測評分如下：

(4)

式中，根據(jù)不同用戶打分習慣不同，在計算預測評分時，對fv做如下調(diào)整。

對于原始評分矩陣中每一個rui值，其評分區(qū)間為[rmin,rmax]，則目標用戶u與近鄰用戶v間的相關系數(shù)corruv計算如下：

(5)

(6)

2.2 Item-DTDCF算法

在傳統(tǒng)Item-based CF算法的基礎上，對物品近鄰重新選擇、物品近鄰機制重新定義并進行基于物品的主觀評分規(guī)范化得到Item-DTDCF算法，改進方法同2.1節(jié)中User-DTDCF算法生成。

2.3 冷啟動解決

文中改進后的算法User-DTDCF和Item-DTDCF仍存在冷啟動問題[14]，故在算法開始前先進行判斷，若不存在新用戶、新物品，則直接用DTDIM-CF算法進行預測，反之，若存在，則利用SVD算法特性，當新用戶或新物品出現(xiàn)時，提取該新數(shù)據(jù)，將剩余數(shù)據(jù)作為新的數(shù)據(jù)集，運用DTDIM-CF算法進行評分預測，得到評分矩陣后，添加已提取數(shù)據(jù)到該矩陣中，再使用SVD算法進行二次矩陣分解得到最終預測結果，進而解決算法冷啟動問題。冷啟動解決流程如圖1所示。

圖1 DTDIM-CF算法冷啟動解決流程

2.4 加權混合策略

針對User-based CF、Item-based CF算法基于已有信息為用戶進行推薦，冷啟動問題無法解決，SVD算法解釋性不強等，DTDIM-CF算法充分利用各算法優(yōu)勢將三種算法進行動態(tài)加權混合。混合策略為：首先將初始用戶-物品評分矩陣R[m×n]使用User-DTDCF、Item-DTDCF和SVD算法分別進行評分預測，得到預測矩陣R1[m×n]、R2[m×n]、R3[m×n]，再根據(jù)所得的預測評分與已有歷史數(shù)據(jù)的不匹配度將三種算法進行不同情況下的動態(tài)加權混合，其中，若存在冷啟動問題，則使用SVD算法進行二次矩陣分解，最終得到預測評分矩陣R4[m×n]。DTDIM-CF算法流程如圖2所示。

圖2 DTDIM-CF算法流程

一般情況下基于用戶、物品的協(xié)同過濾算法推薦準確度較高、可解釋性較強，但在數(shù)據(jù)稀疏情況下效果不佳，不同環(huán)境下表現(xiàn)也不同。DTDIM-CF算法根據(jù)算法預測評分與歷史數(shù)據(jù)的不匹配度動態(tài)調(diào)整各算法權重，若某一算法原始評分存在而預測評分為空，則認為該算法在該情況下的效果較差，適當降低該算法權重，若存在多個合理推薦值，則優(yōu)先選擇匹配度較高算法進行預測。定義DTDIM-CF推薦算法中，初始用戶-物品評分矩陣R[m×n]中，用戶u對物品i評分值為rui，通過User-DTDCF、Item-DTDCF、SVD算法進行預測得到的評分矩陣R1[m×n]、R2[m×n]、R3[m×n]中預測評分值分別為r1ui、r2ui、r3ui，len=∑items，a為矩陣R1中空值個數(shù)，b為矩陣R2中空值個數(shù)。首先判斷歷史數(shù)據(jù)與User-DTDCF、Item-DTDCF算法所得預測評分空值情況，若歷史數(shù)據(jù)為空，而以上兩種算法均無預測評分，則使用SVD算法進行評分預測；若歷史數(shù)據(jù)為空，而以上兩種算法僅有一種算法有評分，則使用SVD算法與該算法進行特定加權混合得到預測評分。User-DTDCF算法推薦為空時，三種算法權重因子分別為w1=0、w2=1/2(1-b/len)、w3=1/2(1+b/len)，Item-DTDCF算法推薦為空時，三種算法權重因子分別為w1=1/2(1-a/len)、w2=0、w3=1/2(1+b/len)；若User-DTDCF、Item-DTDCF算法均有評分，則使用三種算法進行特定加權混合作為預測評分，權重因子分別為w1=1/4(1-a/len)、w2=1/4(1-b/len)、w3=1/4(2+(a+b)/len)；反之，若歷史數(shù)據(jù)不為空，而以上兩種算法均無預測評分，則使用SVD算法進行評分預測；若歷史數(shù)據(jù)不為空，而以上兩種算法僅有一種算法有評分，則選擇SVD算法與該算法中與歷史評分相比較接近的評分值作為預測評分；若兩種算法均有評分，則使用三種算法中與歷史評分值較接近的評分值作為預測評分。三種算法涉及權重因子時，總評分為r4ui=w1r1ui+w2r2ui+w3r3ui，由DTDIM-CF算法加權混合后得到的最終評分預測矩陣R4[m×n]中評分值為r4ui。算法加權混合流程如圖3所示。

3 實驗分析

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

文中使用的數(shù)據(jù)集為GroupLens提供的MovieLens，實驗采用ml-100k的數(shù)據(jù)集，數(shù)據(jù)格式如表1所示，其中包含用戶-電影(943*1 682)，共100 000條評分，分值為0-5分，每位用戶至少有20條打分記錄，數(shù)據(jù)集稀疏度達0.936 9，評分時間段為1997/9/20 11:5:10-1998/4/23 7:10:38，換算為時間戳為874724710-893286638。

表1 ml-100k數(shù)據(jù)集(部分數(shù)據(jù)截取)

3.2 評價標準

文中涉及的所有實驗均使用均方根誤差(root mean square error，RMSE)和平均絕對誤差(mean absolute error，MAE)作為評價指標。

圖3 DTDIM-CF算法加權混合流程

RMSE計算公式如下：

(7)

MAE計算公式如下：

(8)

3.3 實驗結果

3.3.1 num-User-based CF中num值選取

通過在傳統(tǒng)User-based CF算法的基礎上添加公共評分數(shù)限制，并考察時間因子進行用戶鄰居選擇，對算法進行改進。實驗比較當鄰居數(shù)Nn改變時，num-User-based CF算法在公共評分數(shù)num值不同的情況下，通過時間因子進行鄰居選擇得到的推薦結果。

實驗得到，隨著鄰居數(shù)Nn的增加，改進后的num-User-based CF算法誤差逐漸減小，當Nn值取40時總體誤差最小，算法中num值的選取對算法最終推薦效果起到了積極作用，使得根據(jù)時間因子進行鄰居選擇后算法誤差明顯小于傳統(tǒng)User-based CF算法，隨著num值增大，總體呈現(xiàn)先減小后增大的趨勢，故調(diào)整公共評分數(shù)后通過時間因子選擇鄰居可使算法的誤差減小，且鄰居選擇更加合理有效。當num=40時，RMSE和MAE的誤差值均取到較小值，故將此num值作為最佳公共評分數(shù)。

3.3.2 用戶的近鄰選擇User-DTDCF中t0值選取

在上一節(jié)中對傳統(tǒng)User-based CF添加了公共評分數(shù)限制并通過時間因子選擇鄰居得到num-User-based CF算法的基礎上進一步改進，考察由于時間信息造成的用戶信任衰減，從而調(diào)整鄰居影響得到User-DTDCF算法。實驗比較信任衰減未發(fā)生的時間段t0在不同值下的算法推薦效果，為User-DTDCF算法找到合適的t0值，取num=40，t0取值范圍為[0,t]，當鄰居數(shù)Nn改變時，調(diào)整t0/t的值以獲得較小的誤差值。

實驗得到，隨著鄰居數(shù)Nn的增加，改進后的算法誤差逐漸減小，當Nn值取30時總體誤差最小，在上一節(jié)對算法改進的基礎上通過信任衰減定義鄰居影響，進而進行預測得到的User-DTDCF算法推薦誤差明顯小于num-User-based CF算法，隨著t0/t值的增大，誤差逐漸增大，當t0/t=0%時，RMSE和MAE誤差值均最小，此時，算法效果最佳。根據(jù)前文假設，在某固定時間范圍[0,t0]內(nèi)，認為評分影響不發(fā)生改變，而最佳t0值為0，由此可得出結論，User-based CF鄰居影響中信任衰減總是存在，且時刻都在衰減。

3.3.3 num-Item-based CF中num'值選取

通過在傳統(tǒng)Item-based CF算法的基礎上添加公共評分數(shù)限制，并考察時間因子進行物品的鄰居選擇，對算法進行改進，實驗比較當鄰居數(shù)Nn改變時，num-Item-based CF算法在公共評分數(shù)num'值不同的情況下，通過時間因子進行鄰居選擇得到的推薦結果。

實驗得到，改進后的num-Item-based CF算法的RMSE和MAE誤差值較傳統(tǒng)Item-based CF算法明顯減小，算法中num'值的選取對算法最終推薦效果起到了積極作用，使得根據(jù)時間因子進行鄰居選擇后算法誤差明顯小于傳統(tǒng)Item-based CF算法，隨著num'值增大，誤差出現(xiàn)波動，總體呈現(xiàn)先減小后緩慢增大的趨勢，故調(diào)整公共評分數(shù)后通過時間因子選擇鄰居可使算法的誤差減小，且鄰居選擇更加合理有效。當num'=40時，RMSE和MAE的誤差值均取到較小值，故將此num'值作為最佳公共評分數(shù)。

3.3.5 傳統(tǒng)User-based CF和User-DTDCF、DTDIM-CF算法比較

通過在傳統(tǒng)User-based CF算法的基礎上添加公共評分數(shù)限制并引入時間信息為目標用戶選擇最佳鄰居，考察由于時間信息造成的信任衰減，以及不同鄰居對目標用戶影響不同，動態(tài)調(diào)整鄰居選擇，進而進行評分預測，得到User-DTDCF算法。在此基礎上，將改進后的User-DTDCF、Item-DTDCF和SVD算法根據(jù)信息匹配度進行混合推薦，得到DTDIM-CF算法。設置對比實驗，比較當鄰居數(shù)Nn改變時，三種算法的推薦效果。本實驗中User-DTDCF、DTDIM-CF算法涉及到的變量采用值如表2所示(實驗3.3.1-3.3.4)。實驗得到的RMSE、MAE誤差值如圖4所示[15]。

表2 實驗3.3.5變量采用值(實驗3.3.1-3.3.4)

圖4 傳統(tǒng)的User-based CF、改進的User-DADCF 和DTDIM-CF算法的RMSE、MAE比較

由圖4得，隨著鄰居數(shù)Nn的增加，User-based CF、User-DTDCF、DTDIM-CF算法誤差RMSE和MAE均逐漸降低，三種算法進行比較發(fā)現(xiàn)，相較User-based CF，User-DTDCF算法誤差有所降低，添加公共評分數(shù)限制并通過時間因子選擇后獲取的鄰居關系更緊密，考慮信任衰減動態(tài)調(diào)整用戶的鄰居影響，對于用戶評分預測更具有參考價值，算法可解釋性更強，算法推薦效果有所提升。

與前兩個算法相比，DTDIM-CF算法誤差RMSE和MAE均大幅度下降，將改進的User-DTDCF、Item-DTDCF算法與SVD算法進行混合，充分利用各算法優(yōu)勢，彌補傳統(tǒng)User-based CF算法冷啟動、可擴展性差等問題，得到的混合算法DTDIM-CF能有效解決和改善算法不足，并取得較好的推薦效果。

3.3.6 傳統(tǒng)Item-based CF、Item-DTDCF、DTDIM-CF算法比較

通過在傳統(tǒng)Item-based CF算法的基礎上添加公共評分數(shù)限制并引入時間信息為目標物品選擇最佳鄰居，考察由于時間信息造成的信任衰減，以及不同鄰居對目標物品影響不同，動態(tài)調(diào)整鄰居選擇，進而進行評分預測，得到Item-DTDCF算法。在此基礎上，將改進后的User-DTDCF、Item-DTDCF和SVD算法根據(jù)信息匹配度進行混合推薦，得到DTDIM-CF算法。設置對比實驗，比較當鄰居數(shù)Nn改變時，三種算法推薦效果。本實驗中Item-DTDCF、DTDIM-CF算法涉及到的變量采用值如表2所示。實驗得到的RMSE、MAE誤差值如圖5所示。

圖5 傳統(tǒng)的Item-based CF、改進的Item-DADCF 和DTDIM-CF算法的RMSE、MAE比較

由圖5得，隨著鄰居數(shù)Nn的增加，Item-based CF、Item-DTDCF、DTDIM-CF算法誤差RMSE和MAE均逐漸降低，三種算法進行比較發(fā)現(xiàn)，相較Item-based CF，Item-DTDCF算法誤差大幅度降低，添加公共評分數(shù)限制并通過時間因子選擇后獲取的鄰居關系更緊密，考慮信任衰減動態(tài)調(diào)整物品的鄰居影響，對于用戶評分預測更具有參考價值，算法可解釋性更強，算法推薦效果有所提升。

與前兩個算法相比，DTDIM-CF算法誤差RMSE和MAE均大幅度下降，將改進的User-DTDCF、Item-DTDCF算法與SVD算法進行混合，充分利用各算法優(yōu)勢，彌補傳統(tǒng)Item-based CF算法冷啟動、可擴展性差、有時推薦效果不佳等問題，得到的混合算法DTDIM-CF能有效解決和改善算法不足，并取得較好的推薦效果。

3.3.7 混合算法有效性驗證

針對User-DTDCF、Item-DTDCF算法冷啟動問題無法解決且稀疏矩陣中推薦效果差，而SVD算法解釋性不強等問題，將User-DTDCF、Item-DTDCF和SVD算法根據(jù)推薦信息匹配度進行混合，得到DTDIM-CF混合算法。設置對比實驗驗證混合算法的有效性，使用DTDIM-CF算法混合策略對傳統(tǒng)的User-based CF、Item-based CF和SVD算法進行加權混合，將得到的預測結果(tradition CF)與DTDIM-CF算法作比較，同時與傳統(tǒng)的User-based CF、Item-based CF作比較，隨著近鄰數(shù)Nn的改變，各算法RMSE和MAE值的比較結果分別如圖6和圖7所示，本實驗中DTDIM-CF算法涉及到的變量如表2所示。

由圖6、圖7得，隨著Nn值的增大，傳統(tǒng)的User-based CF、Item-based CF以及DTDIM-CF算法誤差明顯減小，混合后的tradition CF誤差緩慢減小，故各算法隨著近鄰數(shù)增大推薦效果變好。相較傳統(tǒng)的User-based CF、Item-based CF，混合后的tradition CF算法誤差RMSE和MAE值均減小，幾組算法比較中，DTDIM-CF算法誤差始終最小，推薦效果最好，且本實驗通過控制變量，使用傳統(tǒng)User-based CF、Item-based CF算法與SVD算法進行混合后得到的混合算法較傳統(tǒng)算法推薦誤差均有所降低，故文中混合算法的加權混合策略即使作用于傳統(tǒng)算法對于改進推薦效果也有明顯作用。

圖6 傳統(tǒng)的User-based CF、Item-based CF、混合后 的tradition CF、DTDIM-CF算法的RMSE比較

圖7 傳統(tǒng)的User-based CF、Item-based CF、混合后 的tradition CF、DTDIM-CF算法的MAE比較

4 結束語

文中提出了一種基于動態(tài)信任衰減和信息匹配的混合推薦算法，對傳統(tǒng)協(xié)同過濾算法進行了改進，通過添加近鄰公共評分數(shù)限制并引入時間因子調(diào)整近鄰選擇，考察隨著時間動態(tài)發(fā)生的信任衰減重新定義了近鄰影響機制，使得推薦更加合理有效。提出一種評分規(guī)范化方法規(guī)范預測評分，充分發(fā)揮各算法優(yōu)勢，根據(jù)算法預測與歷史數(shù)據(jù)匹配度進行動態(tài)加權混合推薦，算法可擴展性得以提高，可解釋性加強，通過二次矩陣分解，解決了冷啟動問題，稀疏矩陣中也有較好的推薦效果。在GroupLens提供的MovieLens數(shù)據(jù)集上進行實驗，結果表明算法誤差明顯降低，可解釋性、可擴展性都有所提高，推薦效果得以提升?；趧討B(tài)信任衰減的方法可有效改善協(xié)同過濾算法性能，并應用于基于協(xié)同方法的多數(shù)混合算法中，未來研究對該方法進行調(diào)整以合理提升基于協(xié)同過濾的混合算法性能和利用率。