论文研究-分布式并行PCA算法在大样本数据集中的应用 .pdf

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：0.69M 资料格式：pdf 举报版权申诉

weixin_39840387-11575190-4744302543399874030.pdf-第1页.png

第1页 / 共10页

weixin_39840387-11575190-4744302543399874030.pdf-第2页.png

第2页 / 共10页

weixin_39840387-11575190-4744302543399874030.pdf-第3页.png

第3页 / 共10页

weixin_39840387-11575190-4744302543399874030.pdf-第4页.png

第4页 / 共10页

weixin_39840387-11575190-4744302543399874030.pdf-第5页.png

第5页 / 共10页

weixin_39840387-11575190-4744302543399874030.pdf-第6页.png

第6页 / 共10页

weixin_39840387-11575190-4744302543399874030.pdf-第7页.png

第7页 / 共10页

weixin_39840387-11575190-4744302543399874030.pdf-第8页.png

第8页 / 共10页

文本预览

中国科技论文在线 http://www.paper.edu.cn 分布式并行 PCA 算法在大样本数据集中的应用# 张涛1,2，王纯1,2，李炜1,2** 5 10 15 （1. 北京邮电大学网络与交换技术国家重点实验室，北京 100876； 2. 东信北邮信息技术有限公司，北京 100191）摘要：主成分分析（principal components analysis，PCA）是一种被广泛应用的线性降维方法。传统的 PCA 计算方法都是采用单节点在内存中对数据进行处理，面对海量的样本数据，这种处理方式已经很难满足需求。本文提出了一种基于 MapReduce 计算模型的分布式并行 PCA 计算方法，能够不受样本数量的限制，针对海量样本数据高效的进行计算。在介绍了分布式 PCA 计算方法之后，对计算性能做了详细的对比实验。最后对一个电子商务网站 2000 多万用户的样本集进行了性能实验。关键词：主成分分析，分布式，并行计算，大样本中图分类号：TP391 Application of Distributed Parallel PCA Algorithm in Large Sample data sets Zhang Tao1,2, Wang Chun1,2, LI Wei1,2 20 (1. State Key Lab of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876，P.R.China; 2. EBUPT Information Technology Co., Ltd. Beijing 100191，P.R.China) Abstract: Principal component analysis (PCA) is a widely used linear dimension reduction method. Traditional PCA calculation method uses/applies a single node for data processing in the memory. While this approach is hard to meet the requirements in face of massive sample data set. This paper presents a distributed parallel computing method of PCA based on MapReduce computational model, which is not limited by the quantity of samples and is efficient for the calculation of massive sample data. After the introduction of distributed computing method of PCA, we made a detailed contrast experiment on the computing performance. Finally, we made a performance test on more than 20 million sample sets of users from an e-commerce Website. Key words: Principal Components Analysis；parallel computing；distributed；Large sample 25 30 0 引言在数据分析、统计分析中，主成分分析（principal components analysis，PCA）是一种分 35 析、简化数据集的技术。它是一个正交化线性变换。这个变换把数据变换到一个新的坐标系统中，使得任何数据投影的第一大方差在第一个坐标（称为第一主成分）上，第二大方差在第二个坐标（第二主成分）上，依次类推。主成分分析经常用减少数据集的维数，同时保持数据集中对方差贡献最大的特征。这是通过保留低阶主成分，忽略高阶主成分做到的。这样低阶成分往往能够保留住数据的最重要方面[1]。基金项目：国家 973 计划项目（No. 2012CB315802）；国家自然科学基金（No. 61072057，60902051，61101119）；长江学者和创新团队发展计划资助；国家科技重大专项（No. 2011ZX03002-001-01，移动互联网总体架构研究）；中央高校基本科研业务费专项资金（BUPT2009RC0505）作者简介：张涛（1987），男，硕士研究生，主要研究方向为分布式计算通信联系人：王纯（1970），男，高工，主要研究方向为下一代网络，通信软件. E-mail: wangchun@ebupt.com - 1 -

