文 / 阿里淘系 – 白罗

作为最经典的机器学习算法之一，决策树（包括其衍生或以其为最小决策单元的算法，包括随机森林、坡度爬升树、XGBoost等）在神经网络盛行的今天，在监督式学习算法家族中，依旧有着重要的地位。

它是一种基于树形模型提供决策能力的机器学习预测模型，树中的每个节点表示对象，而相应的分叉路径代表其属性值，叶子结点则对应从根节点到该叶子结点所经历的路径表示的对象的值。下文将会在阐述决策树的基本原则与原理的基础上，通过一个经典的例子来展示一个基本的决策树模型是如何运作的。
​

1. 经验风险最小化 (Empirical Risk Minimization)

对于监督式学习任务往往存在以下的训练集和目标：
训练集： S = {(X1, y1), …, (Xn, yn)}
目标：h: X->y的映射，能在实际任务T中有着较好的表现。（h表示hypothesis）
​

对于模型在真实情景下的运行情况，我们不得而知。但是我们通常会在一组被标记过的训练集上验证模型的性能。而经验风险最小化原理，机器学习算法的最终目标是在一类假设 (a set of hypotheses) 中找到一个在数据集上平均损失函数最小的假设（即风险最小的）：
​

**R(h) = E(L(h(x), y)) E表示期望，L表示损失函数 **
​

当然，这一切都是建立在训练集对真实情况有足够的代表性的前提下。众所周知，在训练集往往对真实情况缺乏代表性，结果就是造成模型的过拟合，类似带答案的习题和期末考试之间的差别。

2. 决策树算法原理 (Decision Tree)

决策树是一种有向无环图 (Directed Acyclic Graph)，它的特点是每一个非叶子结点 (non-leaf nodes) 都与一种属性相关联，并且边 (edge) 表示了属性的父节点的值，同时叶子结点 (leaf nodes) 与标签相关联。我们这里可以用一个非常经典的例子来理解决策树算法的基本原理，下面是一个天气状况与决定是否打网球的训练集 (这是一个四维输入一维输出)