计算机应用   2017, Vol. 37 Issue (10): 2828-2833, 2860  DOI: 10.11772/j.issn.1001-9081.2017.10.2828
0

引用本文 

金亮, 于炯, 杨兴耀, 鲁亮, 王跃飞, 国冰磊, 廖彬. 基于聚类层次模型的视频推荐算法[J]. 计算机应用, 2017, 37(10): 2828-2833, 2860.DOI: 10.11772/j.issn.1001-9081.2017.10.2828.
JIN Liang, YU Jiong, YANG Xingyao, LU Liang, WANG Yuefei, GUO Binglei, Liao Bin. Video recommendation algorithm based on clustering and hierarchical model[J]. Journal of Computer Applications, 2017, 37(10): 2828-2833, 2860. DOI: 10.11772/j.issn.1001-9081.2017.10.2828.

基金项目

国家自然科学基金资助项目(61262088,61462079,61562086,61363083,61562078)

通信作者

于炯, E-mail:yujiong@xju.edu.cn

作者简介

金亮(1992-), 男, 安徽滁州人, 硕士研究生, CCF会员, 主要研究方向:推荐系统;
于炯(1964-), 男, 新疆乌鲁木齐人, 教授, 博士生导师, 博士, CCF会员, 主要研究方向:网络安全、网格与分布式计算;
杨兴耀(1984-), 男, 湖北襄阳人, 博士, CCF会员, 主要研究方向:推荐系统;
鲁亮(1990-), 男, 新疆乌鲁木齐人, 博士研究生, CCF会员, 主要研究方向:云计算、分布式计算;
王跃飞(1991-), 男, 新疆乌鲁木齐人, 博士研究生, 主要研究方向:分布式计算、云计算;
国冰磊(1992-), 女, 湖北襄阳人, 博士研究生, CCF会员, 主要研究方向:绿色计算、云计算;
廖彬(1986-), 男, 新疆乌鲁木齐人, 副教授, 博士, CCF会员, 主要研究方向:大数据、绿色计算

文章历史

收稿日期:2017-04-05
修回日期:2017-06-07
基于聚类层次模型的视频推荐算法
金亮1, 于炯1,2, 杨兴耀1, 鲁亮2, 王跃飞2, 国冰磊2, 廖彬3    
1. 新疆大学 软件学院, 乌鲁木齐 830008;
2. 新疆大学 信息科学与工程学院, 乌鲁木齐 830046;
3. 新疆财经大学 统计与信息学院, 乌鲁木齐 830012
摘要: 目前推荐系统存在评论数据稀疏、冷启动和用户体验度低等问题,为了提高推荐系统的性能和进一步改善用户体验,提出基于聚类层次模型的视频推荐算法。首先,从相关用户方面着手,通过近邻传播(AP)聚类分析得到相似用户,从而收集相似用户中的历史网络视频数据,进而形成视频推荐集合;其次,利用用户行为的历史数据计算出用户对视频的喜好值,再把视频的喜好值转换成视频的标签权重;最后,通过层次分析模型算出视频推荐集合中用户喜好视频的排序,产生推荐列表。基于MovieLens Latest Dataset和YouTube视频评论文本数据集,实验结果表明所提算法在均方根误差和决策精度方面均表现出良好的性能。
关键词: 视频推荐    稀疏性    冷启动    层次模型    聚类分析    
Video recommendation algorithm based on clustering and hierarchical model
JIN Liang1, YU Jiong1,2, YANG Xingyao1, LU Liang2, WANG Yuefei2, GUO Binglei2, Liao Bin3     
1. School of Software, Xinjiang University, Urumqi Xinjiang 830008, China;
2. School of Information Science and Engineering, Xinjiang University, Urumqi Xinjiang 830046, China;
3. School of Statistics and Informatiion, Xinjiang University of Finance and Economics, Urumqi Xinjiang 830012, China
Abstract: 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.
Key words: video recommendation    sparseness    cold start    hierarchical model    clustering analysis    
0 引言

