决策树学习通常包括3个步骤：特征选择，决策树生成，决策树修剪。

决策树的一个重要性质： 路径是互斥且完备的。

决策树通常是递归的选择最优特征，根据该特征对数据进行分割。可能会有过拟合问题，所以在生成决策树之后要进行剪枝。

1. 特征选择

数据集会有很多各种各样的特征，怎么选取最优的特征，最具分类能力的特征，排除无关影响？

通常特征选择的准则是信息增益或信息增益比 最大的。

信息增益：表示得知特征X的信息之后，使类Y的信息的不确定性减少的程度。

熵：是表示随机变量不确定性的度量，不确定性越大，熵的值就越大。

H(p) = -∑p_ilogp_{i    这是对整个数据类的熵，不是单个特征的。}

H(Y|X) = ∑p_iH(Y|X=x_i)   条件熵：在X给定的条件下，Y的不确定性。如果X特征只有一个取值，就不用最外面的求和了。（该特征可以舍弃，说明无用）

所以：

信息增益（互信息）：g(Y,X) = H(Y) - H(Y|X)

----可能会存在偏向于选择取值较多的特征的问题，使用信息增益比校正。

信息增益比： g_R(Y,X) = (H(Y) - H(Y|X)) / H(X)   　　　　--H(X): 是训练数据集中特征X的熵

 

2. 决策树生成

2.1 ID3算法

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

输出：决策树T

　　1. 若D中所有实例属于同一类C_k，则T为单节点树，将该类C_k作为该节点的类标记，返回T。

　　2. 若A=Ø，则T为单节点树，并将D中实例树最大的类C_k作为该节点的类标记，返回T。

　　　　3. 否则： 计算A中各特征的信息增益，选择信息增益最大的特征Ag；

　　　　4. 如果Ag的信息增益小于阈值e，则置T为单节点树，将D中实例树最大的类C_k作为该节点的类标记，返回T。

　　　　　　5. 否则，根据Ag的特征取值将D进行分割，并将Di中实例数最大的类作为（子节点or该节点？）标记，构成树T。

　　　　　　6. 对第i个子节点，递归进行上述1～5步，得到子树Ti，返回Ti。

问题：虽然使用了一个阈值e，但是仍然容易产生过拟合问题。

2.2 C4.5算法

将上述ID3算法中的信息增益替换为信息增益比。

 

3. 决策树的剪枝

决策树会对已知的训练数据分类很准确，但是对未知数据却没有那么准确，会产生过拟合现象。

剪枝往往通过极小化决策树整体的损失函数实现。

C(T) = ∑N*H(T) + α|T|

|T|:  是叶节点个数。

N是叶节点t的样本点个数，H是叶节点t的经验熵。

算法：

输入：决策树生成算法产生的树T，参数α。

输出：修剪后的子树T_α。

1. 计算每一个节点的经验熵。

2. 递归的从树的叶节点向上收缩。

　　含该叶节点的树Tb，收缩到其父节点的树Ta，

　　　　若损失函数C(Tb) >= C(Ta)

　　　　则进行剪枝。

3. 返回2，直到不能继续为止。