《决策树分类算法的应用、进展和发展前景.ppt》由会员分享，可在线阅读，更多相关《决策树分类算法的应用、进展和发展前景.ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、机器学习 第3章 决策树学习决策树分类算法的进展决策树分类算法的发展前景2003.11.181机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏 主要决策树算法最早的决策树算法是由Hunt等人于1966年提出的CLS。当前最有影响的决策树算法是Quinlan于1986年提出的ID3和1993年提出的C4.5。其它早期算法主CART、FACT、CHAID算法。后期的算法主要有SLIQ、SPRINT、PUBLIC等。2003.11.182机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏决策树分类算法的进展传统的决策树分类算法主要是针对小数据集的，大
2、都要求训练集常驻内存，这使得在处理数据挖掘任务时，传统决策树算法在可伸缩性、精度和效率方面受到了很大的限制。而在实际的数据挖掘应用中我们面临的数据集往往是容量巨大的数据库或者数据仓库，在构造决策树时需要将庞大的数据在主存和缓存中不停的导入导出使得运算效率大大降低。针对以上问题许多学者提出了处理大型数据集的决策树算法。下面我们分三个方面对一些算法的改进进行讨论。2003.11.183机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏1、数据预处理数据挖掘处理的是海量数据集不仅样本容量大、含有的属性集大而且数据中往往含有一些与挖掘任务不相关和无意义的部分。在这样的数据集上进
3、行分析会花费很长时间使得挖掘任务不可行。此外决策者有时需要在数据的多个抽象层上进行分析以获得有价值的信息。在这种情况下我们需要先用过滤、概化和归约等方法对数据进行预处理然后再对预处理后的数据集进行挖掘。2003.11.184机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏1、数据预处理数据概化是指将数据集从较低的概念层抽象到较高的概念层。面向属性的归纳（AOI）是一种有用的概化方法它考查数据集中每个属性的不同取值，通过属性删除或者属性概化等操作在给定的概念分层上概化数据库，由此抽取有意义的知识。使用AOI方法可能出现的问题是:如果属性概化得太高可能导致过分概化,产生的
4、规则可能没有多少信息;而如果属性概化不到足够高的层次,则可能概化不足,得到的规则可能也不含多少信息。因此面向属性的概化应当把握好尺度。2003.11.185机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏1、数据预处理针对这个问题,有专家提出了一种新的基于信息增益比的数据概化方法ITA。其基本思想是给定一组候选的提取分层,ITA选择一个最优的提取并对原始数据库进行概化。其操作步骤可以概括为从原始数据库中选定某一属性,计算属性的信息增益比,假设其值为I1;对于候选提取分层中的每一种提取,计算其针对选定属性的信息增益比,选择信息增益比最大的提取,假设该提取的信息增益比为I
5、2;计算I2/I1，若商大于给定阈值,则对属性值进行概化,否则删除该属性。ITA较好地保留了原始数据库中的类分布,数据库的尺寸也大大减小。这使得产生的决策树更加紧凑,大大减小了树的尺寸,而且精度也没有明显地降低。此外它适当地控制了面向属性归纳中的概化过程,自动选择对数据库的最优概化,弥补了AOI的缺陷。之后,又进一步提出了迭代ITA的思想,并将其应用于C4.5的每一次属性选择的迭代过程,更好地保留了原始数据库中的类分布。2003.11.186机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏1、数据预处理在实际应用中数据集往往含有很多的属性，而有一些属性是多余的。直接利
6、用这种数据集来产生决策树会增加存储和计算方面的负担。在这种情况下，对数据集进行压缩或者精简是必要的。利用粗糙集理论中的不可分辨关系将数据集进行属性归约和数据过滤，去除与决策无关的多余信息也是当前比较热门的研究。将利用粗糙集简化后的数据集作为输入产生的决策树会更加紧凑。2003.11.187机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏2、抽样方法在进行数据挖掘的分类任务时利用抽样方法也可以提高决策树的效率，特别是当我们对算法的效率要求很高时。在构建决策树时可以对数据集进行抽样，也可以在产生节点的过程中对节点进行抽样。对数据集进行抽样是指利用统计抽样方法抽取整个数据集
7、的一个子集，用该子集产生一棵决策树对未知样本进行分类或者从中抽取分类规则。这种做法的缺点在于，通过子集产生的决策树只能捕捉到整个数据集的大体的信息，有可能漏掉数据集中有价值的模式。因此这种做法是以牺牲精确度为代价来提高运算效率的。另一种抽样方法节点抽样是决策树方法中特有的我们主要对其进行介绍。2003.11.188机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏2、抽样方法树构造阶段在内部节点（属性）进行属性选择时，如果面对的是连续值属性，我们一般按如下方法选择最优分裂点（split）：设A为连续值属性,最多可能有n个属性值。先对数据集按照属性A从小到大进行排序排序后
8、的结果为a1，a2，。按照排序后的顺序依次取分裂点，计算其属性选择度量值，如信息增益、基尼指数等，从而得到最优划分。若ai属性选择度量值最优，通常取split=（a（i）+a（i+1）/2。对于连续值属性,为了在内部节点选择最优分裂点需要对每个属性的每个取值计算其相应的基尼指数。当训练样本非常大时,计算量也会很大。针对这一问题,B.Chandra等人指出，可以选择一个合适的间隔,利用它来选择每个数值型属性的某些取值而不是全部取值来计算其基尼指数,这样计算量会大大降低。但是在间隔如何选择的问题上人为的因素比较多。2003.11.189机器学习-决策树学习 译者：曾华军等 作者：Mitchell
9、讲者：陶晓鹏2、抽样方法 Khaled Alsabti等人提出了一种新的决策树分类器CLOUDS,提供了两种确定数值型属性最优分裂点的新方法SS和SSE.其中SS采用分位技术将每一个数值型属性的取值范围分为若干个区间(每一个区间包含的数据点基本相等),计算每个区间两个端点的基尼指数并将基尼指数最小的点作为最优分裂点进行下一步的分枝。SSE是SS的改进算法,它利用求出最小基尼指数并估计出每一个区间上基尼指数的下限。若区间的基尼指数下限小于最小基尼指数,则将区间保留;否则删除,然后对于那些被保留区间中的每一个点,计算其基尼指数,取基尼指数最小的点为最优分裂点。SSE的精度要高于SS,但是计算量也大
10、。CLOUDS通过一个估计步 对数值型属性的所有取值进行抽样,由此可以缩小寻找最优分裂点的搜索空间。与传统的决策树算法相比,明显地降低了运算的复杂度而且产生的决策树在精度和规模上也保持了较高的质量。2003.11.1810机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏3.重新构造数据前面提到的数据概化、归约和抽样方法都可以简化数据集,提高决策树算法的效率。然而这样也可能漏掉数据中有价值的信息。所以有必要研究能够直接对大型数据集进行处理而运行时间不会太长的决策树算法。Manish Mehta等人提出的SLIQ和Shafer J.C.等人提出的SPRINT是能对大型数据
11、集进行处理的决策树算法,它们都能处理连续值属性和离散值属性。这两种算法都使用了预排序技术,并对原始数据集的结构进行了重新构造。2003.11.1811机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏3.重新构造数据SLIQ使用若干驻留磁盘的属性表和单个驻留内存的类表。每一个属性具有一个属性表,由记录标志符(RID)建立索引。每个元组由属性表中链接到类表的一个表目链接表示,而类表的表目则链接到它在决策树中对应的叶节点。SLIQ的特点是将类表驻留在主存,在决策树的学习过程中经常访问它,因此算法的效率会提高。SLIQ使用基尼指数作为选择测试属性的标准,选择基尼指数最小的属性
12、作为最优分裂点,具体到每个节点的分割又包括矩形类图 的更新和类表的更新。SLIQ采用了MDL的方法来修剪树。这一算法的缺点是类表的大小随训练集中样本数目增长,当类表太大而不能放在主存时,它的性能会随着下降。2003.11.1812机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏3.重新构造数据SPRINT使用不同的属性表数据结构存放类和RID信息。当节点分裂时,属性表被相应划分，并在子节点中分布。在对表进行划分时，维持表中记录的次序不变。因此，划分表时不需要重新排序。当SLIQ和SPRINT处理的数据量太大,不能一次装入内存时,SLIQ 的可伸缩性受限于它所使用的常驻
13、内存的数据结构。而SPRINT不受内存限制,但仍需要使用与训练集大小成比例的散列树。当训练集非常大时,SPRINT的效率有待考验。SPRINT易于并行化,已经有一些算法对SPRINT进行改进,并实现了并行,这就进一步增强了可伸缩性。2003.11.1813机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏决策树分类算法的发展前景目前决策树技术的主要研究方向有以下几点:1、决策树算法的并行性研究2、寻找新的构造决策树的方法3、寻找更好的简化决策树的方法4.研究产生决策树的训练和检验数据的大小及特性与决策树特性之间的关系5.不确定环境下决策树研究6.将决策树用于多智能体控制
14、并不多见7.决策树时间复杂度与准确性之间的矛盾8.决策树技术的软件实现2003.11.1814机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏1、决策树算法的并行性研究Chan和Stolfo提出，可以将样本划分成子集或者从原始数据集中抽取若干子集，使得每个子集可以放在内存中；然后由每个子集构造一棵决策树；最后，输出的分类法将由每个子集得到的分类法组合在一起。尽管该方法可以用于大数据集的分类，但其分类的准确性不如一次使用所有数据的方法高。除了以上方法之外，还可以在构造决策树的过程中使用并行机制。一种思路是：在每个节点上选择测试属性，即最优分裂属性时，各个属性之间是相互独
15、立的，它们的信息增益或者基尼指数的计算可以在不同的处理器上并行进行。另一种思路是：在决策树中同一层的节点、或者不同层的没有父子关系的节点，当它们进行属性选择或者子集分割时，两两之间也互不冲突，因此可以进行并行运算。综上所述，在并行机制中，所有的处理器可以同时处理决策树的某一个节点，也可以将处理器分成若干组，不同的组分别处理决策树的不同部分。2003.11.1815机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏2、寻找新的构造决策树的方法自从Quinlan提出ID3和C4.5方法后,有不少专家提出了其他构造决策树的方法,如由Brieman等人提出的CART方法和由Ka
16、ss提出的CHAID方法。最近.Ankerst等提出了基于多维可视化下的交互式的决策树构造。此方法在决策树构造阶段加入了专家知识，这样便于用户更深地理解产生决策树的数据及最终产生的决策树。同时此方法也显著地减小了决策树的大小。在M.Ankerst等提出的方法中，他们主要用两类进化算法替代了传统的贪婪搜索算法以实现数值属性的任意分割。2003.11.1816机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏3、寻找更好的简化决策树的方法简化决策树的研究工作主要有两个方面，一是对比各种不同的简化决策树方法，分析它们各自的特性、优点和缺点。另外一个就是寻找更好的与传统方法不同
17、的简化决策树的方法，这一直是决策树技术研究的一个热点。近年来，针对不同的应用领域并且随着其他新技术的加入，陆续有这方面的文章发表。例如D.Founrnier等提出的一种新的修剪决策树的方法，DI修剪法。此方法针对数据不确定的情况,利用特性索引来权衡处理决策树深度和节点杂质。DI修剪法将保持那些虽不能减小错误率但能指出一些特殊性质的群体的子树。D.Founrnier等认为这对于研究不确定数据是非常关键的。2003.11.1817机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏4.研究产生决策树的训练和检验数据的大小及特性与决策树特性之间的关系与上述简化决策树不同,这类研
18、究着眼于产生决策树的数据。训练数据的增加经常造成决策树大小的线性增加,而这种增加并没有都带来决策树准确性的提高。一些专家认为,在产生决策树前尽量减少数据量比在决策树产生后再简化决策树更加有效。实际上,这就是经常提起的数据预处理技术,与决策树修剪技术相对应,也称它为数据减少技术。近几年有关这方面的研究取得了一些进展。2003.11.1818机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏5.不确定环境下决策树研究不确定环境下的决策研究一直是一个热点,决策树技术就是其中一个重要的方法之一。前面介绍的决策树技术与模糊集合原理的结合就是一个不错的选择。此外Z.Eloudi等人
19、提出了一种基于置信度函数的决策树。此算法利用置信度函数原理来代表分类问题中的参数不确定性，在不确定环境下决策树构造和不确定环境下的分类均取得了比较好的效果。目前正在进行决策树与专家系统相结合的研究，以便在不确定环境下更好地决策。2003.11.1819机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏6.将决策树用于多智能体控制并不多见但正由于多智能体系统的复杂性，而机器学习有潜力提供一个鲁棒性较强的机制来有效协调各智能体间的行为，因此对多智能体结合机器学习是一个很有前途的方向。P.Stone和M.Veloso提出了基于决策树C4.5算法中置信度下的多智能体控制并将此应
20、用于机器人足球控制。2003.11.1820机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏7.决策树时间复杂度与准确性之间的矛盾决策树与神经网络相比所具有的最大优点就是训练决策树的时间远远低于训练神经网络的时间。决策树如何处理时间复杂度和分类准确性之间的矛盾是一个令人感兴趣的问题。到底如何取舍需要具体问题具体分析。例如,O.Taner等人提出的全变量决策树 在分类正确性方面超过了其他决策树方法却付出了需要更多训练时间的代价。随着微处理器速度越来越快、价钱越来越便宜，以及并行计算的运用，使人们在做决定时拥有比以前更大的自由。2003.11.1821机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏8.决策树技术的软件实现将决策树技术软件化一直是决策树技术的方向之一。目前市场上的许多数据挖掘的商用软件，如SAS,SPSS,CART,IBM Intelligent Miner等产品也将决策树方法嵌入到它们的产品当中,并且得到了广泛的应用。如何开发出功能更加强大、使用更加方便、界面更加友好的软件以实现决策树技术,一直是大家努力的方向。2003.11.1822机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏谢谢！2003.11.1823机器学习-决策树学习 译者：曾华军等 作者：Mitchell 讲者：陶晓鹏