# R语言与机器学习（分类算法）决策树算法

## 决策树的构建

### 一、KD3的想法与实现

1、 计算给定数据集的熵

[plain] view plaincopyprint

1. calcent<-function(data){
2. nument<-length(data[,1])
3. key<-rep("a",nument)
4. for(i in 1:nument)
5. key[i]<-data[i,length(data)]
6. ent<-0
7. prob<-table(key)/nument
8. for(i in 1:length(prob))
9. ent=ent-prob[i]*log(prob[i],2)
10. return(ent)
11. }

> 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

2、 按照给定特征划分数据集

R代码：

[plain] view plaincopyprint?

1. split<-function(data,variable,value){
2. result<-data.frame()
3. for(i in 1:length(data[,1])){
4. if(data[i,variable]==value)
5. result<-rbind(result,data[i,-variable])
6. }
7. return(result)
8. }

> 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、选择最佳划分（基于熵增益）

[plain] view plaincopyprint?

1. choose<-function(data){
2. numvariable<-length(data[1,])-1
3. baseent<-calcent(data)
4. bestinfogain<-0
5. bestvariable<-0
6. infogain<-0
7. featlist<-c()
8. uniquevals<-c()
9. for(i in1:numvariable){
10. featlist<-data[,i]
11. uniquevals<-unique(featlist)
12. newent<-0
13. for(jin 1:length(uniquevals)){
14. subset<-split(data,i,uniquevals[j])
15. prob<-length(subset[,1])/length(data[,1])
16. newent<-newent+prob*calcent(subset)
17. }
18. infogain<-baseent-newent
19. if(infogain>bestinfogain){
20. bestinfogain<-infogain
21. bestvariable<-i
22. }
23. }
24. return(bestvariable)
25. }

> choose(mudat)

[1] 1

4、 递归构建决策树

>choose(animals)

[1] 1

>choose(animals)

[1] 4

[plain] view plaincopyprint

1. bulidtree<-function(data){
2. if(choose(data)==0)
3. print("finish")
4. else{
5. print(choose(data))
6. level<-unique(data[,choose(data)])
7. if(level==1)
8. print("finish")
9. else
10. for(i in1:length(level)){
11. data1<-split(data,choose(data),level[i])
12. if(length(data1)==1)print("finish")
13. else
14. bulidtree(data1)
15. }
16. }
17. }

>bulidtree(lenses)

[1] 4

[1]"finish"

[1] 3

[1] 1

[1]"finish"

[1]"finish"

[1] 1

[1]"finish"

[1]"finish"

[1] 2

[1]"finish"

[1] 1

[1]"finish"

[1]"finish"

[1]"finish"

### 二、C4.5算法

C4.5算法描述 ：

（1） 创建根节点N;

（2） IF T都属于同一类C，则返回N为叶节点，标记为类C；

（3） IF T_attributelist为空或T中所剩的样本数少于某给定值则返回N为叶节点，标记为T中出现最多的类；

（4） FOR each T_attributelist中的属性计算信息增益率information gain ratio;

（5） N的测试属性test_attribute=T_attributelist中具有最高信息增益率的属性；

（6） IF测试属性为连续型则找到该属性的分割阀值；

（7） FOR each 由节点N长出的新叶节点{

IF 该叶节点对应的样本子集T’为空

ELSE在该叶节点上执行C4.5formtree(T’,T’_attributelist),对它继续分裂；

}

(8) 计算每个节点的分类错误，进行树剪枝。

setosa 50 0 0

versicolor 0 49 1

virginica 0 2 48

hard no lenses soft

hard 3 1 0

no lenses 0 14 1

soft 0 0 5

（注：图片与预测表输出结果是已经经过剪枝的，所以可能和我们之前程序算出的有些不同）

Give.Birth = no | Live.in.Water = no | | Can.Fly = no: reptiles (4.0/1.0) | | Can.Fly = yes: birds (3.0) | Live.in.Water = sometimes: amphibians (4.0/2.0) | Live.in.Water = yes: fishes (2.0) Give.Birth = yes: mammals (7.0/1.0) 这个分类与我们之前使用ID3分类得到的结果有所不同（搜索效率高了一些，准确率相当），使用信息增益倾向于多分类的贪心算法导致的不足在这里显示的淋漓尽致，更可以看出C4.5比ID3改进的地方绝不止能处理连续变量这一条。

### 三、 CART算法

CART算法描述

（1） 创建根节点N;

