第三章决策树分类算法的应用进展和发展前景ppt课件

《第三章决策树分类算法的应用进展和发展前景ppt课件》由会员分享，可在线阅读，更多相关《第三章决策树分类算法的应用进展和发展前景ppt课件（23页珍藏版）》请在装配图网上搜索。

1、机器学习 第3章 决策树学习决策树分类算法的进展决策树分类算法的开展前景 主要决策树算法最早的决策树算法是由Hunt等人于1966年提出的CLS。当前最有影响的决策树算法是Quinlan于1986年提出的ID3和1993年提出的C4.5。其它早期算法主CART、FACT、CHAID算法。后期的算法主要有SLIQ、SPRINT、PUBLIC等。决策树分类算法的进展 传统的决策树分类算法主要是针对小数据集的，大都要求训练集常驻内存，这使得在处置数据发掘义务时，传统决策树算法在可伸缩性、精度和效率方面遭到了很大的限制。而在实践的数据发掘运用中我们面临的数据集往往是容量宏大的数据库或者数据仓库，在构造

2、决策树时需求将庞大的数据在主存和缓存中不停的导入导出使得运算效率大大降低。针对以上问题许多学者提出了处置大型数据集的决策树算法。下面我们分三个方面对一些算法的改良进展讨论。1、数据预处置 数据发掘处置的是海量数据集不仅样本容量大、含有的属性集大而且数据中往往含有一些与发掘义务不相关和无意义的部分。在这样的数据集上进展分析会破费很长时间使得发掘义务不可行。此外决策者有时需求在数据的多个笼统层上进展分析以获得有价值的信息。在这种情况下我们需求先用过滤、概化和归约等方法对数据进展预处置然后再对预处置后的数据集进展发掘。1、数据预处置 数据概化是指将数据集从较低的概念层笼统到较高的概念层。面向属性的归

3、纳AOI是一种有用的概化方法它调查数据集中每个属性的不同取值，经过属性删除或者属性概化等操作在给定的概念分层上概化数据库，由此抽取有意义的知识。运用AOI方法能够出现的问题是:假设属性概化得太高能够导致过分概化,产生的规那么能够没有多少信息;而假设属性概化不到足够高的层次,那么能够概化缺乏,得到的规那么能够也不含多少信息。因此面向属性的概化该当把握好尺度。1、数据预处置 针对这个问题,有专家提出了一种新的基于信息增益比的数据概化方法ITA。其根本思想是给定一组候选的提取分层,ITA选择一个最优的提取并对原始数据库进展概化。其操作步骤可以概括为从原始数据库中选定某一属性,计算属性的信息增益比,假

4、设其值为I1;对于候选提取分层中的每一种提取,计算其针对选定属性的信息增益比,选择信息增益比最大的提取,假设该提取的信息增益比为I2;计算I2/I1，假设商大于给定阈值,那么对属性值进展概化,否那么删除该属性。ITA较好地保管了原始数据库中的类分布,数据库的尺寸也大大减小。这使得产生的决策树更加紧凑,大大减小了树的尺寸,而且精度也没有明显地降低。此外它适当地控制了面向属性归纳中的概化过程,自动选择对数据库的最优概化,弥补了AOI的缺陷。之后,又进一步提出了迭代ITA的思想,并将其运用于C4.5的每一次属性选择的迭代过程,更好地保管了原始数据库中的类分布。1、数据预处置 在实践运用中数据集往往含

5、有很多的属性，而有一些属性是多余的。直接利用这种数据集来产生决策树会添加存储和计算方面的负担。在这种情况下，对数据集进展紧缩或者精简是必要的。利用粗糙集实际中的不可分辨关系将数据集进展属性归约和数据过滤，去除与决策无关的多余信息也是当前比较抢手的研讨。将利用粗糙集简化后的数据集作为输入产生的决策树会更加紧凑。ciiipp12log2、抽样方法 在进展数据发掘的分类义务时利用抽样方法也可以提高决策树的效率，特别是当我们对算法的效率要求很高时。在构建决策树时可以对数据集进展抽样，也可以在产生节点的过程中对节点进展抽样。对数据集进展抽样是指利用统计抽样方法抽取整个数据集的一个子集，用该子集产生一棵决

6、策树对未知样本进展分类或者从中抽取分类规那么。这种做法的缺陷在于，经过子集产生的决策树只能捕捉到整个数据集的大体的信息，有能够漏掉数据集中有价值的方式。因此这种做法是以牺牲准确度为代价来提高运算效率的。另一种抽样方法节点抽样是决策树方法中特有的我们主要对其进展引见。2、抽样方法 树构造阶段在内部节点属性进展属性选择时，假设面对的是延续值属性，我们普通按如下方法选择最优分裂点split：设A为延续值属性,最多能够有n个属性值。先对数据集按照属性A从小到大进展排序排序后的结果为a1，a2，。按照排序后的顺序依次取分裂点，计算其属性选择度量值，如信息增益、基尼指数等，从而得到最优划分。假设ai属性选

