基本算法
以递归的形式生成一个树 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23#输入训练集D和属性集A
def TreeGenerate(D, A):
node = generate_node() #生成节点
if D.all() in types[C]: #如果D中所有节点都属于类别C
node.type = ('leaf', C) #将node标记为C类叶节点
if A.empty() or D.all().A.same(): #如果A为空集或者D中样本在A上取值相同
C = D.type.most() #类别C为D中样本数最多的类别
node.type = ('leaf', C) #将node标记为C类叶节点
a = best_divide(A) #从A中选择出最优划分属性a
for a_val in a: #遍历最优划分a的所有值
d = D.find(a.val = a_val) #找到D中所有属性a的值等于a_val的样本
if d.empty():
child = generate_node(father = node) #生成node的分支节点
C = D.type.most() #类别C为D中样本数最多的类别
child.type = ('leaf', C) #将child标记为C类叶节点
else:
child = TreeGenerate(d, A\a) #递归获得child
child.father = node #将child作为node的分支节点
return node
划分最优属性
信息增益（information entropy）
假定当前样本集合\(D\)中第\(k\)类样本所占的比例为\(p_k (k=1,2,...,|Y| )\)，则\(D\)的信息熵定义为 \[Ent(D)=-\sum_{k=1}^{|Y|}p_k\log_2p_k\] \(Ent(D)\)的值越小，\(D\)的纯度越高。
用属性\(a\)对样本集\(D\)进行划分所获得的“信息增益”（information gain）为 \[Gain(D,a)=Ent(D) - \sum_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)\] 信息增益越大，意味着使用属性\(a\)来进行划分所获得的“纯度提升”越大，因此可以使用\(a_* = \arg\max\limits_{a \in A}Gain(D,a)\)来选择属性。
信息增益有一个问题，在某个属性的每个分支节点仅包含一个样本的时候，其信息增益极大，但仅仅是因为每个分支的纯度都达到最大，这样的决策树并不具有泛化能力。
ID3决策树算法（ID：Iterative Dichotomiser 迭代二分器）使用信息增益为准则来选择划分属性。
增益率（gain ratio）
为了解决信息增益存在的问题，可以使用增益率（gain ratio） \[Gain\_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）。属性\(a\)的可能取值数目越多，\(IV(a)\)的值通常越大。
增益率准则对可取值数目较少的属性有所偏好，不适合直接使用。
C4.5决策树算法选择划分属性时使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
基尼指数（Gini index）
用基尼值来度量数据集\(D\)的纯度： \[Gini(D)=\sum_{k=1}^{|Y|}\sum_{k'\not=k}p_kp_{k'}=1-\sum_{k=1}^{|Y|}p_k^2\] 基尼值反映了从数据集\(D\)中随机抽取两个样本，其类别表集不一致的概率，因此基尼值越小，数据集D纯度越高
属性\(a\)的基尼指数定义为： \[Gini\_index(D,a)=\sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)\]
因此可以使用\(a_* = \arg\max\limits_{a \in A}Gini\_index(D,a)\)来选择最优划分属性。
CART（Classification and Regression Tree）决策树用尼基指数来作为准则来选择划分属性。