社交網(wǎng)絡(luò)服務(wù)中的多維空間視頻推薦算法

周 嬌,霍 歡,b

(上海理工大學(xué)a.光電信息與計(jì)算機(jī)工程學(xué)院;b.上?，F(xiàn)代光學(xué)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,上海200093)

社交網(wǎng)絡(luò)服務(wù)中的多維空間視頻推薦算法

周 嬌a,霍 歡a,b

(上海理工大學(xué)a.光電信息與計(jì)算機(jī)工程學(xué)院;b.上海現(xiàn)代光學(xué)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,上海200093)

視頻推薦作為一項(xiàng)幫助用戶迅速找到其最感興趣視頻的關(guān)鍵技術(shù),是社交網(wǎng)絡(luò)服務(wù)中比較重要的研究內(nèi)容之一。傳統(tǒng)推薦算法未能充分利用視頻社會化網(wǎng)站中的多維信息,會導(dǎo)致冷啟動和數(shù)據(jù)稀疏的問題。為此,提出一種社交網(wǎng)絡(luò)服務(wù)中的多維空間視頻推薦算法。綜合分析構(gòu)成視頻社會化網(wǎng)絡(luò)的多維信息源要素,在此基礎(chǔ)上,通過構(gòu)建多維聚類空間,進(jìn)而實(shí)現(xiàn)基于多維聚類空間的視頻推薦算法,利用構(gòu)成視頻社會化網(wǎng)絡(luò)的多維信息源要素,為視頻的個(gè)性化推薦提供信息來源,以解決冷啟動和數(shù)據(jù)稀疏問題。實(shí)驗(yàn)結(jié)果表明,該算法在視頻推薦準(zhǔn)確度方面相對于傳統(tǒng)視頻推薦算法有明顯提高。

視頻推薦;社交網(wǎng)絡(luò)服務(wù);多維空間;屬性相似性;內(nèi)容相似性;社交關(guān)聯(lián)性

1 概述

隨著Internet上信息的爆炸式增長,用戶面臨著嚴(yán)峻的信息過載[1]問題。為了找到想要的信息,用戶需要花更多時(shí)間和精力去搜索和選擇,視頻網(wǎng)站也面臨同樣的問題。在這種背景下,高效的個(gè)性化視頻推薦技術(shù)[2]變得越來越重要,該問題成為學(xué)者們研究的重要課題之一。

目前的視頻推薦算法包括基于內(nèi)容的推薦、協(xié)同過濾推薦和基于社交網(wǎng)絡(luò)服務(wù)(Social NetworkService,SNS)的推薦。

基于內(nèi)容的推薦[3]是計(jì)算視頻與用戶偏好模型的相似度,進(jìn)而推薦相似的視頻給用戶,其實(shí)現(xiàn)機(jī)制簡單,具有較好的性能,但由于該方法總是向用戶推薦與用戶模型匹配的視頻,因此不能為用戶發(fā)現(xiàn)新的感興趣的視頻,同時(shí),存在冷啟動[4]和稀疏性問題[5]。

協(xié)同過濾推薦方法是通過用戶之間的相似性或者項(xiàng)目之間的相似性來產(chǎn)生推薦。常見的協(xié)同過濾算法有基于用戶最近鄰?fù)扑](UserCF)[6],基于物品的最近鄰?fù)扑](ItemCF)[7]及兩者結(jié)合的算法[8],目前,較常用的協(xié)同過濾算法是ItemCF。其優(yōu)點(diǎn)是可以發(fā)現(xiàn)用戶可能感興趣的新視頻,其缺點(diǎn)是同樣存在冷啟動和稀疏性問題。

隨著社交網(wǎng)絡(luò)服務(wù)的興起,把視頻引進(jìn)到社交網(wǎng)絡(luò)服務(wù)并分享已成為一大熱點(diǎn)研究問題[9]。文獻(xiàn)[10]通過用戶間信任度來推薦,文獻(xiàn)[11]把用戶社交關(guān)聯(lián)性、用戶行為活動、內(nèi)容相似性結(jié)合起來推薦,視頻搜索網(wǎng)站Clicker利用Facebook的好友關(guān)系做出推薦。社交網(wǎng)絡(luò)服務(wù)中的視頻推薦仍面臨以下問題:(1)視頻社會化網(wǎng)站中的多維信息沒有被充分利用,目前,結(jié)合社交網(wǎng)絡(luò)服務(wù),視頻、用戶之間正在形成一個(gè)動態(tài)的、復(fù)雜的視頻社會化網(wǎng)絡(luò),該網(wǎng)絡(luò)強(qiáng)大的信息聚合能力為視頻的個(gè)性化推薦提供了豐富的信息來源;(2)極端的數(shù)據(jù)稀疏性和冷啟動問題。

