决策树(Decision Tree)学习笔记(一)

版权声明:本文为博主原创文章,转载请注明出处。

博客最近才开始用,过去两年学习的算法很多都缺乏总结。最近在复习总结一些经典的机器学习方法和图像处理算法,包括这篇博文要总结的决策树。决策树是一种经典的统计学习方法,在上世纪八九十年代提出和完善,直到今日都还有许多基于决策树的改进方法产生。另外其它一些机器学习模型,如adaboost等也经常会用到决策树。

决策树基础

决策树是一种典型的分类方法,首先对数据进行处理,利用归纳算法生成可读的规则和决策树,然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。

决策树相关的重要算法包括

1、CLS学习系统(Hunt,Marin和Stone ,1966年)。

2、ID3算法(J.R. Quinlan,1986年)。

3、ID4算法(Schlimmer 和Fisher ,1986年)。

4、ID5算法(Utgoff,1988年)。

5、C4.5算法(Quinlan,1993年)。

6、CART算法。 (Breiman,1984)

首先看一个简单的例子。

上图就是一个最基本的决策树。决策树的基本组成部分:决策结点、分支和叶子。决策树中最上面的结点称为根结点。是整个决策树的开始。每个分支是一个新的决策结点,或者是树的叶子。
每个决策结点代表一个问题或者决策.通常对应待分类对象的属性。每个叶结点代表一种可能的分类结果。在沿着决策树从上到下的遍历过程中,在每个结点都有一个测试。对每个结点上问题的不同测试输出导致不同的分枝,最后会达到一个叶子结点。这一过程就是利用决策树进行分类的过程,利用若干个变量来判断属性的类别。

以上的例子很简单,稍加思考就能马上构建出这样一个决策树。但是试想一个分类问题,有上百维甚至上千维的特征,特征有可能是连续的也有可能是离散的,怎样构建一个能够完成分类的最小的决策树,且避免过拟合,在测试数据上也能有较好的分类或回归效果,这就是决策树算法要解决的问题。换句话说,我们要找到一个最佳决策树,尽可能小并且能够拟合数据

决策树的基本算法是自顶向下的归纳,具体如下。

1 找到最佳的决策属性A,并为节点分配一个决策属性A。

2 对于每一个A的值,创建一个新的分支,并划分训练样本

3 重复1-2这个过程,直到获得足够小的树。

要搞清楚决策树算法,其实就是搞清楚以下几个问题。

Q1: 选择最好的属性:用什么来衡量属性的“最好”?

Q2: 怎么确定何时停止分裂:避免过拟合

Q3: 如何处理连续属性?

Q4: 用缺失的属性值如何处理训练数据?

Q5: 如何处理不同代价的属性?

属性质量衡量

常见的属性质量衡量方式包括信息增益(Information gain)、增益比(Gain Ratio)、互信息(Mutual information)等。

要搞清楚这些东西,首先要明确一个很难懂的概念,熵。S是训练样本中的一个实例,熵是测量S的“不纯度”的一种方法。当结点很纯时,希望其度量值应为0。S的熵定义为

\(H\left( S \right) =-\sum_i{p\left( c_i \right) \log p\left( c_i \right)}\)

 

 

\(P(c_i)\)\(S\)属于\(c_i\)类的概率。来看一个例子。

共14个实例,9个正例(yes),5个负例(no)。这样当前数据的信息量(原始状态)用熵来计算就是:

\(H=-\frac{9}{14}\log _2\left( \frac{9}{14} \right) -\frac{5}{14}\log _2\left( \frac{5}{14} \right) =0.94\)

(1)信息增益

信息增益就是决策树在进行属性选择划分前和划分后的信息差值。信息增益越大,划分越好。

\(InfoGain\left( Y|X \right) =H\left( Y \right) -H\left( Y|X \right)\)

又写作InfoGain (Y, X)

例如,通过属性Outlook进行划分后,熵计算如下。

\(info\left( \left[ 2,3 \right] \right) =-\frac{2}{5}\log _2\left( \frac{2}{5} \right) -\frac{3}{5}\log _2\left( \frac{3}{5} \right) =0.971bits\)
\(info\left( \left[ 4,0 \right] \right) =-\frac{4}{4}\log _2\left( \frac{4}{4} \right) -\frac{0}{4}\log _2\left( \frac{0}{4} \right) =0\)
\(info\left( \left[ 3,2 \right] \right) =-\frac{3}{5}\log _2\left( \frac{3}{5} \right) -\frac{2}{5}\log _2\left( \frac{2}{5} \right) =0.971bits\)

