decision

机器学习之决策树（DecisionTree）

决策树（DecisionTree）

1.决策树⼜称为判定树，是数据挖掘中的⼀种重要的分类与回归⽅法，它是⼀种以树结构(包括⼆叉树和多叉树)形式来表达的预测分析模

型

2.是⼀种有监督的算法

3.决策树有两种，⼀种是分类树（输⼊是离散的），⼀种是回归树（输⼊是连续的）

决策树由节点和分⽀组成：（详情参考数据结构书本）

1.节点分为三种：根节点，内部节点，叶节点

2.分⽀：⽤于连接各个节点

决策树分为以下结构：

每个内部节点对应于某个属性上的测试(test)或者说是⼤类

每个分⽀对应于该测试的⼀种可能结果

每个叶节点对应于⼀个预测结果

学习过程：通过对训练样本的分析来确定划分属性，即内部节点所对应的属性

预测过程：将测试⽰例从根节点开始沿着划分属性所构成的判定测试序列向下⾏进，直到到达叶节点

决策树学习的⽬的是为了产⽣⼀棵泛化能⼒强的决策树，决策树如下所⽰

也就是⽤多个判定语句进⾏判定，很容易转化成if-then语句：

由决策树的根节点到叶节点的每⼀条路径构建⼀条规则

路径上内部节点的特征对应着规则的条件，⽽叶节点的类标签对应着规则的结论

决策树的⽣成过程中⼀定要遵循互斥且完备这⼀规则（互斥且完备：每⼀个实例都被有且只有⼀条路路径或⼀条规则所覆盖）

决策树的构建

策略：⾃上⽽下，分⽽治之

⾃根节点⾄叶节点的递归过程中，在每个中间节点寻找⼀个划分属性

1.构建根节点，并且所有训练数据都放在根节点，选择⼀个最优特征，按着这⼀特征将训练数据集分割成⼦集，进⼊⼦节点

2.所有⼦集按内部节点的属性然后递归的进⾏分割

3.如果这些⼦集已经能够被基本正确分类，那么构建叶⼦结点，并将这些⼦集分到对应的叶节点上去

4.每个⼦集都被分到叶⼦节点上，即都拥有了明确的类别，则决策树构建完成

停⽌条件

1.⽆需划分：当前节点包含的样本全属于同⼀类别

2.⽆法划分：当前属性集为空，或是所有样本在所有属性上取值相同

3.不能划分：当前节点包含的样本集合为空

如何选择最优的划分属性是决策树算法的核⼼，也就是先划分哪⼀个属性

特征（属性）选择

1.特征选择是决定⽤哪⼀个特征来划分空间

1.我们希望决策树的内部节点所包含的样本尽可能属于同⼀类别，即节点的纯度越来越⾼，可以⾼效的从根节点到达叶节

点，得到决策结果

2.信息熵：是度量样本纯度的最常⽤的指标

若P=0，则P㏒₂P=0

若P=1，则P㏒₂P=0

ENT(D)的最⼩值为0，最⼤值为㏒₂|y|

ENT(D)的值越⼩，则D的纯度越⾼

3.信息增益：信息增益直接以信息熵为基础，计算当前划分对信息熵所造成的变化

1.离散属性a的取值：{a₁,a₂,a₃,…,av},Dv：D在a上取值为av的样本集合

2.以属性a对数据集D进⾏划分所获得的信息增益为：

信息增益越⼤，则意味着使⽤属性a来进⾏划分所获得的纯度提升越⼤

信息增益越⼤，则意味着使⽤属性a来进⾏划分所获得的纯度提升越⼤

以信息增益为基础进⾏分类的著名决策树算法有ID3决策树算法

2.特征选择表⽰从众多的特征中选择⼀个特征作为当前节点分裂的标准

3.如何选择特征有不同的量化评估⽅法，从⽽衍⽣出不同的决策树

==算法改进（C4.5算法）：==以信息增益为基础进⾏分类的决策树算法有缺陷，表现为：对可取值数⽬较多的属性有所偏好，所以就

