Fork me on GitHub

决策树

介绍决策树及其算法实现

kNN算法可以完成很多的分类任务,但是它最大的缺点就是无法给出数据的内在含义,决策树的主要优势就在于数据形式非常容易理解。决策树的一个基本任务就是为了理解数据中所蕴含的知识信息,因此决策树可以使用不熟悉的数据集合,并从中提取出一系列规则,这些机器根据数据创建规则的过程就是机器学习的过程。决策树也是专家系统中经常使用的算法。

决策树的构造

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

我们所需要解决的第一个问题就是,当前数据集哪个特征在划分数据分类时起决定性作用,而为了找到决定性特征,划分出最好的结果,我们必须评估每个特征。下面展示创建集合分支的伪代码函数createBranch():

1
2
3
4
5
6
7
8
9
检测数据集中的每个子项是否属于同一分类:
if so return 类标签
else
寻找划分数据集的最好特征
划分数据
创建分支节点
for 每个划分的自己
调用函数createBranch()并增加返回结果到分支节点中
return 分支节点

决策树的一般流程

  • 收集数据
  • 准备数据:树构造方法只适用于标称型数据,因此数值型数据必须离散化
  • 分析数据:可以使用任何方法,构造树完成以后,应该检查图形是否符合预期
  • 训练算法:构造树的数据结构
  • 测试算法:使用经验树计算错误率
  • 使用算法

信息增益

划分数据集的大原则是:将无序的数据变得更加有序。组织杂乱无章数据的一种方法就是使用信息论度量信息。在划分数据集前后发生的信息变化称为信息增益,获得信息增益最高的特征就是最好的选择。在求解信息增益之前,我们需要先计算“熵”——信息的期望值。

分类$x_i$的信息定义为$l(x_i)=-log_2p(x_i)$,$p(x_i)$代表选择该分类的概率

那么熵则等于$H=-\sum_{i=1}^np(x_i)log_2p(x_i)$,下面这个函数是用于计算给定数据集的熵

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
from math import log

# 创建一个简单的数据集用于测试
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

# 计算给定数据集的熵
def calcShannonEnt(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) #log base 2
return shannonEnt

# 测试熵计算函数
myDat,labels = createDataSet()
print(calcShannonEnt(myDat))
myDat[0][-1]='maybe'
print(calcShannonEnt(myDat))

熵越高,则混合的数据也就越多(即越混乱),之前的分类为两种即yes和no,熵值输出为0.97,我们再添加一个分类maybe观察熵值变化。输出如下

1
2
3
0.9709505944546686
[[1, 1, 'maybe'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
1.3709505944546687

即一个数据集里面标签越多,分类越混乱,熵越大。

划分数据集

分类算法除了需要测量信息熵,还需要划分数据集,度量划分数据集的熵,以便判断当前是否正确地划分了数据集。我们将对每一个特征划分数据集的结果计算一次信息熵,然后判断哪个特征划分的数据集是最好的划分方式。

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
# 按照给定特征划分数据集
'''
@dataSet:待划分的数据集
@axis:划分数据集的特征
@value:需要返回的特征的值
'''
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

# 测试划分数据集函数
a = [1,2,3]
b = [4,5,6]
a.append(b)
print("append",a)
c = [7,8,9]
c.extend(b)
print("extend",c)
print(splitDataSet(myDat,0,1))
print(splitDataSet(myDat,0,0))

输出

1
2
3
4
append [1, 2, 3, [4, 5, 6]]
extend [7, 8, 9, 4, 5, 6]
[[1, 'maybe'], [1, 'yes'], [0, 'no']]
[[1, 'no'], [1, 'no']]

选择最好的划分方式

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
# 遍历整个数据集,循环计算熵和splitDataSet()函数,找出最好的特征划分方式
'''
函数中调用的数据要满足一定的要求:数据必须是一种由列表元素组成的列表,而且所有列表元素都要具有相同的数据长度;
数据的最后一列或者每个实例的最后一个元素是当前实例的类别标签
'''
def chooseBestFeatureToSplit(dataSet):
# 有一个长度是标签所以-1
numFeatures = len(dataSet[0]) - 1
# 数据集划分之前的熵
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeature = -1
# 遍历数据集中所有特征
for i in range(numFeatures):
# 将数据集中所有第i个特征值或所有可能存在的值写入新的list中
featList = [example[i] for example in dataSet]
# 将list转化为set重复值
uniqueVals = set(featList)
# 初始化新的熵值
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
# 比较所有特征中的信息增益,返回最好特征划分的索引值
if (infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature

# 测试函数
print(chooseBestFeatureToSplit(myDat))

输出结果

1
0

递归构建决策树

目前我们已经学习了从数据集构造决策树算法所需要的子功能模块,其工作原理如下:得到原始数据集,然后基于最好的特征属性值划分数据集,由于特征值可能多于两个,因此可能存在大于两个分支的数据集划分。第一次划分之后,数据将被向下传递到树分支的下一个结点,在这个结点上,我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。

递归结束的条件:程序遍历完所有的属性,或者每个分之下所有的实例都有相同的分类。

如果数据集已经处理了所有属性,但是类标签依然不是唯一的,此时我们需要决定如何定义该节点,在这种情况下,我们通常会采用多数表决的方式决定该叶子节点的分类。

接下来的代码由于涉及迭代,理解起来还是有点费心的

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
45
46
47
48
49
50
# knn分类器
def majorityCnt(classList):
classCount = {}
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]

# 创建树
'''
@dataSet:数据集
@labels:标签列表,包含了数据集中所有特征标签,算法本身不需要这个变量但是为了给出数据的明确含义,我们将他作为一个输入参数提供。
'''
def createTree(dataSet, labels):
# 将所有数据标签添加到列表中
classList = [example[-1] for example in dataSet]
# 如果集合中类别完全相同,则停止划分,即列表中只有该标签
if classList.count(classList[0]) == len(classList):
return classList[0]
'''
递归函数的第二个停止条件是使用完了所有特征,仍然不能将数据集划分成仅包含唯一类别的分组。由于第二个条件无法简单地返回唯一的
类标签,这里使用majorityCnt()挑选出现次数最多的类别作为返回值
'''
print("dataSet[0]:",dataSet[0])
if len(dataSet[0]) == 1:
return majorityCnt(classList)
# 选择最优的分类属性
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat]
# 使用字典类型存储树
myTree = {bestFeatLabel: {}}
# 将最优属性从标签中删除,即下次接着从剩下属性中取最优
del (labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet]
# 将list转化为set去掉重复值
uniqueVals = set(featValues)
for value in uniqueVals:
'''
将类标签复制到subLabels中,python中函数参数使列表类型时,参数使按照引用方式传递的。为了保证每次调用函数createTree()时,
不改变原始列表内容,使用新变量代替原始列表
'''
subLabels = labels[:]
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
return myTree

# 测试函数
myTree = createTree(myDat,labels)
print(myTree)

输出结果

1
2
3
4
dataSet[0]: [1, 1, 'maybe']
dataSet[0]: [1, 'maybe']
dataSet[0]: ['maybe']
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'maybe'}}}}

