决策树可用于分类与回归. 本文讲分类.

1.概述

决策树由根节点, 判断节点及叶子节点组成.
从根节点起, 根据提问与样本的属性做出判断, 一步步往下走, 最终到达叶子节点, 得出最终的决策.
分类-决策树
图1 西瓜数据集

分类-决策树
图2 由西瓜数据集得到的决策树

2.相关概念

2.1 信息熵

信息熵, Information Entropy, 是度量集合中样本分布随机性的一种指标.
假定样本集合D中包含了n类样本, 第k类样本的出现频率为pk, 则D的信息熵定义为

E n t (D) = - \sum k = 1 n p k log 2 p k (1)

熵越小, 则D的纯度越高; 熵越大, 样本分布约随机.

2.2 信息增益

在划分数据集之前之后, 信息发生的变化叫做信息增益, Information Gain.
首先引入条件熵的概念. Ent(D|a)表示在已知变量a的情况下, D中分布的不确定性.
假定离散属性a有V个可能的取值{a1,a2,...,av}, 若只依据a来对数据集D进行划分, 则会产生V个子集, 把元素类别为av的子集记为Dv. 我们可根据式(1)计算出Dv的信息熵. 考虑到不同的子集大小不一样, 所以给不同的子集赋予不同的权重|Dv||D|.

E n t (D | a) = \sum v = 1 V | D v | | D | E n t (D v) (2)

可根据下式计算出用属性a划分D的信息增益:

G a i n (D, a) = E n t (D) - E n t (D | a) = E n t (D) - \sum v = 1 V | D v | | D | E n t (D v) (3)

一般而言, 信息增益越大, 则意味着使用属性a来进行划分所获得的 “纯度提升” 越大. 因此, 我们可用信息增益来选择决策树的划分属性. 不断地寻找下式中的参属性a, 递归地建树.

arg max a G a i n (D, a) (4)

2.3 信息增益比

G a i n_r a t i o (D, a) = G a i n (D, a) E n t a (D) (5)

Enta(D)=−∑Vv=1|Dv||D|log2|Dv||D|, 表示集合中样本只依据a属性来分类时的熵.

3.算法步骤

依照不同的方法来找划分属性, 就有了不同的决策树学习算法. 但主流程是一样的:

从根节点开始, 按照某种方法得到最佳划分属性, 由该属性的不同取值建立孩子节点, 对应划分后的不同子
集.

把孩子节点当作树根, 递归地重复上述方法, 就能得到最终的决策树.

3.1 ID3

以信息增益为准则来选择划分属性.

3.2 C4.5

以信息增益为准则来选择划分属性, 存在偏向于选择取值较多的特征的问题. 使用信息增益比可以对这一问题进行纠正.

3.3 CART

二叉树.

分类-决策树