机器学习概述
决策树（decision trees）
根据数据的属性采用树状结构建立决策模型。决策树模型常常用来解决分类和回归问题，从名字看解决离散型的分类问题的是决策树，决策连续型值的回归问题的是回归树（明白决策树的运行机制后，回归树也可理解）。常见的算法包括 CART (Classification And Regression Tree)、ID3、C4.5，它们都是采用贪心（即非回溯）方法，自顶向下递归的分治方法构造。在决策树理论中，“用较少的东西，照样可以做很好的事情。越是小的决策树，越优于大的决策树”。
a) 决策树原理：决策树最简单的就是二元划分，类似于二叉树，也可以认为决策树是一种if-then规则集合（例子，见图18-1）。数据分类是一个两阶段过程，包括模型学习阶段（构建分类模型）和分类预测阶段（使用模型预测给定数据的类标号）：
第一阶段（以分类为例）：可以看作是根据样本来学习一个映射或者函数y=f(x)表达式，能够使用它预测给定元祖X的标号y。
第二阶段：使用第一阶段得到的模型进行分类。首先评估分类器的预测准确率，这个过程要尽量减少过拟合（过拟合无法避免，再好的模型也有过拟合的情况）。
简单决策树，预测用户是否有能力偿还贷款，树中每个结点表示某个对象，内部结点表示一个特征或属性，叶结点表示一个类，而每个分叉路径则代表某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。
b) 决策树算法优点：算法比较简单、理论易于理解、与噪声数据有很好的健壮性。现在决策书是应用最广泛的归纳推理算法之一，衍生出许多出色的集成算法：随机森林、adaboost、gradient tree boosting等都是基于决策树模型。
c) 决策树算法一般流程：
收集数据：任意方法和途径
准备数据：树构造算法只适用于标准型数据，因此数据必须离散化
分析数据：构造树完成后，检查图形是否符合预测
训练算法：决策树的数据构造
测试算法：一般将决策树用于分类，可以用错误率衡量，而错误率经常用经验率计算
使用算法：决策树可以用于任何监督学习算法
d) 具体的，我们有了数据后要怎么构造一颗决策树？首先应该解决三个：
根节点放置哪个条件属性？（信息增益最大的一个属性/特征作为根节点）
下面的节点放置哪个属性？（我们只需要将已经得到的结点看做一个新的根结点，利用最小化条件信息熵的方法即可。）
什么时候停止树的生长？（当我们发现所有特征的信息增益均很小，或者我们没有特征可以选择了就可以停止了）
e) 要解决这三个问题就要明白些概念：
特征选择。选择一个合适的特征作为判断节点，可以快速的分类，减少决策树的深度。决策树的目标就是把数据集按对应的类标签进行分类。最理想的情况是，通过特征的选择能把不同类别的数据集贴上对应类标签。特征选择的目标使得分类后的数据集比较纯。如何衡量一个数据集纯度，这里就需要引入数据纯度函数。下面将介绍两种表示数据纯度的函数：信息增益、基尼指数。
信息熵（entropy）：它确定了要编码集合 S 中任意成员（即以均匀的概率随机抽出的一个成员）的分类所需要的最少二进制位数。，通俗解释即，“预测随机变量Y的取值”的难度。信息熵表示的是不确定度，是系统有序化程度的度量，信息熵越小，系统越是有序。均匀分布时，不确定度最大，此时熵就最大。当选择某个特征对数据集进行分类时，分类后的数据集信息熵会比分类前的小，其差值表示为信息增益。信息增益可以衡量某个特征对分类结果的影响大小。
我们可以举例子解释：1）假如你在地球上，手里握着一个铁块，当你不对铁块施力而直接松手的情况下，请你判断它是会向下坠落，还是向上飞去，根据我们的常识我们能很容易判断出石块会下落，那么判断这个事情的结果就非常容易，那么此时的信息熵就可以认为是0。2）假如让你判断一枚匀质的硬币抛出后正面朝上还是反面朝上，这个问题我们就比较难回答了，因为正面朝上和反面朝上的概率均等，我们不能有一个很确定的判断硬币到底哪个面朝上，那么这个时候判断就比较难了，所以此时的信息熵就可以认为是1。
信息熵的抽象理解的数学化定义与描述有很多，具体看下图，现在最常用的就是香农信息熵
上图的香农信息熵公式表示D(ata)中的元祖所有分类所有可能值的信息期望，其中，D表示训练数据集，m表示数据类别数，pi表示类别i样本数量占所有样本的比例。熵越大，说明系统越混乱，携带的信息就越少。熵越小，说明系统越有序，携带的信息就越多，信息的作用就是在于消除不确定性。
对应数据集D,选择特征A作为决策树判断节点时，在特征A作用后的信息熵为infoA(D)（作用之前的信息熵为info(D)）。其计算公式为，其中，K表示样本D被分为K部分，信息增益表示数据集D在特征A作用后，其信息熵减少的值，公式为：。对于决策树节点最合适的特征选择，就是Gain(A)值最大的特征。
基尼系数：另一种数据纯度的度量方法，公式为：，其中，c表示数据集中类别的数量，pi表示类别i样本数占所有样本的比例。从该公式可以看出，当数据集中数据混合的程度越高，基尼指数也就越高。当数据集 D 只有一种数据类型，那么基尼指数的值为最低 0。
如果选取的属性为 A，那么分裂后的数据集 D 的基尼指数的计算公式为：
，其中，其中 k 表示样本 D 被分为 k 个部分，数据集 D 分裂成为 k 个 Dj 数据集。
对于特征选取，需要选择最小的分裂后的基尼指数。也可以用基尼指数增益值作为决策树选择特征的依据，公式如下
：
决策树选择特征时，应选择基尼指数增益值最大的特征，作为该节点分裂条件。
f) 不同的决策树算法在选择目标函数上会有差别：有最小化条件信息熵、信息增益（ID3）、信息增益比（C4.5）和基尼系数（CART）。
ID3：信息增益最大的准则
C4.5：信息增益比最大的准则
CART：
[1] 回归树: 平方误差最小的准则
[2] 分类树: 基尼系数最小的准则
g) 剪枝：分类模型建立的过程中，很容易出现过拟合的现象。过拟合是指在模型学习训练中，训练样本达到非常高的逼近精度，但对检验样本的逼近误差随着训练次数而呈现出先下降后上升的现象。过拟合时训练误差很小，但是检验误差很大，不利于实际应用。决策树的过拟合现象可以通过剪枝进行一定的修复，剪枝分为预先剪枝和后剪枝两种。
预先剪枝：决策树生长过程中，使用一定条件加以限制，使得产生完全拟合的决策树之前就停止生长。预先剪枝的判断方法也有很多，比如信息增益小于一定阀值的时候通过剪枝使决策树停止生长。但如何确定一个合适的阀值也需要一定的依据，阀值太高导致模型拟合不足，阀值太低又导致模型过拟合。
后剪枝：决策树生长完成之后，按照自底向上的方式修剪决策树。后剪枝有两种方式，一种用新的叶子节点替换子树，该节点的预测类由子树数据集中的多数类决定。另一种用子树中最常使用的分支代替子树。
预先剪枝可能过早的终止决策树的生长，后剪枝一般能够产生更好的效果。但后剪枝在子树被剪掉后，决策树生长的一部分计算就被浪费了。
h) 决策树模型评估：用来判断得到的决策树模型的优劣。学习算法模型使用训练集建立模型、使用测试集评估模型。
i) 决策树的评估指标：分类准确度、召回率（recall）、虚警率和精确度等，具体这些指标是基于混淆矩阵（confusion matrix）进行计算的，矩阵的行表示实际分类，矩阵列表示预测分类。以二类分类为例（要识别的是类1）（与前面6相似）：
实际为类1 |
实际为类2 |
|
预测为1 |
TP(true positive) |
FN(false negative) |
预测为2 |
FP(false positive) |
TN(true negative) |
总计 |
P(positive) |
N(negative) |
TP:待预测图片是类1，且被准确识别为类1；
FN:待预测图片是非类1（类2），却被错误识别为类1；
FP:待预测图片是类1，却被错误识别为非类1（类2）；
TN:待预测图片是非类1（类2），且被正确识别为非类1（类2）；
P:测试过的所有真实类别为类1的测试图片；
N:测试过的所有真实类别为非类1（类2）的测试图片；
准确度（对错样本分别被正确分类的概率）公式：
召回率（对的样本被识别的概率）公式：
虚警率（错的样本被错误当作对的样本的概率）公式：
精确度（分类为正样本中正确图片的概率）公式：
i) 决策树评估方法：保留法、随机二次抽样、交叉验证和自助法等。
保留法 (holdout) 是评估分类模型性能的最基本的一种方法。将被标记的原始数据集分成训练集和检验集两份，训练集用于训练分类模型，检验集用于评估分类模型性能。但此方法不适用样本较小的情况，模型可能高度依赖训练集和检验集的构成。
随机二次抽样 (random subsampling) 是指多次重复使用保留方法来改进分类器评估方法。同样此方法也不适用训练集数量不足的情况，而且也可能造成有些数据未被用于训练集。
交叉验证 (cross-validation) 是指把数据分成数量相同的 k 份，每次使用数据进行分类时，选择其中一份作为检验集，剩下的 k-1 份为训练集，重复 k 次，正好使得每一份数据都被用于一次检验集 k-1 次训练集。该方法的优点是尽可能多的数据作为训练集数据，每一次训练集数据和检验集数据都是相互独立的，并且完全覆盖了整个数据集。也存在一个缺点，就是分类模型运行了 K 次，计算开销较大。
自助法 (bootstrap) 是指在其方法中，训练集数据采用的是有放回的抽样，即已经选取为训练集的数据又被放回原来的数据集中，使得该数据有机会能被再一次抽取。用于样本数不多的情况下，效果很好。