网络电视推荐系统框架及协同过滤算法的研究

黄 乔，尹四清

(中北大学 电子与计算机科学技术学院，山西 太原030051)

随着互联网迅猛发展，网络电视媒体也逐渐走入了千家万户，面对其日趋成熟的发展，媒体内容不断丰富，资源量也在不断的增大，给用户在查找感兴趣内容时带来了不便。为解决了这个问题，引入了个性化推荐系统，其中的协同过滤推荐技术［1］应用比较广泛，它是假设用户A和用户B具有相似的兴趣度，即用户A感兴趣的内容，用户B同样感兴趣。在网络电视推荐系统中的协同过滤算法，是根据所有用户对已评分视频的评分记录来预测某一未评分视频的评分，把用户和视频之间的评分记录整理成一个用户—项目评分矩阵，再通过评分矩阵获取有价值的信息，进行一系列的计算之后产生一个推荐列表。但这种传统的推荐技术存在一些固有缺陷，例如，“稀疏性”问题、“冷启动”问题、“实时性”问题等［2-3］，针对这些问题，很多人都进行了研究，并提出了一系列的改进算法。本文提出了一种将聚类、用户相似—信任关系和项目属性关系相组合的协同过滤推荐算法，该推荐算法能够有效改善或克服传统协同过滤技术中出现的问题，为目标用户提供更好的推荐结果。实验结果表明，该算法能够降低预测与实际用户评分之间的平均绝对偏差，提高网络电视推荐系统的推荐质量。

1 网络电视推荐系统框架

网络电视推荐系统［4］框架如图1所示。

图1 网络电视推荐系统

1)Web服务器用来收集个人用户信息并储存到数据库服务器中，也可将产生的推荐页面呈现给用户。

2)数据库服务器主要用来存储各类数据信息数据库、用户信息数据库和用户资料数据库。

3)协同过滤推荐技术是该推荐系统的关键组成部分，主要通过对数据的处理，为用户产生满意的推荐结果。

2 改进的协同过滤推荐技术相关概念

本文提出的改进算法是将聚类、用户相似—信任关系和项目属性关系相组合的协同过滤推荐算法。首先，聚类用于缩小原始数据集，获得更有效的搜索空间，缓解推荐算法的实时性问题。其次，用户信任关系与用户相似度相结合，用于搜寻最近邻居用户，解决算法稀疏性、冷启动等问题。最后，基于项目属性的算法用于预测评分计算，得到影片推荐结果。

2.1 聚类

2.2 用户相似—信任关系

相对于推荐技术，人们更愿意通过朋友的介绍或向熟人打听有用的推荐信息，如果把信任的用户加到推荐技术的用户群里，那么利用该推荐技术推荐的信息就会更有价值。基于这个思想，把信任关系引入到推荐系统中。本文中的信任主要是表示当前用户对其他用户提供服务的评论。在本文中，信任度计算的数据来自于用户之间主观的信任评分，用户信任被评用户，值为1，否则为0，所构成的评分矩阵即为用户信任度矩阵Trust(i，j)。

根据某种相似度计算方法来计算用户之间的相关性sim(i，j)，得到用户之间的相似度矩阵Sim(i，j)。其实对于评分矩阵来说，就是计算两个行向量的相关性。计算相似度的方法［7］很多，通常用修正的余弦相似度公式，即

式中:Ric为用户i对项目c的评分，为用户i对项目的平均评分，为用户j对项目的平均评分。

经过各种研究表明，在同一应用领域下，用户的相似度和信任度存在相关性［8］。故将相似度和信任度线性结合，得到相似—信任度矩阵Q(i，j)=α×Sim(i，j)+(1-α)×Trust(i，j)，α＞0，其中α表示相似度的权重。再利用Q(i，j)来搜索当前用户的k个最近邻居用户。

2.3 项目属性关系

