第三章 决策树分类算法的应用进展和发展前景.pptVIP

2003.11.18 机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏 机器学习 第3章 决策树学习 决策树分类算法的进展 决策树分类算法的发展前景 主要决策树算法 最早的决策树算法是由Hunt等人于1966年提出的CLS 。当前最有影响的决策树算法是Quinlan于1986年提出的ID3和1993年提出的C4.5。 其它早期算法主CART、FACT、CHAID算法 。后期的算法主要有SLIQ、SPRINT 、PUBLIC等。 决策树分类算法的进展 传统的决策树分类算法主要是针对小数据集的，大都要求训练集常驻内存，这使得在处理数据挖掘任务时，传统决策树算法在可伸缩性、精度和效率方面受到了很大的限制。而在实际的数据挖掘应用中我们面临的数据集往往是容量巨大的数据库或者数据仓库，在构造决策树时需要将庞大的数据在主存和缓存中不停的导入导出使得运算效率大大降低。针对以上问题许多学者提出了处理大型数据集的决策树算法。下面我们分三个方面对一些算法的改进进行讨论。 1、数据预处理 数据挖掘处理的是海量数据集不仅样本容量大、含有的属性集大而且数据中往往含有一些与挖掘任务不相关和无意义的部分。在这样的数据集上进行分析会花费很长时间使得挖掘任务不可行。此外决策者有时需要在数据的多个抽象层上进行分析以获得有价值的信息。在这种情况下我们需要先用过滤、概化和归约等方法对数据进行预处理然后再对预处理后的数据集进行挖掘。 1、数据预处理 数据概化是指将数据集从较低的概念层抽象到较高的概念层。面向属性的归纳（AOI）是一种有用的概化方法它考查数据集中每个属性的不同取值，通过属性删除或者属性概化等操作在给定的概念分层上概化数据库，由此抽取有意义的知识。使用AOI方法可能出现的问题是:如果属性概化得太高可能导致过分概化,产生的规则可能没有多少信息;而如果属性概化不到足够高的层次,则可能概化不足,得到的规则可能也不含多少信息。因此面向属性的概化应当把握好尺度。 1、数据预处理 针对这个问题 ,有专家提出了一种新的基于信息增益比的数据概化方法ITA。其基本思想是给定一组候选的提取分层,ITA选择一个最优的提取并对原始数据库进行概化。其操作步骤可以概括为从原始数据库中选定某一属性,计算属性的信息增益比,假设其值为I1;对于候选提取分层中的每一种提取,计算其针对选定属性的信息增益比,选择信息增益比最大的提取,假设该提取的信息增益比为I2;计算I2/I1， 若商大于给定阈值,则对属性值进行概化,否则删除该属性。 ITA较好地保留了原始数据库中的类分布,数据库的尺寸也大大减小。这使得产生的决策树更加紧凑,大大减小了树的尺寸,而且精度也没有明显地降低。此外它适当地控制了面向属性归纳中的概化过程,自动选择对数据库的最优概化,弥补了AOI的缺陷。之后,又进一步提出了迭代ITA的思想,并将其应用于C4.5的每一次属性选择的迭代过程,更好地保留了原始数据库中的类分布。 1、数据预处理 在实际应用中数据集往往含有很多的属性，而有一些属性是多余的。直接利用这种数据集来产生决策树会增加存储和计算方面的负担。在这种情况下，对数据集进行压缩或者精简是必要的。利用粗糙集理论中的不可分辨关系将数据集进行属性归约和数据过滤，去除与决策无关的多余信息也是当前比较热门的研究。将利用粗糙集简化后的数据集作为输入产生的决策树会更加紧凑。 2、抽样方法 在进行数据挖掘的分类任务时利用抽样方法也可以提高决策树的效率，特别是当我们对算法的效率要求很高时。在构建决策树时可以对数据集进行抽样，也可以在产生节点的过程中对节点进行抽样。对数据集进行抽样是指利用统计抽样方法抽取整个数据集的一个子集，用该子集产生一棵决策树对未知样本进行分类或者从中抽取分类规则。这种做法的缺点在于，通过子集产生的决策树只能捕捉到整个数据集的大体的信息，有可能漏掉数据集中有价值的模式。因此这种做法是以牺牲精确度为代价来提高运算效率的。另一种抽样方法节点抽样是决策树方法中特有的我们主要对其进行介绍。 2、抽样方法 树构造阶段在内部节点（属性）进行属性选择时，如果面对的是连续值属性，我们一般按如下方法选择最优分裂点（split）：设A为连续值属性,最多可能有n个属性值。先对数据集按照属性A从小到大进行排序排序后的结果为a1，a2，… 。按照排序后的顺序依次取分裂点，计算其属性选择度量值，如信息增益、基尼指数等，从而得到最优划分。若ai属性选择度量值最优，通常取split=（a（i）+a（i+1））/2。对于连续值属性,为了在内部节点选择最优分裂点需要对每个属性的每个取值计算其相应的基尼指数。。当训练样本非常大时,计算量也会很大。针对这一问题,B.Chandra等人指出，可以选择一个合适的间隔,利用它来选择每