并行数据挖掘算法综述
并行数据挖掘算法综述
(1)数据集并行 当训练数据集从原始数据中抽出后,被分割成N个子集,各个子集独立分布在不同处理器中进行处理,各处理器处理完数据子集,由主处理器进行综合处理,产生最后结果的最优决策树。
(2)属性并行 决策树中属性与属性之间是相互独立的,因此对各个属性信息增益比的计算可以在不同的子处理器上进行,最后将结果反馈给父处理器,进行综合分析。
(3)混合并行 通过属性并行方法,可以并行计算信息增益比。但数据分片不能并行处理。另外,充分利用数据集并行很难实现循环并行的线性加速,因此可以考虑将属性并行和数据集并行结合起来使用,即混合并行。 1.1.2 结点间并行
结点间并行是在多个节点间进行并行处理。决策树在对当前结点进行分割后,将形成若干个子结点,这些子结点不存在任何依赖关系,则可以进行并行处理。决策树的结构使这种并行性具有良好的可理解性。 1.2 SLIQ算法
关。
1.2.2 分布类列表方式(SLIQ/D)
这种方式将类列表分解至多个处理器上,每个减小了对内存的限制。处理器仅保存类列表的1/N,
在扫描每个属性列表时,需同时查看类别标识和每个属性相应的指针,每个处理器都要做N-
1
次通N
信,通过批处理降低了请求查看属性列表的通信代价,但其远程查看请求的代价仍然很高,且更新类列表通信也使其运行效率有所降低。
1.3 SPRINT算法
SPRINT算法是在无共享的并行环境下的实现,N个处理器都有各自的内存和硬盘,通过通信网络来传递信息。创建决策树的过程分为树构建和剪枝两个阶段。 1.3.1 关键技术
SPRINT算法采用了属性列表和类统计分布图两种数据结构。属性表由属性值、类别标识和数据记录的索引(rid)组成,随节点的扩展而划分。类统计分布图描述节点上某个属性的类别分布。当描述连续属性时,节点上关联两个统计矩形表:Cbelow,
SLIQ是一个能够处理连续及离散属性的决策树分类器。在树的构建阶段使用了预排序(Pre-sorting)技术减少计算连续属性的代价,广度优先的建树策略分类驻留在磁盘上的数据集。同时,使用了快速分割子集算法以确定离散属性的分支及最小描述长度(MDL)原理的树修剪算法。故
Caove,前者描述已处理过的类,后者描述未处理过的分布;当描述离散属性时,节点上只关联一个记数矩阵。类统计分布图主要用于计算对应节点的最佳分割属性。
在SPRINT算法中,如何最好的分割某个节点是采用gini参数度量的。gini参数最小的对应的属性被选做该节点的分割属性。对连续属性,侯选分割点为训练集中相邻属性值的中点;对离散分割点,需要对属性列表一次扫描求出计数矩阵的统计数据。
在确定某个节点的最佳分割属性后,SPRINT算法将每个记录的rid插入哈希表以便对其他属性进行分割。采用哈希表克服了SLIQ方法需要类列表常驻内存的缺陷。 1.3.2 并行实现
在SPRINT树的剪枝阶段计算耗时不大,故
SLIQ能处理大规模的数据集,不限制训练数据的数量及属性的数量,提高了分类精度。
SLIQ使用的数据结构是类列表,它需要随机访问并频繁更新,这就要求类列表必须常驻内存。以下就SLIQ并行处理两种方式进行分析。 1.2.1 复制类列表方式(SLIQ/R)
按选定的分割点进行属性列表的划分时,需对每个训练样例更新其类列表。因此,每个处理器的本地内存中都有一个与整个数据集上的类列表一致的备份,这就需要各处理器间的协调通信来完成类列表的更新。这种方式的缺点是单个处理器内存的大小限制了可处理的训练集的大小,仅能处理类列表比内存小的训练集,但与处理器的数目无66 IT Age/ Jan. 15, 2006
SPRINT算法的并行集中在建树阶段。
在并行建树中通过将属性列表平均分配到N个处理器上,解决了以前SLIQ算法中需要将训练数
数据挖掘算法综述_IT认证_资格考试/认证_教育专区。无20 10 年 8 月 电 脑...神经网络的优点就是并行分布处理能力强,分类的准 确度高, 对噪声数据有较强的...
并行频繁项集挖掘算法综述 陈晓云 赵娟 (兰州大学信息科学与工程学院 兰州 ...由于数据挖掘在开始被提出时就是面向海量数据的, 庞大的搜索空间使得许多传统的...
数据挖掘方法综述摘 要:首先介绍了数据挖掘的概念,再从挖掘对象、挖掘方法和挖掘...遗传算法具有的隐含并行性、易于和其它模型结合等性质使得它在数据挖掘中被 加以...
序列模式挖掘算法综述_IT/计算机_专业资料。该文档详细叙述了数据挖掘中的序列模式...由于本身良好的鲁棒性、自组织自适应性、并行处理、分布存储和 高度容错等特性...
数据挖掘层次聚类算法研究综 数据挖掘层次聚类算法研究综述 层次聚类算法研究 摘要...参考文献 [1]王里.并行层次聚类技术研究,硕士学位论文.湖南大学.2006.12 [2]...
电脑知识与技术 数据库与信息管理 数据挖掘算法研究与综述王元志, 王芳 ( 徐州...遗传算法的优点是容易并行化, 但它也存在许多缺点: 遗传 算法对于最终用户来说...
并行数据挖掘这一结台并行计算技术和数据挖掘技术 在社会各个方面得到了大规模的...文献(4,5】已经对这些算法做了一个全面的综述。并行化 总是体现在两个方面:...
数据挖掘中的文本挖掘的分类算法综述_IT/计算机_专业资料。数据挖掘文本挖掘的分类...源于高 性能(并行)计算的技术在处理海量数据集方面常常是重要的。分布式技术也能...
离群数据挖掘综述 6页 免费 基于聚类高维空间算法的离... 5页 免费 基于聚类...利用并 行计算和 属性相 关性分 析思想, 给出 了一 种离群数据并行挖掘算法...
数据的转换。将数据转换成一个分析模型,这个分析模型是针对挖掘算法建立的, 建立...3.2 神经网络方法 3 神经网络由于本身良好的鲁棒性、自组织自适应性、并行处理...
热门文档