201513

Size: px

Start display at page:

Download "201513"

接纵蒙
5 years ago
Views:

1 Computer Engineering and Applications 计算机工程与应用 2015,51(13) 111 数据库数据挖掘机器学习基于云计算技术的个性化推荐系统应 1,2 毅, 刘亚军 3 4, 陈诚 YING Yi 1,2, LIU Yajun 3, CHEN Cheng 4 1. 三江学院软件学院, 南京三江学院计算机科学与工程学院, 南京东南大学计算机科学与工程学院, 南京易立方教育科技有限公司, 南京 School of Software, Sanjiang University, Nanjing , China 2.College of Computer Science and Technology, Sanjiang University, Nanjing , China 3.School of Computer Science and Engineering, Southeast University, Nanjing , China 4.eCube Education Technology Co., Ltd., Nanjing , China YING Yi, LIU Yajun, CHEN Cheng. Personalization recommender system based on cloud-computing technology. Computer Engineering and Applications, 2015, 51(13): Abstract:Traditional collaborative filtering recommendation technology works poor under the environment of bigdata. To solve this problem, a personalized recommendation method based on cloud-computing technology is proposed. In this method, the large dataset and recommended calculation will be decomposed into multiple computers for parallel processing. It uses the open source framework Hadoop to establish a parallel recommendation engine on the basis of the classical ItemCF algorithm with MapReduce technology. The effectiveness of this system has already been verified on English training platforms by recommending learning resources. Experimental results indicate that the use of cloud-computing technology in the cluster to process massive data can significantly improve the scalability of Recommender Systems. Key words:recommender systems; item-based collaborative filtering; MapReduce; ItemCF-MR algorithm; learning resources recommend 摘要 : 传统的协同过滤推荐技术在大数据环境下存在一定的不足针对该问题, 提出了一种基于云计算技术的个性化推荐方法 : 将大数据集和推荐计算分解到多台计算机上并行处理在对经典 ItemCF 算法 MapReduce 化后, 建立了一个基于 Hadoop 开源框架的并行推荐引擎, 并通过在已商用的英语训练平台上进行学习推荐工作验证了该系统的有效性实验结果表明, 在集群中使用云计算技术处理海量数据, 可以大大提高推荐系统的可扩展性关键词 : 推荐系统 ; 基于物品的协同过滤 ;MapReduce;ItemCF-MR 算法 ; 学习资源推荐文献标志码 :A 中图分类号 :TP39 doi: /j.issn 引言信息过载 (information overload) 是 Web2.0 技术被广泛应用之后, 互联网用户和移动互联网用户所面临的最严重问题之一据 EMC 公司的 Digital Universe 项基金项目 : 横向课题智能英语语言训练系统 ; 江苏省电力公司科技项目 (No.J ); 江苏省高等学校软件服务外包类专业嵌入式人才培养项目 ( 苏教高函 [2014]8 号 ); 江苏省卓越工程师 ( 软件类 ) 计划试点专业项目 ( 苏教高函 [2012]17 号 ); 三江大学本科工程二期项目 (No.J14001) 作者简介 : 应毅 (1979 ), 男, 讲师, 主要研究领域为大数据处理与数据库 ; 刘亚军 (1953 ), 女, 教授, 硕士生导师, 主要研究领域为软件工程与数据库应用 ; 陈诚 (1989 ), 男, 助理工程师, 主要研究领域为推荐引擎与 Java 平台 @qq.com 收稿日期 : 修回日期 : 文章编号 : (2015) CNKI 网络优先出版 : ,

