决策树(Decision Tree)是目前比较火的模型之一,它的升级版GBDT以及XGBoost等都是广泛应用的,它的思路相比于逻辑回归(Logistic Regression)具有更好的可解释性。

决策树实际上是将空间用超平面进行划分的一种方法,每次分割的时候,都将当前的空间一分为二, 这样使得每一个叶子节点都是在空间中的一个不相交的区域,在进行决策的时候,会根据输入样本每一维feature的值,一步一步往下,最后使得样本落入N个区域中的一个(假设有N个叶子节点)。决策树是基于树结构来进行决策的,可以分为分类树和回归树,分类树是面向于离散的数据变量,而回归树则是面向于连续的数据变量,下面我将分块介绍这些不同的东西。

本篇博客代码在这

分类树

这一段大量参照**[REFERENCES 1]**中的案例,其中只是对中间有些我不是很明白的地方做一下重点处理。

我们判定一个西瓜的好坏,我们通常会进行一些"if else"结构判断,即这个瓜的色泽如何,如果色泽好,就是好瓜,如果色泽不好就不是好瓜等等,一连串的"if else"结构串起来就成了一个树结构,如下图所示。

image-20180816095005229

也就是判定过程非常类似于人类,但是决策树最关键的问题在于如何构建这样一棵树,比如第一个是色泽好一些,还是根蒂好一些,还是敲声好一些……我们需要一个统一的判定条件,对应于ID3方法,使用的是信息增益判别标准,当然这个一会再说,接下来还需要说一下这棵树长到啥时候停止,共有三种情况(注意这是面向训练集的):

  1. 当前结点包含的样本全属于同一类别,无需划分。假设上图色泽是青绿的时候都是好瓜了,那么这个树就没必要再分了,你无论再怎么分都是好瓜,所以无需划分。
  2. 当前属性集为空,或是所有样本在所有属性上取值相同,无法划分。假设目前属性值就只有色泽、根蒂、敲声,但是这三个属性都划分完了,还是有好瓜和坏瓜,这个时候树应该继续生长的,可是没有属性了,没有划分的依据了,只好作罢,因此这是无法划分。
  3. 当前结点包含的样本集合为空,不能划分。这就是说属性还没用完的时候已经没有瓜了,也就是样本集合为空,这也划分不了。

因此这三点共同决定树何时停止增长。接下来就要讨论一下如何从属性集中选择最优属性划分的办法。

属性划分

我们希望分支结点所包含的样本尽可能属于同一类别,即结点的“纯度”(purity)越来越高,而信息熵(information entropy)是度量样本纯度的一种常用指标,定义为

$Ent(D) = - \sum ^ {|\mathcal{Y}|} _ {k =1} p_k log_2p_k$

其中Y|\mathcal{Y}|表示的类别数量,比如上面的西瓜问题Y=2|\mathcal{Y}| = 2,即好瓜、坏瓜,pkp_k是指在每一个类别中所占的比例,Ent(D)Ent(D)越小说明纯度越高。比如是二分类问题的时候,当分类1的概率为1,分类2概率为0时,这时候Ent(D)=0Ent(D) = 0,因为只有分类1,纯度非常高,纯度最低的时候是这几个分类概率一样的时候。

ID3(Iterative Dichotomiser 3)

假定离散属性值aaVV个可能的取值{a1,a2,,aV}\{a^1, a^2, \dots, a^V\},其中DvD^v表示D中取值为ava^v的样本,我们可以根据这些计算信息增益(information gain)

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

其中Ent(D)Ent(D)是原有数据的信息熵,v=1VDvDEnt(Dv)\sum ^ V _ {v = 1} \frac{|D^v|}{|D|} Ent(D^v)可以理解为按照属性aa划分后的信息熵,两者相减就是新划分的属性的信息熵相对于原先没划分之前下降了多少,差值越大说明纯度提升越高。

因此ID3的核心算法就是遍历各个属性,找到信息增益最大的那个属性作为最优划分属性,数学符号表示为a=argmaxaAGain(D,a)a_* = \mathop{\arg\max}_{a \in A} Gain(D, a)

image-20180816110037639

上面是西瓜数据集,我们需要一个个计算各个属性的信息增益,我们这里以色泽为例。

首先需要计算Ent(D)Ent(D),其中正例(好瓜)有8个,反例有9个,因此

