ID3决策树的不足 ID3没有剪枝策略,容易过拟合 信息增益准则对可取值数目较多的特征有所偏好,类似“编号”的特征 其信息增益接近于1 只能用于处理离散分布的属性 没有考虑缺失值 21
ID3决策树的不足 ◼ ID3 没有剪枝策略，容易过拟合 ◼ 信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征 其信息增益接近于 1 ◼ 只能用于处理离散分布的属性 ◼ 没有考虑缺失值 21
信息增益率 C4.5算法继承了ID3算法的优点,算法基本过程与ID3算法相似, 但在选择决策树的分枝属性时用信息増益率选择属性,克服了选 择属性时信息增益偏向选择取值种类较多的属性的不足。 属性A信息增益率sn-mto(4的定义为: gain(d gain_ratio(d ∑malg:p(a) 式中为属性A的不同取值的个数,从中可以看出,当v比较大时, 就会降低增益率
信息增益率 ◼ C4.5算法继承了ID3算法的优点，算法基本过程与ID3算法相似， 但在选择决策树的分枝属性时用信息增益率选择属性，克服了选 择属性时信息增益偏向选择取值种类较多的属性的不足。 ◼ 属性A信息增益率 的定义为： 式中v为属性A的不同取值 的个数，从中可以看出，当v比较大时， 就会降低增益率。 22
c45相对于ID3的改进 引入悲观剪枝策略进行后剪枝 引入信息增益率作为划分标准 将连续特征离散化,假设n个样本的连续特征A有m个取值,C4.5将其排序并 取相邻两样本值的平均数共m-1个划分点,分别计算以该划分点作为二元分类点 时的信息增益,并选择信息增益最大的点作为该连续特征的二元离散分类点
C4.5相对于ID3的改进 ◼ 引入悲观剪枝策略进行后剪枝 ◼ 引入信息增益率作为划分标准 ◼ 将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并 取相邻两样本值的平均数共 m-1 个划分点，分别计算以该划分点作为二元分类点 时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点 23
预剪枝和后剪枝 预剪枝 在节点划分前来确定是否继续增长,及早停止增长的主要方法有: 节点内数据样本低于某一阈值 节点划分前准确率比划分后准确率高。 预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间,但会带来欠拟合风险 后剪枝 在已经生成的决策树上进行剪枝,从而得到简化版的剪枝决策树。 C4.5采用的悲观剪枝方法,比较剪枝后与剪枝前相比其错误率是保持或者下降。 C4.5通过训练数据集上的错误分类数量来估算未知样本上的错误率 后剪枝决策树的欠拟合风险很小,泛化性能往往优于预剪枝决策树。但冋时其训练时间会大 的多 24
预剪枝和后剪枝 ◼ 预剪枝 在节点划分前来确定是否继续增长，及早停止增长的主要方法有： 节点内数据样本低于某一阈值； ◼ 节点划分前准确率比划分后准确率高。 ◼ 预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但会带来欠拟合风险。 ◼ 后剪枝 在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。 C4.5 采用的悲观剪枝方法，比较剪枝后与剪枝前相比其错误率是保持或者下降。 ◼ C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。 后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但同时其训练时间会大 的多 24
基尼指数( Gini Index) ■集合T包含n个类别的记录,那么其Gin指数就是 P1类别出现的频率)=1-1P7 如果集合T分成两部分 N, and m2。那么这个分割的Gn就是 gini(T)=gini(T+n2 入ini(T2) 提供最小 ginisplit(对应基尼增益)就被选择作为分割的标准 叫es"10 221 =0 vaa=fa, I a=[期 EE[ eu E
25 基尼指数（Gini Index） ◼ 集合T包含n个类别的记录，那么其Gini指数就是 pj 类别j出现的频率 ◼ 如果集合T分成两部分 N1 and N2 。那么这个分割的Gini就是 ◼ 提供最小Ginisplit （对应基尼增益）就被选择作为分割的标准. = = − n j p j gini T 1 2 ( ) 1 ( ) ( ) ( ) 2 2 1 1 gini T N N gini T N T N ginisplit = +