1.决策树简介

决策树的特点：

• 既可以处理分类问题，也可以处理回归问题
• 对于缺失值数据也能比较好的处理
• 高度可解释

决策树的思想：

• 从树根开始把分类任务按顺序分解成一个个选择

• 在优化和搜索的过程中，决策树用贪婪的启发式算法，评估当前学习阶段的最优选项

决策树的生成分如下几步：
1）节点的分裂：一般当一个节点所代表的属性无法给出判断时，将这一个节点分裂成若干个子节点；
2）阈值的确定：选择适当的阈值使得分类错误率最小。
3）深度的确定
4 ）最终预测值的算法确定

2.熵

按照一般说法，熵就是混沌状态的一种度量。熵越大，表示越混沌。所谓的增熵原理，就是说宇宙中的事物都有自发变得更混乱的倾向，也就是说熵会不断增加。

信息熵（Entropy）
信息量是对信息的度量。越小概率的事情发生了产生的信息量越大，如湖南产生的地震了；越大概率的事情发生了产生的信息量越小，如太阳从东边升起来了。

3.CART 决策树算法

CART（Classification and Regression Tree ），分类和回归树

CART回归树

CART作为回归树时，用SSE来进行度量划分节点的优劣，采用叶子节点的均值或者中位数来预测输出结果。具体来说，度量目标是对于划分特征A，对应划分点s两边的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小。

#给定一个分类点，将数据分为两类，分别计算这两类的均方差
compute_SSE_split <- function(v, y, split_point) {
  index<-v<split_point #index是false或者true，也可以认为是0和1
  y1<-y[index] #取出来所有为true对应的y值
  y2<-y[!index] #取出所有为fasle对应的y值
  SSE<-sum((y1-mean(y1))^2) + sum((y2-mean(y2))^2) #计算两堆数的方差
  return(SSE)
}

#给定一个向量v和一个y值，把向量v按照里面的每个元素进行分类，将数据分为两类，分别计算这两类数据的均方差
compute_all_SSE_splits <- function(v, y) {
  sapply(unique(v), function(sp) compute_SSE_split(v,y,sp))
}

set.seed(99)
#生成20个0,1,1次试验,概率0.5
x1<-rbinom(20,1,0.5) 
set.seed(100)
#生产20个均值为5，标准差也为5的随机数，加上10后，四舍五入，保留两位小数
x2<-round(10+rnorm(20,5,5),2) 
set.seed(101)
#生成y
y<-round((1+(x2*2/5)+x1-rnorm(20,0,3)),2)
rcart_df<-data.frame(x1,x2,y)
rcart_df

#对特征1计算所有的方差。因为x1只有0和1两个数，因此只会有2个结果。其中小于0并不能进行区分，其实是有一个结果有效。
x1splits<-compute_all_SSE_splits(x1,y)
#对特征2计算所有的方差。特征2是离散值，有多少个不同的特征，就会有多少个不同的结果。当然，对于最小的特征，其最终得到的sse也是无用的。
x2splits<-compute_all_SSE_splits(x2,y)

#画图
p1 <- ggplot(data = NULL, aes(x = unique(x1), y = x1splits)) + 
  geom_point(shape=4) + 
  ggtitle("SSE values for Splits on Feature x1") + 
  theme(plot.title = element_text(lineheight=.8, face="bold", vjust=2), legend.position="bottom") +
  xlab("x1") + 
  ylab("SSE") + 
  coord_cartesian(xlim = c(-0.1,1.1), ylim = c(225,235)) + 
  annotate("text", x = unique(x1), y = x1splits, label = round(x1splits,2), vjust = -1, hjust = 1, size = 3)
p1

p2 <- ggplot(data = NULL, aes(x = unique(x2), y = x2splits)) + 
  geom_point(shape=4) + 
  ggtitle("SSE values for Splits on Feature x2") + 
  theme(plot.title = element_text(lineheight=.8, face="bold", vjust=2), legend.position="bottom") +
  xlab("x2") + 
  ylab("SSE") + 
  coord_cartesian(xlim = c(10,30), ylim = c(110,250)) +
  annotate("text", x = unique(x2), y = x2splits, label = round(x2splits,2), vjust = -1, hjust = 1, size = 3)
