李航《统计学习⽅法》——第五章决策树及Python实现（附习题答案）
⽂章⽬录
先感叹⼀下，C++⽔平真的差啊~~~~⼈⽣苦短，我⽤Python
决策树是⼀种基本的分类与回归模型，呈树形结构。可以看作if-then的处理结构，也可以看作条件概率分布，对特征空间进⾏划分，在⼦特征空间进⾏类别判断，⼤于阈值则属于⼦空间的类别。
1 模型
由结点和有向边组成，结点有两种类型，内部结点和叶结点
分类模型 ：内部结点表⽰⼀个特征或者⼀个属性
山药土鸡汤
叶节点表⽰⼀个类——每个结点的样本可能很多，可使⽤多数投票进⾏判断
回归模型：内部节点表⽰划分的值，也相当于属性
叶结点表⽰预测结果——样本到达叶结点预测结果的判定，可采⽤所有叶结点的均值
《机器学习实战》第九章介绍，样本到达叶节点，也可以对叶结点的样本采⽤构造回归模型进⾏处理，这样可 以回归模型可以针对数据⽣成不同的回归函数（分段），拟合效果更好
2 策略
正则化的最⼤似然函数【拟合程度+模型复杂度（叶⼦结点的个数）】
模型复杂度是为防⽌过拟合的剪枝过程
3 算法
泽科特征选择：回归问题——最⼩⼆乘
分类问题——信息增益——>算法ID3
——信息增益⽐——>算法C4.5
——基尼系数——>算法CART 决策树⽣成
剪枝 预剪枝和后剪枝
3.1 ID3 算法（C
4.5算法）决策树
3.1.1 特征选择
ID3 算法
信息增益
表⽰得知特征X的信息⽽使得类Y的信息的不确定性减少的程度。
特征A对训练数据集D的信息增益记为，集合D的信息熵为，给定特征A时集合D的条件经验熵记为，则信息增益就等于
其中[表⽰样本中每⼀类的个数表⽰总样本数]
[表⽰根据特征A将D可以划分为⼏个数据集，为每个数据集样本的
个数，相加等于。表⽰对每⼀个以特征A划分的⼦数据集中划分类别，然后求熵——也就是对每⼀个以特征A划分的⼦数据集求经验熵，然后计算加权和]因此对框架的构造很重要，⾸先需要有根据特征对数据集进⾏划分的函数，然后对计算⼀个集合的熵。⼀开始对公式的理解不到位，直接按H（D|A）的公式计算，⼗分的⿇烦-----
Python实现，⾸先根据某个特征的某个取值进⾏数据集划分成其特征值个⼦集。
'''
按照特定特征划分数据集，axis 特征的维度，value 特征的值
'''
def splitDataSet (dataSet ,axis ,value ):
retDataSet = []
for featvec in dataSet :
if featvec [axis ] == value :
#⼀下两句，是将这个特征去除了
reduceFeatVec = featvec [:axis ]
reduceFeatVec .extend (featvec [axis +1:])
retDataSet .append (reduceFeatVec )
return retDataSet
#计算数据集的熵
def calEntropy (dataSet ,feature =-1):
#增加⼀个feature 参数，默认 -1，也就是计算最后⼀列类别的熵
#如果改变数值，可以计算信息增益⽐中，数据集D 关于每个特征的经验熵
numSamples = len (dataSet )
labelCounts = {}
#根据样本标签计算每⼀类的样本个数
for featVec in dataSet :
currentLabel = featVec [feature ]
if currentLabel not in labelCounts .keys ():
labelCounts [currentLabel ] = 0
labelCounts [currentLabel ] += 1
Entropy = 0.0
for key in labelCounts :
prob = float (labelCounts [key ])/numSamples
Entropy = Entropy - prob *log (prob ,2)
return Entropy
ID3算法存在的问题：
g (D ,A )H (D )H (D ∣A )g (D ,A )=H (D )−H (D ∣A )
H (D )=−log ∑k =1K ∣D ∣∣C ∣
k 2∣D ∣∣C ∣k ∣C ∣k ∣D ∣H (D ∣A )=H (D )=∑i =1n ∣D ∣∣D ∣i i −log ∑i =1n ∣D ∣∣D ∣i ∑k =1K ∣D ∣i ∣D ∣ik 2∣D ∣i ∣D ∣ik n ∣D ∣i ∣D ∣D ik
ID3采⽤信息增益⼤的特征优先建⽴决策树的节点。很快就被⼈发现，在相同条件下，取值⽐较多的特征⽐取值少的特征信息增益⼤。⽐如⼀个变量有2个值，各为1/2，另⼀个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的⽐取2个值的信息增益⼤。如果校正这个问题呢？
C4.5算法
信息增益⽐
针对利⽤信息增益计算要选择的特征会会偏重选择特征值较多的特征的问题，利⽤数据集D关于特征A取值 的熵进⾏校正。
其中，是特征A取值的个数。针对这⼀改变，将数据集D关于特征A的熵进⾏计算。
#计算单个特征的熵
def calFeatureEntropy (dataSet ):
numSamples = len (dataSet )
featureCounts = {}
featureEntropy = []
for i in range (len (dataSet [0])-1):
Entropy = calEntropy (dataSet ,feature =i )
featureEntropy .append (Entropy )
return featureEntropy
以上是针对不同的算法得到不同的特征重要性衡量⽅法，接下来就要根据计算来选择最好的特征了。⽆论是信息增益还是信息增益⽐，都是⼀个寻找最⼤的值的过程，也就是如果满⾜得到的信息增益⽐baInfoGain ⼤就就变换baInfoGain 。
'''
使⽤信息增益计算最好的特征，返回特征列的索引
这实现起来很有意思啊
info 计算条件尚的⽅法，默认id3，也可以设置为C54
'''
def chosBestFeatureToSplit (dataSet ,info ='id3'):
numFeatures = len (dataSet [0])-1
if info == 'id3':
featureEntropy = ones ((numFeatures ,1))
elif info =='c54':
featureEntropy = calFeatureEntropy (dataSet )
baEntropy = calEntropy (dataSet )
baInfoGain = 0.0
baFeature = -1
for i in range (numFeatures ):
#我靠，这⽐C++简单多了
featList = [example [i ] for example in dataSet ]
uniqueVals = t (featList ) #⽤t 创建⽆序不重复集合
newEntropy = 0.0
for value in uniqueVals :
subDataSet = splitDataSet (dataSet ,i ,value )
prob = len (subDataSet )/float (len (dataSet ))
newEntropy += prob *calEntropy (subDataSet )
infoGain = baEntropy - newEntropy
infoGain = infoGain /featureEntropy [i ]
if (infoGain >baInfoGain ):
baInfoGain = infoGain
baFeature = i
return baFeature
3.1.2 决策树⽣成
H (D )A g (D ,A )=R H (D )
A g (D ,A )
H (D )=
A −log ∑i =1n ∣D ∣∣D ∣i 2∣D ∣∣D ∣i n
输⼊：训练数据集D，特征集A [实现的时候没有使⽤：阈值 ]
输出：决策树T
[1]. 若D中所有实例属于同⼀类，则为单节点树，并将类作为该点的类标记，返回[2]. 若A=，则为单节点树，并将D中实例数最⼤的类作为该节点的类标记，返回T
[3]. 否则计算各个特征对数据集D的信息增益（⽐），选择信息增益（⽐）最⼤的特征[4]. 如果的信息增益⼩于阈值，则置T为单结点树，并将D中实例数最⼤的类作为该节点的类标记，返回T
已连接不可上网[5]. 否则，对的每⼀种可能值，依将D分割为若⼲⾮空⼦集，将中实例数最⼤的类作为类标记，构建⼦节点，由结点及其⼦节点构成树T，返回T
[6]. 对第个⼦节点，以为训练集，以为特征集，递归调⽤前⾯五步，得到，返回据算法步骤使⽤python实现，参考了《机器学习实战》，并有⼀些细微改动。
''' 多数表决，classCount ，字典，按照标签存储每个标签预测的个数 '''
def majorityCnt (classList ):
classCount = {}
for vote in classList :
if vote not in classCount .keys ():
classCount [vote ] = 0
classCount [vote ] += 1
初见美
#operator.itemgetter(1) 选择第⼀个域的值 相当于定义了⼀个函数
#sorted 可以对list 或者iterator 进⾏排序 true 降序排列
sortedClassCount = sorted (classCount .items (),key = operator .itemgetter (1),rever = True )
return sortedClassCount [0][0]
def createTree (dataSet ,labels ,info = 'id3'):
路由器哪家好
classList = [example [-1] for example in dataSet ]
#如果都是⼀类则 返回这⼀类作为类标签 第[1]步
if classList .count (classList [0]) == len (classList ):
return classList [0]
# 所有的特征都进⾏过分⽀，只剩下类别列，进⾏投票判决[$A=\emptyt$] 第[2]步
if len (dataSet [0]) == 1:
return majorityCnt (classList )
# 选择信息增益最⼤的特征，返回的是特征的序号 第[3]步学习期
bestFeat = chosBestFeatureToSplit (dataSet ,info )
bestFeatLabel = labels [bestFeat ]
myTree = {bestFeatLabel :{}} #递归构造树
del (labels [bestFeat ])
'''第[5]步 及 第[6]步，计算特征每个取值的集，构建⼦结点，然后递归前⾯⼏步构造树
没有对阈值的计算，如果计算的话，可以在chosBestFeatureToSplit （）设置阈值，如果⼩于阈值，
返回⼀个特征标号和⼀个标志，然后构造单节点树即可'''
featValues = [example [bestFeat ] for example in dataSet ]
uniqueVals = t (featValues )
for value in uniqueVals :
subLabels = labels [:]
myTree [bestFeatLabel ][value ] = createTree (splitDataSet (dataSet ,bestFeat ,value ),subLabels )
return myTree
这两个算法的实现没有采⽤剪枝，所以这⾥贴出完整代码，所⽤数据集都是《机器学习实战》中附加的。
ϵC k T C k T
∅T C k A g
A g ϵC k A g a i A =g a i D i D i i D i A −A g T i T i
# -*- coding: utf-8 -*-
''' Created on Oct 12, 2010 Decision Tree Source Code for Machine Learning in Action Ch. 3 @author: Li '''
from math import log
import operator
import treePlotter
def CreatDataSet():
dataSet =[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]
labels =['no surfacing','flippers']
return dataSet,labels
def calEntropy(dataSet):
def calFeatureEntropy(dataSet):
def splitDataSet(dataSet,axis,value):
def chosBestFeatureToSplit(dataSet,info ='id3'):
def majorityCnt(classList):
def createTree(dataSet,labels,info ='id3'):
新加坡读研''' 不是C++ 指针实现意义上的树，使⽤Python字典实现，嵌套字典结构存储树结构递归查找树，到节点为⽌ '''
def classify(inputTree,featLabels,testVec):
firstStr = inputTree.keys()[0]
condDict = inputTree[firstStr]
featIndex = featLabels.index(firstStr)
for key in condDict.keys():
if testVec[featIndex]== key:
if type(condDict[key]).__name__ =='dict':
classLabel = classify(condDict[key],featLabels,testVec)
el:
classLabel = condDict[key]
return classLabel ##存储树结构
def storeTree(inputTree,fileName):
import pickle
fw =open(fileName,'w')
pickle.dump(inputTree,fw)
fw.clo()
##加载树结构
def loadTree(fileName):
import pickle
fr =open(fileName)
return pickle.load(fr)
def main():
fr =open('')
序数词英语1到20len =[inst.strip().split('\t')for inst adlines()]
lensLabels =['age','prescript','astigmatic','tearRate']
lenTree = createTree(len,lensLabels,info='c54')
return len
if __name__ =="__main__":
len = main()
3.2 CART(回归树和决策树)
ID3等不能处理连续型数据，只能事先将连续型变量处理成离散型，才可以。CART假设决策树是⼆叉树，等价于递归⼆分每个特征，因此能够便于处理连续数据，即可⽤于回归⼜可⽤于分类。
【区别，最主要的根据特征⼆分数据集，因此需要选择好特征和特征值，也就是特征选择会发⽣变化】
3.2.1 特征选择
下⾯根据统计学习⽅法，及机器学习实战，实现了分类回归树的三种叶⼦节点计算⽅式和误差计算⽅法。
3.2.1.1 回归——最⼩⼆乘
