2012年 6月 第 33卷 第 6期 计 算机 工 程 与 设 计 C0M PUTER ENGINEERING AND DESIGN Jun．2012 VoL 33 No．6 基 于 大 数据 集 的协 同过 滤 算 法 的 并 行化 研 究 李 改 ，潘 嵘。 ，李章凤 ，李 磊。 (1．顺德 职 业技 术 学 院 电子与信 息 工程 系 ，广 东 顺 德 528300；2． 中山大学 信 息科 学与技 术 学 院 ， 广 东 广 州 510006；3． 中山 大学 软 件研 究所 ，广 东 广 州I 510275) 摘 要：通过对基 于 ALS的协 同过滤算法及 分布式 Hadoop平 台的相 关特 性进行 深入 研 究，将基 于 ALS的协 同过滤算 法 在 Hadoop上进行 并行化 ，解 决了传统 的基 于 ALS的协 同过滤算法在 大规模数据 集上的运 算问题。经过 实验 验证 ，在 Ha— doop平 台上 实现 的并行化 的 ALS协 同过滤算法不仅 能够保证 实验结果 的准确 性，而且与 单节点上 实现的算 法相 比，运 算 效率显著提 高。 关键 词 ：推 荐 系统 ；协 同过 滤 ；hadoop；交 叉 最 小 二 乘 法 ； 并行 化 中图 法 分 类 号 ：TP309 文 献 标 识 号 ：A 文 章 编 号 ：1000—7024 (2012) 06—2437—05 Collaborative filtering algorithm parallelize research based on large data sets LI Gai ， ， PAN Rong ， LI Zhang-feng ， LI Lei ’。 (1．Department of Electronic and Information Engineering，Shunde Polytechnic College，Shunde 528300，China； 2．School of Information Science and Technology，Sun Yat-Sen University，Guangzho u 510006，China； 3．Software Institute，Sun Yat-Sen University，Guangzhou 510275，China) Abstract：Through intensive study the property of the distributed platform-Hadoop and the collaborative filtering algorithm based on ALS。a Parallel collaborative filtering algorithm based on ALS in Hadoop is presented and the computing problem of large-scale data is solved in the collaborative filtering algorithm． Experim ental results show that the Parallel algorithm based on ALS implemented in Hadoop can not only guarantee the accuracy of experimental results。but also im prove the com puting effi— ciency compare with the algorithm implemented in single node． Key words： recomm ended systems；collaborative filtering；hadoop；alternating least squares；parallelization 0 引 言 法设计与实现 。但随着互联 网的迅猛发展 ，推荐 系统 中用户 及推荐对象的数量在 呈几何 倍数 增长 ，使 得实现 在单节 点 协 同过滤 算 法是 推 荐 系统 中运 用 最 广泛 的 的推 荐 算 机器上的这些算 法要 算 出结 果需 要耗 费大量 时间 ，无法 满 法[1_3]。协 同过滤算法的核心是分析用 户兴趣 ，在用户群 中 足大数 据集 的运算需 要 。因此 如果我 们能对 这些 算法 实现 找到与指定用户相似 (兴趣) 的用户 ，综 合这 些相 似用 户 分布式计算 ，将 会 大大缩短 计算 所需 时间 ，同时必 将对 大 对某一信息的评价 ，形 成系统 对该指 定用户 对此信 息 的喜 规模协同过滤算 法的应用研究 有较 大的推动作用 。 好程度预测 4 ]。最近几年 提 出了各 种高效 的 CF算 法 ，其 本 文 的 主要 贡献 是 ：研 究 基 于 矩 阵分 解 的 Alternating- 中包 括潘 嵘 等提 出 了基 于 ALS的协 同过 滤推 荐算 法_6 ]， LeasvSquares(ALS)协同过滤算法的并行化 问题 ，并 详细 N．Srebro等提 出了 MMM ]，R．Salakhutdinov等提出 了 介绍如何在 开源 的云计 算平 台 Hadoop[“]上实 现该算 法 的 PMF和 RBM[11123，Daniel D．Lee等提 出了 NNMF[”]，以 并行化 。同时对 ALS算 法在 多个 节点下 的并行 化算法 与其 及聚类模型等等 。 在单节点上的串行算 法运行 的时间进行 对 比，进 而对 实验 当前对这些协 同过 滤算法 的研究 都侧 重于单 节点 的算 进行评估 。实验证明了 ALS算法 的可并行 性 ，并行后 ALS 收稿 日期 ：2011-06—09；修订 日期 ：201卜12—28 基金项 目：国家 自然科学基金项 目 (61003140、61033010) 作者简介：李改 (1981一)，男，湖北荆州人 ，博士研究生 ，讲师，CCF会员 ，研 究方 向为机器 学习、数 据挖掘、推荐系统 ；潘嵘 (1976一)， 男，广东广州人 ，博士 ，副教授 ，研究方向为数据挖掘 、机器学 习、低秩逼近 ；李章凤 (1989一)，男 ，福建福 州人，硕士研究生 ，研究方 向 为数据挖掘、推荐系统 ；李磊 (1951一)，男，湖南益 阳人 ，博士 ，教授 ，博 士生导 师，研究方 向为数据库 、数据挖 掘、人工智能 。 E-mail：ligai999@ 126．tom 

计 算机 工程 与设 计 2012年 算 法的运算性能获得 了极大提高 。 法计算 出的 RMSE值 收敛或迭代次数 足够 多而结束迭代 。 1 基 于 ALS协 同过滤 算法 介绍 本节我们将首先简单介绍基 于 ALS的二维协 同过滤推 (3)X— UV ，返 回矩 阵 X。 2 ALS算 法在 Hadoop上并 行实现 荐算法 。 本节主要介绍 ALS算 法在 Hadoop上 的并行 实现 。包 给定一个矩 阵 (R一 ( ) ) ∈ {0，1) “，该矩 阵 括算法设计和算法 的实现细节部分 。 表示具有 m个用户 、n个对 象的评 分矩 阵。我们希 望找到 2．1 Itadoop平 台简 介 一 个低 秩矩阵 X，来逼 近矩 阵 R。同时最小化 下 面的 Fro— 云计算 的核心计算模式是 Map／Reduce，该技 术是云计 benius损 失函数 算 的运 算 基 础。它 的存 储 基 础是 Hadoop Distributed File L(x)一 ∑ ( 一 ) (1) System (HDFS)项 目，是云平 台 的大规模 数 据存储 技术 。 在上面的 目标 函数 L (X)中，( 一)(jj) 是低秩逼近 中 常见平 方误差项 。下面我 们来考 虑如何 有效并 且快 速的求 解 最 优 化 问 题 argmin xL (X)。 考虑矩阵分解 x—UVr，UECm ，d表示特 征个 数 ， 一 般 d<< r，r表示矩阵 R的秩 ，r~min (m，n)。这时式 (1)可 以改 写 为 L(U ，V) 一 ( — )。 (2) 为了防止过 拟合 ，我们 给式 (2)加上 正则 化项 ，则式 (2) 可 改写 为 下 面 我 们 就 这 两 个 技 术 分 别 加 以 介 绍 E14-15]。 Hadoop的计 算核心是 Map／Reduce模式l1 。区别 于 网 格计算 ，Map／Reduce计算模式要求并行处理 的数据块 之间 是相互独立 的。Map／Reduce计 算模 式 的数据 输入 是 Key／ Value对 。Map过程 由 Key／Value进行数 据的处理 和整合 ， 输 出到 Reduce过程 ，最 终 的输 出依 然 是 Key／Value数 据 对 ，Map和 Reduce操作 由程 序员 自己编 写 提交 给 系统 处 理 。由 Hadoop的作 业调度机 制将数据 和 Map和 Reduce操 作分发给不同的虚 拟机进行 处理 ，并 把计算 结果 输 出到分 布式文件存储平 台上。计算集 群 中的各个数 据处 理模 块相 L(U， )： ∑ (R — ． ) + (IIui II}+II II}) 互独立 。Map过程处理完成之后 ，系统要对结 果进行排 序 ， (3) 排序后 的结果又 由 Hadoop的作业调度机制分 发给不 同 Re— 固定 V，对 U 求导 旦 “ U i 一 0， 我们得到下 面求 解 U 的公 式 duce操作处理 ，最终将结 果输 出 。MapReduce的处理 流程 图可参考文献 [14—153。 HDFS是一个高 度容错 的文件 系统 ，非 常适 合部 署到 — R (V + D i∈ Ez～ m] (4) 廉价 的机 器 群 上。HDFS的设 计侧 重 于数 据 的吞度 量 上 ， 式 (4) 中 的 R 表 示 用 户 i评 过 的 电 影 的评 分 组 成 的 向 而不是处理速度 。尤其是与 Hadoop的计算模式相结合 ，使 量 ，vu；表示用 户 i评过 的电影 的特征 向量组成 的特征矩阵 。 计算程序与数据存 储尽 可能 的在 同一 个虚拟 机上 ，保 证数 nui表示 用 户 i评 过 的 电影 的数 量 。 据 的极 大 吞 吐量 。 HDFS采 用 master／slave架 构 。HDFS集 同理 ，固定 U，可以得到下面求解 V．的公 式 群 由一个 Namenode和若 干个 Datanode组成 。Namenode设 — R u柳( + D。 ∈ E1～ ] (5) 置于中心服务器 ，负责 管理整个 HDFS的名 字空 间和用户 式 (5)中的 Ri表示评过 电影 j的用户的评分组成 的向 对 HDFS的访 问 ；Datanode是 分 布 在 不 同 虚 拟 机 上 的 数 据 量 ，U i表 示 评 过 电影 j的 用 户 的特 征 向量 组 成 的特 征 矩 阵 。 节点 ，负责用户 对数 据 的读 写 等操作 。HDFS同时提 出 了 表示评过 电影 j的用户的数量。 数据均衡 的方案 ，系统会 自动 的将数据 从一 个容量 不足数 在式 (4)、(5)中 I表示一个 d×d的单位矩阵 。 据节点上转移到 其他空 闲节 点 ，保证整 个文 件系统 的数据 基于式 (4)、(5)，我们提出下面的基于代正则化 的交 均衡 。HDFS的结构示 意图可参考文献 E15]。 叉最／J,,--乘法 (AI S)的二维协 同过 滤推荐 算 法。①我们 2．2 并 行 算 法设 计 用 0均值 ，偏差为 0．01的高斯随机数初 始化矩阵 V，② 我 在算法 1中 ，我们 知道 ，ALS算法 一次 迭代需 要分 别 们用式 (4)更新矩 阵 U，接着我们用式 (5)更 新矩 阵 V， 计算 u和 V，而求 u或求 V这个过程是 比较耗时的 ，而这 直到本算法计算 出的 RMSE值收敛或 迭代次数 足够多 而结 个过程正是算 法并 行之所在 。根据式 (4)和 (5)，我们 知 束迭代为止 。具体算法描述如下 ： 道 ，在计算 每一个用户 的特征 向量 Ui时 ，与它相关 的量 只 算法 1 基于 ALS的二维协 同过滤推荐算法 有电影特 征矩 阵 V 和该用 户 i评 过分 的 电影 的集合 即 R， 输入 ：用户的评分矩阵 R，特征个数 d。 R 是 一个 向量 ；同理在计 算每 一部 电影 的特 征 向量 V 时， 输 出：矩阵 R的逼近矩 阵 X。 与它相关 的量只有用户特征 矩阵 U 和评价 过 电影 j的用 户 (1)初始化 V。 的集合 ，即 R ，R 是一个 向量 。用 户与用户 之 间，电影 与 (2)反复迭代运用式 (4)、(5)更新 u、V，直 到本算 电影 之间是没有联 系的 ，所 以我们在 计算用 户或 电影 的特 

