MapReduce海量数据并行处理-数据挖掘基础算法.ppt

MapReduce并行化算法设计思路 根据前述的思路，判断一个未标记的测试样本属于哪个类Yi的核心任务成为：根据训练数据集计算Yi出现的频度和所有属性值xj在Yi中出现的频度。 据此，并行化算法设计的基本思路是：用MapReduce扫描训练数据集，计算每个分类Yi出现的频度FYi (即P(Yi))、以及每个属性值出现在Yi中的频度Fxij (即 P(xj|Yi)) 而在MapReduce中对训练数据集进行以上的频度计算时，实际上就是简单地统计Yi和每个xj出现的频度 在进行分类预测时，对一个未标记的测试样本，根据其包含的每个具体属性值xj，根据从训练数据集计算出的Fxij进行求积得到FXi(即P(X|Yi))，再乘以FYi即可得到X在各个Yi中出现的频度P(X|Yi)P(Yi)，取得最大频度的Yi即为X所属的分类。 MapReduce并行化算法实现 训练数据集频度统计Mapper伪代码 class Mapper map(key, tr) // tr为一个训练样本 { tr ? trid, A, y emit(y, 1) for i=0 to A.lenghth) { A[i] ? 属性名an和属性值av emit(y, an, av, 1) } } MapReduce并行化算法实现 训练数据集频度统计Reducer伪代码 class Reducer reduce(key, value_list) // key 或为分类标记y，或为y, an, av { sum =0 while(value_list.hasNext()) sum += value_list.next().get(); emit(key, sum) } 输出结果为所有Yi的出现频度FYi,以及所有属性值xj在Yi中的出现频度 进行未标记测试样本X分类预测时，可以从这个输出数据文件中快速查找相应的频度值并最终计算出X在各个Yi中出现的频度P(X|Yi)P(Yi)，最后取得最大频度的Yi即为X所属的分类 MapReduce并行化算法实现 测试样本分类预测Mapper伪代码 class Mapper setup(…) { 读取从训练数据集得到的频度数据 分类频度表 FY = { (Yi, 每个Yi的频度FYi) } 属性频度表 Fx = { (Yi, an, av, 出现频度Fxij ) } } map(key, ts) // ts为一个测试样本 { ts ? tsid, A MaxF = MIN_VALUE; idx = -1; for (i=0 to FY.length) { FX = 1.0；Yi = FY[i].Yi; FYi = FY[i].FYi for (j=0 to A.length) { an = A[j].an; av = A[j].av 根据Yi, an, av扫描Fx表, 取得Fxij FX = FX * Fx[i][j]; } if(FX* FYi MaxF) { MaxF = FX*FYi; idx = i; } } emit(tsid, FY[idx].Yi) } 决策树分类并行化算法的基本处理思路 决策树的最关键技术是如何递归地在决策树的节点上选取最好的分支属性，而属性通常用信息增益(information gain）进行度量。 信息增益的计算通常需要求取与前述朴素贝叶斯分类方法中的分类标记频度或“分类标记-属性名-属性值”的出现频度。 因此，决策树分类算法中信息增益的计算方法与前述朴素贝叶斯分类算法的处理过程类似。 在一层属性选择完成后，训练数据将被分为数个数据数据子集，然后再用MapReduce过程对每一个子集递归地进行下一层属性的选取。 在以上属性选取过程中，逐步形成决策规则 对测试样本进行分类预测时，将利用所产生的决策规则来进行匹配处理，最终得出测试样本的分类标记。 9.1数据挖掘并行算法研究的重要性 9.2 基于MapReduce的K-Means聚类算法 9.3 基于MapReduce的分类算法 9.4 基于MapReduce的频繁项集挖掘算法 1.频繁项集挖掘问题概述 2. 现有算法概述 3. PS