基于聚類層次模型的視頻推薦算法

金 亮,于 炯,,楊興耀,魯 亮,王躍飛,國(guó)冰磊,廖 彬

(1.新疆大學(xué) 軟件學(xué)院,烏魯木齊 830008; 2.新疆大學(xué) 信息科學(xué)與工程學(xué)院,烏魯木齊 830046;3.新疆財(cái)經(jīng)大學(xué) 統(tǒng)計(jì)與信息學(xué)院,烏魯木齊 830012) (*通信作者電子郵箱yujiong@xju.edu.cn)

基于聚類層次模型的視頻推薦算法

金 亮1,于 炯1,2*,楊興耀1,魯 亮2,王躍飛2,國(guó)冰磊2,廖 彬3

(1.新疆大學(xué) 軟件學(xué)院,烏魯木齊 830008; 2.新疆大學(xué) 信息科學(xué)與工程學(xué)院,烏魯木齊 830046;3.新疆財(cái)經(jīng)大學(xué) 統(tǒng)計(jì)與信息學(xué)院,烏魯木齊 830012) (*通信作者電子郵箱yujiong@xju.edu.cn)

目前推薦系統(tǒng)存在評(píng)論數(shù)據(jù)稀疏、冷啟動(dòng)和用戶體驗(yàn)度低等問題,為了提高推薦系統(tǒng)的性能和進(jìn)一步改善用戶體驗(yàn),提出基于聚類層次模型的視頻推薦算法。首先,從相關(guān)用戶方面著手,通過近鄰傳播(AP)聚類分析得到相似用戶,從而收集相似用戶中的歷史網(wǎng)絡(luò)視頻數(shù)據(jù),進(jìn)而形成視頻推薦集合；其次,利用用戶行為的歷史數(shù)據(jù)計(jì)算出用戶對(duì)視頻的喜好值,再把視頻的喜好值轉(zhuǎn)換成視頻的標(biāo)簽權(quán)重；最后,通過層次分析模型算出視頻推薦集合中用戶喜好視頻的排序,產(chǎn)生推薦列表。基于MovieLens Latest Dataset和YouTube視頻評(píng)論文本數(shù)據(jù)集,實(shí)驗(yàn)結(jié)果表明所提算法在均方根誤差和決策精度方面均表現(xiàn)出良好的性能。

視頻推薦;稀疏性;冷啟動(dòng);層次模型;聚類分析

0 引言

伴隨著網(wǎng)絡(luò)費(fèi)用的下降以及4G網(wǎng)絡(luò)的完善和5G網(wǎng)絡(luò)的到來,視頻數(shù)量將變得越來越龐大,其網(wǎng)絡(luò)視頻數(shù)據(jù)如表1所示,如何在大量的視頻中推薦出用戶喜歡的視頻是一個(gè)巨大的挑戰(zhàn)。就目前而言,傳統(tǒng)的推薦系統(tǒng)主要分為基于內(nèi)容推薦[1]、協(xié)同過濾推薦[2-3]和混合過濾推薦[4]。基于內(nèi)容推薦是通過機(jī)器學(xué)習(xí)的方法從訓(xùn)練集中提取出內(nèi)容特征,再與用戶的興趣特征相比通過內(nèi)容特征與興趣特征的相似度來產(chǎn)生推薦。這其中存在內(nèi)容難以提取有意義的特征和無法得到其他用戶的判斷情況等問題?；陉P(guān)聯(lián)規(guī)則推薦則是以項(xiàng)目的相關(guān)性為基礎(chǔ),通過大量的數(shù)據(jù)統(tǒng)計(jì)找出項(xiàng)目的相關(guān)性,但是關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)耗時(shí)和項(xiàng)目的同義性問題有待解決?；谛в猛扑]需要為每個(gè)用戶創(chuàng)建一個(gè)有效函數(shù),這樣存在用戶有效函數(shù)的創(chuàng)建問題和屬性重疊問題。協(xié)同過濾推薦是通過用戶評(píng)價(jià)的方式來建立用戶和項(xiàng)目之間的聯(lián)系,把用戶評(píng)價(jià)轉(zhuǎn)換成用戶對(duì)項(xiàng)目的喜好程度來預(yù)測(cè)用戶對(duì)項(xiàng)目的喜好從而形成推薦。但是后來研究發(fā)現(xiàn)僅憑這樣產(chǎn)生的推薦結(jié)果很難反映出用戶的喜好[5]。

表1 中國(guó)網(wǎng)絡(luò)視頻用戶規(guī)模和使用率