中国科技论文在线 http://www.paper.edu.cn 40 PCA 在各个学科中都有着十分广泛的应用，在数据分析、数据挖掘、机器学习的数据预处理方法中，PCA 扮演着十分重要的角色。随着计算机技术的飞速发展，人们日常生活中的方方面面都通过计算机进行。需要分析处理的数据也成指数的增加，要对这些海量数据采用 PCA 方法进行降维操作，采用单机处理的方式已经很难满足需求。为了能够方便的在集群环境上并行处理海量数据， Google 公司于 2004 提出了 45 MapReduce 分布式编程框架，并应用于 Google 搜索引擎的数据处理之中。Hadoop 是一个实现了 Google 的 MapReduce 计算模型的开源分布式并行编程框架，借助于 Hadoop，程序员可以轻松地编写分布式并行程序，将其运行于计算机集群上，完成海量数据的计算[2]。本文主要针对海量样本情况下的 PCA 计算，即样本数目 n 远大于样本变量数目 p 的情况。基于 Hadoop 提供的 MapReduce 分布式编程框架，将传统的 PCA 算法并行化，来处理 50 海量样本数据的效率。 1 PCA 原理以及计算方法在多变量问题的研究时，变量太多会大大增加分析问题的复杂度。在很多情形，变量之间是有一定的相关关系的，当两个变量之间有一定相关关系时，可以认为这两个变量所包含的信息有一定的冗余。主成分分析就是为了消除这种信息冗余，并减少变量数目而提出的。 55 主成分分析也称为主分量分析，由 Karl Pearson 于 1901 年引入[3]。在基于无监督统计方法中，主成分分析（PCA）是用得最多的方法[4]，PCA 从样本的显式特征变量中提取信息，重新组合成不可直接观测到的隐含变量。它是一种线性映射方法，采用的原则是使方差最大，以尽可能多地保留原变量所包含的信息，同时又能用尽可能少的主成分替代原有变量，从而达到降维的目的[5]。 60 假设一个给定的训练数据集含有 n, 每个样本由 p 维特征向量描述为：则样本矩阵表示为： 65 由于各个指标变量的方差与采用的度量单位有关，度量单位越小, 则指标数值越大, 方差也越大, 往往突出了单位小、数值大的指标作用。为消除各指标因量纲带来的不利影响, 实际应用中往往先对样本值进行标准化[6]。 - 2 - 123[,,,]iiiiipxxxxx…,11112221221 ppijnpnnpnpxxxxxxxxxx1,2,,1,2,...,injp

中国科技论文在线主成分分析步骤如下[7]： 1). 计算各个指标的样本均值和样本标准差。 http://www.paper.edu.cn 70 其中 j = 1,2, …, p 2). 对原样本的各个指标变量做标准化处理，标准化之后的矩阵为： 75 其中： 3). 对标准化之后的样本矩阵求相关系数矩阵 R= 且 rii=1，rij=rji，(i,j = 1,2,3, … , p) 80 4). 求解相关系数矩阵 R= 的特征值和特征向量。若能通过正交单位矩阵 Q 做变换，使得：则即为所求特征值。不妨设，则 Q 的各个列向量 - 3 - 21111 1nnjjijjijiixxSxxnn11112221221ppijnpnnpnpyyyyyyyyyy1,2,, 1,2,...,injp jijijjxxySijnpyijppr11 1nijkikjkryynijppr12000000TpRQQ21,...,, p12 p

中国科技论文在线 http://www.paper.edu.cn 即为所对应的正则化特征向量(i, j = 1,2,3, … , p)。 85 5). 建立主成分。按照积累方差贡献率大于 85%（或 80%）的准则，确定 k，从而确定前 k 个主成分。方差贡献率的定义如下：根据特征值对应的特征向量 (j=1,2,3,…,k)，就可以将原始样本从 p 为转换到 k 90 维，转换后的样本为： 2 MapReduce 简介 Hadoop 是一个实现了 Google 的 MapReduce 计算模型的开源分布式并行编程框架，借助于 Hadoop，程序员可以轻松地编写分布式并行程序，将其运行于计算机集群上，完成海量数据的计算[2]。目前，企业界和研究机构都对 Hadoop 进行了深入的研究和应用[8]。 95 Hadoop 主要包括 HDFS（Hadoop Distributed File System）和基于 HDFS 的 MapReduce。 MapReduce 主要应用于对大数据集进行并行的分布式处理。它包括 Map 和 Reduce 两个阶段，也可以由多个 Map 和 Reduce 的操作串联而成。计算模型的关键是 map 和 reduce 两个函数，这两个函数由用户实现。在 Map 阶段数据以对的形式作为 map 函数的输入， 100 在 map 函数中进行处理，并可以根据需要转换为新的对输出。在 Reduce 阶段， Map 阶段输出的键值对将按照键值聚合，作为 redcue 函数的输入，即 reduce 函数的输入为。图 1 MapReduce 计算模型工作原理 - 4 - 123[,,...]Tjjjjpjlllll11 kjjpjj方差贡献率12 1,2,3,...,iikin,,zxl...l,l

