C5.0决策树之ID3、C4.5、C5.0算法

C5.0决策树之ID3、C4.5、C5.0算法
一、起源
最早的决策树算法起源于CLS（Concept Learning System）系统,即概念学习系统。

它是最早的决策树算法,为今后的许多决策树算法提供了借鉴。

[]
决策树模型，通过对训练样本的学习，建立分类规则；依据分类规则，实现对新样本的分类；属于有指导（监督）式的学习方法，有两类变量：目标变量（输出变量），属性变量（输入变量）。

决策树模型与一般统计分类模型的主要区别：决策树的分类是基于逻辑的，一般统计分类模型是基于非逻辑的。

1、常见决策树
常见的算法有CHAID、CART、Quest和C5.0。

对于每一个决策要求分成的组之间的“差异”最大。

各种决策树算法之间的主要区别就是对这个“差异”衡量方式的区别。

决策树很擅长处理非数值型数据，这与神经网络智能处理数值型数据比较而言，就免去了很多数据预处理工作。

[]
二、原理——如何制定节点[]
1、信息熵（Entropy）
信息量的数学期望，是心愿发出信息前的平均不确定性，也称先验熵。

决策属性的Entropy(熵)：
2、信息增益
例如outlook里面有三个属性sunny、OverCas、Rain，每个属性在决策属性中，sunny有2个yes，3个no。

outlook信息增益：
=0.940286-5/14*0.97095-0-5/14*0.97095=0.24675
以下其他属性同理。

Outlook=0.24675
我们看到Outlook的信息增益是最大的，所以作为决策树的一个根节点。

即：
然后，从Outlook下面出来三个树枝，最左边的Sunny，我们从Outlook是Sunny的实例数据中，找到信息增益最大的那一个，依次类推。

3、分离信息（Split Information）
数据集通过条件属性A的分离信息。

分离信息的计算方法,数学符号表达式为：
数据集通过Outlook这个条件属性的分离信息，Outlook有三个属性值分别为：Sunny,Overcast,Rain，它们各占5,4,5，所以：
4、信息增益率（Information gain ratio）
数学符号表达式
数据集S针对Outlook的信息增益率，
分子和分母这两个值都已经求出来，选择信息增益率最大的那个属性，作为节点。

5、剪枝
剪枝一般分两种方法：先剪枝和后剪枝。

（1）先剪枝
先剪枝方法中通过提前停止树的构造（比如决定在某个节点不再分裂或划分训练元组的子集）而对树剪枝。

先剪枝有很多方法，比如（1）当决策树达到一定的高度就停止决策树的生长；（2）到达此节点的实例具有相同的特征向量，而不必一定属于同一类，也可以停止生长（3）到达此节点的实例个数小于某个阈值的时候也可以停止树的生长，不足之处是不能处理那些数据量比较小的特殊情况（4）计算每次扩展对系统性能的增益，如果小于某个阈值就可以让它停止生长。

先剪枝有个缺点就是视野效果问题，也就是说在相同的标准下，也许当前扩展不能满足要求，但更进一步扩展又能满足要求。

这样会过早停止决策树的生长。

（2）后剪枝
它由完全成长的树剪去子树而形成。

通过删除节点的分枝并用树叶来替换它。

树叶一般用子树中最频繁的类别来标记。

（3）悲观剪枝法
使用训练集生成决策树又用它来进行剪枝，不需要独立的剪枝集。

悲观剪枝法的基本思路是：设训练集生成的决策树是T，用T来分类训练集中的N的元组，设K为到达某个叶子节点的元组个数，其中分类错误地个数为J。

由于树T是由训练集生成的，是适合训练集的，因此J/K不能可信地估计错误率。

三、ID3、C4.5、C5.0对比
四、五种决策算法的比较[]
通过十七个公开数据集，对比FS-DT、Yuan’s、FDT、C4.5、Fuzzy ID3、CART五种决策树方法。

1、准确率比较
CD值，临界差值，在Nemen yi检验和Tukey检验方法两种检验方法用差异时可以用CD值来衡量。

得分越低，表示相应的算法的准确率越高。

Fuzzy ID3比FS-DT表现优秀。

2、叶子节点比较
普遍看来,CART和FS-DT两种算法的叶子节点数目比较少。

比较三种模糊决策树，FS-DT、Yuan’s FDT、Fuzzy ID3，FS-DT算法节点比较少。

3、相似性比较
关于相似性,一种观点认为两种分类器的分类准确率相同,则它们具有较高的相似度；另一方面，即两种分类器讲相同的样本分到了同一类,则相似度较高。

大部分两次实验的相似度能达到以上,但有些实验的相似度只有,如应用于第二类五次实验的相似度。

下面分析具体是哪种原因导致上面的问题。

对于C4.5应用于Iris数据集，第二类的相似度中存在只有50%的相似度问题,对比算法在第二类的相似度,全部
高于90%,这说明分类器的选取没有问题。

问题可能存在于Iris数据集中第二类的数据中,这一类数据集分布不集中,导致了分类难度的增加。

（欢迎加好友，一起学习哟~~）。