為此,本文提出基于聚類層次模型的視頻推薦算法(Video Recommendation algorithm Based on Clustering and Hierarchical model, VRBCH),首先通過相關(guān)用戶屬性標(biāo)簽的近鄰傳播(Affiliation Propagation, AP)聚類[6]得到與推薦用戶相似的其他用戶集合；然后通過其他用戶的歷史數(shù)據(jù)獲得視頻推薦集合；最后通過被推薦用戶歷史數(shù)據(jù)信息分析得出視頻分類標(biāo)簽權(quán)重,利用視頻推薦集合和視頻分類標(biāo)簽權(quán)重算出視頻推薦集合中視頻的順序,推薦給用戶。本文通過對(duì)推薦用戶歷史數(shù)據(jù)進(jìn)行訓(xùn)練,調(diào)整PageRank[7]模型參數(shù),通過反復(fù)迭代得到用戶歷史視頻的重要性,然后通過視頻重要性確定視頻中分類標(biāo)簽的權(quán)重。PageRank模型偏向于歷史數(shù)據(jù),然而人的興趣愛好是通過實(shí)踐逐漸產(chǎn)生的,短時(shí)間內(nèi)不會(huì)出現(xiàn)興趣愛好大幅度改變問題,所以得到的興趣愛好數(shù)據(jù)無需頻繁更新。本文通過推薦用戶行為算出視頻分類標(biāo)簽權(quán)重,降低了用戶自己定義視頻分類標(biāo)簽權(quán)重的誤差。另外,在分析視頻集合中的某個(gè)視頻傾向于某個(gè)分類標(biāo)簽時(shí)采用視頻專家的建議,避免了用戶自己分析時(shí)存在不確定誤差。

1 相關(guān)工作

當(dāng)前,推薦系統(tǒng)研究最多的是協(xié)同推薦模型,其原理是相似的用戶都會(huì)有共同點(diǎn),不相似的用戶各有各的不同。例如,相似的兩個(gè)人他們會(huì)在某一觀點(diǎn)、某一愛好或某些事物都有相似或相同的興趣愛好。協(xié)同過濾推薦主要包括基于模型的協(xié)同過濾推薦和基于近鄰的協(xié)同過濾推薦。

楊興耀等[8]利用用戶評(píng)分的奇異性和擴(kuò)散性對(duì)原有用戶相似性模型進(jìn)行改進(jìn)、擴(kuò)展,找出與用戶相似的近鄰集合Ku；利用評(píng)分預(yù)測(cè)函數(shù),通過近鄰用戶對(duì)項(xiàng)目的評(píng)分計(jì)算出用戶對(duì)項(xiàng)目的預(yù)測(cè)評(píng)分從而得到用戶的推薦集合。尹路通等[9]通過用戶評(píng)論利用情感詞分析技術(shù),計(jì)算出用戶的興趣傾向度,再利用興趣傾向度建立用戶虛擬評(píng)分矩陣,來彌補(bǔ)現(xiàn)實(shí)評(píng)分的不足；同時(shí)建立用戶興趣模型,利用隱語義模型把傳統(tǒng)的二元推薦擴(kuò)充為三元推薦來預(yù)測(cè)用戶的喜好產(chǎn)生推薦。孫光福等[10]通過用戶消費(fèi)的先后時(shí)間順序得到用戶與產(chǎn)品、用戶與用戶、產(chǎn)品與產(chǎn)品的影響關(guān)系,來構(gòu)建用戶與產(chǎn)品、用戶與用戶、產(chǎn)品與產(chǎn)品的結(jié)構(gòu)關(guān)系，并以此為基礎(chǔ)計(jì)算出它們的相似度，再利用概率分解模型來重構(gòu)評(píng)分矩陣,利用評(píng)分矩陣產(chǎn)生相應(yīng)的推薦。張付志等[11]利用核主成分分析法提取用戶評(píng)分矩陣的非線性特征,最大限度地保留了用戶和項(xiàng)目的特征信息；最后，還引入了Cauchy加權(quán)M-估計(jì)量函數(shù),雖然損失了部分精度，但是在滿足需求下提高了算法的魯棒性。張燕平等[12]利用歷史記錄的評(píng)分矩陣得到用戶信譽(yù),對(duì)于信譽(yù)低的用戶通過抑制其推薦影響來達(dá)到降低精度影響。胡勛等[13]引入圖像檢索中常用的推土機(jī)距離計(jì)算方法,融入項(xiàng)目特征計(jì)算出用戶的相似性，降低了協(xié)同推薦算法中稀疏性帶來的挑戰(zhàn),避免了評(píng)分矩陣的稀疏性對(duì)用戶相似性的影響；此外還引入了社會(huì)用戶關(guān)系計(jì)算信任權(quán)重得到近鄰用戶，提高了混合推薦的精度。郭磊等[14]從推薦對(duì)象間的關(guān)聯(lián)關(guān)系出發(fā),融合了用戶的社會(huì)關(guān)系、項(xiàng)目間關(guān)系和評(píng)分信息三種不同類型的信息,利用共享特征空間的方法對(duì)推薦結(jié)果進(jìn)行優(yōu)化,起到了優(yōu)化推薦結(jié)果的作用。陳克寒等[15]利用兩階段用戶聚類的方法先從稀疏數(shù)據(jù)中聚類出密集子集形成核心聚類,然后對(duì)其提取用戶特征再進(jìn)行聚類，最后將聚類結(jié)果用于推薦。

