SPRINT算法

2003年3月24日星期一SPRINT:AScalableParallelClassifierforDataMining——SPRINT：一种用于数据挖掘的可伸缩并行分类器主讲人：梁敏第2页/共25页2003年3月24日星期一决策树分类算法SPRINT串行算法数据结构属性选择基本算法SPRINT并行算法SPRINT算法的性能评估总结内容简介第3页/共25页2003年3月24日星期一决策树分类算法决策树分类过程决策树生成算法分成两个步骤树的生成开始，数据都在根节点递归的进行数据分片树的修剪去掉一些可能是噪音或者异常的数据判定树分类算法output训练集决策树input第4页/共25页2003年3月24日星期一生成决策树的基本算法ProcedureBuildTree(S，A)(S:训练样本集，A：分类属性集合）用样本集S创建节点NifA为空then返回N，标记为S中最普遍的类ifN纯(pure)then返回Nelse{for每一个属性A估计该节点在A上的信息增益选出最佳的属性A*，将S分裂为Si，N长出分支foreachSiifSi为空then返回叶节点，标记为S中最普遍的类elseBuildTree(Si,A-A*)}第5页/共25页2003年3月24日星期一一般算法存在的伸缩性问题问题：限制训练样本存放在内存中。训练样本在内存和高速缓存中换进换出，效率低。一些改进方法采样方法数据分片、生成多树、多树合并构造新的数据结构第6页/共25页2003年3月24日星期一决策树分类算法SPRINT串行算法数据结构属性选择基本算法SPRINT并行算法SPRINT算法的性能评估总结第7页/共25页2003年3月24日星期一串行算法：数据结构属性列表：（预排序）属性值类标记记录索引第8页/共25页2003年3月24日星期一串行算法：数据结构直方图数值字段值：Cabove、Cbelow种类字段值：countmatrix第9页/共25页2003年3月24日星期一串行算法：属性选择统计度量：基尼指数——Giniindex集合S包含N个类别的记录，那么其Gini指标就是，pj类j出现的频率如果集合S分成两部分S1andS2。那么这个分割的Gini就是提供最小Ginisplit就被选择作为分割的标准数值字段：可能的分割点是每两个值的中点种类字段：可能的分割是属性值的所有子集2()11jnginiSpj1212()()()splitnnSginiginiginiSSnn第10页/共25页2003年3月24日星期一使用基尼指数进行属性选择如计算ginisplit(27.5)S1:S2:Ginisplit(27.5):同理：Ginisplit(18.5)=0.4Ginisplit(37.5)=0.417213(27.5)1()03giniS22212(27.5)1(()())0.4433giniS33(27.5)*0*0.440.2266splitgini第11页/共25页2003年3月24日星期一串行算法：基本算法ProcedureBuildTree(S，A)(S:训练样本集，A：分类属性集合）初始化样本集S，生成有序属性列表和直方图，创建节点队列，放入Nwhile队列不为空{从队列中取出第一个节点NifN纯or为空then标记为叶节点，continueforN的每一个分割点F计算该节点F上的基尼指数，选出最佳分割点F*，N长出分支节点N1、N2，放入队列中。将该分割点的属性列表分割，并用该列表的rids生成记录所在节点的哈希表，用哈希表分割其他属性列表，列表分割同时生成属性直方图。}第12页/共25页2003年3月24日星期一属性列表分割如图：第13页/共25页2003年3月24日星期一与SLIQ的比较SLIQSPRINT数据结构属性列表：属性值、索引类列表：类标签、指针直方图属性列表：属性值、类标记、记录索引直方图属性选择Gini指数Gini指数算法分割时只需变换类表中节点的指针，无需分割属性表。类表必须常驻内存。分割属性列表，并用该列表的rids生成记录元组所在节点的哈希表，用该哈希表分割其他属性列表。第14页/共25页2003年3月24日星期一决策树分类算法SPRINT串行算法数据结构属性选择基本算法SPRINT并行算法SPRINT算法的性能评估总结第15页/共25页2003年3月24日星期一并行算法数据分布：在N个处理器间平均分配属性列表属性选择统计度量仍用基尼指数，但对节点的属性直方图的处理与串行时有不同。数值字段：Cbelow和Cabove必须记录整个节点的类个数，因此在计算最佳分割点前，各处理器的Cbelow和Cabove要进行全局初始化。种类字段：countmatrix也必须记录整个节点的类个数，因此在分割前由某一处理器统计全局个数，各处理器按它更改。节点分割：唯一增加的步骤是要从各处理器收集rids，来生成节点的哈希表。第16页/共25页2003年3月24日星期一与SLIQ的比较SPRINTSLIQ/RSLIQ/D数据分布平均分配属性表平均分配属性表每个处理器都有一张完整的类表。平均分配属性表每个处理器只有1/N份类表。属性选择属性直方图要进行全局初始化。选处理器中gini值最小的分割点。属性直方图要进行全局初始化。选处理器中gini值最小的分割点。属性直方图要进行全局初始化。计算数值字段的分割点时，各处理器要交换大量的信息。选处理器中gini值最小的分割点。节点分割收集rids，生成节点的哈希表，分割属性表。类表更新，在所有处理器交换信息。类表更新，在所有处理器交换信息。第17页/共25页2003年3月24日星期一决策树分类算法SPRINT串行算法数据结构属性选择基本算法SPRINT并行算法SPRINT算法的性能评估总结第18页/共25页2003年3月24日星期一SPRINT算法与SLIQ算法的执行比较串行环境刚开始SPRINT比SLIQ时间消耗高一些，样本继续增加后，SLIQ失效。第19页/共25页2003年3月24日星期一SPRINT算法与SLIQ算法的执行比较并行环境相同处理器的条件下，相应时间：SLIQ/DSLIQ/RSPRINT第20页/共25页2003年3月24日星期一SPRINT算法在并行环境中的伸缩性与理想状态有差距是由创建rids的哈希表所用时间造成的。第21页/共25页2003年3月24日星期一SPRINT算法在并行环境中的加速性与理想状态有差距是由处理器交换信息和创建rids的哈希表所用的时间造成的。第22页/共25页2003年3月24日星期一SPRINT算法在并行环境中的扩容性优于理想状态是因为处理器间选择分割点和属性直方图初始化的交流耗费是不随样本量改变的。第23页/共25页2003年3月24日星期一决策树分类算法SPRINT串行算法数据结构属性选择基本算法SPRINT并行算法SPRINT算法的性能评估总结第24页/共25页2003年3月24日星期一总结优点：训练样本量不受内存限制。具有优秀的伸缩性、加速性和扩容性。并行实现容易，效率高。缺点使用属性列表，使存储代价是原来的三倍。节点分割要创建哈希表，加大系统负担。节点分割处理相对复杂。第25页/共25页2003年3月24日星期一谢谢！