决策在kaggle上的利器(一)

01-目录大纲

决策树

决策树的直观理解
分类树
回归树

02-决策树的直观理解

决策在kaggle上的利器(一)

02 分类树-信息熵

2-1 信息熵

信息熵是用来衡量信息不确定性的指标，不确定性是一个事出现不同结果的可能性。计算方法如下所示
$H(x)=-\sum_{i=1}^nP(X=i)\log_2P(X=i)$
其中： $P (X=i）$ 为随机变量ⅹ取值为 i 的概率

硬币	P
正面	0.5
反面	0.5

$Entropy=-0.5*\log 0.5-0.5*\log 0.5=1$

硬币	P
正面	0.99
反面	0.01

$Entropy=-0.99*\log 0.99-0.01*\log 0.01=0.08$

条件熵：在给定随机变量 Y 的条件下，随机变量 X 的不确定性

$H(X|Y=v)=-\sum_{i=1}^nP(X=i|Y=v)\log_2P(X=i|Y=v)$
信息增益：熵-条件熵，代表了在一个条件下，信息不确定性减少的程度

$I(X,Y)=H(X-H(X|Y)$

2-2 计算信息增益（举例）

父节点熵 $-(\frac{14}{30}\log \frac{14}{30})-(\frac{16}{30}\log \frac{16}{30})=0.996$

子节点熵 $-(\frac{13}{17}\log \frac{13}{17})-(\frac{4}{17}\log \frac{4}{17})=0.787$

子节点熵 $-(\frac{1}{13}\log \frac{1}{13})-(\frac{12}{13}\log \frac{12}{13})=0.391$

条件熵:子节点加权熵 $(\frac{17}{30}·0.787)+(\frac{13}{30}·0.391)=0.615$

信息增益=父节点熵-子节点加权熵=0.996-0.615

假设高尔夫球场拥有不同天气下某个客户的打高尔夫球的历史记录，如下图所示

决策在kaggle上的利器(一)

我们无法单纯的通过 Yes 和 No 的历史频率判断用户明天会不会打高尔夫因此我们需要借助天气信息减少不确定性

首先是构建根节点，我们先看下 Play Golfl 的熵

Play Golf	Frequency	P	Entropy
No	5	0.36	-0.531
Yes	9	0.64	-0.410
	14		0.940

$H(X)=-\sum_{i=1}^nP(X=i)\log_2P(X=i)$

在 14 条历史数据中，打球的概率为 0.64, 不打球的概率为 0.36, 熵值为 0.94。接下来我们寻找晴朗与否，湿度，风力和温度四种状况与是否打高尔夫相关性最高的一个，进行决策树的构建。

晴朗程度 Outlook 的条件熵与信息增益

Outlook	Yes	No	Frequency	P
Rainy	2	3	5	0.36
Overcast	4	0	4	0.29
Sunny	3	2	5	0.36
			14	1

构建熵如下

Outlook	Yes	No	Entropy
E(Rainy)	0.40	0.60	0.971
E(Overcast)	1.00	0.00	0.000
E(Cool)	0.60	0.40	0.971

使用 Outlook 的条件熵 $0.36*0.971+0.29*0+0.36*0.971=0.69$ 信息增益： $0.940-0.69=0.25$ （最佳分隔特征）

使用 Temp 分隔的熵 $0.29*1+0.43*0.918+0.29*0.811=0.92$ 信息增益： $0.940-0.92=0.02$

使用 Humidity。分隔的熵 $0.5*0.985+0.5*0.592=0.79$ 信息增益： $0.940-0.79=0.15$

使用 Wind 分隔的熵 $0.57*0.811+0.43*1=0.89$ , 信息增益： $0.940-0.89=0.05$

根节点分割结果

决策在kaggle上的利器(一)

03 分类树-基尼指数

3-1 基尼指数

基尼指数（Gini 不纯度）表示在样本集合中一个随机选中的样本被分错的概率

Gini 指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。当集合中所有样本为个类时，基尼指数为 0 基尼指数的计算方法

$Gini(p)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_{k}^2$

其中，pk 表示选中的样本属于第 k 个类别的概率

根据天气状况预测是否打高尔夫球，首先计算根节点的基尼指数：

原始数据的基尼不纯度计算：共 14 条数据

5次No,概率$p1=5/14 $

9次Yes,概率 $p2=9/14$
$Gini=1-\sum_{i=1}^3p_i^2=1-(\frac{5}{14})^2-(\frac{9}{14})^2=0.459$
睛朗程度 outlookl 的 Gini 指数

Outlook	Yes	No	Frequency	P
Rainy	2	3	5	0.36
Overcast	4	0	4	0.29
Sunny	3	2	5	0.36
			14

outlookl 加权的基尼不纯度:

$\begin{aligned} &(5/14)gini(2,3)+(4/14)gini(4,0)+(5/14)gini(3,2) \\ &=5/14*(1-(2/5)^2-(3/5)^2 +4/14*(1-(4/4)^2-(0/4)^2)+\\ &5/14*(1(3/5)^2-(2/5)^2)=0.342 \end{aligned}$
那么Gin增益： $0.459-0.342=0.117$

湿度 Humidity加权的基尼不纯度
$\begin{aligned} &(7/14)gini(3,4)+(7/14)gini(6,1)\\ &7/14*(1-(3/7)^2-(4/7)^2 \\ &+7/14*(1-(6/7)^2-(1/7)^2)=0.3674 \end{aligned}$
Gini 増益： $0.459-0.3674=0.0916$

风力 wind加权的基尼不纯度
$\begin{aligned} &(8/14)gini(6,2)+(6/14)gini(3,3) \\ &=8/14*(1-(6/8)^2-(2/8)^2) \\ &+6/14*(1-(3/6)^2-(3/6)^2)=0.4286 \end{aligned}$
Gini 増益： $0.459-0.4286=0.0304$

CART 树是二叉树，对于一个具有多个取值（超过 2 个）的特征，需要计算以每一个取值作为划分点，对样本 D 划分之后子集的纯度 Gini (D, Ai）然后从所有的可能划分的 Gini (D, Ai）中找出 Gini 指数最小的划分，这个划分的划分点，便是使用特征 A 对样本集合 D 进行划分的最佳划分点

使用 Outlook 分隔的 Gini 增益：0.117（最佳分隔特征）

使用 Temp 分隔的 Gini 增益：0.0185

使用 Humidity 分隔的 Gini 增益：0.0916

使用 Wind 分隔的 Gini 增益：0.0304

Outlook 是最优的分割特征，揭下来计算 rainy, overcast，和 sunny 的基尼指数，选择最小的作为分割节点即可

04 回归树

回归树（regression tree），就是用树模型做回归问题，每一片叶子都输出一个预测值。预测值一般是叶子节点所含训练集元素输出的均值。

决策在kaggle上的利器(一)

回归树的分支标准：标准方差（Standard Deviation）。回归树使用某特征将原集合分为多个子集，用标准方差衡量子集中的元素是否相近越小表示越相近。首先计算根节点的标准方差

$Count=n=14$ ; Count：数据集的元素个数

$Average=\bar x=\frac{\sum x}{n}=39.8$ ; Average：数据集的均值，如果为叶子节点,那么就是预测值

$Standard Deviation=S=\sqrt{\frac{\sum(x-\bar x)^2}{n}}=9.32$ ; 标准方差衡量集合中元素的相似度

$Coefficient of Variation=Cv=\frac{S}{\bar x}*100\%=23\%$ 变化系数用于決定是否停止进一分叉

使用标准方差来确定分支，以计算 Outlook 分支后的标准差为例
$S(TT,X)=\sum_{c\in X}P(c)S(c)$

决策在kaggle上的利器(一)
$\begin{aligned} &S(Houres, Outlook)=\\ &P(Sunny)*S(Sunny)+P(Overcast)*S(Overcast)+P(Rainy)*S(Rainy)\\ &=(4/14)*3.49+(5/14)*7.78+(5/14)*10.87\\ &=7.66 \end{aligned}$
所以可以如下写法：
$S(T,X)=\sum_{c\in X}P(c)S(c)$