下载掌阅APP，畅读海量书库
立即打开
首先，我们定义一个函数用来计算熵。函数以一组类标签（0或者1组成的数组）为输入，输出数据集的熵。熵越高，表示数据集越混乱；熵越低，表示数据集越单纯。决策树希望找到能够把数据集分割为较为单纯的子集的划分。
import math
#计算概率为x的随机事件的熵
def h(x):
if x>=1 or x<=0:return 0
return-x * math.log2(x)
#计算包含0和1两个类别的数据集的熵
def data_entropy(labels):
if len(labels)<1:return 0
#计算正样本比例
p=sum(labels)/len(labels)
#计算负样本数量
n=1-p
return h(p)+h(n)
下面我们测试上面的函数。可以看到，它的输出能够反映出数据集中类标签的纯度。当数据集中正负样本数量参半时，熵达到最大值。反之，当数据集只包含单一类别的样本时，熵达到最小值。
print(data_entropy([0,0,0,1,1,1])) #输出1，表示熵最高，数据集中正负样本参半，纯度低 print(data_entropy([0,1,1,1,1,1])) #输出0.65，比上面的数据集要单纯一些 print(data_entropy([0,0,0,0,0,0])) #输出0，表示熵最低，数据集最为纯粹，只包含单一类别的样本
下面，我们要在前面所述的天气二分类问题的数据上进行决策树算法的实验。首先，准备数据集，将每一条数据描述为一个具有5个元素的数组，分别记录天气的观感、温度、湿度、风力和是否适合运动。对于天气观感，用0表示晴，1表示阴，2表示雨；对于温度，用0表示热，1表示中等，2表示凉；对于湿度，用0表示潮湿，1表示正常；对于风力，用0表示无风，1表示有风；对于类标签，即是否适合运动，用0表示不适合，1表示适合。
import numpy #每一行的5个元素分别表示 #天气观感（晴、阴、雨），温度，湿度，风力和是否适合运动 weather_data=numpy.array([[0,0,0,0,0],[0,0,0,1,0],[0,1,0,0,0], [0,2,1,0,1],[0,1,1,1,1],[1,0,0,0,1],[1,2,1,1,1], [1,1,0,1,1],[1,0,1,0,1],[2,1,0,0,1],[2,2,1,0,1], [2,2,1,1,0],[2,1,1,0,1],[2,1,0,1,0]])
值得注意的是，我们用numpy软件包
将数据封装为一个numpy数组。这是因为，numpy数组可以存储各种不同维度的向量（一维数组）、矩阵（二维数组）和张量（三维或者三维以上的数组），而且可以很方便地对这些数组进行索引和计算。可以使用Python的软件包管理器
pip
来安装numpy软件包。我们后面还会常常用到numpy软件包进行数据处理和计算。
pip install numpy
下面我们开始实现决策树算法。决策树算法递归地分割数据集，每一次都尽可能使得分割得到的两个数据子集的熵较低。因此，需要计算数据划分的熵。这里我们定义一个函数，以数据集、划分选取的属性和属性值为输入，输出为划分的熵，以及划分得到的两个数据子集。
#计算某个划分的熵
#输入是数据集、划分选取的属性和属性值
#输出是熵和分割出的两个数据集
def split_entropy(data, property_id, property_value):
#选取property_id这一列与property_value进行比较
left_index=data[:, property_id]==property_value
right_index=data[:, property_id] !=property_value
#根据比较结果选取分支两侧的数据子集
left_data=data[left_index,:]
right_data=data[right_index,:]
#取数据子集的最后一列，即类标签列，计算子集的熵
left_entropy=data_entropy(left_data[:,-1])
right_entropy=data_entropy(right_data[:,-1])
#计算分割后两个子集的加权平均熵
split_entropy=(left_data.shape[0]*left_entropy+right_data.shape[0]*right_entropy)/data.shape[0]
return split_entropy, left_data, right_data
print(split_entropy(weather_data, 0, 0)[0])
#输出0.838，即用天气观感“晴”作为划分条件，分割得到的两个数据集的平均熵是0.838
在此基础上，我们可以通过枚举所有属性和可能的划分，找到对于当前数据集最优的划分。
#选择划分的函数
#输入是数据集，输出是划分后的熵、选取的属性和属性值，划分后的数据子集
def find_split(data):
min_entropy=None
best_split_property_id=None
best_split_property_value=None
best_split_left=None
best_split_right=None
#枚举所有属性
for index in range(data.shape[1]-1):
#获取该属性的可能取值
unique_values=numpy.unique(data[:,index])
if len(unique_values)<2:continue
#枚举属性和可能的划分（划分比取值数量少1）
for value in unique_values[0:-1]:
entropy, left, right=split_entropy(data, index, value)
if min_entropy is None or min_entropy>entropy:
min_entropy=entropy
best_split_property_id=index
best_split_property_value=value
best_split_left=left
best_split_right=right
return min_entropy, best_split_property_id, best_split_property_value,
best_split_left, best_split_right
split=find_split(weather_data)
print('entropy={0}property_id={1}, property_value={2}'.format(
split[0], split[1], split[2]))
#输出：
# entropy=0.714... property_id=0, property_value=1
从上面的实验结果可以看到，对于天气数据集，第一个划分应该选取天气观感是否为“阴”，这样划分后数据集的平均熵最小。
下面我们来构造并打印决策树，只要递归地使用 find_split 函数即可。当无法产生有效划分的时候，就到达了决策树的叶节点；如果能够将数据集划分为两个子集，就可以把它们作为左右子树递归地划分下去。
#构造并打印决策树
#输入参数是数据集和控制缩进用的空白
def build_decision_tree(data, tabspace):
class_count=len(numpy.unique(data[:,-1]))
#如果数据集包含不同类别，就进行划分
if class_count>1:
split=find_split(data)
else:
split=[None]
#如果无法划分，则到达决策树的叶节点
if split[0] is None:
print('{0}class={1}'.format(tabspace, data[0,-1]))
return
#如果划分成功，递归地划分左右子树
print('{0}property{1}value={2}'.format(tabspace, split[1], split[2]))
build_decision_tree(split[3], tabspace+' ')
build_decision_tree(split[4], tabspace+' ')
build_decision_tree(weather_data, '')
上面的算法在天气数据集上会输出下面的决策树。从上向下读这个输出结果，可以看到第1行是决策树的根节点所选取的划分，用属性0取值1（天气观感为阴）来划分。第2行缩进显示了左子树，左子树仅包含类别为1（适合运动）的样本，因此不能继续划分，达到了叶节点。第3行显示了右子树，右子树采取属性2取值0（湿度为潮湿）进行划分，分为左、右两棵子树。两棵子树可以继续递归划分下去，以此类推。读者可以将它与图2.2做对比，看是否一致。
property0 value=1
class=1
property2 value=0
property0 value=0
class=0
property3 value=0
class=1
class=0
property3 value=0
class=1
property0 value=0
class=1
class=0
当我们实际使用机器学习算法的时候，通常不需要从头开始重复“制造轮子”。“制造轮子”是我们学习的必由之路，可以帮助我们理解“轮子”的原理。但是在实际使用过程中，我们可以直接使用一些已经构筑好的、更加坚固的“轮子”。我们使用软件包有两方面原因。一方面，有些算法进行完善的实现是相当复杂的，软件包可以帮助我们节省时间，避免重复劳动；另一方面，软件包对算法的性能进行了充分的优化，排除了常见的漏洞，妥善处理了可能存在的边界情况或者极端情况，可以有效地帮助我们快速、准确地使用各种算法和模型。
当然，“制造轮子”在有些情况下仍然是无法避免的。比如，如果读者希望深入理解某个算法或者模型的原理，或者想对算法进行一些修改、裁剪或者改进，那么，从头开始实现这个算法是很有必要的。再如，如果出于某些工程需求，我们要把算法应用于某个特定场景中，或者对算法的性能和运行环境有某些特殊要求，那么就需要采用适于目标环境的实现方式，针对特定的应用场景对算法的实现进行技术上的优化，这就要求我们必须重新实现该算法，而这是复用现有软件包难以实现的。
在这里，我们介绍scikit-learn软件包
该软件包实现了机器学习的大部分常用算法和模型，读者可以利用这个软件包快速地试验或者应用某种算法。我们可以用Python软件包管理器安装这个软件包。
pip install scikit-learn
下面我们利用scikit-learn构建决策树分类器。在scikit-learn软件包中，分类器的训练数据通常包含样本属性数据 X 和样本的类标签 Y 两个部分。其中， X 是一个矩阵，矩阵的每一行是一个样本，样本的不同属性对应于矩阵的各列。而 Y 是一个数组，包含各样本的类标签。我们使用 fit 方法从样本数据构造决策树，用 predict 方法对输入样本进行分类。分类方法可以接收多行数据（多个样本），同时对多行数据进行分类，因此，输入是一个二维矩阵，输出是一个数组。
from sklearn import tree X=weather_data[:,0:-1] Y=weather_data[:,-1] clf=tree.DecisionTreeClassifier() #用数据构造决策树 clf.fit(X, Y) #用决策树进行分类 result=clf.predict([[0,0,0,0]]) print(result) #输出：[0]表示不适合运动 #将决策树的结构可视化 tree.plot_tree(clf)
如图2.4所示，在可视化的决策树结构图中，每个节点的第1行表示划分子树的条件，叶节点由于不需要进一步划分，因此这一行是缺失的。第2行是落入节点的数据子集的基尼不纯度（Gini值），第3行是数据子集的样本量，第4行是不同类别的样本数量。图2.4中的树结构和我们用ID3算法得到的并不相同，其中的原因有两点。
1）scikit-learn软件包采用的是CART算法 [1] ，该算法可以更好地用于具有连续取值的属性，并且同时适用于分类和回归问题。
2）该算法将天气观感这样的离散枚举型样本属性当作连续值处理，因此，得到的划分与ID3算法不同。
图2.4 用scikit-learn构造决策树并可视化的结果
值得注意的是，scikit-learn中的CART决策树算法并不支持枚举型的样本属性，只支持数值型的样本属性，也就是说，样本属性构成的矩阵 X 中的值必须全部为数值。严格来说，天气观感为晴、阴、雨这样的属性是枚举类型的，3个值之间并无数值上的大小关系，将它们直接映射到单个数值是稍有问题的。比如，如果设0表示晴，1表示阴，2表示雨，就隐含了这样的假设，即晴和阴之间的距离与阴和雨之间的距离是相同的，而晴和雨之间的距离是晴和阴之间距离的2倍。这样的假设对于天气观感这个属性来说并没有太大坏处。然而，对于某些枚举值更多的属性或者类别信息来说，将它们直接映射到整数上，是极有可能带来问题的。比如，假设有个属性表示动物的类别，那么将它们映射到整数上就会给这些类别凭空赋予次序的关系和距离的差异。严格来说，为了使枚举值之间的距离相互均等，应该采取“独热”（One-hot）表示映射到数值类型，比如，天气观感为“晴、阴、雨”，应该映射到3个数值维度，分别用1和0表示“是否晴”“是否阴”“是否雨”，于是“晴、阴、雨”分别表示为[1，0，0]，[0，1，0]，[0，0，1]。这样的数值表示保证了各个枚举值之间的欧氏距离一致，不会引入次序关系和距离差异，是更加严谨的表示方式。“独热”表示是机器学习中常用的数据表达方式，我们会常常遇到它。