第 33卷 第 6期 李改 ，潘嵘 ，李章 凤 ，等 ：基 于大数 据集 的协 同过 滤算 法的并行 化研 究 ·2439 · 征 向量 时 ，是 可 以通 过 并 行 方 式 来 处 理 的 。 记 录 为 ： 基 于 MapReduce的 ALS算法 ，一次迭代需要启动两次 1 1 3 MapReduce过程 ，每次求 U或 V都需启 动一 次 MapReduce 2 1 5 过程 。每次 MapReduce过程 ，执行算法 1中的步骤 (2)或 3 1 1 (3)。Hadoop的 MapReduce编程模 型有两个 阶段 Map (映 则 R 表示 为 ： 射 )和 Reduce (规 约 )， 由于 用 户 ID 和 电影 ID 的 唯 一 性 ， 1 13。 25。 31 基 于 MapReduce的 ALS算法并不需要 Reduce过程 。 这个数据 预 处 理 过程 也 可 以利 用 Hadoop的 MapRe— 基 于 MapReduce的 ALS算法求 解 U步 骤如下 ：①输 duce实现 。这个预处理需 要启 动两 次 MapReduce，一次 求 入用户评过分 的电影 的集合 R [n](n为用户数量 )及 电影 用户评过分的 电影 的 n个集合 R．．，一 次求评价过 电影的用 特征矩 阵 V。②启动 MapReduce过程 ，将 电影特征矩 阵 V 户 的 rn个集 合 R 。MapReduce编程模 型 默认 的输 入格 式 分发到各个节点 。输人为存在 DFS上的用户 评过分 的 电影 是文本输入 ，每一行数 据都是 一条记 录 。Map函数接受 一 的集合 R En3。③ Map过 程 ：输 人 为 R [1…n]，对 于 R 组数据并将其转换为一个 key／value对列表 ，输入域 中的每 Eli，利 用 式 (4)，计 算 用 户 i的 特 征 向 量 U 。输 出 为 i， 个元素对应一个 key／value对 。Reduce函数接受 Map函数 U 。其 中 i为 key，U．为 value。 生成 的列表 ，然后根据它们的键 (为每个键生 成一个键 ／值 同理 ，基于 MapReduce的 AI S算法求解 V步骤如 下 ： 对 ) 缩 小 key／value对 列 表 。 ①输入评价 过 电影 的用户 的集合 R I-m](m 为 电影 数量 ) 如 以下是 4条评分记录 ： 及用户特征矩 阵 U。②启 动 MapReduce过程 ，将用户 特征 矩 阵 U 分发到各个节点 。输人为存在 DFS上 的评价 过 电影 的用户 的集合 R f-m]。③ Map过 程 ：输 人 为 R [1…m]， 对 于 R [j]，利用式 (5)，计算 电影 j的特征 向量 。输出 1 1 3 1 3 5 2 1 1 3 7 2 为 j， 。其 中 j为 key，vj为 value。 在求用户评过分的电影 的集合 时 ，运行 Map函数将 得 2．3 并 行 化 算 法 实 现 细 节 2．3．1 数 据 预 处 理 出 以 下 的 key／value对 列 表 ： (1 13) (1 35) (2 11) (3 72) 在实验 中使用 的原 始数据 集是 由一条 一条用 户的评 分 如 果 对 这 个 key／value对 列 表 应 用 Reduce函 数 ，将 得 记录组成 的。每一条评分记录都以一个 三元 组表示 ：(Use— 到 以 下 一 组 key／value对 ： riD，ItemlD，Rate)。其表示 的含义是某一个 用户对某 一个 对 象 进 行 打 分 (这 里 的评 分 我们 统 一 用 1到 5分 ， 1分 表示 非常不喜欢 ，5分代表非常喜欢 )。我 们需要 将其进 行处 理 得到 ：用户 i评 过分 的电影 的集合 R 和评价过 电影 J的用 (1 13， 35) (2 11) (3 72) 同理在求评价过 电影 的用户 的集 合 ，运行 Map函数将 户 的集合 R ，如果 有 n个用 户 ，m部 电影 ，则一共 有 n个 得 出 以下 以下 的 key／value对 列表 ： ira，m 个 R 。 (1 13) (4 15) (1 21) (7 32) 对于式 (4)，R．集 合 中的元 素不仅 仅只是评 分 ，还需 如果对这个 key／value对列 表应 用 Reduce函数 ，将得 要 保存 用 户 评 价 过 哪 些 电 影 。 因 为 分 数 是 1到 5分 ，所 以 到 以下 一 组 key／value对 ： R 集合 中的元素是 ItemID * 10+ Rate。这样 电影 与评分 一 一 对 应 ，而不 丢失 信 息 。 如 ：ID 为 1的用 户 评 过 电影 1，3，5，评 分 记 录为 ： (1 13， 21) (4 15) (7 32) l 1 3 1 3 5 1 5 1 则 R．表示 为 ： 1 13， 35， 51 数据预处理 中 MapReduce的逻辑数据流如图 1所示 。 图 1 MapReduee的 逻 辑 数 据 流 同理对于式 (5)，合 中的元素不 仅仅 只是 评分 ，还需 要保存 电影 被 哪些用 户 评价 过 。所 以 R 集 合 中 的元素 是 2．3．2 Hadoop参 数传 递 UseriD * 1O+ Rate。这样用 户与评 分一一对 应 ，而不 丢 在 ALS算法 中 ，求用 户特征矩 阵 U时需要事先知道 电 失信息 。 影特征矩阵 V，求 电影 特征矩 阵 V 时需 要事 先知道用 户特 如 ：ID 为 1的 电 影 被 用 户 1， 2， 3评 过 分 ，评 分 征矩阵 u，所 以求 U时 ，需要将 V作为参数传递到算 U 的 

