基于改進(jìn)的BiasSVD和聚類用戶最近鄰的協(xié)同過濾混合推薦算法

劉 超 趙文靜 賈毓臻 蔡冠宇

1(江蘇大學(xué)電氣信息工程學(xué)院 江蘇 鎮(zhèn)江 212013) 2(鎮(zhèn)江市丹徒區(qū)科學(xué)技術(shù)局 江蘇 鎮(zhèn)江 212000)

0 引 言

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

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

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

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

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

圖1 混合推薦算法流程

1 改進(jìn)的BiasSVD協(xié)同過濾推薦算法

1.1 BiasSVD

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

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

Am×n=U×S×VT

(1)

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

(2)

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

Am×n=PTQ

(3)

(4)

FunkSVD相對于傳統(tǒng)的奇異值分解進(jìn)行了優(yōu)化，但該方法得到的預(yù)測評分依然存在一定程度誤差，下面將其改進(jìn)得到BiasSVD。

(5)

(6)

從而計算出誤差平方和：

(7)

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

(8)

1.2 改進(jìn)的BiasSVD算法

(9)

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

(10)

(11)

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

(12)

根據(jù)梯度下降算法，則推導(dǎo)出遞推計算式為：

bu-bj)]-λxj)

bu→bu+γ(eui-λbu)

bi→bi+γ(eui-λbi)

(13)

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

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

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

(3) 按照改進(jìn)BiasSVD公式預(yù)測用戶在此類視頻的關(guān)注度。

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

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

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

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

2 改進(jìn)的聚類用戶最近鄰協(xié)同過濾推薦算法

2.1 k-means聚類

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

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

本文將選擇采用Pearson相關(guān)系數(shù)代表用戶相似度：

(14)

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

2.2 興趣熱度因子

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

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

(15)

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

2.3 改進(jìn)的聚類用戶最近鄰

本節(jié)在傳統(tǒng)k-means聚類算法的基礎(chǔ)上，引入權(quán)值函數(shù)f(t)，則式(14)可以優(yōu)化為：

(16)

(17)

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

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

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

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

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

3 混合推薦算法

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

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

上述混合推薦算法中偏差調(diào)整的計算式為：

(18)

(19)

4 實 驗

4.1 實驗環(huán)境和數(shù)據(jù)集

實驗環(huán)境：MATLAB R2016a，Windows 10 64位專業(yè)版，AMD A10-7890K Radeon R7。

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

在上述數(shù)據(jù)集基礎(chǔ)上可對用戶項目的評分矩陣稀疏度進(jìn)行計算，具體如下：

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

4.2 實驗評價標(biāo)準(zhǔn)

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

(20)

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

4.3 實驗結(jié)果

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

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

圖2 特征矩陣維度與近鄰數(shù)的關(guān)系

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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