基于云计算及数据挖掘技术的海量数据处理研究

Presentation on theme: "基于云计算及数据挖掘技术的海量数据处理研究"— Presentation transcript:

1 基于云计算及数据挖掘技术的海量数据处理研究
报告人：胡建政 2017年3月20日

2 前言 选择云计算做海量数据的分类数据挖掘处理，可以减少构建分布式计算平台的开销，同时将底层屏蔽掉，便于开发，使得原有的设备拥有对大数据集的较高处理效率，增加了节点的个数和容错能力，提高了从海量数据中提取有效信息的能力

3 SPRINT算法数据结构 SPRINT算法表示数据特征的方式是采用属性表与直方图这两种数据结构，其中，后者是依附在前者之上，而前者又是随着节点的划分而分裂的。它会依据属性的不同性质，如连续型或离散型而显现出相应的表现形式。

4 SPRINT算法数据结构 属性列表：（预排序） 属性值 类标记 记录索引

5 SPRINT算法数据结构 直方图 数值字段值： Cabove、Cbelow 种类字段值： count matrix

6 计算最佳分裂 SPRINT算法使用 Gini指数代替信息量作为选择最佳分裂点的依据，它对决策树的生成至关重要，Gini指数方法可以定义为：
对 于 有 n种类别的数据集S ，pi 为 S 种类别i 的相对频率. 对数据集 S 划分为 S1、S2 两个部分，分别有n1、n2 个记录，则对应的Gini指数定义为：

7 基于Hadoop的SPRINT算法的并行化
由于SPRINT算法能较好地支持并行处理即允许多处理器并行工作，所以可以利用Hadoop在并行处理方面的优势对SPRINT算法以并行的方式计算以减少串行计算时所带来的过大的时间复杂度.由此可以得到新的SPRINTbH(SPRINTbasedonHadoop)算法.

8 基于Hadoop的SPRINT算法的并行化
SPRINTbH算法描述： (1)首先根据训练数据集创建初始属性表，如果是连续属性，则要对属性表进行预排序. (2)由于MapReduce的函数的输入输出都会被存储在文件系统.所以输人是存放在文件中的已经预排序的属性表，在交给Map函数处理前，文件会被分割成多个文件块，每个文件块被分配存储到数据节点上，Map函数处理时，每个节点就近读取本地存储的数据处理.

9 基于Hadoop的SPRINT算法的并行化
(3)如果是连续属性，那么每个Map函数获得的就是以属性值大小排序的属性表，同时生成直方图.而属性值排序的顺序则是以Map函数读取的顺序.然后每个Map函数对自己获得的属性表进行最佳分裂点计算，即计算出在各自的Map函数处理环节的所有的gini值，实时更新直方图（对于离散属性，无需排序，直方图无需更新），并且找出其中的最优方案，即最小的gini值.对于分类属性，每个Map函数分别统计各自的属性记录的类的分布信息。

10 基于Hadoop的SPRINT算法的并行化
(4)每个Map函数在计算出各自的最优方案后，在输出过程中，会将所有具有相同属性的属性表求得的gini值合并，作为Reduce函数的输人，Reduce函数找出这所有的gini值中最小的值，确定全局的最优方案，即最佳分裂属性和分裂点.Reduce函数同时还要将Map函数中统计出的类的分布信息进行相加，得到全局的类分布频率。

11 基于Hadoop的SPRINT算法的并行化
(5)确定了最优方案以后，将Reduce的输出作为新的Map函数的输人，每个Map函数将各自的属性表划分到相应的子结点中.可以通过将划分到左子结点的属性的rid记录到事先建立好的哈希表中，即每个Map函数可以将自己统计的记录到哈希表的左子结点中的属性作为输出，传递给Reduce函数作为输人Reduce函数统计所有的Map函数的输出，得到所有的被划分到左子结点的属性.然后确定在这个结点中的所有的左子结点和右子结点的属性。 (6)重复(2)~(5)步骤，直到满足决策树结束条件

12 实验结果分析 把 SPRINTbH算 法 在 Hadoop平台上用打高尔夫球的训练数据集做实验，对这个算法的有效性进行验 证 ，其分布如表1 所示.

13 实验结果分析 通过实验验证得到在创建根节点时的经过预排序的属性表（如表2和表3所示）

14 实验结果分析 由Reduce函数进行处理得到的在确定根节点阶段的最优方案是在ginisplit(Outlook)时的值最小，所以将Outlook属性作为决策树的第一次分裂.创建的根节点处的哈希表如图2所示.

15 实验结果分析 5台pc机(其中一台主机，4台从机），采用SUSE以及Hadoop、Eclipse、JDK,.然后通过集群测试数据集在不同数量的节点上的运行时间.运行统计结果如图4所示：

16 结束语 在这个数据呈爆炸式发展的时代，各类企业对大规模及超大规模数据进行处理和和挖掘的强烈需求促生了数据挖掘以及云计算等技术。本文就是在这个大背景下，把数据挖掘分类算法同基于云计算的 HADOOP 集群框架进行结合，借助于其超凡的存储计算能力，达到了对海量数据挖掘的优化。

17 谢谢大家！！ 祝大家幸福快乐！