222a7b8f1420e20a7e2ff086e7bf4e67
决策树&ID3,C4.5,CART

1、 前言

之前我们已经说了,机器学习的从线性回归,概率这个出发点发展的算法。这次我们讲从第三个出发点,使用信息熵的算法,决策树。

2、 信息熵

首先我们来介绍什么是信息熵,信息熵是1948年,香农引入信息熵。一个系统越是有序, 信息熵就越低,一个系统越是混乱,信息熵就越高,所以信息熵被认为是一个系统有序程度的度量。举个例子,太阳从东边升起这个规律人人都知道,所以信息熵低,而GAN算法是怎么推导的知道的人就不多,所以它的信息熵高。
注:一个事件发生的概率大,那么它含有的信息少。

一言已概之就是:信息熵就是用来描述系统信息量的不确定度。其公式如下:
$$
H(x) = - \sum_{i=1}^m p_i log_2(p_i)
$$

条件熵的定义为: 给定条件X的情况下,所有不同x值情况下Y的信息熵的平均值叫做条件熵。
$$
H(Y|X) = \sum_{j=1}P(X = v_j)H(Y|X = v_j)
$$
$$
H(Y|X) = H(X,Y)-H(X)
$$

3、 纵览决策树算法

在了解了这个算法的关键评判标准后,我们来看下决策树是什么,决策树 ( Decision Tree ) 是在已知各种情况发生概率的基础上,通过构建决策树来进行分析的一种方式,是一种直观应用概率分析的一种图解法。决策树是一种树形结构, 其中每个内部节点表示一个属性的测试,每个分支表示一个测试输出,每个叶节点代表一种类别。
换句话说,决策树的使用是一种模拟了简单的人类思考过程的思路。通过许多if...else...进行判断最后得到一个结论。

3.1、 决策树构建过程

构建步骤如下:

  1. 将所有的特征看成一个一个的节点;
  2. 遍历每个特征的每一种分割方式,找到最好的分割点;将数据划分为不同的子节点 $N_1, N_2,...,N_m$。计算划分之后所有子节点的纯度信息。
  3. 对第二步产生的分割,选择出最优的特征以及最优的划分方式。得出最终的子节点: $N_1,N_2,...,N_m $
  4. 对子节点分别继续执行2-3步,直到每个最终的子节点都足够
    注:这里的纯度指的是每个字节点的类别尽量相同。注意构建过程中的选择最优特征的步骤决定了后期算法的不同

3.2、划分方式的选择

在上述 3.1 中提到了两个关键性的事情,叫做划分方式和选择最优特征,这里我们就要讨论的是划分方式。众所周知,数据分为离散的和连续的,显然我们对他们的处理有些不同。

如果属性是离散值,且要求是二叉树,我们就可以按照一般的逻辑方式,按照属于此子集不属于此子集分成两个分支。如果没有要求是二叉树则一个属性就是一个分支。

如果是属性为连续值,则可以确定一个值作为分裂点split_point,按照>split_point<=split_point生成两个分支。

3.3、 决策树分割属性选择

之前我们说了划分方式,那么我们如何选择最优的特征呢。答案是比较纯度。首先决策树算法是一种“贪心”算法策略,只考虑在当前数据特征情况下的最好分割方式,且不能进行回溯操作。而对于整体的数据集而言,通过查看每个特征属性划分后,纯度的变化进行比较,选择能让数据集变得更纯的特征属性进行分割。之后重复上述步骤直到满足条件。

注:题外话,虽然我们很少需要自己造轮子,但是还是需要知道树的结构是符合递归规律的,一般而言树的构建都可以使用递归算法

那么纯度是什么,纯度其实就是一种判断决策树是否向着正确方向前进的判断。粗鄙的类比,就是母猪配种,选择最合适的方式将不同种的猪分开,尽量保证每波猪都是纯种的。纯度的判断标准不同也决定了之后的算法的名称不同,其标准如下三种:

  • 基尼系数:$Gini = 1 - \sum_{i=1}^nP(i)^2$
  • 信息熵:$-\sum_{i=1}^n P(i)log_2(P(i))$
  • 误差率:$Error = 1 - max_{i=1}^n \{P(i)\}$

注1:这里我说的是算法名称不同,其实更多的想指代他们是一个系列的算法,和 LR 与 Lasso 和 Ridge 的关系一样
注2:如上公式都体现了纯度值越小信息量越大这个理念
上面是基础的一些系数,在剪枝和判断的时候需要一个种体现变化的系数,于是出现了如下公式来作为 C4.5 和 ID3 的判别标准。简单的理解为,这个公式表达了以A属性划分后,信息量增加的量,或者说指代的是纯度变纯了多少。

top Created with Sketch.