决策树的一些知识
决策树
决策树的定义:
分类决策树模型是一种描述对实例进行分类的树形结构,决策树由结点和有向边组成,结点有两种类型:内部结点和叶结点。内部节点表示一个特征或属性,叶结点表示一个类。
决策树示意图,圆点——内部节点,方框——叶节点
决策树学习的目标:根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确的分类。
决策树学习的本质:从训练集中归纳出一组分类规则,或者说是由训练数据集估计条件概率模型。
决策树学习的损失函数:正则化的极大似然函数
决策树学习的测试:最小化损失函数
决策树学习的目标:在损失函数的意义下,选择最优决策树的问题。
决策树原理和问答猜测结果游戏相似,根据一系列数据,然后给出游戏的答案。
决策树的构造:
决策树学习的算法通常是一个递归地选择最优特征,并根据该特征对训练数据进行分割,使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分,也对应着决策树的构建。
1) 开始:构建根节点,将所有训练数据都放在根节点,选择一个最优特征,按着这一特征将训练数据集分割成子集,使得各个子集有一个在当前条件下最好的分类。
2) 如果这些子集已经能够被基本正确分类,那么构建叶节点,并将这些子集分到所对应的叶节点去。
3)如果还有子集不能够被正确的分类,那么就对这些子集选择新的最优特征,继续对其进行分割,构建相应的节点,如果递归进行,直至所有训练数据子集被基本正确的分类,或者没有合适的特征为止。
4)每个子集都被分到叶节点上,即都有了明确的类,这样就生成了一颗决策树。
决策树的特点:
优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据。
缺点:可能会产生过度匹配的问题
适用数据类型:数值型和标称型
首先:确定当前数据集上的决定性特征,为了得到该决定性特征,必须评估每个特征,完成测试之后,原始数据集就被划分为几个数据子集,这些数据子集会分布在第一个决策点的所有分支上,如果某个分支下的数据属于同一类型,则当前无序阅读的垃圾邮件已经正确的划分数据分类,无需进一步对数据集进行分割,如果不属于同一类,则要重复划分数据子集,直到所有相同类型的数据均在一个数据子集内。
信息增益:
划分数据集的大原则是:将无序数据变得更加有序,但是各种方法都有各自的优缺点,信息论是量化处理信息的分支科学,在划分数据集前后信息发生的变化称为信息增益,获得信息增益最高的特征就是最好的选择,所以必须先学习如何计算信息增益,集合信息的度量方式称为香农熵,或者简称熵。
希望通过所给的训练数据学习一个贷款申请的决策树,用以对未来的贷款申请进行分类,即当新的客户提出贷款申请时,根据申请人的特征利用决策树决定是否批准贷款申请。
特征选择就是决定用哪个特征来划分特征空间。比如,我们通过上述数据表得到两个可能的决策树,分别由两个不同特征的根结点构成。
图(a)所示的根结点的特征是年龄,有3个取值,对应于不同的取值有不同的子结点。图(b)所示的根节点的特征是工作,有2个取值,对应于不同的取值有不同的子结点。两个决策树都可以从此延续下去。问题是:究竟选择哪个特征更好些?这就要求确定选择特征的准则。直观上,如果一个特征具有更好的分类能力,或者说,按照这一特征将训练数据集分割成子集,使得各个子集在当前条件下有最好的分类,那么就更应该选择这个特征。信息增益就能够很好地表示这一直观的准则。
什么是信息增益呢?在划分数据集之前之后信息发生的变化成为信息增益,知道如何计算信息增益,我们就可以计算每个特征值划分数据集获得的信息增益,获得信息增益最高的特征就是最好的选择。
熵定义为信息的期望值,如果待分类的事物可能划分在多个类之中,则符号Xi的信息定义为:
其中,p(Xi)是选择该分类的概率。
为了计算熵,我们需要计算所有类别所有可能值所包含的信息期望值,通过下式得到:
其中,nn为分类数目,熵越大,随机变量的不确定性就越大。
当熵中的概率由数据估计(特别是最大似然估计)得到时,所对应的熵称为经验熵(empirical entropy)。什么叫由数据估计?比如有10个数据,一共有两个类别,A类和B类。其中有7个数据属于A类,则该A类的概率即为十分之七。其中有3个数据属于B类,则该B类的概率即为十分之三。浅显的解释就是,这概率是我们根据数据数出来的。我们定义贷款申请样本数据表中的数据为训练数据集D,则训练数据集D的经验熵为H(D),|D|表示其样本容量,及样本个数。设有K个类Ck,k = 1,2,3,···,K,|Ck|为属于类Ck的样本个数,这经验熵公式可以写为:
根据此公式计算经验熵H(D),分析贷款申请样本数据表中的数据。最终分类结果只有两类,即放贷和不放贷。根据表中的数据统计可知,在15个数据中,9个数据的结果为放贷,6个数据的结果为不放贷。所以数据集D的经验熵H(D)为:
经过计算可知,数据集D的经验熵H(D)的值为0.971。
在理解信息增益之前,要明确——条件熵
信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。
条件熵H(Y∣X)H(Y∣X)表示在已知随机变量X的条件下随机变量Y的不确定性,随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) H(Y|X),定义X给定条件下Y的条件概率分布的熵对X的数学期望:
当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的分别为经验熵和经验条件熵,此时如果有0概率,令0log0=00log0=0
信息增益:信息增益是相对于特征而言的。所以,特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,即:
g(D,A)=H(D)−H(D∣A)
一般地,熵H(D)与条件熵H(D|A)之差成为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
信息增益值的大小相对于训练数据集而言的,并没有绝对意义,在分类问题困难时,也就是说在训练数据集经验熵大的时候,信息增益值会偏大,反之信息增益值会偏小,使用信息增益比可以对这个问题进行校正,这是特征选择的另一个标准。
信息增益比:特征AA对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集DD的经验熵之比:
特征选择案例(统计学习方法):
如图
计算并得出最优特征:
在编写代码之前,我们先对数据集进行属性标注。
年龄:0代表青年,1代表中年,2代表老年;
有工作:0代表否,1代表是;
有自己的房子:0代表否,1代表是;
信贷情况:0代表一般,1代表好,2代表非常好;
类别(是否给贷款):no代表否,yes代表是。
创建数据集,计算经验熵的代码如下:
from math import log
"""
函数说明:创建测试数据集
Parameters:无
Returns:
dataSet:数据集
labels:分类属性
Modify:
2018-03-12
"""
def creatDataSet():
# 数据集
dataSet=[[0, 0, 0, 0, 'no'],
[0, 0, 0, 1, 'no'],
[0, 1, 0, 1, 'yes'],
[0, 1, 1, 0, 'yes'],
[0, 0, 0, 0, 'no'],
[1, 0, 0, 0, 'no'],
[1, 0, 0, 1, 'no'],
[1, 1, 1, 1, 'yes'],
[1, 0, 1, 2, 'yes'],
[1, 0, 1, 2, 'yes'],
[2, 0, 1, 2, 'yes'],
[2, 0, 1, 1, 'yes'],
[2, 1, 0, 1, 'yes'],
[2, 1, 0, 2, 'yes'],
[2, 0, 0, 0, 'no']]
#分类属性
labels=['年龄','有工作','有自己的房子','信贷情况']
#返回数据集和分类属性
return dataSet,labels
"""
函数说明:计算给定数据集的经验熵(香农熵)
Parameters:
dataSet:数据集
Returns:
shannonEnt:经验熵
Modify:
2018-03-12
"""
def calcShannonEnt(dataSet):
#返回数据集行数
numEntries=len(dataSet)
#保存每个标签(label)出现次数的字典
labelCounts={}
#对每组特征向量进行统计
for featVec in dataSet:
currentLabel=featVec[-1] #提取标签信息
if currentLabel not in labelCounts.keys(): #如果标签没有放入统计次数的字典,添加进去
labelCounts[currentLabel]=0
labelCounts[currentLabel]+=1 #label计数
shannonEnt=0.0 #经验熵
#计算经验熵
for key in labelCounts:
prob=float(labelCounts[key])/numEntries #选择该标签的概率
shannonEnt-=prob*log(prob,2) #利用公式计算
return shannonEnt #返回经验熵
#main函数
if __name__=='__main__':
dataSet,features=creatDataSet()
print(dataSet)
print(calcShannonEnt(dataSet))
结果如下
第0个特征的增益为0.083
第1个特征的增益为0.324
第2个特征的增益为0.420
第3个特征的增益为0.363
第0个特征的增益为0.252
第1个特征的增益为0.918
第2个特征的增益为0.474
{'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}
计算信息增益
from math import log
"""
函数说明:创建测试数据集
Parameters:无
Returns:
dataSet:数据集
labels:分类属性
Modify:
2018-03-12
"""
def creatDataSet():
# 数据集
dataSet=[[0, 0, 0, 0, 'no'],
[0, 0, 0, 1, 'no'],
[0, 1, 0, 1, 'yes'],
[0, 1, 1, 0, 'yes'],
[0, 0, 0, 0, 'no'],
[1, 0, 0, 0, 'no'],
[1, 0, 0, 1, 'no'],
[1, 1, 1, 1, 'yes'],
[1, 0, 1, 2, 'yes'],
[1, 0, 1, 2, 'yes'],
[2, 0, 1, 2, 'yes'],
[2, 0, 1, 1, 'yes'],
[2, 1, 0, 1, 'yes'],
[2, 1, 0, 2, 'yes'],
[2, 0, 0, 0, 'no']]
#分类属性
labels=['年龄','有工作','有自己的房子','信贷情况']
#返回数据集和分类属性
return dataSet,labels
"""
函数说明:计算给定数据集的经验熵(香农熵)
Parameters:
dataSet:数据集
Returns:
shannonEnt:经验熵
Modify:
2018-03-12
"""
def calcShannonEnt(dataSet):
#返回数据集行数
numEntries=len(dataSet)
#保存每个标签(label)出现次数的字典
labelCounts={}
#对每组特征向量进行统计
for featVec in dataSet:
currentLabel=featVec[-1] #提取标签信息
if currentLabel not in labelCounts.keys(): #如果标签没有放入统计次数的字典,添加进去
labelCounts[currentLabel]=0
labelCounts[currentLabel]+=1 #label计数
shannonEnt=0.0 #经验熵
#计算经验熵
for key in labelCounts:
prob=float(labelCounts[key])/numEntries #选择该标签的概率
shannonEnt-=prob*log(prob,2) #利用公式计算
return shannonEnt #返回经验熵
"""
函数说明:计算给定数据集的经验熵(香农熵)
Parameters:
dataSet:数据集
Returns:
shannonEnt:信息增益最大特征的索引值
Modify:
2018-03-12
"""
def chooseBestFeatureToSplit(dataSet):
#特征数量
numFeatures = len(dataSet[0]) - 1
#计数数据集的香农熵
baseEntropy = calcShannonEnt(dataSet)
#信息增益
bestInfoGain = 0.0
#最优特征的索引值
bestFeature = -1
#遍历所有特征
for i in range(numFeatures):
# 获取dataSet的第i个所有特征
featList = [example[i] for example in dataSet]
#创建set集合{},元素不可重复
uniqueVals = set(featList)
#经验条件熵
newEntropy = 0.0
#计算信息增益
for value in uniqueVals:
#subDataSet划分后的子集
subDataSet = splitDataSet(dataSet, i, value)
#计算子集的概率
prob = len(subDataSet) / float(len(dataSet))
#根据公式计算经验条件熵
newEntropy += prob * calcShannonEnt((subDataSet))
#信息增益
infoGain = baseEntropy - newEntropy
#打印每个特征的信息增益
print("第%d个特征的增益为%.3f" % (i, infoGain))
#计算信息增益
if (infoGain > bestInfoGain):
#更新信息增益,找到最大的信息增益
bestInfoGain = infoGain
#记录信息增益最大的特征的索引值
bestFeature = i
#返回信息增益最大特征的索引值
return bestFeature
"""
函数说明:按照给定特征划分数据集
Parameters:
dataSet:待划分的数据集
axis:划分数据集的特征
value:需要返回的特征的值
Returns:
shannonEnt:经验熵
Modify:
2018-03-12
"""
def splitDataSet(dataSet,axis,value):
retDataSet=[]
for featVec in dataSet:
if featVec[axis]==value:
reducedFeatVec=featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
#main函数
if __name__=='__main__':
dataSet,features=creatDataSet()
# print(dataSet)
# print(calcShannonEnt(dataSet))
print("最优索引值:"+str(chooseBestFeatureToSplit(dataSet)))
结果
第0个特征的增益为0.083
第1个特征的增益为0.324
第2个特征的增益为0.420
第3个特征的增益为0.363
最优索引值:2
也就是说最优特征是有自己的房子,因为他的信息增益g(D,A3)最大
决策树的生成
稍后再写。
上一篇: Python——线性回归模型的应用
下一篇: java socket编程实例代码讲解
推荐阅读
-
决策树的一些知识
-
关于上篇的python实现决策树案例的一些总结
-
对于正则表达式的一些整理
-
关于vue-awesome-swiper使用遇到的一些问题和心得(手动设置宽、手机翻转问题、回调函数、滑动)
-
对于fork()的一些总结
-
【机器学习入门一】决策树及ID3决策树的python实现
-
python基础教程:决策树剪枝算法的python实现方法详解本文实例讲述了决策树剪枝算法的python实现方法。分享给大家供大家参考,具体如下: 决策树是一种依托决策而建立起来的一种树。在机器学习中
-
关于HBase的一些零碎事
-
浅谈对于《机器学习》(周志华)第四章4.2.1信息增益与ID3决策树训练算法的个人理解
-
基于信息增益的决策树特征选择算法(ID3算法)及python实现