前言
决策树（Decision Tree）是一种常见的机器学习方法。决策树基于树形结构进行决策，其每个非叶节点表示一个某属性集上的划分，每个分支代表这个特征属性在某个值域上的输出，每个叶节点则对应一个类别。本文主要总结一些基础的决策树算法。
决策树基本算法
输入:
训练集 \(D\) = \(\{(x_1, y_1), (x_2, y_2), ..., (x_m, y_m)\}\)
属性集 \(A\) = \(\{(a_1, a_2, ..., a_d)\}\)
过程：函数 \(TreeGenerate(G, A)\)
if \(D\) 中的样本全属于同一类别 \(C\) then
将node标记为 \(C\) 类叶节点; return
end if
if \(A\) = \(\emptyset\) OR \(D\) 中的样本在 \(A\) 上的取值相同 then
将node标记为叶节点，类别为 \(D\) 中样本最多的一类; return
end if
从 \(A\) 中选择最优化分属性 \(a_*\)
for \(a_*\) 的每一个取值 \(a_{*}^{v}\) do
为node生成一个分支；令 \(D_v\) 表示 \(D\) 中在 \(a_*\) 上取值为 \(a_{*}^{v}\) 的样本子集;
if \(D_v\) 为空 then
将分支结点标记为叶节点，其类别标记为 \(D\) 中样本最多的类; return
else
以 \(TreeGenerate(D_v, A \setminus\{a_*\})\) 为分支结点
end if
end for
属性划分
假定当前样本集合 \(D\) 中第 \(k\) 类样本所占比例为 \(p_k\) (\(k\) = 1,2, ... ,\(\mathcal{|Y|}\))
1.信息熵 \[Ent(D) = - \sum_{k=1}^{|\mathcal{Y}|}p_klog_2p_k\] 2.信息增益 \[ Gain(D, a) = Ent(D)-\sum_{v=1}^{V}\frac{\lvert D^v\rvert}{\lvert D \rvert}Ent(D^v)\]
3.信息增益率 \[Gain\_ratio = \frac{Gain(D, a)}{IV(a)}\] \[IV(a) = -\sum_{v=1}^{V}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}\] 4.基尼系数 \[Gini(D)=\sum_{k=1}^{|\mathcal{Y}|}\sum_{k^{`} \neq k}p_k p_{k^`}\] \[Gini\_index(D,a) = \sum_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v)\]