社交网络服务中的多维空间视频推荐算法

周 娇,霍 欢,b

(上海理工大学a.光电信息与计算机工程学院;b.上海现代光学系统重点实验室,上海200093)

社交网络服务中的多维空间视频推荐算法

周 娇a,霍 欢a,b

(上海理工大学a.光电信息与计算机工程学院;b.上海现代光学系统重点实验室,上海200093)

视频推荐作为一项帮助用户迅速找到其最感兴趣视频的关键技术,是社交网络服务中比较重要的研究内容之一。传统推荐算法未能充分利用视频社会化网站中的多维信息,会导致冷启动和数据稀疏的问题。为此,提出一种社交网络服务中的多维空间视频推荐算法。综合分析构成视频社会化网络的多维信息源要素,在此基础上,通过构建多维聚类空间,进而实现基于多维聚类空间的视频推荐算法,利用构成视频社会化网络的多维信息源要素,为视频的个性化推荐提供信息来源,以解决冷启动和数据稀疏问题。实验结果表明,该算法在视频推荐准确度方面相对于传统视频推荐算法有明显提高。

视频推荐;社交网络服务;多维空间;属性相似性;内容相似性;社交关联性

1 概述

随着Internet上信息的爆炸式增长,用户面临着严峻的信息过载[1]问题。为了找到想要的信息,用户需要花更多时间和精力去搜索和选择,视频网站也面临同样的问题。在这种背景下,高效的个性化视频推荐技术[2]变得越来越重要,该问题成为学者们研究的重要课题之一。

目前的视频推荐算法包括基于内容的推荐、协同过滤推荐和基于社交网络服务(Social NetworkService,SNS)的推荐。

基于内容的推荐[3]是计算视频与用户偏好模型的相似度,进而推荐相似的视频给用户,其实现机制简单,具有较好的性能,但由于该方法总是向用户推荐与用户模型匹配的视频,因此不能为用户发现新的感兴趣的视频,同时,存在冷启动[4]和稀疏性问题[5]。

协同过滤推荐方法是通过用户之间的相似性或者项目之间的相似性来产生推荐。常见的协同过滤算法有基于用户最近邻推荐(UserCF)[6],基于物品的最近邻推荐(ItemCF)[7]及两者结合的算法[8],目前,较常用的协同过滤算法是ItemCF。其优点是可以发现用户可能感兴趣的新视频,其缺点是同样存在冷启动和稀疏性问题。

随着社交网络服务的兴起,把视频引进到社交网络服务并分享已成为一大热点研究问题[9]。文献[10]通过用户间信任度来推荐,文献[11]把用户社交关联性、用户行为活动、内容相似性结合起来推荐,视频搜索网站Clicker利用Facebook的好友关系做出推荐。社交网络服务中的视频推荐仍面临以下问题:(1)视频社会化网站中的多维信息没有被充分利用,目前,结合社交网络服务,视频、用户之间正在形成一个动态的、复杂的视频社会化网络,该网络强大的信息聚合能力为视频的个性化推荐提供了丰富的信息来源;(2)极端的数据稀疏性和冷启动问题。

为解决上述问题,本文提出一种社交网络服务中的多维空间视频推荐算法。首先对视频社会化网站中的多维信息源进行分析,然后通过聚类构建多维空间并进行视频推荐。

2 多维空间视频推荐算法

2.1 多维信息源分析

视频社会化网站中的多维信息可分为3类:与用户相关的信息;与视频相关的信息;与用户视频相关的信息。具体如下:

(1)与用户相关的信息,可进一步细分为用户属性信息[12]矩阵A、用户间关注信息矩阵B。其中,用户属性信息表示用户注册时的属性信息,比如性别、年龄、职业、兴趣等,矩阵A中的任意值aij代表用户ui与用户uj的属性相似度。用户间的关注信息矩阵B表示用户之间的关注关系,矩阵任意值bij代表用户ui是否对用户uj进行关注,表示如下:

2.2 多维空间视频推荐算法框架

多维空间视频推荐算法框架如图1所示,以3类信息作为输入。该算法包括2个模块:一个模块是多维空间生成算法,该模块利用原始的输入信息,通过聚类算法生成多维聚类空间;另一模块是基于多维聚类空间的推荐算法,该算法对于某个用户ui和某个视频vj,分别计算出用户ui与视频vj在多维空间的隶属度矢量,最后计算出用户ui与视频vj的偏好程度来决定是否将视频vj推荐给用户ui。

(2)与视频相关的信息,可进一步细分为视频属性信息矩阵C、视频内容信息矩阵D。在视频系统中,视频的属性信息是指视频时间、视频主要参与人物、导演等,矩阵C中的任意值cij代表视频vi与视频vj的属性相似度。视频的内容信息可以从视频的描述文档中抽取关键词来表示,也可用标注在视频上的Tag表示,视频内容矩阵D中的任意值dij代表视频vi与视频vj的内容相似度。

(3)用户-视频信息表示用户对视频的分享行为矩阵E。矩阵E中任意值eij代表用户ui对视频vj的分享情况,表示如下:

图1 多维空间视频推荐算法框架

3 多维空间生成算法

在多维空间生成算法中通过经典的K-均值聚类算法[13]生成多维空间,整个空间分为用户空间和视频空间。用户空间可进一步细分为用户属性子空间和用户结构子空间,用户属性子空间是根据用户的属性信息聚类而成的空间,该属性子空间由K个用户簇构成,聚类使得簇内用户之间的属性最相似,而簇间用户之间属性差异最大化;用户结构子空间是根据用户之间的关注信息聚类而成的空间,该结构子空间由K个用户簇构成,聚类使得簇内用户之间关联最紧密,而簇间用户之间关联最弱。视频空间也可以进一步细分为视频属性子空间和视频内容子空间,根据视频的属性信息聚类而成的空间是视频属性子空间,该属性子空间由K个视频簇构成,聚类使得簇内视频间的属性最相似,而簇间视频间属性差异最大化。根据视频的内容信息聚类而成的空间是视频内容子空间,该内容子空间由K个视频簇构成,聚类使得簇内视频间的内容最相似,而簇间视频间内容差异最大化。算法结构如图2所示。

图2 多维空间生成算法结构

对于生成这4个子空间过程中用到的聚类,都采用经典的K-均值聚类算法,唯一区别的是K-均值聚类算法中采用的相似度计算公式是不同的。下面分别给出对这4个子空间进行聚类时所采用的相似度计算公式:

(1)用户属性子空间的相似度计算公式:设m个对象在属性空间中有n个属性特征(如年龄、性别、职业、兴趣等)对其进行描述,对各属性值标准化后,描述对象向量X的n个属性值记为X=则对象X和Y属性相似度为:

其中,x′,y′代表向量中所有分量的平均值。用户间属性相似度aij可以通过式(3)计算得到。

(2)用户结构子空间的相似度计算公式:

其中,fans(ui)是指关注ui的用户集,该信息可以从用户关注信息矩阵B中获取。在微博类的弱关联社交网络服务[14]中,一般用户对名人用户的关注很好地反应了用户的兴趣爱好,所以,两用户共同的粉丝规模能较好地衡量他们的相似度。

(3)视频属性(如视频时间、主演、导演等)子空间的相似度计算公式cij可通过式(3)得到。

(4)视频内容子空间相似度计算公式:视频ci与视频cj的内容相似度为:

4 算法描述

对于某个用户ui和某个视频vj,多维空间视频推荐算法首先计算出用户ui与4个子空间的隶属度矢量集合,然后计算出视频vj与 4个子空间的隶属度矢量,最后计算出用户ui与视频vj的偏好程度来决定是否将视频vj推荐给用户ui。多维空间视频推荐算法如图3所示。

图3 多维空间视频推荐算法

用户ui与4个子空间的匹配度矢量的计算公式如下:

(1)用户ui隶属于用户属性子空间的隶属度矢量表示用户ui与此聚类空间第x个群组中代表用户的平均属性相似度,其中,表示第x个群组中用户或视频总个数。则ui与k个群组中代表用户平均属性相似度产生的向量为,其中,用户ui属性与哪个群组中用户属性越相似,向量的哪个分量值越大。

(2)用户ui隶属于用户结构子空间的隶属度矢量表示用户ui关注此聚类空间第x个群组中代表用户的比例则ui关注k个群组中代表用户的比例产生的向量为,其中,用户ui关注哪个群组中的用户的人数比例越大,向量的哪个分量值越大。

(3)用户ui隶属于视频属性子空间隶属度矢量表示用户ui对此聚类空间第x个群组中视频分享个数比例,,则产生相应向量为,其中,用户ui分享哪个群组中视频个数比例越大,向量的哪个分量值越大。

(4)用户ui隶属于视频内容子空间的隶属度矢量表示用户ui对此聚类空间第x个群组中视频的分享个数比例,则产生的相应向量为,其中,用户ui分享哪个群组中的视频的个数比例越大,向量的哪个分量值越大。

视频vj与4个子空间的匹配度矢量的计算公式分别如下:

(1)视频vj隶属于用户属性子空间的隶属度矢量表示此聚类空间第x个群组的代表用户中分享过视频vj的人数比例,,则产生的相应向量为

(2)视频vj隶属于用户结构子空间的隶属度矢量表示此聚类空间第x个群组的代表用户中分享过视频vj的人数比例,,则产生的相应向量为

(3)视频vj隶属于视频属性子空间的隶属度矢量表示视频vj与此聚类空间第x个群组中代表视频的平均属性相似度,则产生的相应向量为

(4)视频vj隶属于视频内容子空间的隶属度矢量表示视频vj与此聚类空间第x个群组中代表视频的平均内容相似度,则产生的相应向量为

利用下式计算出用户ui与视频vj的偏好程度,其中,sim为相似度计算公式,见式(3);α表示用户空间和视频空间的权重。

5 实验结果和性能分析

5.1 数据集及度量标准