這些算法的優(yōu)缺點(diǎn)如表2所示,它們都是在用戶相似度和評(píng)分上直接操作來產(chǎn)生推薦,并未對(duì)推薦結(jié)果進(jìn)行排序處理,在一定程度上限制了算法性能的進(jìn)一步提升。好的推薦排序模型必將獲得好的推薦結(jié)果[16],好的推薦結(jié)果必將產(chǎn)生好的用戶體驗(yàn),達(dá)到用戶對(duì)推薦產(chǎn)生依賴的效果。利用推薦用戶歷史數(shù)據(jù)和瀏覽行為把視頻喜好程度分解成視頻喜好標(biāo)簽權(quán)重，然后再結(jié)合視頻推薦集合算出用戶對(duì)視頻的喜好值,形成推薦。

表2 協(xié)同過濾推薦算法的優(yōu)缺點(diǎn)

2 VRBCH算法詳述

總體上說,VRBCH大致可分為以下三個(gè)階段:對(duì)相關(guān)用戶進(jìn)行AP聚類分析、將推薦用戶歷史數(shù)據(jù)行為轉(zhuǎn)換成視頻喜好標(biāo)簽權(quán)值和用層次排序模型產(chǎn)生推薦。

2.1 聚類分析

對(duì)視頻用戶的聚類算法有很多,比如k-均值、模糊集等。本文通過AP聚類分析[6]找出相似用戶進(jìn)而找到他們喜愛的視頻,是因?yàn)锳P聚類不需要指定聚類數(shù)目,與其他聚類算法相比誤差平方和較低。本文通過分析用戶的性別、年齡、學(xué)歷、住址(手機(jī)號(hào)碼)、興趣愛好等用戶屬性找出相似用戶,現(xiàn)設(shè)有n個(gè)用戶,每個(gè)用戶有p個(gè)屬性,則用戶矩陣為:

其中:xij(i=1,2,…,n;j=1,2,…,p)為第i個(gè)用戶第j個(gè)屬性數(shù)據(jù)。

第1步 先對(duì)用戶數(shù)據(jù)進(jìn)行歸一化處理。本文通過式(1)把數(shù)據(jù)壓縮到[0,1]閉區(qū)間上：

(1)

第2步 構(gòu)建相似度矩陣S。

第3步 利用式(2)～(4)迭代更新吸引度矩陣R和歸屬度矩陣a。計(jì)算公式如下:

(2)

如果i≠k時(shí):

(3)

(4)

式(2)是用相似度矩陣S=[s(i,k)]和歸屬度矩陣a=[a(i,k)]更新吸引度矩陣R=[r(i,k)]；式(3)是用吸引度矩陣R=[r(i,k)]更新歸屬度矩陣a=[a(i,k)]。其中S[s(i,k)]是點(diǎn)i到k的相似度。

第4步 判斷是否達(dá)到預(yù)設(shè)迭代次數(shù)：如果已達(dá)到迭代次數(shù)，則進(jìn)行第5步。如果沒有達(dá)到迭代次數(shù)，則判斷a(i,i)+r(i,i)是否大于0，若小于0，則重復(fù)第3～4步；若大于0，則進(jìn)行第5步

第5步 迭代更新結(jié)束選擇聚類中心，并分配聚類輸出聚類集合P。

其算法如下。

算法1 相似用戶AP聚類的核心算法。

輸入 相似用戶集合C，阻尼系數(shù)λ。

輸出 相似用戶集合P。

BEGIN

1)

初始化a(i,j)=r(i,j)=0;

2)

建立相似矩陣S;

3)

計(jì)算吸引度矩陣:

4)

5)

計(jì)算歸屬度矩陣:

6)

ifi≠k

7)

a(i,k)←

8)

else

9)

10)

ifa(i,i)+r(i,i)gt;0

11)

選擇聚類中心;

12)

else

13)

返回3)重新計(jì)算;

END

2.2 層次排序模型

層次排序模型[17]是為了解決視頻排序過程中用戶對(duì)一些視頻標(biāo)簽無法準(zhǔn)確估量和量化的分析模型,用于解決用戶難以準(zhǔn)確定位自身需求和興趣權(quán)重的問題。其本質(zhì)是根據(jù)具體需求決定分類標(biāo)簽的影響權(quán)重從而求出最優(yōu)解。首先將決策問題分解成多個(gè)層次,如圖1所示,再構(gòu)造成對(duì)比較矩陣,計(jì)算權(quán)重向量并作一致性檢驗(yàn),最后得出最優(yōu)解。

圖1 選擇視頻的層次結(jié)構(gòu)

層次分析往往將一些難以量化的分類標(biāo)簽通過人的主觀判斷實(shí)現(xiàn)量化處理。但是在人的主觀判斷中往往存在誤差,因此本文引入PageRank[7]排序模型,計(jì)算出用戶歷史視頻的重要性值,構(gòu)建成對(duì)比較矩陣計(jì)算出分類標(biāo)簽的權(quán)重,最終從視頻推薦集合中找出最優(yōu)視頻集合。

