[Machine Learning]机器学习算法的R语言实现：决策树算法

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

决策树的R语言实现如下：

1. library(plyr)
   
2. 
   
3. # 测试数据集 http://archive.ics.uci.edu/ml/datasets/Car+Evaluation
   
4. 
   
5. ##计算训练集合D的熵H（D）
   
6. ##输入：trainData 训练集，类型为数据框
   
7. ##      nClass 指明训练集中第nClass列为分类结果
   
8. ##输出：训练集的熵
   
9. cal_HD <- function(trainData, nClass){
   
10.   if ( !(is.data.frame(trainData) & is.numeric(nClass)) )
    
11.     "input error"
    
12.   if (length(trainData) < nClass)
    
13.     "nClass is larger than the length of trainData"
    
14.   
    
15.   rownum <- nrow(trainData)
    
16.   #对第nClass列的值统计频数
    
17.   calss.freq <- count(trainData,nClass)
    
18.   
    
19.   #计算每个取值的  概率*log2(概率)
    
20.   calss.freq <- mutate(calss.freq, freq2 = (freq / rownum)*log2(freq / rownum))
    
21.   
    
22.   -sum(calss.freq[,"freq2"])
    
23.   
    
24.   #使用arrange代替order，方便的按照多列对数据框进行排序
    
25.   #mtcars.new2 <- arrange(mtcars, cyl, vs, gear)
    
26. }
    
27. 
    
28. #cal_HD(mtcars,11)
    
29. 
    
30. ##计算训练集合D对特征值A的条件熵H（D|A）
    
31. ##输入：trainData 训练集，类型为数据框
    
32. ##      nClass 指明训练集中第nClass列为分类结果
    
33. ##      nA 指明trainData中条件A的列号
    
34. ##输出：训练集trainData对特征A的条件熵
    
35. cal_HDA <- function(trainData, nClass, nA){
    
36.   rownum <- nrow(trainData)
    
37.   
    
38.   #对第nA列的特征A计算频数
    
39.   nA.freq <- count(trainData,nA)
    
40.   i <- 1
    
41.   sub.hd <- c()
    
42.   for (nA.value in nA.freq[,1]){
    
43.     #取特征值A取值为na.value的子集
    
44.     sub.trainData <- trainData[which(trainData[,nA] == nA.value),]
    
45.    
    
46.     sub.hd[i] <- cal_HD(sub.trainData,nClass)
    
47.     i <- i+1
    
48.   }
    
49.   
    
50.   nA.freq <- mutate(nA.freq, freq2 = (freq / rownum)*sub.hd)
    
51.   sum(nA.freq[,"freq2"])
    
52. }
    
53. 
    
54. ##计算训练集合D对特征值A的信息增益g(D,A)
    
55. ##输入：trainData 训练集，类型为数据框
    
56. ##      nClass 指明训练集中第nClass列为分类结果
    
57. ##      nA 指明trainData中特征A的列号
    
58. ##输出：训练集trainData对特征A的信息增益
    
59. g_DA <- function(trainData, nClass, nA){
    
60.   cal_HD(trainData, nClass) - cal_HDA(trainData, nClass, nA)
    
61. }
    
62. 
    
63. ##根据训练集合生成决策树
    
64. ##输入：trainData 训练集，类型为数据框
    
65. ##      strRoot 指明根节点的属性名称
    
66. ##      strRootAttri 指明根节点的属性取值
    
67. ##      nClass 指明训练集中第nClass列为分类结果
    
68. ##      cAttri 向量，表示当前可用的特征集合，用列号表示
    
69. ##      e 如果特征的最大信息增益小于e，则剩余作为一个分类，类频数最高的最为分类结果
    
70. ##输出：决策树T
    
