動態信任衰減和信息匹配的混合推薦算法

任靜霞，武志峰

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

0 引 言

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

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

1 傳統算法

1.1 基于相似度的協同過濾算法

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

1.2 基于模型的協同過濾算法

2 DTDIM-CF算法

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

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

2.1 User-DTDCF算法

2.1.1 用戶的近鄰選擇

在傳統User-based CF的鄰居選擇中，首先考察目標用戶與用戶備選鄰居的共同評分數，通過已評分物品挖掘用戶潛在興趣，用戶間公共評分物品越多，二者越可能有共同興趣，則用戶關系越密切。反之，若用戶間公共評分物品數較少，在根據已有評分分析用戶時，認為用戶間關聯較少，關系較疏遠。故在鄰居選擇前添加最低公共評分限制，不滿足公共評分數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 基于用戶的主觀評分規范化

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

(4)

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

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

(5)

(6)

2.2 Item-DTDCF算法

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

2.3 冷啟動解決

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

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

2.4 加權混合策略

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

圖2 DTDIM-CF算法流程

一般情況下基于用戶、物品的協同過濾算法推薦準確度較高、可解釋性較強，但在數據稀疏情況下效果不佳，不同環境下表現也不同。DTDIM-CF算法根據算法預測評分與歷史數據的不匹配度動態調整各算法權重，若某一算法原始評分存在而預測評分為空，則認為該算法在該情況下的效果較差，適當降低該算法權重，若存在多個合理推薦值，則優先選擇匹配度較高算法進行預測。定義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中空值個數，b為矩陣R2中空值個數。首先判斷歷史數據與User-DTDCF、Item-DTDCF算法所得預測評分空值情況，若歷史數據為空，而以上兩種算法均無預測評分，則使用SVD算法進行評分預測；若歷史數據為空，而以上兩種算法僅有一種算法有評分，則使用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)；反之，若歷史數據不為空，而以上兩種算法均無預測評分，則使用SVD算法進行評分預測；若歷史數據不為空，而以上兩種算法僅有一種算法有評分，則選擇SVD算法與該算法中與歷史評分相比較接近的評分值作為預測評分；若兩種算法均有評分，則使用三種算法中與歷史評分值較接近的評分值作為預測評分。三種算法涉及權重因子時，總評分為r4ui=w1r1ui+w2r2ui+w3r3ui，由DTDIM-CF算法加權混合后得到的最終評分預測矩陣R4[m×n]中評分值為r4ui。算法加權混合流程如圖3所示。

3 實驗分析

3.1 數據集

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

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

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值選取

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

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

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

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

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

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

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

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

3.3.5 傳統User-based CF和User-DTDCF、DTDIM-CF算法比較

通過在傳統User-based CF算法的基礎上添加公共評分數限制并引入時間信息為目標用戶選擇最佳鄰居，考察由于時間信息造成的信任衰減，以及不同鄰居對目標用戶影響不同，動態調整鄰居選擇，進而進行評分預測，得到User-DTDCF算法。在此基礎上，將改進后的User-DTDCF、Item-DTDCF和SVD算法根據信息匹配度進行混合推薦，得到DTDIM-CF算法。設置對比實驗，比較當鄰居數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 傳統的User-based CF、改進的User-DADCF 和DTDIM-CF算法的RMSE、MAE比較

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

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

3.3.6 傳統Item-based CF、Item-DTDCF、DTDIM-CF算法比較

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

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

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

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

3.3.7 混合算法有效性驗證

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

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

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

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

4 結束語

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