是一个预测模型，分为回归决策树和分类决策树，根据已知样本训练出一个树模型，从而根据该模型对新样本因变量进行预测，得到预测值或预测的分类
从根节点到叶节点的一条路径就对应着一条规则．整棵决策树就对应着一组表达式规则。叶节点就代表该规则下得到的预测值。如下图决策树模型则是根据房产、结婚、月收入三个属性得到是否可以偿还贷款的规则。
核心是如何从众多属性中挑选出具有代表性的属性作为决策树的分支节点。
最基本的有三种度量方法来选择属性
1. 信息增益（ID3算法）
信息熵
一个信源发送出什么符号是不确定的，衡量它可以根据其出现的概率来度量。概率大，出现机会多，不确定性小；反之不确定性就大。不确定性函数f是概率P的 减函数 。两个独立符号所产生的不确定性应等于各自不确定性之和，即f(P1,P2)=f(P1)+f(P2)，这称为可加性。同时满足这两个条件的函数f是对数函数，即
在信源中，考虑的不是某一单个符号发生的不确定性，而是要考虑这个信源所有可能发生情况的平均不确定性。因此，信息熵被定义为
决策树分类过程
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进行划分时，划分值分别有三个，因而有三种划分的可能集合，划分后的子集如下：
对于上述的每一种划分，都可以计算出基于 划分特征= 某个特征值 将样本集合D划分为两个子集的纯度：
决策数分类过程
先剪枝 ：提前停止树的构建对树剪枝，构造树时，利用信息增益、统计显著性等，当一个节点的划分导致低于上述度量的预定义阈值时，则停止进一步划分。但阈值的确定比较困难。
后剪枝 ：更为常用，先得到完全生长的树，再自底向上，用最下面的节点的树叶代替该节点
CART使用代价复杂度剪枝算法 ：计算每个节点剪枝后与剪枝前的代价复杂度，如果剪去该节点，代价复杂度较小（复杂度是树的结点与树的错误率也就是误分类比率的函数），则剪去。
C4.5采用悲观剪枝 ：类似代价复杂度，但CART是利用剪枝集评估代价复杂度，C4.5是采用训练集加上一个惩罚评估错误率
决策树的可伸缩性
ID3\C4.5\CART都是为较小的数据集设计，都限制训练元祖停留再内存中，为了解决可伸缩性，提出了其它算法如
RainForest(雨林）：对每个属性维护一个AVC集，描述该结点的训练元组，所以只要将AVC集放在内存即可
BOAT自助乐观算法：利用统计学，创造给定训练数据的较小样本，每个样本构造一个树，导致多颗树，再利用它们构造1颗新树。优点是可以增量的更新，当插入或删除数据，只需决策树更新，而不用重新构造。
决策树的可视化挖掘
PBC系统可允许用户指定多个分裂点，导致多个分支，传统决策树算法数值属性都是二元划分。并且可以实现交互地构建树。
rpart是采用cart算法，连续型“anova”离散型“class”
2）进行剪枝的函数：prune()
3）计算MAE评估回归树模型误差，这里将样本划分成了训练集和测试集，testdata为测试集
rt.mae为根据训练集得到的决策树模型对测试集因变量预测的结果与测试集因变量实际值得到平均绝对误差
决策树的典型算法有ID3，C4.5，CART等。国际权威的学术组织，数据挖掘国际会议ICDM （the IEEE International Conference on Data Mining）在2006年12月评选出了数据挖掘领域的十大经典算法中，C4.5算法排名第一。基于R语言的分类算法之决策树ID3 《= 最大信息熵增益，只能处理离散型数据
C4.5 《= 信息增益率，可处理连续性和离散型数据，相比ID3，减少了因变量过多导致的过拟合
C5.0 《= 信息增益率，运算性能比C4.5更强大
CART 《= 基尼指数最小原则，连续性和离散型数据均可
信息熵体现的是数据的杂乱程度，信息越杂乱，信息熵越大，反之越小。 例如：拥有四种连续型变量的特征变量的信息熵一定比拥有三种的要大。
特征变量的N种可能性，每种可能性的概率相同，N越大，信息熵越大。
每种可能性的概率不同，越偏态，信息熵越小。
所有特征变量中，信息增益率的，就是根节点（root leaf），根节点一般是选择N越大的特征变量，因为N越大，信息熵越大。
信息增益率是在信息熵的基础上作惩罚计算，避免特征变量可能性多导致的高信息增益。
代码相关
library（C50）
C5.0(x,y, trials = 1, rules=FALSE,weights=NULL,control=C5.0Control(),costs=NULL)
x为特征变量，y为应变量
trials 为迭代次数（这个值根据不同数据而不同，并非越大越好，一般介于5-15之间，可以用遍历来寻找最高准确率的模型，对模型准确率的提升效果中等）
cost 为损失矩阵，R中应该传入一个矩阵（据说是对准确率矩阵约束猜测错误的项，但是并没特别明显的规律，可以使用遍历来寻找最好的cost，准确率提升效果小）
costs <- matrix(c(1,2,1,2),
ncol = 2, byrow = TRUE,
dimnames = list(c("yes","no"), c("yes","no")))
control 设置C5.0模型的其他参数，比如置信水平和节点最小样本等（水很深，参数很多，可以自行查阅R的帮助文档，我只设置了一个CF，准确率提升效果小）
control = C5.0Control(CF = 0.25)
library(C50)
#对iris随机划分训练集和测试集
set.seed(1234)
index <- sample(1:nrow(iris), size = 0.75*nrow(iris))
train <- iris[index,]
test <- iris[-index,]
#查看训练集和测试集分布是否合理
prop.table(table(train$Species))
prop.table(table(test$Species))
#不设置任何参数
fit1 <- C5.0(x = train[,1:4], y = train[,5])
pred1 <- predict(fit1, newdata = test[,-5])
freq1 <- table(pred1, test[,5])
accuracy <- sum(diag(freq1))/sum(freq1)
pred1setosa versicolor virginica
setosa 16 0 0
versicolor 0 13 1
virginica 0 0 8
准确率为0.9736842，只有一个错误。。。显然150个iris太少了，优化都省了。
