《推荐网络分析及个性化推荐算法研究》由会员分享，可在线阅读，更多相关《推荐网络分析及个性化推荐算法研究（85页珍藏版）》请在金锄头文库上搜索。
1、 电 子 科 技 大 学 UNIVERSITY OF ELECTRONIC SCIENCE AND TECHNOLOGY OF CHINA 硕士学位论文 MASTER THESIS 论文题目 推荐网络分析及个性化推荐算法研究 学 科 专 业 计算机软件与理论 学 号 201121060354 作 者 姓 名 关远 指 导 教 师 尚明生 教授分类号 密级 UDC注1 学 位 论 文 推荐网络分析及个性化推荐算法研究 （题名和副题名） 关远 （作者姓名） 指导教师 尚明生 教 授 电子科技大学 成 都 （姓名、职称、单位名称） 申请学位级别 硕士 学科专业 计算机软件与理论 提交论文日期 201
2、4.03.27 论文答辩日期 2014.05.14 学位授予单位和日期 电子科技大学 2014 年 06 月 日 答辩委员会主席 评阅人 注 1：注明国际十进分类法 UDC的类号。ANALYSIS OF RECOMMENDATION NETWORK AND RESEARCH OF PERSONALIZED RECOMMENDATION ALGORITHMS A Master Thesis Submitted to University of Electronic Science and Technology of China Major: Computer Software and Theor
3、y Author: Guan Yuan Advisor: Professor Shang Mingsheng School : School of Computer Science 1,2,.,)iAaiNM来表示， 其中矩阵中的一行代表一个用户结点， 矩阵中的一列代表一个产品结点。 其中的元素,1ia表示用户i喜欢产品，反之表明用户不喜欢该产品（本文使用拉丁字母和希腊字母分别表示用户索引和产品索引）。 3.2.1 基于产品流行性的推荐算法 基于商品流行性的推荐算法 Popular 是典型的非个性化推荐算法的代表。Popular 算法将当前被用户选择次数最多，也就是最受欢迎的产品推荐给用户。该
4、算法的实现首先需要对产品的度（产品当前被选择的次数）进行统计，然后按照产品度从大到小的顺序进行排序，排除掉用户已经选择过的产品，将其他产品推荐给用户。由于即使是最活跃的用户，相比于系统中数目庞大的产品集合也仅仅是一小部分，所以推荐系统将呈现给用户基本相同的推荐结果。 3.2.2 基于用户的协同过滤算法 基于用户的协同过滤推荐算法（User Based Collaborative filtering, 简称 UCF）的基本思路21是“相似的用户喜欢相似的产品”。推荐系统将把和目标用户相似的用户所喜欢的产品推荐给目标用户。首先计算用户间的相似度，见公式（3-1） 。 ( , )ijijIIs i
5、jkk（3-1）其中，iI表示用户i选择过的产品集合，ik是用户i的度，显然iikI。求出目标用户与其他用户的相似度之后，即可进行预测评分。UCF 为用户i预测产品的得第三章 用户级个性化推荐算法 21 分见公式（3-2） 。 , 1( , ) Nij jps i j a（3-2）3.2.3 基于产品的协同过滤算法 基于产品的协同过滤算法(Item Based Collaborative filtering, 简称 ICF)的基本思路是，用户喜欢跟先前选择过的产品相似的产品。ICF22首先计算产品之间的相似度并基于相似度进行预测评分。 产品间的相似度如公式 （3-3） 所定义。 其中，U表示选
6、择过产品的用户集合，k是用户的度，显然kU。 ( ,) UUskk（3-3）根据产品的相似度，即可进行预测评分，参照公式（3-4）。 , 1( ,) Miipsa（3-4）3.2.4 物质扩散算法 不同于基于产品的协同过滤算法 ICF，物质扩散算法（简称 Diffuse 算法）引入了一个资源分配矩阵W， 其中的元素表示资源从拥有资源的产品到目标产品的传播概率，类似于 ICF 中的产品相似度矩阵。物质扩散算法计算产品间相似度的公式参照公式（3-5） ： 11( ,) MjjDjja askk（3-5） 物质扩散算法将用户对产品的偏好信息建模为二部图网络，推荐算法是资源在该二部图上的传播机制。目标
7、用户被赋予一定的初始资源，而目标用户得到的最终资源反映了用户对产品的偏好程度。算法为用户i预测产品的得分的计算机制见公式（3-6） ： , 1( ,) Miiipfsa（3-6） 电子科技大学硕士学位论文 22 3.2.5 热传导算法 类似于物质扩散算法，热传导算法同样引入了资源分配矩阵W，但资源从拥有资源的产品到目标产品的传播概率发生了改变，热传导算法计算产品间相似度的机制见公式（3-7） ： 11( ,) MjjHjja askk（3-7）而目标用户得到的最终资源的计算，与物质扩散算法相同，见公式（3-6） 。 3.2.6 用户级的个性化推荐算法 本文提出用户级的个性化推荐算法，即同一系统
8、中的用户可以使用不同的推荐算法。本文将以上提到的 Popular、UCF、ICF、Diffuse 以及 HeatS 算法考虑为推荐系统的候选算法。这些算法各有优劣，并没有绝对的赢家。用户级的个性化推荐系统，将根据用户自身的特性，为用户匹配其最佳的推荐算法（候选算法中为用户推荐效果最好的一个） 。后文中理想推荐算法是指，使得每个用户匹配到其最佳推荐算法的推荐机制。 3.3 实验设计 本文给出进行实验设计采用的数据集和评价指标，并阐述实验方法和过程。实验中选择了三种用户特性指标。 3.3.1 实验数据 本文使用 MovieLens 数据集来测试推荐算法的性能。MovieLens （http:/ m
9、ovielens.umn.edu）是一个电影推荐网站，用户对电影进行评分，评分等级从 1-5。评分为 1 表明用户不喜欢该电影；评分为 5 表示用户非常喜欢该电影。MovieLens100K 数据集包含 943 个用户对 1682 部电影的 10 万条评分记录。本文中对 MovieLens 数据集进行粗粒度化处理，即忽略小于 3 分的评分，只关注用户喜欢的部分。处理后的数据集统计信息见表 3-1，其中稀疏度定义为|E|/(M*N)，|E|是数据集的边数，M=|U|是用户数，N=|O|是产品数。 表 3-1 数据集的统计信息 数据集 |U| |O| |E| 稀疏度 MovieLens100K 9
10、43 1572 82520 5.20*10-2 第三章 用户级个性化推荐算法 23 3.3.2 评价指标 本文采用 AUC、RS 和 precision 来衡量推荐算法的效果，它们被广泛用于二部图网络的推荐中。 AUC 指标用来衡量一个推荐算法能够在多大程度上将用户喜欢的产品与不喜欢的产品区分出来52，近似估计 AUC 的步骤如下： （1） 随机从用户喜欢的商品（测试集中的产品）中选取一个商品 （2） 随机选择一个不相关商品(没有出现在训练集和测试集中的产品) （3） 若相关产品的预测评分大于不相关产品，则加 1；若相关产品的预测评分与不相关产品的预测评分相等，则加 0.5。 （4） 重复步骤
11、 1-3，一共进行 n 次选择和比较。 如果在 n 次比较中，相关产品预测评分大于不相关产品，这种情况出现的次数为 n次；相关产品的预测评分与不相关产品的预测评分相等，这种情况发生了 n次，那么所求 AUC 的值见公式（3-8）： 0.5 nnAUCn （3-8）平均排序分41通过统计用户喜欢的产品在推荐列表中的位置，能够衡量推荐算法预测用户喜欢产品的能力，见公式（3-9） ： ( , ) ( , ) i i irRSL（3-9）其中，( , )ir表示测试集中的边( , )i在用户i的推荐列表中的排序位置，iL是用户i的推荐列表长度，表示用户i未选择过的产品数目。 准确率 precision
12、 衡量推荐系统能够正确预测用户喜欢或者不喜欢某个商品的能力， 它关注推荐列表的前 L 个结果。 若用( )iH L表示用户i的前L个推荐列表中，用户喜欢的产品个数。那么用户i的准确率见公式（3-10） ： ( )( ) i iH LP LL（3-10） 3.3.3 实验方法和过程 1. 为了测试不同算法的表现，本文按照训练集：测试集=9:1 的比例对数据集进行了随机划分。实验对数据集进行了 5 次划分，最终的实验结果取 5 次实验的平均。 2. 为了考察用户级个性化推荐算法的研究意义，本文对此机制的推荐效果进电子科技大学硕士学位论文 24 行统计。通过对所有用户按照不同推荐机制进行推荐的结果进
13、行评估，可以获得每个用户的最佳推荐算法。令所有用户均采用其最佳推荐算法进行推荐，本文将此称为理想算法，将得到的推荐效果与各单一推荐机制进行对比。 3. 为了说明用户级个性化推荐算法的必要性，本文对用户各自的最佳推荐算法进行统计。通过对所有用户按照不同推荐机制进行推荐的结果进行评估，获得每个用户的最佳推荐算法。将所有用户按照其最佳推荐算法进行分类，得到 5 个对应的用户类，依次命名为 Popular、UCF、ICF、Diffuse 和 HeatS。 4. 为了得到用户的最佳推荐算法，本文对用户特性与其最佳推荐算法进行关联。实验中使用用户的度（ik） ，用户选择产品的平均度（id） ，以及用户选择
14、产品的平均相似性（is）来刻画用户特性。之所以选择上述 3 个指标，是基于这样的常识：较好地符合用户过去偏好的推荐机制，可以预测用户未来的选择行为。例如，小度的用户一般是潮流跟随者，而拥有丰富经验的大度用户则会根据自己的兴趣主动挑选一些自己喜欢的冷门产品。过去喜欢选择流行产品的用户，在未来的行为中也会对流行产品有所偏好。为用户推荐与先前所选产品相似的产品，有望使用户满意。通过对用户进行分类，探寻类内用户的共同点，以及类间用户的不同点在用户特性上的体现。 5. 为了使用户级个性化推荐算法更具有针对性，本文单独对敏感用户的最佳推荐算法进行了研究。这些用户的最优推荐算法相比于其他候选算法，表现非常突
15、出，为这些用户匹配最佳推荐算法将对推荐效果有直接且显著提高。可以通过统计用户的最优推荐算法和次优推荐算法的差别，找到最优推荐算法相比次优推荐算法提高幅度大于 10%的用户，即为敏感用户。 6. 为了考察最佳推荐算法选择依据对用户特性与最佳算法关联性的影响，本文改变最佳推荐算法的选择依据为用户级的 RS 指标，进行了若干实验。 7. 为了考察以 precision 指标作为最佳推荐算法选择依据对实验结果的影响，本文以用户级 precision 作为算法选择依据进行了若干实验。实验中变化 L 的取值分别为 1、2、5、8、10、20、50、80、100。 3.4 实验结果及分析 通过实验，可以得到以下结论： 1. 理想算法相比单一推荐机制，推荐效果显著提高。 2. 用户的最佳个性化推荐算法互异。 3. 用户特性与其最佳推荐算法的关联性有待继续探
