决策树

决策树

最经常使用的数据挖掘算法

其只要优势在于数据形式非常容易理解,分为判断模块(decision block)与终止模块(terminating block)

决策树

  • 优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据
  • 缺点:可能会产生过度匹配问题
  • 适用数据类型:数值型和标称型

该决策树算法能够读取数据集合

决策树的一个重要任务就是了解数据中所蕴含的知识信息,因此其可以使用不熟悉的数据集合并从中提取出一些列规则

本文全部代码以及测试文档

决策树的一般流程

  • 收集数据:可以使用任何方法
  • 准备数据:树构造算法只使用于标称型数据,因此数值型数据必须离散化
  • 分析数据:可以使用任何方法,构造树完成后,我们应该检查图形是否符合预期
  • 训练算法:构造树的数据结构
  • 测试算法:使用经验树计算错误率
  • 使用算法:此步骤可以试用于任何监督学习算法,而使用决策树可以更好地理解数据的内在含义

构造决策树时需要解决的第一个问题就是:当前数据集上哪个特征在划分数据类型时起决定性作用

计算熵

信息增益:在划分数据集之前之后信息发生的变化称为信息增益

:集合信息的度量方式称为Shannon熵,简称熵

现在当前目录下建立tree.py文件,并在里面写下如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from math import log

# 计算给定数据集的shannon熵
def caluShannonEnt(dataSet):
numEntries = len(dataSet)
# 为所有可能分类创建字典
labelCounts = {}
for featVec in dataSet:
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) # 以2为底求对数
return shannonEnt

上诉代码的每一段作用都在里面用注释标明了

为了测试上端函数,我们可以在tree.py文件中建立自己的简单数据集

1
2
3
4
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

然后在命令行中进入当前目录,然后进入python环境

1
2
3
python
import trees
meDat, labels = trees.createDataSet()

效果图如下:

熵越高则混合的数据越多

划分数据集

按照给定特征划分数据集,当我们按照某个特征划分数据集时,就需要将所有符合要求的元素抽取出来

参数:

dataSet:待划分的数据集
axis:划分数据集的特征
value:需要返回的特征的值

1
2
3
4
5
6
7
8
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis] # chop out axis used for splitting
reducedFeatVec.extend(featVec[axis + 1:])
retDataSet.append(reducedFeatVec)
return retDataSet

上面的函数中创建新的list的对象,这是因为:

在python中函数传递的是列表的引用,若该列表在函数中被修改则会影响该列表对象的整个生存周期。为了消除这个不良影响,我们创建一个新的列表对象,以不修改原始数据

接下来我们要选择最好的数据划分方式,遍历整个数据集,循环计算Shannon熵和spiltDataSet()函数,找到最好的特征划分方式

从数据集构造决策树算法所需要的子功能模块,其工作原理如下:

  • 得到原始数据集
  • 然后基于最好的属性值划分数据集
  • 由于特征值可能多余两个,因此可能存在大于两个分支的数据集划分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def chooseBestFeatureToSpilt(dataSet):
numFeatures = len(dataSet[0]) - 1
baseEntropy = caluShannonEnt(dataSet)
bestInfoGain = 0.0; bestFeature = -1
for i in range(numFeatures):
# 创建唯一的分类标签列表
featList = [example[i] for example in dataSet]
uniqueVals = set(featList)
# 从列表中创建集合是python中得到列表中唯一元素值最快的方法
newEntropy = 0.0
for value in uniqueVals:
# 计算每种划分方式的信息熵
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob * caluShannonEnt(subDataSet)
infoGain = baseEntropy - newEntropy
if (infoGain > bestInfoGain):
# 计算最好的信息增益
bestInfoGain = infoGain
bestFeature = i
return bestFeature

第一次划分后,数据将被向下传递到树分支的下一个节点,在这个节点上我们可以再次划分数据。因此,我们可以采用递归的原则处理数据集

数据需要满足的要求

  • 数据必须是一种由列表元素组成的列表,而且所有的列表元素都要具备相同的数据长度
  • 数据的最后一列或者每个实例的最后一个元素是当前实例的类型标签

递归构建决策树

使用分类名称的列表,然后创建键值为classList中唯一值的数据字典,字典对象存储了classCount中每个类标签出现的频率