為解決上述問題,本文提出一種社交網(wǎng)絡(luò)服務(wù)中的多維空間視頻推薦算法。首先對視頻社會化網(wǎng)站中的多維信息源進(jìn)行分析,然后通過聚類構(gòu)建多維空間并進(jìn)行視頻推薦。

2 多維空間視頻推薦算法

2.1 多維信息源分析

視頻社會化網(wǎng)站中的多維信息可分為3類:與用戶相關(guān)的信息;與視頻相關(guān)的信息;與用戶視頻相關(guān)的信息。具體如下:

(1)與用戶相關(guān)的信息,可進(jìn)一步細(xì)分為用戶屬性信息[12]矩陣A、用戶間關(guān)注信息矩陣B。其中,用戶屬性信息表示用戶注冊時(shí)的屬性信息,比如性別、年齡、職業(yè)、興趣等,矩陣A中的任意值aij代表用戶ui與用戶uj的屬性相似度。用戶間的關(guān)注信息矩陣B表示用戶之間的關(guān)注關(guān)系,矩陣任意值bij代表用戶ui是否對用戶uj進(jìn)行關(guān)注,表示如下:

2.2 多維空間視頻推薦算法框架

多維空間視頻推薦算法框架如圖1所示,以3類信息作為輸入。該算法包括2個(gè)模塊:一個(gè)模塊是多維空間生成算法,該模塊利用原始的輸入信息,通過聚類算法生成多維聚類空間;另一模塊是基于多維聚類空間的推薦算法,該算法對于某個(gè)用戶ui和某個(gè)視頻vj,分別計(jì)算出用戶ui與視頻vj在多維空間的隸屬度矢量,最后計(jì)算出用戶ui與視頻vj的偏好程度來決定是否將視頻vj推薦給用戶ui。

(2)與視頻相關(guān)的信息,可進(jìn)一步細(xì)分為視頻屬性信息矩陣C、視頻內(nèi)容信息矩陣D。在視頻系統(tǒng)中,視頻的屬性信息是指視頻時(shí)間、視頻主要參與人物、導(dǎo)演等,矩陣C中的任意值cij代表視頻vi與視頻vj的屬性相似度。視頻的內(nèi)容信息可以從視頻的描述文檔中抽取關(guān)鍵詞來表示,也可用標(biāo)注在視頻上的Tag表示,視頻內(nèi)容矩陣D中的任意值dij代表視頻vi與視頻vj的內(nèi)容相似度。

(3)用戶-視頻信息表示用戶對視頻的分享行為矩陣E。矩陣E中任意值eij代表用戶ui對視頻vj的分享情況,表示如下:

圖1 多維空間視頻推薦算法框架

3 多維空間生成算法

在多維空間生成算法中通過經(jīng)典的K-均值聚類算法[13]生成多維空間,整個(gè)空間分為用戶空間和視頻空間。用戶空間可進(jìn)一步細(xì)分為用戶屬性子空間和用戶結(jié)構(gòu)子空間,用戶屬性子空間是根據(jù)用戶的屬性信息聚類而成的空間,該屬性子空間由K個(gè)用戶簇構(gòu)成,聚類使得簇內(nèi)用戶之間的屬性最相似,而簇間用戶之間屬性差異最大化;用戶結(jié)構(gòu)子空間是根據(jù)用戶之間的關(guān)注信息聚類而成的空間,該結(jié)構(gòu)子空間由K個(gè)用戶簇構(gòu)成,聚類使得簇內(nèi)用戶之間關(guān)聯(lián)最緊密,而簇間用戶之間關(guān)聯(lián)最弱。視頻空間也可以進(jìn)一步細(xì)分為視頻屬性子空間和視頻內(nèi)容子空間,根據(jù)視頻的屬性信息聚類而成的空間是視頻屬性子空間,該屬性子空間由K個(gè)視頻簇構(gòu)成,聚類使得簇內(nèi)視頻間的屬性最相似,而簇間視頻間屬性差異最大化。根據(jù)視頻的內(nèi)容信息聚類而成的空間是視頻內(nèi)容子空間,該內(nèi)容子空間由K個(gè)視頻簇構(gòu)成,聚類使得簇內(nèi)視頻間的內(nèi)容最相似,而簇間視頻間內(nèi)容差異最大化。算法結(jié)構(gòu)如圖2所示。

