决策树是简单的，易懂的，易实现的，同样也是强大的。

　　决策树本身是一连串的if-else的组合，其最关键的问题就是对于一个输入数据集我们应该怎么去寻找这个if-else规则。按照先贤们的分法主要有如下几种：ID3,C4.5,CART。本文也将介绍这三种决策树。

　　一、ID3

　　要想弄明白ID3决策树，我们必须先了解信息论的开创者——香农对信息是如何量化的。

　　（1）熵

　　熵（Entropy），一个无法理解的字，香农给了他的定义：表示随机变量不确定的度量。假设X是一个有限的随机变量，其概率分布为：P(X=xi)=pi，则熵的定义为：

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　  H(X) = -∑pilog(pi)

　　在这里就不展开讲熵的一些特性了，具体可以参考信息论的任意一本相关书籍。从熵我们可以继而引出条件熵的概念。条件熵表示在已知X的情况下Y的不确定性，定义为：

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　H(Y|X) = ∑piH(Y|X=xi)

　　当我们对信息量化之后，我们就可以根据这些量化后的数值来选取决策树的分类规则。我们用信息增益，表示得知特征X的信息如何对类Y的信息不确定性的减少程度。我们如下定义：特征A对训练数据集D的信息增益g(D,A)等于集合D的经验熵与特征A给定条件下D的经验条件熵之差，即：

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 g(D,A)=H(D)-H(D|A)

　　那么根据信息增益我们特征选取的方法如下，针对每个训练数据集D，计算每个特征的信息增益，并比较他们的大小，选择信息增益最大的特征。设训练数据集D，|D|表示其样本容量，设K个类Ck,k=1,2,……K，|Ck|为该类的样本个数，∑|Ck|=|D|。设特征A有n个不同的取值{a1,a2,……an}，根据特征A我们将整个D划分为n个子集D1，D2，……Dn。记子集Di中属于类Ck的样本集合记为Dik。算法描述如下：

　　输入：训练数据集D和特征A；

　　　　(1)计算数据集D的经验熵H(D)，H(D)=∑|Ck|/|D|log|Ck|/|D|;

　　　　(2)计算特征A对数据集D的经验条件熵H(D|A)，H(D|A)=∑|Di|/|D|H(Di)

　　　　(3)得到信息增益：g(D,A)=H(D)-H(D|A)

　　得到信息增益算法后我们来描述ID3算法来生成决策树：

　　输入：训练数据集D，特征集A，阈值ε

　　　　　(1)若D为同一类数据，则T为单节点树，返回该类；

　　　　　(2)若A为空，则T为单节点树，并将D中实例数最大的类作为节点值返回；

　　　　   (3)否则计算所有A中所有特征的信息增益，选择信息增益最大的Ag；

　　　　　(4)如果Ag信息增益小于阈值ε，则以D中实例最大的类标记，返回T；

　　　　   (5)否则，对的每一个可能值将D分割为若干非空子集，将Di中实例最大的类作为标记，构建子节点，返回T；

　　　　　(6)对第i个子节点，以Di为训练集，以剩余的特征集递归调用。

　　就这样我们构造了一颗决策树，ID3算法本质是从经验概率的极大似然估计。

　　二、C4.5

　　C4.5相比于ID3只是把信息增益换成了信息增益比而已，其余一致。

　　三、决策树剪枝

　　按照我们的算法，一步一步的训练下去，会对输入的训练集有个近乎100%的准确分类，但显然这会导致Overfitting，为了避免这种情况出现我们要对生成的树进行剪枝。剪枝可以分为预剪枝和后剪枝，预剪枝是提前设定好的一个叶子数目，当叶子数目达到阈值时就不再生成，但这显然可能会导致分类准确率的下降，所以我们一般采用后剪枝。

　　决策树的剪枝往往通过极小化决策树的整体的损失函数来实现，设树T的叶结点个数为|T|，t是树T的叶结点，该节点上有Nt个样本点，其中k类的有Ntk,我们如此定义决策树的损失函数：

　　　　　　　　　　　　　　　　　　　　　　　　　　　　C(T)=∑NtHt(T)+α|T|

　　而α|T|就相当于正则化项，与其他机器学习算法一致。我们就依此来减去能使cost function变小的叶子节点。

 

　　四、C&RT

　　C&RT全称是classfication and regression tree，显然这种决策可以用于分类或者回归，我们只描述分类准则就不再赘述整个树的分类算法。

　　对于回归树，我们用平方误差准则。对于分类树，我们用Gini index最小化准则。C&RT的剪枝算法不同于上述的剪枝算法，但因为我写乏了，下次有机会补上！