2 ,51(13) Computer Engineering and Applications 计算机工程与应用目统计,2010 年 2011 年全球新增数据总量分别为 1.2 ZB 和 1.8 ZB,2012 年数据总量高达 2.8 ZB [1-2] [3] 推荐系统建立在推荐技术和数据挖掘理论基础上, 根据用户的兴趣特征, 从海量信息中挖掘用户可能感兴趣或需要的资源, 并对用户做出相应的推荐主流的推荐技术主要包括以下几种 : 基于内容的推荐基于用户统计信息的推荐基于协同过滤的推荐基于关联 [4] 规则的推荐协同过滤推荐是个性化推荐系统中应用最为成功的技术之一, 它利用兴趣相同或拥有共同经验的群体的偏好来为用户推荐感兴趣的物品或资源, 它的最大优点是数据依赖性低协同过滤推荐主要分为三类 : 基于用户 (User-based) 的协同过滤基于物品 (Itembased) 的协同过滤 [5-6] 基于模型的协同过滤当前, 随着 Web 应用系统规模的不断扩大, 协同过滤推荐技术面临多方面的挑战, 主要有 :(1) 数据稀疏性问题面对海量数据, 一般用户的评价信息所涉及到的物品只占物品总数的 1%~2%, 经两个用户共同评价的物品更少, 评估矩阵数据相当稀疏, 难以找到用户或物品的最近邻居, 推荐质量降低严重 (2) 可扩展性问题协同过滤算法需要在整个数据空间上进行全量计算, 当数据量较小时, 能够在合适的时间内获得比较好的推荐效果, 但对于拥有上百万用户 / 物品的系统, 算法会遇到严重的扩展性问题, 该问题直接影响推荐系统的实时性和准确性 (3) 硬件条件制约问题传统的推荐技术都是针对单机运行模式的, 面对超大数据集时, 很容易受到 CPU 速度存储容量等计算机硬件条件的制约为了解决推荐计算的性能问题, 国内外学者做了大量的研究工作 : 文献 [7] 提出了基于多通道扩散的协同过滤算法 ; 文献 [8-9] 通过聚类贝叶斯网络减少计算空间 ; 文献 [10] 提出通过奇异值分解 (SVD) 的方法减小 User-Item 矩阵的维度这些工作提高了推荐系统的处理能力, 但或多或少都有自身难以解决的问题, 例如 SVD 算法提高了推荐系统的扩展能力, 但降维会导致信息损失, 同时也降低了推荐质量, 在物品空间维数很高的情况下, 降维的效果难以保证云计算技术是解决海量数据问题的另一个手段文献 [11] 在 Hadoop 上实现了 User-based CF 算法的并行化 ; 文献 [12] 讨论了使用云计算技术在移动网络中进行商务推荐的框架 ; 文献 [13] 研究了使用 Hadoop 在电子商务领域进行推荐的方案 ; 国立成功大学为数字电视节目平台构建了一个云编程推荐系统 CPRS [14] 上述研究都是通过云计算的大规模并行计算能力来解决在海量数据中进行推荐的效率问题本文提出了 ItemCF-MR 算法在学习资源推荐方面的理论和应用首先讨论了 ItemCF 算法的理论和执行过程, 然后提出一种基于 MapReduce 编程模型的 ItemCF 算法, 最后给出了基于 Hadoop 框架的混合推荐系统, 并结合英语训练平台, 对该系统进行了测试和效果分析实验证明,ItemCF-MR 算法具有良好的可扩展性 2 基于物品的协同过滤算法 2.1 ItemCF 算法理论基于物品的协同过滤算法是目前工业界应用最多的算法, 它通过分析用户的历史行为来计算物品间的相似度 ItemCF 算法主要分为两步 :(1) 计算物品间的相似度 ;(2) 根据用户历史行为和物品相似度计算用户的推荐列表度量物品之间相似性的方法有多种挖掘长尾信息是推荐系统的目标之一, 为了避免推荐出热门物品, 可以用余弦相似度定义物品 i 和物品 j 的相似度 : N(i) N( j) w ij = (1) N(i) N( j) 假设系统中有 m 个物品, 如下公式计算用户 u 对物品 i 的兴趣, 其中,r uj 表示用户 u 对物品 j 的兴趣 m P ui = åw ij r uj (2) j = ItemCF 算法的执行过程从理论上看,ItemCF 算法较为简单, 但是推荐系统通常都是应用于电子商务平台社交网络等大数据环境, 不管是用户量还是物品数量, 都非常巨大, 这就要考虑计算的复杂性和可行性常见的 ItemCF 算法的执行过程如下 : (1) 从用户的行为记录中获取用户感兴趣的物品列表 (2) 得到每个用户的个人共现矩阵 (3) 将所有用户的个人共现矩阵相加, 得到系统的物品共现矩阵 C m m C[i][ j] 被称为协同因子 (4) 对共现矩阵中每一个不为 0 的元素计算物品的余弦相似度, 得到物品之间的余弦相似度矩阵 W m m 阵 R (5) 从用户的行为记录中获取用户对物品的偏好矩 (6) 物品相似度矩阵偏好矩阵该矩阵乘法的结果是一个 m n 的矩阵 P,P[i][ j] 表示用户 j 对物品 i 的兴趣值 W m m R m n = P m n (3) (7) 对矩阵 P 的每一列进行排序, 同时剔除用户已评分的物品, 即得到针对每个用户的 TopN 推荐结果 3 基于云计算技术的 ItemCF 算法改进 3.1 云计算技术云计算是能够提供动态资源池虚拟化和高可用性的下一代计算平台, 具有数据高可靠性可扩展性经济性等特征 Hadoop 是一种基于批处理技术的开源云计算平台, 由 HDFS [15] 和 Hadoop MapReduce 两个核心部件组

