共计 1864 个字符，预计需要花费 5 分钟才能阅读完成。
CART 树
CART 树（Classification and Regression Tree）分类回归树，既能够用于创立分类树，也能够用于创立回归树。
分类树：以 C4.5 为例，每次分枝时，是穷举每 个特色 的每一个阈值，依照 $featur{e_i} \le threshold$ 来划分最大熵值的特色 + 阈值。
回归树：总体流程相似，区别在于回归树的每个节点都会失去一个预测值，这个预测值个别是被划分样本均值。在穷举 feature 值寻找最长处时，衡量标准不再是最大熵而是均方误差。
区别：
- 不论是分类树还是回归树，每棵树都是一个判断的特色阈值。
- 分类树最初是类别，回归树最初是一个拟合值。
- 寻找划分阈值时，分类树用 C4.5；回归树用最小二乘。
- 节点输入值，回归树多一个拟合值。
重点讲下回归树是如何选取特色和阈值；以及决定节点的输入值？
1. 抉择特色 + 阈值：
假如将输出空间划分为 m 个区域：${R_1},{R_2},…,{R_{\rm{m}}}$，每个区域上输入值为 ${c_m}$，回归树模型能够示意为：
$$
f(x) = \sum\limits_{m = 1}^M {{c_m}I(x \in {R_m})}
$$
抉择第 j 个特色 ${x^{(j)}}$ 和它的取值 s 作为切分根据，定义两个区域：
$$
{R_1}(j,s) = \{x|{x^{(j)}} \le s\} ,{R_2}(j,s) = \{x|{x^{(j)}} > s\}
$$
利用最小二乘寻找最优切分点：
$$
\mathop {\min}\limits_{j,s} [\mathop {\min}\limits_{{c_1}} \sum\limits_{{x_i} \in {R_1}} {{{({y_i} – {c_1})}^2} + } \mathop {\min}\limits_{{c_2}} \sum\limits_{{x_i} \in {R_2}} {{{({y_i} – {c_2})}^2}} ]
$$
抉择的特色为 j，j 特色的阈值为 s。
2. 节点的输入值：
选定最优切分变量 j 和最优阈值 s 后，此节点的输入值为:
$$
{c_1} = mean({y_i}|{x_i} \in {R_1}(j,s)),{c_2} = mean({y_i}|{x_i} \in {R_2}(j,s))
$$
遍历所有的特色形成(j,s)，并一直顺次划分空间，这样就生成了一棵回归树。
分类树的三个准则
熵值计算：
$$
H(D) = – \sum\limits_{k = 1}^K {\frac{{\left| {{C_k}} \right|}}{{\left| D \right|}}\log } \frac{{\left| {{C_k}} \right|}}{{\left| D \right|}} = – \sum {{p_i}\log {p_i}}
$$
1. 信息增益（ID3）
$$
信息增益 =entropy(前)-entropy(后)
$$
$$
g(D,A) = H(D) – H(D|A)
$$
ID3 偏差取值较多的特色（取值较多的特色更容易失去纯度高的子集），因为取值越多越有机率使得子集纯度更高
2. 信息增益比（C4.5）
$$
信息增益比 = 惩办系数 * 信息增益
$$
$$
{g_R}(D,A){\rm{ =}}\frac{{g(D,A)}}{{{H_A}(D)}},{H_A}(D) = – \sum\limits_{k = 1}^n {\frac{{\left| {{D_k}} \right|}}{{\left| D \right|}}\log } \frac{{\left| {{D_k}} \right|}}{{\left| D \right|}}
$$
${H_A}(D)$：特色 A 有 n 个值，计算 D 下依照 n 个 A 值进行划分，n 越多 H 值越大以此来克制多值的特色。
3. 基尼指数（Gini）
基尼指数示意：在样本汇合中一个随机样本被份错的概率
$$
基尼指数 = 样本被选中的概率 * 样本被分错的概率
$$
$$
Gini(p) = \sum\limits_{k = 1}^K {{p_k}(1 – {p_k})}
$$
$$
Gini(D) = 1 – {\sum\limits_{k = 1}^K {(\frac{{\left| {{C_k}} \right|}}{{\left| D \right|}})} ^2}
$$
$$
Gini(D,A) = \frac{{\left| {{D_1}} \right|}}{{\left| D \right|}}Gini({D_1}) + \frac{{\left| {{D_2}} \right|}}{{\left| D \right|}}Gini({D_2})
$$
CART 采纳的就是基尼指数
参考 https://zhuanlan.zhihu.com/p/…