机器学习决策树算法学习笔记

作者：xiabigao

基本概念

决策树是分类算法。

数据类型：数值型和标称型。因为构造算法只适用于标称型，所以数值型数据必须离散化。

工作原理

利用香浓熵找到信息增益最大的特征，按照信息增益最大的特征划分数据，如此反复，让无序的数据变的更加有序。使用ID3算法构建树结构。当传入一个新数据时，按照数据找到对应树节点，直到最后没有叶子节点时，完成分类。

样例

不浮出水面是否可以生存？ 是否有脚蹼？ 是否是鱼类？

通过“不浮出水面是否可以生存”和“是否有脚蹼”这两个特征来判断是否是鱼类。构建一个简单决策树，如果得到一个新的生物，可以用此来判断是否是鱼类。

样例代码

				
					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
			

香农熵公式

如果待分类的事务可能划分在多个分类之中，则符号Xi的信息定义为：

其中P(Xi)是选择该分类的概率

为了计算熵，需要计算所有类别所有可能值包含的信息期望值总和，公式为：

其中n是分类的数目

香农熵算法

				
					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
			

按照香农熵划分数据

除了需要测量信息熵，还需要划分数据集，度量花费数据集的熵，以便判断当前是否正确划分。 循环计算香浓熵和splitDataSet()，找到最好的特征划分方式。

				
					def
					splitDataSet
					(dataSet, axis, value)
					:
				
				# 这个算法返回axis下标之外的列
				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
				
					def
					chooseBestFeatureToSplit
					(dataSet)
					:
				
				# 先取最后一列，用在标签结果：是鱼或不是鱼。
				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]
				# 利用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
			

数据集需要满足一定的要求：

• 数据必须是一种有列表元素组成的列表。（二维数组）
• 所有列表元素必须有相同长度。
• 最后一列必须是当前实例的标签。

递归构建决策树

多数表决算法

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

				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
				), reverse=
				True
				)
				return
				sortedClassCount[
				0
				][
				0
				]
			

构建树算法

				
					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 = 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[:]
				# 递归的构建树
				myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
				return
				myTree
			

使用决策树分类

				
					def
					classify
					(inputTree,featLabels,testVec)
					:
				
				firstStr = inputTree.keys()[
				0
				]
				secondDict = inputTree[firstStr]
				featIndex = featLabels.index(firstStr)
				# print 'featIndex %s' % (featIndex)
				key = testVec[featIndex]
				# print 'key %s' % (key)
				valueOfFeat = secondDict[key]
				if
				isinstance(valueOfFeat, dict):
				classLabel = classify(valueOfFeat, featLabels, testVec)
				else
				: classLabel = valueOfFeat
				return
				classLabel
				dataSet, labels = createDataSet()
				mytree = createTree(dataSet, labels[:])
				#因为内部会删除labels里的值所以用这样copy一份
				print
				mytree
				# {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
				print
				classify(mytree, labels, [
				0
				,
				1
				])
				no
			

决策树的存储

构造决策树是耗时的任务，即使处理很小的数据集。所以我们可以使用构造好的决策树。

				
					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)
			

优点

• 计算复杂度不高
• 输出结果易于理解
• 对中间值缺失不敏感
• 可以处理不相关特侦

缺点

• 可能产生过度匹配问题

End.

转载请注明来自36大数据（36dsj.com)： 36大数据 » 机器学习决策树算法学习笔记