3 应毅, 刘亚军, 陈诚 : 基于云计算技术的个性化推荐系统 2015,51(13) 113 成 MapReduce [16] 把以往通用的以 MPI/PVM 为基础的并行计算技术理念加以简化和提炼, 形成了能并发处理海量数据的并行编程模型, 同时也是一种任务调度模型, 特别适合于大数据的搜索挖掘分析和机器智能学习 3.2 大矩阵的存储方式至 2012 年 12 月底, 新浪微博注册用户数超 5 亿, 日 [17] 活跃用户万, 如果要深入了解用户的共同特征, 就需要构造 n n 的用户相似度矩阵, 在这个例子中, 矩阵的维度即为万万大矩阵计算是 Web 智能计算的常见形态使用常见的二维数组存储大矩阵将会造成海量数据所幸 Web 应用中的大矩阵多为稀疏矩阵 : 如 Each- Movie 网站评估数目占总数的比例为 2.37%;MovieLens 站点评分数据占总数的比例为 5.14% [18] 通常认为矩阵 M 的稀疏因子 δ(m ) 5% 时,M 为稀疏矩阵对于稀疏矩阵, 更好的方法是只存储那些非零的数据对于矩阵的每一个元素, 用一个三元组表示 : (i j V i j ) 其中,i 表示行坐标,j 表示列坐标,V i j 表示元素的值 3.3 ItemCF-MR 算法协同过滤算法虽然思想简单, 但其计算复杂度是非常高的, 面对大数据环境, 可扩展性问题已成为制约推荐系统发展的原因之一并行化是解决协同过滤算法可扩展性问题的有效途径, 在云计算环境下, 计算可以被划分成多个子任务, 理论上随着集群中结点数量的增加, 其效率呈线性增长, 这样可以大大提高推荐系统的可扩展性基于 2.2 节的分析, 本文利用云计算并行执行的特点, 对 ItemCF 算法进行改进, 用 MapReduce 编程模型重新设计实现, 通过执行多个 MapReduce 任务的方式实现推荐计算, 称作基于 MapReduce 编程模型的 ItemCF 算法 (Item-based Collaborative Filtering base MapReduce, ItemCF-MR) 该算法步骤如算法 1 所示算法 1 ItemCF-MR 算法 1. 输入 : 用户对物品评分的三元组文件 (UserID,ItemID, Preference) 2. 输出 : 用户对物品的兴趣值文件 Key/Value 形式 (ItemID, UserID/Recommendation) 3. 根据用户对物品的评分数据, 使用 MapReduce 并行化计算个人共现矩阵 4. Mapper: 收集单一用户的评分物品集合 5. Reducer: 两层迭代计算物品对 6. 根据个人共现矩阵, 使用 MapReduce 并行化计算物品共现矩阵 C m m 7. Mapper:NULL 8. Reducer: 对同一物品对累加求和 9. 根据 C m m 和用户行为记录, 依据公式 (1), 计算物品余弦相似度矩阵 W m m 10. 使用 MapReduce 并行化计算用户兴趣矩阵 P m n, P m n 是 W m m 和偏好矩阵 R m n 的乘积 11. Mapper: 收集计算 p ik 所需要的元素 12. Reducer: 根据公式 (4), 计算 w ij 向量和 r jk 向量的点积 13. 对兴趣值文件剔除无效数据下面详述每一个步骤的具体工作 (1) 计算个人共现矩阵给用户和物品唯一编号 UserID 和 ItemID, 用户对物品的行为用字段 Preference 保存, 三元组 (UserID, ItemID,Preference) 表示用户对某一个具体物品的评分, 它以文件的形式存储在 HDFS 中 Map 函数抽取正反馈数据, 输出的 Key/Value 是 :UserID/ItemID Reduce 的输入是用户感兴趣的物品集合 :UserID/ItemID 1 ItemID 2 ItemID n Reduce 函数计算单个用户的协同因子, 它对物品集合进行两层嵌套的循环操作, 得到所有的物品对, 输出的 Key/Value 是 :ItemID i /1, 它表明有一个同时喜欢物品 i 和物品 j 的用户该算法步骤如算法 2 所示算法 2 个人共现矩阵的 MR 算法 1.map(key,value) 2. if value.preference>0 then // 正反馈 3. output(value.userid/value.itemid) 4.reduce(key,values) 5. for ItemID i in values 6. for ItemID j in values 7. if ItemID i! = ItemID j then 8. output(itemid i ItemID j /1) 9. output(itemid j ItemID i /1) (2) 计算物品共现矩阵 C m m 第二次 MapReduce 计算的输入是上一次 MapReduce 的输出 :ItemID i /1 Map 函数为空 Reduce 的输入是相同的 ItemID i, 将其累加, 得到物品 i 和物品 j 的协同因子, 输出的 Key/Value 是 :ItemID i, ItemID j /n, 它表明在系统中同时喜欢物品 i 和物品 j 的用户有 n 个该算法步骤如算法 3 所示算法 3 物品共现矩阵的 MR 算法 1.map(key,value) 2. NULL 3.reduce(key,values) 4. i 0 5. for val in values 6. i++ // 统计 val 的个数 7. output(key/i) (3) 计算物品余弦相似度矩阵 W m m 根据 C m m, 对其中每个元素, 使用公式 (1), 计算余弦相似度计算时, 喜欢物品 i 的用户数 N(i) 可以从用