圖2 多維空間生成算法結(jié)構(gòu)

對于生成這4個(gè)子空間過程中用到的聚類,都采用經(jīng)典的K-均值聚類算法,唯一區(qū)別的是K-均值聚類算法中采用的相似度計(jì)算公式是不同的。下面分別給出對這4個(gè)子空間進(jìn)行聚類時(shí)所采用的相似度計(jì)算公式:

(1)用戶屬性子空間的相似度計(jì)算公式:設(shè)m個(gè)對象在屬性空間中有n個(gè)屬性特征(如年齡、性別、職業(yè)、興趣等)對其進(jìn)行描述,對各屬性值標(biāo)準(zhǔn)化后,描述對象向量X的n個(gè)屬性值記為X=則對象X和Y屬性相似度為:

其中,x′,y′代表向量中所有分量的平均值。用戶間屬性相似度aij可以通過式(3)計(jì)算得到。

(2)用戶結(jié)構(gòu)子空間的相似度計(jì)算公式:

其中,fans(ui)是指關(guān)注ui的用戶集,該信息可以從用戶關(guān)注信息矩陣B中獲取。在微博類的弱關(guān)聯(lián)社交網(wǎng)絡(luò)服務(wù)[14]中,一般用戶對名人用戶的關(guān)注很好地反應(yīng)了用戶的興趣愛好,所以,兩用戶共同的粉絲規(guī)模能較好地衡量他們的相似度。

(3)視頻屬性(如視頻時(shí)間、主演、導(dǎo)演等)子空間的相似度計(jì)算公式cij可通過式(3)得到。

(4)視頻內(nèi)容子空間相似度計(jì)算公式:視頻ci與視頻cj的內(nèi)容相似度為:

4 算法描述

對于某個(gè)用戶ui和某個(gè)視頻vj,多維空間視頻推薦算法首先計(jì)算出用戶ui與4個(gè)子空間的隸屬度矢量集合,然后計(jì)算出視頻vj與 4個(gè)子空間的隸屬度矢量,最后計(jì)算出用戶ui與視頻vj的偏好程度來決定是否將視頻vj推薦給用戶ui。多維空間視頻推薦算法如圖3所示。

圖3 多維空間視頻推薦算法

用戶ui與4個(gè)子空間的匹配度矢量的計(jì)算公式如下:

(1)用戶ui隸屬于用戶屬性子空間的隸屬度矢量表示用戶ui與此聚類空間第x個(gè)群組中代表用戶的平均屬性相似度,其中,表示第x個(gè)群組中用戶或視頻總個(gè)數(shù)。則ui與k個(gè)群組中代表用戶平均屬性相似度產(chǎn)生的向量為,其中,用戶ui屬性與哪個(gè)群組中用戶屬性越相似,向量的哪個(gè)分量值越大。

(2)用戶ui隸屬于用戶結(jié)構(gòu)子空間的隸屬度矢量表示用戶ui關(guān)注此聚類空間第x個(gè)群組中代表用戶的比例則ui關(guān)注k個(gè)群組中代表用戶的比例產(chǎn)生的向量為,其中,用戶ui關(guān)注哪個(gè)群組中的用戶的人數(shù)比例越大,向量的哪個(gè)分量值越大。

(3)用戶ui隸屬于視頻屬性子空間隸屬度矢量表示用戶ui對此聚類空間第x個(gè)群組中視頻分享個(gè)數(shù)比例,,則產(chǎn)生相應(yīng)向量為,其中,用戶ui分享哪個(gè)群組中視頻個(gè)數(shù)比例越大,向量的哪個(gè)分量值越大。