计算机 工程 与设 计 2012正 函数中 ；求 V 时 ，需要 将 u作 为参 数传递 给算 V 的函数 Map的任 务 就 是 求 每 一 个 用 户 或 每 一 个 对 象 的 特 中 。将 ALS算法实现 在单节 点 时，只需要 将 U 和 V 设置 征 向量 。 成 全局 变量 ，就可 以解决参数传递 问题 。 然 而在基于 MapReduce的 ALS算法 中 ，我们知道在将 3 实验 评估 MapReduce作业提 交 给 Hadoop集 群 时 ，相关 的输 入 数据 本章主要对 ALS算法在 Hadoop平 台实现 的性能进 行 将 按照 Block的大小 首先被 划分为 多个片 ，分 发到各 个节 评估 ，并 阐述实验环境和实验结果。 点进行 计算 ，各个 节点 在计 算 时只执 行 MapReduce任 务 ， 3．1 Itad~p集 群 配 置 所以 MapReduce编程模 型并 不支持全 局变量 。然 而在求用 我们 的 Hadoop集 群配 置 如下 ：在实验 中分别 使用 了 户特征矩阵 U时 ，每个 节点计算 过程都需要知道 V，这时 ， 一 台 Master、2台 Slave和一 台 Master、5台 Slave组成 的 我们就需要将 V作为参数传 递到各个 节点 。选择合 适 的方 Hadoop集群 。所 有的机器 都是 HP计算 机 ，每台计算 机配 式来传递参数既能提高工作效率 ，也可 以避免 bug的产生 。 置 为 4颗 Intel(R)Core (TM )i7处 理 器 ， 8GB 内 存 。这 在基于 MapReduce的 ALS算法 中，求用 户特 征矩 阵 U 些机器都处于 同一个局域 网内。 时 ，电影特征矩阵 V是 存在 DFS中。我们 知道在 MapRe— 3．2 实 验数 据 集 duce过程中 ，会 将输 人数 据按 照 Block的大小分 块 ，假设 在这个实验 中，我们使用的数据 集是 Netflix对外 发布 分成批 P块 ，则 有 P个 Map任务 ，每个 Map任务求解 K个 的一个 电影评分数据集[2 ]。这个数 据集包括 了 480 189个 用户特征 向量 。如果在求 每个 用户的特征 向量 U_时，都从 用户在对 17 770部电影 的 103，297，638个 评分 。所 有 的 DFS中读取 电影 特征矩 阵 V，那 样效率会 非 常低 ，因为如 评分值都是 1到 5中的整数值 ，其 中分 数越 高表示客 户对 果有 n个用户 ，则需从 DFS中读取 n次 。并且 V矩 阵一般 相应 电影 的评价越高 (越喜欢)。这个数 据集非 常稀疏 ，有 比较 大 ，其 大 小 是 mXd (m 是 电影 数 量 ，d为 特 征 数 )，所 将近 99 的评分值未知 。从这个数据集 中随机抽取 140万 以这种参数传递方式效率非常低 ，并不 可取 。 条评分记 录作 为测试集 TestSet，其余作 为训 练集 TrainSet。 同理求 电影特征矩 阵 V时 ，这种参 数传递方 式也不 可 3．3 实 验 结 果 取 。每个 Map任务在开始前都会 进行初始化 操作 ，如果 在 本论 文进行 了 3个实验 ，分别是 ALS算 法在单 节点 的 初始化 时 ，读 取 文 件放 到 变 量 中 ，将 这 个变 量 做 为 整个 实现 ，在一 台 Master、2台 Slave的 Hadoop集群 中的实 现 Map任务 的共享变量 ，则 读取文 件次 数将减 少 ，有多少个 和在 一台 Master、5台 Slave的 Hadoop集群 中的实现 。 Map任务 ，只需要读多少次文件 ，效率将 大大提 高。 ALS算法 中有两个参数 ，分别是特征个数和迭代次数 。 Hadoop的分布式缓存 机制使得一个 job的所有 map或 在第 一轮实验 中 ，设定迭代次数 为 1，特征个数 分别 为 reduce可以访问同一 份文件。在任务提交后 ，hadoop将 由一 1O，2O，3O，4O，5O。最终 实验结果 如图 2所示 。 files和一archive选 项 指 定 的文 件 复 制 到 HDFS上 (Job— Tracker的 文 件 系 统 )。在 任 务 运 行 前 ，TaskTracker从 Job— Tracker文件系统复制文件 到本 地磁盘作为缓存 ，这样 任务 就 可 以访 问 这些 文件 。对 于 job来说 ，它 并 不 关 心 文 件 是 从 哪儿来 的。在使用 hadoop的缓 存文件 DistributedCache时 ， 对于本 地化文件 的访 问，通 常使 用 Symbolic Link来访 问 ， 这样更方 便。通过 URI hdfs：／／namenode／test／input／filel# myfile指定的文件 在 当前工 作 目录 中被符 号链接 为 myfile。 这样 j0b里面可直接通过 myfile来访 问文件 ，而不 用关心该 文件在本地的具 体路径 。 2．3．3 Map函数实现 由于 用 户 I【)和 电影 ID 的 唯 一 性 ，基 于 MapReduce的 ALS算法并不需要 Reduce过程 。Map函数主要对输入 的每 一 条数据进行处 理 ，其 默认 的输 入格式 是文本输 入 ，每一 行数据都是 一 条记 录 。在数 据 预处 理 时，我们 已经知 道 ， 每 一 行 的 数 据 格 式 是 ： UserID value1， value2 … valueK 或者 ： 茎篙 横坐标为特征个数 ，纵坐标为时 间，单位为秒 (S)。 由图 2可 以看 出，随着特征 数 的增 多 ，ALS算 法在单 节点运行 的时间 与在 Hadoop集群 上运 行 的时 间之 间的 比 例是越来越大 ，当特征 数为 5O时 ，其 比例达 到了 5。由式 (4)和式 (5)可知 ，特征数 的增 多 ，意味着运 算复杂度 增 加。当特征数为 1O时 ，ALS算法在单节点运行 的时 间比在 Hadoop集群运行 的要快 ，这 是 因为 Hadoop集群进 行并 行 化时 ，master需要进行 调度 ，特 征数为 10时 ，运算 复杂度 ItemID value1． value2 … valueK 并不 高 ，所 以用 Hadoop集群进行并行计算 ，并不能体现出 