7、择度量值最优，通常取split=ai+ai+1/2。对于延续值属性,为了在内部节点选择最优分裂点需求对每个属性的每个取值计算其相应的基尼指数。当训练样本非常大时,计算量也会很大。针对这一问题,B.Chandra等人指出，可以选择一个适宜的间隔,利用它来选择每个数值型属性的某些取值而不是全部取值来计算其基尼指数,这样计算量会大大降低。但是在间隔如何选择的问题上人为的要素比较多。2、抽样方法 Khaled Alsabti等人提出了一种新的决策树分类器CLOUDS,提供了两种确定数值型属性最优分裂点的新方法SS和SSE.其中SS采用分位技术将每一个数值型属性的取值范围分为假设干个区间(每一个区间包含

8、的数据点根本相等),计算每个区间两个端点的基尼指数并将基尼指数最小的点作为最优分裂点进展下一步的分枝。SSE是SS的改良算法,它利用求出最小基尼指数并估计出每一个区间上基尼指数的下限。假设区间的基尼指数下限小于最小基尼指数,那么将区间保管;否那么删除,然后对于那些被保管区间中的每一个点,计算其基尼指数,取基尼指数最小的点为最优分裂点。SSE的精度要高于SS,但是计算量也大。CLOUDS经过一个估计步 对数值型属性的一切取值进展抽样,由此可以减少寻觅最优分裂点的搜索空间。与传统的决策树算法相比,明显地降低了运算的复杂度而且产生的决策树在精度和规模上也坚持了较高的质量。3.重新构造数据 前面提到的

9、数据概化、归约和抽样方法都可以简化数据集,提高决策树算法的效率。然而这样也能够漏掉数据中有价值的信息。所以有必要研讨可以直接对大型数据集进展处置而运转时间不会太长的决策树算法。Manish Mehta等人提出的SLIQ和Shafer J.C.等人提出的SPRINT是能对大型数据集进展处置的决策树算法,它们都能处置延续值属性和离散值属性。这两种算法都运用了预排序技术,并对原始数据集的构造进展了重新构造。3.重新构造数据 SLIQ运用假设干驻留磁盘的属性表和单个驻留内存的类表。每一个属性具有一个属性表,由记录标志符(RID)建立索引。每个元组由属性表中链接到类表的一个表目链接表示,而类表的表目那么

10、链接到它在决策树中对应的叶节点。SLIQ的特点是将类表驻留在主存,在决策树的学习过程中经常访问它,因此算法的效率会提高。SLIQ运用基尼指数作为选择测试属性的规范,选择基尼指数最小的属性作为最优分裂点,详细到每个节点的分割又包括矩形类图 的更新和类表的更新。SLIQ采用了MDL的方法来修剪树。这一算法的缺陷是类表的大小随训练集中样本数目增长,当类表太大而不能放在主存时,它的性能会随着下降。3.重新构造数据 SPRINT运用不同的属性表数据构造存放类和RID信息。当节点分裂时,属性表被相应划分，并在子节点中分布。在对表进展划分时，维持表中记录的次序不变。因此，划分表时不需求重新排序。当SLIQ和

11、SPRINT处置的数据量太大,不能一次装入内存时,SLIQ的可伸缩性受限于它所运用的常驻内存的数据构造。而SPRINT不受内存限制,但仍需求运用与训练集大小成比例的散列树。当训练集非常大时,SPRINT的效率有待考验。SPRINT易于并行化,曾经有一些算法对SPRINT进展改良,并实现了并行,这就进一步加强了可伸缩性。决策树分类算法的开展前景目前决策树技术的主要研讨方向有以下几点:1、决策树算法的并行性研讨2、寻觅新的构造决策树的方法3、寻觅更好的简化决策树的方法4.研讨产生决策树的训练和检验数据的大小及特性与决策树特性之间的关系5.不确定环境下决策树研讨6.将决策树用于多智能体控制并不多见7

