常见的几种决策树

https://www.cnblogs.com/pinard/p/6053344.html
https://blog.csdn.net/a857553315/article/details/95620881

---

特征选择：

如果瞎猜中的概率与特征选择出来的概率相差无几，那么就可以放弃该特征了。特征选择的标准是信息增益或信息增益比。

---

ID3算法与信息增益：（木有剪枝，只能处理离散数据）

得知特征X的信息而使输出的分类Y的不确定性减少的程度。

条件熵：$H(Y|X)=\sum_{n}^{i=1}p_iH(Y|X=x_i)$

信息增益：$g(D,A)=H(D)-H(D|A)$，D是数据集，A是特征。

---

计算过程：

（1）计算数据集D的经验熵：

$H(D)=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$ ，k为第一级特征{纹理，色泽，触感}

（2）计算条件熵：

$H(D|A)=\sum_{i=1}^{n}\frac{|D_i|}{D}H(D_i)=\sum_{i=1}^{n}\frac{|D_i|}{|D|}\sum_{k=1}^{K}\frac{|D_{ik}|}{D_i}log_2\frac{|D_{ik}|}{|D_i|}$

i为第一级特征{ 纹理 / 色泽 / 触感 }，ik为纹理中的第二级特征{ 清晰，模糊，稍糊 }

（3）$g(D,A)=H(D)-H(D|A)$，越大越好。

• ID3算法就是完全依赖信息增益，但是信息增益明显对多个取值的特征有偏好，所以出现了使用增益率的C4.5算法。

---

C4.5算法与增益率（后剪枝，可以处理连续数据—>多叉树，特征要计算排序）

$Gainratio(D,a)=\frac{Gain(D,a)}{IV(a)}$

固有值：$IV(a)=-\sum_{v=1}^{V}\frac{|D_v|}{|D|}log_2\frac{|D_v|}{|D|}$ ，Dv是第一级特征a下的第二级特征，固有值随V的个数增加而增加。

---

CART决策树（减少log的使用降低计算量，还可以用于回归，二叉树）

使用Gini系数替代ID3里的熵，Gini系数越小越均衡（被错分的概率低），说明该样本只属于同一类的概率（纯度）越高。

$Gini(D)=\sum_{k=1}^{y}\sum_{k’ \ne k}p_k*p_k’=1-\sum_{k=1}^{y}p_k^2$

pk表示选中的样本属于k类别的概率，则这个样本被分错的概率是(1-pk)

基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率

预剪枝与后剪枝：（对抗过拟合与欠拟合）

• 预剪枝：（边自上往下生成枝杈边剪枝）

预剪枝使得很多分支没有展开，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间。但是，有些分支虽当前不能提升泛化性。甚至可能导致泛化性暂时降低，但在其基础上进行后续划分却有可能导致显著提高，因此预剪枝的这种贪心本质，给决策树带来了欠拟合的风险。

• 后剪枝：（先生成枝桠，最后从下往上剪枝）

后剪枝通常比预剪枝保留更多的分支，其欠拟合风险很小，因此后剪枝的泛化性能往往优于预剪枝决策树。但后剪枝过程是从底往上裁剪，因此其训练时间开销比前剪枝要大。

---

连续值处理：（密度/甜度）

连续（非离散）特征可以将特征值从小到大排列然后取

$$T_a={\frac{a_i+a_{i+1}}{2},0<i<n}$$ $$Gain(D,a)=\max_{t \in T_a} Gain(D,a,t)=max Ent(D)-\sum_{\lambda \in {-,+}}\frac{|D_t^\lambda|}{|D|}Ent(D_t^\lambda)$$

按照 $T_a$ 进行划分 { - ，+ }，从而得到该情况下的信息增益。

---

缺失值处理：（检测数据缺失）

（1）如何在属性值缺失的情况下进行划分属性的选择？（创建决策树的时候怎么计算缺失值存在下的信息增益，选择正确的属性）
（2）给定划分属性，若样本在该属性上的值是缺失的，那么该如何对这个样本进行划分？（在分类过程中有缺失值的话怎么进行划分）

无缺失样本所占比例：$p=\frac{ \sum_{x \in \tilde{D}}w_x}{ \sum_{x \in D} w_x}$
无缺失样本中第k类所占比例：$\tilde{p}_k=\frac{ \sum_{x \in \tilde{D}_k}w_x}{ \sum_{x \in \tilde{D}} w_x}$
无缺失样本中在特征a上取值为$a_v$的样本所占比例：$\tilde{r}_v=\frac{ \sum_{x \in \tilde{D}_k}w_x}{ \sum_{x \in \tilde{D}} w_x}$

最后得到了推广了的公式：

$$Gain(D,a)=p*Gain(D,\tilde a)=p*(Ent(\tilde D)-\sum_{v=1}^{V}\tilde{r}_vEnt(\tilde D^v))$$

• 上式 = 总样本中非缺失的比例 *（非缺失中各类的熵-各类概率*各类特征值的熵）

$$Ent(\tilde D)=-\sum_{k=1}^{y}\tilde{p}_klog_2{\tilde{p}_k}$$

---

多变量决策树：

一般的决策树分类边界由若干个与坐标轴平行的分段组成：

判断过程：密度 -> 含糖率 -> 密度 -> 含糖率…

多变量决策树有d个属性对应d维空间的一个数据点，对样本分类表示在坐标空间中找到不同样本之间的分类边界。

“多变量决策树”能实现斜的划分边界，使决策树模型简化。在多变量决策树的学习过程中，不是为非叶结点寻找最优划分属性，而是试图建立合适的线性分类器：

可以通过最小二乘或者嵌入神经网络进一步优化。

---

增量学习：根据新样本可对学得的模型进行调整适应当前形势，而不需要重新训练。如ID4，ID5R还有ITI

---

熵与基尼系数哪个好

和熵模型的度量方式比，基尼系数对应的误差有多大呢？对于二类分类，基尼系数和熵之半的曲线如下：

Gini = 2 * p * (1-p)
H = (-p * np.log2(p) - (1 - p) * np.log2(1 - p))/2.0

import numpy as np
from matplotlib import pyplot as plt 
import matplotlib as mpl
mpl.rcParams['font.sans-serif'] = ['simHei']
mpl.rcParams['axes.unicode_minus'] = False
 
p = np.linspace(0.0001, 0.9999 ,50)
Gini = 2 * p * (1-p)
H = (-p * np.log2(p) - (1 - p) * np.log2(1 - p))/2.0
x1 = np.linspace(0,0.5,50)
y1 = x1
x2 = np.linspace(0.5,1,50)
y2 = 1- x2
 
plt.figure(figsize=(10,5))
plt.plot(p, Gini, 'r-', label='基尼指数')
plt.plot(p, H, 'b-', label='半熵')
plt.plot(x1, y1, 'g-', label='分类误差率')
plt.plot(x2, y2, 'g-')
plt.legend()
plt.xlim(-0.01, 1.01)
plt.ylim(0, 0.51)
plt.show()

从上图可以看出，基尼系数和熵之半的曲线非常接近，因此，基尼系数可以做为熵模型的一个近似替代。而CART分类树算法就是使用的基尼系数来选择决策树的特征。为了进一步简化，CART分类树算法每次仅仅对某个特征的值进行二分，而不是多分，这样CART分类树算法建立起来的是二叉树，而不是多叉树。