【机器学习详解】决策树与随机森林算法

时间:2021-11-05 23:56:06

转载请注明出处:勿在浮沙筑高台http://blog.csdn.net/luoshixian099/article/details/51811945

决策树

决策树模型是一种树形结构,基于特征对实例进行分类或回归的过程。即根据某个特征把数据分划分到若干个子区域(子树),再对子区域递归划分,直到满足某个条件则停止划分并作为叶子节点,不满足条件则继续递归划分。
一个简单的决策树分类模型:红色框出的是特征。
【机器学习详解】决策树与随机森林算法

决策树模型学习过程通常包3个步骤:特征选择、决策树的生成、决策树的修剪。

1.特征选择

选择特征顺序的不同将会产生不同决策树,选择好的特征能使得各个子集下标签更纯净。度量特征对产生子集的好坏有若干方法,如误差率,信息增益、信息增益比和基尼指数等。
1.1误差率
训练数据D被特征A分在若干子结点后,选择子节点中出现数目最多的类标签作为此结点的返回值,记为 yc^ 。则误差率定义为 1|D|i=1|Dc|I{yiyc}
1.2信息增益

熵与条件熵:表示随机变量不确定性的度量。设计随机变量X为有限离散随机变量,且 pi=P(X=xi) 。熵的定义为 H(X)=ni=1pilog(pi) 。熵越大,随机变量的不确定性就越大,当X取某个离散值时概率为1时,则对应的熵H(X)为0,表示随机变量没有不确定性。条件熵:表示已知随机变量X的条件下随机变量Y的不确定性,定义 H(Y|X)=ni=1piH(Y|X=xi) ,其中 pi=P(X=xi) 。这里X表示某个特征,即表示根据某个特征划分后,数据Y的熵。如果某个特征有更强的分类能力,则条件熵H(Y|X)越小,表示不确定性越小。
信息增益:特征A对训练数据集D的信息增益定义为g(D,A)=H(D)-H(D|A).即有特征值A使得数据D的不确定性下降的程度。所以信息增益越大,表明特征具有更强的分类能力。

1.3信息增益比

信息增益比也是度量特征分类能力的方法。定义训练数据D关于特征A的值的熵 HA(D)=ni=1|Di||D|log2(|Di||D|) , |D| 表示训练数据的总数, |Di| 表示训练数据D中特征A取第i个值的总数目。信息增益比越大,表明特征分类能力越强。
gR(D,A)=g(D,A)HA(D)

1.4基尼指数
假设随机变量X可以取K的离散值, p(X=k)=pk 则X的基尼指数定义为: Gini(X)=Kk=1pk(1pk)=1Kk=1p2k .对于给定的样本集合D,其基尼指数为 Gini(D)=1Kk=1(|Ck||D|)2 , |Ck| 是D中属于第k类的样本个数,K是类的个数。基尼指数表示样本集合的不确定性程度,所以基尼指数越小,对应的特征分类能力越强。


下图表示一个二分类的情况下,度量样本集合的不确定性程度几种方法。熵(Entropy),基尼指数(Gini),误差率的关系(Error rate).为了方便比较熵被缩小一半。
【机器学习详解】决策树与随机森林算法

2.决策树的生成

ID3与C4.5都是决策树的经典分类决策树算法。唯一不同的是ID3算法采用信息增益作为特征选择准则,而C4.5采用的是信息增益比的方法。下面介绍ID3决定树生成算法的过程,C4.5类似。


ID3算法
从根节点开始,在数据集D上计算所有可能的特征A分别计算信息增益,选择信息增益最大的特征作为分类条件,对该特征不同的取值分别建立子集作为子节点,最对子集递归地调用以上方法。直到没有特征可以选择或者信息增益很小为止。
下面的代码来自《机器学习实战》