(4)用戶ui隸屬于視頻內(nèi)容子空間的隸屬度矢量表示用戶ui對此聚類空間第x個(gè)群組中視頻的分享個(gè)數(shù)比例,則產(chǎn)生的相應(yīng)向量為,其中,用戶ui分享哪個(gè)群組中的視頻的個(gè)數(shù)比例越大,向量的哪個(gè)分量值越大。

視頻vj與4個(gè)子空間的匹配度矢量的計(jì)算公式分別如下:

(1)視頻vj隸屬于用戶屬性子空間的隸屬度矢量表示此聚類空間第x個(gè)群組的代表用戶中分享過視頻vj的人數(shù)比例,,則產(chǎn)生的相應(yīng)向量為

(2)視頻vj隸屬于用戶結(jié)構(gòu)子空間的隸屬度矢量表示此聚類空間第x個(gè)群組的代表用戶中分享過視頻vj的人數(shù)比例,,則產(chǎn)生的相應(yīng)向量為

(3)視頻vj隸屬于視頻屬性子空間的隸屬度矢量表示視頻vj與此聚類空間第x個(gè)群組中代表視頻的平均屬性相似度,則產(chǎn)生的相應(yīng)向量為

(4)視頻vj隸屬于視頻內(nèi)容子空間的隸屬度矢量表示視頻vj與此聚類空間第x個(gè)群組中代表視頻的平均內(nèi)容相似度,則產(chǎn)生的相應(yīng)向量為

利用下式計(jì)算出用戶ui與視頻vj的偏好程度,其中,sim為相似度計(jì)算公式,見式(3);α表示用戶空間和視頻空間的權(quán)重。

5 實(shí)驗(yàn)結(jié)果和性能分析

5.1 數(shù)據(jù)集及度量標(biāo)準(zhǔn)

本文從騰訊微博和優(yōu)酷視頻中抽取真實(shí)數(shù)據(jù)集,數(shù)據(jù)集從優(yōu)酷五大最流行類別中隨機(jī)選取1 800個(gè)視頻,這些視頻的發(fā)布日期在2013年4月到10月期間,總共分享量達(dá)到5 000 000次。

抽取的數(shù)據(jù)包括以下信息:(1)用戶-用戶矩陣,用戶間的相互關(guān)注信息,以及用戶注冊內(nèi)容、微博內(nèi)容等屬性信息。(2)用戶-內(nèi)容矩陣,騰訊微博記錄了某視頻是否被用戶分享過。(3)內(nèi)容-內(nèi)容矩陣,視頻的文本描述、視頻屬性信息。在以下的實(shí)驗(yàn)中,把用戶-內(nèi)容矩陣80%的數(shù)據(jù)用作訓(xùn)練集,20%的數(shù)據(jù)用作測試集。

本文采用絕對平均偏差(MAE)來衡量推薦算法的準(zhǔn)確度。MAE的定義為:

其中,N表示推薦服務(wù)的個(gè)數(shù);實(shí)驗(yàn)推薦的結(jié)果為pi;而實(shí)際記錄為qi。MAE體現(xiàn)了算法預(yù)測值和實(shí)際值的差異,MAE值越小表明推薦算法越準(zhǔn)確。

5.2 結(jié)果分析

由于在采用K-均值聚類算法生成多維空間時(shí),聚類個(gè)數(shù)k的取值會對聚類結(jié)果產(chǎn)生影響,因此本文選擇k從2～15的14個(gè)值分別進(jìn)行實(shí)驗(yàn),在同等條件下計(jì)算出MAE,發(fā)現(xiàn)當(dāng)k為6時(shí),MAE值趨于穩(wěn)定且最小,故后續(xù)實(shí)驗(yàn)中取k等于6。

首先檢驗(yàn)推薦算法中權(quán)值α對視頻推薦結(jié)果的影響。圖4表明α值在0.56時(shí)得到最好推薦效果, α值太大或者太小都造成較低的準(zhǔn)確度,因?yàn)棣林堤髸r(shí)忽略了視頻空間因素,α值太小時(shí)忽略了用戶空間因素,而α值在0.56時(shí)同時(shí)考慮到用戶空間、視頻空間的影響,權(quán)衡好這兩大空間,才能得到最好的推薦效果。因此,在后續(xù)的實(shí)驗(yàn)中,選擇α為0.56作為多維空間視頻推薦算法中的權(quán)值。