對(duì)于成對(duì)比較矩陣的構(gòu)建,假設(shè)歷史數(shù)據(jù)中有n個(gè)視頻,每個(gè)視頻相當(dāng)于一個(gè)節(jié)點(diǎn),根據(jù)用戶行為信息建立視頻與視頻之間的互連模型,如圖2所示。則視頻的排序值(Rank值)的計(jì)算公式[18]為:

(5)

其中:R(pi)表示第i個(gè)視頻的排序值;d是阻尼因子,1-d是隨機(jī)瀏覽新的視頻的概率;L(pj)是視頻pj的鏈出視頻數(shù);r是歷史數(shù)據(jù)中相同視頻重復(fù)的個(gè)數(shù)。

圖2 用戶行為網(wǎng)絡(luò)圖

在n個(gè)歷史視頻中找出分類標(biāo)簽,例如視頻的地域、年份、動(dòng)作、科幻、戰(zhàn)爭(zhēng)、主演、導(dǎo)演等為w1,w2,…,wm,利用式(5)算出每個(gè)視頻的Rank值并賦給對(duì)應(yīng)視頻下的分類標(biāo)簽,若不同視頻中含有相同分類標(biāo)簽則取該相同分類標(biāo)簽中的最大值。

定義1 設(shè)pi視頻對(duì)應(yīng)的Rank值為ri,其含有的分類標(biāo)簽為w1,w2,…,wi,則其分類標(biāo)簽對(duì)應(yīng)的值為w1=w2=…=wi=ri;pj視頻對(duì)應(yīng)的Rank值為rj,其含有的分類標(biāo)簽為w1,w2,…,wj則其分類標(biāo)簽對(duì)應(yīng)的值為w1=w2=…=wj=rj;如果rigt;rj則w1=w2=w3=ri。

定義2 比較m個(gè)視頻標(biāo)簽對(duì)上一層視頻標(biāo)簽的影響用aij表示,則aij=wi/wj,其尺度含義如表3所示。

定義3 由于式(5)計(jì)算出視頻重要值為非整數(shù),為了減少計(jì)算量和計(jì)算誤差，本文在四舍五入的基礎(chǔ)上進(jìn)行同步取整。例如,wi=4.3,wj=5.3,aij=wi/wj=4/5;wi=4.6,wj=5.6,aij=wi/wj=5/6;wi=4.3,wj=5.6,aij=wi/wj=5/6;wi=4.6,wj=5.3,aij=wi/wj=5/6。

表3 1～9尺度aij的含義

在視頻標(biāo)簽權(quán)重的計(jì)算過程中,通過上面規(guī)則構(gòu)建成對(duì)比較矩陣:

本文采用冪法逐步迭代對(duì)成對(duì)比較矩陣進(jìn)行特征值和特征向量的求解并作一致性檢驗(yàn)。

首先,選取n維歸一化初始向量w(0);計(jì)算出w(k+1)=Aw(k),k=0,1,…;然后歸一化w(k+1)。即:

(6)

如果|wi(k+1)-wi(k)|lt;ε(i=1,2,…,n)時(shí),則為所求的特征向量;否則返回w(k+1)=Aw(k)。其中ε為預(yù)先給定的常數(shù)精度。

最后計(jì)算出最大特征根:

(7)

為了確定特征向量是否適合為分類標(biāo)簽的權(quán)重,必須對(duì)特征向量w作一致性檢驗(yàn)。其一致性比率CR計(jì)算公式如下:

CR=CI/RIlt;0.1

(8)

其中:CI為一致性指標(biāo)。CI=0時(shí),A為一致陣。CI越大A越偏離一致陣,其公式如式(9)所示。RI為不同的n利用正互反矩陣算出CI的平均值作為隨機(jī)一致性指標(biāo),如表4所示。

(9)

表4 隨機(jī)一致性指標(biāo)RI的數(shù)值

2.3 推薦流程

視頻推薦流程步驟如下。

輸入 相關(guān)用戶數(shù)據(jù)集合C。

輸出 針對(duì)用戶集合中用戶所觀看視頻的推薦集合I。

1)收集所有相關(guān)用戶、標(biāo)注屬性,利用AP聚類得到相似用戶。

2)收集所有相似用戶觀看的歷史視頻數(shù)據(jù)形成預(yù)推薦集合,并按照觀看時(shí)長(zhǎng)和視頻出現(xiàn)的時(shí)間進(jìn)行整理。

3)判斷推薦用戶是否是新用戶,如果是則按照第2)步整理的視頻進(jìn)行推薦。

4)利用推薦用戶觀看的歷史數(shù)據(jù)進(jìn)行PageRank排序分析,通過用戶行為形成網(wǎng)絡(luò)圖計(jì)算出用戶對(duì)歷史視頻的喜愛程度。

5)分解歷史視頻數(shù)據(jù)的受喜愛標(biāo)簽,構(gòu)建標(biāo)簽成對(duì)比較矩陣。

6)計(jì)算標(biāo)簽權(quán)重,利用第2)步得到的視頻預(yù)推薦集合進(jìn)行計(jì)算形成推薦集合。

3 實(shí)驗(yàn)評(píng)估與分析