伴随着网络费用的下降以及4G网络的完善和5G网络的到来, 视频数量将变得越来越庞大, 其网络视频数据如表 1所示, 如何在大量的视频中推荐出用户喜欢的视频是一个巨大的挑战。就目前而言, 传统的推荐系统主要分为基于内容推荐[1]、协同过滤推荐[2-3]和混合过滤推荐[4]。基于内容推荐是通过机器学习的方法从训练集中提取出内容特征, 再与用户的兴趣特征相比通过内容特征与兴趣特征的相似度来产生推荐。这其中存在内容难以提取有意义的特征和无法得到其他用户的判断情况等问题。基于关联规则推荐则是以项目的相关性为基础, 通过大量的数据统计找出项目的相关性, 但是关联规则的发现耗时和项目的同义性问题有待解决。基于效用推荐需要为每个用户创建一个有效函数, 这样存在用户有效函数的创建问题和属性重叠问题。协同过滤推荐是通过用户评价的方式来建立用户和项目之间的联系, 把用户评价转换成用户对项目的喜好程度来预测用户对项目的喜好从而形成推荐。但是后来研究发现仅凭这样产生的推荐结果很难反映出用户的喜好[5]

表 1 中国网络视频用户规模和使用率 Table 1 Scale and rate usage of video users in China

为此, 本文提出基于聚类层次模型的视频推荐算法(Video Recommendation algorithm Based on Clustering and Hierarchical model, VRBCH), 首先通过相关用户属性标签的近邻传播(Affiliation Propagation, AP)聚类[6]得到与推荐用户相似的其他用户集合;然后通过其他用户的历史数据获得视频推荐集合;最后通过被推荐用户历史数据信息分析得出视频分类标签权重, 利用视频推荐集合和视频分类标签权重算出视频推荐集合中视频的顺序, 推荐给用户。本文通过对推荐用户历史数据进行训练, 调整PageRank[7]模型参数, 通过反复迭代得到用户历史视频的重要性, 然后通过视频重要性确定视频中分类标签的权重。PageRank模型偏向于历史数据, 然而人的兴趣爱好是通过实践逐渐产生的, 短时间内不会出现兴趣爱好大幅度改变问题, 所以得到的兴趣爱好数据无需频繁更新。本文通过推荐用户行为算出视频分类标签权重, 降低了用户自己定义视频分类标签权重的误差。另外, 在分析视频集合中的某个视频倾向于某个分类标签时采用视频专家的建议, 避免了用户自己分析时存在不确定误差。

1 相关工作

当前, 推荐系统研究最多的是协同推荐模型, 其原理是相似的用户都会有共同点, 不相似的用户各有各的不同。例如, 相似的两个人他们会在某一观点、某一爱好或某些事物都有相似或相同的兴趣爱好。协同过滤推荐主要包括基于模型的协同过滤推荐和基于近邻的协同过滤推荐。

杨兴耀等[8]利用用户评分的奇异性和扩散性对原有用户相似性模型进行改进、扩展, 找出与用户相似的近邻集合Ku;利用评分预测函数, 通过近邻用户对项目的评分计算出用户对项目的预测评分从而得到用户的推荐集合。尹路通等[9]通过用户评论利用情感词分析技术, 计算出用户的兴趣倾向度, 再利用兴趣倾向度建立用户虚拟评分矩阵, 来弥补现实评分的不足;同时建立用户兴趣模型, 利用隐语义模型把传统的二元推荐扩充为三元推荐来预测用户的喜好产生推荐。孙光福等[10]通过用户消费的先后时间顺序得到用户与产品、用户与用户、产品与产品的影响关系, 来构建用户与产品、用户与用户、产品与产品的结构关系,并以此为基础计算出它们的相似度,再利用概率分解模型来重构评分矩阵, 利用评分矩阵产生相应的推荐。张付志等[11]利用核主成分分析法提取用户评分矩阵的非线性特征, 最大限度地保留了用户和项目的特征信息;最后,还引入了Cauchy加权M-估计量函数, 虽然损失了部分精度,但是在满足需求下提高了算法的鲁棒性。张燕平等[12]利用历史记录的评分矩阵得到用户信誉, 对于信誉低的用户通过抑制其推荐影响来达到降低精度影响。胡勋等[13]引入图像检索中常用的推土机距离计算方法, 融入项目特征计算出用户的相似性,降低了协同推荐算法中稀疏性带来的挑战, 避免了评分矩阵的稀疏性对用户相似性的影响;此外还引入了社会用户关系计算信任权重得到近邻用户,提高了混合推荐的精度。郭磊等[14]从推荐对象间的关联关系出发, 融合了用户的社会关系、项目间关系和评分信息三种不同类型的信息, 利用共享特征空间的方法对推荐结果进行优化, 起到了优化推荐结果的作用。陈克寒等[15]利用两阶段用户聚类的方法先从稀疏数据中聚类出密集子集形成核心聚类, 然后对其提取用户特征再进行聚类,最后将聚类结果用于推荐。