\(info\left( \left[ 2,3 \right] ,\left[ 4,0 \right] ,\left[ 3,2 \right] \right) =\frac{5}{14}\times 0.971+\frac{4}{14}\times 0+\frac{5}{14}\times 0.971=0.693bits\)

因此,outlook属性划分的信息增益就是0.94-0.693。类似的,计算Temperature、Windy、和Humidity的信息增益,选择信息增益最大一个属性进行划分。

(2)增益比

信息增益更适合有很多值的属性,它有一个代替方案就是增益比。

\(GainRatio\left( S,A \right) =\frac{infoGain\left( S,A \right)}{SplitInfo\left( S,A \right)}\)

\(SplitInfo\left( S,A \right) =H_s\left( A \right) =-\sum_{a\in Values\left( A \right)}{\frac{|S_a|}{|S|}\log _2\frac{|S_a|}{|S|}}\)

避免过拟合

一个假设在训练数据上能够获得比其他假设更好的拟合,但是在训练数据外的数据集上却不能很好的拟合数据。此时我们就叫这个假设出现了overfitting的现象。过拟合的标准定义:给定一个假设空间H,一个假设h属于H,如果存在其他的假设h’属于H,使得在训练样例上h的错误率比h’小,但在整个实例分布上h’比h的错误率小,那么就说假设h过度拟合训练数据。

决策树避免过拟合的方法有停止生长法和后剪枝法。停止生长法是指,设定一个阈值,当信息增益或树的深度或其它的一些指标达到阈值后,停止生长。后剪枝法更常用也更可靠。顾名思义,后剪枝法是训练中或训练后通过在验证集或训练集本身做测试,修剪掉没有用的分支。后剪枝法的一般步骤如下。

a. 将数据拆分为训练集和验证集,来评估剪枝方法在修剪结点上的效用

b. 做如下步骤,直到进一步修剪是有害的

        使用所有的训练集合进行训练,用统计测试来估计修剪特定结点是否会改善验证数据的评估性能

        贪婪地删除那些不能在验证集上提高性能的点

既然要在验证集上做测试,就涉及到评价方法和指标的问题。一般评价方式包括直接在验证集上验证和交叉验证两种方式。指标包括准确率、误差分类代价和MDL ( Minimum Description Length)准则。前两个好理解,MDL准则将在下一篇中详述。

连续属性的处理

上面举得例子中的属性都是离散的,但是分类数据很多都是带有连续的特征,如温度等。一般决策树的处理方式是建立分割点,如teperature>40? True:False。那么分割点如何选择呢?一般步骤如下。

a. 根据连续属性的值进行样本排序。

b. 确定那些目标标签和属性值不同的相邻的样本,组成一个候选分割点集合。

c. 计算每个分裂点的增益,选择一个具有最高增益的。

处理缺失的属性值

解决方案有,假设一个属性可以让值“空白;给节点n分配训练数据中最常见的值A;给节点n分配训练数据中最常见的值A,他们有相同目标类;分配概率pi 给A属性每个可能的值vi;给树的每个后代的样本分配一个分数( pi )

i)计算属性a的增益或者增益率时,如果有些样本没有属性a,那么可以有这么几种处理方式:(I)忽略这些缺失属性a的样本。(C)给缺失属性a的样本赋予属性a一个均值或者最常用的的值。(R)计算增益或者增益率时根据缺失属性样本个数所占的比率对增益/增益率进行相应的“打折”。(S)根据其他未知的属性想办法把这些样本缺失的属性补全。
Ii)当属性a已经被选择,该对样本进行分支的时候,如果有些样本缺失了属性a,那么:(I)忽略这些样本。(C)把这些样本的属性a赋予一个均值或者最常出现的值,然后再对他们进行处理。(R)把这些属性缺失样本,按照具有属性a的样本被划分成的子集样本个数的相对比率,分配到各个子集中去。至于哪些缺失的样本被划分到子集1,哪些被划分到子集2,这个没有一定的准则,可以随机而动。

代价

属性的代价可能不同。例如物品的成本等。用低代价期望学习一棵树,可以用以下函数代替增益。

\( \frac{Gain^2\left( S,A \right)}{Cost\left( A \right)}\)

以上就是决策树基本内容。下一篇博文将回顾几种经典的决策树算法,ID3、C4.5和CART。

返回首页