實(shí)驗(yàn)部分,本文先選定所用數(shù)據(jù)集,介紹評(píng)定標(biāo)準(zhǔn),然后用現(xiàn)有數(shù)據(jù)模擬現(xiàn)實(shí)環(huán)境,再利用歷史數(shù)據(jù)優(yōu)化參數(shù)。最后介紹VRBCH算法與其他算法的對(duì)比實(shí)驗(yàn)并作相應(yīng)的分析。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

為了綜合評(píng)估算法性能,實(shí)驗(yàn)采用MovieLens Latest Datasets和YouTube視頻評(píng)論文本[19]數(shù)據(jù)集,基本參數(shù)如表5所示。

表5 評(píng)分?jǐn)?shù)據(jù)集的基本參數(shù)

3.2 評(píng)估標(biāo)準(zhǔn)

為了更好地驗(yàn)證VRBCH算法的性能,本文采用均方根誤差(Root Mean Square Error, RMSE)、F-measure來作為評(píng)價(jià)標(biāo)準(zhǔn)。RMSE通過計(jì)算預(yù)測(cè)的用戶行為和實(shí)際的用戶行為之間的偏差來衡量預(yù)測(cè)的準(zhǔn)確性。假設(shè)對(duì)n個(gè)用戶行為進(jìn)行預(yù)測(cè),得到的預(yù)測(cè)結(jié)果集合為P={p1,p2,…,pn},對(duì)應(yīng)的實(shí)際用戶行為集合為Ur={r1,r2,…,rn}，則算法RMSE表示為:

(10)

本文的準(zhǔn)確率采用準(zhǔn)確率和召回率的加權(quán)調(diào)和平均即F-measure作為衡量標(biāo)準(zhǔn),其定義為:

(11)

(12)

(13)

其中:precision為準(zhǔn)確率;recall為召回率;P為預(yù)測(cè)結(jié)果集合;Ur為實(shí)際用戶行為集合。

另外,確保最大限度地利用數(shù)據(jù)集,實(shí)驗(yàn)采用十折交叉驗(yàn)證法(10-floder cross validation),實(shí)驗(yàn)中將選中的數(shù)據(jù)分成10份,輪流將其中9份作為訓(xùn)練集,1份作為驗(yàn)證集。10次結(jié)果的正確率的平均值作為對(duì)算法精度的估計(jì)。

3.3 推薦算法參數(shù)優(yōu)化

就聚類算法和排序模型而言,恰當(dāng)?shù)膮?shù)選擇對(duì)推薦算法的性能有很大影響。AP聚類中的所有數(shù)據(jù)初始相似度的p值決定聚類數(shù)目的多少,p值越大輸出聚類數(shù)目越多,p值越小輸出聚類數(shù)目越少,所以p值為所有數(shù)據(jù)相似度的均值。

(14)

其中：s(i,k)是數(shù)據(jù)相似度。

AP聚類中阻尼系數(shù)λ的大小決定著聚類過程中迭代的次數(shù):λ減小,迭代次數(shù)減少但容易引起震蕩;λ增大迭代次數(shù)增加,增加系統(tǒng)時(shí)間開銷。

從圖3所示的λ系數(shù)對(duì)比圖可以看出:當(dāng)λ=0.6,0.7時(shí),其震蕩效果相似,即λgt;0.6時(shí)其震蕩效果相似,所以本文為了降低時(shí)間開銷λ取0.6。

圖3 不同λ取值時(shí)系統(tǒng)的震蕩情況

對(duì)于Pagerank模型來說,阻尼因子d的正確選擇不僅影響著Pagerank模型的冪法收斂速度還影響著排序的公正性,其d值減小雖然提高了Pagerank的收斂速度,但是降低了其排序的公正性。所以本文取不同的d值分別測(cè)試對(duì)推薦結(jié)果的影響,其結(jié)果如圖4所示。

圖4 不同d值對(duì)推薦模型的影響

從圖4可以看出在PageRank模型中,阻尼系數(shù)d取0.78時(shí)VRBCH推薦算法的RMSE值取得最小,且F-measure值取得最大,此時(shí)推薦效果較為理想,下節(jié)在比較不同推薦算法的性能優(yōu)劣時(shí)均采用此設(shè)置。

3.4 實(shí)驗(yàn)結(jié)果比較