中国科技论文在线 http://www.paper.edu.cn 105 Fig. 1 MapReduce computational model MapReduce 的详细工作过程如图 1[9]所示。在 Map 阶段多个 Worker 实例并行的读入并处理数据。在 Reduce 阶段，多个 Worker 会将 Map 阶段输出的数据进行聚合后，进行进一步处理。从上图可以清晰的看出，无论是在 Map 阶段还是 Reduce 阶段，都有多个 Worker 同时在工作，这些 Worker 实例可以分散在集群中不同的计算节点上，配合 HDFS 将数据切 110 分成小块后冗余存储在不同节点的策略，能大大提高整个系统的资源利用率，从而通过集群的计算能力缩短计算时间。 3 本文 PCA 的实现为了处理海量的样本数据，本文采用 MapReduce 计算模型实现了 PCA 计算的分布式、并行化处理。 115 120 由于样本数量十分巨大，全部集中放入计算机内存中计算成本太高，所以本文采用的将数据依次读入内存中进行计算。按照上一节介绍的 PCA 传统方法，需要对全部数据进行四次遍历，依次是：计算各个变量均值，计算各个变量标准差，样本标准化，以及求标准化之后的相关系数举证。即便样本标准化和求相关矩阵这两个过程可以合并，也至少需要对全部数据进行三次遍历。在海量数据 PCA 处理时，磁盘 IO 是一个主要瓶颈，对全量数据进行三次遍历将使时间大大增加。即便是采用 MapReduce 分布式并行处理方法，多次遍历数据也是十分低效的。为了适应 MapReduce 计算框架，也为了减小对数据的遍历次数，根据 PCA 的计算方法，本文对传统的 PCA 计算步骤进行了修改。修改后的步骤如下： 1). 计算样本矩阵的平方矩阵 U= ，计算方法如下： 2). 计算样本的和向量 e，以及平方和向量 f。 125 130 3). 求相关系数矩阵 R= ，由上节介绍的相关系数矩阵的求解方法进行推导，可得： - 5 - ijppu1 nijkikjkuxx213,,,..., peeeee1 1,2,3,...,nikikexin213,,,..., 1,2,3,...,pffffinf21 1,2,3,...,nikikfxinijppr

中国科技论文在线 http://www.paper.edu.cn 135 前三步的计算相关系数举证的过程由 MapReduce 计算框架实现，之后的步骤与传统 PCA 计算方法完全相同，也是采用单节点计算。本文 MapReduce 计算方法涉及一个 Map 过程和一个 Reduce 过程。 Map 过程负责对数据进行遍历，每个 mapper 实体（Map 阶段的 Worker）处理一部分样本。多个 mapper 实体分别计算自己负责样本的数量，平方矩阵，和向量，以及平方和向量。 140 在 Reduce 过程中，只需要一个 Reducer（Reduce 阶段的 Worker），将 Map 阶段各个 mapper 求得的平方矩阵全部相加，得到和矩阵就是全部样本的平方矩阵 U；将各个 mapper 输出的和向量、平方和向量分别相加，得到的就是所有样本的和向量 e，以及平方和向量 f。所有的样本总数目 n 也是在 reduce 过程汇总。 MapReduce 程序的处理过程如图 2 所示。 145 图 2 MapReduce 程序过程 Fig. 2 MapReduce application process 4 实验本文对基于 MapReduce 的 PCA 算法进行性能对比测试。程序运行在 Hadoop 集群上， 150 集群由 10 台 PC 机组成，1 台 namenode 负责集群的协调管理，9 台 datanode 复杂数据存储与计算。每台 PC 机的配置为：双核 2.8GHz CPU，4GB 内存，2TB 硬盘。软件配置为：操作系统为 Red Hat Enterprise Linux Server release 5.5，hadoop 版本为 0.20.2。 - 6 - ij22///ijijiijjueenrfenfen样本集1样本1平方矩阵Mapper1样本1和向量样本1平方和向量样本集2Mapper2样本集kMapperkreducer相关系数矩阵样本2平方矩阵样本2和向量样本2平方和向量样本k平方矩阵样本k和向量样本k平方和向量

