目录
什么是决策树
决策树的节点
决策树的特点
决策树的基本算法
决策树的划分选择
如何选择最优划分属性
方法一：信息增益
方法二：增益率
小总结
方法三：基尼指数
什么是决策树
分类决策树模型是一种描述对实例进行分类的树形结构，它由节点和有向边组成
决策树的节点
分为内部节点和叶节点
内部节点——代表一个特征或属性
叶节点——代表一个类
如下图 ，黑色的为内部节点，红色的为叶节点：
决策树的特点
1.对属性进行“测试”即对就决策过程中的问题进行判定
2.决策树上的每条路径都是一个判定测试序列
决策树的最终学习目的是为了产生一颗泛化能力强即能够有效处理未知样本的决策树
决策树的基本算法
注意：当某一判定测试序列的结果为空（无对应样本），将当前节点标记为叶子节点并进行回溯——回到父节点，以父节点的测试结果为准
决策树的划分选择
优秀的决策树应该具备优秀的划分属性、高纯度的节点
如何选择最优划分属性
方法一：信息增益
信息熵——度量样本集合纯度的指标之一，信息熵（Ent(D)）的值越小，则样本集合（D）的纯度越高，Ent(D)最小为0，最大值为log2|y|
Ent(D)计算公式：
PS：Pk为第k类样本在样本集合D中所占的比例
当p=0或p=1时，样本集合纯度百分百。
原因：
信息熵的python代码实现：该函数可计算数据集的香农熵，将数据集的最后一列设为键值，并为所有可能的分类创建字典，其中若发现新分类（新键值），则扩展字典并加入新键值。
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}#字典
for featVec in dataSet: #the the number of unique elements and their occurance
currentLabel = featVec[-1]
#扩展字典添加新键值
if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1#统计键值出现的次数
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key])/numEntries#统计某一键值出现频率
shannonEnt -= prob * log(prob,2) #log base 2
return shannonEnt
信息增益基于信息熵（Ent(D)）
用信息增益划分最优属性的python代码：以下代码为信息增益公式的代码形式，是实现信息增益划分属性的核心：
baseEntropy = calcShannonEnt(dataSet)#得到总熵值 #得到每种决策属性的比例 prob = len(subDataSet)/float(len(dataSet)) #得到各个特征值对应的熵 newEntropy += prob * calcShannonEnt(subDataSet)
从下列代码我学习到了：
1.python的列表推导式：[表达式 for 变量 in 列表]；形如：[example[i] for example in dataSet]
以行的形式遍历数据集，并取出第i列；
2.利用set集合的性质取出列表中的重复元素，得到某一属性的分类标签列表。
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 #the last column is used for the labels
baseEntropy = calcShannonEnt(dataSet)#得到总熵值
bestInfoGain = 0.0; bestFeature = -1
for i in range(numFeatures): #iterate over all the features
featList = [example[i] for example in dataSet]#create a list of all the examples of this feature
#利用set内值不重复的性质得到某一属性的分类标签列表
uniquevals = set(featList) #get a set of unique values
newEntropy = 0.0
#遍历特征值得到相应的数据集
for value in uniquevals:
subDataSet = splitDataSet(dataSet, i, value)
#得到每种决策属性的比例
prob = len(subDataSet)/float(len(dataSet))
#得到各个特征值对应的熵
newEntropy += prob * calcShannonEnt(subDataSet)
#计算信息增益
infoGain = baseEntropy - newEntropy #calculate the info gain; ie reduction in entropy
if (infoGain > bestInfoGain): #compare this to the best gain so far
bestInfoGain = infoGain #if better than current best, set to best
bestFeature = i
#返回最优划分属性的索引值
return bestFeature #returns an integer
ID3决策树学习算法就是以信息增益为准则来划分属性的算法
特点：一般而言，信息增益越大，则意味着该属性越适合作为划分属性；信息增益对可取值数目较多的属性有所偏好。
方法二：增益率
IV(a):属性a的固有值，属性a的可能取值数目越大，IV(a)的值通常越大
增益率基于IV(a)
公式如下：
特点：增益率准则对可取数目较少的属性有所偏好。
小总结
以上两种方法各有特点亦为缺点，故可采用一个启发式方法：先从候选划分属性中找到信息增益高于平均水平的属性，再从中选取增益率最大的。
方法三：基尼指数
分类问题中，设D中有K个类，样本点属于第K类的概率为Pk，则概率分布的基尼值定义为：
给定数据集D，属性a的基尼指数定义为：
故知Gini(D)越小，数据集D的纯度越高，因此在选择划分属性时，选择那个使得划分后基尼指数最小的属性作为最优划分属性。
决策树相关代码理解
通过一些方法得到最优划分属性后，我们需要建造决策树；一棵决策树里包含很多分支，为了得到这些分支，我们需要一个可以按照给定特征值划分数据集的函数，如下列代码：
按照给定特征值划分数据集：
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
#判断featVec数组的第axis个是否等于value
reducedFeatVec = featVec[:axis]
#从0到axis #chop out axis used for splitting
reducedFeatVec.extend(featVec[axis+1:])
#从axis到最后 所以reducedFeatVec就是一列除去特征值的数组
retDataSet.append(reducedFeatVec)
#retDataSet就是符合条件featVec[axis] == value：并所有除去特征值的数组的集合
return retDataSet
我学到的点：
1.代码中extend函数的作用是直接将需要添加的部分拆解后逐个扩展在列表最后：
>>>a=[1,2,3] >>>b=[4,5,6] >>>a.extend(b) >>>a [1,2,3,4,5,6]
而append函数的作用是把需要添加的部分完整地以列表形式添加在列表最后：
>>>a=[1,2,3] >>>b=[4,5,6] >>>a.append(b) >>>a [1,2,3,[4,5,6]]
2. featVec[:axis]代表featvec数组从头到第axis个元素；featVec[axis:]代表featvec数组从第axis个元素到尾；featVec[-1]代表数组的最后一个元素。
创建树的函数代码：
def createTree(dataSet,labels):
#遍历取出数据集的最后一列，即取出每条数据的类别 [example[-1]代表每行的的最后一个元素
classList = [example[-1] for example in dataSet]
#若classList[0]类别的个数等于总类别个数，则代表每条数据的类别都相等（类别完全相同）
if classList.count(classList[0]) == len(classList):
#返回该类别，停止继续划分
return classList[0]#stop splitting when all of the classes are equal
#若dateset的每条数据只剩一个元素则代表已经没有特征可以继续划分
if len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSet
#返回出现次数最多的类别
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)#获取最优划分属性
bestFeatLabel = labels[bestFeat]#最优划分属性的标签
myTree = {bestFeatLabel:{}}
del(labels[bestFeat])
#取出最优划分属性对应的所有的值
featValues = [example[bestFeat] for example in dataSet]
#利用set内值不重复的性质得到最优划分属性对应的的互不相同的值
uniquevals = set(featValues)
for value in uniquevals:
subLabels = labels[:] #copy all of labels, so trees don't mess up existing labels
# print(subLabels)
#递归调用createTree函数 splitDataSet(dataSet, bestFeat, value)为符合条件并除去特征值的所有数组的集合
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
return myTree
实现决策树可视化：
'''
Created on Oct 14, 2010
@author: Peter Harrington
'''
import matplotlib.pyplot as plt
decisionNode = dict(box, fc="0.8")
leafNode = dict(box, fc="0.8")
arrow_args = dict(arrow)
def getNumLeafs(myTree):
numLeafs = 0
firstStr = list(myTree.keys())[0]
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]).__name__=='dict':#test to see if the nodes are dictonaires, if not they are leaf nodes
numLeafs += getNumLeafs(secondDict[key])
else: numLeafs +=1
return numLeafs
def getTreeDepth(myTree):
maxDepth = 0
firstStr = list(myTree.keys())[0]
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]).__name__=='dict':#test to see if the nodes are dictonaires, if not they are leaf nodes
thisDepth = 1 + getTreeDepth(secondDict[key])
else: thisDepth = 1
if thisDepth > maxDepth: maxDepth = thisDepth
return maxDepth
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',
xytext=centerPt, textcoords='axes fraction',
va="center", ha="center", bbox=nodeType, arrowprops=arrow_args )
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)
def plotTree(myTree, parentPt, nodeTxt):#if the first key tells you what feat was split on
numLeafs = getNumLeafs(myTree) #this determines the x width of this tree
depth = getTreeDepth(myTree)
firstStr = list(myTree.keys())[0] #the text label for this node should be this
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
for key in secondDict.keys():
if type(secondDict[key]).__name__=='dict':#test to see if the nodes are dictonaires, if not they are leaf nodes
plotTree(secondDict[key],cntrPt,str(key)) #recursion
else: #it's a leaf node print the leaf node
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
#if you do get a dictonary you know it's a tree, and the first element will be another dict
def createPlot(inTree):
fig = plt.figure(1, facecolor='white')
fig.clf()
axprops = dict(xticks=[], yticks=[])
createPlot.ax1 = plt.subplot(111, frameon=False, **axprops) #no ticks
#createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses
plotTree.totalW = float(getNumLeafs(inTree))
plotTree.totalD = float(getTreeDepth(inTree))
plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0;
plotTree(inTree, (0.5,1.0), '')
plt.show()
#def createPlot():
# fig = plt.figure(1, facecolor='white')
# fig.clf()
# createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses
# plotNode('a decision node', (0.5, 0.1), (0.1, 0.5), decisionNode)
# plotNode('a leaf node', (0.8, 0.1), (0.3, 0.8), leafNode)
# plt.show()
def retrieveTree(i):
listOfTrees =[{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}},
{'no surfacing': {0: 'no', 1: {'flippers': {0: {'head': {0: 'no', 1: 'yes'}}, 1: 'no'}}}}
]
return listOfTrees[i]
#createPlot(thisTree)
输出结果：