引出了增益率这⼀概念，可以在信息增益的基础上将数⽬对属性的影响进⾏消除，使结果更加合理。

基尼指数（CART算法）：此算法抛弃了信息熵，⽽是采⽤基尼指数来进⾏运算

决策树的⼀般构建步骤（按照信息熵）：

⾸先要按照此公式计算出根节点的信息熵（根节点的分类其实就是以最终的判别结果来进⾏的分类）

以鸢尾花的分类为例（鸢尾花有四个特征，分别为花萼长度、花萼宽度、花瓣长度、花瓣宽度）：

为了⽅便理解，此处鸢尾花的每个特征都假设为只有三个值，分别为长，中，短

==|y|：==表⽰区分成的种类数，判别鸢尾花的时候只有三种标签（iris-tosa或iris-versicolour或iris-virginica），所以鸢尾花分类中

的|y|=3

==P:==此变量的k也是以鸢尾花的类别进⾏分类的，也就是每个种类占总数集的⽐重，⽐如设iris-tosa的⽐重为P，iris-versicolour

的⽐重为P，iris-virginica的⽐重为P，且P+P+P=1

所以由此可以计算出根节点的信息熵ENT(D)（ENT(D)的值越⼩，则D的纯度越⾼），判断根节点是否纯，如果不纯需要进⾏下⾯的划分。

然后进⾏根节点的选取，也就是以哪⼀个特征作为根节点来进⾏第⼀次的种类划分，依旧是求信息熵，不过此时求的信息熵是以各个特征为

准来分别进⾏划分，假设先求鸢尾花的花萼长度的信息熵，步骤如下：

花萼长度分别有长花萼(D)、中花萼(D)、短花萼(D)

先求Pk，找出长花萼中所对应的各个种类（iris-tosa或iris-versicolour或iris-virginica）占长花萼总数量的⽐重即为每个种类所对应的

P，P+P+P=1，但此时的y依旧是根据标签来判定的，也就是说要代⼊的数据P是每个

种类中各个标签所占的⽐重，⽽不是本种类占总数⽬的⽐重

中花萼和短花萼的信息熵的求法与此相同

由此可以求出各个花萼长度的信息熵D、D、D

也是就是说要计算每⼀个特征的各个属性的信息熵

然后再以此公式求得此特征的信息增益：

公式的前半部分：Ent(D)是根节点的信息熵，也就是上⾯第⼀步所求得的

公式的后半部分：V表⽰特征中属性的个数，上述例⼦中V=3，⽽分母中的|D|则表⽰特征中参与运算的数据的条数，|D|则表⽰D属性的

条数，Ent(D)表⽰D的信息熵，上⾯步骤已经求得，直接计算即可

然后对每个特征都进⾏上述运算，可以针对每个特征分别得出⼀个信息增益，假设所得信息增益为（信息增益越⼤证明分类越纯）：

Gain(D,花萼长度)、Gain(D,花萼宽度)、Gain(D,花瓣长度)、Gain(D,花瓣宽度)，假设其中的花瓣长度所得信息增益最⼤，那么，则以花瓣

长度代替前⾯提到的根节点作为新的根节来点进⾏第⼀次划分所得的枝⼲分别为

k1

23123

123

(长花萼iris-tosa)(长花萼iris-versicolour)(长花萼iris-virginica)k

123

v

v

v

v

注意：当下⾯继续划分的时候，则进⼊递归，此时注意排除掉花瓣长度这⼀特征，因为计算时要使决策树保持互斥的特性，并且特别需要注

意的是，假设在长花瓣的分⽀下继续进⾏分类的时候，此时参与分类的只有D{1、4、7、10……}数据⾏，其他⾏不参与此次计算

参与计算的特征集合为花萼长度、花萼宽度、花瓣宽度三个特征，此时要基于D按照上⾯所述⽅法计算各特征的信息增益，若有多个特征的

信息增益同样⼤，则任取⼀个特征来进⾏划分

最终可得到⼀个完整的决策树

