分类算法

决策树可以用来解决分类与回归问题。

基本算法

如何度量信息量的大小： 信息增益
熵

建立决策树使用的3个经典的算法分别是：
- ID3
- C4.5
- CART

小结

方法	特征选择
ID3	信息增益	$g(D, A)=H(D)- H(D\|A)$
C4.5	信息增益比	$<span class="arithmatex"><span class="MathJax_Preview">g_r(D,A)=g(D,A)/H(D)</span><script type="math/tex">g_r(D,A)=g(D,A)/H(D)$
CART(分类+回归)	基尼系数; 平方误差	$Gini(p)=\sum p_k(1-p_k)$

树剪枝

为了防止过拟合问题，因为树的深度越深、叶子节点数越多越可能过拟合。所以需要考虑决策树的负责度，对已经生成的树进行简化——剪枝。

CART

假设决策树都是二叉树，决策树的生成就是递归地构建二叉树的过程，对于

(1) 回归树：用平方误差最小
假设已将输入空间划分为M各单元R1,R2..Rm,并且每个单元Rm上有一个固定的输出Cm，回归树表示为:
$<span class="arithmatex"><span class="MathJax_Preview">f(x)=\sum_1^M c_mI(x\in R_m)</span><script type="math/tex">f(x)=\sum_1^M c_mI(x\in R_m)$
- 当输入空间划分确定后，可以利用平方误差计算来表示蓄念的误差，，所以很容易确定每个划分空间下$\hat c_m = avg(y_i|x_i \in R_m)$

• 如何进行空间划分
  启发式：选择第j个变量x(j)和它取的值s，作为切分变量和切分点，定义两个区域：
  
  然后寻找最优的切分变量和切分点 是得两个的误差损失和最小

遍历所有的输入变量，找到最优的切分变量和对应的切分点。
然后重复上面的过程，进行二叉树构造。

(2) 分类树：基尼指数
基尼指数：假设有k个分类，则概率分布的基尼指数定义为
$<span class="arithmatex"><span class="MathJax_Preview">Gini(p)=\sum_1^K p_k(1-p_k)=1-\sum p_k^2</span><script type="math/tex">Gini(p)=\sum_1^K p_k(1-p_k)=1-\sum p_k^2$
如果样本集合D根据特征A是否为a被分割成D1和D2，则在特征A的条件下，集合D的基尼指数

CART生成算法
输入：训练数据集D，停止计算条件
输出：CART决策树
从根节点开始，递归对每个结点操作
1 设结点数据集为D，对每个特征A，对其每个值a，根据样本点对A=a的测试为是或否，将D分为D1，D2，计算A=a的基尼指数
2 在所有的特征A以及所有可能的切分点a中，选择基尼指数最小的特征和切分点，将数据集分配到两个子结点中。
3 对两个子结点递归调用1，2步骤
4 生成CART树

其他：
- CART的特征是有放回的，即同一个特征可能会出现在多个节点上