从西瓜书和统计学习方法中学习了决策树的相关知识，同时在网上查找了树的知识点，最重要的是 二叉树和树3种的遍历方式

• 树的知识
• 决策树
• 剪枝问题

树

树一种抽象类型数据，用来模拟具有树状结构性质的数据集合。它是由多个有限节点组成一个层次关系的集合。特点：

• 每个节点有0个或者多个子节点
• 没有父节点的节点称之为根节点
• 每个非根节点有且只有一个根节点

术语

• 节点的度：一个节点含有的 子树的个数 称为该节点的度
• 树的度： 最大的节点的度 称之为数的度
• 叶节点或终端节点： 度为零 的节点
• 父节点：含有子节点的节点上级
• 子节点：一个节点还有的子树的根节点称为该节点的子节点
• 兄弟节点：具有相同父节点的节点
• 节点的层次：根节点为第一层，其子节点为第二层，类推
• 树的高度或者深度：节点最大层次
• 堂兄弟节点：父节点在同一层次的节点
• 森林：由多个树互不相交的树的集合称为 森林

二叉树

每个节点最多只有两个子节点：左子树和右子树，性质：

• 第 i 层上最多 2^{(i-1)} 个节点
• 深度为 k 的二叉数最多有 2^k-1 个节点
• 具有 n 个节点的完全二叉树的深度必为 log2(n+1)
• 叶结点数为 N_0 ，深度为2的节点总数为 N_2 ，则 N_0=N_2+1

树的遍历

深度遍历的三种遍历顺序：

在子节点中，必须先左后右

• 前序遍历：根—>左—>右
• 中序遍历：左—>根—>右
• 后序遍历：左—>右—>根

树的种类

• 无序树：任意节点的子节点之间没有任何的顺序关系，称之为无序树，也叫自由树
• 有序树：子节点之间由顺序关系
• 二叉树：每个节点最多含有两个子树的树
• 完全二叉树：若一棵树的深度为d，除去第d层外，其他各层的节点数目达到了最大值，且第d层所有节点从左向右连续紧密的排列的二叉树
• 满二叉树：所有层的节点数达到了最大数
• 平衡二叉树：当且仅当任何节点之间的 两颗子树的高度差不大于1 的二叉树
• 排序二叉树：二叉搜索树，二叉查找树，性质：任何节点左边的数比节点上的数小，右边比节点上的数大
• 霍夫曼树：用于信息编码
• B 树/ B^+ 树：在 MySQL 的索引中使用

决策树

决策树介绍

决策树是基于树结构进行决策的，其目的是产生一颗泛化能力强，即处理未见示例能力强的决策树，它是一种有监督分类模型

一颗决策树包含：

1. 一个根节点
2. 若干个内部节点
3. 若干个叶节点； 叶节点对应于决策结果

决策树学习

决策树学习的本质上是从训练数据集上归纳出一组分类规则，通过训练数据集估计条件概率模型。

决策树学习的 损失函数 通常是 正则化的极大似然函数 。

决策树基本算法

• 决策树的生成是一个递归过程
• 重点是第8行：最优属性的选择；分支节点所包含的样本尽可能的是属于一个类别，节点的“纯度”要高

---

ID.3

信息增益

ID.3算法是基于 信息增益 来选择最优划分属性。信息增益的计算基于 信息熵 information entropy（样本集合纯度的指标） 。

的信息熵定义为：

Ent(D)=-\sum^K_{k=1} p_klog_2{p_k}

比如：某个事件发生的结果有3种情形，出现的概率分别是：

信息熵的计算如下：

Ent=-(\frac{1}{3}log_2\frac{1}{3}+\frac{1}{2}log_2\frac{1}{2}+\frac{1}{6}log_2\frac{1}{6})

---

信息熵越小，数据集 X 的纯度越大

假设数据集中离散属性 a 共有 V 个可能的取值 {a1,…,aV} 。使用属性 a 对整个数据集进行划分，会产生V个分支节点；

