本博客还有多个超详细综述,感兴趣的朋友可以移步:
卷积神经网络:卷积神经网络超详细介绍
目标检测:目标检测超详细介绍
语义分割:语义分割超详细介绍
数据增强:一文看懂计算机视觉中的数据增强
损失函数:分类检测分割中的损失函数和评价指标
Transformer:A Survey of Visual Transformers
机器学习实战系列:决策树
YOLO 系列:v1、v2、v3、v4、scaled-v4、v5、v6、v7、yolof、yolox、yolos、yolop
(声明:本文内容来自机器学习实战和统计学习方法,是两者的整合,并非来自单个书籍)
决策树(decision tree):是一种基本的分类与回归方法,此处主要讨论分类的决策树。
在分类问题中,表示基于特征对实例进行分类的过程,可以认为是if-then的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。
决策树通常有三个步骤:特征选择、决策树的生成、决策树的修剪。
用决策树分类:从根节点开始,对实例的某一特征进行测试,根据测试结果将实例分配到其子节点,此时每个子节点对应着该特征的一个取值,如此递归的对实例进行测试并分配,直到到达叶节点,最后将实例分到叶节点的类中。
下图为决策树示意图,圆点——内部节点,方框——叶节点
决策树学习的目标:根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确的分类。
决策树学习的本质:从训练集中归纳出一组分类规则,或者说是由训练数据集估计条件概率模型。
决策树学习的损失函数:正则化的极大似然函数
决策树学习的测试:最小化损失函数
决策树学习的目标:在损失函数的意义下,选择最优决策树的问题。
决策树原理和问答猜测结果游戏相似,根据一系列数据,然后给出游戏的答案。
上图为一个决策树流程图,正方形代表判断模块,椭圆代表终止模块,表示已经得出结论,可以终止运行,左右箭头叫做分支。
上节介绍的k-近邻算法可以完成很多分类任务,但是其最大的缺点是无法给出数据的内在含义,决策树的优势在于数据形式非常容易理解。
决策树学习的算法通常是一个递归地选择最优特征,并根据该特征对训练数据进行分割,使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分,也对应着决策树的构建。
1) 开始:构建根节点,将所有训练数据都放在根节点,选择一个最优特征,按着这一特征将训练数据集分割成子集,使得各个子集有一个在当前条件下最好的分类。
2) 如果这些子集已经能够被基本正确分类,那么构建叶节点,并将这些子集分到所对应的叶节点去。
3)如果还有子集不能够被正确的分类,那么就对这些子集选择新的最优特征,继续对其进行分割,构建相应的节点,如果递归进行,直至所有训练数据子集被基本正确的分类,或者没有合适的特征为止。
4)每个子集都被分到叶节点上,即都有了明确的类,这样就生成了一颗决策树。
决策树的特点:
过程:
首先,确定当前数据集上的决定性特征,为了得到该决定性特征,必须评估每个特征,完成测试之后,原始数据集就被划分为几个数据子集,这些数据子集会分布在第一个决策点的所有分支上,如果某个分支下的数据属于同一类型,则当前无序阅读的垃圾邮件已经正确的划分数据分类,无需进一步对数据集进行分割,如果不属于同一类,则要重复划分数据子集,直到所有相同类型的数据均在一个数据子集内。
创建分支的伪代码 createBranch()
如下图所示:
检测数据集中每个子项是否属于同一类:
If so return 类标签:
Else
寻找划分数据集的最好特征
划分数据集
创建分支节点
for 每个划分的子集
调用函数createBranch()并增加返回结果到分支节点中
return 分支节点
使用决策树做预测需要以下过程:
本节使用ID3算法来划分数据集,该算法处理如何划分数据集,何时停止划分数据集。
划分数据集的大原则是:将无序数据变得更加有序,但是各种方法都有各自的优缺点,信息论是量化处理信息的分支科学,在划分数据集前后信息发生的变化称为信息增益,获得信息增益最高的特征就是最好的选择,所以必须先学习如何计算信息增益,集合信息的度量方式称为香农熵,或者简称熵。
希望通过所给的训练数据学习一个贷款申请的决策树,用以对未来的贷款申请进行分类,即当新的客户提出贷款申请时,根据申请人的特征利用决策树决定是否批准贷款申请。
特征选择就是决定用哪个特征来划分特征空间。比如,我们通过上述数据表得到两个可能的决策树,分别由两个不同特征的根结点构成。
图 (a) 所示的根结点的特征是年龄,有3个取值,对应于不同的取值有不同的子结点。
图 (b) 所示的根节点的特征是工作,有2个取值,对应于不同的取值有不同的子结点。两个决策树都可以从此延续下去。
问题是:究竟选择哪个特征更好些?这就要求确定选择特征的准则。
直观上,如果一个特征具有更好的分类能力,或者说,按照这一特征将训练数据集分割成子集,使得各个子集在当前条件下有最好的分类,那么就更应该选择这个特征。
信息增益就能够很好地表示这一直观的准则。
什么是信息增益呢?在划分数据集之前之后信息发生的变化成为信息增益,知道如何计算信息增益,我们就可以计算每个特征值划分数据集获得的信息增益,获得信息增益最高的特征就是最好的选择。
熵定义为信息的期望值,如果待分类的事物可能划分在多个类之中,则符号 x i x_i xi 的信息定义为:
l ( x i ) = − l o g 2 p ( x i ) l(x_i)=-log_2 p(x_i) l(xi)=−log2p(xi)
其中, p ( x i ) p(x_i) p(xi)是选择该分类的概率。
为了计算熵,我们需要计算所有类别所有可能值所包含的信息期望值,通过下式得到:
H = − Σ i = 1 n p ( x i ) l o g 2 p ( x i ) H=-\Sigma_{i=1}^n p(x_i)log_2 p(x_i) H=−Σi=1np(xi)log2p(xi)
其中, n n n为分类数目,熵越大,随机变量的不确定性就越大。
当熵中的概率由数据估计(特别是最大似然估计)得到时,所对应的熵称为经验熵(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 ) = − Σ ∣ c k ∣ ∣ D ∣ l o g 2 ∣ c k ∣ ∣ D ∣ H(D)=-\Sigma \frac{|c_k|}{|D|}log_2\frac{|c_k|}{|D|} H(D)=−Σ∣D∣∣ck∣log2∣D∣∣ck∣
根据此公式计算经验熵H(D),分析贷款申请样本数据表中的数据。最终分类结果只有两类,即放贷和不放贷。根据表中的数据统计可知,在15个数据中,9个数据的结果为放贷,6个数据的结果为不放贷。所以数据集D的经验熵H(D)为:
H ( D ) = − 9 15 l o g 2 9 15 − 6 15 l o g 2 6 15 = 0.971 H(D)=-\frac{9}{15} log_2\frac{9}{15}-\frac{6}{15} log_2\frac{6}{15}=0.971 H(D)=−159log2159−156log2156=0.971
经过计算可知,数据集D的经验熵H(D)的值为0.971。
在理解信息增益之前,要明确——条件熵
信息增益表示得知特征 X 的信息而使得类Y的信息不确定性减少的程度。
条件熵 H ( Y ∣ X ) H(Y|X) H(Y∣X) 表示在已知随机变量X的条件下随机变量Y的不确定性,随机变量X给定的条件下随机变量Y的条件熵 (conditional entropy) H(Y|X),定义X给定条件下Y的条件概率分布的熵对X的数学期望:
H ( Y ∣ X ) = ∑ i = 1 n p i H ( Y ∣ X = x i ) H(Y|X)=\sum_{i=1}^n p_iH(Y|X=x_i) H(Y∣X)=i=1∑npiH(Y∣X=xi)
其中, p i = P ( X = x i ) p_i=P(X=x_i) pi=P(X=xi)
当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的分别为经验熵和经验条件熵,此时如果有0概率,令 0 l o g 0 = 0 0log0=0 0log0=0
信息增益:信息增益是相对于特征而言的。所以,特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,即:
g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D,A)=H(D)-H(D|A) g(D,A)=H(D)−H(D∣A)
一般地,熵H(D)与条件熵H(D|A)之差成为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
信息增益值的大小相对于训练数据集而言的,并没有绝对意义,在分类问题困难时,也就是说在训练数据集经验熵大的时候,信息增益值会偏大,反之信息增益值会偏小,使用信息增益比可以对这个问题进行校正,这是特征选择的另一个标准。
信息增益比:特征 A A A对训练数据集D的信息增益比 g R ( D , A ) g_R(D,A) gR(D,A)定义为其信息增益 g ( D , A ) g(D,A) g(D,A)与训练数据集 D D D的经验熵之比:
g R ( D , A ) = g ( D , A ) H ( D ) g_R(D,A)=\frac{g(D,A)}{H(D)} gR(D,A)=H(D)g(D,A)
在编写代码之前,我们先对数据集进行属性标注。
创建数据集,计算经验熵的代码如下:
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
对比我们自己计算的结果,发现结果完全正确!最优特征的索引值为2,也就是特征A3(有自己的房子)。
我们已经学习了从数据集构造决策树算法所需要的子功能模块,包括经验熵的计算和最优特征的选择。
其工作原理如下:
得到原始数据集,然后基于最好的属性值划分数据集,由于特征值可能多于两个,因此可能存在大于两个分支的数据集划分。
第一次划分之后,数据集被向下传递到树的分支的下一个结点。在这个结点上,我们可以再次划分数据。
因此我们可以采用递归的原则处理数据集。
构建决策树的算法有很多,比如C4.5、ID3和CART,这些算法在运行时并不总是在每次划分数据分组时都会消耗特征。
由于特征数目并不是每次划分数据分组时都减少,因此这些算法在实际使用时可能引起一定的问题。
目前我们并不需要考虑这个问题,只需要在算法开始运行前计算列的数目,查看算法是否使用了所有属性即可。
决策树生成算法递归地产生决策树,直到不能继续下去未为止。这样产生的树往往对训练数据的分类很准确,但对未知的测试数据的分类却没有那么准确,即出现过拟合现象。
过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类,从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度,对已生成的决策树进行简化。
ID3算法的核心是在决策树各个结点上对应信息增益准则选择特征,递归地构建决策树。
具体方法是:
1)从根结点(root node)开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征。
2)由该特征的不同取值建立子节点,再对子结点递归地调用以上方法,构建决策树;直到所有特征的信息增益均很小或没有特征可以选择为止;
3)最后得到一个决策树。
ID3相当于用极大似然法进行概率模型的选择
算法步骤:
分析数据:
上面已经求得,特征A3(有自己的房子)的信息增益最大,所以选择A3为根节点的特征
它将训练集D划分为两个子集D1(A3取值为“是”)D2(A3取值为“否”)
由于D1只有同一类的样本点,所以它成为一个叶结点,结点的类标记为“是”。
对D2则需要从特征A1(年龄),A2(有工作)和A4(信贷情况)中选择新的特征,计算各个特征的信息增益:
g ( D 2 , A 1 ) = H ( D 2 ) − H ( D 2 ∣ A 1 ) = 0.251 g(D2,A1)=H(D2)-H(D2|A1)=0.251 g(D2,A1)=H(D2)−H(D2∣A1)=0.251
g ( D 2 , A 2 ) = H ( D 2 ) − H ( D 2 ∣ A 2 ) = 0.918 g(D2,A2)=H(D2)-H(D2|A2)=0.918 g(D2,A2)=H(D2)−H(D2∣A2)=0.918
g ( D 2 , A 3 ) = H ( D 2 ) − H ( D 2 ∣ A 3 ) = 0.474 g(D2,A3)=H(D2)-H(D2|A3)=0.474 g(D2,A3)=H(D2)−H(D2∣A3)=0.474
根据计算,选择信息增益最大的A2作为节点的特征,由于其有两个取值可能,所以引出两个子节点:
①对应“是”(有工作),包含三个样本,属于同一类,所以是一个叶子节点,类标记为“是”
②对应“否”(无工作),包含六个样本,输入同一类,所以是一个叶子节点,类标记为“否”
这样就生成一个决策树,该树只用了两个特征(有两个内部节点),生成的决策树如下图所示:
与ID3算法相似,但是做了改进,将信息增益比作为选择特征的标准。
递归构建决策树:
从数据集构造决策树算法所需的子功能模块工作原理如下:得到原始数据集,然后基于最好的属性值划分数据集,由于特征值可能多于两个,因此可能存在大于两个分支的数据集划分,第一次划分之后,数据将被向下传递到树分支的下一个节点,在此节点在此划分数据,因此可以使用递归的原则处理数据集。
递归结束的条件是:
程序完全遍历所有划分数据集的属性,或者每个分支下的所有实例都具有相同的分类,如果所有实例具有相同的分类,则得到一个叶子节点或者终止块,任何到达叶子节点的数据必然属于叶子节点的分类。
编写ID3算法的代码
from math import log
import operator
"""
函数说明:计算给定数据集的经验熵(香农熵)
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:无
Returns:
dataSet:数据集
labels:分类属性
Modify:
2018-03-13
"""
def createDataSet():
# 数据集
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:待划分的数据集
axis:划分数据集的特征
value:需要返回的特征值
Returns:
无
Modify:
2018-03-13
"""
def splitDataSet(dataSet,axis,value):
#创建返回的数据集列表
retDataSet=[]
#遍历数据集
for featVec in dataSet:
if featVec[axis]==value:
#去掉axis特征
reduceFeatVec=featVec[:axis]
#将符合条件的添加到返回的数据集
reduceFeatVec.extend(featVec[axis+1:])
retDataSet.append(reduceFeatVec)
#返回划分后的数据集
return retDataSet
"""
函数说明:计算给定数据集的经验熵(香农熵)
Parameters:
dataSet:数据集
Returns:
shannonEnt:信息增益最大特征的索引值
Modify:
2018-03-13
"""
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
"""
函数说明:统计classList中出现次数最多的元素(类标签)
Parameters:
classList:类标签列表
Returns:
sortedClassCount[0][0]:出现次数最多的元素(类标签)
Modify:
2018-03-13
"""
def majorityCnt(classList):
classCount={
}
#统计classList中每个元素出现的次数
for vote in classList:
if vote not in classCount.keys():
classCount[vote]=0
classCount[vote]+=1
#根据字典的值降序排列
sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
return sortedClassCount[0][0]
"""
函数说明:创建决策树
Parameters:
dataSet:训练数据集
labels:分类属性标签
featLabels:存储选择的最优特征标签
Returns:
myTree:决策树
Modify:
2018-03-13
"""
def createTree(dataSet,labels,featLabels):
#取分类标签(是否放贷:yes or no)
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)
#最优特征的标签
bestFeatLabel=labels[bestFeat]
featLabels.append(bestFeatLabel)
#根据最优特征的标签生成树
myTree={
bestFeatLabel:{
}}
#删除已经使用的特征标签
del(labels[bestFeat])
#得到训练集中所有最优特征的属性值
featValues=[example[bestFeat] for example in dataSet]
#去掉重复的属性值
uniqueVls=set(featValues)
#遍历特征,创建决策树
for value in uniqueVls:
myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),
labels,featLabels)
return myTree
if __name__=='__main__':
dataSet,labels=createDataSet()
featLabels=[]
myTree=createTree(dataSet,labels,featLabels)
print(myTree)
结果:
第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'}}
决策树生成算法递归的产生决策树,直到不能继续下去为止,这样产生的树往往对训练数据的分类很准确,但对未知测试数据的分类缺没有那么精确,即会出现过拟合现象。
过拟合产生的原因在于在学习时过多的考虑如何提高对训练数据的正确分类,从而构建出过于复杂的决策树,解决方法是考虑决策树的复杂度,对已经生成的树进行简化。
剪枝(pruning):从已经生成的树上裁掉一些子树或叶节点,并将其根节点或父节点作为新的叶子节点,从而简化分类树模型。
实现方式:极小化决策树整体的损失函数或代价函数来实现
决策树学习的损失函数定义为:
C α ( T ) = ∑ t = 1 ∣ T ∣ N t H t ( T ) + α ∣ T ∣ C_\alpha(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T| Cα(T)=t=1∑∣T∣NtHt(T)+α∣T∣
其中:
参数 | 意义 |
---|---|
T T T | 表示这棵子树的叶子节点, |
H t ( T ) H_t(T) Ht(T) | 表示第 t t t个叶子的熵,[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QHgonDQQ-1663157039225)(//img-blog.csdn.net/20180314091812955?watermark/2/text/Ly9ibG9nLmNzZG4ubmV0L2ppYW95YW5nd20=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70)] |
N t N_t Nt | 表示该叶子所含的训练样例的个数, |
α \alpha α | 惩罚系数, |
∣ T ∣ |T| ∣T∣ | 表示子树的叶子节点的个数。 |
因为:
所以有: C α ( T ) = C ( T ) + α ∣ T ∣ C_\alpha(T)=C(T)+\alpha|T| Cα(T)=C(T)+α∣T∣
其中:
参数 | 意义 |
---|---|
C ( T ) C(T) C(T) | 表示模型对训练数据的预测误差,即模型与训练数据的拟合程度; |
∣ T ∣ |T| ∣T∣ | 表示模型复杂度 |
α \alpha α | 参数 α > = 0 \alpha>=0 α>=0控制两者之间的影响,较大的 α \alpha α促使选择较简单的模型(树),较小的 α \alpha α促使选择较复杂的模型(树), α = 0 \alpha=0 α=0意味着只考虑模型与训练数据的拟合程度,不考虑模型的复杂度。 |
剪枝就是当 α \alpha α确定时,选择损失函数最小的模型,即损失函数最小的子树。
损失函数认为对于每个分类终点(叶子节点)的不确定性程度就是分类的损失因子,而叶子节点的个数是模型的复杂程度,作为惩罚项,损失函数的第一项是样本的训练误差,第二项是模型的复杂度。
如果一棵子树的损失函数值越大,说明这棵子树越差,因此我们希望让每一棵子树的损失函数值尽可能得小,损失函数最小化就是用正则化的极大似然估计进行模型选择的过程。
决策树的剪枝过程(泛化过程)就是从叶子节点开始递归,记其父节点将所有子节点回缩后的子树为Tb(分类值取类别比例最大的特征值),未回缩的子树为 T a Ta Ta,如果 C α ( T a ) ≥ C α ( T b ) C_α(T_a)≥C_α(T_b) Cα(Ta)≥Cα(Tb) 说明回缩后使得损失函数减小了,那么应该使这棵子树回缩,递归直到无法回缩为止,这样使用“贪心”的思想进行剪枝可以降低损失函数值,也使决策树得到泛化。
可以看出,决策树的生成只是考虑通过提高信息增益对训练数据进行更好的拟合,而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。
公式 C α ( T ) = C ( T ) + α ∣ T ∣ C_\alpha(T)=C(T)+\alpha|T| Cα(T)=C(T)+α∣T∣ 定义的损失函数的极小化等价于正则化的极大似然估计,剪枝过程示意图:
决策树算法很容易过拟合(overfitting),剪枝算法就是用来防止决策树过拟合,提高泛华性能的方法。
剪枝分为预剪枝与后剪枝。
预剪枝是指在决策树的生成过程中,对每个节点在划分前先进行评估,若当前的划分不能带来泛化性能的提升,则停止划分,并将当前节点标记为叶节点。
后剪枝是指先从训练集生成一颗完整的决策树,然后自底向上对非叶节点进行考察,若将该节点对应的子树替换为叶节点,能带来泛化性能的提升,则将该子树替换为叶节点。
那么怎么来判断是否带来泛化性能的提升那?最简单的就是留出法,即预留一部分数据作为验证集来进行性能评估。
这里代码都是关于 Matplotlib 的,如果对于 Matplotlib 不了解的,可以先学习下,Matplotlib的内容这里就不再累述。可视化需要用到的函数:
getNumLeafs
:获取决策树叶子结点的数目
getTreeDepth
:获取决策树的层数
plotNode
:绘制结点
plotMidText
:标注有向边属性值
plotTree
:绘制决策树
createPlot
:创建绘制面板
from math import log
import operator
from matplotlib.font_manager import FontProperties
import matplotlib.pyplot as plt
"""
函数说明:计算给定数据集的经验熵(香农熵)
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:无
Returns:
dataSet:数据集
labels:分类属性
Modify:
2018-03-13
"""
def createDataSet():
# 数据集
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:待划分的数据集
axis:划分数据集的特征
value:需要返回的特征值
Returns:
无
Modify:
2018-03-13
"""
def splitDataSet(dataSet,axis,value):
#创建返回的数据集列表
retDataSet=[]
#遍历数据集
for featVec in dataSet:
if featVec[axis]==value:
#去掉axis特征
reduceFeatVec=featVec[:axis]
#将符合条件的添加到返回的数据集
reduceFeatVec.extend(featVec[axis+1:])
retDataSet.append(reduceFeatVec)
#返回划分后的数据集
return retDataSet
"""
函数说明:计算给定数据集的经验熵(香农熵)
Parameters:
dataSet:数据集
Returns:
shannonEnt:信息增益最大特征的索引值
Modify:
2018-03-13
"""
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
"""
函数说明:统计classList中出现次数最多的元素(类标签)
Parameters:
classList:类标签列表
Returns:
sortedClassCount[0][0]:出现次数最多的元素(类标签)
Modify:
2018-03-13
"""
def majorityCnt(classList):
classCount={
}
#统计classList中每个元素出现的次数
for vote in classList:
if vote not in classCount.keys():
classCount[vote]=0
classCount[vote]+=1
#根据字典的值降序排列
sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
return sortedClassCount[0][0]
"""
函数说明:创建决策树
Parameters:
dataSet:训练数据集
labels:分类属性标签
featLabels:存储选择的最优特征标签
Returns:
myTree:决策树
Modify:
2018-03-13
"""
def createTree(dataSet,labels,featLabels):
#取分类标签(是否放贷:yes or no)
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)
#最优特征的标签
bestFeatLabel=labels[bestFeat]
featLabels.append(bestFeatLabel)
#根据最优特征的标签生成树
myTree={
bestFeatLabel:{
}}
#删除已经使用的特征标签
del(labels[bestFeat])
#得到训练集中所有最优特征的属性值
featValues=[example[bestFeat] for example in dataSet]
#去掉重复的属性值
uniqueVls=set(featValues)
#遍历特征,创建决策树
for value in uniqueVls:
myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),
labels,featLabels)
return myTree
"""
函数说明:获取决策树叶子节点的数目
Parameters:
myTree:决策树
Returns:
numLeafs:决策树的叶子节点的数目
Modify:
2018-03-13
"""
def getNumLeafs(myTree):
numLeafs=0
firstStr=next(iter(myTree))
secondDict=myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]).__name__=='dict':
numLeafs+=getNumLeafs(secondDict[key])
else: numLeafs+=1
return numLeafs
"""
函数说明:获取决策树的层数
Parameters:
myTree:决策树
Returns:
maxDepth:决策树的层数
Modify:
2018-03-13
"""
def getTreeDepth(myTree):
maxDepth = 0 #初始化决策树深度
firstStr = next(iter(myTree)) #python3中myTree.keys()返回的是dict_keys,不在是list,所以不能使用myTree.keys()[0]的方法获取结点属性,可以使用list(myTree.keys())[0]
secondDict = myTree[firstStr] #获取下一个字典
for key in secondDict.keys():
if type(secondDict[key]).__name__=='dict': #测试该结点是否为字典,如果不是字典,代表此结点为叶子结点
thisDepth = 1 + getTreeDepth(secondDict[key])
else: thisDepth = 1
if thisDepth > maxDepth: maxDepth = thisDepth #更新层数
return maxDepth
"""
函数说明:绘制结点
Parameters:
nodeTxt - 结点名
centerPt - 文本位置
parentPt - 标注的箭头位置
nodeType - 结点格式
Returns:
无
Modify:
2018-03-13
"""
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
arrow_args = dict(arrowstyle="<-") #定义箭头格式
font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14) #设置中文字体
createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction', #绘制结点
xytext=centerPt, textcoords='axes fraction',
va="center", ha="center", bbox=nodeType, arrowprops=arrow_args, FontProperties=font)
"""
函数说明:标注有向边属性值
Parameters:
cntrPt、parentPt - 用于计算标注位置
txtString - 标注的内容
Returns:
无
Modify:
2018-03-13
"""
def plotMidText(cntrPt, parentPt, txtString):
xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0] #计算标注位置
yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)
"""
函数说明:绘制决策树
Parameters:
myTree - 决策树(字典)
parentPt - 标注的内容
nodeTxt - 结点名
Returns:
无
Modify:
2018-03-13
"""
def plotTree(myTree, parentPt, nodeTxt):
decisionNode = dict(boxstyle="sawtooth", fc="0.8") #设置结点格式
leafNode = dict(boxstyle="round4", fc="0.8") #设置叶结点格式
numLeafs = getNumLeafs(myTree) #获取决策树叶结点数目,决定了树的宽度
depth = getTreeDepth(myTree) #获取决策树层数
firstStr = next(iter(myTree)) #下个字典
cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff) #中心位置
plotMidText(cntrPt, parentPt, nodeTxt) #标注有向边属性值
plotNode(firstStr, cntrPt, parentPt, decisionNode) #绘制结点
secondDict = myTree[firstStr] #下一个字典,也就是继续绘制子结点
plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD #y偏移
for key in secondDict.keys():
if type(secondDict[key]).__name__=='dict': #测试该结点是否为字典,如果不是字典,代表此结点为叶子结点
plotTree(secondDict[key],cntrPt,str(key)) #不是叶结点,递归调用继续绘制
else: #如果是叶结点,绘制叶结点,并标注有向边属性值
plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW
plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD
"""
函数说明:创建绘制面板
Parameters:
inTree - 决策树(字典)
Returns:
无
Modify:
2018-03-13
"""
def createPlot(inTree):
fig = plt.figure(1, facecolor='white')#创建fig
fig.clf()#清空fig
axprops = dict(xticks=[], yticks=[])
createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)#去掉x、y轴
plotTree.totalW = float(getNumLeafs(inTree))#获取决策树叶结点数目
plotTree.totalD = float(getTreeDepth(inTree))#获取决策树层数
plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0#x偏移
plotTree(inTree, (0.5,1.0), '')#绘制决策树
plt.show()#显示绘制结果
if __name__ == '__main__':
dataSet, labels = createDataSet()
featLabels = []
myTree = createTree(dataSet, labels, featLabels)
print(myTree)
createPlot(myTree)
if __name__=='__main__':
dataSet,labels=createDataSet()
featLabels=[]
myTree=createTree(dataSet,labels,featLabels)
print(myTree)
这三个是非常著名的决策树算法。简单粗暴来说,ID3 使用信息增益作为选择特征的准则;C4.5 使用信息增益比作为选择特征的准则;CART 使用 Gini 指数作为选择特征的准则。
一、ID3
熵表示的是数据中包含的信息量大小。熵越小,数据的纯度越高,也就是说数据越趋于一致,这是我们希望的划分之后每个子节点的样子。
信息增益 = 划分前熵 - 划分后熵。信息增益越大,则意味着使用属性 a 来进行划分所获得的 “纯度提升” 越大 。也就是说,用属性 a 来划分训练集,得到的结果中纯度比较高。
ID3 仅仅适用于二分类问题。ID3 仅仅能够处理离散属性。
二、C4.5
C4.5 克服了 ID3 仅仅能够处理离散属性的问题,以及信息增益偏向选择取值较多特征的问题,使用信息增益比来选择特征。信息增益比 = 信息增益 / 划分前熵 选择信息增益比最大的作为最优特征。
C4.5 处理连续特征是先将特征取值排序,以连续两个值中间值作为划分标准。尝试每一种划分,并计算修正后的信息增益,选择信息增益最大的分裂点作为该属性的分裂点。
三、CART
CART 与 ID3,C4.5 不同之处在于 CART 生成的树必须是二叉树。也就是说,无论是回归还是分类问题,无论特征是离散的还是连续的,无论属性取值有多个还是两个,内部节点只能根据属性值进行二分。
CART 的全称是分类与回归树。从这个名字中就应该知道,CART 既可以用于分类问题,也可以用于回归问题。
回归树中,使用平方误差最小化准则来选择特征并进行划分。每一个叶子节点给出的预测值,是划分到该叶子节点的所有样本目标值的均值,这样只是在给定划分的情况下最小化了平方误差。
要确定最优化分,还需要遍历所有属性,以及其所有的取值来分别尝试划分并计算在此种划分情况下的最小平方误差,选取最小的作为此次划分的依据。由于回归树生成使用平方误差最小化准则,所以又叫做最小二乘回归树。
分类树种,使用 Gini 指数最小化准则来选择特征并进行划分;
Gini 指数表示集合的不确定性,或者是不纯度。基尼指数越大,集合不确定性越高,不纯度也越大。这一点和熵类似。另一种理解基尼指数的思路是,基尼指数是为了最小化误分类的概率。
信息增益 vs 信息增益比
之所以引入了信息增益比,是由于信息增益的一个缺点。那就是:信息增益总是偏向于选择取值较多的属性。信息增益比在此基础上增加了一个罚项,解决了这个问题。
Gini 指数 vs 熵
既然这两个都可以表示数据的不确定性,不纯度。那么这两个有什么区别那?
依靠训练数据构造了决策树之后,我们可以将它用于实际数据的分类。
在构建决策树的代码,可以看到,有个featLabels参数。它是用来干什么的?它就是用来记录各个分类结点的,在用决策树做预测的时候,我们按顺序输入需要的分类结点的属性值即可。
举个例子,比如我用上述已经训练好的决策树做分类,那么我只需要提供这个人是否有房子,是否有工作这两个信息即可,无需提供冗余的信息。
from math import log
import operator
"""
函数说明:计算给定数据集的经验熵(香农熵)
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:无
Returns:
dataSet:数据集
labels:分类属性
Modify:
2018-03-13
"""
def createDataSet():
# 数据集
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:待划分的数据集
axis:划分数据集的特征
value:需要返回的特征值
Returns:
无
Modify:
2018-03-13
"""
def splitDataSet(dataSet,axis,value):
#创建返回的数据集列表
retDataSet=[]
#遍历数据集
for featVec in dataSet:
if featVec[axis]==value:
#去掉axis特征
reduceFeatVec=featVec[:axis]
#将符合条件的添加到返回的数据集
reduceFeatVec.extend(featVec[axis+1:])
retDataSet.append(reduceFeatVec)
#返回划分后的数据集
return retDataSet
"""
函数说明:计算给定数据集的经验熵(香农熵)
Parameters:
dataSet:数据集
Returns:
shannonEnt:信息增益最大特征的索引值
Modify:
2018-03-13
"""
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
"""
函数说明:统计classList中出现次数最多的元素(类标签)
Parameters:
classList:类标签列表
Returns:
sortedClassCount[0][0]:出现次数最多的元素(类标签)
Modify:
2018-03-13
"""
def majorityCnt(classList):
classCount={
}
#统计classList中每个元素出现的次数
for vote in classList:
if vote not in classCount.keys():
classCount[vote]=0
classCount[vote]+=1
#根据字典的值降序排列
sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
return sortedClassCount[0][0]
"""
函数说明:创建决策树
Parameters:
dataSet:训练数据集
labels:分类属性标签
featLabels:存储选择的最优特征标签
Returns:
myTree:决策树
Modify:
2018-03-13
"""
def createTree(dataSet,labels,featLabels):
#取分类标签(是否放贷:yes or no)
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)
#最优特征的标签
bestFeatLabel=labels[bestFeat]
featLabels.append(bestFeatLabel)
#根据最优特征的标签生成树
myTree={
bestFeatLabel:{
}}
#删除已经使用的特征标签
del(labels[bestFeat])
#得到训练集中所有最优特征的属性值
featValues=[example[bestFeat] for example in dataSet]
#去掉重复的属性值
uniqueVls=set(featValues)
#遍历特征,创建决策树
for value in uniqueVls:
myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),
labels,featLabels)
return myTree
"""
使用决策树进行分类
Parameters:
inputTree;已经生成的决策树
featLabels:存储选择的最优特征标签
testVec:测试数据列表,顺序对应最优特征标签
Returns:
classLabel:分类结果
Modify:2018-03-13
"""
def classify(inputTree,featLabels,testVec):
#获取决策树节点
firstStr=next(iter(inputTree))
#下一个字典
secondDict=inputTree[firstStr]
featIndex=featLabels.index(firstStr)
for key in secondDict.keys():
if testVec[featIndex]==key:
if type(secondDict[key]).__name__=='dict':
classLabel=classify(secondDict[key],featLabels,testVec)
else: classLabel=secondDict[key]
return classLabel
if __name__=='__main__':
dataSet,labels=createDataSet()
featLabels=[]
myTree=createTree(dataSet,labels,featLabels)
#测试数据
testVec=[0,1]
result=classify(myTree,featLabels,testVec)
if result=='yes':
print('放贷')
if result=='no':
print('不放贷')
结果:
第0个特征的增益为0.083
第1个特征的增益为0.324
第2个特征的增益为0.420
第3个特征的增益为0.363
第0个特征的增益为0.252
第1个特征的增益为0.918
第2个特征的增益为0.474
放贷
构造决策树是很耗时的任务,即使处理很小的数据集,如前面的样本数据,也要花费几秒的时间,如果数据集很大,将会耗费很多计算时间。然而用创建好的决策树解决分类问题,则可以很快完成。
因此,为了节省计算时间,最好能够在每次执行分类时调用已经构造好的决策树。为了解决这个问题,需要使用Python模块pickle序列化对象。序列化对象可以在磁盘上保存对象,并在需要的时候读取出来。
假设我们已经得到决策树{'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}
,使用pickle.dump
存储决策树。
import pickle
"""
函数说明:存储决策树
Parameters:
inputTree:已经生成的决策树
filename:决策树的存储文件名
Returns:
无
Modify:
2018-03-13
"""
def storeTree(inputTree,filename):
with open(filename,'wb') as fw:
pickle.dump(inputTree,fw)
if __name__=='__main__':
myTree={
'有自己的房子':{
0:{
'有工作':{
0:'no',1:'yes'}},1:'yes'}}
storeTree(myTree,'classifierStorage.txt')
运行代码,在该Python文件的相同目录下,会生成一个名为classifierStorage.txt
的txt文件,这个文件二进制存储着我们的决策树。
很简单使用pickle.load
进行载入即可,编写代码如下:
import pickle
"""
函数说明:读取决策树
Parameters:
filename:决策树的存储文件名
Returns:
pickle.load(fr):决策树字典
Modify:
2018-03-13
"""
def grabTree(filename):
fr = open(filename, 'rb')
return pickle.load(fr)
if __name__ == '__main__':
myTree = grabTree('classifierStorage.txt')
print(myTree)
步骤:
收集数据:使用书中提供的小型数据集
准备数据:对文本中的数据进行预处理,如解析数据行
分析数据:快速检查数据,并使用createPlot()函数绘制最终的树形图
训练决策树:使用createTree()函数训练
测试决策树:编写简单的测试函数验证决策树的输出结果&绘图结果
使用决策树:这部分可选择将训练好的决策树进行存储,以便随时使用
sklearn.tree
——提供了决策树模型,用于解决分类和回归问题
class sklearn.tree.DecisionTreeClassifier(criterion=’gini’, splitter=’best’, max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort=False)[source]
参数说明如下:
criterion
:特征选择标准,可选参数,默认是gini,可以设置为entropy。gini是基尼不纯度,是将来自集合的某种结果随机应用于某一数据项的预期误差率,是一种基于统计的思想。entropy是香农熵,也就是上篇文章讲过的内容,是一种基于信息论的思想。Sklearn把gini设为默认参数,应该也是做了相应的斟酌的,精度也许更高些?ID3算法使用的是entropy,CART算法使用的则是gini。
splitter
:特征划分点选择标准,可选参数,默认是best,可以设置为random。每个结点的选择策略。best参数是根据算法选择最佳的切分特征,例如gini、entropy。random随机的在部分划分点中找局部最优的划分点。默认的”best”适合样本量不大的时候,而如果样本数据量非常大,此时决策树构建推荐”random”。
max_features
:划分时考虑的最大特征数,可选参数,默认是None。寻找最佳切分时考虑的最大特征数(n_features为总共的特征数),有如下6种情况:
max_depth
:决策树最大深,可选参数,默认是None。这个参数是这是树的层数的。层数的概念就是,比如在贷款的例子中,决策树的层数是2层。如果这个参数设置为None,那么决策树在建立子树的时候不会限制子树的深度。一般来说,数据少或者特征少的时候可以不管这个值。或者如果设置了min_samples_slipt参数,那么直到少于min_smaples_split个样本为止。如果模型样本量多,特征也多的情况下,推荐限制这个最大深度,具体的取值取决于数据的分布。常用的可以取值10-100之间。
min_samples_split
:内部节点再划分所需最小样本数,可选参数,默认是2。这个值限制了子树继续划分的条件。
min_weight_fraction_leaf
:叶子节点最小的样本权重和,可选参数,默认是0。这个值限制了叶子节点所有样本权重和的最小值,如果小于这个值,则会和兄弟节点一起被剪枝。一般来说,如果我们有较多样本有缺失值,或者分类树样本的分布类别偏差很大,就会引入样本权重,这时我们就要注意这个值了。
max_leaf_nodes
:最大叶子节点数,可选参数,默认是None。通过限制最大叶子节点数,可以防止过拟合。如果加了限制,算法会建立在最大叶子节点数内最优的决策树。如果特征不多,可以不考虑这个值,但是如果特征分成多的话,可以加以限制,具体的值可以通过交叉验证得到。
class_weight
:类别权重,可选参数,默认是None,也可以字典、字典列表、balanced。指定样本各类别的的权重,主要是为了防止训练集某些类别的样本过多,导致训练的决策树过于偏向这些类别。类别的权重可以通过{class_label:weight}这样的格式给出,这里可以自己指定各个样本的权重,或者用balanced,如果使用balanced,则算法会自己计算权重,样本量少的类别所对应的样本权重会高。当然,如果你的样本类别分布没有明显的偏倚,则可以不管这个参数,选择默认的None。
random_state
:可选参数,默认是None。随机数种子。如果是证书,那么random_state会作为随机数生成器的随机数种子。随机数种子,如果没有设置随机数,随机出来的数与当前系统时间有关,每个时刻都是不同的。如果设置了随机数种子,那么相同随机数种子,不同时刻产生的随机数也是相同的。如果是RandomState instance,那么random_state是随机数生成器。如果为None,则随机数生成器使用np.random。
min_impurity_split
:节点划分最小不纯度,可选参数,默认是1e-7。这是个阈值,这个值限制了决策树的增长,如果某节点的不纯度(基尼系数,信息增益,均方差,绝对差)小于这个阈值,则该节点不再生成子节点。即为叶子节点 。
presort
:数据是否预排序,可选参数,默认为False,这个值是布尔值,默认是False不排序。一般来说,如果样本量少或者限制了一个深度很小的决策树,设置为true可以让划分点选择更加快,决策树建立的更加快。如果样本量太大的话,反而没有什么好处。问题是样本量少的时候,我速度本来就不慢。所以这个值一般懒得理它就可以了。
除了这些参数要注意以外,其他在调参时的注意点有:
当样本数量少但是样本特征非常多的时候,决策树很容易过拟合,一般来说,样本数比特征数多一些会比较容易建立健壮的模型
如果样本数量少但是样本特征非常多,在拟合决策树模型前,推荐先做维度规约,比如主成分分析(PCA),特征选择(Losso)或者独立成分分析(ICA)。这样特征的维度会大大减小。再来拟合决策树模型效果会好。
推荐多用决策树的可视化,同时先限制决策树的深度,这样可以先观察下生成的决策树里数据的初步拟合情况,然后再决定是否要增加深度。
在训练模型时,注意观察样本的类别情况(主要指分类树),如果类别分布非常不均匀,就要考虑用class_weight来限制模型过于偏向样本多的类别。
决策树的数组使用的是numpy的float32类型,如果训练数据不是这样的格式,算法会先做copy再运行。
如果输入的样本矩阵是稀疏的,推荐在拟合前调用csc_matrix稀疏化,在预测前调用csr_matrix稀疏化。
sklearn.tree.DecisionTreeClassifier()
提供了一些方法供我们使用
数据预处理:将string
类型的数据集进行编码:
为了对string类型的数据序列化,需要先生成pandas数据,这样方便我们的序列化工作。这里我使用的方法是,原始数据->字典->pandas数据,编写代码如下:
import pandas as pd
from sklearn.preprocessing import LabelEncoder
# import pydotplus
# from sklearn.externals.six import StringIO
if __name__ == '__main__':
# 加载文件
with open('lenses.txt', 'r') as fr:
# 处理文件
lenses = [inst.strip().split('\t') for inst in fr.readlines()]
# 提取每组数据的类别,保存在列表里
lenses_target = []
for each in lenses:
lenses_target.append(each[-1])
# 特征标签
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
# 保存lenses数据的临时列表
lenses_list = []
# 保存lenses数据的字典,用于生成pandas
lenses_dict = {
}
# 提取信息,生成字典
for each_label in lensesLabels:
for each in lenses:
lenses_list.append(each[lensesLabels.index(each_label)])
lenses_dict[each_label] = lenses_list
lenses_list = []
# 打印字典信息
print(lenses_dict)
#生成pandas.DataFrame
lenses_pd = pd.DataFrame(lenses_dict)
# print(lenses_pd)
# 生成pandas.DataFrame
lenses_pd = pd.DataFrame(lenses_dict)
# 打印pandas.DataFrame
print(lenses_pd)
# 创建LabelEncoder()对象,用于序列化
le = LabelEncoder()
# 为每一列序列化
for col in lenses_pd.columns:
lenses_pd[col] = le.fit_transform(lenses_pd[col])
print(lenses_pd)
1)pydotplus
安装
直接在anaconda prompt下输入:
pip install pydotplus
安装步骤安装,之后win+R
->sysdm.cpl
在“环境变量”中的“系统变量”中找到“PATH”,之后将路径
C:\Anaconda\pkgs\graphviz-2.38.0-4\Library\bin
添加到后面,重启 Pycharm 即可。
优点:
缺点:
决策树算法主要包括三个部分:特征选择、树的生成、树的剪枝。常用算法有 ID3、C4.5、CART。
特征选择。特征选择的目的是选取能够对训练集分类的特征。特征选择的关键是准则:信息增益、信息增益比、Gini 指数;
决策树的生成。通常是利用信息增益最大、信息增益比最大、Gini 指数最小作为特征选择的准则。从根节点开始,递归的生成决策树。相当于是不断选取局部最优特征,或将训练集分割为基本能够正确分类的子集;
决策树的剪枝。决策树的剪枝是为了防止树的过拟合,增强其泛化能力。包括预剪枝和后剪枝。
梯度提升决策树GBDT(Gradient Boosting Decision Tree)也被称为是MART(Multiple Additive Regression Tree))或者是GBRT(Gradient Boosting Regression Tree),也是一种基于集成思想的决策树模型,但是它和Random Forest有着本质上的区别。
不得不提的是,GBDT是目前竞赛中最为常用的一种机器学习算法,因为它不仅可以适用于多种场景,更难能可贵的是,GBDT有着出众的准确率。这也是为什么很多人称GBDT为机器学习领域的“屠龙刀”。
Boosting,迭代,即通过迭代多棵树来共同决策。这怎么实现呢?
难道是每棵树独立训练一遍,比如A这个人,第一棵树认为是10岁,第二棵树认为是0岁,第三棵树认为是20岁,我们就取平均值10岁做最终结论?
当然不是!且不说这是投票方法并不是GBDT,只要训练集不变,独立训练三次的三棵树必定完全相同,这样做完全没有意义。
之前说过,GBDT是把所有树的结论累加起来做最终结论的,所以可以想到每棵树的结论并不是年龄本身,而是年龄的一个累加量。
GBDT的核心就在于:
每一棵树学的是之前所有树结论和的残差,这个残差就是一个加预测值后能得真实值的累加量。
其实从这里我们可以看出GBDT与Random Forest的本质区别,GBDT不仅仅是简单地运用集成思想,而且它是基于对残差的学习的。我们在这里利用一个GBDT的经典实例进行解释。
在GBDT的迭代中,假设我们前一轮迭代得到的强学习器是 f t − 1 ( x ) f_{t−1}(x) ft−1(x), 损失函数是 L ( y , f t − 1 ( x ) ) L ( y , f t − 1 ( x ) ) L(y,f_{t−1}(x))L(y,f_{t−1}(x)) L(y,ft−1(x))L(y,ft−1(x)), 我们本轮迭代的目标是找到一个CART回归树模型的弱学习器 h t ( x ) h_t(x) ht(x),让本轮的损失损失 L ( y , f t ( x ) = L ( y , f t − 1 ( x ) + h t ( x ) ) L(y,ft(x)=L(y,f_{t−1}(x)+h_t(x)) L(y,ft(x)=L(y,ft−1(x)+ht(x))最小。
也就是说,本轮迭代找到决策树,要让样本的损失尽量变得更小。
GBDT主要的优点有:
可以灵活处理各种类型的数据,包括连续值和离散值。
在相对少的调参时间情况下,预测的准备率也可以比较高。这个是相对SVM来说的。
使用一些健壮的损失函数,对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。
GBDT的主要缺点有:
这篇博客也很好机器学习算法GBDT
文章浏览阅读965次。strace、traceroute、tracert、sar、ifconfig、ip、nc、lsof、stat、netstat、ps、pstree、ss、telnet、top、Htop、iotop、powertop、iftop、dstat、nethogs、Nmon、vnstat、host、dig、route、tcpdump_nc -u 172.0.0.1 12345
文章浏览阅读2.6k次。作用指定如何解析主机域名,可设置网络安全。默认文件内容默认情况,/etc/hosts.conf 文件有如下内容 order hosts,bind multi on12参数说明order是解析顺序的参数,order hosts,bind,nis ,说明先查询解析/etc/hosts文件,然后DNS,再是NIS。multi表示是否运行/etc/hosts文件允许主机指定多个多个地址 ,multi on表示运行。nospoof是否允许服务器对ip地址进行其欺骗,nospoof on表_/etc/host.conf
文章浏览阅读7.1k次,点赞7次,收藏10次。自1954年世界上第一台机器人诞生以来,世界工业发达国家已经建立起完善的工业机器人产业体系。日本、德国的工业机器人水平全球领先,“四大家族”(ABB、库卡、发那科、安川)为全球主要的工业机器人供应商,占据全球约50%的市场份额,这主要因为他们具备先发优势和技术沉淀。 图表1:全球工业机器人“四大家族”介绍随着我国工业自动化、智能化的发展加速,工业机器人的应用普及也带来了市场的急剧增长。既然在中国机..._abb机器人 panbaidu com
文章浏览阅读410次。终端命令格式command [-option] [parameter]command :命令option : 选项parameter:参数查阅命令帮助信息command –help : 帮助信息man command: Linux手册中函数的具体使用通配符* :任意个数字符? :至少一个字符[] :字符组 [abc][a-f]自动补全..._输入重定向命令,首先输入grep ipv6 /etc/*,观察结果,然后将此命令的输出信息
文章浏览阅读9.5k次,点赞4次,收藏14次。1、下载文件到官网下载Verilog的语法高亮文件,链接如下:http://www.ultraedit.com/index.php?name=Content&pa=showpageπd=40#wordfiles2、文件配置将下载到的“verilog.uew”放到ulteaedit安装路径下的wordfiles文件夹内,以及C:\Documents and Setti_verilog.uew
文章浏览阅读941次。1. 字符流----------- android培训、java培训、java学习型技术博客、期待与您交流! ------------3.1 概念:计算机不区分二进制文件与文本文件。所有的文件都是以二进制形式存储的,因此,从本质上说,所以的文件都是二进制文件。所以字符流是建立在字节流之上,它能够提供字符层次的编码和解码。在写入一个字符时,Java虚拟机会将字符_记录一个程序运行的次数,当满足指定次数,改程序就不可以再继续运行了
文章浏览阅读1.2k次。什么是低音炮,低音炮的原理与音效2011-06-15 15:16 低音炮是大家的一个俗称或者简称,严格讲应该是:同轴喇叭,高音仔,超高音,超重低音。就人耳可闻的音频分析而言,由超重低音、低音、低中音、中音、中高音、高音、超高音等组成。 ..._音效是控制低音炮的原理
文章浏览阅读2.1k次。引言:本文旨在提供读者制作一个自己的聚合SDK的思路,抛砖引玉,让更多的读者对聚合SDK有好的理解。 这是最好的时代,这是最坏的时代,这是智慧的时代,这是愚蠢的时代;这是信仰的时期,这是怀疑的时期;这是光明的季节,这是黑暗的季节;这是希望之春,这是失望之冬;人们面前有着各样事物,人们面前一无所有;人们正在直登天堂;人们正在直下地狱。——《双城记》 双城记的开头,正是_typesdk
文章浏览阅读6.4k次。装好keras后,马上运行了例程minst_mlp.py,哇好牛逼,准确率98.4%,但是并不知道自己干了啥。好吧,啃代码。 1. 开头就懵了,数据集在哪呐。 好,从这句入手,找到mnist.py, 从网上下载了minst.pkl.gz,自己顺手下了下来,解压,打开,,,然而并看不懂。肿么办? 不怕,看这里:机器学习–读取mnist数据集 对于这个数据集的详情也可以参考这里:THE_mnist_mlp.py
文章浏览阅读1.7k次,点赞3次,收藏8次。Solidity 从入门到实战(三)注意:本专栏主要来自于https://www.bilibili.com/video/BV1St411a7Pk?p=11&spm_id_from=pageDriver的学习笔记以及https://blog.csdn.net/weixin_45067603/article/details/105751748以太坊中的地址1.以太坊中的地址以40位的16进制表示,储存以uint160进行存储2.地址之间支持大小比较、3.可以分为外部账户地址和合约地址_remix 转账
文章浏览阅读5.6k次,点赞7次,收藏20次。一、文件介绍.log日志文件。这个文件记录了VMwareWorkstation对虚拟机调节运行的情况,记录虚拟机操作,可用了故障诊断。.vmdk这是一个虚拟磁盘文件,它储存了虚拟机硬盘驱动器里的内容。一台虚拟机可以由一个或几个虚拟磁盘文件组成。如果你已经特别指定了虚拟磁盘每2GB为一单独文件的话,虚拟磁盘的大小就决定了虚拟磁盘文件的数量。随着数据写入虚拟磁盘,虚拟磁盘文件将变大,直到这些文件为2GB。(如果你在创建虚拟磁盘时已经把所有的空间都分配了,那么这些文件将在初始时就具..._.vmem
文章浏览阅读1.3k次,点赞5次,收藏18次。问题描述:据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus和他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。请你编写一个函数,计算一下Josephus 和他的朋友应该安排在什么位置,才能免于一死(最后剩下他们两人)。【要求人的总数与报数均由键_今天她玩了一个新游戏,发现每次死亡后角色的金币都会掉落,假设角色开局有g个金币,