《云计算下的海量数据挖掘研究》由会员分享，可在线阅读，更多相关《云计算下的海量数据挖掘研究（27页珍藏版）》请在金锄头文库上搜索。
1、云计算下的海量 数据挖掘研究关键词-云计算;数据挖掘;Hadoop;SPRINT;MapReduc云计算的出现为愈来愈多的中小企业分析海量数据提供廉价的解决方案。在介绍基于云计算的Hadoop集群框架和 数据挖掘技术中的SPRINT 分类算法的基础上详细描述SPRINT并行算法在Hadoop中的MapReduce编程模型上的 执行流程并利用分折出的决策树模型对输入数据进行分类引 言云计算的应用价值得到了包括IBM、Google在内的众多公司的重视其未来将像工业革命一样影响计算机应用的 发展 目前云计算处于研究和应用的初级阶段ll1云计算走出实验室迈向商业化指日可待云计算的特点使存储 及数据商业
2、化海量数据存储和挖掘是一个具有理论和应用价值的研究领域本稿在云计算开源框架下对虚拟银 行提出海量数据挖掘算法和应用并给出了实施步骤Hadoop及MapReduceHad00p是Apache下的一个开源软件，它最早是作为一个开源搜索引 擎项目Nutch的基础平台而开发的随着项目的进展，Hadoop被作 为一个单独的开源项目进行开发。HadooD作为一个开源的软件平台 使得编写和运行用于处理海量数据的应用程序更加容易。HadoopHado0D框架中最核心的设计就是MapReduce和HDFS MapReduce的思想是由Google的一篇 论文所提及而被广为流传的简单的一句话解释MapReduce
3、就是任务的分解与结果的汇 总。HDFS是Hado0p分布式文件系统Hado0D Distributed File System 的缩写为分布式计算 存储提供了底层支持MapReducMapReduce从它名字上来看就大致可以看出个缘由两个动词map和reducemap就是将一个任务分解成为多个任务reduce就是将分解后多任务处理的结果汇总起来得出最后的分析结果 这不是什么新思想其实在多线程、多任务的设计中就可以找到这种思想的影子.不论是现实社会，还是在程序设计中一项工作往往可以被拆分成为多个任务.任务之间的关系可以分为两种:一种是不相关的任务,可以并行执行;另一种是任务之间有相互的依赖,先后
4、顺序不能够颠倒.这类任务是无法并行处理的 在分布式 系统中机器集群就可以看作硬件资源池将并行的任务拆分然后交由每一个空闲机器资源去处理能够极大地提高计算效率同时这种资源无关性对于计算集群的扩展无疑提供了最好的设计保证 任务 分解处理以后那就需要将处理以后的结果再汇总起来。这就是reduce要做的工作图1展示了MapReduce的工作模式map负责分解任务，reduce负责将分解的任务进行合并SPRINT算法改进SPRINT算法很早就用于数据挖掘中的分类中在数据挖掘 中具有很高的价值31。在云计算下具有分布特点在对比 其他算法的情况下，借用SPRINT分类特性经过改进用于云 计算海量数据挖掘决策
5、树是一树状结构.从 根节点开始,对数据样本 进行测试.根据不同的结 果将数据样本划分成不 同的数据样本子集.每个 数据样本子集构成一子 节点通过一系列规则对数据进行分 类的过程它提供一种在什么 条件下会得到什么值的类似规 则的方法。多数决策树算法都包括两个阶段：构 造树阶段和树剪枝阶段。在构造树阶 段，通过对分类算法的递归调用产 生一棵完全生长的决策树。树剪枝阶 段的目的是要剪去过分适应训练样本 集的枝条。这里主要研究构造树的阶 段决策树的概念SPKINT 改进后的基本思想直方图附属在节点上用 来描述节点上某个属性的 类别分布。当描述数值型 属性的类分布时，节点上 关联2个直方图。 前者描述已
6、处理样本的类 别分布后者描述未处理 样本的类别分布二者的 值皆随运算进行更新。当 描述离散属性的类分布时 ，节点上只有一个直方图 SPRINT剪枝采用了最小 描述长度原则。属性表由一个属性 值、一个类别标识 和数据记录的索引3 个字段组成。记录 全部数据无法驻留 于内存可将属性 列表存于硬盘上。 属性表随节点的扩 展而划分并附属 于相应的子节点。改进 SPRINT算 法定义了两 种数据结构 ，分别是属 性表和直方 图。最佳分裂属性的选择分裂指数是属性分裂规则优劣程度的一个度量Gini指数方法能够有效地搜索最佳分裂点 提供最小Gini指数的分割具有最大信息增益被选为最佳分割。在SPRINT算法中
7、采用了 Gini指数方法，这对于生成一棵好的决策树至关重要。Gini指数方法可以简述如下：(1)如果 集合T包含n个类别的m条记录，则其Gini指数为： (2)如果集合T分成T1和T2两部分， 分别对应m1和m2条记录，则此分割 的Gini指数为 寻找分裂属性及最佳分裂点：根据以上方法 得到所有属性的 候选最佳分裂点 选择具有最小 Gini值的侯选 最佳分裂点。 即为最终的最 佳分裂点相应属性为当 前分裂属性。SPRINT并行处理 在云计算下海量数据，多有并行数据发 生。处理好并行数据，减少数据容错 性。数据结构 SPRINT并行算法除了属性表和直方图外还 需要引入哈希表数据结构来存储分割点两
8、侧 的数据记录，为并行节点提供分割依据。哈希 表第i条记录的值代表原数据中第i条记录被划 分到的树节点号。哈希表分为两项：(NodeID ，SubNodeID)，NodeID代表树节点号 SubNodeID表示当前树节点的儿子节点号默 认SubNodeID为0时表示该记录位于树节点的 左子节点为1时位于树节点的右子节点。并行算法希表。各分站点根据哈希表分割其他属性列表，列表分割同时生成 属性直方图。SPRINT移植 经过以上对SPRINT算法改进后可以将 算法移植到云计算的MapReduce框架下 进行分布合成处理。SPRINT与MapReduce水平划分 结合算法描述从队列取出 第一个节点
9、N.初始阶段 所有数据记 录都在根节 点N.训练样 本只有一份Hadoop的 MapReduce要求 输入数据对训 练样本进行水平 平均分割分割 数目为M份此 工作由 InputFormat完 成。将数据块划 分为InputSplit对1M的训练集进行输入格式 化水平划分后要对数据格式进 行统一InputFormat实现了 RecordReader接口，可以将数据 格式化为对。具体 格式化为 ，这里A 表示数据表被平均分为 M份后，第n份表中的A列。 对 应第n个表中属性列表的数据单 元的索引值，对第n 个表中对应 属性的值。Class 代表记录的类 别。这样就可以做map操作了。 这里也是对
10、训练样本进行垂直分 割水平分割和垂直分割过程例如map生成了R 个partition文件， key值为A，B，C ，这里会把 partition中含有A 的交给同一个 reduce，B和C同 样由partition利 用模计算将 每个文件分 配到指定的 reduce上。map操作过程的 主要任务是对输 入的每个记录进 行扫描，将相同 key的键值对进行 划分归类，写到 相应文件中reduce操作。对于连续 属性要对属性值进行从 小到大排序排序同时 生成直方图，初始阶段 为0，为该节点对应记录 的类分布每个reduce 的任务计算分裂点的Gini值实时地 更新直方图。对于离散属性。 无需排序直方
11、图也无需更新 第一次扫描数据记录 就生成直方图。计算 每个分类子集的Gini 值。最后每个 reduce都会得出它所 计算属性列的最小分 裂Gini值及其分裂点每个reduce根据分裂点生成哈希表。哈希表化为键值对的数据结构为哈希表第N条记录的值代表原数据中第N条记录被划分到的树节点将reduce的输出进行比较。选择最小Gini值所对应的属性及其分裂点和哈希表对原数据表进行分裂。从节点N生成N 和N：节点，将 N ，N 压入队列对N1和N2:循环进行(1)(8) 操作。数据 样本都属于一类或者没有属 性 可操作或者训练数据样本 太少，则返回 队列如果 队列为空 退出 程序SPRINT 与Map
12、Reduce垂直划分结合算法描述垂直划分的SPRINT算法和水平算法相近只是在输人格式化阶段，对每个Inap的输入是不同的，最终具有相同键的输人被分配到唯一一个reduce上A、B、C和D分别代表以属性类别为key的键值对的集合，经过map的分配任务。将具有相同键即key通过Partition分配到唯一一个reduce中 这样在每个reduce中就可以对每个属性列进行求解最小Gini值和最佳分裂点，并且生成哈希表。最后比较每个reduce的输出从全局角度 选出最佳分裂点和哈希表，对原表进行分裂，然后迭代执行以上步骤，直到终止条件满足为止Research on Mass Data Mining
13、under Cloud Computing用模型对数据进行分类 对银行训练数据进行分类以建立分类模 型。训练数据的属性分别为编号、年 龄、收入、文化程度、拥有车数量、欠 款额和欠款时间。要根据这些属性对银 行客户进行信用风险等级进行评估将 客户分为两类。信用高风险用户和信用 低风险用户分类模型建立后就要对输入数据进行分类 了这里使用Java的if_else语句实现这个 决策树模型。然后就可以用模型对输入数 据分类了本文首先介绍了Hadoop及其M印Reduce编程模型然后针对MapReduce编程模型的程序执行可并行性提出 了基于决策树的可并行的SPRINT数据挖掘算法。最后给出SPRINT算法移植到MapReduce编程模型上的算法 描述然后利用if-else语句实现模型的具体建立