中国科技论文在线 http://www.paper.edu.cn 对比软件为 WEKA 和 SPSS，由于这两个软件使用安装环境限制，所以采用 windows 环境 PC 机运行。机器配置为：双核 2.0 Ghz CPU，3GB 内存。WEKA 与 SPSS 软件的计算 155 过程全部在内存中完成，数据读入内存和 PCA 计算两部分时间之和，作为总共的计算时间。本文所提出的 MR 方案(MapReduce 方案)时间也分为两部分：求相关系数矩阵，以及求特征向量。这两部分时间之和作为整个 PCA 的计算时间。 4.1 模拟数据实验模拟样本数目为 n，样本变量个数为 p，其中独立变量个数为 h 向下取整，h 为 p/8 的结 160 果下取整，余下的 p – h 个变量是这 h 个独立变量的线性组合。即样本：其中之间相互独立，是自变量的一次函数。实验一 165 保持样本数目 n=20000 保持不变，样本变量个数 p 依次增大，实验结果如表 1 所示。表格 1不同变量个数情况下的性能对比 TABLE. 1 The performance comparison in the case of different variables 样本变量个数 p 200 300 400 500 600 700 800 装载时间(s) 计算时间(s) 总时间(s) 装载时间(s) 计算时间(s) 总时间(s) 1 140 141 10 10 20 3 318 321 14 22 36 7 558 565 19 15 34 10 905 915 25 17 42 14 14 16 1397 2022 2769 1411 2036 2785 30 24 54 31 38 69 33 45 78 求相关系数矩阵(s) 22.1 26.3 32.3 30.4 38.4 43.2 53.3 求特征向量(s) 总时间(s) 0.6 1.1 2.0 4.2 6.8 11.6 18.1 22.7 27.3 34.2 34.6 45.2 54.8 71.4 WE KA SPS S MR 方案实验二保持样本变量个数 p=200 不变，样本数目 n 依次增大，实验结果如表 2、表 3 所示： - 7 - 123,,,,..1,2,3,...,.,iiiiipxxxxinx()12,,...,1,2,.,..,()ihkkiiihxfxxxkph123,,,., ..iiiihxxxx12,, ,kiiihfxxx

中国科技论文在线 http://www.paper.edu.cn 170 表格 2不同样本数目情况下的性能对比(1) TABLE. 2 The performance comparison in the case of different samples (1) 样本数目 n(万) 装载时间(s) 计算时间(s) 总时间(s) 装载时间(s) 计算时间(s) 总时间(s) 3 5 241 246 12 12 24 4 35 310 345 17 16 33 5 9 384 393 24 14 38 6 11 459 470 28 12 40 7 12 546 558 31 20 51 求相关系数矩阵(s) 21.6 21.5 19.6 19.7 20.5 8 14 649 663 38 13 51 22 10 17 741 758 45 15 60 25.9 求特征向量(s) 总时间(s) 0.5 22.1 0.5 22 0.6 0.5 20.2 20.2 0.5 21 0.5 0.5 22.5 26.4 WE KA SPS S MR 方案 175 TABLE. 3 The performance comparison in the case of different samples (2) 表格 3不同样本数目情况下的性能对比(2) SPS S MR 方案样本数目 n(万) 装载时间(s) 计算时间(s) 总时间(s) 15 57 14 71 20 76 18 94 求相关系数矩阵(s) 28.5 29.3 求特征向量(s) 0.5 0.6 25 85 16 101 30.5 0.6 30 113 19 132 32.4 0.5 35 160 20 180 37.8 0.5 40 183 22 205 36.2 0.6 总时间(s) 29.0 29.9 31.1 32.9 38.3 36.8 当样本数目 n 大于等于 15 万时，WEKA 由于内存限制已经无法进行计算。当样本数目大于等于 45 万时，SPSS 也因为内存限制无法进行计算。而本文提出的 MR 方案，并不是将所有数据放入内存中计算，所以可以处理海量样本的情况。从表 2、表 3 可以明显看出，随着样本数目的增加 MR 方案的优势变得越来越明显。 180 当样本数目 n 大于等于 200 万时，MR 方案性能测试如图 3 所示。 - 8 -

分享到：

赞收藏

资料库

论文研究-分布式并行PCA算法在大样本数据集中的应用 .pdf

相关推荐

开发技术

热门标签

最新资料