4 ,51(13) Computer Engineering and Applications 计算机工程与应用户的行为记录中统计, 并将其缓存, 减少查询的次数这一步是在主节点上串行地执行对于 W m m 的 HDFS 文件, 为了与偏好矩阵相区别, 在坐标之前加一个矩阵标识 W :W,ItemID i /Similarity (4) 计算用户兴趣矩阵 P m n 偏好矩阵 R m n 来自于用户的行为记录, 它是一个 Key/Value 形式 :R,ItemID,UserID/Preference 与共现矩阵不同,Preference 可以是正值 ( 正反馈 ), 也可以是负值 ( 负反馈 ) 第三次 MapReduce 完成物品相似度矩阵 W m m 和偏好矩阵 R m n 的矩阵乘法由于矩阵相乘的特点, 结果 P 中各元素的计算是相互独立的, 矩阵 W 或矩阵 R 中的一个元素会对矩阵 P 中的多个元素有影响, 因此一个输入元素将会转变为多个 Key/Value 对,Key 的形式是 i,k Map 函数对 W m m 每个元素 w ij, 产生多个 Key/Value : i,k/w,j,w ij, 其中 K = 1 2 n ; 同理, 对 R m n 每个元素 r jk, 产生多个 Key/Value :I,k/R,j,r jk, 其中 I = 1 2 m Reduce 函数接收到的 Value 一部分是 W,j,w ij, 一部分是 R,j,r jk 需要将相同 j 值的 w ij 和 r jk 相乘, 并求和, 即得到矩阵 P m n 中坐标为 i,k 的元素的值如公式 (4) 所示 Reduce 函数的输出为 :i,k/p ik m p ik = å(w ij r jk ) (4) j = 1 算法步骤如下所示 : 算法 4 用户兴趣矩阵的 MR 算法 1.map(key,value) // 收集计算相同 key 的元素 2. if key.target is W // 来自相似度矩阵 3. then 4. for i 1 to n do 5. output(itemid i,i/w,similarity) 6. else if key.target is R // 来自偏好矩阵 MasterNode 7. for i 1 to m do 8. output(i,userid/r,itemid,preference) 9.reduce(key,values) // 解析收集到的元素并计算 p ik 10. for value in values 11. if value.target is W 12. then 13. w[value.itemid j ] value.similarity // 来自矩阵 W 的元素放入一个数组 14. else if value.target is R 15. r[value.itemid] value.preference // 来自矩阵 R 的元素放入一个数组 16. for i 1 to m do 17. sum sum + w[i] r[i] // 计算向量的点积 18. output(key/sum) (5) 优化推荐结果 P m n 的输出 :ItemID,UserID/Recommendation, 表示用户对物品的偏好程度, 剔除负值并剔除用户已评分物品, 即可得到最终的推荐结果以上通过 3 次 MapReduce 计算和 2 次批处理完成了 ItemCF-MR 算法的全量计算 5 个子算法中, 最为复杂的是用户兴趣矩阵的计算, 它用一个单轮 MapReduce 完成矩阵乘法理论上分析,W m m 和 R m n 相乘的时间复杂度为 O(m m n), 但在推荐系统中矩阵通常极为稀疏, 单机中用三元组表示的稀疏矩阵相乘的时间复杂度为 O(m n (1 + m δ(w ) δ(r))), 这要比理论上的复杂度低在并行系统中, 每个计算单元的执行任务都非常简单, 算法的时间耗费主要在通信开销上对于 nz(m ) = O(n) 的稀疏矩阵, 每条数据会被发送 n 次, 总的网络传输是 O(n 2 ) [19] 这比单机的稀疏矩阵乘法的计算复杂度要低 3.4 基于 Hadoop 的推荐引擎依托上述 ItemCF-MR 算法, 以 Hadoop 框架为基础, 本文设计了基于云计算技术的个性化推荐系统, 其整体结构如图 1 所示系统中的节点分为两类 : 主节点 DBServer 推荐引擎算法库 Java Application 行为提取过滤用户行为日志用户属性相关表 JobTracker NameNode 排名物品属性相关表推荐结果相关表 SlaveNode1 SlaveNode2 SlaveNoden TaskTracker DataNode TaskTracker DataNode TaskTracker DataNode 图 1 基于 Hadoop 的个性化推荐系统