然后使用operator操作键值排序字典,并返回出现最多的分类名称

还是在tree.py文件中

1
2
3
4
5
6
7
8
9
10
import operator

def majorityCnt(classList):
classCount = {}
for vote in classList:
if vote not in classCount.keys():
classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.iteritems(), key = operator.itemgetter(1),reversed = True)
return sortedClassCount

递归结束的条件是:

程序遍历完所有划分数据集的属性,或者下个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类,则得到一个叶子结点或者终止块

创建树的函数代码

参数:

dataSet:数据集,数据集的要求同上
labels:标签列表,标签列表包含了数据集中所有特征的标签,算法本身并不需要这个变量,但是为了给出数据明确的含义,我们将它作为一个参数输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def createTree(dataSet, labels):
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 = chooseBestFeatureToSpilt(dataSet)
bestFeatLabel = labels[bestFeat]
# 得到列表包含的所有属性值
myTree = {bestFeatLabel:{}}
del(labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:] # 复制类标签,为保护原始数据
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
return myTree

变量myTree包含了很多代表数结构的嵌套的字典,从左边开始,第一个关键字是第一个划分数据集的特征名称,该关键字也是另一个数据字典。第二个关键字是第一个特征划分的数据集,这些关键字是第一个关键字结点的子节点。这些值有可能是类标签,也可能是另一个数据字典。如果值是类标签,则该子节点是叶子结点;反之则是一个判断结点。这种格式不断重复构成了整棵树。

构造树的部分先到此,接下来介绍如何绘制图形

Matplotlib的使用

默认的python环境是不自带Matplotlib的,所以我们需要安装,这里以macOS系统为例

首先先要安装pip,如果你已经安装过pip则直接向下看

1
sudo easy_install pip

接下来使用pip来继续安装

1
sudo pip install matplotlib

这里注意一下,一定要加上sudo,否则会提示你安装错误。网上很多教程都是直接pip,前面没有sudo,我在安装时出现了很多错误浪费了很多时间

安装好之后就可以使用Matplotlib来绘制图形了

使用文本注解绘制树节点

在当前目录下创建新的文件,treePlotter.py,我们关于绘制树的相关函数都会在这个文件中实现

1
2
3
4
5
6
7
8
9
10
11
12
import matplotlib.pyplot as plt

# 定义文本框与箭头格式
decisionNode = dict(boxstyle = "sawtooth", fc = "0.8")
leafNode = dict(boxstyle = "round4", fc = "0.8")
arrow_args = dict(arrowstyle = "<-")

# 绘制带箭头的注解
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
createPlot.axl.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',
xytext=centerPt, textcoords='axes fraction',
va="center", ha="center", bbox=nodeType, arrowprops=arrow_args )

构造注解树

构造注解树时必需解决的第一个问题是:

我们必须知道有多少个叶子结点,以便可以正确确定X轴长度;以及树的层数来确定y轴长度

获取叶子结点的数目和树的层数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def getNumLeaves(myTree):
numLeaves = 0
firstStr = myTree.keys()[0]
secondDict = myTree[firstStr]
# 测试结点的数据类型是否为字典
for key in secondDict.keys():
if type(secondDict[key]).__name__=='dict':
numLeaves += getNumLeaves(secondDict[key])
else:
numLeaves += 1
return numLeaves

def getTreeDepth(myTree):
maxDepth = 0
firststr = 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

预创建树

1
2
3
4
5
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]

保存文件后回到命令行,输入

1
2
3
4
5
import treePlotter
treePlotter.retrieveTree(1)
myTree = treePlotter.retrieveTree(0)
treePlotter.getNumLeaves(myTree)
treePlotter.getTreeDepth(myTree)

效果图如下,函数retrieveTree()主要用于测试,返回预定义的树结构

然后我们要完善刚刚构造的注解树,将下面函数在treePlotter.py中实现,同时重写一下先前的createPlot函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 在父子结点间填充文本信息
def plotMidText(cntrPt, parentPt, txtString):
xMid = (parentPt[0] - cntrPt[0])/2.0 + cntrPt[0]
yMid = (parentPt[1] - cntrPt[1])/2.0 + cntrPt[1]
createPlot.axl.text(xMid, yMid, txtString)