（2） 为N分配类别；

（3） IF T都属于同一类别OR T中只剩一个样本

（4） FOR each T_attributelist 中的属性

（5） N的测试属性test_attribute=T_attributelist中具有最小GINI系数的属性；

（6） 划分T得T1、T2两个子集；

（7） 调用cartformtree(T1);

（8） 调用cartformtree(T2)；

`J48(formula, data, subset, na.action,`
`    control = Weka_control(), options = NULL)`
`tree(formula, data, weights, subset,`
`     na.action = na.pass, control = tree.control(nobs, ...),`
`     method = "recursive.partition",`
`     split = c("deviance", "gini"),`
`     model = FALSE, x = FALSE, y = TRUE, wts = TRUE, ...)`

split为划分指标，分为deviance（偏差）和”gini”（基尼）

control涉及树剪枝的各种凶残细节，有兴趣的可以通过阅读帮助文档解决。而且剪枝是一个十分复杂的过程，剪枝也是视需求而定的，C4.5是事后剪枝，id3也就是我们试图实现的建树，也可以去手动剪枝。

### 四、R内置命令实现

[plain] view plaincopyprint

1. library(RWeka)
2. library(party)
3. oldpar=par(mar=c(3,3,1.5,1),mgp=c(1.5,0.5,0),cex=0.3)
4. data(iris)
5. m1<-J48(Species~Petal.Width+Petal.Length,data=iris)
6. m1
7. table(iris\$Species,predict(m1))
8. write_to_dot(m1)
9. if(require("party",quietly=TRUE))
10. plot(m1)

[plain] view plaincopyprint

2. m1<-J48(V5~.,data=lenses)
3. m1
4. table(lenses\$V5,predict(m1))
5. write_to_dot(m1)
6. if(require("party",quietly=TRUE))
7. plot(m1)

CART算法的鸢尾花例：

[plain] view plaincopyprint

1. library(tree)
2. oldpar=par(mar=c(3,3,1.5,1),mgp=c(1.5,0.5,0),cex=1.2)
3. ir.tr <- tree(Species~Petal.Width+Petal.Length, iris)
4. ir.tr
5. plot(ir.tr)
6. text(ir.tr)

0 条评论

• ### 使用Python绘制点击图、热图

via: http://blog.csdn.net/wenyusuran/article pyHeatMap是一个使用Python生成热图的库，基本代码是我一年...

• ### 使用sklearn自带的贝叶斯分类器进行文本分类和参数调优

Part 1: 本篇内容简介 在前一篇文章完整手写一个朴素贝叶斯分类器，完成文本分类，我们使用首先假设在文档中出现的单词彼此独立，利用贝叶斯定理，完成了一个简...

• ### 机器学习算法-决策树C4.5练习

决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应...

• ### 【学习】R语言与机器学习学习笔记（2）决策树算法

算法二：决策树算法 决策树定义 首先，我们来谈谈什么是决策树。我们还是以鸢尾花为例子来说明这个问题。 观察上图，我们判决鸢尾花的思...

• ### R中t()转置后为什么会变成字符型数据

数值型数据全部变成了字符型，怎么回事？其实是因为cluster那一列数据并不是数值型，而是字符型。因为这一列代表某一群细胞，如cluster0.所以才会出现这个...

• ### React项目配置3(如何管理项目API接口)

本教程总共6篇,每日更新一篇,请关注我们!你可以进入历史消息查看以往文章,也敬请期待我们的新文章! 1、React项目配置1(如何管理项目公共js方法)---...

• ### 消失的魔术：隐藏在js引用和原型链背后的超级能力

js这门语言有很多诟病，然而很多被无视的点，构成了js最为美妙的语言特性。这篇文章将带你走进魔术般的引用型数据类型和原型链背后，寻找那些被遗忘的超能力。并且，基...

• ### rxjs operator学习笔记

operator就是函数式编程世界里的一等公民，接收一个Observable作为输入，返回另一个新的Observable对象。

• ### 太强了，竟然可以根据指纹图像预测性别！

在进入神经网络世界之前，让我们先谈一谈指纹？众所周知，没有两个人具有相同的指纹，但是我们可以建立一个CNN模型来从指纹图像中预测性别吗？让我们看看……

• ### python在webservice接口测

本次拿免费的互联网国内手机号码归属地查询WEB服务webservice接口做例子，当然有很多免费webservice接口可以供大家使用，百度一下就有N多...