特征选择（节点划分）
一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)越来越高。
符号声明
假设当前样本集合
中第
类样本所占的比例为))
，离散属性
有
个可能的取值
，若使用来对样本集进行划分，则会产生个分支结点，其中第
个分支结点包含了中所有在属性上取值为
的样本，记作
。
样本集合的信息熵定义为
%3D-%5Csum_%7Bk%3D1%7D%5E%5Cmathcal%7B%7CY%7C%7D%20p_k%5Clog_2%7Bp_k%7D)
1. 信息增益
%20%3D%20Ent(D)-%5Csum_%7Bv%3D1%7D%5E%7BV%7D%20%5Cfrac%7B%7CD%5Ev%7C%7D%7B%7CD%7C%7DEnt(D%5Ev)%5Ctag%7B1%7D)
实际上，信息增益准则对可取数目较多的属性有所偏好。
2. 增益率
决策树算法选择增益率(gain ratio)来选择最优划分属性。
%3D%5Cfrac%7BGain(D%2Ca)%7D%7BIV(a)%7D%20%5Ctag%7B2%7D%20%5C%5C%20s.t.%20%5Cquad%20IV(a)%3D-%5Csum_%7Bv%3D1%7D%5E%7BV%7D%5Cfrac%7B%7CD%5Ev%7C%7D%7B%7CD%7C%7D%5Clog_2%5Cfrac%7B%7CD%5Ev%7C%7D%7B%7CD%7C%7D)
)
称作属性的固有值(intrinsic value)。
需注意的是，增益率准则对可取值较少的属性有所偏好，因此，算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
3. 基尼指数
%20%26%3D%20%5Csum_%7Bk%3D1%7D%5E%7B%5Cmathcal%7B%7CY%7C%7D%7D%5Csum_%7Bk'%20%5Cneq%20k%7Dp_k%20p_%7Bk'%7D%5C%5C%20%26%3D%201-%5Csum_%7Bk%3D1%7D%5E%7B%5Cmathcal%7B%7CY%7C%7D%7Dp_k%5E%7B2%7D%20%5Cend%7Baligned%7D)
直观来讲，)
反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。因此，越小，则数据集的纯度越高。
属性的基尼指数：
%20%3D%20%5Csum_%7Bv%3D1%7D%5E%7BV%7D%20%5Cfrac%7B%7CD%5Ev%7C%7D%7B%7CD%7C%7DGini(D%5Ev)%20%5Ctag%7B3%7D)
于是，我们在候选属性集合
中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即：
)
