决策树(Decision Tree)学习笔记(二)

上一篇博文介绍了决策树的基本概念,对决策树相关的五个问题进行了解答。这篇博文将介绍常见的ID3、C4.5和CART算法,并介绍sklearn中的决策树算法。

ID3算法

ID3算法可以处理基本的情况——离散的属性,没有遗漏的信息等。将信息增益作为质量测量的指标。

1)决定分类属性

2)对目前的数据表,建立一个节点N。

3)如果数据表中的数据都属于同一类,N就是树叶,在树叶上标上所属的那一类。

4)如果数据表中没有其他属性可以考虑,N也是树叶,按照少数服从多数的原则在树叶上标上所属类别。

5)否则,根据平均信息期望值E或Gain值选出一个最佳属性作为节点N的测试属性。

6)节点属性选定以后,对于该属性的每一个值:

     w从N生成一个分支, 并将数据表中与该分支有关的数据收集形成分支节点的数据表,在表中删除节点属性那一栏。

     w如果分支数据表非空,则运用以上算法从该节点建立子树。

C4.5算法

C4.5算法是ID3算法的一个扩展,它继承了ID3算法的优点,同时在以下方面做了改进:

1)用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足(信息增益率详见上一节
2)在树构造过程中进行剪枝
3)能够完成对连续属性的离散化处理
4)能够对不完整数据进行处理

相比于称它作算法,把它称作一套决策树的规则更为合适。

C4.5算法也可以选择运用另一种指标--Gini指标。

具体算法思想:假设某节点v处的数据样本集合Sv包含c个类别的记录,其中,pi为类别i在节点v处的概率那么Gini指标定义为:

\(Gini\left( \nu _i \right) =1-\sum_{i=1}^c{p_i^2}\)

如果集合分成l个部分,那么关于分割V 的平均Gini指标定义为:

\(Gini\left( V \right) =\sum_{k=1}^l{\frac{n_i}{n}}Gini\left( v_i \right)\)

具有最低基尼指数的属性是最好的属性。

Wind(Strong) Wind(Weak)
Play(Yes)  3 6
Play(No) 3 2

\(Gini\left( wind/strong \right) =1-\left( 3/6 \right) ^2-\left( 3/6 \right) ^2=0.5\)

\(Gini\left( wind/weak \right) =1-\left( 2/8 \right) ^2-\left( 6/8 \right) ^2=0.375\)

\(Gini=6/14\times 0.5+8/14\times 0.375=0.428571\)

C4.5算法有如下优点:产生的分类规则易于理解,准确率较高。其缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。此外,C4.5适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。

CART算法

是一种产生二叉决策树的技术。它有两个重要的思想:第一个,递归地划分自变量空间;第二个:用验证数据进行剪枝。

递归划分 

用Y表示因变量(分类变量),用X1,X2,…,XP表示自变量,通过递归的方式把关于X的P维空间划分为不重叠的矩形。

划分步骤

首先,选择一个自变量,例如Xi和Xi的一个值Si,若选择Si把P维空间分为两部分:一部分包含的点都满足Xi<=Si;另一部分包含的点满足Xi>Si.

其次,再把上步中得到的两部分中的一个部分,通过选择一个变量和该变量的划分值以相似的方式再划分.

重复上述步骤,直至把整个X空间划分成的每个小矩形都尽可能的是同构的.

划分点搜索准则为Gini指数。

对于连续值处理引进“分裂点”的思想,假设样本集中某个属性共n个连续值,则有n-1个分裂点,每个“分裂点”为相邻两个连续值的均值 (a[i] + a[i+1]) / 2。

用验证数据进行剪枝

CART过程中第二个关键的思想是用独立的验证数据集对根据训练集生成的树进行剪枝,生成一个具有最小错误的树。

CART用“成本复杂性”标准来剪枝,成本复杂性标准是分类树的简单误分(基于验证数据的) 加上一个对树的大小的惩罚因素。

即成本复杂性标准为Err(T)+α|L(T)|,其中:Err(T)是验证数据被树误分部分;L(T)是树T的叶节点数;α是每个节点惩罚成本, α的值大于等于0。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注