為了精準(zhǔn)評(píng)估本文所提出的VRBCH算法性能,本節(jié)選取基于時(shí)序行為的矩陣分解(Sequential Matrix Factorization, SequentialMF)算法[10]、基于用戶的協(xié)同過濾(User Collaboration Filter, UserCF)算法、不確定近鄰的協(xié)同過濾(Uncertain Neighbors’ Collaborative Filtering, UNCF)算法[20]作對(duì)比實(shí)驗(yàn)。其中,SequentialMF中,在關(guān)系影響參數(shù)λ=5,數(shù)據(jù)稀疏性為99%的情況下通過用戶觀看視頻的時(shí)間構(gòu)建用戶關(guān)系網(wǎng)絡(luò),利用網(wǎng)絡(luò)圖進(jìn)行關(guān)系計(jì)算,再通過概率矩陣分解模型挖掘出推薦視頻。在UserCF中,把數(shù)據(jù)集分成測(cè)試集和訓(xùn)練集,利用訓(xùn)練集計(jì)算出K=10個(gè)用戶的相似性獲得相似性矩陣usersim,再計(jì)算出這10個(gè)鄰居對(duì)視頻的興趣集合,推薦20個(gè)視頻給用戶。在UNCF中,利用視頻或用戶的相似性計(jì)算產(chǎn)生近鄰因子,通過近鄰因子在調(diào)和參數(shù)Ф=20的情況下計(jì)算視頻的預(yù)測(cè)評(píng)分產(chǎn)生推薦。

通過不同數(shù)據(jù)集數(shù)據(jù)量的百分比,利用RMSE和F-measure評(píng)價(jià)指標(biāo)進(jìn)行實(shí)驗(yàn),percentage值取區(qū)間[10,90]，實(shí)驗(yàn)結(jié)果如圖5～6所示。

圖5 不同推薦算法的RMSE性能比較

在圖5中，隨著實(shí)驗(yàn)數(shù)據(jù)量百分比的不斷增加RMSE整體呈下降趨勢(shì),當(dāng)實(shí)驗(yàn)數(shù)據(jù)量達(dá)到50%以后下降趨勢(shì)緩慢,數(shù)據(jù)量達(dá)80%后其RMSE性能基本不變。從圖5中可以看出,VRBCH算法與SequentialMF、UserCF、UNCF算法的RMSE性能相比,雖然前期有較大波動(dòng)但最終結(jié)果較為理想,前期波動(dòng)主要由于數(shù)據(jù)量過小而誤差較大。從圖6可以看出各算法F-measure性能隨著數(shù)據(jù)集百分比的遞增均呈上升趨勢(shì),其中VRBCH算法的F-measure性能最高。當(dāng)數(shù)據(jù)量達(dá)到80%時(shí)VRBCH算法性能上升趨勢(shì)平穩(wěn),所以VRBCH算法在不同數(shù)據(jù)量情況下的F-measure性能仍較為理想。在圖6中UNCF算法在數(shù)據(jù)量在30%到35%之間上升較緩，因?yàn)閅ouTube視頻評(píng)論文本評(píng)分稀疏度為98.37%,數(shù)據(jù)量較少，存在實(shí)驗(yàn)誤差。相比較而言,前期由于數(shù)據(jù)量過少，SequentialMF、UserCF、UNCF算法對(duì)數(shù)據(jù)稀疏性問題要求較高,所以其F-measure性能比VRBCH性能低。

由于VRBCH算法中提出層次排序概念,通過用戶自己的行為來決定用戶自己的興趣愛好值,避免視頻關(guān)注點(diǎn)存在模糊多變的性質(zhì)從而影響用戶興趣愛好評(píng)估的準(zhǔn)確性，所以VRBCH算法在視頻推薦上擁有良好的推薦性能。

圖6 不同推薦算法的F-measure性能比較

4 結(jié)語

推薦系統(tǒng)是數(shù)據(jù)挖掘領(lǐng)域中一大熱點(diǎn),本文改變了傳統(tǒng)推薦算法利用項(xiàng)目評(píng)分來計(jì)算相似用戶的方式，改為利用被推薦用戶瀏覽視頻的行為計(jì)算出用戶對(duì)歷史數(shù)據(jù)中視頻的喜好程度,通過被推薦用戶的歷史數(shù)據(jù)找出用戶對(duì)視頻的喜好標(biāo)簽,從而成功地實(shí)現(xiàn)用戶行為和喜好標(biāo)簽權(quán)重的轉(zhuǎn)換,避免了傳統(tǒng)層次分析中用戶自定義權(quán)重值。另外,考慮到用戶可能是新用戶,沒有歷史數(shù)據(jù),本研究從相似用戶中找出最新最受喜愛的視頻推薦給用戶,有效地避免了冷啟動(dòng)問題。最后形成的推薦集合中采用排序的形式,提高了用戶的體驗(yàn)度。實(shí)驗(yàn)結(jié)果表明,本模型在RMSE、F-measure這兩個(gè)方面的性能獲得提高,基于MovieLens Latest Datasets和YouTube 視頻評(píng)論文本數(shù)據(jù)集與其他模型進(jìn)行實(shí)驗(yàn)對(duì)比,結(jié)果表明本文模型取得了良好的推薦效果。

