原理

特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的准则是信息增益或信息增益比。

信息增益

在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为

\[P(X=x_1)=p_i, i=1,2,...,n\]

则随机变量X的熵定义为

\[H(X)=-\sum_{i=1}^N p_i log p_i\]

若\(p_i=0\)，则定义\(0log0=0\)。通常，上式中对数以2为底或以e为底（自然对数），这时熵的单位分别称作比特（bit）或纳特（nat）。由定义可知，熵只依赖于X的分布，而与X的取值无关，所以也可以将X的熵记作H(p)，即

\[H(p) = -\sum_{i=1}^N p_i log p_i\]

熵越大，随机变量的不确定性就越大。

设有随机变量(X,Y)，其联合概率分布为

\[P(X=x_i, Y=y_i)=p_{ij}, i=1,2,...,n; j=1,2,...,m\]

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵（conditional entropy）H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望

\[H(Y|X)=\sum_{i=1}^n p_i H(Y|X=x_i)\]

这里，\(p_i=P(X=x_i), i=1,2,...,n\)。

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。此时，如果有0概率，令0log0=0。

信息增益（information gain）表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

信息增益：特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即

\[g(D,A) = H(D) - H(D|A)\]

一般地，熵H(Y)与条件熵\(H(Y\mid X)\)之差称为互信息（mutual information）。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

决策树学习应用信息增益准则选择特征。给定训练数据集D和特征A，经验熵H(D)表示对数据集D进行分类的不确定性。而经验条件熵H(D|A)表示在特征A给定的条件下对数据集D进行分类的不确定性。那么它们的差，即信息增益，就表示由于特征A而使得对数据集D的分类不确定性减少的程度。显然，对于数据集D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。

根据信息增益准则的特征选择方法是：对训练数据集（或子集）D，计算每个特征的信息增益 ，并比较它们的大小，选择信息增益最大的特征。

设训练数据集为D，|D|表示其样本容量，即样本个数。设有K个类\(C_k,k=1,2,...,K\)，\(\mid C_k \mid\)为属于类\(C_k\)的样本个数，\(\sum_{k=1}^K \mid C_k \mid = \mid D \mid\)。设特征A有n个不同的取值\({a_1,a_2,...,a_n}\)，根据特征A的取值将D划分为n个子集\(D_1, D_2,...,D_n\)，\(\mid D_i \mid\)为\(D_i\)的样本个数，\(\sum_{i=1}^n \mid D_i \mid = \mid D \mid\)。记子集\(D_i\)中属于类\(C_k\)的样本的集合为\(D_{ik}\)，即\(D_{ik} = D_i \cap C_k\)，\(\mid D_{ik} \mid\)为\(D_{ik}\)的样本个数。于是信息增益的算法如下：

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

输出：特征A对训练数据集D的信息增益g(D,A)

(1) 计算数据集D的经验熵H(D)

\[H(D) = -\sum_{k=1}^K \frac{\mid C_k \mid}{\mid D \mid} log_2 \frac{\mid C_k \mid}{\mid D \mid}\]

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

\[H(D \mid A)=\sum_{i=1}^n \frac{\mid D_i \mid}{\mid D \mid}H(D_i) = -\sum_{i=1}^n \frac{\mid D_i \mid}{\mid D \mid} \sum_{k=1}^K \frac{\mid D_{ik} \mid}{\mid D_i \mid} log_2 \frac{\mid D_{ik} \mid}{\mid D_i \mid}\]

(3) 计算信息增益

\[g(D,A)=H(D)-H(D \mid A)\]

信息增益比

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比（information gain ratio）可以对这一问题进行校正。这是特征选择的另一个准则。

信息增益比：特征A对训练数据集D的信息增益比\(g_R(D,A)\)定义为其信息增益\(g(D,A)\)与训练数据集D关于特征A的值的熵\(H_A(D)\)之比，即

\[g_R(D,A)=\frac{g(D,A)}{H_A(D)}\]

其中，\(H_A(D)=-\sum_{i=1}^n \frac{\mid D_i \mid}{\mid D \mid} log_2 \frac{\mid D_i \mid}{\mid D \mid}\)，n是特征A取值的个数。

决策树的生成

ID3算法

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。

具体方法是：从根结点（root node）开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一个决策树。ID3相当于用极大似然法进行概率模型的选择。

ID3算法

输入：训练数据集D，特征集A，阈值\(\varepsilon\);

输出：决策树T.

(1) 若D中所有实例属于同一类\(C_k\)，则T为单结点树，并将类\(C_k\)作为该结点的类标记，返回T;

(2) 若\(A=\emptyset\)，则T为单结点树，并将D中实例数最大的类\(C_k\)作为该结点的类标记，返回T;

(3) 否则，计算A中各特征对D的信息增益，选择信息增益最大的特征\(A_g\);

(4) 如果\(A_g\)的信息增益小于阈值\(\varepsilon\)，则置T为单结点树，并将D中实例数最大的类\(C_k\)作为该结点的类标记，返回T;

(5) 否则，对\(A_g\)的每一可能值\(a_i\)，依\(A_g=a_i\)将D分割为若干非空子集\(D_i\)，将\(D_i\)中实例最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T;

(6) 对第i个子结点，以\(D_i\)为训练集，以\(A-{A_g}\)为特征集，递归地调用步(1)~步(5)，得到子树T，返回\(T_i\)。

ID3算法只有树的生成，所以该算法生成的树容易产生过拟合。

C4.5的生成算法

C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进，C4.5在生成的过程中，用信息增益比来选择特征。

参考文献

  • 统计学习 李航 第5章 决策树