学习心得
（1）决策树常用于分类，目标就是将具有 P PP 维特征的 n nn 个样本分到 C CC 个类别中，相当于做一个映射 C = f ( n ) C = f(n)C=f(n) ，将样本经过一种变换赋予一个 l a b e l labellabel。可以把分类的过程表示成一棵树，每次通过选择一个特征 p i pipi 来进行进一步分叉。而根据每次分叉选择哪个特征对样本进行划分，能够又快又准地对样本进行分类，即根据不同的特征选择方案，我们分为了：ID3、C4.5、CART等算法。
（2）掌握节点分类指标的引入原因、定义和计算，掌握两种分类树的原理和区别，掌握CART树与树减枝的原理。
（3）ID3使用【信息增益度】选择测试属性。从直觉上讲，小概率事件比大概率事件包含的信息量大，即百年一见的事情比习以为常的事情包含的信息量大。
（4）信息增益 = 信息熵 - 条件熵
其中【熵】指信息量的大小，即表示随机变量的不确定性，熵越大，随机变量的不确定性越大。如果用p(ai)表示事件ai发生的概率，熵则表示为事件a i aiai的信息量I(ai)：
取任意随机变量的概率均相同时，不确定性越高，即均匀分布的信息熵最大。
（5）CART树：
回归问题：用均方误差（MSE）或平均绝对误差（MAE）来替换熵和条件熵的位置。
分类问题：用基尼系数（CART将熵中的log \loglog在p = 1 p=1p=1处利用一阶泰勒展开，基尼系数定义为熵的线性近似）。
零、从一个栗子开始
通过信息增益计算的公式，我们可以计算我们的决策特征顺序，首先计算总的经验熵：
同理其他的工作、房子和信贷对应的信息增益可以计算：g ( D , A 2 ) = 0.324 , g ( D , A 3 ) = 0.420 , g ( D , A 4 ) = 0.363 g(D, A 2)=0.324, g(D, A 3)=0.420, g(D, A 4)=0.363g(D,A2)=0.324,g(D,A3)=0.420,g(D,A4)=0.363，可以比较发现特征A3（有自己的房子）的信息增益最大，所以我们选择特征A3作为第一个判定的特征。
一、信息论基础
1.1 节点纯度
树具有天然的分支结构。对于分类问题而言，决策树的思想是用节点代表样本集合，通过某些判定条件来对节点内的样本进行分配，将它们划分到该节点下的子节点，并且要求各个子节点中类别的纯度之和应高于该节点中的类别纯度，从而起到分类效果。
节点纯度：反映的节点样本标签的不确定性。
当一个节点的纯度较低时，说明每种类别都倾向于以比较均匀的频率出现，从而我们较难在这个节点上得到关于样本标签的具体信息，其不确定性较高。当一个节点的纯度很高时，说明有些类别倾向于以比较高的频率出现，有更多把握这个节点样本标签的具体信息，即确定性较高。
1.2 度量不确定性的函数H
那对于给定在n nn个状态上定义的离散分布
如何定义度量不确定性的函数H ( p ) H(\textbf{p})H(p)，即H ( p 1 , . . . , p n ) H(p_1,...,p_n)H(p
1
,...,p
n
)呢？香农（1916-2001）于1948年，在创造信息论的著名论文《A Mathematical Theory of Communication》中指出如下定理：
信息熵定理
（该定理证明见论文的Appendix 2）
若度量不确定性的函数H HH满足三个信息熵条件，则H HH的形式只能是
其中，信息熵条件如下：
（1）从构造和计算的角度而言，条件一是容易满足的。
（2）对于条件二而言，假设原来箱子里分别有10个球和100个球，加入每次摸到的球都是等概率抽出的，那么100个球的箱子产生的不确定性必然是要大于10个球的箱子产生的不确定性，即H HH在等概率条件下关于n nn递增。
（3）条件三看上去比较复杂，但其意义是容易理解的，即n nn个事件拆分为n + 1 n+1n+1个事件时的不确定性增加了，并且增加的不确定性与拆分时的比例和拆分事件的概率有关。举例来说：将p = [ 0.9 , 0.1 ] \textbf{p}=[0.9,0.1]p=[0.9,0.1]分别拆分为p 1 = [ 0.45 , 0.45 , 0.1 ] \textbf{p}_1=[0.45,0.45,0.1]p
1
=[0.45,0.45,0.1]和p 2 = [ 0.9 , 0.05 , 0.05 ] \textbf{p}_2=[0.9,0.05,0.05]p
2
=[0.9,0.05,0.05]，那么显然p 1 \textbf{p}_1p
1
增加的不确定性远超过p 2 \textbf{p}_2p
2
；同时，将p = [ 0.9 , 0.1 ] \textbf{p}=[0.9,0.1]p=[0.9,0.1]分别拆分为p 3 = [ 0.8 , 0.1 , 0.1 ] \textbf{p}_3=[0.8,0.1,0.1]p
3
=[0.8,0.1,0.1]，那么显然p 1 \textbf{p}_1p
1
增加的不确定性也远超过p 3 \textbf{p}_3p
3
。
由于指标 H ( p ) H(\textbf{p})H(p) 中的自变量 p \textbf{p}p 是对于某个随机变量 Y YY 分布的描述，因此不妨将其记为信息熵 H ( Y ) H(Y)H(Y) 来反应 Y YY 的不确定性。对于定义在有限状态集合
时，H ( X ) = 0 H(X)=0H(X)=0。因此，离散信息熵的最小值为0且在单点分布时取到。由于p ∗ \mathbf{p}^*p
∗
是极值问题的唯一解，因此离散熵的最大值为log K \log KlogK且在离散均匀分布时取到。
1.3 条件熵
在决策树的分裂过程中，我们不但需要考察本节点的不确定性或纯度，而且还要考察子节点的平均不确定性或平均纯度来决定是否进行分裂。子节点的产生来源于决策树分支的条件，因此我们不但要研究随机变量的信息熵，还要研究在给定条件下随机变量的平均信息熵或条件熵（C o n d i t i o n a l ConditionalConditional E n t r o p y EntropyEntropy）。从名字上看，条件熵就是条件分布的不确定性，那么自然可以如下定义条件熵H ( Y ∣ X ) H(Y\vert X)H(Y∣X)为
E X [ E Y ∣ X [ − log 2 p ( Y ∣ X ) ] ] \mathbb{E}_{X}[\mathbb{E}_{Y\vert X}[-\log_2p(Y\vert X)]]
对于离散条件熵，设随机变量X XX所有可能的取值为{ x 1 , . . . , x M } \{x_1,...,x_M\}{x
1
,...,x
M
}，上式可展开为
``
sklearn的sklearn.tree.DecisionTreeClassifier的参数min_impurity_decrease用来描述父节点的不纯度 - 子节点的不纯度：
上图源自sklearn的sklearn.tree.DecisionTreeClassifier介绍
1.4 信息增益
有了信息熵和条件熵的基础，我们就能很自然地定义信息增益（Information Gain），即节点分裂之后带来了多少不确定性的降低或纯度的提高。在得到了随机变量X XX的取值信息时，随机变量 Y YY 不确定性的平均减少量为
从直觉上说，随机变量Y YY关于X XX的信息增益一定是非负的，因为我们额外地知道了随机变量X XX的取值，这个条件降低了Y YY的不确定性。下面我们就从数学角度来证明其正确性。
定理：设Y YY和X XX为离散随机变量，Y YY关于X XX的信息增益G ( Y , X ) G(Y,X)G(Y,X)非负。
证明：
由信息增益的定义得：
从上式可以发现，信息增益G ( Y , X ) G(Y,X)G(Y,X)在本质上就是p ( y , x ) p(y,x)p(y,x)关于p ( y ) p ( x ) p(y)p(x)p(y)p(x)的KL散度，而KL散度的非负性由Jensen不等式可得：
