第三章 决策树的构造
- 决策树简介
- 在数据集中度量一致性
- 使用递归构造决策树
- 使用Matplotlib绘制树形图
决策树主要优势：数据形式非常容易理解。
优点：
计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征。
缺点：
可能会产生过度匹配问题，即过拟合问题。
例子：
长方形：判断模块
椭圆形：终止模块
左右箭头：分支
3.1 决策树的构造
构造决策树：
步骤：选取起决定性左右的特征作为根节点，根据根节点特征的几个类别的值划分原始数据集为几个数据子集，如是否包含"曲棍球"这个特征，以其为根节点后，划分训练数据集为包含"曲棍球"这个训练数据集，和不包含。分别在两个子训练数据集上，再选取其他特征，不必再考虑这个特征。直到在训练子集全为一类。
如果所有的数据都是包含"曲棍球"，那么是否包含"曲棍球"这个特征是最好的特征了，因为这个特征能够很好的将数据全部分为一类，算法结束，否则算法需要继续寻找最好的特征。为此需要用上信息论里面的熵(entropy)的概念，并用基于熵的ID3算法划分数据。
伪代码函数createBranch():
Figure3-1: createBranch()函数
信息增益
划分数据集的最大原则: 将无序的数据变得更加有序。
信息增益(information gain): 在划分数据集之前之后信息发生的变化
熵(entropy): 信息的期望值，或者集合信息的度量方式。
信息定义：
如果待分类的事务可能划分在多个分类之中，则xi的信息定义为：
其中，p(xi)是选择该分类的概率。
信息期望值：
其中，n是分类的数目。
理解熵：
计算给定数据集的熵：
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 3 22:59:01 2015
@author: shifeng
"""
from math import log
def calcShnnonEnt(dataSet):
numEntries = len(dataSet) #数据集需要是每行一个训练样本，并且最后一列为训练labels
labelCounts = {}
for featVec in dataSet:
currentLabel = featVec[-1] #对每个样本来说，取其label，即某行最后一个值
# if currentLabel not in labelCounts.keys():
# labelCounts[currentLabel] = 0
# labelCounts[currentLabel] += 1
labelCounts[currentLabel] = labelCounts.get(currentLabel, 0)+1 #此处就体现了字典的get()函数的威力，代替上面三行
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key])/numEntries #选择该分类的概率值
shannonEnt -= prob*log(prob, 2) #计算信息熵的期望值
return shannonEnt
def createDataSet():
dataSet = [[1,1,"yes"],[1,1,"yes"],[1,0,"no"],[0,1,"no"],[0,1,"no"]]
labels = ["no surfacing","flippers"]
return dataSet, labels
#myDat,labels = trees.createDataSet()
Figure3-2: 计算熵的函数测试
划分类标: 3个yes, 2个no, H=-0.6log2(0.6)-0.4log2(0.4) = 0.97 < 1, 需要一枚重量不均匀的硬币即可区分。而增加了一个类标maybe, 变成: 1个yes, 1个maybe, 3个no, H=-0.2log2(0.2)-0.2log2(0.2)-0.6log2(0.6)=1.37<2, 至少需要2枚硬币区分，增加一个类标，不确定性增加了，变得更“混乱”了。
划分数据集
按照给定特征划分数据集：
def splitDataSet(dataSet, axis, value):
'''
axis：特征的坐标。axis=0时,第0个特征其值可能为0或1,
value=1时，dataSet前3个都符合，从而得到子集[[1,"yes"],[1,"yes"],[0,"no"]]。
'''
retDataSet = [] #需要新创建一个列表变量，因列表的参数是按照引用方式传递的
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
Figure3-3: 划分数据子集测试
选择最好的数据集划分方式：
def chooseBestFeatureToSplit(dataSet):
'''
数据集格式：
1.由列表元素组成的列表，并且所有列元素都要具有相同数据长度。
2.数据最后一列为label.
如同createDataSet()中dataSet变量的数据集
'''
numFeatures = len(dataSet[0]) -1 #特征的个数，随便第一个实例的长度，去掉最后一个标签。
baseEntropy = calcShnnonEnt(dataSet)
bestInfoGain = 0.0 #定义基尼指数
bestFeature = -1
for i in range(numFeatures): #对第i个特征处理，
featList = [example[i] for example in dataSet]
uniqueVals = set(featList) #第i个特征的属性值全放在集合里面，第0个特征有属性值0或者1，
newEntropy = 0.0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value) #对第i个特征，其值为value划分数据
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob*calcShnnonEnt(subDataSet) #调用计算熵的公式。
infoGain = baseEntropy - newEntropy #计算基尼指数。利用基尼指数得到熵最低的特征。
if infoGain > bestInfoGain:
bestInfoGain = infoGain
bestFeature = i
return bestFeature
Figure3-4: 选择最好的特征
计算选择第0个特征作为划分特征：
Figure3-5: 计算最好的选择特征
递归构建决策树
工作原理：得到原始数据集，基于最好的属性值划分数据集，第一次划分后，再次划分数据。因此可以递归处理数据集。
递归结束的条件：划分数据集所有属性，或者每个分支下的所有实例都具有相同的分类。
如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时我们通常采用多数表决的方法决定该叶子节点的分类。
<span style="font-size:14px;">def splitDataSet(dataSet, axis, value):
'''
axis：特征的坐标。axis=0时,第0个特征其值可能为0或1,
value=1时，dataSet前3个都符合，从而得到子集[[1,"yes"],[1,"yes"],[0,"no"]]。
'''
retDataSet = [] #需要新创建一个列表变量，因列表的参数是按照引用方式传递的
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)</span>
子功能模块构建好了后，将其组合起来，以得到我们需要的结果：树
<span style="font-size:14px;"># -*- coding: utf-8 -*-
"""
Created on Thu Sep 3 22:59:01 2015
@author: shifeng
"""
import operator
from math import log
def calcShnnonEnt(dataSet):
numEntries = len(dataSet) #数据集需要是每行一个训练样本，并且最后一列为训练labels
labelCounts = {}
for featVec in dataSet:
currentLabel = featVec[-1] #对每个样本来说，取其label，即某行最后一个值
# if currentLabel not in labelCounts.keys():
# labelCounts[currentLabel] = 0
# labelCounts[currentLabel] += 1
labelCounts[currentLabel] = labelCounts.get(currentLabel, 0)+1 #此处就体现了字典的get()函数的威力，代替上面三行
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key])/numEntries #选择该分类的概率值
shannonEnt -= prob*log(prob, 2) #计算信息熵的期望值
return shannonEnt
def createDataSet():
dataSet = [[1,1,"yes"],[1,1,"yes"],[1,0,"no"],[0,1,"no"],[0,1,"no"]]
labels = ["no surfacing","flippers"]
return dataSet, labels
#myDat,labels = trees.createDataSet()
def splitDataSet(dataSet, axis, value):
'''
axis：特征的坐标。axis=0时,第0个特征其值可能为0或1,
value=1时，dataSet前3个都符合，从而得到子集[[1,"yes"],[1,"yes"],[0,"no"]]。
'''
retDataSet = [] #需要新创建一个列表变量，因列表的参数是按照引用方式传递的
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
def chooseBestFeatureToSplit(dataSet):
'''
数据集格式：
1.由列表元素组成的列表，并且所有列元素都要具有相同数据长度。
2.数据最后一列为label.
如同createDataSet()中dataSet变量的数据集
'''
numFeatures = len(dataSet[0]) -1 #特征的个数，随便第一个实例的长度，去掉最后一个标签。
baseEntropy = calcShnnonEnt(dataSet)
bestInfoGain = 0.0 #定义基尼指数
bestFeature = -1
for i in range(numFeatures): #对第i个特征处理，
featList = [example[i] for example in dataSet]
uniqueVals = set(featList) #第i个特征的属性值全放在集合里面，第0个特征有属性值0或者1，
newEntropy = 0.0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value) #对第i个特征，其值为value划分数据
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob*calcShnnonEnt(subDataSet) #调用计算熵的公式。
infoGain = baseEntropy - newEntropy #计算基尼指数。利用基尼指数得到熵最低的特征。
if infoGain > bestInfoGain:
bestInfoGain = infoGain
bestFeature = i
return bestFeature
def majorityCnt(classList): #classList为类标例表
classCount = {}
for vote in classList:
classCount[vote] = classCount.get(vote,0)+1
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
def createTree(dataSet, labels): #labels = ["no surfacing","flippers"],其值为特征名
classList = [example[-1] for example in dataSet] #取dataSet每个实例的最后一个元素，也即label
if classList.count(classList[0]) == len(classList): #类别完全相同则停止划分，取第一个就行了，第一个的个数等于所有的个数
return classList[0]
if len(dataSet[0]) == 1: #遍历完所有特征时，返回label出现次数最多的
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat] #labels列表中包含了具体的属性值
myTree = {bestFeatLabel:{}} #关键所在
del(labels[bestFeat]) #类标的某个特征被选择了后，就不必再考虑了
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:]
#递归调用createTree()函数，并且将返回的tree插入到myTree字典中，
#利用最好的特征划分的子集作为新的dataSet传入到createTree()函数中。
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
return myTree
</span>
Figure3-6: 分类结果
由于我们需要得到一颗决策树，用字典这种数据结构再好不过，字典嵌套构成树的整个结构，如果字典的属性值为类标签，那么子节点就是叶子节点，如果字典的属性值为字典，那么子节点是另一个判断节点。
另外，多数表决的方法在多数情况下卤主也不确定是否好，还需继续探究。
3.2 在python中使用Matplotlib注解绘制树形图
这部分跟机器学习相关性不大，主要是熟悉python可视化包Matplotlib画图的功能，方便展示给他人。有兴趣可参考教材。
3.3 测试和存储分类器
这部分有个比较有用的是关于决策树的存储，用到了pickle模块序列化对象。
3.4 示例：使用决策树预测隐形眼睛类型
目标：通过决策树预测患者需要佩戴的隐形眼睛类型。
隐形眼睛数据集：
Figure3-7: lenses data
测试结果：
Figure3-8: lenses数据测试结果
3.5 小结
这里主要是采用ID3算法划分数据集，用递归的方法将数据集转化为决策树，并可用pickle模块存储决策树的结构。
ID3算法无法处理直接数值型数据，需要将其化为标量型数值。
决策树最大的缺点在于过拟合问题。在构建树的时候，其能够完全匹配实验数据，但是这并不是我们想要的，为此，可以删掉一些只增加了很少信息的节点，将其并入到其他叶子节点中，或者裁剪一些分支。具体决策树的很多问题也待整理。