机器学习算法(1): 决策树

Posted on | In

1. 决策树概述

决策树是一种基本的分类和回归算法。其根据数据的特征，采用树结构进行决策的方法。通常包括 3 个步骤：

  • 特征划分选择
  • 决策树生成
  • 剪枝处理

一般地，一颗决策树包含一个根节点，若干内部节点和若干叶节点。其算法的基本流程如下，其中 D 为数据集，A 为特征集：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def creatTree(D, A):
	根据 D 生成叶节点集 node  # 数据标记
	if len(node)==1:       # D 中样本属于同一类别
		标记所有数据为同一叶节点
	if A == [] or len(D.feature)==1 # D 中只有一个特征
		将 node 标记为叶节点，其 label 为 D 中样本数量最多的类
	#
	从 A 中挑出最优特征 a
	#
	for value in a:
		生成新的特征集 A* = (A-a)
		生成新的数据集 D* 表示 D 中取值为 value 的样本子集
		if D* == []
			将 node 标记为叶节点，其 label 为 D* 中样本数量最多的类
		else:
			creatTree(D*, A*)
	return tree

可以看到，算法第 8 行是决策树算法最关键的内容，即特征划分的选择：怎么选出最优特征。

2. 特征划分选择

我们希望采用某个值，按照该值可以对 A 中的特征进行排序，自然就选出了最优的特征。

2.1. 信息增益

假定当前数据集 D 中第 $k$ 类样本所占比例为 $p_k$，则 D 的信息熵为：
\begin{equation}
entropy(D) = -\sum_{k=1}^n p_k log_2 p_k
\end{equation}
假设属性 $a$ 有 $V$ 个取值，记 $D^v$ 为取值为 $a^v$ 的样本子集。用属性 $a$ 划分数据集所获得的信息增益为：
\begin{equation}
Gain(D,a) = entropy(D) - \sum^V_1 \frac{|D^v|}{D}entropy(D^v)
\label{id3}
\end{equation}
信息熵代表信息的混沌程度，信息增益的含义为：数据的混沌程度减去用 $a$ 划分后的数据混沌程度，划分后的数据集混沌程度越小，信息增益越大。因此我们可以用信息增益作为准则来选择最优特征。

2.2. ID3

ID3 就是采用公式 (\ref{id3}) 作为准则来划分特征的。

2.3. C4.5

信息增益偏好于取值数目较多的特征，为了减少这种偏好，C4.5 采用增益率作为划分特征的准则：
\begin{equation}
Gain-Ratio(D,a) = \frac{Gain(D,a)}{IV(a)}
\label{c4.5}
\end{equation}
其中：
\begin{equation}
IV(a) = -\sum_1^V \frac{|D^v|}{D} log_2 \frac{|D^v|}{D}
\end{equation}
与 $a$ 的取值数目成正比，因此，增益率准则偏好于取值数目较少的特征，为了减少这种偏好，C4.5 并不是直接采用增益率作为划分准则，而是分为两步：

  1. 找出信息增益高于平均水平的属性；
  2. 从上述属性集中选取增益率最高的属性。

2.4 CART

CART 采用基尼指数作为划分准则。基尼指数定义为：
\begin{equation}
Gini-Index(D,a) = \sum_1^V \frac{|D^v|}{D} Gini(D^v)
\end{equation}
其中，基尼值定义为：
\begin{equation}
Gini(D) = 1 - \sum_1^n p^2_k
\end{equation}
表示从数据集 D 中随机抽取两个不一样的样本的概率。

3. 剪枝处理

剪枝是为了处理过拟合，基本策略有：

  • 预剪枝：在决策树生成过程中，对每个节点划分前先进行估计，若不能带来泛化性能提升，则停止划分；
  • 后剪枝：先生成一颗完整的树，自下而上的对非叶节点进行估计，若该节点对应的子树替换成叶节点能带来泛化性能提升，则将子树替换为叶节点。

预剪枝有可能引起欠拟合，后剪枝通常比预剪枝保留更多分支。一般来说，后剪枝剪枝效果好但是时间花销大。

参考资料

[1] 《机器学习》, 周志华