第 v 个节点包含数据集合 D 在属性 a 上取值为 av 的样本，记为 Dv ；节点的权重为 \frac{|D^v|}{|D|} ，样本数越多的分支节点，其影响越大

对数据集的信息增益表示为

Gain(D,a)=Ent(D)-\sumV_{v=1}\frac{|Dv|}{|D|}Ent(D^v)

上面的式子：表示的是以属性

具体过程

1. 从根节点开始，对所有节点计算所有可能的特征的信息增益
2. 选择信息增益最大的特征作为节点的特征，由特征的不同取值建立子结点
3. 再对子结点调用上述方法，递归地创建决策树（步骤2中使用的属性特征不再重复使用）

缺点

ID3算法的缺点是：偏向于 取值较多的属性 进行分割

---

C4.5

介绍

为了解决 ID3 算法的缺点，引入了 C4.5

C4.5使用的是信息增益率作为划分属性的准则，定义为：

GainRatio(D,a)=\frac{Gain(D,a)}{IV(a)}

其中

IV(a)=-\sumV_{v=1}\frac{|Dv|}{|D|}log_2\frac{|D^v|}{|D|}

上式中的

C4.5选择属性的依据

1. 不是选择增益率最大的，可能对数目较少的属性有所偏好
2. 从候选属性中找出信息增益率高于平均水平的属性
3. 步骤2的基础上，选择增益率最高的
4. 使用过后的属性在下次进行划分的时候，不再考虑
5. 如果在某次划分的过程中，有多个属性的信息增益是相同的，任取其中一个。
6. 对于连续值属性，可取值数目不再有限，采用离散化技术（如二分法）进行处理。
   1. 将属性值从小到大排序，然后选择中间值作为分割点
   2. 数值比它小的点被划分到左子树，数值不小于它的点被分到右子树，计算分割的信息增益率，选择信息增益率最大的属性值进行分割。

---

CART

基尼系数Gini

CART 决策树采用的 Gini 基尼系数来划分属性。采用的是二元切分法，每次将数据分成两份，分别进入左右两边的子树中。在整个树中

• 每个非叶子节点都有两个孩子
• CART中叶子节点比非叶子节点多1
• 选取基尼系数作为划分标准，每次迭代都会降低基尼系数。

\begin{align} Gini(D) & =\sum{|Y|}_{k=1}\sum_{k \neq k}p_kp_{k^} \ & = 1-\sum{|Y|}_{k=1}p_k2 \end{align}

Gini系数特点

1. 反应从数据集中随机抽取两个样本，类别标志不一样的概率
2. 基尼系数越小越好，数据的纯度越高
3. 选择使得划分后 基尼系数最小 的属性作为最优划分属性

---

实例demo

在 demo 中主要是讲解 如何计算 信息熵，信息增益，信息增益率，基尼系数。数据样本取自西瓜书

信息熵

1. 在整个样本中的正反例为8：9，信息熵为：

Ent(D)=-(\frac{8}{17}log_2 \frac{8}{17}+\frac{9}{17}log_2 \frac{9}{17})=0.998

1. 选择以属性“色泽seze”为例，有青绿、乌黑、浅白3种取值方案 D_1,D_2,D_3 ，分别占比为6：6：5，每个子集数据中占比为（3：3）：（4：2）：（1：4），那么3个子节点的信息熵分别为：

Ent(D_1)=-(\frac{3}{6}log_2\frac{3}{6}+\frac{3}{6}log_2\frac{3}{6})=1.000

Ent(D_2)=-(\frac{4}{6}log_2\frac{4}{6}+\frac{2}{6}log_2\frac{2}{6})=0.918

Ent(D_1)=-(\frac{1}{5}log_2\frac{1}{5}+\frac{4}{5}log_2\frac{4}{5})=0.722

信息增益

根据上面的计算，得到 基于色泽 属性的信息增益为 \begin{align} Gain(D,seze)