5 应毅, 刘亚军, 陈诚 : 基于云计算技术的个性化推荐系统 2015,51(13) 115 (MasterNode) 和从节点 (SlaveNode) 主节点由 NameNode JobTracker 推荐引擎算法库 Java Application 组成, 在系统中只有一个从节点由 DataNode TaskTracker 组成, 负责实际的计算工作和存储工作, 在系统中可以有任意多个 NameNode 是 HDFS 的管理者, 负责管理文件系统的集群配置信息命名空间和 Block 复制等 NameNode 会将文件系统的 Metadata 存储在内存中, 这些信息主要包括了文件信息每一个文件对应 Block 的信息和每一个文件块到 DataNode 的映射信息等 DataNode 是文件实际存储的基本单元, 它将文件块存储在本地系统中, 并保存文件块的 Metadata 推荐引擎算法库负责存储 ItemCF-MR 算法和批处理算法, 为了利用云计算分布式的特点, 其中需要并行执行的算法必须使用 MapReduce 编程模型重新设计实现并行算法放入 MasterNode 的算法库中,JobTracker 会自动将其分发至各 SlaveNode, 供 TaskTracker 执行时使用批处理算法用 Java 语言实现, 由 Java Application 执行, 它负责从数据库服务器中抽取用户行为日志, 形成 HDFS 文件, 交给分布式推荐引擎处理, 最后再将推荐结果回写到数据库服务器的相关表中 JobTracker 和 TaskTracker 采用主 - 从工作结构,Job- Tracker 的职责是启动跟踪和调度各个 SlaveNode 的任务执行 ;TaskTracker 负责在 SlaveNode 上根据应用要求对本地数据进行处理, 并将状态和完成的信息汇报给 JobTracker 从功能上划分,NameNode DataNode DBServer 形成了系统的存储部件,JobTracker 推荐引擎算法库 TaskTracker Java Application 形成了系统的计算部件整个系统使用普通 PC 作为硬件设备, 节点间通过 100 Mb/s 网络连接, 以 Hadoop 作为基础, 搭建在 CentOS 5.5 之上 4 应用实例 4.1 英语训练平台中的混合推荐系统英语训练平台是一套依赖于庞大的规范化的英语教学资源库和英语测试题库的智能化个性化的在线学习系统, 它为大学英语教学提供课前预习课后复习作业测试等信息化支持系统载有近 25 万道作业题试题和相关资源, 并以每年道的速度增长由于种类丰富数量庞大, 学生在使用过程中出现了选择困难, 有必要向使用者提供个性化的学习推荐内容学习推 [20] 荐能在合适的时机, 将合适的内容, 推荐给合适的学习者, 为学习者的学习活动提供个性化支持, 激发学习者的学习兴趣, 并使学习者对系统产生依赖和搜索引擎不同, 个性化推荐系统需要依赖用户的行为数据, 因此一般都是作为一个应用存在于不同网站之中如图 2 所示, 英语训练平台向用户提供 Web 页面并和用户交互用户在系统中的大部分操作 ( 例如做作业阅读文章给题目评分 ) 都会被记录到用户日志和数据库中推荐系统获取日志和表数据, 分析用户的行为数据, 进行挖掘和计算, 得到推荐物品列表, 并记录到数据库中, 最终展现到页面上推荐系统图 2 为了避免协同过滤推荐存在的冷启动问题 [13], 系统在 ItemCF-MR 算法的基础上, 结合了基于人口统计学的推荐和专家推荐这两种技术作为补充,3 种机制使用推荐结果混合方式构建 [21], 如图 3 所示基于人口统计学的推荐是粗粒度的个性化推荐技术, 针对学生用户的特征, 在性别年级专业这 3 个维度上进行分类, 并将学习资源与各分类进行关联标注, 对新用户主要使用这种推荐方式英语专家推荐是一种大众化推荐方法, 主要针对热门物品进行, 例如 : 刚结束的英语四六级考试试题纽约时报对当前流行事件的报道和评论等同时, 为了提高推荐效果, 降低复杂度, 本次实验只对阅读和听力题型进行了学习推荐用户属性基于人口统计学的推荐图 3 用户的行为数据主要存储在偏好行为表 Preference 中, 该表最主要的是 3 个字段 :UserID ItemID PreferenceValue PreferenceValue 是一个 int 值, 来自于用户的隐性反馈和显性反馈隐性反馈行为包括 : 做完收藏下载 ; 显性反馈行为主要是评分, 这是一个英语语言的学习和训练平台, 用户只有在特别不满或者特别满意时才会评分, 因此系统使用了二级评分机制顶 / 踩, 各分值如表 1 所示日志数据存储英语训练系统推荐结果用户界面推荐引擎位于整个系统的后端新用户行为日志基于物品的协同过滤推荐初始推荐集过滤排名推荐列表普通用户混合推荐引擎的工作流程物品属性专家推荐补充推荐集

