Decision Tree

决策树分类(ID3,C4.5,CART)

先导概念

决策树

决策树是一种基本的分类与回归方法,它可以看作if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。

将决策树转换成if-then规则的过程如下:

由决策树的根节点到叶节点的每一条路径构建一条规则;
路径内部结点的特征对应规则的条件;
叶节点的类对应规则的结论.

决策树的路径具有一个重要的性质:互斥且完备,即每一个样本均被且只能被一条路径所覆盖。

决策树学习算法主要由三部分构成:

  • 特征选择
  • 决策树生成
  • 决策树的剪枝

主要参考和整理自知乎黄耀鹏的回答

决策树模型 ID3/C4.5/CART算法比较

基础概念

信息熵(entropy)

信息熵用来表示所有信息量的期望。期望是试验中每次可能结果的概率乘以其对应结果的总和。

所以信息量的熵可以表示为:(这里的X是一个离散型随机变量)

对于 0-1 分布问题,如果一种情况发生的概率为$P(x)$,那么另一个情况发生的概率为$1-P(x)$。所以对于0-1分布问题,计算熵的公式可以简化如下:

条件熵(conditional entropy)

参考自

设有随机变量(X,Y),其联合概率分布为

条件熵$H(Y|X)$表示在已知随机变量X的条件下随机变量Y的不确定性。定义为:

条件熵,是指在给定某个数(某个变量为某个值)的情况下,另一个变量的熵是多少,变量的不确定性是多少.

假设随机变量Y = {嫁, 不嫁},随机变量X(长相)= {帅,不帅}

当已知帅的条件下,满足条件的有8个数据了,这八个数据中,不嫁的个数为5个,占5/8;嫁的个数为3个,占3/8.那么此时

同理我们可以计算出已知不帅的条件下对应部分的数值,代入条件熵计算公式就可以得到结果。

其实条件熵意思是按一个新的变量的每个值对原变量进行分类,比如上面这个题把嫁与不嫁按帅,不帅分成了俩类。
然后在每一个小类里面,都计算一个小熵,然后每一个小熵乘以各个类别的概率,然后求和。
我们用另一个变量对原变量分类后,原变量的不确定性就会减小了,因为新增了X的信息,不确定程度减少了多少就是信息的增益。

互信息(mutual information)

互信息和刚刚写到的两个熵的定义关联密切。

信息增益(information gain)

信息增益表示的是:得知特征X的信息而使得类Y的信息的不确定性减少的程度。

信息增益依赖于特征,不同的特征往往具有不同的信息增益,信息增益大的特征具有更强的分类能力。

特征A对训练数据集D的信息增益 ,定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,即

信息增益与互信息的区别联系

一、信息增益指的是经验熵和经验条件熵的差值,经验熵和经验条件熵是通过样本进行极大似然估计得出来的,是一个估计值的差。互信息是对总体的信息量的评价,不是估计值。

二、Gain是各元素之间的人为定义的关系信息,I只是两两之间客观关系信息,当然I也能够扩展,通过扩展可以计算得到Gain,不论是I还是Gain他们都是关系信息。

信息增益是互信息的无偏估计,所以在决策树的训练过程中, 两者是等价的。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。说“互信息”的时候,两个随机变量的地位是相同的;说“信息增益”的时候,是把一个变量看成减小另一个变量不确定度的手段。但其实二者的数值是相等的。

决策树的特征选择

信息增益(information gain)

根据信息增益准则进行特征选择的方法是:对训练数据集D,按照数据的每个属性进行划分,最后计算它们划分后的信息增益,最后再根据三种划分的信息增益的大小来确定采用哪个属性进行划分。

假设训练数据集为D,样本数量为$|D|$,有k个类别$C_k$(也就是结果值y有k种), $|C_k|$为类别$C_k$的样本个数。某一特征A有n个不同的取值$a_1,a_2,…,a_n$。根据特征A的取值可以将数据集D划分为n个子集$D_1,D_2,…,D_n,|D_i|$为$D_i$的样本个数。并记子集$D_i$中属于类$C_k$的样本的集合为$D_{ik}$,$|D_{ik}|$为$D_{ik}$的样本个数

那么信息增益的计算步骤如下:

(1) 计算数据集D的经验熵H(D)