def plotTree(myTree, parentPt, nodeTxt):
# 计算宽与高
numLeaves = getNumLeaves(myTree)
depth = getTreeDepth(myTree)
firstStr = myTree.keys()[0]
cntrPt = (plotTree.xOff + (1.0 + float(numLeaves))/2.0/plotTree.totalW,
plotTree.yOff)
# 标记子节点属性值
plotMidText(cntrPt, parentPt, nodeTxt)
plotNode(firstStr, cntrPt, parentPt, decisionNode)
secondDict = myTree[firstStr]
# 减少y偏移
plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD
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

# 绘制图形
# x轴与y轴的范围都是0.0 ~ 1.0
def createPlot(inTree):
fig = plt.figure(1, facecolor = 'white')
fig.clf()
axprops = dict(xticks=[], yticks=[])
createPlot.axl = plt.subplot(111, frameon = False, **axprops)
# 储存树的宽度
# 树的宽度用于计算放置判断结点的位置,主要的计算原则是将它放在所有叶子结点的中间,而不仅仅是他子节点的中间
plotTree.totalW = float(getNumLeaves(inTree))
# 储存树的深度
plotTree.totalD = float(getTreeDepth(inTree))
# 全局变量xOff, yOff 来追踪已经绘制的结点的位置,以及下一个结点的恰当位置
plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0
plotTree(inTree, (0.5, 1.0), '')
plt.show()

现在让我们验证一下实际效果

1
2
3
reload(treePlotter)
myTree = treePlotter.retrieveTree(0)
treePlotter.createPlot(myTree)

这样,我们就会得到如下的注解树

使用决策树执行分类

绘制树的部分结束了,我们重新回到tree.py中,我们接下来要实现使用决策树算法来分类数据集了

1
2
3
4
5
6
7
8
9
10
11
def classify(inputTree, featLabels, testVec):
firstStr = inputTree.keys()[0]
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

在上面的函数中我们将标签类型转换为引索,这是为了解决程序无法确定特征在数据集中的位置。

特征标签列表将帮助程序处理这个问题

决策树的储存

我们可以将分类器储存在硬盘上,而不用每次对数据分类是重新学习一遍,这也是决策树的优点之一,k-means算法就无法持久化分类器

我们可以预选提炼并储存数据集中包含的知识信息,在需要对事物进行分类是再使用这些知识

我们使用pickle模块来储存决策树

储存决策树的原因:为节省时间,能够在每次执行分类时调用已经构造好的决策树

1
2
3
4
5
6
7
8
9
10
def storeTree(inputTree, fileName):
import pickle
fw = open(fileName,'w')
pickle.dump(inputTree, fw)
fw.close()

def grabTree(fileName):
import pickle
fr = open(fileName)
return pickle.load(fr)

示例:使用决策树预测隐形眼镜类型

步骤:

  • 收集数据:提供的文本文件
  • 准备数据:解析tab键分隔的数据行
  • 分析数据:快速检查数据,确保正确的解析数据内容,使用creatrPlot()函数绘制最终的树形图
  • 训练算法:使用createTree()
  • 测试算法:编写测试函数验证决策树可以正确分类给定的数据实例
  • 使用算法:储存树的结构,以便下次使用时无序重新构造树
1
2
3
4
5
6
reload(treePlotter)
fr = open('lenses.txt')
lenses = [inst.strip().split('\t') for inst in fr.readlines()]
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
lensesTree = trees.createTree(lenses, lensesLabels)
treePlotter.createPlot(lensesLabels)

得到的注解树如下所示:

上图所示的决策树非常好的匹配了实验数据,然而这些匹配选项可能太多了。我们将这种情况称之为过拟合(overfitting)。

为了避免过拟合问题,我们可以裁剪决策树,去掉一些没必要的叶子结点。

小结

决策树分类器就像带有终止块的流程图,终止块表示结果。

开始处理数据时,我们要先测量一下数据集中的熵,然后寻找最优方案划分数据集,知道数据集中的所有数据属于同一分类。

本文采用的构建决策树的算法是ID3算法,该算法可以用于划分标称型数据集。

在构建决策树时,我们通常采用递归的方式将数据集转化为决策树。一般我们不使用新的数据结构,因为python中的字典储存树结点信息已经足够了

决策树算法和以前整理的k-means算法都是结果确定的分类算法,数据实例最终会被明确划分到某个分类中。