是一个预测模型，分为回归决策树和分类决策树，根据已知样本训练出一个树模型，从而根据该模型对新样本因变量进行预测，得到预测值或预测的分类
从根节点到叶节点的一条路径就对应着一条规则．整棵决策树就对应着一组表达式规则。叶节点就代表该规则下得到的预测值。如下图决策树模型则是根据房产、结婚、月收入三个属性得到是否可以偿还贷款的规则。
核心是如何从众多属性中挑选出具有代表性的属性作为决策树的分支节点。
最基本的有三种度量方法来选择属性
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为根据训练集得到的决策树模型对测试集因变量预测的结果与测试集因变量实际值得到平均绝对误差
R语言学习之决策树决策树最重要的2个问题：决策树的生长问题，决策树的剪枝问题。生长问题又包括了2个子问题：从分组变量的众多取值中选择一个最佳分割点和从众多输入变量中选择当前最佳分组变量；剪枝问题包括2个子问题：预修剪（事先指定树的最大深度，叶子的最小样本量等）和后修剪（先让树充分生长，然后边修剪边检验）。
在R中，实现决策树需要加载包library(rpart)，如果想把分类图画的漂亮点，还可以加载这个包：library(rpart.plot)## rpart.control对树进行一些设置## xval是10折交叉验证## minsplit是最小分支节点数，这里指大于等于20，那么该节点会继续分划下去，否则停止## minbucket：叶子节点最小样本数## maxdepth：树的深度## cp全称为complexity parameter，指某个点的复杂度，对每一步拆分,模型的拟合优度必须提高的程度，用来节省剪枝浪费的不必要的时间，R内部是怎么计算的还真不知道唉ct <- rpart.control(xval=10, minsplit=20, cp=0.1)## kyphosis是rpart这个包自带的数据集## na.action：缺失数据的处理办法，默认为删除因变量缺失的观测而保留自变量缺失的观测。 ## method：树的末端数据类型选择相应的变量分割方法:## 连续性method=“anova”,离散型method=“class”,计数型method=“poisson”,生存分析型method=“exp”## parms用来设置三个参数:先验概率、损失矩阵、分类纯度的度量方法（gini和information）## cost我觉得是损失矩阵，在剪枝的时候，叶子节点的加权误差与父节点的误差进行比较，考虑损失矩阵的时候，从将“减少-误差”调整为“减少-损失”fit <- rpart(Kyphosis~Age + Number + Start, data=kyphosis, method="class",control=ct， parms = list(prior = c(0.65,0.35), split = "information"))## 作图有2种方法## 第一种：par(mfrow=c(1,3))plot(fit)text(fit,use.n=T,all=T,cex=0.9)## 第二种，这种会更漂亮一些：rpart.plot(fit, branch=1, branch.type=2, type=1, extra=102, shadow.col="gray", box.col="green", border.col="blue", split.col="red", split.cex=1.2, main="Kyphosis决策树")## rpart包提供了复杂度损失修剪的修剪方法，printcp会告诉分裂到每一层，cp是多少，平均相对误差是多少## 交叉验证的估计误差（“xerror”列），以及标准误差(“xstd”列)，平均相对误差=xerror±xstdprintcp(fit)## 通过上面的分析来确定cp的值## 我们可以用下面的办法选择具有最小xerror的cp的办法：## prune(fit, cp= fit$cptable[which.min(fit$cptable[,"xerror"]),"CP"])fit2 <- prune(fit, cp=0.01)待续。。。。。。
注：1.在预测分类目标字段时为类别指定先验概率。先验概率是对总体（从中可提取训练数据）中的每个目标分类的总相对频率的估计。换句话说，先验概率是对预测值有任何了解之前对每个可能的目标值的概率估计。确定决策树分支准则的时候会用到，具体内部算法，我暂时还没有查到。
数据分析之美：决策树R语言实现R语言实现决策树
1.准备数据
[plain] view plain copy
>install.packages("tree")
>library(tree)
>library(ISLR)
>attach(Carseats)
>High=ifelse(Sales<=8,"No","Yes") //set high values by sales data to calssify
>Carseats=data.frame(Carseats,High) //include the high data into the data source
>fix(Carseats)
2.生成决策树
[plain] view plain copy
>tree.carseats=tree(High~.-Sales,Carseats)
>summary(tree.carseats)
[plain] view plain copy
//output training error is 9%
Classification tree:
tree(formula = High ~ . - Sales, data = Carseats)
Variables actually used in tree construction:
[1] "ShelveLoc" "Price" "Income" "CompPrice" "Population"
[6] "Advertising" "Age" "US"
Number of terminal nodes: 27
Residual mean deviance: 0.4575 = 170.7 / 373
Misclassification error rate: 0.09 = 36 / 400
3. 显示决策树
[plain] view plain copy
>plot(tree . carseats )
>text(tree .carseats ,pretty =0)
4.Test Error
[plain] view plain copy
//prepare train data and test data
//We begin by using the sample() function to split the set of observations sample() into two halves, by selecting a random subset of 200 observations out of the original 400 observations.
>set . seed (1)
>train=sample(1:nrow(Carseats),200)
>Carseats.test=Carseats[-train,]
>High.test=High[-train]
//get the tree model with train data
>tree. carseats =tree (High~.-Sales , Carseats , subset =train )
//get the test error with tree model, train data and predict method
//predict is a generic function for predictions from the results of various model fitting functions.
>tree.pred = predict ( tree.carseats , Carseats .test ,type =" class ")
>table ( tree.pred ,High. test)
High. test
tree. pred No Yes
No 86 27
Yes 30 57
>(86+57) /200
[1] 0.715
5.决策树剪枝
[plain] view plain copy
/**
Next, we consider whether pruning the tree might lead to improved results. The function cv.tree() performs cross-validation in order to cv.tree() determine the optimal level of tree complexitycost complexity pruning is used in order to select a sequence of trees for consideration.
For regression trees, only the default, deviance, is accepted. For classification trees, the default is deviance and the alternative is misclass (number of misclassifications or total loss).
We use the argument FUN=prune.misclass in order to indicate that we want the classification error rate to guide the cross-validation and pruning process, rather than the default for the cv.tree() function, which is deviance.
If the tree is regression tree,
>plot(cv. boston$size ,cv. boston$dev ,type=’b ’)
*/
>set . seed (3)
>cv. carseats =cv. tree(tree .carseats ,FUN = prune . misclass ,K=10)
//The cv.tree() function reports the number of terminal nodes of each tree considered (size) as well as the corresponding error rate(dev) and the value of the cost-complexity parameter used (k, which corresponds to α.
>names (cv. carseats )
[1] " size" "dev " "k" " method "
>cv. carseats
$size //the number of terminal nodes of each tree considered
[1] 19 17 14 13 9 7 3 2 1
$dev //the corresponding error rate
[1] 55 55 53 52 50 56 69 65 80
$k // the value of the cost-complexity parameter used
[1] -Inf 0.0000000 0.6666667 1.0000000 1.7500000
2.0000000 4.2500000
[8] 5.0000000 23.0000000
$method //miscalss for classification tree
[1] " misclass "
attr (," class ")
[1] " prune " "tree. sequence "
[plain] view plain copy
//plot the error rate with tree node size to see whcih node size is best
>plot(cv. carseats$size ,cv. carseats$dev ,type=’b ’)
/**
Note that, despite the name, dev corresponds to the cross-validation error rate in this instance. The tree with 9 terminal nodes results in the lowest cross-validation error rate, with 50 cross-validation errors. We plot the error rate as a function of both size and k.
*/
>prune . carseats = prune . misclass ( tree. carseats , best =9)
>plot( prune . carseats )
>text( prune .carseats , pretty =0)
//get test error again to see whether the this pruned tree perform on the test data set
>tree.pred = predict ( prune . carseats , Carseats .test , type =" class ")
>table ( tree.pred ,High. test)
High. test
tree. pred No Yes
No 94 24
Yes 22 60
>(94+60) /200
[1] 0.77
