《机器学习实战》之决策树算法（1）算法概述

发表于 | 更新于: | 分类于 | 阅读次数:
字数统计: 3,781 | 阅读时长 ≈ 15

前言：

  本渣渣（WordZzzz直接被舍友叫成了“我的渣”，所以以后我在博客中就以此自居了！），最近在学习Peter Harrington的Machine Learning in Action，一边看书一边用Python3.6实现课本中的算法（原书中使用的是Python2.x）。好记性不如烂笔头，奈何本渣渣连烂笔头都买不起，所以就来这不费笔墨的地方费尽心思写博客。本渣渣记性不是一般的差，在此记下每个算法的学习要点及Python代码实现，一方面方便自己以后复习，另一方面贴出来和大家一起学习，共同进步~~~

注意：python3.x与python2.x的部分函数库有较大差异，针对这个问题，本渣渣会将代码版本升级中遇到的问题在每篇博文的最后列出来，并加以解释说明，帮助大家区分理解。

原著代码（python2.x）地址：https://www.manning.com/books/machine-learning-in-action
本渣渣代码（python3.x）地址：https://github.com/WordZzzz/ML/tree/master/Ch03

  博客中的代码都会在本渣渣的GitHub上贴出，欢迎Watch、Star、Fork。

一、算法介绍：

  上一个算法介绍的是k-近邻算法，它可以完成很多分类任务，但是它最大的缺点就是无法给出数据的内在含义，决策树的主要优势就在于数据形式非常容易理解。决策树的一个重要任务就是为了理解数据中所蕴含的知识信息，所以决策树可以使用不熟悉的数据集合，并从中提取出一系列规则，这些机器根据数据集创建规则的过程就是机器学习的过程。专家系统中经常食用决策树，而且决策树给出结果往往可以匹敌在当前领域具有几十年工作经验的人类专家。流程图形式的决策树如下：



决策树：

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

  在构造决策树之前，我们需要解决一个问题：当前数据集上哪个特征在划分数据分类时起决定性作用。为了找到决定性的特征，划分出最好的结果，我们必须评估每个特征。完成测试之后，原始数据集就被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上，如果某个分支下的数据属于同一类型，则无需进一步对数据进行分割，如果数据子集内的数据不属于同一类型，则需要重复划分数据子集的过程。

决策树的一般流程

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

二、代码实现与详解：

  一些决策树算法采用二分法划分数据，书里面采用的是ID3算法划分数据集，该算法处理如何划分数据集，何时停止划分数据集。
  前面提了个问题，这么多特征，我们每次之选一个特征值进行划分，那这个特征要如何选择呢？下面将进行讲解。

信息增益：

  划分数据集的最大原则是：将无序的数据变得更加有序。组织杂乱无章数据的一种方法是使用信息论度量信息，信息论是量化处理信息的分支科学。我们可以在划分数据之前或者之后使用信息论量化信息的内容。

  在划分数据集之前之后信息发生的变化称之为信息增益，获得信息增益最高的特征就是最好的选择。几何信息的度量方式称为香农熵或者简称为熵（其他学科也有熵这个定义，意思都差不多），这个名字来源于信息论之父克劳德·香农。

  熵定义为信息的期望值，如果待分类的事物可能划分在多类分类中，则符号$x_i$的信息论定义为：

$$l(x_i) = -log_2p(x_i)$$

其中$p(x_i)$是选择该分类的概率。

  为了计算熵，我们需要计算所有类别可能值包含的信息期望值，通过下面的公式得到：

$$H = - \sum{^n_{i-1}p(x_i)log_2p(x_i)}$$

其中n是分类的数目。创建trees.py文件，我们来使用python计算信息熵。

  为了后续测试方便，我们先编写createDataSet()函数，创建数据集。

代码实现：

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
# -*- coding: UTF-8 -*-
"""
Created on Aug 18, 2017
Decision Tree Source Code
@author: wordzzzz
"""
from math import log

def createDataSet():
	"""
	Function：	创建数据集

	Args：		无

	Returns：	dataSet：数据集
				labels：标签
	"""
	#创建数据集
	dataSet = [[1, 1, 'yes'],
				[1, 1, 'yes'],
				[1, 0, 'no'],
				[0, 1, 'no'],
				[0, 1, 'no']]
    #创建标签
	labels = ['no surfacing','flippers']
    #返回创建的数据集和标签
	return dataSet, labels

结果输出：

1
2
3
4
>>> import trees
>>> myDat, labels = trees.createDataSet()
>>> myDat
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]

  接下来编写calcShannonEnt(dataSet)函数，计算给定数据集的香农熵。

代码实现：

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
def calcShannonEnt(dataSet):
	"""
	Function：	计算给定数据集的香农熵

	Args：		dataSet：数据集

	Returns：	shannonEnt：香农熵
	"""
	#计算数据集中实例的总数
	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
		#计算香农熵，log(prob, 2)是以2为底求prob的对数
		shannonEnt -=  prob * log(prob, 2)
	#返回香农熵计算结果
	return shannonEnt

结果输出：

1
2
>>> trees.calcShannonEnt(myDat)
0.9709505944546686

  熵越高，则混合的数据也越多，我们可以在数据集中添加更多的分类，观察熵是如何变化的：

