数据挖掘十大经典算法之 C4.5

一、引入——决策树（分类部分）

决策树是一种基本的分类与回归方法，这一节主要围绕分类来展开。

决策树是一种机器学习的方法，它是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。

决策树是有监督的学习，监管学习就是给出一堆样本，每个样本都有一组属性和一个分类结果，也就是分类结果已知，那么通过学习这些样本得到一个决策树，这个决策树能够对新的数据给出正确的分类。

决策树算法作为一种分类算法，目标就是将具有p维特征的n个样本分到c个类别中去。相当于做一个投影，c=f(n)，将样本经过一种变换赋予一种类别标签。决策树为了达到这一目的，可以把分类的过程表示成一棵树，每次通过选择一个特征pi来进行分叉。

决策树的几大步骤，即：1特征的选择 2决策树的生成 3 决策树的剪枝

1、机器学习中，决策树是一个预测模型；它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。

2、从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。

3、决策树学习也是数据挖掘中一个普通的方法。在这里，每个决策树都表述了一种树型结构，他由他的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。当不能再进行分割或一个单独的类可以被应用于某一分支时，递归过程就完成了。另外，随机森林分类器将许多决策树结合起来以提升分类的正确率。

决策树是如何工作的？

1、决策树一般都是自上而下的来生成的。

2、选择分割的方法有好几种，但是目的都是一致的：对目标类尝试进行最佳的分割。

3、从根到叶子节点都有一条路径，这条路径就是一条―规则

4、决策树可以是二叉的，也可以是多叉的。

对每个节点的衡量：

1) 通过该节点的记录数

2) 如果是叶子节点的话，分类的路径

3) 对叶子节点正确分类的比例。

决策树的生成

主要分以下两步，这两步通常通过学习已经知道分类结果的样本来实现。

1. 节点的分裂：一般当一个节点所代表的属性无法给出判断时，则选择将这一节点分成2个

子节点（如不是二叉树的情况会分成n个子节点）

2. 阈值的确定：选择适当的阈值使得分类错误率最小（Training Error）。

决策树的损失函数（具体看下面剪枝的介绍）：

决策树的优缺点

优点：

一是得到的模型很容易可视化，非专家也很容易理解(至少对于较小的树而言)。

二是算法完全不受数据缩放的影响。由于每个特征被单独处理，而且数据的划分也不依赖于缩放，因此决策树算法不需要特征预处理，比如归一化或标准化。特别是特征的尺度完全不一样时或者二元特征和连续特征同时存在时，决策树的效果很好。

缺点：

即使做了预剪枝，它也经常会过拟合，泛化性能很差。因此，在大多数应用中，往往使用集成方法来替代单棵决策树。

过拟合：通俗的理解就是生成的决策树（模型）对训练数据集的依赖性很高，当这样一个完全针对某一训练集而生成的模型面对训练数据时的准确度是完全可以达到100%的，但是如果面对其他测试集可能错误率也会很高。

预剪枝能更好的让模型的泛化能力更强。预剪枝的限制条件可能包括限制树的最大深度、限制叶结点的最大数目，或者规定一个结点中数据点的最小数目来防止继续划分等，这些在DecisionTreeClassifier的参数中就可以选择。

决策树的剪枝

决策树的剪枝往往通过极小化决策树整体的损失函数或者代价函数实现，假设树的叶结点个数为|T|，t是树的一个叶结点，其上有Nt个样本，其中k类的样本有Ntk个，k=1,2,3...K，Ht(T)为叶结点上的经验熵， $\alpha$ 参数大于0,那么决策树损失函数可以定义为：

这里面C(T)指的是模型对训练数据的预测误差，而|T|表示的就是模型的叶结点个数，代表了模型的复杂度， $\alpha$ 起到了控制平衡两者之间的作用的一个角色， $\alpha$ =0意味着只考虑对训练数据的预测误差而不考虑结点个数，自然会有过拟合的现象产生。

所谓的剪枝，就是当 $\alpha$ 确定的时候，选择损失函数最小的模型。 $\alpha$ 确定时候，子树越大，训练数据拟合程度越好，但是泛化能力就越差，相反的，子树越小，模型的复杂度就越小，对训练数据的拟合程度越差，但是泛化能力相对较好，损失函数同时考虑二者的影响，达到一个平衡的最优！

本质上 这样的损失函数最小化原则就是等价与正则化的极大似然估计，利用损失函数最小化原则进行剪枝，就是利用正则化的极大似然估计进行模型的筛选！

二、C4.5介绍