本文从腾讯微博和优酷视频中抽取真实数据集,数据集从优酷五大最流行类别中随机选取1 800个视频,这些视频的发布日期在2013年4月到10月期间,总共分享量达到5 000 000次。

抽取的数据包括以下信息:(1)用户-用户矩阵,用户间的相互关注信息,以及用户注册内容、微博内容等属性信息。(2)用户-内容矩阵,腾讯微博记录了某视频是否被用户分享过。(3)内容-内容矩阵,视频的文本描述、视频属性信息。在以下的实验中,把用户-内容矩阵80%的数据用作训练集,20%的数据用作测试集。

本文采用绝对平均偏差(MAE)来衡量推荐算法的准确度。MAE的定义为:

其中,N表示推荐服务的个数;实验推荐的结果为pi;而实际记录为qi。MAE体现了算法预测值和实际值的差异,MAE值越小表明推荐算法越准确。

5.2 结果分析

由于在采用K-均值聚类算法生成多维空间时,聚类个数k的取值会对聚类结果产生影响,因此本文选择k从2～15的14个值分别进行实验,在同等条件下计算出MAE,发现当k为6时,MAE值趋于稳定且最小,故后续实验中取k等于6。

首先检验推荐算法中权值α对视频推荐结果的影响。图4表明α值在0.56时得到最好推荐效果, α值太大或者太小都造成较低的准确度,因为α值太大时忽略了视频空间因素,α值太小时忽略了用户空间因素,而α值在0.56时同时考虑到用户空间、视频空间的影响,权衡好这两大空间,才能得到最好的推荐效果。因此,在后续的实验中,选择α为0.56作为多维空间视频推荐算法中的权值。

图4 视频推荐中不同权值对准确度的影响

为了检验各空间的不可或缺性,在相同条件下,分别选取不同数量级的活跃项目(user/video)作为实验自变量。考虑用户结构(US)、用户属性(UA)、视频内容(VC)、视频属性(VA)4个子空间USUA-VC-VA推荐结果与分别考虑3个子空间的推荐结果做比较,考虑用户属性、视频内容、视频属性,即得到UA-VC-VA空间;考虑用户结构、视频内容、视频属性,即得到US-VC-VA空间;考虑用户结构、用户属性、视频属性,即得到US-UA-VA空间;考虑用户结构、用户属性、视频内容,即得到US-UA-VC空间。实验结果如图5所示,可以发现,同时考虑4个子空间US-UA-VC-VA比只考虑其中,3个子空间的推荐效果有较明显的优势,进一步表明在视频推荐算法中维度因素的重要性。实验同时也发现随着活跃项目(user/video)数量的增多,准确度逐渐增大。这是因为活跃项目数量越多,越可以保证聚类的多样性和较高的准确性。

图5 不同空间视频推荐绝对平均偏差比较

为了检验多维空间视频推荐算法的有效性,本文以传统的基于内容的推荐算法、协同过滤推荐算法作为对照,同时,选取不同数量级的顶级活跃项目(user/video)进行测试。实验结果如图6所示,多维空间视频推荐算法推荐效果最好,传统的协同过滤推荐算法次之,传统的基于内容的推荐算法最差,尤其是在顶级活跃用户数量较少的情况下,因为此时数据较稀疏。

图6 不同视频推荐算法绝对平均偏差比较

6 结束语

本文提出一种社交网络服务中的多维空间视频推荐算法,通过对视频社会化网站中的多维信息源进行分析,构建多维聚类空间,实现基于多维聚类空间的视频推荐。该算法很好地解决了传统推荐算法中未能充分利用视频社会化网站中的多维信息导致的冷启动和数据稀疏问题。实验结果表明,该算法在推荐精度方面相对于传统视频推荐算法有较大提高。今后将研究移动社交网络服务移动上下文对视频推荐的影响。

[1] 许海玲,吴 潇,李晓东,等.互联网推荐系统比较研究[J].软件学报,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] 孙冬婷,何 涛,张福海.推荐系统中的冷启动问题研究综述[J].计算机与现代化,2012,(5):58-63.

[5] 吴 颜,沈 洁,顾天竺,等.协同过滤推荐系统中数据稀疏问题的解决[J].计算机应用研究,2007,24(6):94-98.

[6] 范 波,程久军.用户间多相似度协同过滤推荐算法[J].计算机科学,2012,39(1):23-27.

[7] 邓爱林,朱扬勇,施伯乐.基于项目评分预测的协同过滤推荐算法[J].软件学报,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] 王玉祥,乔秀全,李晓峰,等.上下文感知的移动社交网络服务选择机制研究[J].计算机学报,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] 陈克寒,韩盼盼,吴 健.基于用户聚类的异构社交网络推荐算法[J].计算机学报,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

国家自然科学基金资助项目(61003031)。

周 娇(1988-),女,硕士,主研方向:数据挖掘,自然语言处理;霍 欢,副教授、博士。

2014-01-13

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

中文引用格式:周 娇,霍 欢.社交网络服务中的多维空间视频推荐算法[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.