机器学习之决策树

顾名思义,决策树是基于树结构进行决策的。一个决策树包含一个根节点、若干个内部结点和若干个叶结点构成的,叶结点对应于决策结果,其他每个结点则对应一个属性测试,每个结点包含的样本集根据属性测试的结果被划分到子结点中;根结点包含样本全集,从根结点到每个叶结点的路径对应了一个判定测试序列。

决策树学习的目的是为了产生一颗泛化能力前,即处理未见示例能力强的决策树,其基本流程遵循简单且直观的“分而治之”策略。

基本算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
输入:训练集D={(x1,y1).(x1,y2)...,(xm,ym)};
属性集A={a1,a2,...,ad}
过程:函数TreeGenerate(D,A)
1.生成结点node;
2.if D中样本全属于同一类别C then
3. 将node标记为C类叶结点; return
4.end if
5.if A=null or D中赝本在A上取值相同 then
6. 将node标记为叶结点,其类别标记为D中样本书最多的类; return
7.end if
8.从A中划分最优划分属性a*;
9.for a* 的每个一直a*v do
10. 为node生成一个分支;令Dv表示D中在a*上取值为a*v的样本子集;
11. if Dv为空 then
12. 将分支结点标记为叶结点,其类别标记为D中样本最多的类; return
13. else
14. 以TreeGenerate(Dv,A\{ax})为分支结点
15. end if
16.end for
输出: 以node 为根结点的一颗决策树

划分选择

参照上述算法的第8行代码,即如何选择最优划分属性。我们希望决策树的分支结点所包含的样本尽可能属于同一类别,即结点的”纯度”越来越高。

信息熵

信息熵:”信息熵“是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第k类样本所占的比例为pk(k=1,2,3,….|y|),D的信息熵定义为

可见,Ent(D)的值越小,样本的纯度越高。接下来编写代码计算信息熵

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
from math import log
def createDataSet():
dataSet = [[0, 0, 0, 0, 'no'], # 数据集
[0, 0, 0, 1, 'no'],
[0, 1, 0, 1, 'yes'],
[0, 1, 1, 0, 'yes'],
[0, 0, 0, 0, 'no'],
[1, 0, 0, 0, 'no'],
[1, 0, 0, 1, 'no'],
[1, 1, 1, 1, 'yes'],
[1, 0, 1, 2, 'yes'],
[1, 0, 1, 2, 'yes'],
[2, 0, 1, 2, 'yes'],
[2, 0, 1, 1, 'yes'],
[2, 1, 0, 1, 'yes'],
[2, 1, 0, 2, 'yes'],
[2, 0, 0, 0, 'no']]
labels = ['年龄', '有工作', '有自己的房子', '信贷情况'] # 特征标签
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)
return shannonEnt

信息增益

条件熵: 学习信息增益之前,我们有必要先了解条件熵,条件熵H(Y|X)表示已知随机变量X的条件下随机变量Y的不确定性,随机变量X给定的条件下随机变量Y的条件熵H(Y|X)。用通俗的话来说,就是不同的分支结点包含的样本数不同,我们给分支结点赋予权重||Dv|/|D|,即样本数越多的分支结点结点的影响越大。

于是可以计算出用属性a对样本即D进行划分所获得的”信息增益

信息增益越大,则意味着使用属性a来进行划分所获得的”纯度提升”越大。这样,通过这种方式计算得出的信息增益,我们会取最高值作为划分属性。下面给出代码:

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
# 按照给定的特征划分数据集
def splitDataSet(dataSet, axis, value):
retDataSet= []
for featVec in dataSet: # 遍历数据集
if featVec[axis] == value:
reducedFeatVec = featVec[:axis] # 去掉axis特征
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec) # 将符合条件的添加到返回的数据集
return retDataSet
# 选择最优特征
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 # 特征数量
baseEntropy = calcShannonEnt(dataSet) # 计算数据集的特征熵
bestInfoGain = 0.0
bestFeature = -1
for i in range(numFeatures):
# 获取dataSet的第i个所有特征
featList = [example[i] for example in dataSet]
uniqueVals = set(featList) # 创建set集合{},元素不可重复
newEntropy = 0.0 # 经验条件熵
for value in uniqueVals: # 计算信息增益
subDataSet = splitDataSet(dataSet, i, value) # subDataSet划分后的子集
prob = len(subDataSet) / float(len(dataSet)) # 计算子集的概率
newEntropy += prob * calcShannonEnt(subDataSet)# 根据公式计算经验条件熵
infoGain = baseEntropy - newEntropy # 计算信息增益
print("第%d个特征的增益为%.3f" % (i,infoGain))
if (infoGain > bestInfoGain): # 找出最大的信息增益及索引
bestInfoGain = infoGain
bestFeature = i
return bestFeature # 返回最大的信息增益的特征索引
if __name__ == '__main__':
dataSet, features = createDataSet()
print("最优特征索引值:" + str(chooseBestFeatureToSplit(dataSet)))

