决策树
1. 定义
上述图片就是一个决策树。其中，长方形代表判断模块，椭圆形代表中止模块。从判断模块引出的左右箭头叫做树的分支。它可以到达另外一个判断模块和中止模块。
2. 优缺点
优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过度匹配问题。
适用数据类型：数值型和标称型。
3. 构建决策树的大体思路
# 该函数为伪代码
# 本博客主要采用ID3算法来递归构建决策树
# ID3算法的核心是根据信息增益来选择进行划分的特征，然后递归地构建决策树。
def createBranch:
If 数据集中的每个子项都属于一个分类:
return 类标签
else:
寻找划分数据集的最好特征
按照特征划分数据集
创建分支节点
for 每个划分的数据子集:
调用createBranch函数增加返回结果到分支节点中
return 分支节点
在上述的伪代码中，我们需要注意的是：最好特征的寻找要依赖于信息增益和信息熵的计算。
4. 决策树的一般流程
决策树的一般流程
（1）收集数据：可以使用任何方法。
（2）准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。
（3）分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
（4）训练算法：构造树的数据结构。
（5）测试算法：使用经验树计算错误率。
（6）使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。
注意：在接下来的内容里，我们都以上表为案例来讲解决策树的原理。
5. 信息增益和信息熵
信息增益：在划分数据集之前和之后信息发生的变化叫做信息增益。
需要注意的是，我们可以利用每一个特征来划分数据集。每一个特征的不同，划分的数据集也不同，进而信息发生的变化也不同。因此，信息增益肯定也不同。如果某一个特征导致了划分数据集之后信息增益最大。则该特征就是最好特征。那么信息增益如何计算？这个时候我们可以引入熵的概念。
熵或香农熵：集合信息的度量方式。（信息的期望值）
信息：如果待分类的事务要划分在多个分类中，则符号（分类）xi的信息定义为：
l(xi) = -log以2为底p(xi)的对数
其中：p(xi)为选择该分类的概率。
为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面的公式得到：其中n是分类的数目。
# 该代码用于计算香农熵
# 该代码位于trees.py文件中
from math import log
def calcShannonEnt(dataSet):
numEntries = len(dataSet) # 计算数据集中的样本数
labelCounts = {} # 用一个字典来计算每个类别的数量
for featVec in dataSet: # 遍历每一个样本
currentLabel = featVec[-1] # 提取每一个样本的类别(鱼类->yes/非鱼类->no)
# if代码的作用就是为了统计数据集中类别数量
# 如果当前样本的类别并不在字典中，那么把类别添加到字典并且初始化为1，否则该类别数量+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 # 返回该集合的熵
# 该函数的作用是创建数据集，以便于计算该集合的熵
def createDataSet():
# 表示样本的数据集
dataSet = [[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']]
# 表示特征的名字分别是：不浮出水面是否可以生存，是否由脚蹼
labels = ['no surfacing', 'flippers']
#change to discrete values
return dataSet, labels
# 该代码用于测试
# 该代码位于personalTest.py文件中
import trees
dataSet,labels = trees.createDataSet()
print(trees.calcShannonEnt(dataSet))
'''
0.9709505944546686
当我们增加在数据集中的类别时，熵的大小有什么变化？
'''
import trees
dataSet,labels = trees.createDataSet()
dataSet[0][-1] = 'maybe' # 给第一个样本的类别改为maybe
print(trees.calcShannonEnt(dataSet))
'''
1.3709505944546687
通过以上实验，我们可以看出：熵越大，集合中的类别就越多。（混合的数据越多）（集合的无序程度越大）
当某一个集合的熵的值足够小，那么该集合所含的类别就越少。这样的话，我们就可以根据熵的大小来判定集合中的子项是否都属于同一个类别（该集合是否只有一个类别）
'''
6. 划分数据集
# 该函数的作用是根据指定的特征值来划分数据集,只要某样本符合该条件，都会划分到数据集中。
# 需要注意的是，划分之后的数据集中的每一个样本都会去掉该特征。因为已经按照此特征来进行划分子集，子集中的每一个样本当然不能包含此特征。
# 本质上，决策树就是对数据集一层一层的过滤与筛选，减小数据集的大小，最后找到目标答案（数据集）的过程。
# 该函数位于trees.py文件中
# dataSet为数据集、axis为特征（以下标表示）、value代表指定特征的值
def splitDataSet(dataSet, axis, value):
retDataSet = [] # 返回的划分之后的结果数据集
for featVec in dataSet: # 遍历数据集，其中featVec为数据集当中的一个样本
if featVec[axis] == value: # 如果某一个样本的特征，它的值为value，那么就进行处理。否则，不处理。
# 以下语句的作用为：消去指定样本的特征,并添加到结果集中。
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet # 返回结果集
# 该函数的作用是用于测试
# 该函数位于personalTest.py文件中
import trees
dataSet,labels = trees.createDataSet()
print(trees.splitDataSet(dataSet,0,1)) # 以第一个特征值为1为指标划分数据集
'''
[[1, 'yes'], [1, 'yes'], [0, 'no']]
'''
上述代码的extend和append需要区分一下，具体代码如下：
# 该函数的作用就是找到最好的数据集划分方式。找到最适合划分数据集的特征
# 该函数依次遍历每一个特征，按照特征划分数据集并计算经验条件熵，再根据熵与经验条件熵的差来计算某特征的信息增益。
# 获得信息增益最高的特征，就是划分数据集的最佳特征。
# 该函数位于trees.py文件中
# 输入一个集合，该函数会返回划分该集合的最佳特征
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] # 获取某特征在总集合中的全部取值
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 # 返回最佳特征
补充相关知识：经验条件熵
以上图片转载于：https://blog.csdn.net/user_zongji/article/details/107008220
# 该代码的作用是用于测试
# 该代码位于personalTest.py文件中
import trees
dataSet,labels = trees.createDataSet()
print(trees.chooseBestFeatureToSplit(dataSet))
'''
0 # 即0号特征为划分该数据集的最好特征
'''