基于改進的BiasSVD和聚類用戶最近鄰的協同過濾混合推薦算法

劉 超 趙文靜 賈毓臻 蔡冠宇

1(江蘇大學電氣信息工程學院 江蘇 鎮江 212013) 2(鎮江市丹徒區科學技術局 江蘇 鎮江 212000)

0 引 言

隨著互聯網的快速發展，交互式網絡電視(Internet Protocol Television, IPTV)已成為電視業務中不可或缺的一部分。但是IPTV所提供的視頻資源數量龐大，如何幫助用戶從海量數據中快速獲取感興趣的內容是運營商現階段迫切需要解決的問題。雖然關鍵字搜索可以一定程度上緩解信息過載問題，卻不能滿足用戶的個性化需求。亞馬遜表示35%的銷售額來自推薦系統；谷歌新聞稱推薦系統使其文章閱讀量提高了38%[1]。

推薦系統可以根據家庭用戶的收視行為和流量特征，分析用戶的收視偏好，挖掘出用戶的潛在個性化需求，進一步提高用戶收視質量，為用戶提供高效、快速、優質的個性化推薦服務。但是用戶行為數據十分龐大并且每時每刻都在倍增，如何迅速定位用戶偏好，保證推薦時效性，亟待研究。

如今主流的推薦系統主要采用混合推薦方案。混合推薦能夠針對不同的實際情況，綜合各推薦系統的優缺點，將多種推薦方案進行有效結合。劉雨薇[2]提出了一種改進的基于用戶聚類的協同過濾算法，先將用戶根據OCEAN模型進行聚類，然后用基于BiasSVD的協同過濾方法在用戶所屬類簇內對用戶進行協同過濾。鄭丹等[3]提出了一種用戶聚類推薦算法，主要通過Weighted-Slope One來緩解數據稀疏性以及實時性差的問題。陳清浩[4]在SVD算法衍生的隱語義模型中，利用梯度下降法緩解了SVD算法中的可擴展性問題。

在個性化推薦系統中，對每個用戶最近鄰的查找都是基于大規模的用戶空間，而且當出現新用戶或者新物品時，傳統協同過濾推薦算法(Collaborative Filtering,CF)的計算量將會倍增，系統的時效性無法得到保證，推薦物品的可靠性和有效性降低。

本文針對IPTV業務的多樣性和復雜性問題，根據用戶收視偏好，提出基于改進的BiasSVD和聚類用戶最近鄰的協同過濾混合推薦算法，有效緩解用戶評分矩陣可擴展性問題，獲得更加精確的用戶預測評分，為用戶提供精準快速的針對性推薦服務。混合推薦算法基本框架流程如圖1所示。

圖1 混合推薦算法流程

1 改進的BiasSVD協同過濾推薦算法

1.1 BiasSVD

目前應用比較廣泛的矩陣分解方法有奇異值矩陣(SVD)分解[5]、FunkSVD分解[6]和BiasSVD分解[7]。

SVD分解的基本原理是將m×n階的矩陣A分解為U、S和V三個低秩矩陣，表示為:

Am×n=U×S×VT

(1)

奇異值具備衰減速度快的特性，一般情況下前10%甚至1%的奇異值之和就占據所有奇異值之和的99%以上[8]，所以選取前k個奇異值所構成的對角矩陣Sk與其對應的左右奇異向量來近似表示矩陣：

(2)

SVD算法通過選用元素值較大部分的奇異值來降維并進行奇異值分解，該算法存在的不足主要體現在兩個方面。其一，SVD分解要求矩陣不能是稀疏的，即矩陣的所有元素不能有空值，有空值時A不能直接進行SVD分解，而大多數情況下評分矩陣都是十分稀疏的，稀疏度在90%以上。其二，SVD算法的計算繁瑣，并且在高階且密集的矩陣上運算，將大大降低系統運行效率。對此，2006年Funk提出FunkSVD算法，下面對該算法做簡要介紹。

Am×n=PTQ

(3)

(4)

FunkSVD相對于傳統的奇異值分解進行了優化，但該方法得到的預測評分依然存在一定程度誤差，下面將其改進得到BiasSVD。

(5)

(6)

從而計算出誤差平方和：

(7)

根據梯度下降算法，令更新步長為γ，得到遞推公式，表示為:

(8)

1.2 改進的BiasSVD算法

(9)

式中：用戶u已完成評分的項目集合為Iu，瀏覽過但是未進行評分的項目集合為Nu;u對項目j(j∈Iu)的實際評分為αuj;xj是用戶u已完成評分的項目屬性;yj是沒有評過分的項目屬性。則誤差以及誤差平方和分別表示為:

(10)

(11)

則S在變量xj、yj、bu、bi和qi處的梯度分別表示為：

(12)

根據梯度下降算法，則推導出遞推計算式為：

bu-bj)]-λxj)

bu→bu+γ(eui-λbu)

bi→bi+γ(eui-λbi)

(13)

改進的BiasSVD算法雖然在預測過程利用視頻屬性來表示用戶屬性，降低存儲空間，但是預測精度上還是會有一定的偏差存在，因此通過找到目標用戶的最近鄰用戶，并計算其對視頻的預測評分以及真實評分之間的平均差值，從而調整目標用戶的預測評分。改進的BiasSVD算法預測用戶評分流程如下：

(1) 輸入訓練數據，包括商品分類標簽、關注度。初始化偏移向量bu、bi、隱因子矩陣qi，計算評分平均值μ。

(2) 初始化用戶的隱式反饋數據x、y。

(3) 按照改進BiasSVD公式預測用戶在此類視頻的關注度。

(4) 計算誤差值，按照改進BiasSVD公式迭代求解x、y、bu、bi、qi。

(5) 判斷是否存在下一條關注度記錄，存在則轉至步驟(3)，否則轉至步驟(7)。

(6) 判斷是否存在下一個用戶，如果存在則轉至步驟(2)，否則轉至步驟(7)。

(7) 判斷是否存在下一輪迭代，如果存在則轉至步驟(2)，否則輸出關注度預測矩陣，算法結束。

2 改進的聚類用戶最近鄰協同過濾推薦算法

2.1 k-means聚類

k-means聚類[9]過程的核心思想如下：首先在全部對象中任選k個作為聚類中心；然后通過用戶相似度sim(u,v)計算出用戶與每個聚類中心的相似度，并且將用戶分至所得值最大的簇內，直至全部劃分為止，得到k個簇群；再更新聚類中心并重復上述步驟，直到每個聚類中心在每次更新后幾乎不變為止；經過迭代得到最終的k個聚類簇群。

依據以上步驟后得到的各簇內，各用戶之間都擁有極大的相似度。聚類結束后，再根據公式計算出目標用戶和各聚類中心相似程度，目標用戶的鄰居集合就是相似度最高的簇中用戶集合。得到目標用戶與鄰居集合中用戶的相似度值，并且按照從大到小的順序排列，取得的前N個用戶即為最近鄰集合。

本文將選擇采用Pearson相關系數代表用戶相似度：

(14)

然而傳統的CF算法沒有將用戶興趣變化因素考慮其中。用戶對某類視頻的興趣熱度對用戶的行為有很大影響，綜合考慮該影響因素，將會很大程度提高推薦系統的預測準確度。

2.2 興趣熱度因子

用戶對某類視頻的興趣熱度會隨著一些外在或內在因素而產生改變，這就會很大地影響系統的后期預測。依據艾兵浩斯遺忘曲線[10]，關注某類視頻時的時間戳t與用戶的相關性函數定義為：

f(t)=1-μ(T-t)λT≥t

(15)

式中：μ和λ表示興趣熱度衰減因子;T表示當前時間。所以當t=T時，f(t)達到最大，表示此時用戶興趣熱度最大。

2.3 改進的聚類用戶最近鄰

本節在傳統k-means聚類算法的基礎上，引入權值函數f(t)，則式(14)可以優化為：

(16)

(17)

(1) 隨機選擇k個用戶作為聚類中心，按照式(16)得到用戶與k個中心的相似度，將該用戶劃分到相似度最高的簇中，經過不斷迭代聚類中心，最終所有用戶被分別歸類進k個簇中。

(2) 找到目標用戶所在的簇。

(3) 基于式(16)計算出目標用戶與其他用戶之間的相似度，將所有用戶中相似度最高的N個用戶指定為目標用戶最近鄰。

(4) 按照式(17)得出目標用戶對項目的預測評分。

(5) 向目標用戶提供TopN推薦。

3 混合推薦算法

本文綜合改進的BiasSVD和改進的聚類用戶最近鄰兩種算法，提出一種基于改進的BiasSVD和聚類用戶最近鄰的協同過濾混合算法。該混合算法的具體步驟如下：

(2) 根據改進的聚類算法流程中步驟(1)-步驟(3)確定目標用戶的最近鄰用戶user(u)。

上述混合推薦算法中偏差調整的計算式為：

(18)

(19)

4 實 驗

4.1 實驗環境和數據集

實驗環境：MATLAB R2016a，Windows 10 64位專業版，AMD A10-7890K Radeon R7。

