机器学习 | 决策树算法

一、决策树算法概述

1、树模型

决策树：从根节点开始一步步走到叶子节点(决策)。所有的数据最终都会落到叶子节点，既可以做分类也可以做回归。

在分类问题中，表示基于特征对实例进行分类的过程，可以认为是if-then的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

2、树的组成

根节点：第一个选择点

非叶子节点与分支：中间过程

叶子节点：最终的决策结果

3、

决策树通常有三个步骤：特征选择、决策树的生成、决策树的修剪。
决策树学习的目标
- 根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。
决策树学习的本质
- 从训练集中归纳出一组分类规则，或者说是由训练数据集估计条件概率模型。
决策树学习的损失函数：正则化的极大似然函数
决策树学习的测试：最小化损失函数
决策树学习的目标：在损失函数的意义下，选择最优决策树的问题。
训练阶段
- 从给定的训练集构造出来一棵树(从跟节点开始选择特征，如何进行特征切分)。
- 有数据想构建树。
测试阶段
- 根据构造出来的树模型从上到下去走一遍就好了。
- 有数据想得结果。

一旦构造好了决策树，那么分类或者预测任务就很简单了，只需要走一遍就可以了，那么难点就在于如何构造出来一颗树，这就没那么容易了，需要考虑的问题还有很多的!

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

k-近邻算法可以完成很多分类任务，但是其最大的缺点是无法给出数据的内在含义，决策树的优势在于数据形式非常容易理解。

二、熵的作用

1、如何切分特征(选择节点)

问题：根节点的选择该用哪个特征呢?接下来呢?如何切分呢?

想象一下：我们的目标应该是根节点就像一个老大似的能更好的切分数据 (分类的效果更好)，根节点下面的节点自然就是二当家了。

目标：通过一种衡量标准，来计算通过不同特征进行分支选择后的分类情况，找出来最好的那个当成根节点，以此类推。

2、衡量标准-熵

熵是表示随机变量不确定性的度量。

(解释：说白了就是物体内部的混乱程度，比如杂货市场里面什么都有那肯定混乱呀，专卖店里面只卖一个牌子的那就稳定多啦)

熵值公式

举例

A集合[1,1,1,1,1,1,1,1,2,2] B集合[1,2,3,4,5,6,7,8,9,1]

显然A集合的熵值要低，因为A里面只有两种类别，相对稳定一些。而B中类别太多了，熵值就会大很多。

三、信息增益原理

1、熵值

不确定性越大，得到的熵值也就越大。

当p=0或p=1时，H(p)=0,随机变量完全没有不确定性。

当p=0.5时，H(p)=1,此时随机变量的不确定性最大。

2、信息增益

特征X使得类Y的不确定性减少的程度。 (分类后的专一性，希望分类后的结果是同类在一起)

划分数据集的大原则是：将无序数据变得更加有序，但是各种方法都有各自的优缺点，信息论是量化处理信息的分支科学，在划分数据集前后信息发生的变化称为信息增益，获得信息增益最高的特征就是最好的选择，所以必须先学习如何计算信息增益，集合信息的度量方式称为香农熵，或者简称熵。

四、决策树构造及实例

决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。

1）开始：构建根节点，将所有训练数据都放在根节点，选择一个最优特征，按着这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。
2）如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点去。
3）如果还有子集不能够被正确的分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点，如果递归进行，直至所有训练数据子集被基本正确的分类，或者没有合适的特征为止。
4）每个子集都被分到叶节点上，即都有了明确的类，这样就生成了一颗决策树。

决策树的特点：

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过度匹配的问题
适用数据类型：数值型和标称型

过程：

首先，确定当前数据集上的决定性特征，为了得到该决定性特征，必须评估每个特征，完成测试之后，原始数据集就被划分为几个数据子集，这些数据子集会分布在第一个决策点的所有分支上，如果某个分支下的数据属于同一类型，则当前无序阅读的垃圾邮件已经正确的划分数据分类，无需进一步对数据集进行分割，如果不属于同一类，则要重复划分数据子集，直到所有相同类型的数据均在一个数据子集内。

创建分支的伪代码 createBranch() 如下图所示：

检测数据集中每个子项是否属于同一类：

If so return 类标签：
Else
     寻找划分数据集的最好特征
     划分数据集
     创建分支节点
         for 每个划分的子集
             调用函数createBranch()并增加返回结果到分支节点中
         return 分支节点