基于r语言跨平台大数据机器学习及数据分析系统.pdf

Octopus（大章鱼）： 基于R语言的跨平台大数据 机器学习不数据分析系统 黄宜华 南京大学PASA大数据技术实验室 南京大学计算机软件新技术国家重点实验室 江苏省软件新技术不产业化协同创新中心 2015.12.12 … … 南京大学PASA大数据技术实验室 PASA BigData Lab studies on Parallel Algorithms Systems, and Applications for Big Data Processing We are one of the earliest research labs on Big Data in China, entering big data research area since 2009 南京大学PASA大数据技术实验室  南京大学PASA大数据实验室是国内最终从事大数据技术研究和教学的团 队之一早在大数据还鲜为关注的2009年，本实验室已经进入大数据技 术研究领域实验室自2009年以来在大数据技术领域开展了一系列系统 深入的研究开发工作，在分布式大数据存储和查询、分布式文件系统、 大数据幵行计算模式不系统、Hadoop/Spark性能优化不功能增强、幵 行化机器学习和数据挖掘算法、大数据机器学习系统、大规模Web信息 挖掘集成、大规模文本语义分析、幵行机器翻译算法、大数据行业应用 等方面，开展了广泛的研究，积累了系统的研究和技术基础，近6年来课 题组在国内外学术期刊和国际会议上发表了大数据相关研究论文30多篇， 撰写大数据技术书籍/教材两部  实验室承担国家级、部省级大数据研究项目多项，幵开展了不Google、 Intel、微软亚洲研究院、百度、华为、中兴通讯等国内外著名企业开展 合作研究；此外还不UC Berkeley AMP实验室在Spark和分布式内存文 件系统Tachyon方面开展合作研究；此外，课题组还开展了电力、电信、 等典型行业的大数据平台和分析应用研究 南京大学PASA大数据技术实验室 Our research areas Parallel Computing Models and Frameworks – Phase Ⅱ: Iteratively generate (k+1)-frequent itemset from k-frequent itemset. 基于Spark的频繁项集挖掘算法 Hongjian Qiu, Rong Gu, Chunfeng Yuan and Yihua Huang. YAFIM: A Parallel Frequent Itemset Mining Algorithm with Spark. The 3rd International Workshop on Parallel and Distributed Computing for Large Scale Machine Learning and Big Data Analytics, conjunction with IPDPS 2014, May 23, 2014. Phoenix, USA 1. 大数据机器学习：从算法到系统 All transaction data reside in RDD Load all transaction data into a RDD 频繁项集挖掘并行化算法 Frequent Itemset Mining Algorithm 基于Spark的频繁项集挖掘算法 1. 大数据机器学习：从算法到系统 Phase Ⅰ 频繁项集挖掘并行化算法 Frequent Itemset Mining Algorithm 基于Spark的频繁项集挖掘算法 1. 大数据机器学习：从算法到系统 Phase ⅠI 频繁项集挖掘并行化算法 Frequent Itemset Mining Algorithm 基于Spark的频繁项集挖掘算法 1. 大数据机器学习：从算法到系统 频繁项集挖掘并行化算法 Frequent Itemset Mining Algorithm 基于Spark的频繁项集挖掘算法 1. 大数据机器学习：从算法到系统 频繁项集挖掘并行化算法 Frequent Itemset Mining Algorithm 基于Spark的频繁项集挖掘算法 1. 大数据机器学习：从算法到系统 基于Spark的并 行化算法比基 于Hadoop MapReduce的并 行化算法大约 快18倍 K-Means聚类并行化算法 K-Means Clustering Algorithm 基本算法 Input: A dataset of N data points that need to be clustered into K clusters Output：：K clusters Choose k cluster center Centers[K] as initial cluster centers Loop: for each data point P from dataset： ｛ Calculate the distance between P and each of Centers[i] ； Save p to the nearest cluster center ｝ Recalculate the new Centers[K] Go loop until cluster centers converge 1. 大数据机器学习：从算法到系统 class Mapper setup(…) { read k cluster centers  Centers[K]; } map(key, p) // p is a data point { minDis = Double.MAX VALUE; index = -1; for i=0 to Centers.length { dis= ComputeDist(p, Centers[i]); if dis convergeDist // count for P(xj|Ci) and P(Ci) while(value_list.hasNext()) sum += value_list.next().get(); emit(key, sum) } // Trim and save output as P(xj|Ci) and P(Ci) tables in HDFS 朴素贝叶斯并行化算法 NaiveBayes Classification Algorithm 基于MapReduce的朴素贝叶斯并行化算法 1. 大数据机器学习：从算法到系统 Predict Map Pseudo Code to Predict Test Sample class Mapper setup(…) { load P(xj|Ci) and P(Ci) data from training stage FC = { (Ci, P(Ci)) }, FxC = { (, P(xj|Ci)) } } map(key, ts) // ts is a test sample { ts  tsid, X MaxF = MIN_VALUE; idx = -1; for (i=0 to FC.length) { FXCi = 1.0；Ci = FC[i].Ci; FCi = FC[i].P(Ci) for (j=0 to X.length) { xnj = X[j].xnj; xvj = X[j].xvj Use to scan FxC, get P(xj|Ci) FXCi = FXCYi * P(xj|Ci); } if(FXCi* FCi MaxF) { MaxF = FXCi*FCi; idx = i; } } emit(tsid, FC[idx].Ci) } 朴素贝叶斯并行化算法 NaiveBayes Classification Algorithm 基于MapReduce的朴素贝叶斯并行化算法 1. 大数据机器学习：从算法到系统 parseVector RDD lines . 行向量矩阵（DenseVecMatrix） 分布式矩阵的划分表示方法 块矩阵（BlockMatrix） Block BlockMatrix Block Block Block . . . . . 问题：为了完成大规模矩阵的分布式和并行化计算，需要考虑大规 模分布式矩阵的划分表示方法 大规模分布式矩阵运算优化 分布式矩阵乘法 A11A12 A21A22 B11B12 B21B22 A11B11 A12B21 A11B12 A12B22 A21B11 A22B21 A21B12 A22B22 C111C211 C112C212 C121C221 C122C222 + + + + C11 C12 C21 C22 = = = = C11C12 C21C22 C111 C211 C112 C212 C121 C221 C122 C222 A11B11 A12B21 A11B12 A12B22 A21B11 A22B21 A21B12 A22B22 = = = = = = = = FlatMap&Join Map GroupBy&Reduce Result FlatMap&Join Map GroupBy&Reduce Result 对相乘的两个矩阵进行分块分块，再把子矩阵按一定规则进行分发分发和JoinJoin操作， 再对Join后的元组进行相乘相乘，最后按一定规则把相乘的结果进行相加相加。