值得⼀提的是，假设分类的时候特征数据不是长、中、短之类的简单条件，⽽是全部是数，此时决策树中的中间节点则可以按照临界值来划

分，也就是以⼀个值为阈值，特征中的值若⼤于它，则属于某⼀类，若⼩于它，则属于另⼀类，并且可以制定多个阈值来多次划分。

决策树剪枝

在对决策树泛化性能的影响⽅⾯来看，相对于⽤不同的⽅法构建决策树，剪枝⽅法和程度对决策树泛化性能的影响更为显著

剪枝是防⽌决策树过拟合（过拟合：测试集结果完全贴合训练集，也就是测试集和训练集完全⼀样）的⼿段

决策树剪枝对决策树性能提升⾮常⼤，尤其是数据带噪声的时候

剪枝的基本策略为：

预剪枝：提前终⽌某些分⽀的⽣长

后剪枝：⽣成⼀棵完全树，再回头剪枝

剪枝的判断依据为剪枝之前的精度和剪枝之后的精度⽐较，如果精度下降，则此枝不剪；否则减掉此枝，需要将中间节点⼀个⼀个的进⾏⽐

较

预剪枝和后剪枝的对⽐：

1

1

1.时间开销：

1.预剪枝：训练时间开销降低（因为其在构建的时候枝还未⽣长就已经剪掉了，所以花费时间少⼀点），测试时间开销降低（其剪

枝步骤为：先求出最每⼀个特征的信息增益率，挑选出信息增益率最⼤的特征作为根节点，然后以此根节点为基础按照训练集中

的各个标签的⽐重直接进⾏分类，然后将测试集代⼊直接进⾏判断测试集的正确概率并记录，然后也是最关键的地⽅，也就是判

断是否要进⾏每⼀个枝的分类，根据其他特征的信息增益率进⾏分类，计算分类后的正确率并与未分类之前的正确率进⾏⽐较，

换句话说也就是判断，观察正确率和剪枝之前相⽐其是否有提升，若有提升，则进⾏划分；否则禁⽌划分）

2.后剪枝：训练时间开销增加（因为后剪枝是先构建⼀棵树，然后再进⾏剪枝，所以花费时间更多⼀点），测试时间开销降低（其

剪枝步骤为：将某⼀个中间节点先替换为叶节点，判断替换后的精度是否有提升，若有提升，则直将此节点下⾯的分类直接删

除，也就是这个分类下⾯不再进⾏剪枝了（只要是符合条件都认为是某⼀个标签），此节点直接替换为叶节点；否则不替换）

2.过拟合和⽋拟合风险

1.预剪枝：过拟合风险降低，⽋拟合风险增加

2.后剪枝：过拟合风险降低，⽋拟合风险基本不变

3.泛化性能

1.后剪枝优于预剪枝

连续值与缺失值处理

1.连续值处理：

在很多情况下处理的是连续的数据，由于连续属性的可取值数⽬不再有限，因此不能直接根据连续属性的可取值来对节点进⾏划分，

⽽处理这种数据的办法为：连续属性离散化：基本思路为可以在这个连续值上⾯区分⼏个区间，按照区间的不同来对数据进⾏划分，

常⽤⽅法为⼆分法

2.缺失值处理：

在很多情况下会遇到带有缺失值的数据，但是如果对带有缺失值的数据弃之不⽤的话，则会对数据带来极⼤的浪费，所以需要对数据

的划分进⾏处理，从如何进⾏划分属性的选择和若如何对样本属性值有缺失的数据划分属性。解决的基本思路为：样本赋权，权重划

分

3.在划分进⾏计算的时候直接以未缺失的样本来进⾏计算即可，⽐如计算信息熵，但是注意在计算信息增益率的时候是有权重的。假如

在计算的时候⼀共有19条样本数据，但是只有15条样本数据是完整的，所以此时在计算信息增益率的时候需要给赋⼀个15/19的权

重

决策树的本质

每个属性视为坐标空间中的⼀个坐标轴，假设有d个属性描述的样本，就对应了d维空间中的⼀个数据点，⽽决策树中的对样本分类，实