1
2
3
4
5
>>> myDat[0][-1]='maybe'
>>> myDat
[[1, 1, 'maybe'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>> trees.calcShannonEnt(myDat)
1.3709505944546687

划分数据集：

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

  编写splitDataSet(dataSet, axis, value)函数，按照给定特征划分数据集。

代码实现：

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 splitDataSet(dataSet, axis, value):
	"""
	Function：	按照给定特征划分数据集

	Args：		dataSet：带划分的数据集
				axis：划分数据集的特征
				value：需要返回的特征的值

	Returns：	retDataSet：符合特征的数据集
	"""	
	#创建新的list对象  
	retDataSet = []
	#抽取数据集
	for featVec in dataSet:
		#将符合特征的数据抽取出来
		if featVec[axis] == value:
			#截取列表中第axis+1个之前的数据
			reducedFeatVec = featVec[:axis]
			#将第axis+2之后的数据接入到上述数据集
			reducedFeatVec.extend(featVec[axis+1:])
			#将处理结果作为列表接入到返回数据集
			retDataSet.append(reducedFeatVec)
	#返回符合特征的数据集
	return retDataSet

输出结果：

1
2
3
4
5
6
7
8
9
>>> reload(trees)
<module 'trees' from 'E:\\机器学习实战\\mycode\\Ch03\\trees.py'>
>>> myDat, labels = trees.createDataSet()
>>> myDat
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>> trees.splitDataSet(myDat,0,1)
[[1, 'yes'], [1, 'yes'], [0, 'no']]
>>> trees.splitDataSet(myDat,0,0)
[[1, 'no'], [1, 'no']]

注意事项：

  • Python语言不用考虑内存分配问题，在函数中传递的是列表的引用，在函数内部对列表对象的更改，将会影响该列表对象的整个生存周期。为了消除这个不良影响，我们需要在函数的开始创建一个新列表。
  • 代码中使用了extend()和append()来抽取符合要求的元素，这两个方法功能类似，但是在处理多个列表时，这两个方法的处理结果是完全不同的。

append

1
2
3
4
5
>>> a=[1,2,3]
>>> b=[4,5,6]
>>> a.append(b)
>>> a
[1, 2, 3, [4, 5, 6]]

extend

1
2
3
4
>>> a=[1,2,3]
>>> a.extend(b)
>>> a
[1, 2, 3, 4, 5, 6]

  编写chooseBestFeatureToSplit(dataSet)函数， 选择最好的数据集划分方式。该函数调用的数据需要满足一定的要求：第一个要求是，数据必须是一种由列表元素组成的列表，而且所有的列表元素都要具有相同的数据长度；第二个要求是，数据的最后一列或者每个实例的最后一个元素是当前实例的类别标签。

代码实现：

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 chooseBestFeatureToSplit(dataSet):
	"""
	Function：	选择最好的数据集划分方式

	Args：		dataSet：待划分的数据集

	Returns：	bestFeature：划分数据集最好的特征
	"""	
	#初始化特征数量
	numFeatures = len(dataSet[0]) - 1
	#计算原始香农熵
	baseEntropy = calcShannonEnt(dataSet)
	#初始化信息增益和最佳特征
	bestInfoGain = 0.0; bestFeature = -1
	#选出最好的划分数据集的特征
	for i in range(numFeatures):
		#创建唯一的分类标签列表
		featList = [example[i] for example in dataSet]
		#从列表中创建集合，以得到列表中唯一元素值
		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

note：从列表中创建集合是Python语言得到列表中唯一元素值的最快方法。

输出结果：

1
2
3
4
5
6
7
8
>>> reload(trees)
<module 'trees' from 'E:\\机器学习实战\\mycode\\Ch03\\trees.py'>
>>> myDat, labels = trees.createDataSet()
>>> trees.chooseBestFeatureToSplit(myDat)
0
>>> myDat
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>>

递归构建决策树：

  从数据集构造决策树算法的工作原理如下：得到原始数据，然后基于最好的属性值划分数据集。第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，可以再次划分数据（递归）。

  递归结束的条件：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所欲实例都具有相同的分类，则得到一个叶子节点或者终止块。任何到达叶子节点的数据必须属于叶子节点的分类，如下图：



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

  编写majorityCnt(classList)函数，进行多数表决，这里和k-近邻算法里面的classify0部分的投票表决代码非常类似。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def majorityCnt(classList):
	"""
	Function：	决定叶子结点的分类

	Args：		classList：分类列表

	Returns：	sortedClassCount[0][0]：叶子结点分类结果
	"""		
	#创建字典
	classCount={}
	#给字典赋值
	for vote in classList:
		#如果字典中没有该键值，则创建
		if vote not in classCount.keys():
			classCount[vote] = 0
		#为每个键值计数
		classCount[vote] += 1
	#对classCount进行排序
	sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
	#返回叶子结点分类结果
	return sortedClassCount[0][0]

  编写createTree(dataSet, labels)函数，创建树

代码实现：

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 createTree(dataSet, labels):
	"""
	Function：	创建树

	Args：		dataSet：数据集
				labels：标签列表

	Returns：	myTree：创建的树的信息
	"""	
	#创建分类列表
	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]
	#创建字典存储树的信息
	myTree = {bestFeatLabel:{}}
	del(labels[bestFeat])
	#得到列表包含的所有属性值
	featValues = [example[bestFeat] for example in dataSet]
	#从列表中创建集合
	uniqueVals = set(featValues)
	#遍历当前选择特征包含的所有属性值
	for value in uniqueVals:
		#复制类标签
		subLabels =labels[:]
		#递归调用函数createTree()，返回值将被插入到字典变量myTree中
		myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
	#返回字典变量myTree
	return myTree

输出结果：

1
2
3
4
5
6
>>> reload(trees)
<module 'trees' from 'E:\\机器学习实战\\mycode\\Ch03\\trees.py'>
>>> myDat, labels = trees.createDataSet()
>>> myTree = trees.createTree(myDat, labels)
>>> myTree
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

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

系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～

完的汪(∪｡∪)｡｡｡zzz

0%