这些算法的优缺点如表 2所示, 它们都是在用户相似度和评分上直接操作来产生推荐, 并未对推荐结果进行排序处理, 在一定程度上限制了算法性能的进一步提升。好的推荐排序模型必将获得好的推荐结果[16], 好的推荐结果必将产生好的用户体验, 达到用户对推荐产生依赖的效果。利用推荐用户历史数据和浏览行为把视频喜好程度分解成视频喜好标签权重,然后再结合视频推荐集合算出用户对视频的喜好值, 形成推荐。

表 2 协同过滤推荐算法的优缺点 Table 2 Merits and faults of collaborative filtering recommendation algorithms
2 VRBCH算法详述

总体上说, VRBCH大致可分为以下三个阶段:对相关用户进行AP聚类分析、将推荐用户历史数据行为转换成视频喜好标签权值和用层次排序模型产生推荐。

2.1 聚类分析

对视频用户的聚类算法有很多, 比如k-均值、模糊集等。本文通过AP聚类分析[6]找出相似用户进而找到他们喜爱的视频, 是因为AP聚类不需要指定聚类数目, 与其他聚类算法相比误差平方和较低。本文通过分析用户的性别、年龄、学历、住址(手机号码)、兴趣爱好等用户属性找出相似用户, 现设有n个用户, 每个用户有p个属性, 则用户矩阵为:

$\mathit{\boldsymbol{U}}{\rm{ = }}\left[ \begin{array}{l} {x_{11}}\;{x_{12}}\; \cdots {x_{1p}}\\ {x_{21}}\;{x_{22}}\; \cdots {x_{2p}}\\ \; \vdots \;\;\;\;\; \vdots \;\;\;\;\;\;\;\; \vdots \\ {x_{n1}}\;{x_{n2}}\; \cdots {x_{np}} \end{array} \right]$

其中:xij(i=1, 2, …, n; j=1, 2, …, p)为第i个用户第j个属性数据。

第1步  先对用户数据进行归一化处理。本文通过式(1) 把数据压缩到[0, 1]闭区间上:

${x^ * } = \frac{{{x_{ij}} - \mathop {\min }\limits_{1 \le t \le n} {x_{tj}}}}{{\mathop {\max }\limits_{1 \le t \le n} {x_{tj}} - \mathop {\min }\limits_{1 \le t \le n} {x_{tj}}}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {i = 1, \cdots ,n;j = 1, \cdots ,m} $ (1)

第2步  构建相似度矩阵S

第3步  利用式(2) ~(4) 迭代更新吸引度矩阵R和归属度矩阵a。计算公式如下:

$r\left( {i,k} \right) \leftarrow s\left( {i,k} \right) - \mathop {\max }\limits_{k's.t.k' \ne k} \left\{ {a\left( {i,k} \right) + s\left( {i,k} \right)} \right\}$ (2)

如果ik时:

$a\left( {i,k} \right) \leftarrow \min \left\{ {0,r\left( {k,k} \right) + \sum\limits_{i'.s.t.i' \notin \{ i,k\} } {\max \left\{ {0,r\left( {i',k} \right)} \right\}} } \right\}$ (3)
$a\left( {k,k} \right) \leftarrow \sum\limits_{i'.s.t.i' \ne k} {\max \left\{ {0,r\left( {i',k} \right)} \right\}} $ (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)]是点ik的相似度。

第4步  判断是否达到预设迭代次数:如果已达到迭代次数,则进行第5步。如果没有达到迭代次数,则判断a(i, i)+r(i, i)是否大于0,若小于0,则重复第3~4步;若大于0,则进行第5步

第5步  迭代更新结束选择聚类中心,并分配聚类输出聚类集合P

其算法如下。

算法1   相似用户AP聚类的核心算法。

输入  相似用户集合C,阻尼系数λ

输出  相似用户集合P

BEGIN

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

2)   建立相似矩阵S;

3)   计算吸引度矩阵:

4)   $r\left({i, k} \right) \leftarrow s\left({i, k} \right) -\mathop {\max }\limits_{k's.t.k' \ne k} \left\{ {a\left({i, k} \right) + s\left({i, k} \right)} \right\}$;

5)   计算归属度矩阵:

6)   if ik

7)   $\begin{array}{l} a\left({i, k} \right) \leftarrow \\ \quad \quad \quad \min \left\{ {0, r\left({k, k} \right) + \sum\limits_{i'.s.t.i' \notin \{ i, k\} } {\max \left\{ {0, r\left({i', k} \right)} \right\}} } \right\} \end{array}$;

8)   else

9)   $a\left({k, k} \right) \leftarrow \sum\limits_{i'.s.t.i' \ne k} {\max \left\{ {0, r\left({i', k} \right)} \right\}} $;

10)   if a(i, i)+r(i, i)>0

11)   选择聚类中心;

12)   else

13)   返回3) 重新计算;

END

2.2 层次排序模型

层次排序模型[17]是为了解决视频排序过程中用户对一些视频标签无法准确估量和量化的分析模型, 用于解决用户难以准确定位自身需求和兴趣权重的问题。其本质是根据具体需求决定分类标签的影响权重从而求出最优解。首先将决策问题分解成多个层次, 如图 1所示, 再构造成对比较矩阵, 计算权重向量并作一致性检验, 最后得出最优解。

图 1 选择视频的层次结构 Figure 1 Hierarchy of selected videos

层次分析往往将一些难以量化的分类标签通过人的主观判断实现量化处理。但是在人的主观判断中往往存在误差, 因此本文引入PageRank[7]排序模型, 计算出用户历史视频的重要性值, 构建成对比较矩阵计算出分类标签的权重, 最终从视频推荐集合中找出最优视频集合。

对于成对比较矩阵的构建, 假设历史数据中有n个视频, 每个视频相当于一个节点, 根据用户行为信息建立视频与视频之间的互连模型, 如图 2所示。则视频的排序值(Rank值)的计算公式[18]为:

图 2 用户行为网络图 Figure 2 Network diagram of user behavior
$R\left( {{p_i}} \right) = \frac{{1 - d}}{N} + d\sum\limits_{{p_j} \in M\left( i \right)} {\frac{{R\left( {{p_j}} \right)}}{{L\left( {{p_j}} \right)}}} \times r$ (5)

其中:R(pi)表示第i个视频的排序值; d是阻尼因子, 1-d是随机浏览新的视频的概率; L(pj)是视频pj的链出视频数; r是历史数据中相同视频重复的个数。

n个历史视频中找出分类标签, 例如视频的地域、年份、动作、科幻、战争、主演、导演等为w1, w2, …, wm, 利用式(5) 算出每个视频的Rank值并赋给对应视频下的分类标签, 若不同视频中含有相同分类标签则取该相同分类标签中的最大值。

定义1  设pi视频对应的Rank值为ri, 其含有的分类标签为w1, w2, …, wi, 则其分类标签对应的值为w1=w2=…=wi=ri; pj视频对应的Rank值为rj, 其含有的分类标签为w1, w2, …, wj则其分类标签对应的值为w1=w2=…=wj=rj; 如果ri > rjw1=w2=w3=ri

定义2  比较m个视频标签对上一层视频标签的影响用aij表示, 则aij=wi/wj, 其尺度含义如表 3所示。

表 3 1~9尺度aij的含义 Table 3 Definition of scale aij from 1 to 9

定义3  由于式(5) 计算出视频重要值为非整数, 为了减少计算量和计算误差,本文在四舍五入的基础上进行同步取整。例如, 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。

在视频标签权重的计算过程中, 通过上面规则构建成对比较矩阵:

$\mathit{\boldsymbol{A}} = \left[ \begin{array}{l} {w_1}/{w_1}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {w_1}/{w_2}{\kern 1pt} {\kern 1pt} \cdots {\kern 1pt} {\kern 1pt} {\kern 1pt} {w_1}/{w_m}\\ {w_2}/{w_1}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {w_2}/{w_2}{\kern 1pt} {\kern 1pt} \cdots {\kern 1pt} {\kern 1pt} {\kern 1pt} {w_2}/{w_m}\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \vdots {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \vdots {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \vdots \\ {w_m}/{w_1}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {w_m}/{w_2}{\kern 1pt} {\kern 1pt} \cdots {\kern 1pt} {\kern 1pt} {\kern 1pt} {w_m}/{w_m} \end{array} \right]$

本文采用幂法逐步迭代对成对比较矩阵进行特征值和特征向量的求解并作一致性检验。

设矩阵A=(aij)m×m, A>0, 则$\mathop {\lim }\limits_{k \to \infty } \frac{{{\mathit{\boldsymbol{A}}^k}\mathit{\boldsymbol{e}}}}{{{\mathit{\boldsymbol{e}}^T}{\mathit{\boldsymbol{A}}^k}\mathit{\boldsymbol{e}}}} = CW$, 其中WA的最大特征值对应的特征向量, C为常数, 向量e为单位向量。

首先, 选取n维归一化初始向量w(0) ; 计算出w(k+1) =Aw(k), k=0, 1, …; 然后归一化w(k+1) 。即:

${\mathit{\boldsymbol{w}}^{\left( {k + 1} \right)}} = \frac{{{\mathit{\boldsymbol{w}}^{\left( {k + 1} \right)}}}}{{\sum\limits_{i = 1}^n {{\mathit{\boldsymbol{w}}^{\left( {k + 1} \right)}}} }}$ (6)

如果|wi(k+1) -wi(k)|<ε(i=1, 2, …, n)时, 则为所求的特征向量; 否则返回w(k+1) =Aw(k)。其中ε为预先给定的常数精度。

最后计算出最大特征根:

$\lambda = \frac{1}{n}\sum\limits_1^n {\frac{{w_i^{^{\left( {k + 1} \right)}}}}{{w_i^{^{\left( k \right)}}}}} $ (7)

为了确定特征向量是否适合为分类标签的权重, 必须对特征向量w作一致性检验。其一致性比率CR计算公式如下:

$CR = CI/RI < 0.1$ (8)

其中:CI为一致性指标。CI=0时, A为一致阵。CI越大A越偏离一致阵, 其公式如式(9) 所示。RI为不同的n利用正互反矩阵算出CI的平均值作为随机一致性指标, 如表 4所示。

表 4 随机一致性指标RI的数值 Table 4 Value of random consistency index RI
$CI = \frac{{\lambda - n}}{{n - 1}}$ (9)
2.3 推荐流程

视频推荐流程步骤如下。

输入  相关用户数据集合C

输出  针对用户集合中用户所观看视频的推荐集合I

1) 收集所有相关用户、标注属性, 利用AP聚类得到相似用户。

2) 收集所有相似用户观看的历史视频数据形成预推荐集合, 并按照观看时长和视频出现的时间进行整理。

3) 判断推荐用户是否是新用户, 如果是则按照第2) 步整理的视频进行推荐。

4) 利用推荐用户观看的历史数据进行PageRank排序分析, 通过用户行为形成网络图计算出用户对历史视频的喜爱程度。

5) 分解历史视频数据的受喜爱标签, 构建标签成对比较矩阵。

6) 计算标签权重, 利用第2) 步得到的视频预推荐集合进行计算形成推荐集合。

3 实验评估与分析

实验部分, 本文先选定所用数据集, 介绍评定标准, 然后用现有数据模拟现实环境, 再利用历史数据优化参数。最后介绍VRBCH算法与其他算法的对比实验并作相应的分析。

3.1 实验数据集

为了综合评估算法性能, 实验采用MovieLens Latest Datasets和YouTube视频评论文本[19]数据集, 基本参数如表 5所示。

表 5 评分数据集的基本参数 Table 5 Basic parameters of ranking datasets
3.2 评估标准

为了更好地验证VRBCH算法的性能, 本文采用均方根误差(Root Mean Square Error, RMSE)、F-measure来作为评价标准。RMSE通过计算预测的用户行为和实际的用户行为之间的偏差来衡量预测的准确性。假设对n个用户行为进行预测, 得到的预测结果集合为P={p1, p2, …, pn}, 对应的实际用户行为集合为Ur={r1, r2, …, rn},则算法RMSE表示为:

$RMSE{\rm{ = }}\sqrt {\frac{1}{n}\sum\limits_{i = 1}^n {({p_i} - {r_i})} } $ (10)

本文的准确率采用准确率和召回率的加权调和平均即F-measure作为衡量标准, 其定义为:

$F - measure = \frac{{2precision \times recall}}{{precision + recall}}$ (11)
$precision = \frac{{P \cap Ur}}{P} \times 100\% $ (12)
$recall = \frac{{P \cap Ur}}{{Ur}} \times 100\% $ (13)

其中: precision为准确率; recall为召回率; P为预测结果集合; Ur为实际用户行为集合。

另外, 确保最大限度地利用数据集, 实验采用十折交叉验证法(10-floder cross validation), 实验中将选中的数据分成10份, 轮流将其中9份作为训练集, 1份作为验证集。10次结果的正确率的平均值作为对算法精度的估计。

3.3 推荐算法参数优化

就聚类算法和排序模型而言, 恰当的参数选择对推荐算法的性能有很大影响。AP聚类中的所有数据初始相似度的p值决定聚类数目的多少, p值越大输出聚类数目越多, p值越小输出聚类数目越少, 所以p值为所有数据相似度的均值。

$p = \frac{{\sum\limits_{i,j = 1,i \ne j}^n {s\left( {i,j} \right)} }}{{n \times \left( {n - 1} \right)}}$ (14)

其中:s(i, k)是数据相似度。

AP聚类中阻尼系数λ的大小决定着聚类过程中迭代的次数:λ减小, 迭代次数减少但容易引起震荡; λ增大迭代次数增加, 增加系统时间开销。

图 3所示的λ系数对比图可以看出:当λ=0.6, 0.7时, 其震荡效果相似, 即λ>0.6时其震荡效果相似, 所以本文为了降低时间开销λ取0.6。

图 3 不同λ取值时系统的震荡情况 Figure 3 System oscillation under different λ values

对于Pagerank模型来说, 阻尼因子d的正确选择不仅影响着Pagerank模型的幂法收敛速度还影响着排序的公正性, 其d值减小虽然提高了Pagerank的收敛速度, 但是降低了其排序的公正性。所以本文取不同的d值分别测试对推荐结果的影响, 其结果如图 4所示。

图 4 不同d值对推荐模型的影响 Figure 4 Effect of different d values on recommendation model

图 4可以看出在PageRank模型中, 阻尼系数d取0.78时VRBCH推荐算法的RMSE值取得最小, 且F-measure值取得最大, 此时推荐效果较为理想, 下节在比较不同推荐算法的性能优劣时均采用此设置。

3.4 实验结果比较

为了精准评估本文所提出的VRBCH算法性能, 本节选取基于时序行为的矩阵分解(Sequential Matrix Factorization, SequentialMF)算法[10]、基于用户的协同过滤(User Collaboration Filter, UserCF)算法、不确定近邻的协同过滤(Uncertain Neighbors'' Collaborative Filtering, UNCF)算法[20]作对比实验。其中, SequentialMF中, 在关系影响参数λ=5, 数据稀疏性为99%的情况下通过用户观看视频的时间构建用户关系网络, 利用网络图进行关系计算, 再通过概率矩阵分解模型挖掘出推荐视频。在UserCF中, 把数据集分成测试集和训练集, 利用训练集计算出K=10个用户的相似性获得相似性矩阵usersim, 再计算出这10个邻居对视频的兴趣集合, 推荐20个视频给用户。在UNCF中, 利用视频或用户的相似性计算产生近邻因子, 通过近邻因子在调和参数Ф=20的情况下计算视频的预测评分产生推荐。

通过不同数据集数据量的百分比, 利用RMSEF-measure评价指标进行实验, percentage值取区间[10, 90],实验结果如图 5~6所示。

图 5 不同推荐算法的RMSE性能比较 Figure 5 RMSE performance comparison of different recommendation algorithms
图 6 不同推荐算法的F-measure性能比较 Figure 6 F-measure performance comparison of different recommendation algorithms

图 5中,随着实验数据量百分比的不断增加RMSE整体呈下降趋势, 当实验数据量达到50%以后下降趋势缓慢, 数据量达80%后其RMSE性能基本不变。从图 5中可以看出, VRBCH算法与SequentialMF、UserCF、UNCF算法的RMSE性能相比, 虽然前期有较大波动但最终结果较为理想, 前期波动主要由于数据量过小而误差较大。从图 6可以看出各算法F-measure性能随着数据集百分比的递增均呈上升趋势, 其中VRBCH算法的F-measure性能最高。当数据量达到80%时VRBCH算法性能上升趋势平稳, 所以VRBCH算法在不同数据量情况下的F-measure性能仍较为理想。在图 6中UNCF算法在数据量在30%到35%之间上升较缓,因为YouTube视频评论文本评分稀疏度为98.37%, 数据量较少,存在实验误差。相比较而言, 前期由于数据量过少,SequentialMF、UserCF、UNCF算法对数据稀疏性问题要求较高, 所以其F-measure性能比VRBCH性能低。

由于VRBCH算法中提出层次排序概念, 通过用户自己的行为来决定用户自己的兴趣爱好值, 避免视频关注点存在模糊多变的性质从而影响用户兴趣爱好评估的准确性,所以VRBCH算法在视频推荐上拥有良好的推荐性能。

4 结语

推荐系统是数据挖掘领域中一大热点, 本文改变了传统推荐算法利用项目评分来计算相似用户的方式,改为利用被推荐用户浏览视频的行为计算出用户对历史数据中视频的喜好程度, 通过被推荐用户的历史数据找出用户对视频的喜好标签, 从而成功地实现用户行为和喜好标签权重的转换, 避免了传统层次分析中用户自定义权重值。另外, 考虑到用户可能是新用户, 没有历史数据, 本研究从相似用户中找出最新最受喜爱的视频推荐给用户, 有效地避免了冷启动问题。最后形成的推荐集合中采用排序的形式, 提高了用户的体验度。实验结果表明, 本模型在RMSEF-measure这两个方面的性能获得提高, 基于MovieLens Latest Datasets和YouTube视频评论文本数据集与其他模型进行实验对比, 结果表明本文模型取得了良好的推荐效果。

值得注意的是, 本文算法还有许多要改进的方面:1) 聚类时计算量问题, 本文仅对少量的低维数据进行聚类, 在大数据环境中则需要引入分布式计算方法, 下一步会考虑在Spark平台下进行聚类尝试;2) 在用户聚类过程中为了提高聚类效果, 在数据归一化过程中对某些用户属性进行人为处理, 例如用户性别, 未来应从分类的角度出发提高分类精度, 由于可以离线计算, 节约大量实时计算资源;3) 在排序模型中针对历史数据处理粗糙, 降低了推荐精度和用户体验度;4) 在构建视频层对标签层影响过程中由于是非专业人士操作导致推荐结果误差较大。下一步计划利用机器学习内容构建自我学习的排序算法, 充分利用历史数据从而为推荐模型的实际应用起到促进作用。

参考文献(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-N recommendation 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. DOI:10.1109/TKDE.2013.7
[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. DOI:10.1126/science.1136800
[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] 杨兴耀, 于炯, 吐尔根·依布拉音, 等. 融合奇异性和扩散过程的协同过滤模型[J]. 软件学报, 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] 尹路通, 于炯, 鲁亮, 等. 融合评论分析和隐语义模型的视频推荐算法[J]. 计算机应用, 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. DOI:10.11772/j.issn.1001-9081.2015.11.3247)
[10] 孙光福, 吴乐, 刘淇, 等. 基于时序行为的协同过滤推荐算法[J]. 软件学报, 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加权M-估计量的鲁棒推荐算法[J]. 计算机学报, 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] 张燕平, 张顺, 钱付兰, 等. 基于用户声誉的鲁棒协同推荐算法[J]. 自动化学报, 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] 胡勋, 孟祥武, 张玉洁, 等. 一种融合项目特征和移动用户信任关系的推荐算法[J]. 软件学报, 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] 郭磊, 马军, 陈竹敏, 等. 一种结合推荐对象关联关系的社会化推荐算法[J]. 计算机学报, 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] 陈克寒, 韩盼盼, 吴健. 基于用户聚类的异构社交网络推荐算法[J]. 计算机学报, 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] 黄创光, 印鉴, 汪静, 等. 不确定近邻的协同过滤推荐算法[J]. 计算机学报, 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.)