雨林算法框架讲座ppt课件.ppt

《雨林算法框架讲座ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、RainForest——雨林算法框架大数据集决策树快速生成框架报告人：马文国Wednesday,July28,2021决策树简介略Sprint算法的缺点为每个node都保存属性表，这个表的大小有可能是数据库中原始数据大小的好几倍。维护每个node属性表的hash表的开销很大(该表的大小与该node所具有的纪录成正比)。雨林算法框架综述过去的研究提出了多种决策树算法，但是到目前为止并没有一种算法在任何数据集合下生成决策树的质量方面超过所有其他的算法雨林算法框架关注于提高决策树算法的伸缩性，该框架可运用于大多数决策树算法(例如Sprint和SL

2、IQ)，使算法获得的结果与将全部的数据放置于内存所得到的结果一致，但是在运行时可以使用较少的内存。而在内存一定的情况下，也可以更好的满足算法的需求。生成的决策树的质量取决于具体的决策树算法，于本框架无关。雨林算法框架数据结构：AVC-set:节点n包含的所有纪录在某个属性上的投影，其中该AVC-set包括了属性的不同值在每个类别上的计数。AVC-group:一个节点n上所有的AVC-set的集合AVC-set的所占内存的大小正比于对应属性的不同值个数，AVC-group并不是数据库信息的简单的压缩，它只是提供了建立决策树需要的信息，AVC-

3、group所占用的内存空间远远小于数据库所实际占用的空间。设计方案:AVC_set{//存储属性的各个值DistinctValue[]//存储属性各个值在某个类上对应的计数DistinctValueCountForClassA[]DistinctValueCountForClassB[]……}AVC_group{//节点n中的每个属性的avc_setAVC_set[]}雨林算法框架自顶向下决策树算法BuildTree(Nodem,datapatitionD,algorithmdecisionTree)对D使用决策树算法decisionTre

4、e得到分裂指标crit(n)令k为节点n的子节点个数if(k>0)建立n的k个子节点c1,…,ck使用最佳分割将D分裂为D1,…,Dkfor(i=1;i<=k;i++)BuildTree(ci,Di)endforendifRainForest算法框架重新定义的部分：1a)for每一个属性的谓词p,寻找最佳的分割1b)decisionTree.find_best_partitioning(AVC-setofp)1c)endfor2a)k=decisionTree.decide_splitting_criterion();//决定最终的分割算法

5、分析对于(1a)-(1c)所需要的内存为该谓词p所有的avc-set中间占有的最大内存。在(2a)中，使用的输入是由(1a)-(1c)所计算出来的结果，这里所占用的内存时很小的针对上述情况，我们假定现实运行的情况下，一个节点的整个avc-group都可以放在内存中，或者至少一个节点的每一个独立的谓词的avc-set可以放在内存中。雨林算法的常规过程建立节点的AVC-group(通过读取整个原始数据库或者某个分支的数据库表或文件)选择分裂属性和分裂标准：取决于使用雨林算法框架的具体算法，通过逐一检查AVC-set来选择。将数据分解到各个子节点

6、：必须读取整个数据集(数据库或文件)，将各条数据分解到各个子节点中，此时如果有足够的内存，我们将建立一个或多个子节点的AVC-group算法综述算法RF-Write，RF-Read，RF-Hybrid适用于整个根节点的AVC-group都可以放置到内存中的情况，RF-Vertical用于根节点(即一个节点)的AVC-group不能够存放到内存中的情况。本文假定任何一个属性的AVC-set都可以放在内存中。算法RF-Write检索数据库，建立根节点的AVC-group调用某个决策树算法以AVC-group为参数选择分裂标准，建立根节点的k个子

7、节点检索数据库(或文件)，将每一条纪录t分配到各个分支当中（纪录于数据库或文件）将该算法递归的应用于每一个分支注：对于决策树的每一层，算法读取数据库两次，并写数据库一次。算法RF-Read检索数据库，建立根节点的AVC-group调用决策树算法以AVC-group为参数选择分裂标准，建立根节点的k个子节点如果此时具有足够的内存容纳新的子节点的AVC-group,则此时对数据库进行一次检索，根据分裂标准将子节点的AVC-group计算出来，并放置于内存中，并调用决策树算法计算分裂标准。使用相同的方法处理树的每一层，只要有足够的内存容纳新节点的

8、AVC-group，就将所有子节点的AVC-group计算出来。算法RF-Read(续)假设在某一层所有新节点的AVC-group所占内存的大小超过了可用内存，此时我们可将新节点