圖4 視頻推薦中不同權(quán)值對準(zhǔn)確度的影響

為了檢驗(yàn)各空間的不可或缺性,在相同條件下,分別選取不同數(shù)量級的活躍項(xiàng)目(user/video)作為實(shí)驗(yàn)自變量?？紤]用戶結(jié)構(gòu)(US)、用戶屬性(UA)、視頻內(nèi)容(VC)、視頻屬性(VA)4個(gè)子空間USUA-VC-VA推薦結(jié)果與分別考慮3個(gè)子空間的推薦結(jié)果做比較,考慮用戶屬性、視頻內(nèi)容、視頻屬性,即得到UA-VC-VA空間;考慮用戶結(jié)構(gòu)、視頻內(nèi)容、視頻屬性,即得到US-VC-VA空間;考慮用戶結(jié)構(gòu)、用戶屬性、視頻屬性,即得到US-UA-VA空間;考慮用戶結(jié)構(gòu)、用戶屬性、視頻內(nèi)容,即得到US-UA-VC空間。實(shí)驗(yàn)結(jié)果如圖5所示,可以發(fā)現(xiàn),同時(shí)考慮4個(gè)子空間US-UA-VC-VA比只考慮其中,3個(gè)子空間的推薦效果有較明顯的優(yōu)勢,進(jìn)一步表明在視頻推薦算法中維度因素的重要性。實(shí)驗(yàn)同時(shí)也發(fā)現(xiàn)隨著活躍項(xiàng)目(user/video)數(shù)量的增多,準(zhǔn)確度逐漸增大。這是因?yàn)榛钴S項(xiàng)目數(shù)量越多,越可以保證聚類的多樣性和較高的準(zhǔn)確性。

圖5 不同空間視頻推薦絕對平均偏差比較

為了檢驗(yàn)多維空間視頻推薦算法的有效性,本文以傳統(tǒng)的基于內(nèi)容的推薦算法、協(xié)同過濾推薦算法作為對照,同時(shí),選取不同數(shù)量級的頂級活躍項(xiàng)目(user/video)進(jìn)行測試。實(shí)驗(yàn)結(jié)果如圖6所示,多維空間視頻推薦算法推薦效果最好,傳統(tǒng)的協(xié)同過濾推薦算法次之,傳統(tǒng)的基于內(nèi)容的推薦算法最差,尤其是在頂級活躍用戶數(shù)量較少的情況下,因?yàn)榇藭r(shí)數(shù)據(jù)較稀疏。

圖6 不同視頻推薦算法絕對平均偏差比較

6 結(jié)束語

本文提出一種社交網(wǎng)絡(luò)服務(wù)中的多維空間視頻推薦算法,通過對視頻社會化網(wǎng)站中的多維信息源進(jìn)行分析,構(gòu)建多維聚類空間,實(shí)現(xiàn)基于多維聚類空間的視頻推薦。該算法很好地解決了傳統(tǒng)推薦算法中未能充分利用視頻社會化網(wǎng)站中的多維信息導(dǎo)致的冷啟動和數(shù)據(jù)稀疏問題。實(shí)驗(yàn)結(jié)果表明,該算法在推薦精度方面相對于傳統(tǒng)視頻推薦算法有較大提高。今后將研究移動社交網(wǎng)絡(luò)服務(wù)移動上下文對視頻推薦的影響。

[1] 許海玲,吳 瀟,李曉東,等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J].軟件學(xué)報(bào),2009,20(2):350-362.

[2] Deng Zhengyu,Sang Jitao,Xu Changsheng.Personalized Video Recommendation Based on Cross-platform User Modeling[C]//Proceedings of ICME’13.[S.l.]: IEEE Press,2013:1-6.

[3] Pazzani M,Billsus D.Content-based Recommendation Systems[J].Computer Science,2007,4321:325-341.

[4] 孫冬婷,何 濤,張福海.推薦系統(tǒng)中的冷啟動問題研究綜述[J].計(jì)算機(jī)與現(xiàn)代化,2012,(5):58-63.