质上就是在这个坐标空间中寻找不同类样本中的分类边界

决策树的分类边界特点是轴平⾏，也就是它的分类边界由若⼲个与坐标轴平⾏的分段组成

当学习任务对应的分类边界很复杂时，需要很多段划分才能获得较好近似，划分出来的分类⾯可能在图像上呈梯形等图形，当⽆限精分

的时候，梯形等图形就可能会呈现出⼀条柔滑的曲线

注意，决策树可能不仅仅是⼀棵决策树，还可以在决策树的节点中嵌⼊神经⽹络模型或者其他⾮线性模型，嵌⼊了其他模型的决策树叫

混合决策树

决策树由于其算法本⾝的限制，算法受内存⼤⼩限制，不适合进⾏⼤数据集的训练，只能进⾏中⼩样本的训练

决策树使⽤的⽅法

1.可以使⽤中的模型直接计算，使⽤⽅法和⽀持向量机套⽤模型的⽅法类似，在测试鸢尾花数据集的时候，其错误率要⽐

⽀持向量机错误率⾼

"""

-*-coding:utf-8-*-

@Time:2021/8/58:57

@Author:wcc

@FileName:

@Software:PyCharm

@Blog：/qq_41575517?spm=1000.2115.3001.5343

@Blog：/qq_41575517?spm=1000.2115.3001.5343

"""

portDecisionTreeClassifier

importnumpyasnp

asplt

importpandasaspd

classIris:

def__init__(lf,file_name,data_t,labels_t,normal_data_t,data_division):

me=file_name

t=data_t

Mat=labels_t

DataSet=normal_data_t

vision=data_division

#数据预处理

defiris_processData(lf):

fr=open(me)

numOfLines=len(nes())

#此处⼀定记得要把标签排除在外

dataMat=((numOfLines,4))

#标签单独成⼀列

labelsMat=[]

(0,0)

index=0

nes():

line=()

listLine=(',')

dataMat[index,:]=listLine[0:4]

iflistLine[-1]=='Iris-tosa':

(1)

iflistLine[-1]=='Iris-versicolor':

(2)

iflistLine[-1]=='Iris-virginica':

(3)

index+=1

labelsMat=(labelsMat)

t=dataMat

Mat=labelsMat

#数据归⼀化(0-1归⼀化)

defiris_normal(lf):

colDataMax=(0)

colDatamin=(0)

normalDataSet=()

normalDataSet=(t-colDatamin)/(colDataMax-colDatamin)

DataSet=normalDataSet

#决策树对测试集进⾏测试

defiris_decision(lf):

totSize=int([0])

trainSize=int([0]*vision)

testSize=int([0]*(vision))

result=[]

errorCount=0

errorRecords={}

correctRecords={}

index=0

#模型定义

#模型定义

model=DecisionTreeClassifier()

#模型函数,参数为样本数据和数据标签

(DataSet[0:trainSize,:],Mat[0:trainSize])

#模型测试,predict()⽅法为预测⽅法，参数为测试集数据

result=t(DataSet[trainSize:totSize,:])

foriinrange(int(testSize)):

Mat[trainSize+i]!=result[i]:

errorCount+=1

errorRecords[i]=result[i]

correctRecords[i]=Mat[trainSize+i]

print('错误个数：')

print(errorCount)

print('错误位置及错误值：')

print(errorRecords)

print('相应位置的正确值：')

print(correctRecords)

print('正确率：%f%%'%((1-errorCount/testSize)*100))

if__name__=='__main__':

fileName=''#''#⽂件路径

dataMat=[]#数据集（⾃⼰读取）

labelsMat=[]#标签集（⾃⼰读取）

normalDataSet=[]#归⼀化后的数据集

dataDivision=0.8#数据集中训练集和测试集的划分⽐例

iris=Iris(file_name=fileName,data_t=dataMat,labels_t=labelsMat,normal_data_t=normalDataSet,data_division=dataDivision)

_processData()

_normal()

_decision()

2.可以按照算法思路⾃⼰写决策树的算法并进⾏优化