值得注意的是,本文算法還有許多要改進(jìn)的方面：1)聚類時(shí)計(jì)算量問題,本文僅對(duì)少量的低維數(shù)據(jù)進(jìn)行聚類,在大數(shù)據(jù)環(huán)境中則需要引入分布式計(jì)算方法,下一步會(huì)考慮在Spark平臺(tái)下進(jìn)行聚類嘗試；2)在用戶聚類過程中為了提高聚類效果,在數(shù)據(jù)歸一化過程中對(duì)某些用戶屬性進(jìn)行人為處理,例如用戶性別,未來應(yīng)從分類的角度出發(fā)提高分類精度,由于可以離線計(jì)算,節(jié)約大量實(shí)時(shí)計(jì)算資源；3)在排序模型中針對(duì)歷史數(shù)據(jù)處理粗糙,降低了推薦精度和用戶體驗(yàn)度；4)在構(gòu)建視頻層對(duì)標(biāo)簽層影響過程中由于是非專業(yè)人士操作導(dǎo)致推薦結(jié)果誤差較大。下一步計(jì)劃利用機(jī)器學(xué)習(xí)內(nèi)容構(gòu)建自我學(xué)習(xí)的排序算法,充分利用歷史數(shù)據(jù)從而為推薦模型的實(shí)際應(yīng)用起到促進(jìn)作用。

References)

[1] ARORA G, KUMAR A, DEVRE GS, et al. Movie recommendation system based on users’ similarity[J]. International Journal of Computer Science and Mobile Computing, 2014, 3(4): 765-770.

[2] DESHPANDE M, KARYPIS G. Item-based top-Nrecommendation algorithms[J]. ACM Transactions on Information Systems, 2014, 22(1): 143-177.

