决策树（Decision Tree）算法主要用来处理分类问题，是最经常使用的数据挖掘算法之一。
一、决策树 场景
一个叫做 "二十个问题" 的游戏，游戏的规则很简单：参与游戏的一方在脑海中想某个事物，其他参与者向他提问，只允许提 20 个问题，问题的答案也只能用对或错回答。问问题的人通过推断分解，逐步缩小待猜测事物的范围，最后得到游戏的答案。
一个邮件分类系统，大致工作流程如下：
首先检测发送邮件域名地址。如果地址为 myEmployer.com, 则将其放在分类 "无聊时需要阅读的邮件"中。
如果邮件不是来自这个域名，则检测邮件内容里是否包含单词 "曲棍球" , 如果包含则将邮件归类到 "需要及时处理的朋友邮件", 如果不包含则将邮件归类到 "无需阅读的垃圾邮件" 。
二、决策树 原理
1、决策树 须知概念
信息熵 & 信息增益
熵： 熵（entropy）指的是体系的混乱的程度，在不同的学科中也有引申出的更为具体的定义，是各领域十分重要的参量。
信息熵（香农熵）： 是一种信息的度量方式，表示信息的混乱程度，也就是说：信息越有序，信息熵越低。例如：火柴有序放在火柴盒里，熵值很低，相反，熵值很高。
信息增益： 在划分数据集前后信息发生的变化称为信息增益。
2、决策树工作原理
如何构造一个决策树? 我们使用 createBranch() 方法，如下所示：
检测数据集中的所有数据的分类标签是否相同:
If so return 类标签
Else:
寻找划分数据集的最好特征（划分之后信息熵最小，也就是信息增益最大的特征）
划分数据集
创建分支节点
for 每个划分的子集
调用函数 createBranch （创建分支的函数）并增加返回结果到分支节点中
return 分支节点3、决策树开发流程
- 收集数据：可以使用任何方法。
- 准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。
- 分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
- 训练算法：构造树的数据结构。
- 测试算法：使用经验树计算错误率。（经验树没有搜索到较好的资料，有兴趣的同学可以来补充）
- 使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。
4、决策树算法特点
优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过度匹配问题。
适用数据类型：数值型和标称型。
三、决策树 Demo演示
Demo1：决策树分类-鸢尾花数据
#!/usr/bin/python
# coding:utf-8
"""
Created on 2017-06-29
Updated on 2017-06-29
DecisionTree：决策树
@author: 小瑶
《机器学习实战》更新地址：https://github.com/apachecn/MachineLearning
"""
#print(__doc__)
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
%matplotlib inline
# 参数
n_classes = 3
plot_colors = "bmy"
plot_step = 0.02
# 加载数据
iris = load_iris()
for pairidx, pair in enumerate([[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]):
#for pairidx, pair in enumerate([[0, 1]]):
# 我们只用两个相应的features
X = iris.data[:, pair]
y = iris.target
# 训练
clf = DecisionTreeClassifier().fit(X, y)
# 绘制决策边界
plt.subplot(2, 3, pairidx + 1)
#plt.subplot(1, 1, pairidx + 1)
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, plot_step),
np.arange(y_min, y_max, plot_step))
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
cs = plt.contourf(xx, yy, Z, cmap=plt.cm.Paired)
plt.xlabel(iris.feature_names[pair[0]])
plt.ylabel(iris.feature_names[pair[1]])
plt.axis("tight")
# 绘制训练点
for i, color in zip(range(n_classes), plot_colors):
idx = np.where(y == i)
plt.scatter(X[idx, 0], X[idx, 1], c=color, label=iris.target_names[i],
cmap=plt.cm.Paired)
plt.axis("tight")
plt.suptitle("Decision surface of a decision tree using paired features")
plt.legend()
plt.show()
Demo2: 决策树 回归
#!/usr/bin/python
# coding:utf8
"""
Created on 2017-06-29
Updated on 2017-06-29
DecisionTree：决策树
@author: 小瑶
《机器学习实战》更新地址：https://github.com/apachecn/MachineLearning
"""
print(__doc__)
# 引入必要的模型和库
import numpy as np
from sklearn.tree import DecisionTreeRegressor
import matplotlib.pyplot as plt
# 创建一个随机的数据集
# 参考 https://docs.scipy.org/doc/numpy-1.6.0/reference/generated/numpy.random.mtrand.RandomState.html
rng = np.random.RandomState(1)
# print 'lalalalala===', rng
# rand() 是给定形状的随机值，rng.rand(80, 1)即矩阵的形状是 80行，1列
# sort()
X = np.sort(5 * rng.rand(80, 1), axis=0)
# print 'X=', X
y = np.sin(X).ravel()
# print 'y=', y
y[::5] += 3 * (0.5 - rng.rand(16))
# print 'yyy=', y
# 拟合回归模型
# regr_1 = DecisionTreeRegressor(max_depth=2)
# 保持 max_depth=5 不变，增加 min_samples_leaf=6 的参数，效果进一步提升了
regr_2 = DecisionTreeRegressor(max_depth=5)
regr_2 = DecisionTreeRegressor(min_samples_leaf=6)
# regr_3 = DecisionTreeRegressor(max_depth=4)
# regr_1.fit(X, y)
regr_2.fit(X, y)
# regr_3.fit(X, y)
# 预测
X_test = np.arange(0.0, 5.0, 0.01)[:, np.newaxis]
# y_1 = regr_1.predict(X_test)
y_2 = regr_2.predict(X_test)
# y_3 = regr_3.predict(X_test)
# 绘制结果
plt.figure()
plt.scatter(X, y, c="darkorange", label="data")
# plt.plot(X_test, y_1, color="cornflowerblue", label="max_depth=2", linewidth=2)
plt.plot(X_test, y_2, color="yellowgreen", label="max_depth=5", linewidth=2)
# plt.plot(X_test, y_3, color="red", label="max_depth=3", linewidth=2)
plt.xlabel("data")
plt.ylabel("target")
plt.title("Decision Tree Regression")
plt.legend()
plt.show()
4、决策树 项目案例
项目案例1: 判定鱼类和非鱼类
1、项目概述：
根据以下2个特征，将动物分成两类：鱼类和非鱼类。
特征:
不浮出水面是否可以生存
是否有脚蹼
2、开发流程
收集数据：可以使用任何方法
准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化
分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期
训练算法：构造树的数据结构
测试算法：使用决策树执行分类
使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义
1 数据收集：可以使用任何方法
我们利用 createDataSet() 函数输入数据
def createDataSet():
dataSet = [[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']]
labels = ['no surfacing', 'flippers']
return dataSet, labels2 准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化，此处，由于我们输入的数据本身就是离散化数据，所以这一步就省略了。
3 分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期
计算给定数据集的香农熵的函数
def calcShannonEnt(dataSet):
"""
Desc：
calculate Shannon entropy -- 计算给定数据集的香农熵
Args:
dataSet -- 数据集
Returns:
shannonEnt -- 返回 每一组 feature 下的某个分类下，香农熵的信息期望
"""
# -----------计算香农熵的第一种实现方式start------------------------------------------------
# 求list的长度，表示计算参与训练的数据量
numEntries = len(dataSet)
# 下面输出我们测试的数据集的一些信息
# 例如：<type 'list'> numEntries: 5 是下面的代码的输出
# print(type(dataSet), 'numEntries: ', numEntries)
# 计算分类标签label出现的次数
labelCounts = {}
# the the number of unique elements and their occurance
for featVec in dataSet:
# 将当前实例的标签存储，即每一行数据的最后一个数据代表的是标签
currentLabel = featVec[-1]
# 为所有可能的分类创建字典，如果当前的键值不存在，则扩展字典并将当前键值加入字典。每个键值都记录了当前类别出现的次数。
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
# print('-----', featVec, labelCounts)
# 对于label标签的占比，求出label标签的香农熵
shannonEnt = 0.0
for key in labelCounts:
# 使用所有类标签的发生频率计算类别出现的概率。
prob = float(labelCounts[key])/numEntries
# log base 2
# 计算香农熵，以 2 为底求对数
shannonEnt -= prob * log(prob, 2)
# print('---', prob, prob * log(prob, 2), shannonEnt)
# -----------计算香农熵的第一种实现方式end--------------------------------------------------
# # -----------计算香农熵的第二种实现方式start----------------------------------------------
# # 统计标签出现的次数
# label_count = Counter(data[-1] for data in dataSet)
# # 计算概率
# probs = [p[1] / len(dataSet) for p in label_count.items()]
# # 计算香农熵
# shannonEnt = sum([-p * log(p, 2) for p in probs])
# # -----------计算香农熵的第二种实现方式end--------------------------------------------------------------------------------
return shannonEnt按照给定特征划分数据集
将指定特征的特征值等于 value 的行剩下列作为子数据集。
def splitDataSet(dataSet, index, value):
"""splitDataSet(通过遍历dataSet数据集，求出index对应的colnum列的值为value的行)
就是依据index列进行分类，如果index列的数据等于 value的时候，就要将 index 划分到我们创建的新的数据集中
Args:
dataSet 数据集 待划分的数据集
index 表示每一行的index列 划分数据集的特征
value 表示index列对应的value值 需要返回的特征的值。
Returns:
index列为value的数据集【该数据集需要排除index列】
"""
retDataSet = []
for featVec in dataSet:
# index列为value的数据集【该数据集需要排除index列】
# 判断index列的值是否为value
if featVec[index] == value:
# chop out index used for splitting
# [:index]表示前index行，即若 index 为2，就是取 featVec 的前 index 行
reducedFeatVec = featVec[:index]
'''
请百度查询一下： extend和append的区别
list.append(object) 向列表中添加一个对象object
list.extend(sequence) 把一个序列seq的内容添加到列表中
1、使用append的时候，是将new_media看作一个对象，整体打包添加到music_media对象中。
2、使用extend的时候，是将new_media看作一个序列，将这个序列和music_media序列合并，并放在其后面。
result = []
result.extend([1,2,3])
print result
result.append([4,5,6])
print result
result.extend([7,8,9])
print result
结果：
[1, 2, 3]
[1, 2, 3, [4, 5, 6]]
[1, 2, 3, [4, 5, 6], 7, 8, 9]
'''
reducedFeatVec.extend(featVec[index+1:])
# [index+1:]表示从跳过 index 的 index+1行，取接下来的数据
# 收集结果值 index列为value的行【该行需要排除index列】
retDataSet.append(reducedFeatVec)
return retDataSet选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet):
"""chooseBestFeatureToSplit(选择最好的特征)
Args:
dataSet 数据集
Returns:
bestFeature 最优的特征列
"""
# 求第一行有多少列的 Feature, 最后一列是label列嘛
numFeatures = len(dataSet[0]) - 1
# 数据集的原始信息熵
baseEntropy = calcShannonEnt(dataSet)
# 最优的信息增益值, 和最优的Featurn编号
bestInfoGain, bestFeature = 0.0, -1
# iterate over all the features
for i in range(numFeatures):
# create a list of all the examples of this feature
# 获取对应的feature下的所有数据
featList = [example[i] for example in dataSet]
# get a set of unique values
# 获取剔重后的集合，使用set对list数据进行去重
uniqueVals = set(featList)
# 创建一个临时的信息熵
newEntropy = 0.0
# 遍历某一列的value集合，计算该列的信息熵
# 遍历当前特征中的所有唯一属性值，对每个唯一属性值划分一次数据集，计算数据集的新熵值，并对所有唯一特征值得到的熵求和。
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
# 计算概率
prob = len(subDataSet)/float(len(dataSet))
# 计算信息熵
newEntropy += prob * calcShannonEnt(subDataSet)
# gain[信息增益]: 划分数据集前后的信息变化， 获取信息熵最大的值
# 信息增益是熵的减少或者是数据无序度的减少。最后，比较所有特征中的信息增益，返回最好特征划分的索引值。
infoGain = baseEntropy - newEntropy
print ('infoGain=', infoGain, 'bestFeature=', i, baseEntropy, newEntropy)
if (infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature问：上面的 newEntropy 为什么是根据子集计算的呢？
答：因为我们在根据一个特征计算香农熵的时候，该特征的分类值是相同，这个特征这个分类的香农熵为 0； 这就是为什么计算新的香农熵的时候使用的是子集。
4 训练算法：构造树的数据结构
创建树的函数代码如下：
def createTree(dataSet, labels):
"""
Desc:
创建决策树
Args:
dataSet -- 要创建决策树的训练数据集
labels -- 训练数据集中特征对应的含义的labels，不是目标变量
Returns:
myTree -- 创建完成的决策树
"""
classList = [example[-1] for example in dataSet]
# 如果数据集的最后一列的第一个值出现的次数=整个集合的数量，也就说只有一个类别，就只直接返回结果就行
# 第一个停止条件：所有的类标签完全相同，则直接返回该类标签。
# count() 函数是统计括号中的值在list中出现的次数
if classList.count(classList[0]) == len(classList):
return classList[0]
# 如果数据集只有1列，那么最初出现label次数最多的一类，作为结果
# 第二个停止条件：使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组。
if len(dataSet[0]) == 1:
return majorityCnt(classList)
# 选择最优的列，得到最优列对应的label含义
bestFeat = chooseBestFeatureToSplit(dataSet)
# 获取label的名称
bestFeatLabel = labels[bestFeat]
# 初始化myTree
myTree = {bestFeatLabel: {}}
# 注：labels列表是可变对象，在PYTHON函数中作为参数时传址引用，能够被全局修改
# 所以这行代码导致函数外的同名变量被删除了元素，造成例句无法执行，提示'no surfacing' is not in list
del(labels[bestFeat])
# 取出最优列，然后它的branch做分类
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
# 求出剩余的标签label
subLabels = labels[:]
# 遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree()
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
# print('myTree', value, myTree)
return myTree5 测试算法：使用决策树执行分类
def classify(inputTree, featLabels, testVec):
"""
Desc:
对新数据进行分类
Args:
inputTree -- 已经训练好的决策树模型
featLabels -- Feature标签对应的名称，不是目标变量
testVec -- 测试输入的数据
Returns:
classLabel -- 分类的结果值，需要映射label才能知道名称
"""
# 获取tree的根节点对于的key值
firstStr = list(inputTree.keys())[0]
# 通过key得到根节点对应的value
secondDict = inputTree[firstStr]
# 判断根节点名称获取根节点在label中的先后顺序，这样就知道输入的testVec怎么开始对照树来做分类
featIndex = featLabels.index(firstStr)
# 测试数据，找到根节点对应的label位置，也就知道从输入的数据的第几位来开始分类
key = testVec[featIndex]
valueOfFeat = secondDict[key]
print('+++', firstStr, 'xxx', secondDict, '---', key, '>>>', valueOfFeat)
# 判断分枝是否结束: 判断valueOfFeat是否是dict类型
if isinstance(valueOfFeat, dict):
classLabel = classify(valueOfFeat, featLabels, testVec)
else:
classLabel = valueOfFeat
return classLabel6 使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。
#项目一：判定鱼类和非鱼类
#decisionTreePlot.py
#!/usr/bin/python
# -*- coding: UTF-8 -*-
'''
Created on Oct 14, 2010
Update on 2017-02-27
Decision Tree Source Code for Machine Learning in Action Ch. 3
@author: Peter Harrington/jiangzhonglian
'''
import matplotlib.pyplot as plt
%matplotlib inline
# 定义文本框 和 箭头格式 【 sawtooth 波浪方框, round4 矩形方框 , fc表示字体颜色的深浅 0.1~0.9 依次变浅，没错是变浅】
decisionNode = dict(boxstyle="sawtooth", fc="0.8")
leafNode = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")
def getNumLeafs(myTree):
numLeafs = 0
firstStr = list(myTree.keys())[0]
secondDict = myTree[firstStr]
# 根节点开始遍历
for key in secondDict.keys():
# 判断子节点是否为dict, 不是+1
if type(secondDict[key]) is dict:
numLeafs += getNumLeafs(secondDict[key])
else:
numLeafs += 1
return numLeafs
def getTreeDepth(myTree):
maxDepth = 0
firstStr = list(myTree.keys())[0]
secondDict = myTree[firstStr]
# 根节点开始遍历
for key in secondDict.keys():
# 判断子节点是不是dict, 求分枝的深度
# ----------写法1 start ---------------
if type(secondDict[key]) is dict:
thisDepth = 1 + getTreeDepth(secondDict[key])
else:
thisDepth = 1
# ----------写法1 end ---------------
# ----------写法2 start --------------
# thisDepth = 1 + getTreeDepth(secondDict[key]) if type(secondDict[key]) is dict else 1
# ----------写法2 end --------------
# 记录最大的分支深度
maxDepth = max(maxDepth, thisDepth)
return maxDepth
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction', xytext=centerPt, textcoords='axes fraction', va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)
def plotMidText(cntrPt, parentPt, txtString):
xMid = (parentPt[0] - cntrPt[0]) / 2 + cntrPt[0]
yMid = (parentPt[1] - cntrPt[1]) / 2 + cntrPt[1]
createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)
def plotTree(myTree, parentPt, nodeTxt):
# 获取叶子节点的数量
numLeafs = getNumLeafs(myTree)
# 获取树的深度
# depth = getTreeDepth(myTree)
# 找出第1个中心点的位置，然后与 parentPt定点进行划线
cntrPt = (plotTree.xOff + (1 + numLeafs) / 2 / plotTree.totalW, plotTree.yOff)
# print(cntrPt)
# 并打印输入对应的文字
plotMidText(cntrPt, parentPt, nodeTxt)
firstStr = list(myTree.keys())[0]
# 可视化Node分支点
plotNode(firstStr, cntrPt, parentPt, decisionNode)
# 根节点的值
secondDict = myTree[firstStr]
# y值 = 最高点-层数的高度[第二个节点位置]
plotTree.yOff = plotTree.yOff - 1 / plotTree.totalD
for key in secondDict.keys():
# 判断该节点是否是Node节点
if type(secondDict[key]) is dict:
# 如果是就递归调用[recursion]
plotTree(secondDict[key], cntrPt, str(key))
else:
# 如果不是，就在原来节点一半的地方找到节点的坐标
plotTree.xOff = plotTree.xOff + 1 / plotTree.totalW
# 可视化该节点位置
plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
# 并打印输入对应的文字
plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
plotTree.yOff = plotTree.yOff + 1 / plotTree.totalD
def createPlot(inTree):
# 创建一个figure的模版
fig = plt.figure(1, facecolor='green')
fig.clf()
axprops = dict(xticks=[], yticks=[])
# 表示创建一个1行，1列的图，createPlot.ax1 为第 1 个子图，
createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
plotTree.totalW = float(getNumLeafs(inTree))
plotTree.totalD = float(getTreeDepth(inTree))
# 半个节点的长度
plotTree.xOff = -0.5 / plotTree.totalW
plotTree.yOff = 1.0
plotTree(inTree, (0.5, 1.0), '')
plt.show()
# # 测试画图
# def createPlot():
# fig = plt.figure(1, facecolor='white')
# fig.clf()
# # ticks for demo puropses
# createPlot.ax1 = plt.subplot(111, frameon=False)
# plotNode('a decision node', (0.5, 0.1), (0.1, 0.5), decisionNode)
# plotNode('a leaf node', (0.8, 0.1), (0.3, 0.8), leafNode)
# plt.show()
# 测试数据集
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]
# myTree = retrieveTree(1)
# createPlot(myTree)#项目一：判定鱼类和非鱼类
#DecisionTree.py
#!/usr/bin/python
# -*- coding: UTF-8 -*-
'''
Created on Oct 12, 2010
Update on 2017-05-18
Decision Tree Source Code for Machine Learning in Action Ch. 3
@author: Peter Harrington/片刻
《机器学习实战》更新地址：https://github.com/apachecn/MachineLearning
'''
print(__doc__)
import operator
from math import log
#import decisionTreePlot as dtPlot
from collections import Counter
def createDataSet():
"""
Desc:
创建数据集
Args:
无需传入参数
Returns:
返回数据集和对应的label标签
"""
# dataSet 前两列是特征，最后一列对应的是每条数据对应的分类标签
dataSet = [[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']]
# dataSet = [['yes'],
# ['yes'],
# ['no'],
# ['no'],
# ['no']]
# labels 露出水面 脚蹼，注意：这里的labels是写的 dataSet 中特征的含义，并不是对应的分类标签或者说目标变量
labels = ['no surfacing', 'flippers']
# 返回
return dataSet, labels
def calcShannonEnt(dataSet):
"""
Desc：
calculate Shannon entropy -- 计算给定数据集的香农熵
Args:
dataSet -- 数据集
Returns:
shannonEnt -- 返回 每一组 feature 下的某个分类下，香农熵的信息期望
"""
# -----------计算香农熵的第一种实现方式start----------------------------------------------
# 求list的长度，表示计算参与训练的数据量
numEntries = len(dataSet)
# 下面输出我们测试的数据集的一些信息
# 例如：<type 'list'> numEntries: 5 是下面的代码的输出
# print(type(dataSet), 'numEntries: ', numEntries)
# 计算分类标签label出现的次数
labelCounts = {}
# the the number of unique elements and their occurance
for featVec in dataSet:
# 将当前实例的标签存储，即每一行数据的最后一个数据代表的是标签
currentLabel = featVec[-1]
# 为所有可能的分类创建字典，如果当前的键值不存在，则扩展字典并将当前键值加入字典。每个键值都记录了当前类别出现的次数。
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
# print('-----', featVec, labelCounts)
# 对于label标签的占比，求出label标签的香农熵
shannonEnt = 0.0
for key in labelCounts:
# 使用所有类标签的发生频率计算类别出现的概率。
prob = float(labelCounts[key])/numEntries
# log base 2
# 计算香农熵，以 2 为底求对数
shannonEnt -= prob * log(prob, 2)
# print('---', prob, prob * log(prob, 2), shannonEnt)
# -----------计算香农熵的第一种实现方式end------------------------------------------------
# # -----------计算香农熵的第二种实现方式start--------------------------------------------
# # 统计标签出现的次数
# label_count = Counter(data[-1] for data in dataSet)
# # 计算概率
# probs = [p[1] / len(dataSet) for p in label_count.items()]
# # 计算香农熵
# shannonEnt = sum([-p * log(p, 2) for p in probs])
# # -----------计算香农熵的第二种实现方式end----------------------------------------------
return shannonEnt
def splitDataSet(dataSet, index, value):
"""
Desc：
划分数据集
splitDataSet(通过遍历dataSet数据集，求出index对应的colnum列的值为value的行)
就是依据index列进行分类，如果index列的数据等于 value的时候，就要将 index 划分到我们创建的新的数据集中
Args:
dataSet -- 数据集 待划分的数据集
index -- 表示每一行的index列 划分数据集的特征
value -- 表示index列对应的value值 需要返回的特征的值。
Returns:
index 列为 value 的数据集【该数据集需要排除index列】
"""
# -----------切分数据集的第一种方式 start------------------------------------
retDataSet = []
for featVec in dataSet:
# index列为value的数据集【该数据集需要排除index列】
# 判断index列的值是否为value
if featVec[index] == value:
# chop out index used for splitting
# [:index]表示前index行，即若 index 为2，就是取 featVec 的前 index 行
reducedFeatVec = featVec[:index]
'''
请百度查询一下： extend和append的区别
list.append(object) 向列表中添加一个对象object
list.extend(sequence) 把一个序列seq的内容添加到列表中
1、使用append的时候，是将new_media看作一个对象，整体打包添加到music_media对象中。
2、使用extend的时候，是将new_media看作一个序列，将这个序列和music_media序列合并，并放在其后面。
result = []
result.extend([1,2,3])
print(result)
result.append([4,5,6])
print(result)
result.extend([7,8,9])
print(result)
结果：
[1, 2, 3]
[1, 2, 3, [4, 5, 6]]
[1, 2, 3, [4, 5, 6], 7, 8, 9]
'''
reducedFeatVec.extend(featVec[index+1:])
# [index+1:]表示从跳过 index 的 index+1行，取接下来的数据
# 收集结果值 index列为value的行【该行需要排除index列】
retDataSet.append(reducedFeatVec)
# -----------切分数据集的第一种方式 end------------------------------------
# # -----------切分数据集的第二种方式 start------------------------------------
# retDataSet = [data[:index] + data[index + 1:] for data in dataSet for i, v in enumerate(data) if i == index and v == value]
# # -----------切分数据集的第二种方式 end------------------------------------
return retDataSet
def chooseBestFeatureToSplit(dataSet):
"""
Desc:
选择切分数据集的最佳特征
Args:
dataSet -- 需要切分的数据集
Returns:
bestFeature -- 切分数据集的最优的特征列
"""
# -----------选择最优特征的第一种方式 start------------------------------------
# 求第一行有多少列的 Feature, 最后一列是label列嘛
numFeatures = len(dataSet[0]) - 1
# label的信息熵
baseEntropy = calcShannonEnt(dataSet)
# 最优的信息增益值, 和最优的Featurn编号
bestInfoGain, bestFeature = 0.0, -1
# iterate over all the features
for i in range(numFeatures):
# create a list of all the examples of this feature
# 获取每一个实例的第i+1个feature，组成list集合
featList = [example[i] for example in dataSet]
# get a set of unique values
# 获取剔重后的集合，使用set对list数据进行去重
uniqueVals = set(featList)
# 创建一个临时的信息熵
newEntropy = 0.0
# 遍历某一列的value集合，计算该列的信息熵
# 遍历当前特征中的所有唯一属性值，对每个唯一属性值划分一次数据集，计算数据集的新熵值，并对所有唯一特征值得到的熵求和。
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
# gain[信息增益]: 划分数据集前后的信息变化， 获取信息熵最大的值
# 信息增益是熵的减少或者是数据无序度的减少。最后，比较所有特征中的信息增益，返回最好特征划分的索引值。
infoGain = baseEntropy - newEntropy
print('infoGain=', infoGain, 'bestFeature=', i, baseEntropy, newEntropy)
if (infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature
# -----------选择最优特征的第一种方式 end------------------------------------
# # -----------选择最优特征的第二种方式 start------------------------------------
# # 计算初始香农熵
# base_entropy = calcShannonEnt(dataSet)
# best_info_gain = 0
# best_feature = -1
# # 遍历每一个特征
# for i in range(len(dataSet[0]) - 1):
# # 对当前特征进行统计
# feature_count = Counter([data[i] for data in dataSet])
# # 计算分割后的香农熵
# new_entropy = sum(feature[1] / float(len(dataSet)) * calcShannonEnt(splitDataSet(dataSet, i, feature[0])) \
# for feature in feature_count.items())
# # 更新值
# info_gain = base_entropy - new_entropy
# print('No. {0} feature info gain is {1:.3f}'.format(i, info_gain))
# if info_gain > best_info_gain:
# best_info_gain = info_gain
# best_feature = i
# return best_feature
# # -----------选择最优特征的第二种方式 end------------------------------------
def majorityCnt(classList):
"""
Desc:
选择出现次数最多的一个结果
Args:
classList label列的集合
Returns:
bestFeature 最优的特征列
"""
# -----------majorityCnt的第一种方式 start------------------------------------
classCount = {}
for vote in classList:
if vote not in classCount.keys():
classCount[vote] = 0
classCount[vote] += 1
# 倒叙排列classCount得到一个字典集合，然后取出第一个就是结果（yes/no），即出现次数最多的结果
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
# print('sortedClassCount:', sortedClassCount)
return sortedClassCount[0][0]
# -----------majorityCnt的第一种方式 end------------------------------------
# # -----------majorityCnt的第二种方式 start------------------------------------
# major_label = Counter(classList).most_common(1)[0]
# return major_label
# # -----------majorityCnt的第二种方式 end------------------------------------
def createTree(dataSet, labels):
"""
Desc:
创建决策树
Args:
dataSet -- 要创建决策树的训练数据集
labels -- 训练数据集中特征对应的含义的labels，不是目标变量
Returns:
myTree -- 创建完成的决策树
"""
classList = [example[-1] for example in dataSet]
# 如果数据集的最后一列的第一个值出现的次数=整个集合的数量，也就说只有一个类别，就只直接返回结果就行
# 第一个停止条件：所有的类标签完全相同，则直接返回该类标签。
# count() 函数是统计括号中的值在list中出现的次数
if classList.count(classList[0]) == len(classList):
return classList[0]
# 如果数据集只有1列，那么最初出现label次数最多的一类，作为结果
# 第二个停止条件：使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组。
if len(dataSet[0]) == 1:
return majorityCnt(classList)
# 选择最优的列，得到最优列对应的label含义
bestFeat = chooseBestFeatureToSplit(dataSet)
# 获取label的名称
bestFeatLabel = labels[bestFeat]
# 初始化myTree
myTree = {bestFeatLabel: {}}
# 注：labels列表是可变对象，在PYTHON函数中作为参数时传址引用，能够被全局修改
# 所以这行代码导致函数外的同名变量被删除了元素，造成例句无法执行，提示'no surfacing' is not in list
del(labels[bestFeat])
# 取出最优列，然后它的branch做分类
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
# 求出剩余的标签label
subLabels = labels[:]
# 遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree()
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
# print('myTree', value, myTree)
return myTree
def classify(inputTree, featLabels, testVec):
"""
Desc:
对新数据进行分类
Args:
inputTree -- 已经训练好的决策树模型
featLabels -- Feature标签对应的名称，不是目标变量
testVec -- 测试输入的数据
Returns:
classLabel -- 分类的结果值，需要映射label才能知道名称
"""
# 获取tree的根节点对于的key值
firstStr = list(inputTree.keys())[0]
# 通过key得到根节点对应的value
secondDict = inputTree[firstStr]
# 判断根节点名称获取根节点在label中的先后顺序，这样就知道输入的testVec怎么开始对照树来做分类
featIndex = featLabels.index(firstStr)
# 测试数据，找到根节点对应的label位置，也就知道从输入的数据的第几位来开始分类
key = testVec[featIndex]
valueOfFeat = secondDict[key]
print('+++', firstStr, 'xxx', secondDict, '---', key, '>>>', valueOfFeat)
# 判断分枝是否结束: 判断valueOfFeat是否是dict类型
if isinstance(valueOfFeat, dict):
classLabel = classify(valueOfFeat, featLabels, testVec)
else:
classLabel = valueOfFeat
return classLabel
def storeTree(inputTree, filename):
"""
Desc:
将之前训练好的决策树模型存储起来，使用 pickle 模块
Args:
inputTree -- 以前训练好的决策树模型
filename -- 要存储的名称
Returns:
None
"""
import pickle
# -------------- 第一种方法 start --------------
fw = open(filename, 'wb')
pickle.dump(inputTree, fw)
fw.close()
# -------------- 第一种方法 end --------------
# -------------- 第二种方法 start --------------
with open(filename, 'wb') as fw:
pickle.dump(inputTree, fw)
# -------------- 第二种方法 start --------------
def grabTree(filename):
"""
Desc:
将之前存储的决策树模型使用 pickle 模块 还原出来
Args:
filename -- 之前存储决策树模型的文件名
Returns:
pickle.load(fr) -- 将之前存储的决策树模型还原出来
"""
import pickle
fr = open(filename, 'rb')
return pickle.load(fr)
def fishTest():
"""
Desc:
对动物是否是鱼类分类的测试函数，并将结果使用 matplotlib 画出来
Args:
None
Returns:
None
"""
# 1.创建数据和结果标签
myDat, labels = createDataSet()
# print(myDat, labels)
# 计算label分类标签的香农熵
# calcShannonEnt(myDat)
# # 求第0列 为 1/0的列的数据集【排除第0列】
# print('1---', splitDataSet(myDat, 0, 1))
# print('0---', splitDataSet(myDat, 0, 0))
# # 计算最好的信息增益的列
# print(chooseBestFeatureToSplit(myDat))
import copy
myTree = createTree(myDat, copy.deepcopy(labels))
print(myTree)
# [1, 1]表示要取的分支上的节点位置，对应的结果值
print(classify(myTree, labels, [1, 1]))
# 画图可视化展现
#dtPlot.createPlot(myTree)
createPlot(myTree)
if __name__ == "__main__":
fishTest()
#ContactLensesTest()
项目案例2: 使用决策树预测隐形眼镜类型
1、项目概述：
隐形眼镜类型包括硬材质、软材质以及不适合佩戴隐形眼镜。我们需要使用决策树预测患者需要佩戴的隐形眼镜类型。
2、开发流程
收集数据: 提供的文本文件。
解析数据: 解析 tab 键分隔的数据行
分析数据: 快速检查数据，确保正确地解析数据内容，使用 createPlot() 函数绘制最终的树形图。
训练算法: 使用 createTree() 函数。
测试算法: 编写测试函数验证决策树可以正确分类给定的数据实例。
使用算法: 存储树的数据结构，以便下次使用时无需重新构造树。
1 收集数据：提供的文本文件
文本文件数据格式如下：
2 解析数据：解析 tab 键分隔的数据行
lecses = [inst.strip().split('\t') for inst in fr.readlines()]
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']3 分析数据：快速检查数据，确保正确地解析数据内容，使用 createPlot() 函数绘制最终的树形图。
>>> treePlotter.createPlot(lensesTree)4 训练算法：使用 createTree() 函数
>>> lensesTree = trees.createTree(lenses, lensesLabels)
>>> lensesTree
{'tearRate': {'reduced': 'no lenses', 'normal': {'astigmatic':{'yes':
{'prescript':{'hyper':{'age':{'pre':'no lenses', 'presbyopic':
'no lenses', 'young':'hard'}}, 'myope':'hard'}}, 'no':{'age':{'pre':
'soft', 'presbyopic':{'prescript': {'hyper':'soft', 'myope':
'no lenses'}}, 'young':'soft'}}}}}5 测试算法: 编写测试函数验证决策树可以正确分类给定的数据实例。
6 使用算法: 存储树的数据结构，以便下次使用时无需重新构造树。
使用 pickle 模块存储决策树
def storeTree(inputTree, filename):
impory pickle
fw = open(filename, 'w')
pickle.dump(inputTree, fw)
fw.close()
def grabTree(filename):
import pickle
fr = open(filename)
return pickle.load(fr)!ls datalab/2535/data.txt lenses.txt
#项目案例2: 使用决策树预测隐形眼镜类型
def ContactLensesTest():
"""
Desc:
预测隐形眼镜的测试代码，并将结果画出来
Args:
none
Returns:
none
"""
# 加载隐形眼镜相关的 文本文件 数据
fr = open('datalab/2535/lenses.txt')
# 解析数据，获得 features 数据
lenses = [inst.strip().split('\t') for inst in fr.readlines()]
# 得到数据的对应的 Labels
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
# 使用上面的创建决策树的代码，构造预测隐形眼镜的决策树
lensesTree = createTree(lenses, lensesLabels)
print(lensesTree)
# 画图可视化展现
#dtPlot.createPlot(lensesTree)
createPlot(lensesTree)
if __name__ == "__main__":
#fishTest()
ContactLensesTest()
