应用及介绍
是一个预测模型，分为回归决策树和分类决策树，根据已知样本训练出一个树模型，从而根据该模型对新样本因变量进行预测，得到预测值或预测的分类
从根节点到叶节点的一条路径就对应着一条规则．整棵决策树就对应着一组表达式规则。叶节点就代表该规则下得到的预测值。如下图决策树模型则是根据房产、结婚、月收入三个属性得到是否可以偿还贷款的规则。
决策树的构建
核心是如何从众多属性中挑选出具有代表性的属性作为决策树的分支节点。
最基本的有三种度量方法来选择属性
1. 信息增益（ID3算法）
信息熵
一个信源发送出什么符号是不确定的，衡量它可以根据其出现的概率来度量。概率大，出现机会多，不确定性小；反之不确定性就大。不确定性函数f是概率P的减函数。两个独立符号所产生的不确定性应等于各自不确定性之和，即f(P1,P2)=f(P1)+f(P2)，这称为可加性。同时满足这两个条件的函数f是对数函数，即
在信源中，考虑的不是某一单个符号发生的不确定性，而是要考虑这个信源所有可能发生情况的平均不确定性。因此，信息熵被定义为
决策树分类过程
- 首先，假设数据集D中需要预测的标记类分为类A和类B，根据总体类A,B的出现概率计算信息熵G1。
- 依次选择每一个属性，如果该属性为离散型，计算该属性取每个值的类A,B概率，得出该属性的信息熵Gi；若为连续值属性，则依次排序后选每两个相邻值的中点，每个中点得到2个分区类似离散属性的2个类别，选择信息熵最小的那个中点作为该属性的分裂点。计算该属性的信息熵。
- 计算属性i的信息增益，也就是G1 - Gi，选择信息增益最大的属性作为分裂节点，依次递归
2、增益率（C4.5算法）
由于信息增益的缺点是：倾向于选择具有大量值的属性，因为具有大量值的属性每个属性对应数据量少，倾向于具有较高的信息纯度。因此增益率使用【信息增益/以该属性代替的系统熵（类似于前面第一步将play换为该属性计算的系统熵】这个比率，试图克服这种缺点。
g(D,A)代表D数据集A属性的信息增益，
3. 基尼指数（CART算法）
基尼指数：
表示在样本集合中一个随机选中的样本被分错的概率。越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高。
假设集合中有K个类别，则：
说明:
1. pk表示选中的样本属于k类别的概率，则这个样本被分错的概率是(1-pk)
2. 样本集合中有K个类别，一个随机选中的样本可以属于这k个类别中的任意一个，因而对类别就加和
3. 当为二分类是，Gini(P) = 2p(1-p)
基尼指数是将属性A做二元划分，所以得到的是二叉树。当为离散属性时，则会将离散属性的类别两两组合，计算基尼指数。
举个例子：
如上面的特征Temperature，此特征有三个特征取值： “Hot”，“Mild”， “Cool”，
当使用“学历”这个特征对样本集合D进行划分时，划分值分别有三个，因而有三种划分的可能集合，划分后的子集如下：
- 划分点： “Hot”，划分后的子集合 ： {Hot}，{Mild，Cool}
- 划分点： “Mild”，划分后的子集合 ： {Mild}，{Cool，Hot}
- 划分点： “Cool”，划分后的子集合 ： {Cool}，{Mild，Hot}
对于上述的每一种划分，都可以计算出基于 划分特征= 某个特征值 将样本集合D划分为两个子集的纯度：
决策数分类过程
- 首先，假设数据集D中需要预测的标记类分为类A和类B，根据总体类A,B的出现概率计算基尼指数G1。
- 依次选择每一个属性，如果该属性为离散型，按上面的方法将离散属性的类别两两组合，计算基尼指数；若为连续值属性，类似信息增益的方法。计算该属性的基尼指数Gi。
- 计算属性i的基尼指数降低值，也就是G1 - Gi，选择降低最大的属性作为分裂节点，依次递归
总结：以上时分类决策树最常用的三种属性选择度量，信息增益倾向于选择多值属性；增益率倾向于产生不平衡的划分，一个分区比其他分区小得多；基尼指数偏向于多值属性，并且在类的数量很大时会有困难.其它属性选择度量如基于统计卡方检验的属性度量、最小描述长度(MDL，基本思想是首选最简单的解）
剪枝
先剪枝：提前停止树的构建对树剪枝，构造树时，利用信息增益、统计显著性等，当一个节点的划分导致低于上述度量的预定义阈值时，则停止进一步划分。但阈值的确定比较困难。
后剪枝：更为常用，先得到完全生长的树，再自底向上，用最下面的节点的树叶代替该节点
CART使用代价复杂度剪枝算法：计算每个节点剪枝后与剪枝前的代价复杂度，如果剪去该节点，代价复杂度较小（复杂度是树的结点与树的错误率也就是误分类比率的函数），则剪去。
C4.5采用悲观剪枝：类似代价复杂度，但CART是利用剪枝集评估代价复杂度，C4.5是采用训练集加上一个惩罚评估错误率
拓展
决策树的可伸缩性
ID3\C4.5\CART都是为较小的数据集设计，都限制训练元祖停留再内存中，为了解决可伸缩性，提出了其它算法如
RainForest(雨林）：对每个属性维护一个AVC集，描述该结点的训练元组，所以只要将AVC集放在内存即可
BOAT自助乐观算法：利用统计学，创造给定训练数据的较小样本，每个样本构造一个树，导致多颗树，再利用它们构造1颗新树。优点是可以增量的更新，当插入或删除数据，只需决策树更新，而不用重新构造。
决策树的可视化挖掘
PBC系统可允许用户指定多个分裂点，导致多个分支，传统决策树算法数值属性都是二元划分。并且可以实现交互地构建树。
R语言构建决策树
rpart是采用cart算法，连续型“anova”;离散型“class”;
library(rpart)
rtmodel <- rpart(review_Count~.,data=highdata,method="anova")
#绘制决策树
library(rpart.plot)
prp(rtmodel,extra=101,box.col="orange",split.box.col="grey")
printcp(rtmodel)
data$neighborhood <- lapply(data$neighborhood,foo)
data$neighborhood <- as.factor(unlist(data$neighborhood))
maindata <- data[,-c(1:5,10,11)]
2）进行剪枝的函数：prune()
prune(tree, cp, ...)
主要参数说明:
tree：一个回归树对象,常是rpart()的结果对象。
cp：复杂性参量,指定剪枝采用的阈值。cp全称为complexity parameter，指某个点的复杂度，对每一步拆分,模型的拟合优度必须提高的程度，用来节省剪枝浪费的不必要的时间。
3）计算MAE评估回归树模型误差，这里将样本划分成了训练集和测试集，testdata为测试集
rt.mae为根据训练集得到的决策树模型对测试集因变量预测的结果与测试集因变量实际值得到平均绝对误差
rt.predictions.arpu <-
predict(rtmodel, testdata)
rt.mae <- mean(abs(rt.predictions.arpu
- testdata[["oddreview"]]))
rt.mae