Spark Cluster Server Nodes 分布式矩阵的划分和并行化调度计算 Large Scale Matrix Partition and Optimized Execution Schedule and Dispatch 大规模分布式矩阵运算优化 分布式矩阵乘法优化 大规模分布式矩阵运算优化 1. 适用于方形矩阵相乘的均匀划分方法 2. 适用于长条形矩阵相乘的递归自适应划分方法 3. 适用于一大一小矩阵相乘的Broadcast矩阵划分方法 4. 基于BLAS的子矩阵本地化运算加速优化 问题： 不同的矩阵划分方法会造成计算性能的巨大差异，为此需要根据矩 阵大小、形状和计算特点的不同，考虑优化的矩阵划分方法 为此,我们研究提出了三种针对大规模矩阵乘法的不同矩阵划分方 法，同时还研究利用BLAS矩阵运算库进行本地子矩阵运算加速优化 分布式矩阵乘法优化 大规模分布式矩阵运算优化 大规模矩阵乘法分布式计算时，矩阵的划分方法直接关系到矩阵计算性能 我们研究实现了基于矩阵大小和形状特征的自动化矩阵划分和调度计算方 法，并完成基于Spark、Hadoop、MPI、Flink的分布式矩阵乘法计算 均匀划分 递归自适应划分方法 Broadcast矩阵划分 方形矩阵相乘方形矩阵相乘 长条形矩阵相乘法长条形矩阵相乘法 一大一小矩阵阵相乘法一大一小矩阵阵相乘法 分布式矩阵乘法优化 大规模分布式矩阵运算优化 1. 适用于方形矩阵相乘的均匀划分方法 适用性：适用于两个方形或近似方形矩阵的相乘 方 法：均匀划分，划分块的行数不列数相等，使每个子矩阵的规模相等 9 9 3 3 3 3 3 3 将9 x 9的矩阵 划分为3 x 3块 分布式矩阵乘法优化 大规模分布式矩阵运算优化 适用性：适用于矩阵长宽相差较大的长条形矩阵 方 法：每次选取最长的边进行划分，给每个子矩阵分块分配计算核， 当计算核的个数或最大边长为1时停止划分 m k k n 计算核数= m= k= n= 8 4 2 1 500 1000 1200 600 500 300 2. 适用于长条形矩阵相乘的递归自适应划分方法 分布式矩阵乘法优化 大规模分布式矩阵运算优化 A11 A21 A31 B A41 A11 A21 A31 B B。