數據集：為使得研究具有更高的參考價值，實驗采用由明尼蘇達大學收集的標準數據集作為數據輸入。該標準數據集取自MovieLens影評網站中近千名用戶針對1 682部電影的100 000次評分記錄，且每次評論后網站都會對用戶與項目的ID賬號、時間戳、用戶對項目的評分四個屬性進行保存，其中評分范圍是介于1～5之間的整數，分值的高低代表用戶對電影的愛好程度，分值越高表示用戶對此類視頻的興趣度越高[11]。測試集和訓練集的比值為2 ∶8。

在上述數據集基礎上可對用戶項目的評分矩陣稀疏度進行計算，具體如下：

可以看出該數據集稀疏度為93.70%，高于90%，由此可以得出該評分矩陣為稀疏矩陣。

4.2 實驗評價標準

本文采用平均絕對誤差(MAE)方法來驗證所提出的混合算法的準確性與有效性，該方法主要評估預測評分和實際評分間的差異[12]。假設目標用戶對N個項目進行預測評分，MAE計算式為：

(20)

式中：pi為預測評分;ri為實際評分。由式(20)可知MAE值越小，說明推薦的項目越貼近用戶需求，同時表明該推薦算法性能越優。

4.3 實驗結果

本文通過實驗1至實驗3來驗證混合算法的性能。實驗設置更新步長為0.95，即γ=0.95，迭代次數step=100，正則化參數λ=0.3。

實驗1：改進的混合推薦算法在不同特征矩陣維度下不同近鄰數k的MAE值比較。本實驗主要研究不同特征維度下的不同最近鄰居數對本文算法預測準確性的影響。實驗設置特征矩陣維度初始值為10，且每次增加的步長為10，直至矩陣維度達到50截止，選擇的近鄰數依次是k=10、k=20和k=30，實驗結果如圖2所示。

圖2 特征矩陣維度與近鄰數的關系

隨著k值的增加且特征矩陣維度不變的情況下，本文算法的MAE值減小，算法預測準確度提高。隨著矩陣維度的增加且k值不變的情況下，MAE值先降低，當矩陣維度擴大到一定范圍時，MAE沒有繼續下降，因為隨著矩陣維度的增加，該算法計算量增大，有效性有所降低。本次實驗結果表明，當矩陣維度為30時，并且k取30，MAE值最小，推薦質量最好。

實驗2：不同算法在不同特征矩陣維度下MAE值比較。本實驗主要是將BiasSVD算法和本文所提改進混合推薦算法進行不同矩陣維度下的MAE對比。基于實驗1，取k=30作為本文算法的目標用戶的最近鄰數，特征矩陣維度取值范圍從10到50，每次增加10。結果如圖3所示。

圖3 不同算法在不同矩陣維度下MAE值比較

當混合推薦算法的最鄰近k取30時，在不同的矩陣維度下，BiasSVD算法的MAE值均高于本文算法，可見本文算法能夠緩解矩陣可擴展性問題。

實驗3：不同算法在不同近鄰數k下MAE值比較。本實驗主要是將傳統的CF算法與本文算法進行不同近鄰數k下的MAE值對比。基于實驗1，取30作為本文算法的特征矩陣維度，采樣密度為原數據的90%，k取值范圍從5到35，每次增加5，則實驗結果如圖4所示。

圖4 不同算法在不同近鄰數k下MAE值比較

可以看出，當特征矩陣的維度為30時，相比于傳統的CF算法，改進的混合推薦算法擁有更小的MAE值。實驗表明，本文算法的準確度得到較好的改善。

實驗4：不同混合推薦算法在相同稀疏度下的MAE值比較。本實驗將本文算法與基于SVD和用戶聚類的協同過濾算法研究[11]中的混合推薦算法進行對比。采樣密度為原數據的80%，實驗結果如圖5所示。

圖5 不同混合推薦算法在不同k值下的MAE比較

可以看出當最近鄰居數小于15時，本文算法的MAE值較大，當最近鄰居數大于25時，本文算法的MAE值小于基于SVD和用戶聚類的協同過濾算法研究[11]中的混合推薦算法。

5 結 語

為了對用戶做更精準的視頻推薦，本文提出一種基于改進的BiasSVD算法和聚類用戶最近鄰的協同過濾混合推薦算法。根據實驗結果可以得出，本文算法可以改善矩陣的可擴展性問題，并能提高評分預測的準確度。盡管本文的研究已經取得了一定階段性成果，但是對于處理數據的速度還有所欠缺，所以下一步將針對如何基于大規模用戶評分矩陣來快速高效地預測用戶評分問題，進行更深入研究。