1 基本流程

决策树（decision tree）是一类常见的机器学习方法。 一般包含：一个根结点、若干个内部结点和若干个叶结点。

叶结点：决策结果其他每个结点：对应一个属性测试每个结点包含的样本集合：根据属性测试的结果呗划分到子结点中根结点：包含样本全集。从根节点到每个叶结点的路径：对应了一个判定测试序列。

决策树学习目的：产生以可泛化能力强（处理未见实例能力强）的决策树，其基本流程遵循“分而治之”（divide-and-conquer）策略，如所示：

输入：训练集D={（x1,y1）,(x2,y2),...,(xm,ym)} 属性集A={a1,a2,...,ad} 过程：函数TreeGenerate(D,A) 1.生成结点node; 2.if D中样本全属于同一类别C then: 3. 将node标记为C类叶结点；return 4. end if 5. if A=空集 or D中样本再A上取值相同 then: 6. 将node标记为叶结点，其类别标记为D中样本数最多的类；return 7. end if 8. 从A中选择最优划分属性a*; 9. for a*的每一个值a*v do: 10. 为node生成一个分支； 11. if Dv为空 then: 12. 将分支结点标记为叶结点，其类别标记为D中样本最多的类；return 13. else 14. 以TreeGenerate(Dv,A\{ak})为分支结点 15. end if 16. end for 输出：以node为根结点的一棵决策树

由上可知为一个递归过程，有三种情形会导致递归返回：

当前结点包含的样本全属于同一类别，无需划分；当前属性集为空，或是所有样本再所有属性上取值相同，无法划分；当前结点包含的样本集合为空，不能划分。

2 划分选择

2.1 信息增益

信息熵（information entropy）：是度量样本集合纯度最常用的一种指标。

假定当前样本集合D中第k类样本所占的比例为$p_k(k=1,2,...,|y|)$，则D的信息熵定义为： $Ent(D)=-{\sum }_{k=1}^{|y|}{p}_k{\log }_2{p}_k$ $Ent(D)$的值越小，则D的纯度越高。

$Ent(D)$的最小值为0，最大值为${\log }_2|y|$

假定离散属性$a$有$V$歌可能的取值{$a^1,a^2,...,a^V$}，计算用属性$a$对样本集$D$进行划分所获得的”信息增益“(information gain): $Gain(D,a)=Ent(D)-{\sum }_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$

2.2 增益率

把”编号“也作为一个候选划分属性。”增益率“定义为： $Gai{n}_{-}ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$

其中 $IV(a)=-{\sum }_{v=1}^V\frac{|D^v|}{|D|}{\log }_2\frac{|D^v|}{|D|}$ 称为属性$a$的”固有值”(intrinsic value)

2.3 基尼系数

CART(Classification and Regression Tree)决策树使用“基尼系数”(Gini index)来选择划分属性。

数据$D$的纯度可用基尼值来度量： $Gini(D)={\sum }_{k=1}^{|y|}{\sum }_{k^{‘}!=k}{p}_k{p}_{k^{‘}}=1-{\sum }_{k=1}^{|y|}{p}_k^2$