树算法

信息增益的计算方法

https://blog.csdn.net/it_beecoder/article/details/79554388

决策树--信息增益，信息增益比，Geni指数的理解

https://www.cnblogs.com/muzixi/p/6566803.html

熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。

(1)ID3算法---信息增益

做法：计算使用所有特征划分数据集D，得到多个特征划分数据集D的信息增益，从这些信息增益中选择最大的，因而当前结点的划分特征便是使信息增益最大的划分所使用的特征。

缺点：信息增益偏向取值较多的特征

原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集(极端：每个特征值只有1个)，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较偏向取值较多的特征。

(2)C4.5算法--信息增益比

信息增益比 = 惩罚参数 * 信息增益

惩罚参数：数据集D以特征A作为随机变量的熵的倒数

缺点：信息增益比偏向取值较少的特征

原因：当特征取值较少时HA(D)的值较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少的特征。

使用信息增益比：基于以上缺点，并不是直接选择信息增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。

(3)CART树--基尼指数

https://www.jianshu.com/p/b90a9ce05b28

https://www.cnblogs.com/yonghao/p/5135386.html

表示在样本集合中一个随机选中的样本被分错的概率。

Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。

Xgboost

全名：eXtreme Gradient Boosting

https://www.cnblogs.com/zongfa/p/9324684.html

XGBoost是以分类回归树(CART树)进行组合

模型预测： $\tilde{y_i}=\sum_{k=1}^K f_k(x_i)$

损失函数： $Obj(\theta )=\sum_{i=1}^n l(y_i,\tilde{y_i})+\sum\nolimits_{k=1}^K \Omega(f_k)$

其中 $\Omega(f_k)$ 表示第k颗树的正则项；K代表树的总个数。

每次往模型中加入一棵树，其损失函数便会发生变化。另外在加入第t棵树时，则前面第t-1棵树已经训练完成，此时前面t-1棵树的正则项和训练误差都成已知常数项。

$Obj(\theta )=\sum_{i=1}^n l(y_i,\tilde{y_i}^{(t-1)}+f_t(x_i))+\Omega(f_t) +C=\sum_{i=1}^n l(y_i,\tilde{y_i}^{(t-1)}+f_t(x_i))+\Omega(f_t) +C$

如果损失函数采用均方差时，其目标损失函数变为：

$Obj(\theta )=\sum_{i=1}^n (y_i-(\tilde{y_i}^{(t-1)}+f_t(x_i)))^2+\Omega(f_t)+C \\=\sum_{i=1}^n [2(\tilde{y}^{(t-1)}-y_i)f_t(x_i)+f_t{(x_i)}^2]+\Omega(f_t)+C_1$

对于其中每一棵回归树，其模型可以写成： $f_t(x)=w_{q(x)},w\in R^T$

其中w为叶子节点的得分值，q(x)表示样本x对应的叶子节点，T为该树的叶子节点个数。

树的复杂度 $\Omega (f_t)=\gamma T+\frac{1}{2} \lambda \sum_{j=1}^T w_j^2$

泰勒展开式： $f(x+\Delta x)\approx f(x)+f^‘(x)\Delta x+\frac{1}{2}f^{‘‘} (x)\Delta x ^2$

$Obj(\theta )\approx \sum_{i=1}^n [l(y_i,\tilde{y}^{(t-1)} )+\partial _{\tilde{y}^{(t-1)}}l(y_i,\tilde{y}^{(t-1)} )f_t(x_i)+\frac{1}{2} \partial _{\tilde{y}^{(t-1)}}^2l(y_i,\tilde{y}^{(t-1)} )f_t(x_i)^2]+\gamma T+\frac{1}{2}\lambda \sum_{j=1}^T w_j^2$

令： $g_i=\partial _{\tilde{y}^{(t-1)}}l(y_i,\tilde{y}^{(t-1)} )$ ， $h_i=\partial _{\tilde{y}^{(t-1)}}^2l(y_i,\tilde{y}^{(t-1)} )$

去除常数项，得

$Obj(\theta )\approx \sum_{i=1}^n [g_if_t(x_i)+\frac{1}{2} h_i f_t(x_i)^2]+\gamma T+\frac{1}{2}\lambda \sum_{j=1}^T w_j^2 \\ =\sum_{i=1}^n [g_i w_{q(x_i)}+\frac{1}{2} h_i w_{q(x_i)}^2]+\gamma T+\frac{1}{2}\lambda \sum_{j=1}^T w_j^2 \\ =\sum_{j=1}^T [(\sum_{i\in I_j} g_i)w_j+(\frac{1}{2}\sum_{i\in I_j}h_i )w_j^2]+\gamma T+\frac{1}{2}\lambda \sum_{j=1}^T w_j^2 \\=\sum_{j=1}^T [(\sum_{i\in I_j} g_i)w_j+(\frac{1}{2}(\sum_{i\in I_j}h_i+\lambda ) )w_j^2]+\gamma T$