p2

我们发现，最佳的分裂方式是124.05的SSE，所以我们的回归树就一个节点If x2<18.7。

CART分类树
作为分类树时，用基尼系数来进行度量划分节点的优劣，且预测结果采用叶子节点里概率最大的类别作为当前节点的预测类别。

目的：预测抵达某个节点，更有信心能预测类别

• 按照在叶节点的数据点集合进行分类，让该类纯度更大
• 节点纯度的衡量指标

• 基尼系数（Gini index）
  基尼系数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。这和信息增益（比）相反。
  

  假设K个类别，第k个类别的概率为pk，概率分布的基尼系数表达式为：
  
  如果是二分类问题，第一个样本输出概率为p，概率分布的基尼系数表达式为：
  
  

  CART采用的是不停的二分。会考虑把特征A分成{A1}和{A2,A3}、{A2}和{A1,A3}、{A3}和{A1,A2}三种情况，找到基尼系数最小的组合。

分类树与回归树的区别在样本的输出，如果样本输出是离散值，这是分类树；样本输出是连续值，这是回归树。

用基尼系数或者熵来代替SSE

#定义尼基系数函数
gini_index <- function(v) {
  t <- table(v)
  probs <- t / sum(t)
  terms <- sapply(probs,function(p) p*(1-p) )
  return(sum(terms))
}

#基尼系数越小，不纯度越低，特征越好
gini_index(v=c(0,0,0,1,1,1))
gini_index(v=c(0,0,0,1,1,1,1,1,1))
gini_index(v=c(0,0,0,1,1,1,2,2,2))
gini_index(v=c(1,1,1,1,1,1))

#二分类基尼系数
gini_binary <- function(p) {
  return(2 * p * (1 - p))
}
#二分类熵
entropy_binary <- function(p) {
  return(-(p*log2(p) + (1-p)*log2(1-p)))
}


x <- seq(0,1,length=10000)
gini <- gini_binary(x)
entropy <- entropy_binary(x)

#画图
p <- ggplot()+ 
  geom_line(data = NULL, aes(x = x, y = gini, lty = "Gini Index"))+
  geom_line(data = NULL, aes(x = x, y = entropy, lty = "Entropy"))+
  ggtitle("Splitting Criteria for Binary Classification")+
  theme(plot.title = element_text(lineheight=.8, face="bold", vjust=2),
               legend.position="bottom")+
  xlab("Probability of Class 1")+
  ylab("Splitting Criterion")+
  scale_linetype_discrete(name = "Splitting Criterion")+
  coord_cartesian(xlim = c(0,1), ylim = c(0,1))
p

4.总结及R的实现

• 预测特定的纸币是真实的还是伪造

#读取数据
bnote <- read.csv("data_banknote_authentication.txt", header=FALSE)
names(bnote) <- c("waveletVar", "waveletSkew", 
                  "waveletCurt", "entropy", "class")
bnote$class <- factor(bnote$class)

#划分测试集和训练集
library(caret)
set.seed(266)
bnote_sampling_vector <- createDataPartition(bnote$class, 
                                             p = 0.80, list = FALSE)
bnote_train <- bnote[bnote_sampling_vector,]
bnote_test <- bnote[-bnote_sampling_vector,]

#使用C50算法构建决策树
library(C50)
bnote_tree <- C5.0(class~.,data=bnote_train)

#在测试集上进行预测
bnote_predictions <- predict(bnote_tree,bnote_test)
mean(bnote_test$class == bnote_predictions) #在测试集上进行预测

summary(bnote_tree)
plot(bnote_tree)

2）rpart包用法

rpart包常用参数如下：

