ID三、C4.五、CART三种决策树的区别

很早就想写写决策树，提及决策树作过数据挖掘的就不会感受陌生，可是可能对ID3决策树算法、C4.5决策树算法以及CART决策树之间的区别不太了解，下面就这三个比较著名的决策树算法分别写写算法

决策树是如何工做的学习

一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其余每一个结点则对应一个属性测试；每一个结点包含的样本结合根据属性测试的结果被划分到子结点中；根结点包含样本全集，从根结点到每一个叶结点的每一个叶结点的路径对应一个断定测试序列。决策树学习的目的是为了产生一棵泛化能力强，也就是可以处理未见实例的决策树。测试

ID3决策树

信息熵是度量样本集合纯度最经常使用的一种指标。假设样本集合D中第k类样本所占的比重为pk，那么信息熵的计算则为下面的计算方式
blog

当这个Ent(D)的值越小，说明样本集合D的纯度就越高数据挖掘

有了信息熵，当我选择用样本的某一个属性a来划分样本集合D时，就能够得出用属性a对样本D进行划分所带来的“信息增益”io

通常来说，信息增益越大，说明若是用属性a来划分样本集合D，那么纯度会提高，由于咱们分别对样本的全部属性计算增益状况，选择最大的来做为决策树的一个结点，或者能够说那些信息增益大的属性每每离根结点越近，由于咱们会优先用能区分度大的也就是信息增益大的属性来进行划分。当一个属性已经做为划分的依据，在下面就不在参与竞选了，咱们刚才说过根结点表明所有样本，而通过根结点下面属性各个取值后样本又能够按照相应属性值进行划分，而且在当前的样本下利用剩下的属性再次计算信息增益来进一步选择划分的结点，ID3决策树就是这样创建起来的。im

C4.5决策树

C4.5决策树的提出彻底是为了解决ID3决策树的一个缺点，当一个属性的可取值数目较多时，那么可能在这个属性对应的可取值下的样本只有一个或者是不多个，那么这个时候它的信息增益是很是高的，这个时候纯度很高，ID3决策树会认为这个属性很适合划分，可是较多取值的属性来进行划分带来的问题是它的泛化能力比较弱，不可以对新样本进行有效的预测。d3

而C4.5决策树则不直接使用信息增益来做为划分样本的主要依据，而提出了另一个概念，增益率数据

可是一样的这个增益率对可取值数目较少的属性有所偏好，所以C4.5决策树先从候选划分属性中找出信息增益高于平均水平的属性，在从中选择增益率最高的。img

CART决策树

CART决策树的全称为Classification and Regression Tree,能够应用于分类和回归。

采用基尼系数来划分属性

基尼值

基尼系数

所以在候选属性中选择基尼系数最小的属性做为最优划分属性。