02 决策树 - 初识与构建

在讲决策树之前补充了一些基本概念：比特化、信息熵、条件熵，重点理解熵的概念。本章开始正式进入机器学习模型-决策树。
01 决策树 - 数学理论概述

决策树 Decision Tree： 在已知各种情况发生概率的基础上，通过构建决策树来进行分析的一种方式，是一种运用概率分析的图解法。

决策树是一个预测模型，代表对象属性和对象值的映射关系；每个叶子节点都代表一种类别；

决策树分为：决策树可用于有监督的分类和回归算法，回归用于预测连续值，常用算法：ID3、C4.5、CART等。

一、决策树构建过程

决策树算法的重点是决策树的构造，构造过程是进行属性选择度量，确定各个特征属性之间的树形关系。

构建决策树步骤是分裂属性，分裂属性是指在某个节点按照某一类特征属性的不同划分，构建不同的分支。目的在于：让各个分裂子集尽可能。即让一个分裂子类中，待分类的项尽可能的属于同一类别。

比如：根据一个人有没有喉结来判断是男是女。
通过“是否有喉结”这一属性分类出的两个子类：“男”，“女” 。这是一个比较的分类。原来人的分类是男是女不确定性很高，但根据上述分类之后，男和女的分类相当清晰，此时该系统的不稳定性会比较低。

但是：如果根据一个人 “是否带眼镜” 来判断是男是女，显然分类的结果不如根据 “是否有喉结” 进行分类效果好。

此时理解：构造过程是进行属性选择度量，确定各个特征属性之间的树形关系。 这句话的含义是不是就清晰多了。

二、构建步骤如下

1、将所有特征看成一个一个的节点。
2、遍历每个特征的每一种分割方式，找到最好的分割点；将数据划分为不同的子节点，N1、N2、...、Nm，计算划分之后所有子节点的信息。
3、对于第2步产生的分割，选择出最优的特征以及最优的划分方式；得出最终的子节点：N1、N2、...、Nm；
4、对于子节点N1、N2、...、Nm分别继续执行2~3步，直到每个最终子节点都足够。

思考决策树和KD树的区别：
01 KNN算法 - 概述
02 KNN算法 - KD Tree
KD树是一个二叉树，而决策树每一层的叶子节点可以有多个。

---

步骤分析：现在有若干特征x1、x2、... 、xn

假设1：特征x为是否有喉结。
那么对于特征值的划分必然是(0-有,1-没有)，特征划分方式只有一种。二叉树。

假设2：特征x有三种取值：(0,1,2) 那么分类方式有几种？
第1种：(0,1,2)；三个叶子节点。
第2种：属于0类，不属于0类；二叉树。
第3种：属于1类，不属于1类；二叉树。
第4种：属于2类，不属于2类；二叉树。
在这4中分类方式中，我们可以找到一个对系统稳定性最佳的分类方式。

然后对于若干特征x1、x2、... 、xn，我们需要遍历出每一种特征所有的分类方式，并找到一个对系统稳定性最佳的分类方式。

再针对上一步已选出的特征x1、x2、... 、xn中的最佳的分类方式，我们再从这n个分类方式中再找到一个最佳的分类方式，做为决策树第一次分裂。这次的分裂是所有选择中最的分割方式，是整个系统中的最优分割方式。

得到第一个最的分割方式即生成了第1组子节点，我们还可以继续往下划分，以此类推。

注意：
1、一切划分的标准都是基于目标值Y的，一个理想的算法结果是：每一次分割后的子节点，都更够更好得体现目标值。

2、如果一次分裂将子节点分割得太细，如动物分类，我们不是分割到狗就结束，而是一次细分到狗的每一个品种(金毛、泰迪)。分得太细可能会引起过拟合的问题。

3、针对连续值的划分：确定一个值s作为分裂点，将大于s的值作为一条分支，小于等于s的值作为另一条分支。

三、决策树分割属性的选择

决策树算法是一种 “贪心算法” ，我们只可能考虑到每一次分裂的最优分割情况，但是无法找出全局的最优划分情况。

对于整体数据而言，按照所拥有特征属性进行划分操作，对所有划分操作的结果集进行比较，选择越高的属性作为当前需要分割的数据集进行分割操作。持续迭代，直到得到最终结果。

决策树是通过来选择分割特征属性点的。

PS：在本文中，唯一没有深入解释的术语是，文章中统一使用红色标注。是非常重要的一个知识点，会在下一章深入描述。本章中，请先充分认识到在决策树中的作用和意义。

03 决策树 - 量化纯度、信息增益度、停止条件、评估