最后输出的结果观感可能比较差,可以借助数据可视化的手段具体化详细内容可查看《机器学习实战》决策树相应章节

测试算法:使用决策树执行分类

在执行数据分类时,需要使用决策树以及构造决策树的标签向量。然后程序比较测试数据与决策树上的数值,递归执行该过程直到进入叶子节点,最后将测试数据定义为叶子阶段所属的类型。该函数也是利用了迭代过程,为了帮助理解,我添加了很多print()函数

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
'''
使用决策树的分类函数
该函数也是一个递归函数,在存储带有数据特征的数据会面临一个问题:程序无法确定特征在数据集中的位置,特征标签列表将帮助程序处理这个问题
@inputTree:决策树模型
@featLabels:标签向量
@testVec:测试样本
'''
def classify(inputTree, featLabels, testVec):
# 树的第一个键,即根节点
firstSides = list(inputTree.keys())
firstStr = firstSides[0]
print("firstStr:",firstStr)
# 第一个键对应的值(字典)
secondDict = inputTree[firstStr]
print("secondDict:", secondDict)
# 第一个键(特征)在特征列表中的索引
featIndex = featLabels.index(firstStr)
print("featIndex:", featIndex)
# key是相应特征对应测试列表中的的取值,也即是父子节点间的判断
key = testVec[featIndex]
print("key:", key)
valueOfFeat = secondDict[key]
print("valueOfFeat:",valueOfFeat)
# 当valueofFeat不再是字典类型时,退出迭代,此时已经得到分类结果
if isinstance(valueOfFeat, dict):
classLabel = classify(valueOfFeat, featLabels, testVec)
print("classLabel:",classLabel)
else:
classLabel = valueOfFeat
print("classLabel:", classLabel)
return classLabel

# 测试函数
print(labels)
print(myTree)
# 因为之前的删除操作,所以此处恢复标签向量
labels = ['no surfacing','flippers']
print(classify(myTree,labels,[1,0]))

输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
['flippers']
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'maybe'}}}}
firstStr: no surfacing
secondDict: {0: 'no', 1: {'flippers': {0: 'no', 1: 'maybe'}}}
featIndex 0
key: 1
valueOfFeat: {'flippers': {0: 'no', 1: 'maybe'}}
firstStr: flippers
secondDict: {0: 'no', 1: 'maybe'}
featIndex 1
key: 0
valueOfFeat: no
classLabel: no
classLabel: no
no

使用算法:决策树的存储

构造决策树是很耗时的任务,然而用创建好的决策树解决分类问题,则可以很快完成。因此为了节省计算时间,最好能够在每次执行分类时调用已经构造好的决策树。为了解决这一问题需要使用python模块pickle序列化对象。序列化对象可以在磁盘行保存对象,并在需要的时候读取出来。任何对象都可以执行序列化操作。

序列化 (Serialization)将对象的状态信息转换为可以存储或传输的形式的过程。在序列化期间,对象将其当前状态写入到临时或持久性存储区。以后,可以通过从存储区中读取或反序列化对象的状态,重新创建该对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 使用pickle模块存储决策树,pickle模块读写过程中一定要采用二进制读写模式,不然会报错
# 存储模型
def storeTree(inputTree, filename):
import pickle
fw = open(filename, 'wb+')
pickle.dump(inputTree, fw)
fw.close()

# 加载模型
def grabTree(filename):
import pickle
fr = open(filename,'rb')
return pickle.load(fr)

# 测试函数
storeTree(myTree,"classifierStorage.txt")
print("加载模型:",grabTree("classifierStorage.txt"))

输出

1
加载模型: {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'maybe'}}}}

参考

《机器学习实战》. Peter Harrington

序列化. 百度百科

-------------The End-------------