没有树木，哪来森林？谈一谈随机森林算法的基础——决策树与熵

前面几期文章我们通过简单的KNN算法带着大家入门了机器学习，并通过几个案例带着大家熟悉了在Python中的调用sklearn下面封装好的算法实施机器学习项目的一般流程。从本期开始我们进入到下一个算法——决策树（Deceious Tree）以及基于决策树通过加入集成算法思想（ensemble learning）而形成的随机森林（Random forest)和极限森林（Extreme forest)算法的学习。特别是随机森林算法，在最近几年的公开算法大赛中取得了比好的成绩，知名度较高。后面我们也会重点介绍。

我们知道所谓的机器学习，就是让机器模拟人类的学习方法而获取知识过程。把人类从经验/数据中归纳出来可以用与指导生产实践或者做决策的知识/方法等这一过程归抽象成算法，并通过编码可以让机器来执行。这些机器通过执行代码，从而获得我们所谓的智能。决策树就是一个典型的例子。实际上我们每个人脑袋里面对某一事物进行判断很多时候就是一棵树。比如办公室新来了一位小伙伴，大家聚在一起八卦这位小伙伴薪资的时候，很多人肯定会问他的学历啊工作年限啊是否是名校毕业等等，然后根据这些条件来估计薪资水平。把这些条件归纳起来并通过树状结果进行分类或者拟合就是决策树，如下面这张图：

salary.JPG

在实际操作中我们还可以更多的分支，如是否是985学校毕业，是否从大厂跳槽过来等等。我们可以想象：如果可以获得的参考数据越多，我们的结论就会越准确。这个和机器学习完全一致，即可以供算法学习的数据量越大，算法的结果越精确。这也是为什么近年来随着大数据的出现，智能算法精度越来越高。很多时候算法对事物趋势的判断已经远远超越我们人类。国家大力发展5G，IoT, 大数据等基础IT技术（新基建），其目的就是要抢占人工智能这一科技制高点。好了，又扯多了。
从上面这张图我们可以看到决策树算法是根据给定的数据集归纳出分类规则，并采用自顶向下的递归划分（Recursive Partitioning)方式，以树的形式展现出来。这其中，节点是树的主体部分。一般来说，最上面一层为根节点（没有父节点的节点），如上图中的学历菱形框。一个节点按照某个属性分裂时，这个属性就被成为分裂属性，如上图中学历属性和工作年限属性。分到最后出现没有子节点的节点时，该节点就被称为叶子节点。

从这里我们可以看出决策树分类算法的实现关键在于如何根据训练数据构建一颗决策树。而构建决策树的核心问题就在于如何选择一个合适的分裂属性进行一次分裂以及如何制定合适的分裂标准（如工作年限分裂中的>3年和<3年）来产生相应的分支。
上面的八卦薪资例子中，第一个分裂节点可以选择学历，也可以选择工作年限。那么在实际操作中该如何选择呢？这就时下面要说的信息熵（Information Entropy)的概念。算法会根据所有样本信息熵的变化（信息增益）来选择最佳分类。因而信息熵就是决策树方法中分支产生的衡量标准之一。

信息熵来源热力学中的熵（Entropy)的概念。最早由德国物理学家克劳修斯提出，用来表述某个体系的混乱程度。在此基础上，美国的数学家，信息论的创始人香农提出了信息熵的概念。它代表了一个给定数据集中的不确定性或者随机性程度的度量。当一个数据集中的记录全部为同一类时，则没有不确定性，此时熵为0。因此我们也可以把熵看成是信息的数学期望。若要求出熵的大小，则先要计算信息：

设某个事物具有 $n$ 种相互独立的可能结果，则信息的定义为：
$l(x_i) = -log_2p(x_i)$
为什么是以2为底的对数？这个可能和信息中的最小单位比特有关（一个比特只有0/1 2种状态其中），其中 $x_i$ 表示第 $i$ 个分类， $p(x_i)$ 表示第 $i$ 个分类的概率函数，并且： $\sum_{i=1}^np(x_i) = 1$
由此，信息熵 $H（X）$ 就可以表示为：
$H(X) = - \sum_{i=1}^np(x_i) log_2p(x_i)$
对于一个简单的二元分类，此时 $n=2$ ，那么其熵为：
$H(X) = - p(x_1) log_2p(x_1) - p(x_2) log_2p(x_2)$