[5] 吳 顏,沈 潔,顧天竺,等.協(xié)同過濾推薦系統(tǒng)中數(shù)據(jù)稀疏問題的解決[J].計(jì)算機(jī)應(yīng)用研究,2007,24(6):94-98.

[6] 范 波,程久軍.用戶間多相似度協(xié)同過濾推薦算法[J].計(jì)算機(jī)科學(xué),2012,39(1):23-27.

[7] 鄧愛林,朱揚(yáng)勇,施伯樂.基于項(xiàng)目評分預(yù)測的協(xié)同過濾推薦算法[J].軟件學(xué)報(bào),2003,14(9):1621-1628.

[8] Vozalis M,Margaritis K G.On the Combination of Userbased and Item-based Collaborative Filtering[J]. International Journalof Computer Mathematics,2004, 81(9):1077-1096.

[9] Oehlberg L,Ducheneaut N,Thornton J D.Social TV: Designing for Distributed,Sociable Television Viewing[J]. International Journal of Human-computer Interaction,2008, 24(2):136-154.

[10] 王玉祥,喬秀全,李曉峰,等.上下文感知的移動社交網(wǎng)絡(luò)服務(wù)選擇機(jī)制研究[J].計(jì)算機(jī)學(xué)報(bào),2010, 33(11):2126-2135.

[11] Wang Zhi,Sun Lifeng,Zhu Wenwu,et a1.Joint Social and Content Recommendation for User-generated Videos in Online Social Network[J].IEEE Transactions on Multimedia,2013,15(3):698-709.

[12] Anh D,Viennet E.Collaborative Filtering in Social Networks:A Community-based Approach[C]// Proceedings of International Conference on Computing, Management and Telecommunications.[S.l.]:IEEE Press,2013:128-133.

[13] Kanungo T,Mount D M,Netanyahu N S.An Efficient K-means Clustering Algorithm:Analysis and Implementation[J].IEEE Transactionson Pattern Analysisand Machine Intelligence,2002,24(7):881-892.

[14] 陳克寒,韓盼盼,吳 健.基于用戶聚類的異構(gòu)社交網(wǎng)絡(luò)推薦算法[J].計(jì)算機(jī)學(xué)報(bào),2013,36(2):349-359.

編輯 劉 冰

Multi-dimensional Space Video Recommendation Algorithm in Social Network Service

ZHOU Jiaoa,HUO Huana,b
(a.School of Optical-electrical and Computer Engineering;b.Shanghai Key Laboratory of Modern Optical System, University of Shanghai for Science and Technology,Shanghai 200093,China)

The video recommendation,as a key enabling technology to provide users with the most interested and relevant videos,is one of the most important research topics in Social Network Service(SNS).This paper presents a multi-dimensional space based video recommendation algorithm in SNS,againsts the cold start and sparse caused by the traditional recommendation algorithms ignoring multidimensional information.By analyzing the multidimensional information sources in the video social networking sites,the paper imports various elements into the video recommendation,to construct multi-dimensional space by clustering and implement recommendation for user-generated videos based on multi-dimensional clustering space.The algorithm takes full use of the multidimensional information elements which constitute the video social networking providing a rich source of information for video personalized recommendation,and solves the problem of cold start and sparse data.Experimental results demonstrate the effectiveness of the multi-dimensionalspace based video recommendation algorithm,which achievesasignificantly higher recommendation accuracy than the traditional video recommendation algorithms.

video recommendation;Social Network Service(SNS);multi-dimensional space;attribute similarity; content similarity;social correlation

1000-3428(2015)01-0245-06

A

TP314

10.3969/j.issn.1000-3428.2015.01.046

國家自然科學(xué)基金資助項(xiàng)目(61003031)。

周 嬌(1988-),女,碩士,主研方向:數(shù)據(jù)挖掘,自然語言處理;霍 歡,副教授、博士。

2014-01-13

2014-03-18 E-mail:bestzhoujiao@163.com

中文引用格式:周 嬌,霍 歡.社交網(wǎng)絡(luò)服務(wù)中的多維空間視頻推薦算法[J].計(jì)算機(jī)工程,2015,41(1):245-250.

英文引用格式:Zhou Jiao,Huo Huan.Multi-dimensional Space Video Recommendation Algorithm in Social Network Service[J].Computer Engineering,2015,41(1):245-250.