决策树的生成算法有ID3, C4.5、C5.0和CART（Classification And Regression Tree、分类回归树）等（CART的分类效果一般优于其他决策树，CART下一节再介绍）。不同的决策树算法有着不同的特征选择方案。ID3用信息增益，C4.5用信息增益率，CART用gini系数。C4.5是ID3的一个改进算法。

1. 引入——熵

熵:是表示随机变量不确定性的度量，熵的取值越大，随机变量的不确定性也越大。

设X是一个取有限个值的离散随机变量，其概率分布为

P(X=xi)=pi, i=1,2,⋯,n

熵计算公式:H(X)=- ∑ pi * logpi,i=1,2, ... , n

2. ID3

ID3算法的核心是在决策树各个子节点上应用信息增益准则选择特征，递归的构建决策树。（【信息增益:表示特征X使得类Y的不确定性减少的程度。(分类后的专一性，希望分类后的结果是同类在一起) 】）

具体方法是：从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点；再对子节点递归调用以上方法，构建决策树。直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一个决策树。

ID3过程：

根据信息增益(Informationgain)来选取Feature作为决策树分裂的节点.特征A对训练数据集D的信息增益定义为集合D的经验熵(所谓经验熵,指的是熵是由某个数据集合估计得到的)H(D)与特征A给定条件下D的经验条件熵 H(D∣A) 之差,记为g(D,A)。

g(D,A)=H(D)−H(D|A) 实际上就是特征A和D的互信息

实例论证见：https://blog.csdn.net/Andy_shenzl/article/details/83899431?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-1#C4.5%E7%AE%97%E6%B3%95%E4%BC%98%E7%BC%BA%E7%82%B9%E5%88%86%E6%9E%90

https://blog.csdn.net/fuqiuai/article/details/79456971?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase

理论计算过程：

ID3缺点：

ID3采用的信息增益度量存在一个内在偏置,它优先选择有较多属性值的Feature,因为属性值多的Feature会有相对较大的信息增益。

越细小的分割分类错误率越小，所以ID3会越分越细，比如以第一个属性为例：设阈值小于70可将样本分为2组，但是分错了1个。如果设阈值小于70，再加上阈值等于95，那么分错率降到了0，但是这种分割显然只对训练数据有用，对于新的数据没有意义，这就是所说的过度学习（Overfitting）。

分割太细了，训练数据的分类可以达到0错误率，但是因为新的数据和训练数据不同，所以面对新的数据分错率反倒上升了。决策树是通过分析训练数据，得到数据的统计信息，而不是专为训练数据量身定做。

(信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大)。

3. C4.5算法

为了克服ID3的缺点，引进C4.5算法。

避免ID3不足的一个度量就是不用信息增益来选择Feature,而是用信息增益比率(gainratio),增益比率通过引入一个被称作分裂信息(Splitinformation)的项来惩罚取值较多的Feature,分裂信息用来衡量Feature分裂数据的广度和均匀性:

但是当某个Di的大小跟D的大小接近的时候,SplitInformation(D,A)→0,GainRatio(D,A)→∞,为了避免这样的属性,可以采用启发式的思路,只对那些信息增益比较高的属性才应用信息增益比率。

C4.5算法主要有以下四个步骤：

Entropy(S)：计算熵；

Gain(S,A):计算信息增益；

SplitInformation(S,A):计算分裂信息度量；

GainRatio(S,A):计算信息增益率。

根据计算得到的信息增益率进行选择属性集中的属性作为决策树结点，对该结点进行分裂。

相比ID3,C4.5还能处理连续属性值,具体步骤为:

• 把需要处理的样本(对应根节点)或样本子集(对应子树)按照连续变量的大小从小到大进行排序。

• 假设该属性对应的不同的属性值一共有N个,那么总共有N−1个可能的候选分割阈值点,每个候选的分割阈值点的值为上述排序后的属性值中两两前后连续元素的中点,根据这个分割点把原来连续的属性分成bool属性.实际上可以不用检查所有N−1个分割点（https://blog.csdn.net/amour_yue/article/details/71325261）。

• 用信息增益比率选择最佳划分。

C4.5算法的优缺点：

优点：

（1）通过信息增益率选择分裂属性，克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足；

（2）能够处理离散型和连续型的属性类型，即将连续型的属性进行离散化处理；

（3）构造决策树之后进行剪枝操作；

（4）能够处理具有缺失属性值的训练数据；

(5) 产生的分类规则易于理解，准确率较高。

缺点：

（1）在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的计算效率较低，特别是针对含有连续属性值的训练样本时表现的尤为突出。

（2）算法在选择分裂属性时没有考虑到条件属性间的相关性，只计算数据集中每一个条件属性与决策属性之间的期望信息，有可能影响到属性选择的正确性。

参考：