一、什么是决策树

我们看下面这个生活中的例子：

一个女生正在面临择偶的判断，最终的决策是：进一步了解（Yes/No），她往往从如下方面进行考虑（年龄、颜值、收入、价值观匹配度）

这很像一棵树对不对，根据属性对数据一步一步进行筛选（划分），从而达到符合条件的值。

决策树

决策树（Decision tree）是基于已知各种情况（特征取值）的基础上，通过构建树型决策结构来进行分析的一种方式，是常用的有监督的分类算法

决策树组成

一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；叶结点对应于决策结果,其他每个结点则对应于一个属性测试；

决策树就是把样本按属性一层层做“是/否”等测试往下分，直到落到某个叶子；根结点装的是全部样本，每条根到叶的路径就是一串判定规则，叶子给出最终预测。

决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。

上面案例是大多数女生通过定性的主观意识，把年龄放最顶层进行划分，那么如果我们想量化这个过程，该如何划分属性呢？

这里我们先引入信息熵、信息增益、信息增益率、基尼系数的概念。

信息熵

信息熵是度量样本集合纯度最常用的一种指标。

假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k(k=1,2...|y|)$

$Ent(D)$ 的值越小， $D$ 纯度越高。

Ent(D)=-\sum_{k=1}^{|y|}p_klog_2p_k

信息增益

信息增益是相对于属性/特征而言的

对于某个属性 $a$ 有 $V$ 个可能的取值 $\{a^1,a^2...a^V\}$ ，按此划分会产生 $V$ 个分支节点，第 $v$ 个分支节点包含了 $D$ 中所有在属性 $a$ 上取值为 $a^v$ 的样本，记作 $D^v$ 。在结合分支节点赋予权重 $\frac{|D^v|}{|D|}$ ，我们给出信息增益公式：

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

一般来说，信息增益越大，意味着划分的更“纯”，ID3决策树算法就是根据划分属性的。

信息增益率

由信息增益公式我们知道，其对可取值数目较多的属性有所偏好，为了减少这种偏好带来的不利影响，引入了增益率来选择最优划分属性。

Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)} \\ IV(a)=-\sum_{v=1}^{V}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}

其中 $IV$ 为属性 $a$ 的固有值，属性数目越多，其值就越大，C4.5决策树算法就是采用此方式，先从候选划分属性中找到信息增益高于平均水平的属性，再从中选择增益率最高的。

基尼系数

CART决策树算法引入了此方式来划分属性，数据集的纯度可用基尼值来度量

Gini(D)=\sum_{k=1}^{|y|}p_k(1-p_k)=1-\sum_{k=1}^{|y|}p_k^2

属性 $a$ 的基尼指数定义为

Gini\_index(D,a)=\sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)

$Gini(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率，其值越小，数据集纯度越高。

我们在候选属性集合 $A$ 中,选择那个使得划分后基尼指数最小的属性作为最优划分属性，即 $a_*=\underset{a\in A}\argmin \operatorname{Gini\_index}(D, a)$

二、一些决策树算法

示例

小明的是否外出活动与天气条件的关系

编号	天气（晴、阴、雨）	温度 (热、中、冷)	湿度 (高、中)	风力 (强、弱)	外出活动 (是、否)
1	晴	热	高	弱	否
2	晴	冷	高	强	否
3	阴	热	高	弱	是
4	雨	冷	高	强	否
5	雨	冷	中	强	否
6	雨	中	高	强	否
7	阴	热	中	弱	是
8	晴	冷	高	弱	否
9	晴	中	中	强	是
10	雨	中	中	弱	是
11	晴	冷	中	强	是
12	阴	冷	中	强	是
13	阴	中	高	弱	是
14	雨	热	高	强	否

ID3算法

是一种基于信息增益的决策树生成算法，核心思想：每一步选择最能“减少不确定性”的属性来划分数据。

以上述例子，我们开始计算：
用以学习小明是否根据天气预测是否决定外出的决策树，以天气属性为例：

$Ent(D^1)=D^1(天气=晴)、Ent(D^2)=D^2(天气=阴)、Ent(D^3)=D^3(天气=雨)$

$Ent(D^1)=-\frac{3}{5} \log _{2} \frac{3}{5}-\frac{2}{5} \log _{2} \frac{2}{5} \approx 0.97095$

$Ent(D^2)=-\frac{4}{4} \log _{2} \frac{4}{4}\approx 0$

$Ent(D^3)=-\frac{1}{5} \log _{2} \frac{1}{5}-\frac{4}{5} \log _{2} \frac{4}{5} \approx 0.72193$

计算信息增益：

\begin{align} \mathrm{Gain}(D,\text{天气}) &= Ent(D) - \sum_{v=1}^{3}\frac{|D^v|}{|D|}Ent(D^v) \\ &= 1 - \left(\frac{5}{14}\cdot0.97095+\frac{4}{14}\cdot0+\frac{5}{14}\cdot0.72193\right) \\ &= 1 - 0.60460 \\ &= 0.39540 \end{align}

依次类推计算有所有属性的增益，找到最优的进行划分。

C4.5算法

在ID3基础上需要多算一下信息增益率：

\begin{align} \mathrm{IV}({天气}) &= - \sum_{v=1}^{3}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}\\ &= - \left(\frac{5}{14}\cdot log_2{\frac{5}{14}}+\frac{4}{14}\cdot log_2{\frac{4}{14}}+\frac{5}{14}\cdot log_2{\frac{5}{14}}\right) \\ &= 1.575 \end{align}

$Gain\_rate(D,天气)=\frac{Gain(D,天气)}{IV(天气)} = \frac{0.3954}{1.575} \approx 0.2510$

依次类推计算所有属性的增益率，我们选择信息增益率最小的进行划分

引入IV来计算增益率的目的

回顾熵的定义：衡量分布的“不确定性”。

若所有样本都集中在某个取值上，如 $P=[1,0,0...]$ 则 $Ent(D)=Ent(D^1)$

于是 $Gain(D,a)=Ent(D)-\sum_{v=1}^1\frac{|D^v|}{|D|}Ent(D^v)=0$

划分前后的数据分布没有变化，增益为0，说明这个属性对分类没有帮助

若每个取值都一样多，如 $P=[\frac{1}{V},\frac{1}{V},\frac{1}{V}...]$ 则 $Ent(D^v)=0$

于是 $Gain(D,a)=Ent(D)-\sum_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)=Ent(D)$

此时划分后的每个分支都是纯的（熵为0），增益达到最大，但是这样模型毫无泛化能力，因为每个分支都意味着模型要去拟合更多局部规律（过拟合）

故我们引入 $IV$

属性的取值越多，样本划分得越细碎、不确定性越大，因此 $IV$ （本质是熵）越大。
C4.5 用它来惩罚那些取值多但没有实质预测价值的属性。

CART算法

CART的思路完全不同。它构建的是二叉树（Binary Tree），每次划分只分成两部分。
它根据任务类型采用不同的纯度指标：

分类任务：使用基尼指数（Gini Index）
回归任务：使用最小平方误差（MSE）

Kyrie

机器学习-决策树