$Ent(D) = - (\frac{8}{17} log_2\frac{8}{17} + \frac{9}{17} log_2\frac{9}{17}) = 0.998$

我们标记D1D^1为青绿,D2D^2标记为乌黑,D3D^3标记为浅白,其中D1D^1共有6个实例,正例(好瓜)比例为36\frac{3}{6},反例为36\frac{3}{6},那么信息熵为

$Ent(D^1) = - (\frac{3}{6}log_2\frac{3}{6} + \frac{3}{6}log_2\frac{3}{6}) = 1$

同理可以计算出Ent(D2)=0.918,Ent(D3)=0.722Ent(D^2) = 0.918, Ent(D^3) = 0.722,最后我们计算信息增益Gain(D,)Gain(D, 色泽)

$Gain(D, 色泽) = Ent(D) - \sum ^ 3 _ {k = 1} Ent(D^v) = 0.109$

然后我们依次计算根蒂、敲声……直至所有计算完毕,我们可以得到纹理信息增益最大(0.381),因此这个最优属性就是纹理。接着我们通过迭代使得决策树增长,直到满足上述3个停止条件为止。

C4.5决策树算法

使用信息增益会有一个问题,就是它倾向于可取值数目较多的属性,比如我们把上面西瓜数据集的编号也纳入,那么第一次的最有属性一定是编号,因为每一个分类中纯度都是最高的,但是没有实际意义,导致泛化能力过弱,比如下一个西瓜编号为18,那么这个就不行了。

C4.5决策树算法是在上述基础上的概率,引入了增益率,其定义为

$Gain\_ratio(D, a) = \frac{Gain(D, a)}{IV(a)} = \frac{Gain(D, a)}{- \sum^{V}_{v=1} \frac{|D^v|}{|D|}log_2 \frac{|D^v|}{|D|}}$

IV(a)IV(a)称为属性aa的固有值,属性aa的属性值越大通常固有值越大。需要注意的是C4.5算法是一个启发式算法,它不是直接选定一个最优划分属性,而是先从候选属性中找出信息增益高于平均水平的属性,在从中选择增益率最高的。

CART决策树

CART决策树在解决分类问题的时候使用的是基尼指数(Gini Index),数据集DD的纯度可以用基尼值度量

$Gini(D) = \sum^{|\mathcal{Y}|}_{k=1}\sum_{k' \ne k}p_kp_{k'} = 1 - \sum^{|\mathcal{Y}|}_{k=1} p^2_k$

这个直观的说是随便抽取两个样本不一样的概率,如果纯度越高说明抽取到不一样的概率越小,因此基尼值就应该越小。

属性aa的基尼指数定义为

$Gini\_index(D,a) = \sum^V_{v=1} \frac{|D^v|}{|D|} Gini(D^v)$

在选择最优属性的时候我们使得划分后基尼指数最小的属性作为最优划分属性,数学符号描述为a=argminaAGini_index(D,a)a_* = \mathop{\arg\min}_{a \in A} Gini\_index(D, a)

剪枝处理

剪枝处理主要是防止过拟合的,就像之前说的如果不小心加入可西瓜编号,这个东西虽然能很好地拟合训练集,但是根本无法泛化,因此需要做适当的剪枝处理,一般分为两种:预剪枝和后剪枝,这里就不在赘述,有兴趣的可以参照**[REFENERCES 1]**中的内容,这里只说一下这两种方式的特点:

  • 预剪枝采用的是贪心算法,是自顶向下的一种剪枝方式,有一些欠拟合的风险,但是速度更快;
  • 后剪枝则是自底向上的,需要变量整个树,因此时间消耗更多,但是由此带来的好处是欠拟合风险小而且有更强的泛化能力。

回归树

回归树是利用连续属性离散化技术来把在哪里划分点的问题解决了,对于一个连续的属性aa,假定出现了nn个不同的取值,将这些值从小到大进行排序记为{a1,a2,a3,}\{a^1, a^2, a^3, \dots\},基于划分点tt可以将DD子集分为DtD^{-}_tDt+D^{+}_tDtD^{-}_t表示那些属性aa上取值不大于tt的样本,Dt+D^{+}_t同理,对于相邻属性取值aia^iai+1a^{i+1}之间取任意值划分结果相同,因此属性aa包括了n1n-1个可划分点,其集合为

$T_a = \{\frac{a^i + a^{i+1}}{2} | 1 \le i \le n-1\}$

