CS229-03--决策树CART

决策树可以看作是一个基学习器,同样在这个例子中需要了解到相关机器学习中相关基本概念、模型评估和选择的过程中才能更好的继续下去,因为本人觉得ML在除了统计理论推导之外,实验的设计与验证也是非常重要

同样在CART的基础上,结合集成学习:Bagging、Boosting等可以更加优化决策树的性能进而推出更好的模型,但是最基本的东西还是来源于决策树的流程,本文将介绍决策树的基本流程以及代码实现

0x01 决策树(Decision tree)的基本流程

介绍

决策树是一种实现分治策略的层次数据结构,是一种有效的非参数方法,可以用于分类与回归

关于分治法,divide and conquer

  • Divide the problem into a number of subproblems that are smaller instances of the same problem
  • Conquer the subproblems by solving them recurisvely. If the problem sizes are small enough, however,just solve the subproblems in a straightforward manner.
  • Combine the solutions to the subpoblems into the solution for the original problem

(1)对于一个规模为N 的问题,若该问题可以容易地解决,则直接解决,否则执行下面的步骤。
(2)将该问题分解成若干个规模较小的子问题,这些子问题互相独立,并且原问题形式相同。
(3)递归recursively地解子问题。
(4)然后,将各子问题的解合并得到原问题的解

对于参数估计,我们定义整个输入空间上的模型,并使用所有的训练数据学习它的参数,然后对于任意的检验输入使用相同的模型和参数

对于非参数估计,我们将输入空间划分为利用欧几里得范数这样定义的距离度量的局部模型,并对每个输入使用由该区域的训练数据计算得到的对应的局部模型中,在非参数模型汇总给定一个输入,识别定义局部模型的局部数据的开销很大,需要计算从给定的输入到所有训练实例的距离。

决策树是一种用于监督学习的层次模型,局部区域通过少数几步递归分类确定,决策树又一些内部决策节点和终端树叶组成,每个决策节点decision node实现一个具有离散输出的测试函数,由此到达一定条件后形成一个树叶节点leaf node,形成最终的值并输出。

在决策树的实现当中,可以从单个输入变量的单变量树开始(考虑如何使用分类或者回归的方式构造这样的树),之后将这种树推广到所有输入的多变量树的内部节点

参考西瓜书中的算法为代码:

将决策树生成的整个过程分解,本质上是从父节点向下分解的过程,在其中回出现三种情况:

  1. 划分前,父节点全部属于一类;
  2. 划分中,父节点样本中特征结合为空集或者所有取值相同
  3. 划分后,有一个分支为空集,则与另外一个分支合并,将其类别标记为样本最多的类

在正常划分中,区分分类情况和回归情况(即离散值和连续值的划分方法)

image-20220221163207787

单变量分类(classfication)情况

在分类树 classfication tree中,划分的优劣用不纯度度量(impurity measure)分析:

如果对于所有分支,划分后选择相同分支的所有实例都属于相同的类,对于节点m,令N_m为到达节点m的训练实例\\数,N_m个实例中N_m^i都属于C_i类,则对于一个实例x到达节点m,属于C_i类的概率估计为\\ \bar p(C_i|X,m)=N_m^i/N_m\\ (def)节点m是纯的,如果对于所有的i,p_m^i为0或1,当到达节点m的所有实例都不属于C类时,p_m^i为0,\\而当所有节点到达m的所有实例都属于C_i类时候,为1\\

在不纯性度量划分的依据中,需要满足一下基本的性质且需要大于0

1. 对于任意p\in [0,1],\phi(1/2,1/2)>=\phi(p,1-p)\\ 2.\phi(0,1)=\phi(1,0)=0\\ 3. 在[0,1/2]上\phi(p,1-p)是递增的,当p在[1/2,1]上\phi(p,1-p)是递减的

例如常见的不纯性度量函数包括:

  1. 信息熵 Information Entropy