(2) 计算特征A对数据集的经验条件熵H(D|A)

(3) 计算信息增益

信息增益比(information gain ratio)

以信息增益作为特征选择准则,会存在偏向于选择取值较多的特征的问题。可以采用信息增益比对这一问题进行校正。

以信息增益作为特征选择准则,会存在偏向于选择取值较多的特征的问题。可以采用信息增益比对这一问题进行校正。

其中,$H_A(D) = -\sum\limits_{i=1}^{n}\frac{|D_i|}{|D|}log\frac{|D_i|}{|D|}$

基尼指数

基尼值反映了从数据集中随机抽取两个样本,其类别标记不一致的概率,因此基尼值越小,则数据集纯度越高。

分类问题中,假设有K个类别,样本点属于第k类的概率为$p_k$,则概率分布的基尼指数定义为

对属性a进行划分,则属性a的基尼指数定义为:

三种决策树算法的区别

ID3算法

ID3决策树可以有多个分支,但是不能处理特征值为连续的情况。决策树是一种贪心算法,每次选取的分割数据的特征都是当前的最佳选择,并不关心是否达到最优。

从根节点开始,对结点计算所有可能特征的信息增益,选择信息增益最大的特征作为结点的特征,并由该特征的不同取值构建子节点;
对子节点递归地调用以上方法,构建决策树;
直到所有特征的信息增益均很小或者没有特征可选时为止。

ID3的缺点在于:1、没有提出对连续值的处理。2、使用信息增益作为标准,容易偏向于以取值较多的数值作为分类标准。3、不能作为回归树

C4.5算法

C4.5算法与ID3算法的区别主要在于它在生产决策树的过程中,使用信息增益比来进行特征选择。同时C4.5支持了对连续数值的划分,但是,对连续属性值需要扫描排序,会使C4.5性能下降。

具体做法如下:

把需要处理的样本(对应根节点)或样本子集(对应子树)按照连续变量的大小从小到大进行排序.假设该属性对应的不同的属性值一共有N个,那么总共有N−1个可能的候选分割阈值点,每个候选的分割阈值点的值为上述排序后的属性值中两两前后连续元素的中点,根据这个分割点把原来连续的属性分成bool属性.实际上可以不用检查所有N−1个分割点, 切分点只能出现在目标分类不同的相邻实例之间。

CART算法

分类与回归树(classification and regression tree,CART)与C4.5算法一样,由ID3算法演化而来,改进的地方在于支持了回归问题。CART假设决策树是一个二叉树,(ID3和C4.5是可以为多叉树的,譬如一些属性有多个离散可能属性值就是多叉的)它通过递归地二分每个特征,将特征空间划分为有限个单元,并在这些单元上确定预测的概率分布。还有CART的特征划分使用Gini指数。

CART算法中,对于回归树,采用的是平方误差最小化准则;对于分类树,采用基尼指数最小化准则。

平均误差最小化

假设已将输入空间划分为M个单元$R_1,R_2,…,R_M$,并且在每个单元$R_m$上有一个固定的输出值$c_m$,于是回归树可以表示为:

可以用平方误差$\sum\limits_{x_{i}\in{R_m}}(y_i - f(x_i))^2$来表示回归树对于训练数据的预测误差。

连续值与数值缺失

连续值的处理

在lightGBM中(是一个实现GBDT算法的框架),我们介绍了,它通过直方图算法将连续变量映射成一个个的bins,然后将bins看做离散变量再逐一计算那个分裂节点最优。而一般的决策树处理连续变量是只将连续变量做离散二值化。给定样本集合D和连续属性a,如果a的取值有n个不同的取值,分别为${a^1,a^2,…,a^n}$,那么基于划分点t可以将数据集D划分为$D_{t}^{-}, D_{t}^{+}$,他们分别包含属性a上取值不大于t的样本和大于t的样本。因此对连续属性a我们有n-1个候选划分节点.

缺失值的处理

填充或者删除

如果缺省的属性是连续的数值,并且每个样本之间存在一定的关系(时间序列):可以通过上一个时间的数据或者上一个数据和下一个数据的平均值进行填充,这种做法可以保证时间序列的连续性。或者使用平均数、中位数等进行填充