这个时候我们就可以像离散属性值一样来考察这些划分点了,如ID3求信息增益等等。

但是需要注意的是,与离散属性不同,若当前节点划分属性为连续属性,该属性还可以被后代结点进一步划分,如西瓜有一个密度属性,父节点划分属性为0.381密度 \le 0.381,不会禁止在子节点上使用0.294密度 \le 0.294

CART算法

在回归问题中,CART就不是采用Gini指数了,而是最小二乘。我们将jj表示为第jj个特征,取值为ss,那么可以得到两个区域R1(j,s)={xx(j)s}R_1(j, s) = \{x|x^{(j)} \le s\}R2(j,s)={xx(j)>s}R_2(j, s) = \{x|x^{(j)} \gt s\},因此我们可以通过遍历全部的可划分点来找到最优的划分点

$min_{j, s}[min_{c_1} \sum_{x_i \in R_1(j, s)} (y_i - c_1)^2 + min_{c_2} \sum_{x_i \in R_2(j, s)} (y_i - c_2)^2]$

其中cmc_m表示该区域内所有点yy值的平均数,也就是cm=avg(yixiRm)c_m = avg(y_i|x_i \in R_m)

举一个简单的实例,训练数据如下:

x 1 2 3 4 5 6 7 8 9 10
y 5.56 5.7 5.91 6.4 6.8 7.05 8.9 8.7 9 9.05

在本数据集中,只有一个变量,因此最优切分变量自然是xx,切分点为[1.5,2.5,3.5,,9.5][1.5, 2.5, 3.5, \dots, 9.5]共计9个,接下来计算平均值:

s 1.5 2.5 3.5 4.5 5.5 6.5 7.5 8.5 9.5
c1c_1 5.56 5.63 5.72 5.89 6.07 6.24 6.62 6.88 7.11
c2c_2 7.5 7.73 7.99 8.25 8.54 8.91 8.92 9.03 9.05

s=1.5s = 1.5为例,c1=5.56c_1 = 5.56c2=19(5.7+5.91++9.05)=7.5c_2 = \frac{1}{9}(5.7 + 5.91 + \dots + 9.05) = 7.5,最后带入上式中,结果为

s 1.5 2.5 3.5 4.5 5.5 6.5 7.5 8.5 9.5
m(s) 15.72 12.07 8.36 5.78 3.91 1.93 8.01 11.73 15.74

还是以s=1.5s = 1.5为例,m(1.5)=(5.565.56)2+(5.77.5)2+(5.917.5)2++(9.057.5)2=15.72m(1.5) = (5.56 - 5.56) ^ 2 + (5.7 - 7.5) ^ 2 + (5.91 - 7.5)^2 + \dots + (9.05 - 7.5)^2 = 15.72,剩下的以此类推,因此我们知道在s=6.5s = 6.5的时候m(s)最小,因此最优划分点就是6.5的时候,划分完后再两个区域内继续寻找最优点。

过拟合

如果不加干预,这个树长的足够大的时候,也就是在空间切块的时候,只要切得足够多,就可以让每一个样本独占一块区域,这样在训练集中将会有不错的效果,但是泛化能力极低。

解决的办法是加入惩罚项,公式变为

$\sum^{|T|}_{m = 1} \sum_{x_i \in R_m} (y_i - c_m)^2 + \alpha |T|$

其中T|T|代表叶子节点的个数,即划分区域的个数,α\alpha是一个超参数。因此这个的意思是既要满足最小二乘,又不能使叶子节点太多。

Bagging思想

之所以过拟合会出现,原因在于样本里有一些噪声(noisy)使得学习器会把错误的信息学到,那么除了上述添加惩罚项的方式,还可以使用bootstraping方式,假设目前有1000份样本,每次随机抽取800份样本,分发给若干学习器,每个学习器获得的样本时不同的,他们把结果相互制约,这样就有天然的防止过拟合的特性。对于分类问题可以通过投票机制确定,即少数服从多数,对于回归问题可以采用平均值的方式。

随机森林(RandomForest)

随机森林是在bagging基础上进行的改进,除了对样本进行采用,RF还会对特征进行采样,比如一个数据集中有100个属性,RF每次只会随机抽取70个属性分发给学习器,这样可以最大程度的预防过拟合的问题。

REFERENCES

  1. 机器学习 周志强
  2. Regression Tree 回归树