modeling

先简单地举一个例子，看看什么是决策树。以下是一棵分类树，决定下班后是否要观看机器学习公开课。

我们可以看到从根节点开始往下会有分支，最终会走向叶子节点，得到分类结果。每一个非叶子节点都是一个特征，上图中共有三维特征。决策树是所有机器算法中与人脑处理问题方式最接近的算法，所以很好理解。一棵决策树可以被抽象成以下数学公式：

T是路径总数/叶子节点总数（上图中有6个叶子节点），g_t(x)是base hypothesis，上图中是常量Y/N，q_t(x)可以理解成g_t(x)的权重，取值为1或0：

is x on path t ? 1 : 0;

我们也可以用递归的视角来看决策树：

G_c(x)是当前节点的子树：

tree = (root, sub-trees)

构建一棵决策树

按照以下伪代码我们可以递归式地构建一棵决策树：

function DecisionTree(data D = {(x[0], y[0]), ... , (x[N], y[N])}):
    if (termination criteria met):
        return base hypothesis g_t(x);
    else:
        learn branching criteria b(x)   //b(x)决定如何将数据分支
        split D to C parts D_c = {(x[n], y[n]) : b(x) = c}  //按照b(x)分支
        build sub-tree: G_c = DecisionTree(D_c)   //构建子树
        return G(x) = sum([b(x)==c] * G_c(x)) //返回父树

在上面的伪代码中，尚有四个问题没有解决：

1. number of branches C （分支数目）

2. base hypothesis （g_t(x) )

3. branching criteria b(x) （如何分支）

4. termination criteria （终止条件）

classification and regression tree (C&RT)

第一个问题分支数目C：一般来说C=2，构建一棵二叉树，这是个简单的选择。

第二个问题base hypothesis：对于分类或回归两种情况，我们可以简单的采取投票或取平均值(vote / average)的形式。

第三个问题如何分支：这是决策树的关键点，如何选取最有效的特征划分数据集。下面从两个角度聊聊分支。

信息熵

在第一个问题已经解决的情况下，简单地说就是要将数据集划分为两部分，划分数据集的大原则是：将无序的数据变得更加有序。我们可以使用多种方法划分数据集，但是每种方法都有各自的优缺点。组织杂乱无章数据的一种方法就是使用信息论度量信息，信息论是量化处理信息的分支科学。我们可以在划分数据之前和之后使用信息论量化度量信息的内容。

在划分数据集之前之后信息发生的变化称为信息增益(information gain)，获得信息增益最高的特征就是最好的选择。集合信息的的度量方式成为香农熵(entropy)。熵定义为信息的期望值，在明晰这个概念之前，我们必须知道信息的定义。如果待分类的事物可能划分在多个类别之中，则符号x[i]的信息定义为：

其中p(x[i])是选择该分类的概率。

为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通关过下面的公式得到：

数据越有序，熵越小；相反熵越大。得到熵之后，我们就可以按照获取最大信息增益的方法划分数据集。

Purifying

通俗的讲，分支就是要使分开后的数据集纯度(purity)比较高：

|Dc with h|指划分后的数据集的权重，所以$b(x)$就是要使划分后数据集的权重不纯度最小。

对于回归和分类的情况，我们可以分别用regression error和classification error来计算不纯度：

对于分类的情况，我们还有更多的选择，比如说gini index：

第四个问题termination criteria，当以下任一条件满足时，就可以终止了：

1. 所有的y[n]都相同：impurity = 0，即g_t(x) = y[n]

2. 所有的x[n]都相同：no decision stumps

当这四个问题解决之后，C&RT决策树算法就出来了：

剪枝 （Regularization by Pruning）

一棵完全树极易过拟合，因此我们需要一个正则项来防止过拟合：

Ω(G) = NumberOfLeaves(G)

我们通过限制叶子节点数目来对决策树进行剪枝。所以最终的cost function是这样的：

但是显然我们不能枚举出所有可能的G，那样计算量会非常大，通常是这样做的：

1. G(0) = fully-grown tree

2. G(i) = argmin E_in(G) such that G is one-leaf removed from G(i-1)

举个例子，假设现在有一棵有10个叶子节点的树，去掉一个叶子节点，得到10棵有9个叶子节点的树，在这10棵树中，选一棵E_in(G)（training error）最小的树，在这棵树的基础上继续去掉叶子节点，直到满足条件为止。

处理缺失数据

在训练的时候，决策树会保存一些分支的替代分支，替代分支的划分效果会尽可能的接近原来的分支效果。这样，在测试阶段如果我们遇到用来分支的特征正好是缺失数据，就可以用替代分支来代替原来的分支，巧妙地避开了缺失数据且对结果的影响最小。这也是决策树的一大优点：轻松处理缺失数据。