Gain=Gain(DataSet_{parent})-\Sigma N(sub)/N(Dataset_{parent})*Gain(SubDataSet)
  1. 增益率 Gain ratio: 降低分支过多带来的影响,相当于加了一层罚函数在分母

    Gain_{ratio}=Gain(DataSet_{parent})/IV(a)\\ IV(a)=-\Sigma|D^v|/|D|*log_2|D^v|/|D| \ ~ 是该属性的固有值
  2. 基尼指数 gini index

  3. 误分类函数

  4. 等等

单变量回归(regression)情况

回归树可以使用几乎与分类书完全相同的方法构造,唯一不同是适合分类的不纯性度量用适合回归的不纯性度量取代,相比较回归分析之前的差别可能是:

  1. 节点的分类不按照特征集中的类别直接分类,而是按照均值或者中值(noise大的时候用中值)

  2. 节点的不纯度量利用均方误差或者最大误差来实现,当误差小于设定threshold时生成树叶,否则继续分类

  3. threshold的设置中,可以使用复杂度函数来设置,值越小产生的树会越大导致过拟合分线越大,这里同样引入惩罚的概念

  4. image-20220222105230123

  5. 同样的,不利用均值或者中值,可以使用线性回归拟合选定树叶上的实例,但是这样计算开销会比较大

代码实现

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
from math import log
import operator
import numpy as np
class decisionTree():
def dataLoader(self,filename):
dataSet = [];
labels = []
i=1
fr = open(filename)
for line in fr.readlines(): # 逐行读取,滤除空格等
lineArr = line.strip().split(',')
if i==1:
labels=lineArr[1:(len(lineArr)-1)]
i=i+1
else:
dataSet.append(lineArr[1:])
return dataSet,labels


def createExampleDataset(self):
'''
返回示例数据,包括dataset、labels
'''
dataSet = [['白', '高', '男'],
['黑', '高', '男'],
['白', '高', '男'],
['黑', '低', '女'],
['黑', '低', '女'],
['黑', '高', '女'],
['白', '低', '女'],
['黑', '高', '女']]
labels = ['颜色', '身高'] # 两个特征
return dataSet, labels

def calcCrossEntropy(self, dataSet):
'''
计算数据集合中的数据熵
return crossEntropy
'''
classList = [example[-1] for example in dataSet]
unique,counts=np.unique(classList,return_counts=True)
crossEntropy=0
for count in counts:
crossEntropy+=-float(count/len(classList))*log(float(count/len(classList)),2)
return crossEntropy

def chooseBestFeature(self, dataSet):
'''
从不同特征中选择交叉熵差值最低的作为分离特征
return bestFeature下标
'''
bestInfoGain=-1
baseCrossEntropy=self.calcCrossEntropy(dataSet)
numFeature=len(dataSet[0])-1
for i in range(numFeature):
# 根据不同特征分开,并重新计算根据每个特征得到的交叉熵的和
featureList=set([example[i] for example in dataSet])
newCrossEntropy=0
for value in featureList:
subDataSet=self.splitDataSet(dataSet,i,value)

newCrossEntropy+=len(subDataSet)/len(dataSet)*self.calcCrossEntropy(subDataSet)

infoGain=baseCrossEntropy-newCrossEntropy
if infoGain>bestInfoGain:
bestInfoGain=infoGain
bestFeature=i
return bestFeature


def splitDataSet(self, dataSet, index,value):
'''
根据最佳的特征分离数据集,形成新的子集
'''

subDataSet=[]
for example in dataSet:
if example[index]==value:
temp=example[:index]
temp.extend(example[index+1:])
subDataSet.append(temp)
return subDataSet

def ifNodeFeatureIsSame(self,dataSet):
featureMat = [example[:(len(dataSet[0])-1)] for example in dataSet]
uniqueFeatureMat=np.unique(featureMat)
if len(uniqueFeatureMat) == 1:
return True
else:
return False

def majorityCount(self,classList):
className,counts=np.unique(np.array(classList))
return className[np.argmax(counts)]