网络电视推荐系统中，影片的属性有类型、导演、主演、关键字等。本文将影片类型按照爱情片、喜剧片、惊悚片、科幻片、战争片等进行分类，每个分类作为项目属性矩阵的一维，如果影片属于该分类，则相应的值为1，否则为0，所构成的项目属性关系矩阵为Item(i，j)。

3 基于改进协同过滤的网络电视推荐系统的算法设计

3.1 数据准备

用户的注册信息、对视频的浏览记录和评分记录均被保存在数据库服务器中，根据数据库中的数据信息进行建模，产生用户—项目评分矩阵U×I［9］。

3.2 聚类

根据用户—项目评分矩阵进行聚类。聚类算法描述如下:

大石油公司围绕核心业务、重点资源类型构建勘探资产。埃克森美孚主要围绕深水、LNG和非常规在全球开展勘探业务。壳牌注重LNG和深水，巨资并购BG也是看中BG在深水和天然气领域的优质资产。埃尼、道达尔等规模相对较小的大石油公司重点发展深水。国际大石油公司在非常规领域并不占有先机，但通过并购有技术专长的美国本土小石油公司及自身研发来增强在非常规领域的技术实力。埃克森美孚、雪佛龙等美国本土公司都将页岩油气作为未来重回增长的重要领域，BP最近以105亿美元的价格击败壳牌获得了必和必拓在北美的页岩油气资产[9]。这都体现了国际大石油公司力图引领非常规的决心。

1)从数据源中随机选取h个用户作为聚类中心，记作{W1，W2，…，Wh}。并将h个聚类C1，C2，…，Ch初始化为空。

2)计算其余用户与聚类中心用户的相似性(距离)，选择相似性最高(即距离最短)的用户，划分到相应的聚类中。

3)根据聚类用户中所有对象的均值来确定一个新的聚类中心，转入步骤2)。

4)当每个聚类达到稳定后，即可得到所求的用户聚类C1，C2，…，Ch。

3.3 k最近邻用户搜索

1)在h个聚类用户C1，C2，…，Ch中检索目标用户u所在的聚类Cβ;

2)通过用户—用户信任矩阵T检索聚类Cβ的用户—用户信任矩阵T0=Trust(u，v)，即为信任度矩阵T0;

3)通过用户—项目评分矩阵S检索聚类Cβ的用户—项目评分矩阵D0，并进行相似度计算，得到相似度矩阵S=Sim(u，v);

4)由Q(i，j)=α×Sim(i，j)+(1-α)×Trust(i，j)，α＞0，得到信任—相似矩阵Q(i，j)，由Q(i，j)进行k最近邻用户搜索［9］，得到k个最近邻用户。

3.4 预测评分 产生推荐

1)由k最近邻用户整理出相关的项目属性关系矩阵Item(i，j)，利用基于项目属性的协同过滤推荐算法［9］对还未评分的项目进行预测评分计算。用户u对未评分项c的预测评分为［10］

式中:D为项目c的k个最近邻居集合;Rud表示用户u对项目d的评分;和分别表示用户c和用户d对项目的平均评分。

2)计算出项目的预测评分后，通过比较，选择评分最低的前N个项目作为最终的推荐结果，传送给Web服务器，反馈给用户。

4 实验及结果分析

实验平台使用CPU(Intel T2080 D-0 1.73G)，1 Gbyte内存，操作系统为Windows XP，语言为C++标准库和MATLAB。

4.1 实验数据