如果缺省的属性是连续的数值并且和其他的特征具有一定的关系,可以通过其他属性近似推导出缺失数值。

如果缺省数据是离散属性,并且数量较多,可以选择将缺省的数据单独分为一类进行训练。

如果包含缺省数据的样本点较少,可以直接删除缺失数据。如果大多数样本点均不包含此缺失数据,可以考虑放弃这一特征。

用不同的权重进行填充

给定训练集D和属性a,令$\tilde{D}$表示D中在属性a上没有缺失值的样本子集。$\rho$表示无缺失值样本所占的比例,$\tilde{p_k}$表示无缺失值样本中第k类所占的比例,$\tilde{r_v}$表示无缺失值样本中在属性a上取值$a^{v}$的样本所占的比例。

假定我们为每个样本x赋予一个权重$w_x$,并定义

信息增益的计算方法会变成:

若样本x在划分属性a上的取值已知,则将x划入与其取值对应的子节点,且样本权值在子节点中保持为$w_x$。若样本x在划分属性a上的取值未知,则将x同时划入划入所有子节点,并且样本权值在与属性值$a^v$对应的子节点中调整为$\tilde{r_v} \cdot w_x$。

翻译一下:对于缺测的数据,分别用该属性的其他数值进行填充。并且给予每一个填充出来的样本不同的权重,权重根据每一个种类的样本数量进行计算(例如:样本颜色未知,已知的颜色分类有红、黄、蓝,三种分类样本数量分别为2、3、5,则填充出来的样本一共有三个,权重分别为2/10,3/10,5/10)。

xgboost中的方法

在xgboost里,在每个结点上都会将对应变量是缺失值的数据往左右分支各导流一次,然后计算两种导流方案对Objective的影响,最后认为对Objective降低更明显的方向(左或者右)就是缺失数据应该流向的方向,在预测时在这个结点上将同样变量有缺失值的数据都导向训练出来的方向。
ss
例如,某个结点上的判断条件是 A>0 ,有些数据是A<=0,有些是A>0,有些数据的A是缺失值。那么算法首先忽略带缺失值的数据,像正常情况下一样将前两种数据分别计算并导流到左子树与右子树,然后

将带缺失值的数据导向左子树,计算出这时候模型的Objective_L;
接着将带缺失值的数据导向右子树,计算出这时候模型的Objective_R;
最后比较Objective_L和Objective_R。

假设Objective_L更小,那么在预测时所有变量A是缺失值的数据在这个结点上都会被导向左边,当作A<=0处理。当然如果训练中没有数据缺失,预测时出现了数据缺失,那么无法根据上面的方法判断流向,默认被分类到右子树。

决策树生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
def uniquecounts(rows):
results = {}
for row in rows:
r = row[-1]
if r not in results:
results[r] = 0
results[r] += 1
return results

def entropy(rows):
from math import log
log2 = lambda x:log(x)/log(2)
results = uniquecounts(rows)
# 开始计算熵的值
ent = 0.0
for r in results.keys():
p = float(results[r]) / len(rows)
ent -= p * log2(p)
return ent
#定义节点的属性
class decisionnode:
def __init__(self,col = -1,value = None, results = None, tb = None,fb = None):
self.col = col # col是待检验的判断条件所对应的列索引值
self.value = value # value对应于为了使结果为True,当前列必须匹配的值
self.results = results #保存的是针对当前分支的结果,它是一个字典
self.tb = tb ## desision node,对应于结果为true时,树上相对于当前节点的子树上的节点
self.fb = fb ## desision node,对应于结果为true时,树上相对于当前节点的子树上的节点



# 基尼不纯度
def giniimpurity(rows):
total = len(rows)
counts = uniquecounts(rows)
imp = 0
for k1 in counts.keys():
p1 = float(counts[k1])/total
imp+= p1*(1-p1)
return imp

#在某一列上对数据集进行拆分。可应用于数值型或因子型变量
def divideset(rows,column,value):
#定义一个函数,判断当前数据行属于第一组还是第二组
split_function = None
if isinstance(value,int) or isinstance(value,float):
split_function = lambda row:row[column] >= value
else:
split_function = lambda row:row[column]==value
# 将数据集拆分成两个集合,并返回
set1 = [row for row in rows if split_function(row)]
set2 = [row for row in rows if not split_function(row)]
return(set1,set2)