6 ,51(13) Computer Engineering and Applications 计算机工程与应用做完 0.5 分最后的推荐结果存储到推荐表 Recommend 中, 该表最主要的是 3 个字段 :UserID ItemID RecommendValue RecommendValue 是推荐值, 当需要展现推荐列表时, 根据该值排序, 并取前 N 个, 即可进行 TopN 推荐 4.2 运行环境与效果评价基于上述需求, 推荐集群系统由 8 台普通 PC(Intel i5 3.2 GHz CPU,4 GB RAM) 组成, 其中 1 台为主节点,6 台为从节点,1 台为数据库服务器 (1) 加速比实验 : 该实验评估增加计算节点对系统性能的影响根据从节点的个数不同, 实验分为 4 组场景 :1 个 2 个 4 个或 6 个从节点 ( 如图 4) 为了衡量并行效果, 首先定义加速比 S P 的概念 : S P = T 1 T P (5) 其中 T P 代表 ItemCF-MR 算法在集群 (P 个从节点 ) 上运行所花费的时间,T 1 代表 ItemCF-MR 算法在单机 ( 只启动 1 个从节点 ) 上运行所花费的时间 Speedup 表 1 隐性反馈数据收藏 1 分由于 ItemCF-MR 算法会将矩阵计算平均的分配到 P 个从节点上运行, 理论上加速比应该等于 P 但从实验结果可以看出, 实际运行时没有达到这个效果主要是由于除了并行的矩阵运算外, 还有主节点上的批处理计算 ; 各节点之间的通信和同步等开销也不可忽视不过即使如此, 加速比也基本接近于 P, 并呈线性增长 (2) 并行效率实验 : 该实验评估问题规模增大时算法的可扩展性并行效率指标 E 能反映并行系统的加速比接近计算节点数 P 的程度其中,T 0 为系统总并行开销, 包括通信数据同步和从节点空转等时间代价, 它通常是计算数据规模和从节点个数的函数 E = S P P = T 0 T 1 各行为数据分值下载 1 分显性反馈数据 (6) 实验在从节点个数不同的情况下 (2 个 4 个或 6 个 ), 对不同的数据集 (Item 规模分别为顶 1 分踩 -1 分图 4 集群中的从节点个数 ItemCF-MR 算法的加速比曲线图 ) 运行 ItemCF-MR 算法从图 5 可以看出, 随着数据规模增大, 并行效率提高 ; 随着从节点个数增加, 并行效率降低但随着数据规模从节点个数同时增加, 并行效率保持常数 2 个从节点计算数据,4 个从节点计算数据,6 个从节点计算数据, 并行效率 E 都保持在 0.78 左右这说明当数据规模增大时, 总是能通过增加计算节点来弥补性能损失, 即 Item- CF-MR 算法具有良好的可扩展性 Efficiency 另外, 英语训练平台增加了推荐引擎模块后, 与之前相比, 以下指标有了明显的变化 :(1) 学习者的显性反馈行为增加了 24%;(2) 学习者阅读理解的平均练习题数增加了 11%, 听力的平均练习题数增加了 8%;(3) 被下载阅读资源的数量增加了近 10% 这都间接证明了推荐系统的有效性 5 结束语推荐系统经历了将近二十年的发展, 在电子商务社交网站等众多领域越来越重要但面对今天的大数据环境, 原有的算法暴露出许多无法克服的缺点本文依托云计算技术, 对传统的 ItemCF 算法进行了 MapReduce 化, 解决了协同过滤的伸缩性和实时性问题同时, 将云计算推荐引擎融入一个商用系统并成功应用, 证明了云计算与推荐系统结合的可行性参考文献 : 图 5 [1] 李国杰. 大数据研究的科学价值 [J]. 中国计算机学会通讯, 2012,8(9):8-15. 数据规模 [2] IDC 发布最新数字宇宙研究报告 [EB/OL].[ ] /t _ html. [3] Resnick P,Varian H R.Recommender systems[j].communications of the ACM,1997,40(3): [4] Goldberg D,Nichols D,Oki B M,et al.using collaborative filtering to weave an information tapestry[j].communications of the ACM,1992,35(12): 个从节点 4 个从节点 6 个从节点 ItemCF-MR 算法的并行效率曲线图 [5] Sarwar B,Karypis G,Konstan J,et al.item-based collaborative filtering recommendation algorithms[c]//proceedings of the 10th International Conference on World Wide Web.

