决策树基础

概述

决策树是一种树型结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶结点代表一种类别。
决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。

模型 : 特征树决定的空间划分

策略：不确定信息“度量”最小

算法：以不同的指标选择最优特征进行空间划分，直到满足停止条件

ID3 （信息增益）、C4.5 （信息增益比）、CART （二叉树、分类与回归、Gini指数）

流程：

特征选择：决策树在每个节点上选择最佳特征进行分割，这个特征能够最好地区分数据。
树的增长：通过递归地选择特征并分割数据，直到满足停止条件，如达到最大深度或叶节点中的样本数量小于某个阈值。
剪枝：为了防止过拟合，决策树需要剪枝，即去除一些不必要的分支。

算法

（1） ID3

使用信息增益作为选择特征的标准，它倾向于选择具有最高信息增益的特征进行分割。

1.1 熵

日常生活中，当我们要搞清楚某件事情时，这件事情的不确定性越大，我们需要了解的信息就越多。由此可以看出，一条信息的信息量大小和它的不确定性有直接关系。受此启发，人们就拿不确定性这个量来度量信息量的大小。在信息论或概率统计中，用熵度量随机变量的不确定性。熵值越大，随机变量的不确定性就越大。

定义随机变量X的概率分布为p(x)，从而定义X信息量： $H(X)=-log_{2}P(x)$

对离散型随机事件X的信息量求期望，得熵的定义：

$H(X)=\sum_{i=1}^{n}P_{i}logP_i$

注：经典熵的定义，底数是2，单位是bit；

若底数是e，单位是nat(奈特)。

1.2 信息增益

联合熵：

$H(Y,X)=H(Y|X)+H(X)$

条件熵为：

$H(Y|X)=\sum_{x,y}P(x)H(Y|X=x)$

信息增益概念：当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时，所对应的熵和条件熵分别称为经验熵和经验条件熵。

信息增益表示：得知特征A的信息而使得类X的信息的不确定性减少的程度。

信息增益定义：特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：

$g(D,A)=H(D)-H(D|A)$

选择信息增益最大的特征作为当前的分裂特征（根节点）。

其中，数据集D的经验熵为：

$H(D)=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}log_{2}\frac{|C_k|}{|D|}$

信息增益的缺点：特征的类别越多，其信息增益越大，越容易形成分裂特征，造成决策树宽且浅。

（2）C4.5

使用信息增益比（率）来选择特征，以避免偏向于具有更多值的特征

2.1 信息增益比

用信息增益作为划分训练集特征的标准时，有一个潜在的问题，那就是相比之其会倾向于选择类别取值较多的特征。因此人们提出使用信息增益比(Information Gain Ratio)来对这一问题进行校正。

特征X对训练集的信息增益比定义为特征X的信息增益g(Y,X)与特征X的取值的熵 H(X) 的比值，记为 $g_{r}(D,A)$ ,即

$g_{r}(D,A)=\frac{g(D,A)}{H(A)}$

（3）CART（Classification and Regression Trees）

既可以用于分类也可以用于回归任务。使用Gini系数求解分类问题；使用平方误差最小求解回归问题。

3.1 基尼系数——分类树：目标变量是离散型

基尼系数(Gini) 可以用来度量任何不均匀分布，且介于 0~1 之间的数 (0指完全相等，1指完全不相等)。分类度量时，总体包含的类别越杂乱，基尼系数就越大 (与熵的概念相似)。基尼指数主要用来度量数据集的不纯度。基尼指数越小，表明样本只属于同一类的概率越高，即样本的纯净度越高。

分类问题中，假设有k个类，样本点属于k的概率Pk，则概率分布的基尼指数：

对给定的样本集合D，基尼指数：

Gini系数的图像、熵、分类误差率三者之间的关系如下：

说明:Gini系数越小越好。

3.2 平方误差最小——回归树：目标变量是连续型

对于含有M个样本、每个样本的特征维度为N的训练数据集D，遍历样本的特征变量Fn，n=1,2...M,对每一个特征变量Fn，扫描所有可能的K个样本切分点Sk, k = 1,2, ..., K，样本切分点Sk每次将数据集D划分为D1和D2两个子集.我们的目标是选出划分点Sk，使得D1和D2各自集合的标准差最小，同时D1和D2的标准差之和也最小，写为数学表达式为：