机器学习笔记之决策树

决策树 概述

决策树（Decision Tree）算法是一种基本的分类与回归方法，是最经常使用的数据挖掘算法之一。

决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是 if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

决策树学习通常包括 3 个步骤：特征选择、决策树的生成和决策树的修剪。

决策树的定义：

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性(features)，叶结点表示一个类(labels)。

决策树算法的本质就是树形结构，主要有以下几个概念

节点	说明
根节点	没有进边，有出边
中间节点	既有进边也有出边，但进边有且仅有一条，出边也可以有很多条
叶节点	只有进边，没有出边，进边有且仅有一条。每个叶节点都是一个类别标签
父节点和子节点	在两个相连的节点中，更靠近根节点的是父节点，另一个则是子节点。两者是相对的。

用决策树对需要测试的实例进行分类：从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分配到叶结点的类中。

决策树原理

决策树须知概念

特征选择

特征选择就是决定用哪个特征来划分特征空间，其目的在于选取对训练数据具有分类能力的特征。这样可以提高决
策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大的差别，则称这个特征是没有分类
能力的，经验上扔掉这些特征对决策树学习的精度影响不会很大。

那如何来选择最优的特征来划分呢？一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本
尽可能属于同一类别，也就是节点的纯度（purity）越来越高。

度量不纯度的指标有很多种，比如：熵、增益率、基尼值数。

信息熵 & 信息增益

熵（entropy）： 熵指的是体系的混乱的程度，在不同的学科中也有引申出的更为具体的定义，是各领域十分重要的参量。

信息论（information theory）中的熵（香农熵）： 是一种信息的度量方式，表示信息的混乱程度，也就是说：信息越有序，信息熵越低。例如：火柴有序放在火柴盒里，熵值很低，相反，熵值很高。

香农熵及计算函数
熵定义为信息的期望值。在信息论与概率统计中，熵是表示随机变量不确定性的度量。
假定当前样本集合D中一共有n类样本，第i类样本为$x_1$ ，那么的信息$x_1$定义为：
$$l(x_i)=-log_2(x_i)$$
其中 $p(x_i)$是选择该分类的概率。

通过上式，我们可以得到所有类别的信息。为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值(数学期望)，通过下面的公式得到：
$$Ent(D)=-\sum_{k=1}^n p(x_i)log_2(x_i)$$

$Ent(D)$的值越小，则D的不纯度就越低

信息增益（information gain）： 在划分数据集前后信息发生的变化称为信息增益。
信息增益（Information Gain）的计算公式其实就是父节点的信息熵与其下所有子节点总信息熵之差。但这里要注
意的是，此时计算子节点的总信息熵不能简单求和，而要求在求和汇总之前进行修正。

决策树工作原理

如何构造一个决策树?
我们使用 createBranch() 方法，如下所示：

def createBranch():
'''
此处运用了迭代的思想。 感兴趣可以搜索 迭代 recursion， 甚至是 dynamic programing。
'''
    检测数据集中的所有数据的分类标签是否相同:
        If so return 类标签
        Else:
            寻找划分数据集的最好特征（划分之后信息熵最小，也就是信息增益最大的特征）
            划分数据集
            创建分支节点
                for 每个划分的子集
                    调用函数 createBranch （创建分支的函数）并增加返回结果到分支节点中
            return 分支节点

决策树 算法特点

优点：计算复杂度不高，输出结果易于理解，数据有缺失也能跑，可以处理不相关特征。
缺点：容易过拟合。
适用数据类型：数值型和标称型。

参考

apacheCN

打赏