机器学习实战笔记 – 决策树(Decision Tree)

Intro

决策树的核心算法有多种实现,如在机器学习技法介绍的C&RT,以及未涉及的C4.5,以及本书中介绍的ID3。

对于ID3,我们首先定义某个符号或者分类\(x_i\)的信息如下:

$$l(x_i) = -\log_{2}{p(x_i)}$$

其中,\(p(x_i)\)为某符号或者分类在训练集\(D_{train}\)中在所有的符号或者分类中出现的频率,接着我们定义信息熵\(H\):

$$H = – \sum^{n}_{i=1} p(x_i) \log_{2}{p(x_i)}$$

可以看出,信息熵\(H\)其实是求所有符号或分类的期望。

在本节中,决策树的构建算法将选择一个特征及其取值对训练集进行分割,使用该特征及其取值分割训练集可以使得分割后的\(n\)子训练集集信息熵相对于原信息熵增益最大,然后再递归地对子训练集使用该算法,直到训练集特征归一,即无法继续分割。

决策树算法具有如下特点:

优点:计算复杂度低、图形化表示后具有树形结构易于理解、对数据缺失不敏感。

缺点:如果没有Regularization,会出现Overfitting。

适用数据类型:数值型、标称型。

Algorithm

  1. 数据预处理,本算法只支持标称型数据,需要将所有的数值型数据转化为标称型;
  2. 构建决策树根节点,计算原始信息熵,初次选择最佳分割特征,存储最佳分割特征索引;
  3. 根据最佳分割特征及其取值分割训练集,得到的子训练集将原最佳特征列移除;
  4. 对于每一个得到的子训练集重复步骤2到步骤4,直到没有特征可以分割;
  5. 返回决策树;

Code

由于函数与变量名严格按照Objective-C风格命名,表意清晰,故将注释略去。

def create_decision_tree(data_set, tags):

    labels = [vector[-1] for vector in data_set]

    if labels.count(labels[0]) == len(labels):
        return labels[0]

    if len(data_set[0]) == 1:
        return classify(labels)

    best_split_feature_index = get_index_of_best_split_feature(data_set)

    best_split_feature_tag = tags[best_split_feature_index]

    decision_tree = {best_split_feature_tag: {}}

    del(tags[best_split_feature_index])

    best_split_features = [vector[best_split_feature_index] for vector in data_set]

    best_split_features_set = set(best_split_features)

    for best_split_feature in best_split_features_set:

        sub_tags = tags[:]

        sub_data_set = split_data_set(data_set, best_split_feature_index, best_split_feature)

        sub_decision_tree = create_decision_tree(sub_data_set, sub_tags)

        decision_tree[best_split_feature_tag][best_split_feature] = sub_decision_tree

    return decision_tree

Summary

以上是对决策树算法在机器学习实战中的总结,在下一节我们将介绍朴素贝叶斯。

机器学习技法笔记 – Decision Tree(决策树)

Decision Tree Hypothesis

在上一章中,我们介绍了通过Re-weighted思想来差异化\(u^{(t)}_n\)(权重)训练出不同的\(g_t(x)\)然后做Aggregation的AdaBoost。

AdaBoost本质上是一种non-uniform的Bagging Aggregation方法。

在本章中,我们将介绍一种conditional的Bagging Aggregation方法,称之为Decision Tree(决策树)

首先,我们从下图在视觉上初步认识一下决策树:

上图是一个形象化的例子,通过树形图的方式描述了“要不要上课”这一条件决策流程。

其公式化的描述如下:

需要注意的是这是一种递归的描述,其中,\(G(x)\)是一颗生成树,是整颗决策树的入口,\(b(x)\)是判断是否要进入当前分支\(c\)的Branching Criteria Function,\(G_c(x)\)是子树的入口。

接下来,将介绍生成决策树的算法。

Decision Tree Algorithm

生成决策树具有很多著名的算法,在本文中我们介绍C&RT(Classification and Regression Tree),这个算法的主要思路如下:

即对于决策树函数,对于输入的数据集\(D\),如果递归至叶子节点,则输出叶子节点的\(g_t(x)\)对于数据集\(D\)中\((x_n, y_n)\)的值,否则,在当前数据集\(D\)上训练\(b(x)\),然后在将数据集\(D\)一分为二,递归调用决策树函数。

在C&RT中,如何训练\(b(x)\)是非常重要的话题。

其中,\(b(x)\)具有以下形式:

对于每一个\(b(x)\),最小化\(\sum^{2}_{c=1} \vert h(D_c) \vert · impurity(h(D_c))\),可以看出\(c=2\),即\(b(x)\)的输入是被分为两份的数据集\(D\),表现在数据结构上,即是二叉树,而\(impurity(h(D_c))\)是不纯度。

通常,对于回归问题,其\(impurity(h(D_c))\)通常有以下定义:

而对于分类问题,\(impurity(h(D_c))\)则有以下定义:

对于基础的Base Hypothesis,我们依然选择Decision Stump(决策桩),它具有以下形式:

通过最小化\(impurity(h(D_c))\),可以求出最佳的\(\theta\),接下来我们将给出完整的C&RT算法。

Decision Tree Heuristics in C&RT

一个完整的C&RT算法如下:

当\(impurity(h(D_c))=0\),或者\(D_c\)不可再分,则C&RT算法结束。

需要注意的是,C&RT算法生成的决策树如果没有任何的Regularization操作,放任子树生长,会使得\(E_{in}=0\),即会带来Overfitting,所以我们需要为C&RT算法加上Regularization项来避免Overfitting的发生,这个过程也称之为剪枝。

通常可以通过对叶子节点剪枝来做Regularization:

而Regularization项具有以下形式:

具体过程如下:

  • 首先通过C&RT生成决策树
  • 随机剪枝一个或多个叶子节点,重复多次,得到\(N\)个\(G(x)\)
  • 对所有\(G(x)\)在数据集\(D\)做Validation,选取\(E_{in}\)最小的\(G(x)\)

决策树不仅可以用在Numerical Features中,也可以用于Categorical Features:

对于数据集中不分数据的缺失,也可以通过训练多个\(b_n(x)\),来做最佳\(b(x)\)的近似。

Decision Tree in Action

下图是一个C&RT与AdaBoost算法的对比,通常情况下C&RT具有更高的效率:

最后对C&RT做一个总结:

C&RT具有诸多优点,例如对于人类易于解释,易于处理多分类问题,对于有缺失的数据集也可以应对,易于处理非线性分类或者预测问题。

以上是对Decision Tree在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Random Forest。