决策树引导

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

      女儿:多大年纪了?

      母亲:26。

      女儿:长的帅不帅?

      母亲:挺帅的。

      女儿:收入高不?

      母亲:不算很高,中等情况。

      女儿:是公务员不?

      母亲:是,在税务局上班呢。

      女儿:那好,我去见见。

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

信息熵

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

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

通过上面这个例子我们知道决策树的目的就是为了让每个部分更"纯".在信息论中我们用熵来表示"纯度".样本集合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都是不同的,完全生长的决策树每个节点仅会包含一个样本,这是过拟合的.

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

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

  • 设置树深度,当达到一定深度停止生长
  • 设置最小样本数,当节点样本数小于某个阀值停止生长
  • 在生长分支前,使用验证集来验证分支是否对模型有利,如果分支对模型不利则阻止分支的生成.

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

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

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

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

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

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

回归树

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

假设回归树把空间分成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.png


编程实现:
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
评论加载中...

发表评论