文中的代码和数据集下载地址：
https://github.com/TimePickerWang/MachineLearningInAction
介绍决策树之前先介绍两个信息论里的概念：熵和信息增益。
1.熵：代表了信息的混乱程度。也就是说熵越高，混合的数据越多，越无序。熵的计算方式如下（其中
是样本为某一类别的概率。）：
2.信息增益：信息增益可以理解为熵的减少或者说是数据无序度的减少。在划分数据时。为了使划分后数据的熵减少，我们需要选择信息增益最高的特征来划分数据。
决策树的创建过程描述如下，记为creatBranch()方法：
检测数据中的每个样本是否属于同一类别
如果是，返回类标签
否则执行以下步骤：
选择信息增益最高的特征
划分数据集
创建分支节点
对于划分后的每个子集调用creatBranch()进行递归操作
返回分支节点下面直接上计算熵的代码：
from math import log
''' 计算香农熵 Input: data_set: 需要计算熵的m个样本，每个样本向量的最后一列是类别 Output:香农熵的值 '''
def calc_shannonEnt(data_set):
m = len(data_set)
lable_counts = {}
for featVec in data_set:
current_lable = featVec[-1]
lable_counts[current_lable] = lable_counts.get(current_lable, 0) + 1
shannon_ent = 0
for key in lable_counts:
prob = float(lable_counts[key])/m
shannon_ent -= prob * log(prob, 2)
return shannon_ent为了方便计算熵，以上代码用一个字典记录了样本中数据的类别及其出现的次数。传入的数据是一个样本集，每个样本看成一个向量，样本向量的最后一列是该样本所属的类别。
ID3在每次划分数据时，会根据获得信息增益最大的特征来划分数据。并且在每次划分数据后，会删除该特征。然后把剩下的数据作为创建子树的数据重新进行划分，直到所有特征划分完毕。以下代码是通过某一特征来划分数据集，返回的是划分后的数据集：
''' 划分数据集 Input: data_set: 待划分的数据集 axis：划分数据集的特征 value：需要返回的特征的值 Output:划分后的数据集 '''
def split_dataSet(data_set, axis, value):
ret_data_set = []
for feat_vec in data_set:
if feat_vec[axis] == value:
reduced_feat_vec = feat_vec[:axis]
reduced_feat_vec += feat_vec[axis+1:]
ret_data_set.append(reduced_feat_vec)
return ret_data_set为了直观感受以下，假设有如下数据集调用了split_dataSet()方法：
data_set = [[0, 1, 0, 0, 'yes'],
[1, 1, 0, 0, 'yes'],
[0, 1, 1, 0, 'yes'],
[0, 0, 1, 0, 'yes'],
[1, 0, 0, 0, 'yes'],
[0, 0, 1, 0, 'yes'],
[0, 0, 0, 0, 'no'],
[1, 1, 1, 1, 'no'],
[0, 0, 0, 1, 'no'],
[0, 1, 1, 1, 'no'],
[0, 1, 0, 1, 'no']]
split_dataSet(data_set, 1, 0)此时的返回如下：
可以看出返回的是原数据集中第2个特征为0，并把第二个特征删除后的数据。
知道了熵的计算方式和划分数据的方式，接下来需要通过获得信息增益最高的特征来划分数据了。代码如下：
''' Input: data_set: 待划分的数据集 Output:划分结果最好（划分后信息增益最高）的特征索引 '''
def choose_best_feature_to_split(data_set):
feature_num = len(data_set[0]) - 1 # 特征的个数
m = len(data_set) # 样本数
base_entropy = calc_shannonEnt(data_set) # 经验熵
best_info_gain = 0.0 # 最好的信息增益值
best_feature = -1 # 划分后信息增益最高的特征索引值
for i in range(feature_num):
# 数据集中所有第i个特征的值存到feat_list中
feat_list = [example[i] for example in data_set]
unique_feat = set(feat_list)
new_entropy = 0.0 # 条件熵
for feature in unique_feat:
# 根据第i个特征划分数据
sub_data_set = split_dataSet(data_set, i, feature)
prob = len(sub_data_set)/m
new_entropy += prob * calc_shannonEnt(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以上代码仅仅进行了一次数据的划分。首先计算了一下数据划分前的熵，然后遍历数据集的每一个特征，通过某一特征的所有可能取值调用split_dataSet()方法来划分数据，并计算划分数据后的熵之和。将划分数据前后的两个熵香减即是信息增益，用变量best_feature保存获得信息增益最大时划分特征的索引，在遍历完所有特征后返回，此时best_feature的值即是划分数据最好的方式。
要创建一颗决策树，仅仅进行一次划分是不够的，我们需要用完所有的特征。但如果我们用完所有的特征后，数据的类标签依然存在多个，这时我们需要结合kNN中多数表决的方式确定某一样本的类别。多数表决的方式如下：
''' Input: class_list: 分类名称的列表 Output:通过投票机制，返回出现次数最多的分类名称 '''
def majority_label(class_list):
class_count = {}
for vote in class_list:
class_count[vote] = class_count.get(vote, 0) + 1
sorted_class_count = sorted(class_count.items(), key=lambda item: item[1], reverse=True)
return sorted_class_count[0][0]上述方法传入的是一个类别向量（也就是数据集中最后一列值组成的向量），是一个行向量。对sorted()方法不了解的可以看我另一篇博客一：细说python3中sort和sorted。最后，我们就可以用之前的代码来创建决策树了，创建树的代码如下：
''' Input: data_set: 待划分的数据集 labels:标签列表 Output:表示决策树结构的字典 '''
def creat_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_label(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]
feature_values = [example[best_feature] for example in data_set]
unique_feature = set(feature_values)
for value in unique_feature:
sub_lables = labels[:]
my_tree[best_feature_label][value] = creat_tree(
split_dataSet(data_set, best_feature, value), sub_lables)
return my_tree以上代码中，用字典来保存树的所有信息。划分数据最好方式的特征索引用变量best_feature来保存，然后通过该特征的所有来划分数据，创建子树。该方法的放回有两种情况：1.最后的类标签。2.保存子树信息的字典。
好了，接下来通过一些简单的测试数据来试试该算法，测试数据如下：
def test_fun():
data_set = [[0, 1, 0, 0, 'yes'],
[1, 1, 0, 0, 'yes'],
[0, 1, 1, 0, 'yes'],
[0, 0, 1, 0, 'yes'],
[1, 0, 0, 0, 'yes'],
[0, 0, 1, 0, 'yes'],
[0, 0, 0, 0, 'no'],
[1, 1, 1, 1, 'no'],
[0, 0, 0, 1, 'no'],
[0, 1, 1, 1, 'no'],
[0, 1, 0, 1, 'no']]
labels = ["have care", "have house", "have money", "have wife"]
tree = creat_tree(data_set, labels[:])
print(tree)输出的结果如下：
该结果是一颗如下图所示的树：
决策树的一大优点就是我们可以把树结构序列化之后保存起来，这样在分类数据时就不用每次都计算来建造树了，序列化和反序列化的代码如下：
import pickle
''' Input: input_tree: 表示决策树结构的字典 filename: 需要存储的文件名 '''
# 将字典类型的树结构序列化后存储在文件中
def store_tree(input_tree, filename = "./testTree.txt"):
fw = open(filename, 'wb') # 以二进制格式打开一个文件只用于写入。
pickle.dump(input_tree, fw)
fw.close()
''' Input: filename: 需要读取的文件名 Output: 决策树字典 '''
def grab_tree(filename = "./testTree.txt"):
fr = open(filename, "rb")
return pickle.load(fr)需要注意的是，这里序列化和反序列化都需要用二进制格式打开文件，这里书上的代码有问题。这里文件的路径默认为当前路径下的testTree.txt文件。
当跟新数据进行分时的代码如下：
''' Input: input_tree: 表示决策树结构的字典 feat_labels: 标签列表 test_vec：待测试的向量 Output:分类结果 '''
def classify(input_tree, feat_labels, test_vec):
first_fect = list(input_tree.keys())[0]
second_dict = input_tree[first_fect]
feat_index = feat_labels.index(first_fect)
for key in second_dict.keys():
if test_vec[feat_index] == key:
if type(second_dict[key]).__name__ == 'dict':
class_lable = classify(second_dict[key], feat_labels, test_vec)
else:
class_lable = second_dict[key]
return class_lable这也是一个递归的函数，需要判断某一结点是叶子结点函数子树。如果是子树，则该结点的类型为字典类型。
好了， 现在我们将以上测试数据先保存起来，然后通过反序列化，直接通过保存好的决策树树来根新样本分类。代码如下：
# 分类测试数据
def classify_test_data():
tree = grab_tree()
test_vec1 = [1, 0, 1, 0]
test_vec2 = [0, 1, 0, 1]
labels = ["has care", "has house", "has money", "has wife"]
print("分类结果：" + classify(tree, labels, test_vec1))
print("分类结果：" + classify(tree, labels, test_vec2))
classify_test_data()最后结果如下：
在书上还提到了将决策树的结构画出来，这里不做议论，书中还有一个预测隐形眼镜类型的例子，其数据集和代码我在开始已经放出来了，可以去下载，顺便点个星星支持一下，^_^。