文档介绍：(对ID3的改进):1)用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足; 2)在树构造过程中进行剪枝; 3)能够完成对连续属性的离散化处理; 4)能够对不完整数据进行处理。:产生的分类规则易于理解,准确率较高。:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。,香农提出了“信息熵”的概念,解决了对系统信息的量化度量问题。香农认为信息的准确信息量可以用下面的信息熵公式计算:一个系统越是有序,信息熵就越低;反之,一个系统越乱,信息熵就越高。所以,信息熵也可以说是系统有序化程度的一个衡量。,(informationGainRatio)的方法选择测试属性,信息增益率等于信息增益对分割信息量的比值。GainRatio(S,F)=Gain(S,F)/SplitInformation(S,F)设样本集S按离散属性F的V个不同的取值划分为,共V个子集定义分割信息量Split(S,F):那么信息增益率为::将连续型的属性变量进行离散化处理,形成决策树的训练集把需要处理的样本(对应根节点)或样本子集(对应子树)按照连续变量的大小从小到大进行排序假设该属性对应的不同的属性值一共有N个,那么总共有N-1个可能的候选分割阈值点,:在某些情况下,可供使用的数据可能缺少某些属性的值。例如(X,y)是样本集S中的一个训练实例,X=(F1_v,F2_v,…Fn_v)。但是其属性Fi的值Fi_v未知。处理策略:处理缺少属性值的一种策略是赋给它结点t所对应的训练实例中该属性的最常见值另外一种更复杂的策略是为Fi的每个可能值赋予一个概率。例如,给定一个布尔属性Fi,如果结点t包含6个已知Fi_v=1和4个Fi_v=0的实例,那么Fi_v=,而Fi_v=。于是,实例x的60%被分配到Fi_v=1的分支,40%被分配到另一个分支。这些片断样例(fractionalexamples)的目的是计算信息增益,另外,如果有第二个缺少值的属性必须被测试,这些样例可以在后继的树分支中被进一步细分。():有监督的算法需要考虑泛化能力,在有限样本的条件下,决策树超过一定规模后,训练错误率减小,但测试错误率会增加。为了避免过拟合,采用剪枝技术。剪枝:控制决策树规模的方法称为剪枝,一种是预剪枝,一种是后剪枝。所谓先剪枝,实际上是控制决策树的生长;后剪枝是指,对完全生成的决策树进行修剪。预剪枝(pre-pruning):1)数据划分法。划分数据成训练样本和测试样本,使用用训练样本进行训练,使用测试样本进行树生长检验。 2)阈值法。当某节点的信息增益小于某阈值时,停止树生长。3)信息增益的统计显著性分析。从已有节点获得的所有信息增益统计其分布,如果继续生长得到的信息增 益与该分布相比不显著,则停止树的生长。优点:简单直接;缺点:对于不回溯的贪婪算法,缺乏后效性考虑,可能导致树提前停止。(post-pruning):减少分类错误修剪法。使用独立的剪枝集估计剪枝前后的分类错误率,基于此进行剪枝。最小代价与复杂性折中的剪枝。对剪枝后的树综合评价错误率和复杂性,决定是否剪枝。最小描述长度准则。最简单的树就是最好的树。对决策树进行编码,通过剪枝得到编码最小的树。规则后剪枝。将训练完的决策树转换成规则,通过删除不会降低估计精度的前件修剪每一条规则。优点:实际应用中有效缺点:数据量大时,计算代价较大。常见的后剪枝方法有:Reduced-ErrorPruning(REP,错误率降低剪枝)、PessimisticErrorPruning(PEP,悲观剪枝)P、代价复杂度)、ID3、。后剪枝操作是一个边修剪边检验的过程,一般规则标准是:在决策树的不断剪枝操作过程中,将原样本集合或新数据集合作为测试数据,检验决策树对测试数据的预测精度,并计算出相应的错误率,如果剪掉某个子树后的决策树对测试数据的预测精度或其他测度不降低,那么剪掉该子树。(PEP,悲观剪枝),它使用训练集生成决策树又用它来进行剪枝,不需要独立的