def createTree(dataSet, labels) :
classList = [example[-1] for example in dataSet]
if classList.count(classList[0] ) == len(classList) :#数据集全部属于同一个类别
return classList[0] #返回这个类别,并作为叶子结点
if len(dataSet[0]) == 1: #没有特征可以选择
return majorityCnt(classList) #返回数目最多的类别,并作为叶子结点
bestFeat = chooseBestFeatureToSplit(dataSet) #选择信息增益最大的特征A
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel : {}}#建立结点
del (labels[bestFeat]) #特征集中去除特征A
featValues = [example[bestFeat] for example in dataSet] #特征A下的所有可能的取值
uniqueVals = set(featValues)#去重
for value in uniqueVals: #对可能取值分别建立子树
subLabels = labels[ : ]
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)#递归建立子树
return myTree

3.决策树剪枝

不考虑复杂度的情况下,一个完全生长树很容易过拟合,对训练数据拟合很好,但对预测数据效果很差。因此要对生成的决策树做修剪,剪掉一些不必要的branch.可以通过增加正则项来控制决策树的复杂度。定义 Cα(T) 表示决策树的损失, C(T) 表示模型对训练数据的预测误差。 |T| 表示模型的复杂度,即叶子节点的数目。
Cα(T)=C(T)+α|T|
参数 α 权衡训练误差与模型复杂度。
(1)计算每个节点的经验熵
(2)递归地从树的叶节点向上回溯,计算叶节点回溯到父节点之前与之后的损失 Cα(TB) Cα(TA) ,如果 Cα(TA)<Cα(TB) ,代表修剪此节点后,损失函数更小,则进行剪枝。
(3)返回(2),直到不能继续为止。

4.CART算法

CART(Classification and regression tree)算法一种即能做分类又能做分类的决策树算法。
特征选择
回归树采用平方误差最小化准则:数据集D的平方误差定义为 |D|i=1(yiy)2 ,其中 y 表示数据集D的平均值。
分类树选择基尼指数最小化准则。
CART树生成

  • 回归树的生成

    (1)考虑数据集D上的所有特征,遍历每一个特征下所有可能的取值或者切分点,对数据集D划分成两部分 D1 D2
    (2)分别计算上述两个子集的平方误差和,选择最小的平方误差对应的特征与分割点,生成两个子节点。
    (3)对上述两个子节点递归调用(1)(2),直到没有特征可以选择,或者子节点数目很小或者平方误差小于阈值为止,作为叶子节点,并返回节点内样本的均值(也可以在叶子节点内训练回归模型作为预测值)。

  • 分类树的生成

    (1)考虑数据集D上的所有特征,遍历每一个特征下所有可能的取值或者切分点,对数据集D划分成两部分 D1 D2
    (2)分别计算上述两个子集的基尼指数的和,选择最小的基尼指数的和对应的特征与分割点,生成两个子节点。
    (3)对上述两个子节点递归调用(1)(2),直到没有特征可以选择,或者子节点数目小于阈值或者基尼指数小于阈值为止,作为叶子节点,并返回类别数目最多的类别。

CART的剪枝

CART的剪枝算法,从决策树 T0 的底端不断剪枝,直到根节点。计算完全生长树的内部的每一个结点t的剪枝系数g(t),剪枝系数代表修剪后整体损失减小的程度,即修剪前与修剪后的数据的误差下降的程度。在 T0 中剪去最小的g(t),得到的子树作为 T1 ,如此剪下去,直到根节点。利用独立的验证集,测试子树序列 T0,T1,T2...,Tn 每个子树的平方误差或者基尼指数。数值最小的决策树作为最优的决策树。

5.随机森林

最简单的RF(Random Forest)算法是bagging+完全生长CART树的组合。
通过bagging方法是建立多个分类或者回归模型,最后采用投票或平均作为预测值,可以降低过拟合。
【机器学习详解】决策树与随机森林算法
bagging对训练样本采用boostrap采样方法进行M轮,分别建立决策树。由于每轮采用出的样本子集基本不相同,训练的模型相关性会降低小。为了进一步降低模型间的相关性,每轮训练前可以对训练数据的特征进行随机采样,也可以在决策树的每个branch上进行随机特征选择。


Reference:
统计学习方法-李航
MLAPP-Kevin P. Murphy