第33卷 第 6期 李改 ，潘嵘 ，李章凤 ，等 ：基于大数据集的协 同过滤算法的并行化研 究 ·2441· 并行 计 算 的威 力 。 调过滤算法 ，如 RBM、NNMF等 。 Hadoop集群 中节 点 的增 多 ，意 味着 其 运算 能 力 的增 加 ，从 图 2可 以看 出，5个 nodes的 Hadoop集群 运算效率 参 考 文献 ： 要 比 2个 nodes的 Hadoop集群高 。当然 ，并不是越多机器 r1] I U0 Xin，0U YANG Yuanxin，X10NG Zhang，et a1． The 越好 ，假 设每 个 节点 处 理一 个 Map任务 ， 当节 点数 多 于 Map任务时 ，节点的增多并 不能 提高运 算效率 ，此时多 于 的机器会 被 闲置 。所 以理想 情 况 下 ，Map任 务 数 最 好 是 Hadoop集群 节 点数 的倍 数 ，这 样 才能 有效 充 分 利用 Ha— doop集群的运算 能力 。 在第二轮实验 中，设定迭代 次数 为 1O，特征 个数分 别 为 1O，2O，3O，4O，50。最终实验结果如图 3所示 。 6oo 500 g 400 ． { 300 ．量 ． 一 _ I l 麟 200 ： 横坐标为特征个数 ，纵坐标为时间 ，单位 为 ：分钟 。 effect of similarity support in K-nearest-neighborhood based col— laborati ve filtering EJ2．Chinese Journal of Computers，2010， 33(8)：1437—1445 (in Chinese)．[罗辛 ，欧 阳元新 ，熊璋 ， 等．通过相似度支持度优化基于 K近邻的协 同过滤算 法 [J]． 计算机学报 ，2010，33(8)：1437—1445．] [2]Ricci F，Rokach L，Shapira B，et a1．Recommender system handbook[M]．New York：Springer，2011：1—29． [3]Das A，Datar M，Garg A，et a1．Google news personalization： Scalable online collaborative filtering[c]．Canada：Proceedings of the 16th Internationa1 Co nference on W orld W ide W eb， 2007： 271—280． [4] Adomavicius G，Tuzhilin A．Toward the next generation of recomm ender systems： A survey of the state-of-the-art and possih[e extenstions[J]．TKDE，2005，17(6)：734—749． [5] wu J L． Collaborative filtering on the netflix prize dataset [EB／OL]．[2010—08一O1]．http：／／dsec．pku．edu．cn／~jinlong／ r6]PAN R，ZHOU Y，CAO B，et a1．One-class collaborative fihe— ring[C]．Pisa，Italy：Proceedings of the Eighth IEEE Interna— tional Conference on Data M ining ，2008：502—511． [7]PAN R，Martin& Mind the gaps：Weighting the unknown in large-scale one-class collaborative filtering[c]．Paris，France： Proceedings of the 15th ACM SIGKDD International Co nference 在这两个 实验 中，可 以看 出特 征数 越多 ，迭 代次 数越 on Knowledge Discovery and Data M ining，2009： 667—676． 多 ，ALS算法在 Hadoop集群上 的运算效率会提高 的越多 。 r8] zHOU Y H ，W ilkinson D，Schreiber R，et a1． Large-scale 4 结束 语 本文对推荐 系统 的协 同过 滤算法进 行介 绍 ，并针 对其 中基 于矩 阵分 解 的 ALS算 法进 行 了详 细 介 绍 ；同时还 对 Hadoop平 台产生的背景 ，应用背景 ，平台架构 和核心部分 做 了比较详细 的介绍 ；然后在上 述基础上 实现 ALS算 法在 Hadoop平 台的并行化 ，以提高算法性能 。 parallel collaborative filtering for the Netflix prize[c]．Berlin： Proceedings of the 4th Intem ational Co nference on Algorithm ic Aspects in Information and M anagement，2008： 337—348． [9]SrebroN，Rennie J DM，JaakkolaT Mmdmum-marginmatrixfac- torization rC_．Vancouver：MIT Press(NIPS)，2004：1329-1336． [1O]Rennie J D M，Srebro N．Fast maximum ma rgin ma trix factoriza— tion for collaborative prediction[C3．Bonn，Germany：Proceedings of the 22nd International Co nference on Machine Learn ing ，2005： 通过 实验 ，我 们 可 以清楚 看到 基 于 Hadoop平 台实现 713—719． 的算 法在 运算 效 率上 提高 的非 常 明显 。当然 ，在 实验 中 ， [11]Salakhutdinov R，Mnih A Probabilistic matrix factorization [C]． 我们 的实 验数 据集 还 不够 大 ，还 不能 完 全体 现 出 Hadoop Van couver，British Co lum bia，Canada：Proceeding s of the 25th In— 的优 势来 ，据我们所知 Yahoo为 了满 足广告 系统和 web搜 ternational Co nference on Machine Learning ，2007： 1257—1264． 索的研 究 ，在 4000个 服 务 器 集群 上部 署 Hadoop；Face— [12] Salakhutdinov R，Mnih A， Hinton G Restricted boltzrnann book使用 了 1000个节点 的集群部署 HDFS，以支持其大量 ma chines for collaborative filtering [C]．NY，USA：Proceedings 的 日志数据 的存储 ；淘宝 网则使用 hadoop集群 网络 处理大 of the 24th International Co nf erence on Machine Learning ，2007： 量的电子商务相关 的数 据 ；百度 公司利用 hadoop并 行计 算 791—798． 系统 ，进行 大规 模 网页的分 析与搜 索 ，其处 理数据 达每周 200TB。因此协 同过滤 推荐 算法 的并 行化 至关 重要 ，其应 用前 景非 常广 泛 。 在本 实验中我们实现了基 于矩阵分解 的 ALS协 同过 滤 算法在 Hadoop平 台的并 行 化 ，在 时间效 率 上有 提高 ，但 Hadoop集群除 了受集群机器数影响 ，还有受一 些参数配 置 的影 响 ，如 ：文件 Block的大小 ，文件 的复制数等 ，这些参 [13]LEEDD，SeungHS Learnwetheparts ofobjects by non-negative ma trix factorization 口]． Nature，1999，401(11)：788-791． [14] Tom Wbite． Hadoop：The definitive guide [M]．2nd ed． USA ：o Reilly M edia，Inc，2010： 1-60． [15] Apach HDFS Architecture [EB／OL]． http：／／hadoop．a— pache．org／hdfs／docs／current／cn／hdfs_design．htm1． [16]Jeffrey Dean，Sanjay Ghemawat．Map reduce：Simplified data processing on large clusters[C]．San Francisco，CA：Pro— 数配置对 Hadoop集 群 的影 响将 是下 一 步工 作 。本 文所 提 ceedings of the 6th Conference on Sym posium on Opearting 出的并行 化 ALS的算法思想还 可以运用于并行 化其他 的协 System s Design & Implementation，2004： 137—150．