[3] CAI Y, LEUNG H F, LI Q, et al. Typicality-based collaborative filtering recommendation[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(3): 766-779.

[4] KAGITA V R, PUJARI A K, PADMANABHAN V. Virtual user approach for group recommendation systems using precedence relations[J]. Information Sciences, 2015, 294(294): 15-30.

[5] KARATZOGLOU A, BALTRUNAS L, SHI Y. Learning to rank for recommender systems[C]// RecSys 2013: Proceedings of the 7th ACM Conference on Recommender Systems. New York: ACM, 2013: 493-494.

[6] FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972-976.

[7] PAGE L, BRIN S, MOTWANI R, et al. The PageRank citation ranking: bringing order to the Web [EB/OL]. [2017- 01- 10]. http://ilpubs.stanford.edu: 8090/422/1/1999-66.pdf.

[8] 楊興耀, 于炯, 吐爾根·依布拉音, 等. 融合奇異性和擴(kuò)散過程的協(xié)同過濾模型[J]. 軟件學(xué)報(bào), 2013, 24(8): 1868-1884. (YANG X Y, YU J, IBRAHIM T, et al. Collaborative filtering model fusing singularity and diffusion process[J]. Journal of Software, 2013, 24(8): 1868-1884.)

[9] 尹路通, 于炯, 魯亮, 等. 融合評(píng)論分析和隱語義模型的視頻推薦算法[J]. 計(jì)算機(jī)應(yīng)用, 2015, 35(11): 3247-3251. (YIN L T, YU J, LU L, et al. Video recommendation algorithm fusing comment analysis and latent factor model[J]. Journal of Computer Applications, 2015, 35(11): 3247-3251.)

[10] 孫光福, 吳樂, 劉淇, 等. 基于時(shí)序行為的協(xié)同過濾推薦算法[J]. 軟件學(xué)報(bào), 2013, 24(11): 2721-2733. (SUN G F, WU L, LIU Q, et al. Recommendations based on collaborative filtering by exploiting sequential behaviors[J]. Journal of Software, 2013, 24(11): 2721-2733.)

[11] 張付志, 孫雙俠, 伊偉華. 基于非線性特征和Cauchy加權(quán)M-估計(jì)量的魯棒推薦算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2015, 40(6): 1453-1469. (ZHANG F Z, SUN S X, YI W H. Robust recommendation algorithm based on nonlinear characteristics and Cauchy weighted M-estimator[J]. Chinese Journal of Computers, 2015, 40(6): 1453-1469.)

[12] 張燕平, 張順, 錢付蘭, 等. 基于用戶聲譽(yù)的魯棒協(xié)同推薦算法[J]. 自動(dòng)化學(xué)報(bào), 2015, 41(5): 1004-1012. (ZHANG Y P, ZHANG S, QIAN F L, et al. Robust collaborative recommendation algorithm based on user’s reputation[J]. Acta Automatica Sinica, 2015, 41(5): 1004-1012.)[13] 胡勛, 孟祥武, 張玉潔, 等. 一種融合項(xiàng)目特征和移動(dòng)用戶信任關(guān)系的推薦算法[J]. 軟件學(xué)報(bào), 2014, 25(8): 1817-1830. (HU X, MENG X W, ZHANG Y J, et al. Recommendation algorithm combing item features and trust relationship of mobile users[J]. Journal of Software, 2014, 25(8): 1817-1830.)

[14] 郭磊, 馬軍, 陳竹敏, 等. 一種結(jié)合推薦對(duì)象關(guān)聯(lián)關(guān)系的社會(huì)化推薦算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(1): 219-228. (GUO L, MA J, CHEN Z M, et al. Incorporation item relations for social recommendation[J]. Chinese Journal of Computers, 2014, 37(1): 219-228.)

[15] 陳克寒, 韓盼盼, 吳健. 基于用戶聚類的異構(gòu)社交網(wǎng)絡(luò)推薦算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(2): 349-359. (CHEN K H, HAN P P, WU J. User clustering based social network recommendation[J]. Chinese Journal of Computers, 2013, 36(2): 349-359.)

[16] XIE B, TANG X, TANG F. Hybrid recommendation base on learning to rank[C]// Proceedings of the 2015 9th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing. Piscataway, NJ: IEEE, 2015, 53-57.

[17] SAATY T L. The Analytic Hierarchy Process[M]. New York: McGraw-Hill, 1980: 22-71.

[18] ABDERRAHMEN M, MARTIN M, CHRISTOPHE D, et al. PeopleRank: social opportunistic forwarding[C]// Proceedings of IEEE INFOCOM 2010. Piscataway, NJ: IEEE, 2010: 1-5.

[19] O’CALLAGHAN D, HARRIGAN M, CARTHY J, et al. Network analysis of recurring YouTube spam campaigns[C]// Proceedings of the 2012 International Conference on Weblogs and Social Media. Dublin: ICWSM, 2012: 531-534.

[20] 黃創(chuàng)光, 印鑒, 汪靜, 等. 不確定近鄰的協(xié)同過濾推薦算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2010, 33(8): 1369-1377. (HUANG C G, YIN J, WANG J, et al. Uncertain neighbors’ collaborative filtering recommendation algorithm[J]. Chinese Journal of Computers, 2010, 33(8): 1369-1377.)

Videorecommendationalgorithmbasedonclusteringandhierarchicalmodel

JIN Liang1, YU Jiong1,2*, YANG Xingyao1, LU Liang2, WANG Yuefei2, GUO Binglei2, Liao Bin3

(1.SchoolofSoftware,XinjiangUniversity,UrumqiXinjiang830008,China;2.SchoolofInformationScienceandEngineering,XinjiangUniversity,UrumqiXinjiang830046,China;3.SchoolofStatisticsandInformatiion,XinjiangUniversityofFinanceandEconomics,UrumqiXinjiang830012,China)

Concerning the problem of data sparseness, cold start and low user experience of recommendation system, a video recommendation algorithm based on clustering and hierarchical model was proposed to improve the performance of recommendation system and user experience. Focusing on the user, similar users were obtained by analyzing Affiliation Propagation (AP) cluster, then historical data of online video of similar users was collected and a recommendation set of videos was geberated. Secondly, the user preference degree of a video was calculated and mapped into the tag weight of the video. Finally, a recommendation list of videos was generated by using analytic hierarchy model to calculate the ranking of user preference with videos. The experimental results on MovieLens Latest Dataset and YouTube video review text dataset show that the proposed algorithm has good performance in terms of Root-Mean-Square Error (RMSE) and the recommendation accuracy.

video recommendation; sparseness; cold start; hierarchical model; clustering analysis

2017- 04- 05;

2017- 06- 07。

國(guó)家自然科學(xué)基金資助項(xiàng)目(61262088,61462079,61562086,61363083,61562078)。

金亮(1992—),男,安徽滁州人,碩士研究生,CCF會(huì)員,主要研究方向:推薦系統(tǒng); 于炯(1964—),男,新疆烏魯木齊人,教授,博士生導(dǎo)師,博士,CCF會(huì)員,主要研究方向:網(wǎng)絡(luò)安全、網(wǎng)格與分布式計(jì)算; 楊興耀(1984—),男,湖北襄陽人,博士,CCF會(huì)員,主要研究方向:推薦系統(tǒng); 魯亮(1990—),男,新疆烏魯木齊人,博士研究生,CCF會(huì)員,主要研究方向:云計(jì)算、分布式計(jì)算; 王躍飛(1991—),男,新疆烏魯木齊人,博士研究生,主要研究方向:分布式計(jì)算、云計(jì)算; 國(guó)冰磊(1992—),女,湖北襄陽人,博士研究生, CCF會(huì)員,主要研究方向:綠色計(jì)算、云計(jì)算; 廖彬(1986—),男,新疆烏魯木齊人,副教授,博士,CCF會(huì)員,主要研究方向:大數(shù)據(jù)、綠色計(jì)算。

1001- 9081(2017)10- 2828- 06

10.11772/j.issn.1001- 9081.2017.10.2828

TP181

A

This work is partially supported by the National Natural Science Foundation of China (61262088, 61462079, 61562086, 61363083, 61562078).

JINLiang, born in 1992, M. S. candidate. His research interests include recommender system.

YUJiong, born in 1964, Ph. D., professor. His research interests include network security, grid and distributed computing.

YANGXingyao, born in 1984, Ph. D. His research interests include recommender system.

LULiang, born in 1990, Ph. D. candidate. His research interests include cloud computing, distributed computing.

WANGYuefei, born in 1991, Ph. D. candidate. His research interests include cloud computing, distributed computing.

GUOBinglei, born in 1992, Ph. D. candidate. Her research interests include green computing, cloud computing.

LIAOBin, born in 1986, Ph. D., associate professor. His research interests include big data, green computing.