7 应毅, 刘亚军, 陈诚 : 基于云计算技术的个性化推荐系统 2015,51(13) 117 [S.l.]:ACM,2001: [6] Linden G,Smith B,York J.Amazon.com recommendations: Item-to-item collaborative filtering[j].internet Computing, 2003,7(1): [7] Shang M S,Jin C H,Zhou T,et al.collaborative filtering based on multi-channel diffusion[j].statistical Mechanics and its Applications:Physica A,2009,388(23): [8] Dakhel G M,Mahdavi M.A new collaborative filtering algorithm using K-means clustering and neighbors voting[c]// Proceedings of the 11th International Conference on Hybrid Intelligent Systems(HIS).[S.l.]:IEEE,2011: [9] Mittal N,Nayak R,Govil M C,et al.recommender system framework using clustering and collaborative filtering[c]// Proceedings of the 3rd International Conference on Emerging Trends in Engineering and Technology(ICETET).[S.l.]: IEEE,2010: [10] Sarwar B,Karypis G,Konstan J,et al.application of dimensionality reduction in recommender system A case study[r].minnesota Univ Minneapolis Dept of Computer Science,2000. [11] Zhao Z D,Shang M S.User-based collaborative-filtering recommendation algorithms on hadoop[c]//proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining(WKDD 10).[S.l.]:IEEE,2010: [12] 刘春灵. 基于云计算的移动商务推荐服务网络分析 [J]. 电信科学,2010(8A): [13] 李文海, 许舒人. 基于 Hadoop 的电子商务推荐系统的设计与实现 [J]. 计算机工程与设计,2014,35(1): [14] Lai C F,Chang J H,Hu C C,et al.cprs:a cloud-based program recommendation system for digital TV platforms[j]. Future Generation Computer Systems,2011,27(6): [15] Shvachko K,Kuang H,Radia S,et al.the hadoop distributed file system[c]//proceedings of the IEEE 26th Symposium on Mass Storage Systems and Technologies (MSST).[S.l.]:IEEE,2010:1-10. [16] Dean J,Ghemawat S.MapReduce:Simplified data processing on large clusters[j].communications of the ACM, 2008,51(1): [17] 新浪微博用户超 5 亿 [EB/OL].[ ]. rmlt.com.cn/2013/0221/62953.shtml. [18] 周军锋, 汤显, 郭景峰. 一种优化的协同过滤推荐算法 [J]. 计算机研究与发展,2004,41(10): [19] 吴志川, 毛琛, 韩蕾, 等. 高度可伸缩的稀疏矩阵乘法 [J]. 计算机科学与探索,2013,7(11): [20] Manouselis N,Drachsler H,Vuorikari R,et al.recommender systems in technology enhanced learning[m]// Recommender Systems Handbook.[S.l.]:Springer US, 2011: [21] 王国霞, 刘贺平. 个性化推荐系统综述 [J]. 计算机工程与应用,2012,48(7): ( 上接 80 页 ) [2] 朱杰杰, 胡维华, 潘志庚. 虚拟多媒体教室的设计和实现 [J]. 计算机辅助设计与图形学学报,2004,16(1): [3] 任昆, 戴永, 王求真, 等. 上下文感知手写数学公式结构分析 [J]. 湘潭大学自然科学学报,2014,36(2): [4] 戴永, 刘任任, 王求真, 等. 可联网交互的多功能规定格式习字系统及方法 : 中国,ZL [P] [5] 吕军. 电化教学多功能写作装置与系统 : 中国,ZL [P] [6] Yae K Z.System for teaching writing based on a users past writing:us,zl a1[p] [7] Ma Xiaodong,Su Xiao.A new tcp congestion control algorithm for media streaming[c]//proceedings of Multimedia and Exop 2009 ICME International Conference, 2009: [8] Li G,Tian Y C,Fidge C J.A conditional retransmission enabled transport protocol for real-time networked control systems[c]//proceedings of 2011 IEEE 36th Conference on Local Computer Networks(LCN),2011: [9] 王兵, 武杰, 孔阳, 等. 王砚方. 数字传感网络的高速数据传输协议设计 [J]. 仪器仪表学报,2010,31(7): [10] 中华人民共和国教育部. 教育部关于贯彻国务院办公厅转发中央编办教育部财政部关于制定中小学教职工编制标准意见的通知的实施意见 [Z] [11] 中国标准委员会.GB 中小学建筑设计规范 [S] [12] 樊亮, 戴永, 覃冰梅. 触摸屏手写汉字笔画的笔力模糊评价 [J]. 中文信息学报,2013,27(2): [13] 孙广武, 戴永, 喻世东, 等. 音素关联的多文种语音融合编码方法 [J]. 计算机工程与应用,2013,49(19): [14] 覃冰梅, 戴永, 樊亮. 面向联机书写指导的触摸笔迹信息前置处理 [J]. 计算机应用研究,2012,29(9): [15] 戴永, 王心觉, 张维静, 等. 面向指导的自由式英文字母书写跟踪 [J]. 湘潭大学自然科学学报,2012,34(2): [16] 任勇毛, 唐海娜, 李俊, 等. 高速长距离网络传输协议 [J]. 软件学报,2010,21(7):

112 2015,51(13) Computer Engineering and Applications 计算机工程与应用目统计,2010 年 2011 年全球新增数据总量分别为 1.2 ZB 和 1.8 ZB,2012 年数据总量高达 2.8

112 2015,51(13) Computer Engineering and Applications 计算机工程与应用目统计,2010 年 2011 年全球新增数据总量分别为 1.2 ZB 和 1.8 ZB,2012 年数据总量高达 2.8 Computer Engineering and Applications 计算机工程与应用 111 数据库数据挖掘机器学习基于云计算技术的个性化推荐系统应毅 1 2 刘亚军 3 陈诚4 YING Yi1 2, LIU Yajun3, CHEN Cheng4 1.三江学院软件学院南京 210012 2.三江学院计算机科学与工程学院南京 210012 3.东南大学计算机科学与工程学院