1. 决策树概览

对于一个具有多个属性的数据集，决策树根据某种划分决策，依据某个离散属性对数据集进行划分，形成子集，之后递归地对子集进行划分，直到子集均属于某一类别，或是在某个容忍度下属于某种类比。

假设有样本集合 (D)，它有如下属性：

对于决策树的建立，首先要解决的是划分。

2. 划分依据

假设对于样本集合的某个离散属性 (a)，有 (V) 种可能的取值，那么我们使用这个属性对样本集合进行划分后，可以获得 (V) 个子集，即 (V) 个分支节点。有3种常见的划分依据可以选择：

CART决策树使用基尼指数来选择划分属性。

基尼指数使用基尼值来衡量一个集合的纯度：

[egin{align} ext{Gini}(D) &= sum_{k=1}^{|gamma|}sum_{k' eq k}p_kp_{k'}\ &=1-sum_{k=1}^{|gamma|}p_k^2 end{align} ]

直观的来看，基尼值反映了从数据集中任意抽取两个样本，其类别标记不一样的概率。
显然，基尼值越小，则数据集的纯度越高。

据此，基尼指数定义为：

[egin{align} ext{Gini_index}(D,a)=sum_{v=1}^Vfrac{|D_v|}{|D|} ext{Gini}(D_v) end{align} ]

考虑到划分的不同子集的个数不一样，引入权重因子 (frac{|D_v|}{|D|}), 样本越多分支节点影响越大。

划分决策：
在候选属性集合 (A) 种，选择那个使得划分后基尼指数最小的属性作为划分属性

ID3决策树使用信息增益来作为划分依据。

信息增益使用信息熵来衡量一个样本集合的纯度：

[egin{align} ext{Entropy}(D) = ext{Ent}(D)=-sum_{k=1}^{|gamma|}p_klog_2p_k end{align} ]

当集合只有一个类别 (k') 的时候 (p_{k eq k'}=0, p_{k'}=1)，则

[egin{align} min ext{Ent}(D)=0 end{align} ]

当集合中所有类别同概率分布的时候，(p_1=p_2=cdots=p_{|gamma|}=frac{1}{|gamma|})

[egin{align} max ext{Ent}(D)=-|gamma|frac{1}{|gamma|}log_2{frac{1}{|gamma|}}=log_2{|gamma|} end{align} ]

可以看到，( ext{Ent}(D)) 的值越小，则数据集的纯度越高。

同样，根据划分子集进行加权，获得信息增益：

[egin{align} ext{Gain}(D,a)= ext{Ent}(D)-sum_{v=1}^{V}frac{|D_v|}{|D|} ext{Ent}(D_v) end{align} ]

一般来说，信息增益越大，则意味着使用属性 (a) 来划分所获得的 纯度提升 越大。

划分决策：
在候选集合 (A) 中，选择那个使得划分前后信息增益大的属性

相比于基尼指数，信息增益关注划分前后变化，而基尼指数只关注划分后的集合纯度。

[egin{align} error=1-max limits_k p(k|D) end{align} ]

错分误差的纯度判定比较粗暴，它衡量集合是否倾向于某一种分类。

根据公式(8)可以知道，如果集合(D)全是一类，则 (error=0); 而如果集合均匀分布，则(error_{max}=1-frac{1}{|gamma|})

对于决策树，第二个要解决的问题是什么时候停止划分。