决策树
决策树学习算法
决策树的学习算法一共有三点：
特征选择，决策树生成，决策树剪枝
决策树的非叶子节点代表选择的一个划分标准（如，第 \(i\) 个分量 \(x^{(i)}\) 是否大于等于 \(0\)），每一个叶子节点代表一个类（样本属于这些类）
特征选择
希望每一步选择的特征都是良好的，引入一个指标来计算：信息增益。
信息增益：得知 特征X 的信息而使得类 Y 的信息的不确定性减少的程度，即经验熵的改变量。 定义为： \[ g(D, A)=H(D)-H(D|A) \] 其中 \(D\) 为数据集，\(A\) 为我们选择的特征，\(H\) 为经验熵函数。
我们希望 \(H\) 越小越好，即每一步的 \(g(D,A)\) 要大。
容易发现，当 \(A\) 表征的特征有更多选项时更容易被选中，所以引入信息增益比： \[ g_R(D, A)=\dfrac{g(D,A)}{H_A(D)} \] 其中 \(H_A(D)\) 为数据集 \(D\) 关于特征 \(A\) 的熵 \[ H_A(D)=-\sum_{i=1}^n \dfrac{|D_i|}{|D|}\log_2{\dfrac{|D_i|}{|D|}} \]
决策树生成
一共两种算法，ID3 和 C4.5
ID3 算法依赖于信息增益，而 C4.5 则是信息增益比作为评价标准
流程：
给定数据集 \(D\) 以及特征集 \(A\) 阈值 \(\epsilon\)
按照每一个特征，计算信息增益（比）；选取信息增益（比）最大的特征 \(A\)，如果节点全部都属于同一类 \(C_k\)，则直接标记为\(C_k\) 类并返回
否则开始划分，按照 \(A\) 的每一个可能的值 \(a_i\) 将划分为 \(D_i\)，递归此过程，直到子节点全部属于一类或者信息增益（比）小于阈值 \(\epsilon\) 或者特征集 \(A\) 为空。
这两个都容易产生过拟合的问题，故考虑剪枝
决策树剪枝
实质上就是一种正则化手段，利用经验熵作为损失函数，叶子节点数作为正则化项。
定义决策树学习的损失函数为：
\[ C_\alpha(T)=\sum_{t=1}^{|T|} N_tH_t(T)+\alpha|T| \]
其中经验熵函数为
\[ H_t(T)=-\sum_k \dfrac{N_{tk}}{N_t}\log \dfrac{N_{tk}}{N_t} \]
其中，\(|T|\) 为决策树的节点数（正则化项），\(t\) 是子节点编号，\(N_t\) 是每个叶节点的样本数，其中第 \(k\) 类的有 \(N_{tk}\) 个。
当 \(\alpha\) 很小的时候，说明选择损失函数最小的模型，调大 \(\alpha\) 相当于限制（减小）模型复杂度。
剪枝算法： 1. 递归，计算每一个叶节点的经验熵
尝试将一个叶子节点缩到父节点，比较前后的经验熵，如果经验熵减小，说明可以直接剪枝，将父节点变为一个新的叶节点。
回到2，继续操作
CART 决策树
概述
CART 是一种二叉决策树，每次提问都是 y/n；
对于回归问题，使用平方误差作为损失函数；对于分类问题，使用 \(\text{Gini}\) 系数；
模型
回归树
\[ f(x)=\sum_{m=1}^M c_m \mathbb{I}(x\in R_m) \]
其中，\(R_m\) 为提问所划分出的区域，\(c_m\) 为其上的代表值（固定的输出值）；
通过平方误差计算时，容易知道 \(c_m\) 应该取 \(R_m\) 的标签的平均值
现在问题在于如何划分。
采用启发式的方法，每次取一个方向 \(x^{(j)}\)，考虑将 D 按照这个方向上的一个数值 \(s\) 来划分
\[ R_1(j,s)=\{x|x^{(j)}\leq s\},R_2(j,s)=\{x|x^{(j)}> s\} \]
现在来求解
\[ \min_{j,s} \left\{ \min_{c_1} \sum_{x_i\in R_1(j,s)} (y_i-c)^2 + \sum_{x_i\in R_2(j,s)} (y_i-c)^2 \right\} \] 固定 \(j\) 有 \(\hat{c}_1=\text{ave}(y_i|x_i\in R_1(j,s)),\hat{c}_2=\text{ave}(y_i|x_i\in R_2(j,s))\)
重复这个过程，直到达到终止条件。
分类树
定义 \(\text{Gini}\) 系数，对于一个概率分布 \(p\) 有
\[ \text{Gini}(p)=\sum_{k=1}^K p_k(1-p_k)=1-\sum_{k=1}^K p_k^2 \]
容易发现它是一个凸函数。
对于一个集合 D 及其划分 \(C_k\)，类似有
\[ \text{Gini}(D)=\sum_{k=1}^K \dfrac{|C_k|}{|D|} \left(1-\dfrac{|C_k|}{|D|}\right)=1-\sum_{k=1}^K \left( \dfrac{|C_k|}{|D|} \right)^2 \]
类似条件经验熵函数，也可以定义条件 Gini 系数。
\(\text{Gini}\) 系数的概念非常类似经验熵函数，同样描述了数据的不确定程度。
分类树则采用 \(\text{Gini}\) 系数，对于每一个特征 \(A\)，对其所有可能值 \(a_i\)，进行 y/n 分类，将 \(D\) 划分为 \(D_1\)，\(D_2\) 两部分，计算条件 \(\text{Gini}\) 系数；选择最小的作为分类，递归操作直到满足终止条件。
剪枝
TODO