决策树是有监督学习算法中的一种。基于属性做一系列的决策,每次决策要么进入下一级决策,要么生成最终结果。决策树可以作为集成算法中的基分类器,并且有最为广泛的应用。
决策树算法
要想理解决策树的工作原理,首先需要了解决策树的层次结构。决策树由结点与有向边组成,其中,结点分为如下三种:
每个叶节点都有一个类标号,根节点和内部结点包含属性测试条件,每个根节点和内部结点都对应一次条件判断,用来分开有不同特性的记录。对一条记录进行判断时,从根结点开始,根据判断进入相应分支,只到叶节点,叶节点的类别即为分类结果。比如,根据历史贷款记录预测贷款申请者是否会逾期,是否有房和婚姻状况作为属性,是否逾期作为类标号。历史数据如下:
序号 | 有房 | 婚姻状况 | 是否逾期 |
---|---|---|---|
1 | 是 | 单身 | 否 |
2 | 否 | 已婚 | 否 |
3 | 否 | 单身 | 是 |
4 | 是 | 已婚 | 否 |
5 | 否 | 离异 | 是 |
6 | 否 | 已婚 | 否 |
7 | 是 | 离异 | 否 |
8 | 否 | 单身 | 是 |
9 | 否 | 已婚 | 否 |
根据历史贷款记录,可构造如下决策树:
当决策树构造好后,对未标记的记录进行分类就非常容易了。如使用以及构造好的决策树,对如下序号8这个人进行预测,可以知道,最终停在了未逾期这个节点。
序号 | 有房 | 婚姻状况 | 是否逾期 |
---|---|---|---|
8 | 是 | 离异 | ? |
Hunt算法是常用的用来建立决策树的算法,采用贪心策略,在选择划分数据属性时,采取一系列局部最优决策来构造决策树。他是C4.5,CART等决策树算法的基础。
Hunt算法流程
step1
Dt=与结点t相关联的训练记录集;
Y=类标号向量;
step2
if Dt中所有记录都属于同一个类Yt,则t为叶结点,并用Yt标注。
else if Dt中包含多个类记录,选一个属性测试条件,将记录分为更小的子集。对于测试条件的每个输出,创建一个子结点,并根据测试结果将Dt中记录分布到相应结点,对每个结点,递归调用此算法
R语言实现
通过R语言中的rpart包,对iris数据集进行分类。rpart包的处理方式:首先对所有自变量和所有分割点进行评估,最佳的选择是使分割后组内的数据更为“一致”(pure)。这里的“一致”是指组内数据的因变量取值变异较小。rpart包对这种“一致”性的默认度量是Gini值。确定停止划分的参数有很多(参见rpart.control),确定这些参数是非常重要而微妙的,因为划分越细,模型越复杂,越容易出现过度拟合的情况,而划分过粗,又会出现拟合不足。处理这个问题通常是使用“剪枝”(prune)方法。即先建立一个划分较细较为复杂的树模型,再根据交叉检验(Cross-Validation)的方法来估计不同“剪枝”条件下,各模型的误差,选择误差最小的树模型。(来源:百度)maptree包可以画出生成的决策树图,便于直观的对模型进行解释。
formular<-Species~Sepal.Length+Sepal.Width+Petal.Length+Petal.Width
fit<-rpart(formular, method = 'class', data = iris)
print(fit)
draw.tree(fit)
由图中结果,可以观察生成决策树的具体结构图,一般来说,处于越高层级的测试条件,有越高的重要性。因此,在进行特征选择时,可根据决策树的结果协助判断,这个特点也增加了决策树的可解释性。
#观察误差
printcp(fit)
#调用CP(complexity parameter)与xerror的相关图
plotcp(fit)
#用prune命令对树进行修剪
pfit<-prune(fit, cp = fit$cptable[which.min(fit$cptable[,"xerror"]),"CP"])
本例比较简单,因此剪枝后模型没有改变,当遇到复杂模型时,读者可根据相应情况观察前后结果变化。
特点
1,不需要先验假设,不需要属性和类服从一定的分布。
2,非线性分类边界。
3,对噪声有较好的鲁棒性。
4,有较好的解释性。