[机器学习]决策树
决策树
@(技术博客)[机器学习, 决策树, python]
学习决策树首先要搞清楚决策树是什么（what），在弄清楚决策树是什么的过程中，我们也就能够了解决策树这个技术能够干什么；其次我们需要弄清楚决策树是怎样（how）工作的，包括算法的工作原理，训练方法等等；最后我们进一步的研究为什么（why）决策树算法能够从数据中学习到知识的，这是我们弄清楚决策树算法的最终目的，即从最根本的原理上给出清晰的解释。当然了，本着理论与实践相结合的原则，我们也会利用已有的算法库进行一个小实验，一来更直观的理解决策树，二来在具体的例子中回顾前面的what-how-why。
决策树简介
关于决策树的概念，我们直接引用Tom M. Mitchell在Machine Learning一书中的一段描述。
决策树学习是应用最广泛的归纳推理算法之一。它是一种逼近离散数值目标函数的方法，在这种方法中学习到的函数被表示为一棵决策树。学习得到的决策树也能再被表示为多个if-then的规则，以提高可读性。这种学习算法是最流行的归纳推理算法之一，已经成功的应用到从学习医疗诊断到学习评估贷款申请的信用风险的广阔领域。经典的决策树学习方法包括像ID3（Quinlan 1986年）、ASSISTANT和C4.5（Quinlan 1993年）这样广为应用的算法。
在这里要说一句题外话，随着大数据、人工智能技术的兴起，目前这些领域应用神经网络进行深度学习更为流行。但是想想在1986年就有决策树这样的算法诞生，将人从重复、繁琐的工作中释放出来，而且效果还挺不错的，多么令人兴奋。
决策树的表示
下面我们首先来解决第一个问题，也就是what的问题。我们依旧拿Tom大神在Machine Learning一书中的一段叙述以及例子进行学习。
决策树通过把实例从根结点排列（sort）到某个叶子结点来分类实例，叶子结点即为实例所属的分类。树上的每一个结点指定了对实例的某个属性（attribute）的测试，并且该结点的每一个后继分支对应于该属性的一个可能值。分类实例的方法是从这棵树的根结点开始，测试这个结点指定的属性，然后按照给定实例的该属性值对应的树枝向下移动。这个过程再在以新结点为根的子树上重复。
简而言之，决策树首先是一棵树。没错，就是数据结构中所指的树。树中的非叶子节点都是数据在某一维的属性，叶子节点是数据的输出结果。用简单的形式化的语言表示的话，可以令一个数据样本为X=(x_1,x_2,...,x_n)，该数据样本对应的输出为y。那么决策树中非叶子节点则是x_i，叶子节点则是y。
千言万语不如一张图，我们使用书中的一个例子，例子是根据当前的天气的情况（即X），来分类“星期六上午是否适合打网球”（y）。决策树如下图示例所示。
图 1 星期六上午是否适合打网球的决策树
图中的决策树上非叶子节点的Outlook、Humidity、Wind既是上述的x_i，而树干上的值即是属性x_i对应的值，例如Humidity对应的High和Normal。而叶子节点Yes和No既是上述的y。例如，下面的实例：<Outlook=Sunny，Temperature=Hot，Humidity=High，Wind=Strong>将被沿着这棵决策树的最左分支向下排列，因而被评定为反例，即No。
到此我们已经对决策树的概念有了一个基本的了解。
- 决策树是一棵树。
- 决策树是用来对离散数据进行分类的。
- 非叶子节点上是数据的某一项属性，叶子节点是数据的分类结果。
基础的决策树学习算法
在弄清楚what问题后，我们下一步的疑惑便是决策树是怎么生成的，即给了你一组样本数据后，如何从数据中学习出来这一棵神奇的决策树。话不多说，我们开始围绕how这一个主题来继续。
大多数已开发的决策树学习算法是一种核心算法的变体。该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。也就是说决策树的学习问题可以看做是一个搜索问题，是从由数据各个维度的属性张成的空间中，搜索得到一个合适的解的过程。这一核心算法是ID3算法（Quinlan 1986）和后继的C4.5算法（Quinlan 1993）的基础，我们选择这一基本的算法进行讨论学习。
基本的ID3算法通过自顶向下构造决策树来进行学习。那么我们就要问了，该选择哪一个属性作为根节点来进行测试呢？答曰：选择分类能力最好的属性作为根节点。我们又要问了，什么样的属性我们可以说它的分类能力好？这里我们先卖个关子，种个草，回头再来拔草。我们先保持思路继续往前。当我们选择了分类能力最好的属性作为根节点后，那么所有的数据根据该属性可以分成几个分支（分支的个数即属性的取值个数）。在不同分支下的数据，我们又可以按照上面的操作，选择分支下的自数据集里分类能力最好的属性作为“根”节点（即分支里的根节点）。如此迭代，就可以得到一棵决策树。听起来，挺简单的吧。
好了，我们发现算法的核心是如何选取每一个节点要测试的属性，我们希望是选择的属性是有助于分类的，也就是上面所提到的分类能力强。那么啥叫分类能力强呢？这里我们就要定义一个统计数值，称作信息增益（information gain）**，我们用这个属性来衡量属性的分类能力。一看到“信息”这两个字，我们立刻就会联想到熵。没错，就是香农提出的信息熵（你大爷还是你大爷，提出来的东西应用就那么广泛，计算机网络中也有我，机器学习依旧还有我）。关于信息熵更多的知识，大家可以去阅读更多的文章。继续回到主题，信息增益如何定义呢？我们先回顾下信息熵的概念，对于一个随机变量x，令它的概率密度为p(x)，不失一般性的我令x是一个离散变量，那么x的信息熵可表示为H(x)=-\sum_x{p(x)\log_2{p(x)}}
我们把上述的随机变量替换成一个数据集合，就可以得到一个数据集合的信息熵。举个例子，S是一个相对于某个布尔分类的14个样例的集合，包含9个正例和5个反例。那么S相对于这个布尔分类的信息熵为Entropy(S)=-(9/14)\log_2{9/14}-5/14\log_2{5/14}=0.940
已经有了信息熵作为信息的衡量标准，那么我们可以进一步的定义信息增益。
信息增益就是由于使用这个属性分割样本数据集而导致的信息熵的降低。
我们可以这样来理解，使用某个属性分割样本数据集，相当于我们获取了数据中这一个属性的信息。使用这个属性对数据集进行分类，使得我们对于数据集的了解更加清晰，信息熵便会下降。信息熵下降前后的差值既是该属性的信息增益。形式化的表示如下所示，
Gain(S,A)=Entropy(S)-\sum_{v \in Values(A)} \frac{|S_v|}{|S|}Entropy(S_v)
其中Values(A)代表属性A的取值集合，S_v是S中属性A取值为v的集合。所以Gain(S,A)是由于给定了属性A的值而导致的信息熵的减少（熵代表的是系统的混沌状态，给定了信息后，系统的熵值减少，意味着状态更加确定）。换句话来讲，Gain(S,A)是由于给定属性A的值而得到的关于目标函数值的信息。当对S的一个任意成员的目标值编码时，Gain(S,A)的值是在知道属性A的值后可以节省的二进制位数。说到这里大家是不是想起一种编码方式？是的，没错，就是哈夫曼编码（Huffman Coding），在这里就不展开讨论了，依旧还是站在香农的肩膀上。
好了，又到了举例子的时候了。为了演示ID3算法的具体操作，考虑使用下表中的训练数据来进行。
图 2 星期六上午是否适合打网球的数据集
这里，目标属性PlayTennis对于不同的星期六上午具有yes和no两个值，我们将根据其他属性来预测这个目标属性值。首先考虑算法的第一步，选择哪一个属性作为根节点。ID3算法将计算每一个候选属性（Outlook、Temperature、Humidity、Wind）的信息增益，然后选择其中最高的一个。我们可以计算得到
Gain(S,Outlook)=0.246
Gain(S,Humidity)=0.151
Gain(S,Wind)=0.048
Gain(S,Temperature)=0.029
所以Outlook被作为根节点的决策属性，并为它的每一个可能值（也就是Sunny，Overcast和Rain）在根结点下创建分支。部分决策树的结果显示在图1中，同时画出的还有被排列到每个新的后继结点的训练样例。注意到每一个Outlook=Overcast的样例也都是PlayTennis的正例。所以，树的这个结点成为一个叶子结点，它对目标属性的分类是PlayTennis=Yes。相反，对应Outlook=Sunny和Outlook=Rain的后继结点还有非0的熵，所以决策树会在这些结点下进一步展开。
对于非终端的后继结点，再重复前面的过程选择一个新的属性来分割训练样例，这一次仅使用与这个结点关联的训练样例。已经被收编入树的较高结点的属性被排除在外，以便任何给定的属性在树的任意路径上最多仅出现一次。对于每一个新的叶子结点继续这个过程，直到满足以下两个条件中的任一个：
- 所有的属性已经被这条路径包括。
- 与这个结点关联的所有训练样例都具有同样的目标属性值（也就是它们的熵为0）。
决策树学习的归纳偏置
ID3算法从观测到的训练数据泛化以分类未见实例的策略是什么呢？换句话说，它的归纳偏置是什么？这也是就关于why的问题。
如果给定一个训练样例的集合，那么我们能够找到很多决策树来满足这个训练样例集合，为什么ID3算法从千千万万（也许实际上没那么多）棵树中选择了这一棵呢？ID3选择在使用简单到复杂的爬山算法遍历可能的树空间时遇到的第一个可接受的树。概略地讲，ID3的搜索策略为：
- 优先选择较短的树而不是较长的树。
- 选择那些信息增益高的属性离根结点较近的树。
近似的ID3算法归纳偏置：较短的树比较长的优先。那些信息增益高的属性更靠近根结点的树得到优先。
那么为什么优先最短的假设呢？ID3算法中优选较短决策树的归纳偏置，是不是从训练数据中泛化的可靠基础？哲学家们以及其他学者已经对这样的问题争论几个世纪了，而且这个争论至今还未解决。威廉•奥坎姆大约在1320年提出类似的论点 ，是最早讨论这个问题的人之一，所以这个偏置经常被称为“奥坎姆剃刀”（Occam’s razor）。
奥坎姆剃刀：优先选择拟合数据的最简单假设。
这个问题就显得很哲学了。在回归问题里，我们也能找到类似的例子，例如给了一个九个点的样本数据，我们总能找到一个多项式y=\sum_{i=0}^8{w_ix^i}，使得这条曲线完美的穿过这9个点，但是这样一条曲线真的能代表这些数据的实际情况么。例如，数据点是关于房子面积和房价的数据（扎心了吧）。显然这样一条曲线的泛化能力是很差的。所以奥坎姆剃刀法则是对“Simple is best”的诠释。
当然给出一个归纳偏置的名字不等于证明了它。为什么应该优先选择较简单的假设呢？请注意科学家们有时似乎也遵循这个归纳偏置。例如物理学家优先选择行星运动简单的解释，而不用复杂的解释。为什么？一种解释是短假设的数量少于长假设（基于简单的参数组合），所以找到一个短的假设但同时它与训练数据拟合的可能性较小。相反，常常有很多非常复杂的假设拟合当前的训练数据，但却无法正确地泛化到后来的数据。例如考虑决策树假设。500个结点的决策树比5个结点的决策树多得多。如果给定一个20个训练样例的集合，可以预期能够找到很多500个结点的决策树与训练数据一致，而如果一个5结点的决策树可以完美地拟合这些数据则是出乎意外的。所以我们会相信5个结点的树不太可能是统计巧合，因而优先选择这个假设，而不选择500个结点的。
关于why问题的讨论就到这里，其实还有很多的解释以及可以探讨的地方，大家可以阅读更多的材料来解开谜题。
代码示例
在这部分，我们将使用scikit-learn（python语言编写的机器学习包）中的决策树算法库来进行演示。实际动手操作总归会带来对算法不一样的感受。上文中我们只是对最基础的决策树算法ID3进行了理论分析和算法描述，而scikit-learn中包含的决策树算法多种多样。但是核心思想大同小异，更详细的算法细节大家可以阅读大神们的论文、python源码或者文档说明进行了解。
代码如下：
from sklearn.datasets import load_iris
from sklearn import tree
import pydotplus
iris = load_iris()
clf = tree.DecisionTreeClassifier()
clf = clf.fit(iris.data, iris.target)
dot_data = tree.export_graphviz(clf, out_file=None,
feature_names=iris.feature_names,
class_names=iris.target_names,
filled=True, rounded=True,
special_characters=True)
graph = pydotplus.graph_from_dot_data(dot_data)
graph.write_pdf("iris.pdf")
数据集是鸢尾植物数据库花瓣以及萼片的长和宽共四项数据，输出为鸢尾植物的种类setosa、versicolor和virginica三种（更多的信息在代码里debug下，观察iris变量即可）。最后的分类输出如下图。
图 3 鸢尾花植物的分类决策树
我们得到了一棵通过学习算法学习得到的决策树。这里我们可以看到我们没有使用信息熵当做选择根节点的依据，而是选择了gini值，本着学一练二考三的科研训练方法（大学本科某著名教授所提出的，这样的强度确实酸爽），留给大家自己去探索更多的细节。
小结
文章对机器学习中最基础的一种分类算法，决策树，进行了由浅及深的探讨。算是机器学习的入门算法，但是其中包含的学习的思想还是意味深远。接下来会和大家探讨更多的机器学习算法以及目前流行的深度学习算法。
