云计算下的海量数据挖掘研究

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