71. gen_decision_tree <- function(trainData, strRoot, strRootAttri, nClass, cAttri, e){
    
72.   # 树的描述，（上级节点名称、上级节点属性值、自己节点名称，自己节点的取值）
    
73.   decision_tree <- data.frame()
    
74.   
    
75.   nClass.freq <- count(trainData,nClass)   ##类别出现的频数
    
76.   nClass.freq <- arrange(nClass.freq, desc(freq))  ##按频数从低到高排列
    
77.   col.name <- names(trainData) ##trainData的列名
    
78.   
    
79.   ##1、如果D中所有属于同一类Ck，则T为单节点树  
    
80.   if nrow(nClass.freq) == 1{
    
81.     rbind(decision_tree, c(strRoot, strRootAttri, nClass.freq[1,1], ''))
    
82.     return decision_tree
    
83.   }
    
84.   
    
85.   ##2、如果属性cAttri为空，将D中频数最高的类别返回
    
86.   if length(cAttri) == 0{
    
87.     rbind(decision_tree, c(strRoot, strRootAttri, nClass.freq[1,1], ''))
    
88.     return decision_tree
    
89.   }
    
90.   
    
91.   ##3、计算cAttri中各特征值对D的信息增益，选择信息增益最大的特征值Ag及其信息增益
    
92.   maxDA <- 0    #记录最大的信息增益
    
93.   maxAttriName <- ''   #记录最大信息增益对应的属性名称
    
94.   maxAttriIndex <- ''   #记录最大信息增益对应的属性列号
    
95.   
    
96.   for(i in cAttri){
    
97.     curDA <- g_DA(trainData,nClass,i)
    
98.     if (maxDA <= curDA){
    
99.       maxDA <- curDA
    
100.       maxAttriName <- col.name[i]
     
101.     }
     
102.   }
     
103.   
     
104.   ##4、如果最大信息增益小于阈值e，将D中频数最高的类别返回
     
105.   if (maxDA < e){
     
106.     rbind(decision_tree, c(strRoot, strRootAttri, nClass.freq[1,1], ''))
     
107.     return decision_tree
     
108.   }
     
109.   
     
110.   ##5、否则，对Ag的每一可能值ai，依Ag=ai将D分割为若干非空子集Di
     
111.   ##   将Di中实例数最大的类作为标记，构建子节点
     
112.   ##   由节点及其子节点构成树T，返回T
     
113.   for (oneValue in unique(trainData[,maxAttriName])){
     
114.     sub.train <- trainData[which(trainData[,maxAttriName] == oneValue),]  #Di
     
115.     #sub.trian.freq <- count(sub.train,nClass)   ##类别出现的频数
     
116.     #sub.trian.freq <- arrange(sub.trian.freq, desc(freq))  ##按频数从低到高排列
     
117.    
     
118.     rbind(decision_tree, c(strRoot, strRootAttri, maxAttriName , oneValue))
     
119.    
     
120.     ##6、递归构建下一步
     
121.     # 剔除已经使用的属性
     
122.     next.cAttri <- cAttri[which(cAttri !=maxAttriIndex)]
     
123.     # 递归调用
     
124.     next.dt <-gen_decision_tree(sub.train, maxAttriName,
     
125.                                 oneValue, nClass, next.cAttri, e)
     
126.     rbind(decision_tree, next.dt)
     
127.   }
     
128.   
     
129.   names(decision_tree) <- c('preName','preValue','curName','curValue')
     
130.   decision_tree
     
131. }

复制代码

决策树总结
1、R中有实现决策树算法的包rpart，和画出决策树的包rpart.plot，本例自己实现决策树算法是为了更好的理解。
2、由于决策树只能处理离散属性，因此连续属性应首先进行离散化。
3、决策树易于理解，对业务的解释性较强。
4、ID3算法容易引起过拟合，需考虑树的剪枝。

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏5 回帖

关键词：Learning earning machine 机器学习算法 Learn library

Lisrelchen 发表于 2014-7-11 23:55
决策树的R语言实现如下：

很好

get√
谢楼主

andyyuan1988 发表于 2015-3-20 10:58
get√
谢楼主

学习了，谢谢楼主

非常感谢