此次实验的数据集是一个著名的站点MovieLens提供的(http://movielens.umn.edu)，MovieLens是一个基于Web的研究型推荐系统，主要是用来记录用户对电影的评分等。数据集中包括用户关于视频的评分数据(评分值从1～5的整数)，用户之间信任关系评分数据(用户之间存在信任关系评分为1，否则为0)，整理出视频的属性关系(视频属于某一分类则值为1，否则为0)。

4.2 度量标准

本文采用的评价推荐系统推荐质量的标准是平均绝对偏差(Mean Absolute Error，MAE)［11］。通过计算用户的预测评分和实际评分之间的偏差，来评价预测的精确性，偏差值MAE越小，推荐质量就越高。设用户的预测评分集合为{p1，p2，…，pn}，用户实际评分为{s1，s2，…，sn}，平均绝对偏差MAE可通过下式计算得到

4.3 实验结果及分析

4.3.1 实验1

实验选取不同的权重值α来获得不同的推荐效果。取定推荐视频数n的值10。取最近邻居数k的值为15，20，25，30。设置控制相似度和信任度比例的变量α的取值为0，0.2，0.4，0.6，0.8，1.0，MAE值随着α值的变化而变化。结果如图2所示。

图2 实验1结果

从图2的实验结果，可以看出最近邻用户数目越多，预测评分和实际评分的平均绝对偏差MAE值最小，即推荐效果越好。在不同的邻居用户数下，当α取值接近0.7时都取得最好的推荐效果。

4.3.2 实验2

根据实验1中的结果，取推荐结果最好时，α的值为0.7。对改进的协同过滤推荐算法和传统的协同过滤推荐算法的性能进行比较。取最近邻居数k的值为10，15，20，25，30，观察MAE值。实验结果如图3所示。

图3 两种算法实验结果对比

MAE值越小，推荐效果越好，从实验结果可以看出，改进的协同过滤组合推荐算法的MAE值最小，可见本文提出的改进算法推荐性能优于传统算法。

5 结束语

网络电视正在快速发展，如何为用户提供更加准确和有效的信息是很重要的任务，个性化推荐系统是完成这一任务的关键。本文提出的改进算法，把聚类分析用于协同过滤推荐中，相对于原始用户空间而言，由聚类产生的用户搜索空间变小，从而使得最近邻用户搜索的效率变高，有效提高推荐算法的实时响应速度。首先，使用信任度与相似度结合作为搜索最近邻用户的标准将更加精确。其次，信任度的计算并不依赖于用户对视频的评分数量，即使评分数量不多，只要有用户之间的信任评分，就可以搜索到一定数量的邻居用户，并做出推荐，解决了“冷启动”问题。实验研究结果也表明，组合推荐算法更加精确，达到了更好的推荐效果。

［1］ADOMAVICIUS Q TUZHILIN A.Toward the next generation of recommender systems:a survey of the state-of-the-art and possible extensions［J］.IEEE Trans.on Knowledge and Data Engineering，2005，17(6):734-749.

［2］SARWAR B M.Sparsity，scalability，and distribution in recommender systems［D］.Minneapolis，MN:University of Minnesota，2001.

［3］YU Li，LIU Lu，LI Xuefeng.A hybrid collaborative filtering method for multiple-interests and multiple-content recommendation in e-commerce［J］.Expert Systems with Applications，2005，17(4):67-77.

［4］陈萌，杨成，王欢，等.交互式电视中个性化推荐系统的研究［J］.电视技术，2012，36(14):37-40.

［5］BRIN S，MOTWANI R，ULLMAN J D，et al.Dynamic itemset counting and implicate on rules for market basket data［C］//Proc.SIGMOD Record.California:［s.n.］，2007:33-43.

［6］谭勇，荣秋生.一个基于K-means的聚类算法的实现［J］.湖北民族学院学报，2004，22(1):69-71.

［7］ZHOU Qiang.Researches into recommendatory algorithm of coordinated filtration in view of consummers［J］.Journal of Nanchang Junior College，2006，15(3):88-89.

［8］GOLBECK J.Computing and applying trust in web-based social networks［D］.Maryland:University of Maryland，2005.

［9］曾子明，余小鹏.电子商务推荐系统与智能谈判技术［M］.武汉:武汉大学出版社，2008.

［10］徐翔，王煦法.协同过滤算法中的相似度优化方法［J］.计算机工程，2010，36(6 ):52-54.

［11］MCLAUGHLIN M R，HERLOCKER J L.A collaborative filtering algorithm and evaluation metric that accurately model the user experience［C］//Proc.27th annual international ACM SIGIR conference on Research and development in information retrieval.Sheffield，United Kingdom:ACM，2004:329-336.