Created by potrace 1.13, written by Peter Selinger 2001-2015

决策树

决策树引导

通俗来说，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：

      女儿：多大年纪了？

      母亲：26。

      女儿：长的帅不帅？

      母亲：挺帅的。

      女儿：收入高不？

      母亲：不算很高，中等情况。

      女儿：是公务员不？

      母亲：是，在税务局上班呢。

      女儿：那好，我去见见。

这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。

image

信息熵

下面有两个决策树第一次分割后的结果,你觉得哪个分类结果更好呢?

image

很显然,后者的结果更为理想.因为后者的分割后有一部分不需要再继续分割了,也就是很"纯".而前者分割后的两部分都需要进一步分割,所以后者更优.

通过上面这个例子我们知道决策树的目的就是为了让每个部分更"纯".在信息论中我们用熵来表示"纯度".样本集合D的信息熵为:

Ent(D) =-\sum^{|y|}_{i=1}p_ilog_2(p_i)

其中 p_i 表示第i个类别在整个训练元组中出现的概率.

当熵为1时表示样本类别均匀分布,,当熵为0时表示只有一类样本.

条件熵

条件熵代表在某一个条件下，随机变量的复杂度.更通俗的讲,原来的数据不是很纯,我们根据一个条件把这些数据切分后,是不是每一份都变纯了?

假定样本的某个离散属性a有V个可能的取值 \{a^1,a^2,a^3,...,a^v\} ，若使用a来对样本集D进行划分，则会将D分为 \{D^1,D^2,D^3,...,D^v\} .

划分后的条件熵为:

Ent(D | a) = \sum_{v=1}^V \frac{|D^v|}{|D|}Ent(D^v)

此时的条件熵表示,根据属性a划分后,数据的纯度.

信息增益

信息增益代表了某个集合按照某种条件划分后,信息熵的改变程度.即:

信息增益 = 信息熵-条件熵

公式为:

Gain(D,a) = Ent(D) - \sum_{v=1}^V \frac{|D^v|}{|D|}Ent(D^v)

我们会选择对信息熵减小最大的一个属性进行划分,也就是:

a_* = arg \; max_{a \in A} Gain(D,a)

著名的ID3算法就是以信息增益为准则来选择最优划分属性的.

增益率

ID3算法存在一个问题，就是偏向于多值属性，例如，如果存在唯一标识属性ID，则ID3会选择它作为分裂属性，这样每个分支都是最纯的，但这样划分明显是过拟合了,无法泛化模型。

为了解决这个问题,著名的C4.5算法,使用增益率来选取最优的划分属性:

GainRatio(D,a) = \dfrac{Gain(D,a)}{IV(a)}

其中:

IV(a) = \sum_{v=1}^V \frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}

当某属性的取值数目越多IV(a)会越大,这也导致增益率偏向选取取值少的属性,所以我们会先从属性中找寻信息增益率高于平均值的,再从中选取增益率最高的.

基尼指数

CART算法使用基尼指数来选取最优的划分属性.

数据集D的纯度可用基尼值来衡量:

Gini(D) = 1 - \sum_{v=1}^{|y|} p_k^2

属性a的基尼指数定义为:

GiniIndex(D,a) = 1 - \sum_{v=1}^V Gini(D^v)

剪枝

一颗完全生长的决策树会面临一个严重的问题,即过拟合.假设我们使用决策树对DNA进行分类,由于每个人的DNA都是不同的,完全生长的决策树每个节点仅会包含一个样本,这是过拟合的.

为了防止决策树过拟合,我们必须对其进行剪枝.剪枝分为预剪枝和后剪枝.预剪枝是指在子树生长之前,判断该子树是否对模型有利,有利则生长,否则停止该子树的生长.后剪枝指让一个决策树完全生长,然后在去掉对模型泛化能力有影响的子树.

预剪枝注意包括以下三种方案:

预剪枝算法简单,高效,但是需要一定的经验判断.

后剪枝的思想是让决策树完全生长,然后再自底向上依次判断是否需要剪枝,例如可以先计算剪枝前的误差率,再计算剪枝后的误差率,如果剪枝对模型有提高则进行剪枝.后剪枝能保证模型有较好的泛化能力和拟合能力,但是计算量需求较高.

决策树是如何处理非线性的

线性回归通过增加高次多项式可以处理非线性问题.支持向量机通过核函数把低维数据映射到高维空间,从而在高维空间解决非线性分类问题.那么决策树是如何解决非线性问题的呢?来看一个简单的例子:

image

如果用树状图表达的话是这样的:

image

实际上我们可以通过更多次的分割,来处理出更复杂的非线性问题.

回归树

决策树不仅可以用来解决分类问题,还可以用来解决回归问题.

假设回归树把空间分成M个单元 R_1,R_2,...,R_M ,并且在每个单元中有一个固定的输出 c_m ,于是回归树可以表示为:

f ( x ) = \sum _ { m = 1 } ^ { M } c _ { m } I \left( x \in R _ { m } \right)

其中 c_m 为对应单元 R_m 中y的均值.

现在的问题是如何切分能使函数的误差最小.回归树和分类树一样,每次把空间切分成两份,假设以 x_j 为切分点,切分成 R_1,R_2 两个单元,那么损失函数为:

\sum_{x_i\in R_1}(y_i-c_1)^2 + \sum_{x_i\in R_2}(y_i-c_2)^2

可以扫描切分点j,使得损失函数最小:

\min_j\bigg[\sum_{x_i\in R_1}(y_i-c_1)^2 + \sum_{x_i\in R_2}(y_i-c_2)^2\bigg]

接下来递归使用上式对空间进行切分,直到效果满意为止.

下图为回归树分类的效果:

image

编程实现:
https://www.kaggle.com/swimmingwhale/decision-tree

参考:
周志华<机器学习>
Udacity<机器学习入门>
https://www.cnblogs.com/pinard/p/6050306.html
http://www.cnblogs.com/pinard/p/6053344.html
https://juejin.im/post/5a16bd40f265da430c117d64
https://juejin.im/post/5aa503b4518825555d46e1d8

posted @ 2018-09-06 18:54:20
评论加载中...
发表评论