# 以递归方式构造树

def buildtree(rows,scoref = entropy):
if len(rows)==0 : return decisionnode()
current_score = scoref(rows)

# 定义一些变量以记录最佳拆分条件
best_gain = 0.0
best_criteria = None
best_sets = None

column_count = len(rows[0]) - 1
for col in range(0,column_count):
#在当前列中生成一个由不同值构成的序列
column_values = {}
for row in rows:
column_values[row[col]] = 1 # 初始化
#根据这一列中的每个值,尝试对数据集进行拆分
for value in column_values.keys():
(set1,set2) = divideset(rows,col,value)

# 信息增益
p = float(len(set1))/len(rows)
gain = current_score - p*scoref(set1) - (1-p)*scoref(set2)
if gain>best_gain and len(set1)>0 and len(set2)>0:
best_gain = gain
best_criteria = (col,value)
best_sets = (set1,set2)

#创建子分支
if best_gain>0:
trueBranch = buildtree(best_sets[0]) #递归调用
falseBranch = buildtree(best_sets[1])
return decisionnode(col = best_criteria[0],value = best_criteria[1],
tb = trueBranch,fb = falseBranch)
else:
return decisionnode(results = uniquecounts(rows))

# 决策树的显示
def printtree(tree,indent = '*'):
# 是否是叶节点
if tree.results!=None:
print(str(tree.results))
else:
# 打印判断条件
print(str(tree.col)+":"+str(tree.value)+"? ")
#打印分支
print(indent+"T->")
printtree(tree.tb,indent+"*")
print(indent+"F->")
printtree(tree.fb,indent+"*")


# 对新的观测数据进行分类


def classify(observation,tree):
if tree.results!= None:
return tree.results
else:
v = observation[tree.col]
branch = None
if isinstance(v,int) or isinstance(v,float):
if v>= tree.value: branch = tree.tb
else: branch = tree.fb
else:
if v==tree.value : branch = tree.tb
else: branch = tree.fb
return classify(observation,branch)

# test


my_data=[['slashdot','USA','yes',18,'None'],
['google','France','yes',23,'Premium'],
['digg','USA','yes',24,'Basic'],
['kiwitobes','France','yes',23,'Basic'],
['google','UK','no',21,'Premium'],
['(direct)','New Zealand','no',12,'None'],
['(direct)','UK','no',21,'Basic'],
['google','USA','no',24,'Premium'],
['slashdot','France','yes',19,'None'],
['digg','USA','no',18,'None'],
['google','UK','no',18,'None'],
['kiwitobes','UK','no',19,'None'],
['digg','New Zealand','yes',12,'Basic'],
['slashdot','UK','no',21,'None'],
['google','UK','yes',18,'Basic'],
['kiwitobes','France','yes',19,'Basic']]


tree = buildtree(my_data)
printtree(tree = tree)
classify(['(direct)','USA','yes',5],tree)

决策树的剪枝

如果对训练集建立完整的决策树,会使得模型过于针对训练数据,拟合了大部分的噪声,即出现过度拟合的现象。为了避免这个问题,有两种剪枝策略:预剪枝和后剪枝。

预剪枝是指在决策树生成过程中,对每个结点在划分前先进行估计,当熵减少的数量小于某一个阈值时,则停止划分并将当前结点标记为叶节点;后剪枝则是先从训练集中生成一颗完整的树,然后自底向上对非叶节点进行考察,若该节点对应的子树替换为叶节点能够提升泛化能力,则进行剪枝将该子树替换为叶节点,否则不剪枝。

很明显,预剪枝技术存在一个潜在的问题:有可能某一次分支的创建不会令熵有太大的下降,但是随后的子分支却有可能会使得熵大幅降低。这种方法抑制了很多分支的展开,这降低过拟合的同时还减少了训练时间,但是却存在欠拟合的风险;预剪枝基于“贪心”策略,往往可以达到局部最优解却不能达到全局最优解,也就是说预剪枝生成的决策树不一定是最佳的决策树。XGBoost和lightGBM使用的树就是预剪枝的CART决策树,这能保证他们的训练速度较快。
在一些决策树的库函数中,可以通过设置$max_depth$来控制决策树深度。