#预测星际争霸的比赛
skillcraft <- read.csv("SkillCraft1_Dataset.csv")
#去掉GameId，因为不是特征量，对分类无用
skillcraft<-skillcraft[-1]
skillcraft$TotalHours=as.numeric(skillcraft$TotalHours)
skillcraft$HoursPerWeek=as.numeric(skillcraft$HoursPerWeek)
skillcraft$Age=as.numeric(skillcraft$Age)

#划分测试集和训练集
library(caret)
set.seed(133)
skillcraft_sampling_vector <- createDataPartition(skillcraft$LeagueIndex, p = 0.80, list = FALSE)
skillcraft_train <- skillcraft[skillcraft_sampling_vector,]
skillcraft_test <- skillcraft[-skillcraft_sampling_vector,]

#使用rpart进行决策树分类
library(rpart)
regtree <- rpart(LeagueIndex~., data=skillcraft_train)

par(mar=c(2,1,1,1))
plot(regtree, uniform=TRUE, main="Regression Tree for Skillcraft Data Set")
#text(regtree, use.n=FALSE, all=TRUE, cex=.8)

#计算SSE
compute_SSE <- function(correct,predictions) {
  return(sum((correct-predictions)^2))
}

#计算SSE
regtree_predictions = predict(regtree, skillcraft_test)
(regtree_SSE <- compute_SSE(regtree_predictions, skillcraft_test$LeagueIndex))

#minsplit指定父节点和子节点中所包含的最少样本量,是最小分支节点数，这里指大于等于20，那么该节点会继续分划下去，否则停止
#minbucket：叶子节点最小样本数
#cp 复杂程度.用于控制树的复杂度，指某个点的复杂度，对每一步拆分,模型的拟合优度必须提高的程度。值越低，复杂度越高，默认为0.01；
#maxdepth 最大10层
#xval指定交叉验证的次数
regtree.random <- rpart(LeagueIndex~., data=skillcraft_train, 
                        control=rpart.control(minsplit=20, cp=0.001, maxdepth=10))
regtree.random_predictions = predict(regtree.random, skillcraft_test)
(regtree.random_SSE <- compute_SSE(regtree.random_predictions, 
                                   skillcraft_test$LeagueIndex))

#调参
library(e1071)
rpart.ranges<-list(minsplit=seq(5,50,by=5), 
                   cp=c(0,0.001,0.002,0.005,0.01,0.02,0.05,0.1,0.2,0.5), maxdepth=1:10)
(regtree.tune<-tune(rpart,LeagueIndex~., data=skillcraft_train, ranges=rpart.ranges))

#用调参后的值进行预测
regtree.tuned <- rpart(LeagueIndex~., data=skillcraft_train,
                       control=rpart.control(minsplit=50, cp=0.002, maxdepth=7))
regtree.tuned_predictions = predict(regtree.tuned, skillcraft_test)
(regtree.tuned_SSE <- compute_SSE(regtree.tuned_predictions, 
                                  skillcraft_test$LeagueIndex))

plot(regtree.tuned, uniform=TRUE, main="Tuned Regression Tree for Skillcraft Data Set")
text(regtree.tuned, use.n=TRUE, all=TRUE, cex=.8)

par(mar=c(2.5,10,2,2))
barplot(regtree.tuned$variable.importance,horiz=T,las=1,
        main="Variable Importance in Tuned Regression Tree")

1）使用rpart.control()函数的参数进行调优

• 树的大小：minsplit
  尝试一次分裂所需数据点的最小数量
  每个节点至少有这么多数据点
• 复杂度参数：cp
  默认是0.01
• 叶节点和根节点之间节点数量的最大值：maxdepth
  默认值是30
  2）使用tune()函数

5.小结

• 树的优势：
  很容易实现，很容易解释
  无需对数据的相关模型做出任何假设
  特征选择和数据缺失较为容易
  处理数据类型的范围很广
• 树的劣势：
  可能分裂数量的指数增长，给类别型变量找到一个分裂变得成本很高
  数据中很小的变化可能改变树中较高位置的分裂决策变化，从而得到另一颗树，结果不稳定
  过拟合