基于改進(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)容是運(yùn)營商現(xiàn)階段迫切需要解決的問題。雖然關(guān)鍵字搜索可以一定程度上緩解信息過載問題，卻不能滿足用戶的個(gè)性化需求。亞馬遜表示35%的銷售額來自推薦系統(tǒng)；谷歌新聞稱推薦系統(tǒng)使其文章閱讀量提高了38%[1]。

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

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

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

本文針對(duì)IPTV業(yè)務(wù)的多樣性和復(fù)雜性問題，根據(jù)用戶收視偏好，提出基于改進(jìn)的BiasSVD和聚類用戶最近鄰的協(xié)同過濾混合推薦算法，有效緩解用戶評(píng)分矩陣可擴(kuò)展性問題，獲得更加精確的用戶預(yù)測(cè)評(píng)分，為用戶提供精準(zhǔn)快速的針對(duì)性推薦服務(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三個(gè)低秩矩陣，表示為:

Am×n=U×S×VT

(1)

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

(2)

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

Am×n=PTQ

(3)

(4)

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

(5)

(6)

從而計(jì)算出誤差平方和：

(7)

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

(8)

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

(9)

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

(10)

(11)

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

(12)

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

bu-bj)]-λxj)

bu→bu+γ(eui-λbu)

bi→bi+γ(eui-λbi)

(13)

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

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

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

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

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

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

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

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

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

2.1 k-means聚類

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

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

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

(14)

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

2.2 興趣熱度因子

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

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

(15)

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

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

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

(16)

(17)

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

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

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

(4) 按照式(17)得出目標(biāo)用戶對(duì)項(xiàng)目的預(yù)測(cè)評(píng)分。

(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)整的計(jì)算式為：

(18)

(19)

4 實(shí) 驗(yàn)

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

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

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

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

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

4.2 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

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

(20)

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

4.3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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