-
决策树算法
决策树定义
首先，我们来谈谈什么是
决策树。我们还是以鸢尾花为例子来说明这个问题。
观察上图，我们判决鸢尾花的思考
过程可以这么来描述：花瓣的长度小于
2.4cm
的是
setosa(
图中绿色的分类
)
，长度大于
1cm
的呢
?<
/p>
我们通过宽度来判别，宽度小于
1.8cm
的是
versicolor(
图中红色的分类
)
，其余的就是
virginica(
图中黑色的分类
)
我们用图形来形象的展示我们的思
考过程便得到了这么一棵决策树：
这种从数据产生决策树的机器学习技术叫做决策树学习
,
通俗点说就是决策树，
说白了，
这
是一种依托于分类、训练上的预测树，根据已知预测、归类未来。
前面我们介绍的
k-
近邻算法也可以完成很
多分类任务，但是他的缺点就是含义不清，说不
清数据的内在逻辑，
而决策树则很好地解决了这个问题，
他十分好理解。
从存储
的角度来说，
决策树解放了存储训练集的空间，
毕竟与一棵树的
存储空间相比，
训练集的存储需求空间太
大了。
决策树的构建
一、
KD3
的想法与实现
下面我们就要来解决一个很重要的问题：如何构造一棵决策树
?
这涉及十分有趣的细节。
先说说构造的基本步骤，一般来说
，决策树的构造主要由两个阶段组成
:
第一阶段，生成树
阶段
。
选取部分受训数据建立决策树，
决策树是按广度优先建立直到每个叶节点包括相同的
类标记为止。
第二阶段，
决策树修剪阶段
。
用剩余数据检验决策树，
如果所建立的决策树不
能正
确回答所研究的问题，
我们要对决策树进行修剪直到建立一棵正确的决策树。
这样在决
策树每个内部节点处进行属性值的比较，
在叶节点得到结论。
从根节点到叶节点的一条路径
就对应着一条
规则，整棵决策树就对应着一组表达式规则。
问题：我们如何确定起决定作用的划分变量。
我还是用鸢尾花的例子来说这个问题思考的必要性。
使用不同的思考方式，
我们不难发现下
面的决策树也是可以把鸢尾花分成
< br>3
类的。
为了找到决定性特征，
划分出最佳结果，
我们必须认真评估每个特征。
通
常划分的办法为信
息增益和基尼不纯指数，对应的算法为
C4.
5
和
CART
。
关于信息增益和熵的定义烦请参阅百度百科，这里不再赘述。
直接给出计算熵与信息增益的
R
代码：
1
、
计算给定数据集的熵
calcent<-function(data){
nument<-length(data[,1])
key<-rep(
for(i in 1:nument)
key[i]<-data[i,length(data)]
ent<-0
prob<-table(key)/nument
for(i in 1:length(prob))
ent=ent-prob[i]*log(prob[i],2)
return(ent)
}
我们这里把最后一列作为衡量熵的指标，例如数据集
mudat(
自己定义的
)
> mudat
x y z
1 1
1 y
2 1 1 y
3 1 0 n
4 0 1 n
5 0 1 n
计算熵
>
calcent(mudat)
1
0.9709506 <
/p>
熵越高，
混合的数据也越多。
得到熵之后
，
我们就可以按照获取最大信息增益的方法划分数
据集
2
、
按照给定特征划分数据集
为了简单起
见，我们仅考虑标称数据
(
对于非标称数据，我们采用划分的办
法把它们化成标
称的即可
)
。
R
代码：
split<-function(data,variable,value){
result<-()
for(i in
1:length(data[,1])){
if(data[i,variable]==value)
result<-rbind(result,data[i,-variable])
}
return(result)
}
这里要求输入的变量为：数据集，划分特征变量的序号，划分
值。我们以前面定义的
mudat
为例，以“
< br>X
”作为划分变量，划分得到的数据集为：
> split(mudat,1,1)
y z
1 1 y
2 1 y
3 0 n
> split(mudat,1,0)
y z
4 1 n
5 1 n
3
、选择最佳划分
(
基于熵增益
< br>)
choose<-function(data){
numvariable<-length(data[1,])-1
baseent<-calcent(data)
bestinfogain<-0
bestvariable<-0
infogain<-0
featlist<-c()
uniquevals<-c()
for(i
in1:numvariable){
featlist<-data[,i]
uniquevals<-unique(featlist)
newent<-0
for(jin
1:length(uniquevals)){
subset<-split(data,i,uniquevals[j])
prob<-length(subset[,1])/length(data[,1])
newent<-newent+prob*calcent(subset)
}
infogain<-baseent-newent
if(infogain>bestinfogain){
bestinfogain<-infogain
bestvariable<-i
}
}
return(bestvariable)
}
函数
choose
包含三个部分，
第一部分：
求出一个分类的各种标签<
/p>
;
第二部分：
计算每一次划
分的信息熵
;
第三部分：计算最好的信息增益，并返
回分类编号。
我们以上面的简易例子
mudat
为例，计算划分，有：
>
choose(mudat)
[1] 1
也就是告诉我们，
将第一个变量值为
1
的分一类，
变量值为
0
的分为另一类，
< br>得到的划分是
最好的。
4
、
递归构建决策树
我们以脊椎动物数据
集为例，这个例子来自《数据挖掘导论》
，具体数据集已上传至百度云
< br>盘
(
点击可下载
)
我们先忽略建树细节，由于数据变量并不大，我们手动建一棵树先。
>animals<-(
>choose(animals)
[1] 1
这里变量
1
代表
names
，当然是一个很好的分类，但是意义
就不大了，我们暂时的解决方案
是删掉名字这一栏，继续做有：
>choose(animals)
[1] 4
我们继
续重复这个步骤，直至
choose
分类为
0
或者没办法分类
(
比如
sometimes live in
water
的动物
)
为止。得到最终分类树。
给出分类逻辑图
(
遵循多数投票法
)
：
至于最后的建树画图涉及
R
的绘图包
ggplot
，这里不再给出细节。
下面我们使用著名数据集——隐形眼
镜数据集，
利用上述的想法实现一下决策树预测隐形眼
镜类型。
这个例子来自《机器学习实战》，具体数据集已上传至百度云盘
(
点击可下载
)
。
< br>下面是一个十分简陋的建树程序
(
用
R
实现的
)
，
为了叙述方便，
我们给隐形眼镜数据名称加
上标称：
age,prescript,astigmatic,tear rate.
建树的
R
程序简要给出如下：
bulidtree<-function(data){
if(choose(data)==0)
print(
else{
print(choose(data))
level<-unique(data[,choose(data)])
if(level==1)
print(
else
for(i
in1:length(level)){
data1<-split(data,c
hoose(data),level[i])