通过信息熵我们可以精确的度量信息量的大小，香农也因为这一成就成为信息学领域公认的奠基人。我觉得这一成就完全可以媲美牛顿的万有引力定律和爱因斯坦的质能方程，前者确统一了宇宙所有天体的运行规律，后者深刻揭示了质量和能量只不过是同一事物不同的侧面。

下面我们就用Python中内置的鸢尾花数据集来实现决策树算法。

1. 导入计算库和数据

注意决策树分类算法是放在sklearn.tree下面

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from sklearn import datasets
from sklearn import tree

再把鸢尾花的数据导进来

iris = datasets.load_iris()

X = iris['data']
y = iris['target']

iris_feature_names = iris.feature_names
iris_feature_names
print(iris_feature_names)
>>>['sepal length (cm)', 'sepal width (cm)', 'petal length (cm)', 'petal width (cm)']

上面的代码中，我们鸢尾花数据集中的样本的4个维度的特征，单独拿出来用于后面的散点图矩阵分析和决策树分裂属性查看，直观一点。这4个维度分别是花萼长度/宽度，花瓣长度/宽度。

2. 数据初步分析与查看

在之前的文章中，我们已经使用过这个数据集了，知道了大体情况。这里就不再使用shape/size/等查看数据集了。我们直接把数据iris['data']和feature_names即4个维度的名称合并成一个DataFrame，在调用pandas的散点图矩阵观察一下数据集

df = pd.DataFrame(iris['data'], columns = iris_feature_names)
df.head()

image.png

pd.plotting.scatter_matrix(df, c =iris['target'], figsize=(20, 20), marker='o', 
                                       hist_kwds={"bins": 20}, s=40, alpha=.8)

画出4个维度的直方图以及两两之间的散点图，这样可以直观的看到数据分类情况，如下：

matrix.png

稍微观察一下我们就可以发现使用petal length区分度最好，从上面图中的第三行我们可以发现有一种花的petal length特别小，和其他两种有很大的距离。另外petal width也有类似的情况（这两个特征在直方图中中间有断开的地方，以这里作为标准可以很容易的裂分出一类）。下面我们就创建决策树算法，看看算法是不是也是这么“想”的。

3. 构建决策树算法模型并查看模型精度

X_train, X_test, y_train, y_test = train_test_split(X, y , test_size = 0.2, random_state = 1024)

clf = DecisionTreeClassifier(criterion= 'entropy') #以entropy熵作为分裂标准构建决策树
clf.fit(X_train, y_train) #训练
y_ = clf.predict(X_test) #预测
tree_score = accuracy_score(y_test, y_) #查看模型预测结果的精度
print('该决策树模型在测试集上的精度为: {:.2f}'.format(tree_score))
>>>该决策树模型在测试集上的精度为: 1.00

之前我们反复的提到过在sklearn中构建算法模型训练预测都是统一的格式，3-4行代码搞定。上面也是用3行代码完成了模型的创建/训练和预测，之后打印出来模型在测试集上精度。因为数据简单，我们获得了100%的精度，这个和之前的KNN差不多。
决策树算法的构建中同样有很多参数可以调，我们下次再细说。这里最后我们输出一下上面算法的裂分条件和标准，这个是决策树比较赞的地方。我们可以直观的看到算法是如何归纳训练数据集的数据特征并选择最佳分裂条件进行裂分，这个就是算法的学习过程。

plt.figure(figsize=(15,8))
_ = tree.plot_tree(clf, filled = True, feature_names=iris_feature_names,fontsize = 11)

结果如下图：

tree_new.png

可以看到和我们之前预想的一致，算法第一步是按照petal length来裂分，直接得到一个叶子。我们在来套用熵的公式手算验证一下图中第一步得到的信息熵 entroy 为 1.584：

p1 = 39/120
p2 = 42/120
p3 = 39/120
H = -(p1 * np.log2(p1) + p2 * np.log2(p2) + p3 * np.log2(p3))
print(H)
>>>1.5840680553754911

结果和算法一致。有了这个树，我们就可以清晰的知道算法是怎么分类的了。这个是决策树比较好的地方，可视化/可解释性强。有些算法我们不知道或者很难理解算法究竟做了什么来预测或者分类的，比如神经网络。
好了今天就到这里了，决策树还有很多调参的内容以及ID3，C4.5等以及随机森林和极限树等内容我们以后在分享！