# 算法二：决策树算法

## 决策树的构建

### 一、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)

# 预告

• 算法三：朴素贝叶斯算法
• 算法四：支持向量机
• 算法五：神经网络
• 算法六：logistic回归

（to be continue）

0 条评论

• ### 【学习】笨办法学R编程（三）

看到各位对“笨办法系列”的东西还比较感兴趣，我也很乐意继续写下去。今天的示例将会用到数据框（data.frame）这种数据类型，并学习如何组合计算...

• ### 从0到1掌握R语言网络爬虫

引言 网上的数据和信息无穷无尽，如今人人都用百度谷歌来作为获取知识，了解新鲜事物的首要信息源。所有的这些网上的信息都是直接可得的，而为了满足日益增长的数据需求，...

• ### 工具 | 一张图，教你用25种可视化工具如何完成

散点图真是一个比较神奇的图形，正如它的名字一样，一堆纷乱如麻的圆点，看似无迹可寻却能显示出数据难以显示的内在逻辑关系。很多人称它“万表之王”，它在数据分析师手...

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

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

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

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

• ### 使用sklearn随机森林算法实现手写数字识别

随机森林（random forest）是2001年提出来同时支持数据的回归与分类预测算法，在具体了解随机森林算法之前，首先看一下决策树算法（Decision T...

决策树（Decision Tree）又称为分类树（Classification Tree），是最为广泛的归纳推理算法之一，处理类别型或连续型变量...

• ### rxjs of操作符传入数组的单步执行

Observable构造函数接收一个函数作为subscribe的回调函数。我们这个例子，subscribe回调函数通过subscribeToArray构造：

• ### 机器学习实战教程（三）：决策树实战篇之为自己配个隐形眼镜

原文链接：https://cuijiahua.com/blog/2017/11/ml_3_decision_tree_2.html