决策树

决策树是一种常见的机器学习算法.
所谓决策树,其实就是通过某种方法选择特征的筛选顺序,然后对每一个特征进行分分支,也就相当于将每个特征都做成if-else语句.
简单的说,决策树就是多个if-else组合在一起,只是哪一个特征先进行if-else由我们的判定方法决定,而常见的判定方法有: 信息增益, 增益率, 基尼指数
在我们使用代码实现决策树的时候,其实就是一个递归过程.下面请看西瓜书的决策树伪代码:


输入: 训练集 D={(x_1, y_1), (x_2, y_2),...,(x_m, y_m)}
    属性集 A={a_1, a_2,...,a_m} 过程: 函数TreeGenerate(D,A)
   生成结点node;
if D中样本全属于同一类别别C then
    将node标记为C类叶结点; then
end if
if A\neq\varnothing OR D中样本数在A上取值相同 then
   从A中选择最优划分属性a_*;
for a_*的每一个值a_*^v do
   为node生成一个分支;令D中样本最多的类;return
end if
A中选择最优划分属性a_*;
for a_*的每一个值a_* do
   为node生成一个分支;令D_v表示Da_*上取值为a_*^v的样本子集;    if D_v为空 then
      将分支结点标记为叶结点,其类别标记为D中样本最多的类;return
   else       以TreeGenerate(D_v,A\{a_*})为分支结点
   end if
end for


信息熵

信息熵(information entropy)是度量样本集合纯度最常用的一种指标.
假设当前样本集D中第k类样本所占比例为p_k(k=1,2,3,...,n),则D的信息熵为:

Ent(D)=-\sum_{k=1}^{n}p_k\log_2p_k

Ent(D)的值越小,则D的纯度越高

ID3

决策树的ID3算法就是以信息增益为判定方法的.
信息增益就是属性a对样本集D进行划分所获得的:

Gain(D,a)=Ent(D)-\sum^V_{v=1}\frac{|D^v|}{|D|}Ent(D^v)

一般而言,信息增益越大,则意味着使用属性a来进行划分所获得的纯度提升越大.
在进行划分时,我们就需要选择信息增益最大的特征来进行处理.

C4.5

C4.5与ID3的区别就在与其使用的是增益率(Ggain ratio)
由于信息增益准则对可取值树木较多的属性有所偏好,所以我们需要引入增益率:

Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)},其中IV(a)=-\sum^V_{v=1}\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}

IV(a)称为属性a固有值,属性a的可能取值数目越多,则IV(a)的值通常越大,所以可以解决我们上述问题.

CRAT

CART所使用的就不再是信息熵,而是使用基尼指数来进行划分.
由于信息熵的计算有大量的耗时的熵模型,因此我们引入了悉尼指数代替熵模型
数据集D的悉尼值为:

Gini(D)=\sum^{|y|}_{k=1}\sum_{k'\neq k}p_kp'_k=1-\sum^{|y|}_{k=1}p^2_k

直观的说,Gini(D)反映了从数据集D中随机抽取两个样本,其类别标记不一致的概率.因此,Gini(D)越小,则数据集D的纯度越高.
属性a的基尼指数为:

Gini\_index(D,a)=\sum^V_{v=1}\frac{|D^v|}{|D|}Gini(D^v)

我们需要选择那个使划分后基尼系数最小的属性,即a_*=\arg \min_{a\in A} Gini_index(D,a)

文章目录