def createTree(self,dataSet,labels):
# 生成结点node
classList=[example[-1] for example in dataSet]

# 情况1:当前分支中全部都为同一个属性不需要分类
# 情况2:当前分支为1集合不需要分类
# 情况3:最优化划分

if classList.count(classList[0])==len(classList):
return classList[0]

if len(labels)==0 or self.ifNodeFeatureIsSame(dataSet):
return self.majorityCount(classList)

bestFeature=self.chooseBestFeature(dataSet)
bestFeatureLabel=labels[bestFeature]
myTree={bestFeatureLabel:{}}

#删除区分的属性
del(labels[bestFeature])

featureValues=[example[bestFeature] for example in dataSet]
uniqueValues=set(featureValues)
for value in uniqueValues:
sublabels=labels[:]
myTree[bestFeatureLabel][value]= \
self.createTree(self.splitDataSet(dataSet, bestFeature, value), sublabels)
return myTree




if __name__=='__main__':
newTree=decisionTree()
filename='datasets/watermelon.txt'
dataSet,labels=newTree.dataLoader(filename)
#或者直接根据例子来
#dataSet,labels=newTree.createExampleDataset()
print(newTree.createTree(dataSet,labels))

txt文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
编号,色泽,根蒂,敲声,纹理,脐部,触感,好瓜
1,青绿,蜷缩,浊响,清晰,凹陷,硬滑,是
2,乌黑,蜷缩,沉闷,清晰,凹陷,硬滑,是
3,乌黑,蜷缩,浊响,清晰,凹陷,硬滑,是
4,青绿,蜷缩,沉闷,清晰,凹陷,硬滑,是
5,浅白,蜷缩,浊响,清晰,凹陷,硬滑,是
6,青绿,稍蜷,浊响,清晰,稍凹,软粘,是
7,乌黑,稍蜷,浊响,稍糊,稍凹,软粘,是
8,乌黑,稍蜷,浊响,清晰,稍凹,硬滑,是
9,乌黑,稍蜷,沉闷,稍糊,稍凹,硬滑,否
10,青绿,硬挺,清脆,清晰,平坦,软粘,否
11,浅白,硬挺,清脆,模糊,平坦,硬滑,否
12,浅白,蜷缩,浊响,模糊,平坦,软粘,否
13,青绿,稍蜷,浊响,稍糊,凹陷,硬滑,否
14,浅白,稍蜷,沉闷,稍糊,凹陷,硬滑,否
15,乌黑,稍蜷,浊响,清晰,稍凹,软粘,否
16,浅白,蜷缩,浊响,模糊,平坦,硬滑,否
17,青绿,蜷缩,沉闷,稍糊,稍凹,硬滑,否

0x02 剪枝处理

先剪枝(prepruning):基于过少实例决策树导致较大方差,进而导致较大的泛化误差,eg:在到达一个节点的训练实例树小于训练集的某个百分比(5%),则无论是否不纯或者有错误都不近一步分裂

后剪枝(postpruning):回溯其他的选择(留个坑,回溯法还没看),我们让树完全增长知道所有的树叶都是纯的并具有零训练误差,然后找出导致过分拟合的子树并剪掉。eg:我们从最初的被标记的数据集中保留一个剪枝集,在训练阶段不适用,对于每颗子树,我们用一个被该子树覆盖的训练实例标记的树叶节点替代它,如果该树叶在剪枝集合上的性能不必该子树茶,则剪掉该子树并保留树叶节点可因为子树的附加的复杂性是不必要的

0x03 连续与缺失值处理

暂时不重要

0x04 额外的东西

  • 集成学习( ensemble learning):利用弱学习器组合来形成一个强的学习器,包括bagging、stacking、boosting
  • 由bagging得到的随机森林(random forest)、由boosting得到的GBDT(gradient boosting decision tree)并XGBOOST和lightGBM

CS229-03--决策树CART
https://blog.tjdata.site/posts/a32aa49a.html
作者
chenxia
发布于
2022年2月20日
许可协议