上图所示的就是一个决策树，长方形代表判断模块，椭圆形代表终止模块，表示已得出结论，可以终止运行，左右箭头称作分支。
-
决策树的工作原理简单来说就是通过一系列条件判断来将数据分类，最终形成一个树状结构。数据集中的每个数据都可以顺着决策树的条件判断找到符合这个数据的类。
决策树的优势在于数据形式非常容易理解，决策树的一个重要任务就是为了理解数据中所蕴含的知识信息，因此决策树可以使用不熟悉的数据集合，并从中提取出一系列的规则，机器根据数据集创建规则的过程，就是机器学习的过程。
-
决策树的优点在于计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
-
缺点在于可能会产生过度匹配的问题（就是过拟合）
-
决策树适用的数据类型有两种：数值型和标称型。
首先我们讨论数学上如何使用信息论划分数据集。在构造决策树时，我们需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。那么我们如何度量哪种划分数据集的方式更好呢？
我们划分数据集的大原则是：将无序的数据变得更加有序。我们可以使用多种方式划分数据集，在这里只说一种方式。我们可以使用信息论度量信息，我们可以在划分数据之前或之后使用信息论量化度量信息的内容。
在划分数据集之前之后信息发生的变化，我们称之为信息增益。知道如何计算信息增益后，我们就可以在计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。
集合信息的度量方式称为香农熵或者简称熵。熵被定义为信息的期望值，在明确这个概念之前，我们必须知道信息的定义。
假设一个待分类的事务可能划分在多个分类之中，简单的来说就是多分类情况，则符号
的信息定义为：
其中
是选择该分类的概率。
为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过这个公式得到：
知道了如何计算熵后（这里只是简单的介绍如何计算熵），我们就可以知道如何计算信息增益了，我们计算划分数据集之前整个数据集的熵，在计算划分数据集后的熵，将这两个熵相减则得出了信息增益的值。
以下是使用python来计算数据集的熵
def calcShannonEnt(data_set):
'''计算给定数据集的香农熵（即熵）'''
num_entries = len(data_set)
labels_counts = {}
for feat_value in data_set:
current_label = feat_value[-1]
if current_label not in labels_counts.keys():
labels_counts[current_label] = 0
labels_counts[current_label] += 1
shannon_ent = 0.0 # 熵
for key in labels_counts:
prob = float(labels_counts[key]) / num_entries # 计算p(xi)的值
shannon_ent -= prob * log(prob, 2) # 计算H值
return shannon_ent
熵越高代表混合的数据也越多。
按照给定的特征来划分数据集。
def split_data_set(data_set, axis, value): # data_set 待划分的数据集 axis 划分数据集的特征 value: 需要返回的特征的值
'''按照给定特征划分数据集'''
ret_data_set = []
for feat_value in data_set:
if feat_value[axis] == value: # 如果这个数据点中该列特征的值等于value即等与需要的特征，那么将这个特征的前后都添加到一个新的列表中去
reduced_feat_value = feat_value[:axis]
reduced_feat_value.extend(feat_value[axis+1:])
ret_data_set.append(reduced_feat_value)
return ret_data_set
通过实现了上面的两个函数，现在我们可以将其结合起来选择最好的数据集划分方式了
def choose_best_feature_to_split(data_set):
'''选择最好的数据集划分方式'''
num_features = len(data_set[0]) - 1
base_entropy = calcShannonEnt(data_set) # 获得一开始数据集的熵
best_info_gain = 0.0
best_feature = -1
for i in range(num_features):
feat_list = [example[i] for example in data_set] # 将数据集中这个特征对应的所有值取出来
unique_value = set(feat_list) # 创建唯一的分类标签列表
new_entropy = 0.0
for value in unique_value: # 计算每种划分方式的信息熵
sub_data_set = split_data_set(data_set, i, value)
prob = len(sub_data_set) / float(len(data_set)) # 计算这个划分方式下数据集占原来数据集的百分比
new_entropy += prob * calcShannonEnt(sub_data_set) # 这种划分方式下的数据集的熵
info_gain = base_entropy - new_entropy # 计算信息增益
if info_gain > best_info_gain: # 计算最好的信息增益
best_info_gain = info_gain
best_feature = i
return best_feature # 返回最好的划分特征
上述函数中使用的数据都需要满足一定的要求：都一个要求是，数据必须由列表元素组成的列表，而且所有的列表元素的长度都一样；第二个要求是，数据的最后一列或者每个实例的最后一个元素是当前实例的类别标签。
现在我们实现了如何选择最好的数据集方式函数，下面开始使用递归构造决策树，递归结束的条件是：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。当如果数据集已经处理了所有属性，但是类标签依然不是唯一的时候，我们如何定义该叶子节点呢？在这种情况下，我们通常使用多数表决的方法决定该叶子节点的分类。代码如下所示
def majority_cnt(class_list):
'''多数表决决定分类'''
class_count = {}
for vote in class_list:
if vote not in class_count:
class_count[vote] = 0
class_count[vote] += 1
sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True) # 对字典进行排序
return sorted_class_count[0][0]
下面是创建树的函数代码
def create_tree(data_set, labels):
'''创建树的递归函数'''
class_list = [example[-1] for example in data_set]
# 递归函数的停止条件一：所有的类标签完全相同
if class_list.count(class_list[0]) == len(class_list): # 类别完全相同则停止继续划分
return class_list[0] # 标签完全一样的话，就没有在进行划分的必要了，全部数据都属于一个类别了
# 递归函数的停止条件二：使用完了所有的特征，仍然不能讲数据集划分成仅包含唯一类别的分组
if len(data_set[0]) == 1: # 遍历完所有特征后返回出现次数最多的类别
return majority_cnt(class_list)
best_feature = choose_best_feature_to_split(data_set) # 当前数据集选取的最好的特征
best_feature_label = labels[best_feature]
my_tree = {best_feature_label: {}}
del(labels[best_feature])
feat_values = [example[best_feature] for example in data_set] # 得到列表包含的所有属性值
unique_values = set(feat_values) # 去除重复值
for value in unique_values:
sub_labels = labels[:] # 在这里拷贝了类标签列表，是为了不改变原始列表中的内容
my_tree[best_feature_label][value] = create_tree(split_data_set(data_set, best_feature, value), sub_labels)
return my_tree # 储存了树的所有信息
当我们拥有了树的所有信息后，我们可以通过使用matplotlib来绘制树，下面是使用Matplotlib的注解功能绘制树形图。
import matplotlib.pyplot as plt
# 定制文本框和箭头格式
decision_node = dict(boxstyle="sawtooth", fc="0.8")
leaf_node = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")
'''
使用文本注解绘制树节点
'''
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 getNumLeafs(myTree):
numLeafs = 0
firstStr = list(myTree.keys())[0]
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]).__name__ == '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():
if type(secondDict[key]).__name__ == 'dict': # 测试节点的数据类型是否为字典
thisDepth = 1 + getTreeDepth(secondDict[key])
else: thisDepth = 1
if thisDepth > maxDepth: maxDepth = thisDepth
return maxDepth
def plotMidText(cntrPt, parentPt, txtString):
xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]
yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)
def plotTree(myTree, parentPt, nodeTxt): # if the first key tells you what feat was split on
numLeafs = getNumLeafs(myTree) # this determines the x width of this tree
depth = getTreeDepth(myTree)
firstStr = list(myTree.keys())[0] # 这个节点的文本标签
cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)
plotMidText(cntrPt, parentPt, nodeTxt)
plotNode(firstStr, cntrPt, parentPt, decision_node)
secondDict = myTree[firstStr]
plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD
for key in secondDict.keys():
if type(secondDict[key]).__name__ == 'dict': # 测试节点类型是否为字典，
plotTree(secondDict[key], cntrPt, str(key)) # 递归
else: # 如果不是字典，则表明是个叶节点
plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW
plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leaf_node)
plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD
# if you do get a dictonary you know it's a tree, and the first element will be another dict
def createPlot(inTree): # 绘制函数
fig = plt.figure(1, facecolor='white')
fig.clf()
axprops = dict(xticks=[], yticks=[])
createPlot.ax1 = plt.subplot(111, frameon=False, **axprops) # no ticks
# createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses
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()
当我们构建完一颗决策树后，我们可以用pickle模块将其存储起来，代码如下：
# 使用pickle模块存储决策树
def store_tree(input_tree, filenmae):
import pickle
fw = open(filenmae, 'wb')
pickle.dump(input_tree, fw)
fw.close()
# 从文件中读取决策树信息
def grab_tree(filename):
import pickle
fr = open(filename, 'rb')
return pickle.load(fr)
现在我们来测试算法：使用决策树预测隐形眼镜类型，这里我们用到的数据来自www.manning.com/MachineLearninginAction中的CH03文件夹下的lenses.txt。
def classifiy(input_tree, feature_labels, test_vector):
'''决策树的分类函数'''
first_str = list(input_tree.keys())[0]
second_dict = input_tree[first_str]
feature_index = feature_labels.index(first_str) # 将标签字符串转换为索引
for key in second_dict.keys():
if test_vector[feature_index] == key:
if type(second_dict[key]).__name__ == 'dict':
class_label = classifiy(second_dict[key], feature_labels, test_vector)
else:
class_label = second_dict[key]
return class_label
fr = open('lenses.txt')
lenses = [inst.strip().split('\t') for inst in fr.readlines()]
lenses_labeles = ['age', 'prescipt', 'astigmatic', 'tearRate']
lenses_tree = create_tree(lenses, lenses_labeles.copy()) # 这里传递类别标签的副本过去，防止改变原标签
createPlot(lenses_tree )
调用createPlot()函数得到的图像如下，
从图中可以发现，医生最多需要问四个问题就能确定患者需要佩戴哪种类型的隐形眼镜。本章构造决策树使用的算法是ID3，ID3算法无法直接处理数值型数据，其次决策树对于其从未见过的情况可能会做出不是我们想要的分类结果。决策树可以很好的匹配我们给它的数据集，但是这很可能会过度匹配数据集，导致产生太多的分支，我们可以通过裁剪决策树（即剪枝），合并相邻的无法产生大量信息增益的叶节点，从而消除过度匹配的问题。