1.介绍
决策树是一种目标函数为离散值的学习方法(区别于回归)，学习到的函数可以用树形表示也可以使用if-then规则来增加可读性。
什么时候考虑使用决策树：(1)实例可以描述为属性-值对，即监督学习
(2)目标函数是离散值
（3）数据可能包含噪声和缺失值
决策树表示实例属性值上约束合取的析取，这句话比较难理解，可以看一下下面图中的例子：
那么就有三个问题：(1)如何确定属性判断条件
(2)如何确定切分属性顺序
(3)什么时候停止节点的划分
1.1.如何确定属性判断条件
依赖于属性类型(标称顺序连续)和切分方式(二分类和多分类)，二分类与多分类的区别如下图：
1.2.如何确定切分属性顺序
如果将纯净度这一指标量化表示有三个度量标准：基尼系数、熵、误分类误差
(1)基尼系数
举个例子：
可以看出来，如果结点越纯净则基尼系数越大，因此找分类节点依据的属性时应当找分类后基尼系数小的属性，因为依该属性划分后节点更纯净。
(2)熵
熵表示数据的混乱程度，如果数据越不纯则熵越大。还是举个例子：
信息增益：是依据该属性划分后熵的下降差值(划分前的熵减去划分后的熵)，因此选择信息增益大的即熵下降最快的作为划分属性。
(3)误分类率
叶子节点的类标签由子树中的大多数类实例确定，剩下的就是所有分错的数据所占比率，举个例子：
从上面的例子可以看出来，误分类率越小越纯净，另外三个衡量指标的关系如下图所示：
1.3.什么时候停止节点的划分
如果每个节点的数据类别相同或相似就可以停止划分结点了，或者还有一些其他条件下面将谈到。
2.分类树
分类树具有构建简单、可以快速分类未知数据、易于解读和准确率较高的优点,例如ID3和C4.5两种分类树，前者使用信息增益后者使用信息增益率。但是分类树在实际应用中有三个问题：欠拟合与过拟合、缺失值、分类成本
2.1.欠拟合与过拟合
与其他机器学习算法一样，决策树也会出现欠拟合和过拟合情况，另外决策树采用的是贪心算法(每一步都达到当前最优)，很容易出现过拟合。另外过拟合有可能因为噪声数据，
如何解决过拟合问题：预剪枝和后剪枝
(1)预剪枝（早停止规则）
当每个结点中实例数少于用户定义的阈值；如果节点中实例的类分布具有一定的可信度(使用卡方检验)；节点的纯净度不再提升。
(2)后剪枝
后剪枝是自底向上的剪枝，如果修剪后泛化误差得到改善，则用叶节点替换子树。
2.2.缺失值问题
缺失值数据主要影响有三点：影响结点纯净度的度量；影响有缺失值实例的结点类别划分；影响有缺失值测试实例的分类
(1)结点纯净度的度量
先举个例子如下图所示
如图中例子所示，首先去除缺失值属性，其他不含缺失值实例按照正常计算信息增益，然后再乘以非缺失值所占比例即可
(2)节点类别划分
接上面的例子如下图：
之前不含缺失值的时候是数结点个数，且实例属性确定，因此分实例的时候是整个将其分过去的，但是如果此时我们不知道某实例该属性的取值，就可以按照已经分了的实例比率进行划分，例如上例中refund=yes的比例是3/9，那么第十条实例分到refund=yes的概率就是1/3，而本实例所属类别为yes，因此左结点的yes加上1/3
(3)测试实例的类别判断
将缺失值所在的属性进行统计，然后按照概率进行划分。
3.模型评估
有三个问题：(1)使用什么样的指标进行模型的评估
（2）使用什么样的方法进行模型评估
（3）不同的模型之间如何对比相对的性能
3.1.评估指标
这里不考虑模型构建速度等只关注预测准确度，主要使用混淆矩阵。
但是使用准确度有一个局限，比如一个不均衡数据集，类别为0的数据有9990个而类别为1的数据有10个，模型不管怎样都将其预测为类别0，那么准确率就高达99.9%，这是很不科学的，所以我们会在混淆矩阵的基础上再加上成本矩阵例如下图所示：
还有一些其他的评估指标：
3.2.评估方法
(1)Holdout
将整个数据集D划分为训练集和验证集
(2)Random subsampling
重复多次Holdout操作
(3)Cross validation
将整个数据划分为若干段，每次训练选取一段作为测试集其余作为训练集，依次循环直到所有的数据段都作为测试集被训练一次。
(4)Stratified sampling（分层采样）
(5)Bootstrap
有放回等概率采样
3.3.模型比较
受试者工作特征曲线 （receiver operating characteristic curve，简称ROC曲线），x轴是假阳值FP，y轴是真阳性值TP。ROC曲线上的每一个点表示的每个分类器的性能，改变算法的阈值，样本分布或成本矩阵改变点的位置。举例来说：
例子中大于t的判断为正例，左图中红线表示真实为正例的实例，因此TP与FN均为0.5，蓝线表示真实为负例的实例。得到TP与FP，调整t的值会得到多组TP与FP可以据此画出ROC曲线。如果ROC曲线越靠近左上角说明模型性能越好。但是如果出现不好判断的情况，如下图可以通过计算ROC曲线下的面积来决定。
还剩下一个问题：如果模型1基于30个实例进行训练得到准确率85%，模型2基于5000个实例得到准确率75%，我们会说模型1一定比模型2好吗？
答案是否定的，这时候可以这么考虑，将每次预测看作是一次伯努利实验，然后计算置信区间。
具体做法：两个模型：模型1训练集D1（大小n1），误差率e1；模型2训练集D2(大小n2)，误差率e2,当数量很多的时候可以近似成正态分布，
令两者误差率之差为:
,
拿之前那个问题讲，
