是一个预测模型，分为回归决策树和分类决策树，根据已知样本训练出一个树模型，从而根据该模型对新样本因变量进行预测，得到预测值或预测的分类
从根节点到叶节点的一条路径就对应着一条规则．整棵决策树就对应着一组表达式规则。叶节点就代表该规则下得到的预测值。如下图决策树模型则是根据房产、结婚、月收入三个属性得到是否可以偿还贷款的规则。
核心是如何从众多属性中挑选出具有代表性的属性作为决策树的分支节点。
最基本的有三种度量方法来选择属性
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为根据训练集得到的决策树模型对测试集因变量预测的结果与测试集因变量实际值得到平均绝对误差
CART算法就是分类回归树，它只支持二叉树，既可以作分类树，又可以作回归树。
那什么是分类树，什么是回归树呢？假如有个数据集，分别给出了，不同年龄、职业、性别的不同学习时间。如果我构造了一棵决策树，想要基于数据判断这个人的职业身份，这个就属于分类树，因为是从几个分类中来做选择。如果是给定了数据，想要预测这个人的年龄，那就属于回归树。分类树可以处理离散数据，也就是数据种类有限的数据，它输出的是样本的类别，而回归树可以对连续型的数值进行预测，也就是数据在某个区间内都有取值的可能，它输出的是一个数值。
CART算法属性指标是基尼系数。基尼系数本身反应了样本的不确定性。当基尼系数越小的时候，说明样本之间的差异性小，不确定程度低。分类的过程本身是一个不确定度降低的过程，即纯度的提升过程。所以CART算法在构造分类树的时候，会选择基尼系数最小的属性作为属性的划分。
一、基本概念
1.cart使用基尼系数作为划分标准。基尼系数越小，则不纯度越低，区分的越彻底。
2.假设有k个类别，第k个类别的概率为 ,则基尼系数表达式为：
Gini(p)=(1- )=1-
3.对于样本D，如果根据特征A 的值把样本分为D1,D2两部分，则在特征A条件下，D的基尼系数
Gini(D,A)= Gini(D1)+ Gini(D2)
4.CART建立起来的是二叉树，如果特征A有A1,A2，A3三个类别，CART会考虑把A分成{A1},{A2 ,A3}两组，或者是其他两种情况。由于这次A并没有完全分开，所以下次还有机会在子节点把A2,A3分开.
5.对于连续值的切分.假如有1 2 3 4 5 那么cart会有4个切分点 [1.5 2.5 3.5 4.5]
二.实例推导树的建立过程
1.假设我有以下源数据
序号 天气 周末 促销 销量
1 坏 是 是 高
2 坏 是 是 高
3 坏 是 是 高
4 坏 否 是 高
5 坏 是 是 高
6 坏 否 是 高
7 坏 是 否 高
8 好 是 是 高
9 好 是 否 高
10 好 是 是 高
11 好 是 是 高
12 好 是 是 高
13 好 是 是 高
14 坏 是 是 低
15 好 否 是 高
16 好 否 是 高
17 好 否 是 高
18 好 否 是 高
19 好 否 否 高
20 坏 否 否 低
21 坏 否 是 低
22 坏 否 是 低
23 坏 否 是 低
24 坏 否 否 低
25 坏 是 否 低
26 好 否 是 低
27 好 否 是 低
28 坏 否 否 低
29 坏 否 否 低
30 好 否 否 低
31 坏 是 否 低
32 好 否 是 低
33 好 否 否 低
34 好 否 否 低
该数据集有三个特征 天气 周末 促销
2.为了简化建立树的过程,我将忽略基尼系数与样本个数阀值
2.1 首先计算各个特征值对数据集的基尼系数,公式见---- 基本概念.3
Gini(D|天气)=17/34*(1-(11/17)^2-(6/17)^2)+17/34*(1-(7/17)^2-(10/17)^2)=0.4706
Gini(D|周末)=20/34*(1-(7/20)^2-(13/20)^2)+14/34*(1-(11/14)^2-(3/14)^2)=0.4063
Gini(D|促销)=12/34*(1-(9/12)^2-(3/12)^2)+22/34*(1-(7/22)^2-(15/22)^2)=0.4131
周末的基尼系数最小，这也符合我们的一般认识
2.2 第一个分列特征选择周末。此时数据集按照是否周末分成两个。
Gini(周末|天气)=0.2679
Gini(周末|促销)=0.2714
Gini(非周末|天气)=0.3505
Gini(非周末|促销)=0.3875
此时，周末应该以天气作为划分，非周末也是以天气作为划分，下面放个图
三、CART树对于连续特征的处理
假如特征A为连续型变量，则把特征A按照从小到大进行排序，取相邻两点的平均值为切分点，计算基尼系数。则基尼系数最小的点为切分点，大于切分点的为一类，小于切分点的为另一类。举例：特征A的值为 1，2，3，4，5，6 目标变量是高、低、高、低、高、低。则1.5处的基尼系数为 (1/6)*(1-1^2)+(5/6)*(1-(2/5)^2-(3/5)^2)=0.4 2.5处的基尼系数为 (2/6)*(1-(1/2)^2-(1/2)^2)+(4/6)*(1-(2/4)^2-(2/4)^2)=0.5 3.5处的基尼系数为 (3/6)*(1-(1/3)^2-(2/3)^2)+(3/6)*(1-(1/3)^2-(2/3)^2)=0.44 4.5处的基尼系数为 (4/6)*(1-(2/4)^2-(2/4)^2)+(2/6)*(1-(1/2)^2-(1/2)^2)=0.5 5.5处的基尼系数为 (5/6)*(1-(2/5)^2-(3/5)^2)+(1/6)*(1-1^2)=0.4 结论： 1.5和5.5处的基尼系数最小，可以把1分为一类，2-6分为另一类。或者6分为一类，1-5另一类。
四、关于回归树
1.回归树和分类树的区别在于输出值类型不同。分类树输出的是离散值，回归树输出的是连续值。
2.和分类树使用基尼系数不同，回归树使用和均方差来度量最佳分隔点。假设有1 2 3 4 5 6 六个数。假设3.5处把数据分开最合适，那么(1-2)^2+(2-2)^2+(3-2)^2+(4-5)^2+(5-5)^2+(6-5)^2在所有分割点中取得最小值。2，5为各自数据段的平均值。
3.回归树采用最后叶子的平均值或者中值作为输出结果