splitDataSet()函数用来划分数据,即将符合条件的数据从数据集中划分出来,chooseBestFeatureToSplit()函数可以计算出每个特征的信息增益,最后返回信息增益最大的特征索引。程序输出如下:

第0个特征的增益为0.083
第1个特征的增益为0.324
第2个特征的增益为0.420
第3个特征的增益为0.363
最优特征索引值:2

增益率

从算法中可以看出,信息增益算法对可取值较多的特征有所偏好,为了解决这种偏好带来的不利影响,著名的C4.5决策树算法不直接用信息增益,而是使用”增益率”来区分最优特征。

增益率对取值较少的特征有所偏好,它的算法思想是:先从候选划分属性中找出信息增益高出平均水平的属性,再从中选择增益率最高的。

构建决策树

由于需要划分最好的属性构建数据集,而且特征属性不唯一,所以可能存在多个分支的数据集划分。第一次划分时,数据集向下传递到树分支的下一个结点,然后再次划分,所以我们采用递归的思想构建决策树。

递归结束的条件是:程序遍历完所有划分数据集的属性,或者每个分支下所有实例都具有相同的分类。如果所有与的实例拥有相同的分类,则得到一个叶子结点或终止。任何到达数据结点的数据必然属于叶子结点。

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
# 统计classList中出现次数最多的元素(类标签)
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]
"""
函数说明:递归构建决策树
Parameters:
dataSet - 训练数据集
labels - 分类训练属性
featLabels - 存储选择的最优特征标签
"""
def createTree(dataSet, labels, featLabels):
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 = chooseBestFeatureToSplit(dataSet) # 根据信息增益,算出最优特征索引
bestFeatLabel = labels[bestFeat] # 取出最优标签索引
featLabels.append(bestFeatLabel)
myTree = {bestFeatLabel: {}} # 建立以该特征为结点的枝干(根)
del (labels[bestFeat]) # 删除该标签
featValues = [example[bestFeat] for example in dataSet]
uniquevalues = set(featValues) # 取出该标签下的特征数量(去重复)
for value in uniquevalues: # 遍历所有特征进行递归,创建决策树
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), labels, featLabels)
return myTree
if __name__ == '__main__':
dataSet, features = createDataSet()
# print("最优特征索引值:" + str(chooseBestFeatureToSplit(dataSet)))
featLabels = []
myTree = createTree(dataSet, features, featLabels)
print(myTree)

建立决策树的函数有两种情况返回值,一是类别相同时,如果该数据集标签完全相同则以意味着已到叶子结点,该种类型分类完毕。二是在遍历完所有特征后,相当于特征不够用,决策树建立失败,所以返回出现最多的类标签(递归建立决策树过程中,会去除已经使用过的类标签,所以如果特征不够用,分割下来的数据集只有类标签而没有其他属性,所以len(dataSet[0]) = 1)。程序输出如下:

{‘有自己的房子’: {0: {‘有工作’: {0: ‘no’, 1: ‘yes’}}, 1: ‘yes’}}

存储决策树

对于庞大的数据量来说,不可能在每次分类都要构建决策树,这样就需要将样本存储起来,为了节省时间,最好能在每次执行分来是调用已经构造好的决策树。我们使用pickle模块序列化对象。

1
2
3
4
5
6
7
8
9
# 存储决策树
def storeTree(inputTree,filename):
with open(filename,'wb') as fw:
pickle.dump(inputTree,fw)
# 读取决策树
def grabTree(filename):
fr = open(filename,'rb')
return pickle.load(fr)

使用决策树算法进行分类

在使用决策树算法对数据分类时,同样使用递归的思想,具体方法见代码:

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
"""
说明:根据给出的决策树进行分类
Parameters:
inputTree:已经生成的决策树
featLabels:存储选择的最优特征标签(决策树中存在的标签)
testVec:测试数据
Returns:
classLabels:分类结果
"""
def classify(inputTree,featLabels,testVec):
firstStr = next(iter(inputTree)) # 取字典中的键为先判断的条件
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
if __name__ == '__main__':
dataSet, features = createDataSet()
# print("最优特征索引值:" + str(chooseBestFeatureToSplit(dataSet)))
featLabels = []
myTree = createTree(dataSet, features, featLabels)
print(myTree)
testVec = [0,1] #测试数据
result = classify(myTree, featLabels, testVec)
if result == 'yes':
print('放贷')
if result == 'no':
print('不放贷')

需要注意的是,输入的测试数据要满足得出的最优特征集,而且索引要一一对应。输入测试数据[0,1],它代表没有房子,但是有工作,分类结果为放贷。

Powered by Hexo and Hexo-theme-hiker

Copyright © 2016 - 2019 Dreaouth All Rights Reserved.

访客数 : | 访问量 :