min_samples_split:节点在分裂之前必须具有的最小样本数。也就是,如果该节点上的样本数量小于参数设置的数目时,不管怎样,这个节点也不再分裂。

min_samples_leaf:叶节点必须拥有的最少样本数。如果分裂一个节点生成一些叶子,而某个叶子上的样本数量少于参数设置的值时,将不将这些样本单独作为一个叶子。

min_weight_fraction_leaf:和上面一个参数差不多,但表示为加权实例总数的一小部分。

max_leaf_nodes:叶子节点的最大数量。

max_features:对每一个节点评估是否分裂所需要的最少特征数量。

1
2
3
4
5
6
7
from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
iris = load_iris()
X = iris.data[:, 2:] # petal length and width
y = iris.target
tree_clf = DecisionTreeClassifier(max_depth=2)
tree_clf.fit(X, y)

后剪枝技术通常比预剪枝保留了更多的分支,它是自底向上的剪枝,因此它的欠拟合风险较小,泛化能力往往优于预剪枝,然而因为总是要完全生长一棵树,这就要花费很多时间训练了,数据集规模大、维度高时并不适用实际应用。

决策树的剪枝通过极小化决策树整体的损失函数来实现。设决策树T的叶子节点个数为$|T|$,t是树T的叶子节点,改叶节点有$N_t$个样本点,其中k类的样本点有$N_{tk}$个,$H_t(T)$为叶节点t上的经验熵,$\alpha$为正则化系数,则包含剪枝的决策树的损失函数可以定义为:

其中经验熵为:

具体的算法:

1.计算每个节点的经验熵:

2.递归地从树的叶节点向上回缩,如果将某一个父节点的所有叶节点合并,能够使得其损失函数减少,则进行剪枝,将父节点变成新的叶节点;

3.返回2,直到不能继续合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#决策树的剪枝
def prune(tree,mingain):
# 如果分支不是叶节点,则对其进行剪枝
if tree.tb.results == None:
prune(tree.tb,mingain)
if tree.fb.results == None:
prune(tree.fb,mingain)
# 如果两个子分支都是叶节点,判断是否能够合并
if tree.tb.results !=None and tree.fb.results !=None:
#构造合并后的数据集
tb,fb = [],[]
for v,c in tree.tb.results.items():
tb+=[[v]]*c
for v,c in tree.fb.results.items():
fb+=[[v]]*c
#检查熵的减少量
delta = entropy(tb+fb)-(entropy(tb)+entropy(fb)/2)
if delta < mingain:
# 合并分支
tree.tb,tree.fb = None,None
tree.results = uniquecounts(tb+fb)
# test
tree = buildtree(my_data,scoref = giniimpurity)
prune(tree,0.1)
printtree(tree)

这边解释一下为什么最后delta的计算会变成这样,然后是根据delta < mingain觉得是否合并。

delta = entropy(tb+fb)-(entropy(tb)+entropy(fb)/2)

因为在下面这个公式中,你每次把两个叶子节点缩成一个就相当于,把|T|减少了1,$\alpha$就是这边的mingain参数,其实就相当于比较代价函数前后两部分增加减少的量判断代价函数的变化。

阀值设置为0.1时候的结果和不进行剪枝时候一样,这边*号代表二叉树层数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
0:google?
*T->
3:21?
**T->
{'Premium': 3}
**F->
2:no?
***T->
{'None': 1}
***F->
{'Basic': 1}
*F->
0:slashdot?
**T->
{'None': 3}
**F->
2:yes?
***T->
{'Basic': 4}
***F->
3:21?
****T->
{'Basic': 1}
****F->
{'None': 3}

阀值设置为0.9之后,剪枝了

1
2
3
4
5
6
7
8
9
10
11
12
*T->
3:21?
**T->
{'Premium': 3}
**F->
2:no?
***T->
{'None': 1}
***F->
{'Basic': 1}
*F->
{'None': 6, 'Basic': 5}

这时候构建出来的叶节点中可能就包含多类样本,决策树为了让每个叶节点都代表一类,通过投票机制选取该叶结点下样本出现次数最多的那一类作为叶节点代表的类。这边是强行提高阀值展示了剪枝结果,造成了欠拟合。