12、.决策树时间复杂度与准确性之间的矛盾8.决策树技术的软件实现1、决策树算法的并行性研讨Chan和Stolfo提出，可以将样本划分成子集或者从原始数据集中抽取假设干子集，使得每个子集可以放在内存中；然后由每个子集构造一棵决策树；最后，输出的分类法将由每个子集得到的分类法组合在一同。虽然该方法可以用于大数据集的分类，但其分类的准确性不如一次运用一切数据的方法高。除了以上方法之外，还可以在构造决策树的过程中运用并行机制。一种思绪是：在每个节点上选择测试属性，即最优分裂属性时，各个属性之间是相互独立的，它们的信息增益或者基尼指数的计算可以在不同的处置器上并行进展。另一种思绪是：在决策树中同一层的节点、

13、或者不同层的没有父子关系的节点，当它们进展属性选择或者子集分割时，两两之间也互不冲突，因此可以进展并行运算。综上所述，在并行机制中，一切的处置器可以同时处置决策树的某一个节点，也可以将处置器分成假设干组，不同的组分别处置决策树的不同部分。2、寻觅新的构造决策树的方法 自从Quinlan提出ID3和C4.5方法后,有不少专家提出了其他构造决策树的方法,如由Brieman等人提出的CART方法和由Kass提出的CHAID方法。最近.Ankerst等提出了基于多维可视化下的交互式的决策树构造。此方法在决策树构造阶段参与了专家知识，这样便于用户更深地了解产生决策树的数据及最终产生的决策树。同时此方法也

14、显著地减小了决策树的大小。在M.Ankerst等提出的方法中，他们主要用两类进化算法替代了传统的贪婪搜索算法以实现数值属性的恣意分割。3、寻觅更好的简化决策树的方法 简化决策树的研讨任务主要有两个方面，一是对比各种不同的简化决策树方法，分析它们各自的特性、优点和缺陷。另外一个就是寻觅更好的与传统方法不同的简化决策树的方法，这不断是决策树技术研讨的一个热点。近年来，针对不同的运用领域并且随着其他新技术的参与，陆续有这方面的文章发表。例如D.Founrnier等提出的一种新的修剪决策树的方法，DI修剪法。此方法针对数据不确定的情况,利用特性索引来权衡处置决策树深度和节点杂质。DI修剪法将坚持那些虽

15、不能减小错误率但能指出一些特殊性质的群体的子树。D.Founrnier等以为这对于研讨不确定数据是非常关键的。4.研讨产生决策树的训练和检验数据的大小及特性与决策树特性之间的关系 与上述简化决策树不同,这类研讨着眼于产生决策树的数据。训练数据的添加经常呵斥决策树大小的线性添加,而这种添加并没有都带来决策树准确性的提高。一些专家以为,在产生决策树前尽量减少数据量比在决策树产生后再简化决策树更加有效。实践上,这就是经常提起的数据预处置技术,与决策树修剪技术相对应,也称它为数据减少技术。近几年有关这方面的研讨获得了一些进展。5.不确定环境下决策树研讨 不确定环境下的决策研讨不断是一个热点,决策树技术

16、就是其中一个重要的方法之一。前面引见的决策树技术与模糊集合原理的结合就是一个不错的选择。此外Z.Eloudi等人提出了一种基于置信度函数的决策树。此算法利用置信度函数原理来代表分类问题中的参数不确定性，在不确定环境下决策树构造和不确定环境下的分类均获得了比较好的效果。目前正在进展决策树与专家系统相结合的研讨，以便在不确定环境下更好地决策。6.将决策树用于多智能体控制并不多见 但正由于多智能体系统的复杂性，而机器学习有潜力提供一个鲁棒性较强的机制来有效协调各智能体间的行为，因此对多智能体结合机器学习是一个很有出路的方向。P.Stone和M.Veloso提出了基于决策树C4.5算法中置信度下的多智

17、能体控制并将此运用于机器人足球控制。7.决策树时间复杂度与准确性之间的矛盾 决策树与神经网络相比所具有的最大优点就是训练决策树的时间远远低于训练神经网络的时间。决策树如何处置时间复杂度和分类准确性之间的矛盾是一个令人感兴趣的问题。究竟如何取舍需求详细问题详细分析。例如,O.Taner等人提出的全变量决策树 在分类正确性方面超越了其他决策树方法却付出了需求更多训练时间的代价。随着微处置器速度越来越快、价钱越来越廉价，以及并行计算的运用，使人们在做决议时拥有比以前更大的自在。8.决策树技术的软件实现 将决策树技术软件化不断是决策树技术的方向之一。目前市场上的许多数据发掘的商用软件，如SAS,SPSS,CART,IBM Intelligent Miner等产品也将决策树方法嵌入到它们的产品当中,并且得到了广泛的运用。如何开发出功能更加强大、运用更加方便、界面更加友好的软件以实现决策树技术,不断是大家努力的方向。谢谢！