第３３卷第１期 四川兵工学报 ２０１２年１月 【基础理论与应用研究】 基于ＭａｐＲｅｄｕｃｅ的多元线性回归 算法的设计与实现 王大伟 ，沈奇威 ，王玉龙 ’ （１．北京邮电大学网络与交换技术国家重点实验室，北京１００８７６； ２．东信北邮信息技术有限公司，北京１００１９１） 摘要：针对现代大规模数据线性回归在单机计算时间过长的问题，本文设计并实现了一种基于ＭａｐＲｅｄｕｃｅ架构的并行多元 线性回归算法。在用普通ＰＣ搭建的Ｈａｄｏｏｐ集群上的研究实验结果表明，基于ＭａｐＲｅｄｕｃｅ架构的多元线性回归算法在处理 大规模数据时，与单机的多元线性回归算法相比有较大的速度提升。 关键词：ＭａｐＲｅｄｕｃｅ；Ｈａｄｏｏｐ；多元线性回归 中图分类号：ＴＰ３０１ 文献标识码：Ａ 文章编号：１００６—０７０７（２０１２）Ｏ１—０１３３—０３ 在如今数据爆炸的时代，用户数据、Ｗｅｂ数据、ＳＮＳ（ｓｏｃｉａｌ ｎｅｔｗｏｒｋｉｎｇ ｓｅｒｖｉｃｅｓ）数据等各类数据规模呈几何级增长，数据量 已不再是单纯的几十Ｍ，而是几十Ｇ，甚至上Ｔ。同时，数据的条 数动辄上亿，维度从几十维至几百维。而如今，单机处理几十Ｇ 的数据就需要小时级的运行时间，在实际应用中是无法忍受的。 对如此庞大的数据量的处理是目前所面临的问题。因此随着互 即： ｂｋｘ“＋“ ，ｉ＝１，２，…，ｎ 联网的迅猛发展，实现一种高效的数据挖掘算法具有重要的学 术意义和经济价值。 Ｈａｄｏｏｐ…是近年来新兴的、开源的、存储大规模数据的分布 ： ：： ｌｉ： 。＋ 。 。 ＋ ＋ ＋…＋ ＋ 用最小二乘法估计参数ｂ。，ｂ 一，ｂ ，就是要选择参数ｂ。，ｂ 一， ｂ ，使Ｙ的观测值 与相应函数值 的离差平方和达到最小 式文件系统，架构在其上面的ＭａｐＲｅｄｕｃｅ＿２ 计算框架可以有效 地管理多台计算机共同运行一项任务，擅长对海量数据的处理。 作为多元统计分析方法中应用最为广泛的多元线性回归分析方 法，尤其在数据密集型行业的业务预测分析等环节起着重要的 Ｑ：∑（ 一 ）。＝∑（ 一氏一 取最小值时有： 一・一８ｋＸｋｉ） ｆｌ 氏 ：０ 作用。因此，本文对基于ＭａｐＲｅｄｕｃｅ的多元线性回归算法进行 了设计和实现。 ・ ｛ｌ ：０ （３） ｌ 多元线性回归算法原理 在实际生活中，一个经济变量经常受多个因素影响，研究因 变量（被解释变量）对于２个或２个以上自变量（解释变量）之间 的回归问题，称为多元回归分析 。回归分析主要用于分析事 整理得： ｌＩ ｉ ：０ ｆｎ晶＋ ∑ ＋ ∑ ＋．．’＋ ∑％＝∑ｙｌ 物之间的统计关系，侧重考察变量之间的数量变化规律。 若因变量ｌ，与解释变量 ， ， …具有线性关系，则他们 』 ∑ － ＋ ∑ ＋ ∑ ｚ ＋…＋ ∑ ＝∑ （４） ｌ； ｔＧｏＥ％＋ 。∑ （１） 之间的线性回归模型可表示为 Ｙ＝ｂ０＋ｂｌＸｌ＋６２ ＋６３ ＋…＋６＾ ＋ ∑ ＋．．・＋ ∑ ＝∑ｘｋｉＹｉ 其中＂－Ｕ为随机扰动项观测值。对于第ｉ个观测值 收稿日期：２０１１—１１—２８ 基金项目：国家９７３计划项目（２０１２ＣＢ３１５８０２）；国家自然科学基金项目（６１０７２０５７，６０９０２０５１，６１１０１１１９）；长江学者和创新团队 发展计划资助项目；国家科技重大专项项目（２０１１ＺＸ０３００２—００１—０１）；中央高校基本科研业务费专项资金项目 （ＢＵＰＴ２００９ＲＣ０５０５） 作者简介：王大伟（１９８４一），男，硕士，主要从事业务网络智能化研究。 ｌ３４ 四川兵工学报 ｈｔｔｐ：／／ｓｃｂｇ．ｊｏｕｒｓｅＩ、，．ｃｏｒｎ／ ２基于ＭａｐＲｅｄｕｃｅ的多元线性回归算法 ２．１ ＭａｐＲｅｄｕｃｅ简介 本文使用ＭａｐＲｅｄｕｃｅ程序来处理大规模的数据集。ＭａｐＲｅ— ｄｕｃｅ是一个编程模式，由Ｍａｐ和Ｒｅｄｕｃｅ两个函数组成。ＭａｐＲｅ— ｄｕｃｅ程序中的输人、输出和中间数据都是以键值对（ｋｅｙ，ｖａｌｕｅ） 的形式存在。Ｍａｐ函数的输入是一些＜ｋｌ，ｖｌ＞元组集，然后产 生中间数据元组＜ｋ２，ｖ２＞。Ｒｅｄｕｃｅ函数运行时，将所有的ｋｅｙ 按值分，每１个ｋｅｙ值的所有元组运行１次Ｒｅｄｕｃｅ函数。Ｒｅ． ｄｕｃｅ函数的输入是＜ｋ２，ｌｉｓｔ（ｖ２）＞，输出是＜ｋ３，ｖ３＞。 ２．２基于ＭａｐＲｅｄｕｃｅ的多元线性回归算法 使用ＭａｐＲｅｄｕｃｅ程序来计算式（４）中矩阵的系数和最后的 总离差、回归和残差平方和 ｊ。如图１，首先运行一个作业，计算 矩阵的系数（假设矩阵是ｍ维），每个Ｍａｐｐｅｒ（每个ｂｌｏｃｋ对应１ 个Ｍａｐｐｅｒ）维持１个ｍ×ｍ的二维数组，每读１行，运行１次Ｍａｐ 函数，就将计算的数加进去，直到这个ｂｌｏｃｋ（Ｈａｄｏｏｐ里的文件分 块）的Ｍａｐｐｅｒ运行完毕，将结果以键值对的形式写入磁盘；然后 Ｃｏｍｂｉｎｅｒ将本机的所有ｂｌｏｃｋ中间结果相同ｋｅｙ的ｖａｌｕｅ值相 加；最后Ｒｅｄｕｃｅｒ将不同机器上所有中间结果相同ｋｅｙ的ｖａｌｕｅ 值相加，将矩阵的系数写入磁盘，求出结果，即式（１）。 ｌ ＴａｓｋＴｒａｃｋｅｒ ｌ ｌ ＴａｓｋＴｒａｃｋｅｒ Ｉ ｌ ＴａｓｋＴｒａｃｋｅｒ ｌ ／ ＼ ＼ ／ ／ ＼ 。牵。． 户 图ｌ计算流程 再运行一个作业，求总离差和回归差，过程与第１个作业类 似，只不过每个Ｍａｐｐｅｒ维持和更新的是２个变量，而不是１个二 维数组。 计算式（４）中矩阵系数的Ｍａｐｐｅｒ的逻辑 如下： Ｍａｐｐｅｒ＜Ｏｂｊｅｃｔ，Ｔｅｘｔ，Ｔｅｘｔ，ＤｏｕｂｌｅＷｒｉｔａｂｌｅ＞｛ ／／声明本地变量自变量ｘ维数ｍ和系数矩阵ｍａｔｒ ｍ，ｍａｔｒ； ｓｅｔｕｐ（ｃｏｎｔｅｎｘｔ）｛ ／／从ＪｏｂＣｏｎｆ中得到ｍ，并且ｎｅｗ出ｍ维矩阵ｍａｔｒ ｝ ｍａｐ（）｛ ／／更新ｍａｔｒ，将此行得出的自变量之间的乘积加到ｍａ— ｔｒ上 ｝ ｃｌｅａｎｕｐ（）｛ ／／将中间结果矩阵ｍａｔｒ写到磁盘上 ｝ ｝ Ｃｏｍｂｉｎｅｒ和ｒｅｄｕｃｅｒ都是类似ｗｏｒｄｃｏｕｎｔ（ＭａｐＲｅｄｕｃｅ官方例 程）求和的过程。计算总离差和回归差比较简单，是个遍历的 过程。 ３实验与结果分析 ３．１试验环境和数据属性 实验集群：１台ＮａｍｅＮｏｄｅ，９台ＤａｔａＮｏｄｅ，配置是ＣＰＵ双核 ２．４Ｇ、内存２Ｇ，Ｍａｐ任务最大同时运行数量为１８，Ｒｅｄｕｃｅ任务最 大同时运行数目为９。单机程序运行机器的配置是ＣＰＵ双核２． ４Ｇ、内存２Ｇ。表１是所用的实验数据的大小和属性。 表１ 实验数据大小（单位为ＧＢ，列名是数据的 维度大小，行名是数据的条数） ３０万 ０．Ｏ１ ０．Ｏ３ ０．０９ ０．２８ １００万 ０．０４ ０．１ ０．３ Ｏ．９５ ３００万 ０．１１ Ｏ．３ｌ ０．８８ ２．７８ １ ０００万 ０．３８ １．０２ ２．８７ ９．２６ ３．２实验结果及分析 ， 如图２，在集群９台的环境下，数据的维度从３维到１００维， 数据的条数从３Ｏ万到１ ０００万，可以发现数据量在３０（３到１００ 维），１００（３到１００维），３００（３到３Ｏ维）和１ ０００万条（３到１０ 维）的运行时间都在４０ｓ左右，并且表现出无序性，主要原因是 这个时间的大部分比例被作业初始化时间、中间文件生成与传 递时间所占，这是这个ＭａｐＲｅｄｕｃｅ程序运行所需的基本时间。 此时ＭａｐＲｅｄｕｃｅ的并行运算性能优势没有得到发挥。而当数据 量达到１ ０００万３Ｏ维的时候，运行时间开始增加，这个数据量是 ＭａｐＲｅｄｕｃｅ的并行运算优势开始发挥的时候，所以跟单机比较 的时候，采用ｌ ０００万或３Ｏ维的数据。 如图３，先在数据维度为３０，条数逐步递增的情况下比较。 王大伟，等：基于ＭａｐＲｅｄｕｃｅ的多元线性回归算法的设计与实现 可以看到，在数据量３００万３０维的时候运行时间相差无几，而 达到１ ０００万３Ｏ维的时候单机的运行时间已经是集群的２倍 １３５ １００台以上的机器（而且机器都是刀片机），所以预估１００台的集 群，在运行百Ｇ的数据时，速度是百秒级，而单机则需要百分 种 鲫 多。集群（９台）的优势在１ ０００万３０维的时候体现出来。而且 从图３中可以看出，在数据条数增加的情况下，单机运行时间的 加速度比集群的要大，所以在数据量越大的情况下，集群的并行 运算优势越明显。 ｌ舯０ｏ０ １６００ｏＯ １４００ｏ０ １２Ｏ０Ｄ０ ｌ０ｏ００ｏ ８００００ ６００００ ４００ｏＯ ２００００ ０ １０ ３Ｏ ｌ００ ４组数据运行时间／ｍｓ ６０Ｏ０ｏ０ ５０ｏ０ｏ０ ４０００００ ３０００ｏＯ ２０ｏ０ｏＯ １０ｏ０ｏＯ ０ ３０万 １Ｏ０万 ３００万１ ０００万 ３ ０００万 图３ ３０维、条数递增的数据的运行时间／ｍｓ 如图４，１ ０００万条的数据，维度从３到１００的时候，大小是 ０．３８，１．０２，２．８７，９．２６Ｇ，也是在３Ｏ维的时候运行速度优势比较 明显地体现出来。而且在数据维数增加的情况下，单机运行的 时间增加速度比集群的要大。从图４中可以看出，在数据维度 增加的情况下，单机运行时间的加速度比集群的要大，所以在数 据量越大的情况下，集群的并行运算优势越明显。 图４ １ ０００万条、维度递增的数据的运行时间／ｍｓ 图５是１ ０００万条３０维、２．８７Ｇ的数据在集群台数变化的 时候运行时间的结果。在３台的时候是比单机慢，到了４台的 时候开始比单机快。现在一般公司用的Ｈａｄｏｏｐ集群，一般拥有 钟级 。 ２０００ｏＯ １８００ｏ０ １６０ｏｏ０ １４０Ｏ００ ｌ２ＯＯ００ １００００ｏ ８００ｏＯ ６００００ ４０ｏｏＯ ２ＯＯｏ０ ０ 图５ １ ０００万条、３０维的数据在集群台数递增 情况下的运行时间／ｍｓ 实验结果表明：在实验环境中，基于ＭａｐＲｅｄｕｃｅ的多元线性 回归算法在数据大小为ＧＢ级的时候就可以展现出性能的优势； 在数据量为ｌＯＧ的时候，就有３倍的性能优势。 ４结束语 本文利用ＭａｐＲｅｄｕｃｅ并行性的优势，设计了一种基于Ｍａ— ｐＲｅｄｕｃｅ的并行多元线性回归算法。该算法能对大规模的数据 进行线性回归，充分利用了多台普通Ｐｃ组成的Ｈａｄｏｏｐ集群的 性能，从而可以在较短的时间内进行线性回归，提高了近年来社 会化网络中海量数据运算使用线性回归算法的方便性。 同时，这个算法也有一定的缺点和不足，包括此算法需要在 ＭａｐＲｅｄｕｃｅ框架中运行，并且在比较大的数据量下才能显示出 性能优势等。 参考文献： ［１］Ｖｅｎｎｅｒ Ｊ．Ｐｒｏ Ｈａｄｏｏｐ［Ｍ］．ＵＳＡ：Ｂｅｒｋｅｌｙ，２００９． ［２］Ｄｅａｎ Ｊ，Ｇｈｅｍａｗａｔ Ｓ．ＭａｐＲｅｄｕｅｅ：Ｓｉｍｐｌｉｉｆｅｄ Ｄａｔａ Ｐｒｏｃｅｓｓｉｎｇ ｏｎ Ｌａｒｇｅ Ｃｌｕｓｔｅｒｓ［Ｃ］／／Ｐｍｃ．ｏｆ ｔｈｅ ６ｔｈ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍ Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ．Ｓａｎ Ｆｒａｎｃｉｓｃｏ，２００４． ［３］ 贺德化．多元线性回归算法原理［Ｇ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ． ｓｃｕｔｄｅ． ｎｅｔ／ｃｏｕｒｓｅｓ—ｂ／０１０１一ｃｅｆｆｇｅｂｃｆｈ／１０／ｇｈｊ １００１０１０１． ｈｔｍ．２００１． ［４］金欣，沈奇威，王晶．自中心网络生成的高效分布式设计与 实现［Ｊ］．电信科学，２ｏｌｏ（１１）：３２—３６． ［５］ 曹羽中．Ｈａｄｏｏｐ进行分布式并行编程［ＥＢ／ＯＬ］．［２００８—０５ —２２］．ｈｔｔｐ：／／ｗｗｗ．ｉｂｍ．ｅｏｍ／ｄｅｖｅｌｏｐｅｒｗｏｒｋｓ／ｅｎ／ｏｐｅｎ— ｓｏｕｒｃｅ／ｏｓ—ｃｎ—ｈａｄｏｏｐ２／ｉｎｄｅｘ．ｈｔｍ１． ［６］ Ｗａｎ，Ｌｉ．Ｓｏｃｉａｌ ｎｅｔｗｏｒｋ ｉｎｆｏｒｍａｔｉｏｎ ｆｌｏｗ ｍｏｄｅｌ ｂａｓｅｄ ｅｏｌｌａｂｏ— ｒａｔｉｖｅ ｆｉｌｔｅｉｒｎｇ ａｌｇｏｉｒｔｈｍ［Ｊ］．Ｊｉｌｉｎ Ｄａｘｕｅ Ｘｕｅｂａｏ（Ｇｏｎｇｘｕｅ— ｂａｎ），２０１１，４１（１）：２７０—２７５． （责任编辑鲁进）
