西瓜书4-决策树

从西瓜书和统计学习方法中学习了决策树的相关知识，同时在网上查找了树的知识点，最重要的是二叉树和树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的索引中使用

决策树

决策树介绍

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

一颗决策树包含：

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

决策树学习

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

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

决策树基本算法

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

ID.3

信息增益

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

的信息熵定义为：

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

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

结果1	结果2	结果3
$frac{1}{3}$	$frac{1}{2}$	$frac{1}{6}$

信息熵的计算如下：

Ent=-(frac{1}{3}log_2frac{1}{3} frac{1}{2}log_2frac{1}{2} frac{1}{6}log_2frac{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)

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

具体过程

从根节点开始，对所有节点计算所有可能的特征的信息增益
选择信息增益最大的特征作为节点的特征，由特征的不同取值建立子结点
再对子结点调用上述方法，递归地创建决策树（步骤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_2frac{|D^v|}{|D|}

上式中的

C4.5选择属性的依据

不是选择增益率最大的，可能对数目较少的属性有所偏好
从候选属性中找出信息增益率高于平均水平的属性
步骤2的基础上，选择增益率最高的
使用过后的属性在下次进行划分的时候，不再考虑
如果在某次划分的过程中，有多个属性的信息增益是相同的，任取其中一个。
对于连续值属性，可取值数目不再有限，采用离散化技术（如二分法）进行处理。
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系数特点

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

实例demo

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

信息熵

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

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

选择以属性“色泽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_2frac{3}{6} frac{3}{6}log_2frac{3}{6})=1.000

Ent(D_2)=-(frac{4}{6}log_2frac{4}{6} frac{2}{6}log_2frac{2}{6})=0.918

Ent(D_1)=-(frac{1}{5}log_2frac{1}{5} frac{4}{5}log_2frac{4}{5})=0.722

信息增益

根据上面的计算，得到基于色泽属性的信息增益为 $$ begin{align} Gain(D,seze) & =Ent(D)-Ent(D)-sum3_{v=1}frac{|Dv|}{|D|}Ent(D^v) & = 0.998-frac{6}{17}*1.00 frac{6}{17}*0.918 frac{5}{17}*0.722 & = 0.109 end{align} $$ 同理，可以得到基于其他属性的信息增益，不再累述。

信息增益率

还是以上面的色泽属性为例，基于色泽属性的信息增益已经计算出来：

Gain(D,seze)=0.109

属性色泽中有3种结果，对应比例为6：6：5，固有值IV(a)为

end{align}

那么，基于属性色泽的基尼系数为

Gain_ratio=frac{0.109}{1.580}

几种常见算法比较

决策树算法	算法描述
ID3	在各级节点上，使用信息增益作为属性的选择标准只适用于离散的描述属性依赖于选择特征数目较多的属性特征单变量决策树，特征之间的关系不会考虑
C4.5	使用的是信息增益率作为属性的选择标准可以同时处理离散和连续的属性描述
CART	使用的是基尼系数作为属性的选择标准非参数的分类和回归算法构建的一定是二叉树终节点是连续变量，属于回归树终节点是离散变量，属于分类树