本文目录一览：
决策树、随机森林
在了解树模型之前，自然想到树模型和线性模型，他们有什么区别呢？
决策树与逻辑回归的分类区别也在于此。
树形模型更加接近人的思维方式，可以 产生可视化的分类规则，产生的模型具有可解释性 。树模型拟合出来的函数其实是 分区间的阶梯函数 。
决策树（decision tree）是一种基本的分类与回归方法，此处主要讨论分类的决策树。决策树是一种十分常用的分类方法，属于有监督学习（Supervised Learning）。所谓有监督学习，就是给出一堆样本，每个样本都有一组属性和一个分类结果，也就是分类结果已知，那么通过学习这些样本得到一个决策树，这个决策树能够对新的数据给出正确的分类。
决策树是一种树形结构，它主要有三种不同的节点：
决策树算法主要包括三个部分： 特征选择、树的生成、树的剪枝。
比较常用的决策树算法有ID3，C4.5和CART（Classification And Regression Tree），CART的分类效果一般优于其他决策树。
样本数量，特征数量上面，一开始需要注意的：
当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为 经验熵 (empirical entropy)。
什么叫由数据估计？比如有10个数据，一共有两个类别，A类和B类。其中有7个数据属于A类，则该A类的概率即为十分之七。其中有3个数据属于B类，则该B类的概率即为十分之三。浅显的解释就是，这概率是我们根据数据数出来的。
训练数据集D，则训练数据集D的经验熵为H(D)，|D|表示其样本容量，及样本个数。设有K个类Ck，k = 1,2,3,···,K，|Ck|为属于类Ck的样本个数，这经验熵公式可以写为：
信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) H(Y|X)，定义X给定条件下Y的条件概率分布的熵对X的数学期望：
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的分别为经验熵和经验条件熵，此时如果有0概率，令0log0=0。
信息增益
一般地， 熵H(D)与条件熵H(D|A)之差成为互信息(mutual information) 。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
信息增益比
Gini 指数
举例计算Gini指数（不纯度）
这个分类结果明显并不是很好，因为它没有将见面与不见面完全的分开，在算法中，当然不能凭我们的“感觉”去评价分类结果的好坏。我们需要用一个数去表示。（具体数值代入上面的基尼指数计算公式）
信息增益 vs 信息增益比
Gini 指数 vs 熵
ID3算法的核心是在决策树各个结点上对应信息增益准则选择特征，递归地构建决策树。
具体方法是：
1）从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征。
2）由该特征的不同取值建立子节点，再对子结点递归地调用以上方法，构建决策树；直到 所有特征的信息增益均很小或没有特征可以选择 为止；
3）最后得到一个决策树。
ID3相当于用 极大似然法进行概率模型的选择 。
与ID3算法相似，但是做了改进，将信息增益比作为选择特征的标准。
CART 的全称是分类与回归树。从这个名字中就应该知道，CART 既可以用于分类问题，也可以用于回归问题。
回归树中，使用平方误差最小化准则来选择特征并进行划分。每一个叶子节点给出的预测值，是划分到该叶子节点的所有样本目标值的均值，这样只是在给定划分的情况下最小化了平方误差。
要确定最优化分，还需要遍历所有属性，以及其所有的取值来分别尝试划分并计算在此种划分情况下的最小平方误差，选取最小的作为此次划分的依据。由于回归树生成使用平方误差最小化准则，所以又叫做最小二乘回归树。
ID3
熵表示的是数据中包含的信息量大小。熵越小，数据的纯度越高，也就是说数据越趋于一致，这是我们希望的划分之后每个子节点的样子。
信息增益 = 划分前熵 - 划分后熵。信息增益越大，则意味着使用属性 a 来进行划分所获得的 “纯度提升” 越大 **。也就是说，用属性 a 来划分训练集，得到的结果中纯度比较高。
ID3 仅仅适用于二分类问题。ID3 仅仅能够处理离散属性。
C4.5 克服了 ID3 仅仅能够处理离散属性的问题，以及信息增益偏向选择取值较多特征的问题，使用信息增益比来选择特征。 信息增益比 = 信息增益 / 划分前熵 选择信息增益比最大的作为最优特征。
C4.5 处理连续特征是先将特征取值排序，以连续两个值中间值作为划分标准。尝试每一种划分，并计算修正后的信息增益，选择信息增益最大的分裂点作为该属性的分裂点。
CART 与 ID3，C4.5 不同之处在于 CART 生成的树必须是二叉树 。也就是说，无论是回归还是分类问题，无论特征是离散的还是连续的，无论属性取值有多个还是两个，内部节点只能根据属性值进行二分。
决策树生成算法递归的产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但对未知测试数据的分类缺没有那么精确，即会出现过拟合现象。过拟合产生的原因在于在学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，解决方法是考虑决策树的复杂度，对已经生成的树进行简化。
剪枝（pruning）：从已经生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶子节点，从而简化分类树模型。
实现方式：极小化决策树整体的损失函数或代价函数来实现
决策树学习的损失函数定义为：
鉴于决策树容易过拟合的缺点，随机森林采用多个决策树的投票机制来改善决策树，我们假设随机森林使用了m棵决策树，那么就需要产生m个一定数量的样本集来训练每一棵树，如果用全样本去训练m棵决策树显然是不可取的，全样本训练忽视了局部样本的规律，对于模型的泛化能力是有害的。
产生n个样本的方法采用Bootstraping法，这是一种有放回的抽样方法，产生n个样本。
而最终结果采用Bagging的策略来获得，即多数投票机制。
随机森林的生成方法：
1.从样本集中通过重采样的方式产生n个样本
2.假设样本特征数目为a，对n个样本选择a中的k个特征，用建立决策树的方式获得最佳分割点
3.重复m次，产生m棵决策树
4.多数投票机制来进行预测
（需要注意的一点是，这里m是指循环的次数，n是指样本的数目，n个样本构成训练的样本集，而m次循环中又会产生m个这样的样本集）
随机森林是一个比较优秀的模型，在我的项目的使用效果上来看，它对于多维特征的数据集分类有很高的效率，还可以做特征重要性的选择。运行效率和准确率较高，实现起来也比较简单。 但是在数据噪音比较大的情况下会过拟合，过拟合的缺点对于随机森林来说还是较为致命的。
机器学习实战（三）——决策树
决策树与随机森林（三）--提升
转自July--4月机器学习算法班
由决策树和随机森林引发思路
随机森林的决策树分布采样建立，相对独立。
思考：
前m-1棵树是否会影响第m棵树？
各个决策树组成决策森林后，最后的投票过程可否在建立决策树时决定呢？
提升
Adaboost/GDBT
提升的概念：提升是一个机器学习技术，可以用于回归和分类，它每一步产生一个弱预测模型（如决策树），并加权累加到总模型中；如果每一步的弱预测模型生成都是依据 损失函数的梯度方向 ，则称之为提升（Gradient boosting）
梯度提升算法首先给定一个目标损失函数，它的定义域是所有可行的 弱函数集合（基函数） ；提升算法通过迭代的选择一个 负梯度方向上 的基函数来逐渐逼近 局部极小值 。这种在 函数域 的梯度提升观点对机器学习的很多领域有深刻影响
提升的理论意义：如果一个问题存在弱分类器，则可以通过提升的办法得到强分类器。
Adaboost
Adaboost，是英文“Adaptive Boosting”自适应增强的缩写，是一种机器学习方法
其自适应性在于：前一个分类器分错的样本会被用来训练下一个分类器。AdaBoost方法对于噪声数据和异常数据很敏感。
但在一些问题中，AdaBoost方法相对于大多数其他学习算法而言，不会很容易出现过拟合现象。
梯度提升决策树GBDT
梯度提升的典型基函数即决策树（尤其是CART）
在第m步的梯度提升是根据伪残差数据计算决策树tm(x)。
参数设置与正则化
对于训练集拟合过高会降低模型的泛化能力，需要使用 正则化 技术来降低过拟合。
--对于复杂模型增加惩罚项，如：模型复杂度正比于叶节点数目或者叶节点预测值的平方和等。
--用于决策树剪枝
叶节点数目控制了树的层数，一般选择4J8
叶节点包含的最少样本数目
防止出现过小的叶节点，降低预测方差
梯度提升迭代次数M：
增加M可降低训练集的损失值，有过拟合风险
交叉验证
12-分类算法-决策树、随机森林
决策树
生活中的决策树模型：
显然：判断依据的重要性从前往后越来越小
信息的度量和作用
在不知道任何信息的情况下猜测32支球队中的冠军：如果用二分法，需要猜5次，即需要的代价为5bit，这个5bit我们称之为信息熵（H）
5 = -(1/32log(1/32) + 1/32log(1/32) + ... + 1/32log(1/32))
公式：概率log概率 之和
如果我们知道了一些球队的信息，需要的代价会小于5bit
5 -(1/4log(1/32) + 1/8log(1/32) + ... + 1/24log(1/32))
信息熵越大(比如，当每个球队的夺冠几率相等)，不确定性越大
结合决策数，之所以我们先对某些条件进行判断，是因为能够减少我们更多的不确定性
决策树的划分依据——信息增益
信息增益：当得知一个条件之后，减少的信息熵的大小
决策树的api
在泰坦尼克号和titanic2数据帧描述泰坦尼克号上的个别乘客的生存状态。在泰坦尼克号的数据帧不包含从剧组信息，但它确实包含了乘客的一半的实际年龄。关于泰坦尼克号旅客的数据的主要来源是百科全书Titanica。这里使用的数据集是由各种研究人员开始的。其中包括许多研究人员创建的旅客名单，由Michael A. Findlay编辑。
我们提取的数据集中的特征是票的类别，存活，乘坐班，年龄，登陆，home.dest，房间，票，船和性别。乘坐班是指乘客班（1，2，3），是社会经济阶层的代表。
其中age数据存在缺失。
决策树部分图例：
决策树的优缺点以及改进
优点：
缺点：
改进：
集成学习方法
集成学习通过建立几个模型组合的来解决单一预测问题。它的工作原理是 生成多个分类器/模型 ，各自独立地学习和作出预测。这些预测最后结合成单预测，因此优于任何一个单分类的做出预测。
随机森林是一个包含多个决策树的分类器，并且其输出的类别是由个别树输出的类别的众数而定。
随机森林建立多个决策树的过程：
ps：为什么要随机抽样？避免每颗树的训练集的一样，那么最终训练出的上面的分类结果也是完全一样的
随机森林案例：
随机森林的优点：
随机森林几乎没有缺点
决策树（DecisionTree）和随机森林（Random Forests）
令N为训练样例的个数，则单棵决策树的输入样例的个数为N个从训练集中有放回的 随机 抽取N个训练样例。
令训练样例的输入特征的个数为M，我们在每颗决策树的每个节点上进行分裂时，从M个输入特征里 随机 选择m个输入特征，且m远远小于M。然后从这m个输入特征里选择一个最好的进行分裂。 m在构建决策树的过程中不会改变 。
构建决策树的算法主要有以下三种，且根据决策树的输出结果，决策树可以分为 分类树 和 回归树 ，分类树输出的结果为具体的类别，而回归树输出的结果为一个确定的数值。其中 ID3 和 C4.5 是分类树， CART 是分类回归树，且 在ID3 和 C4.5 中，特征（属性）只能选一次，而 CART 没有这样的要求 ：
a. ID3 在决策树生成过程中，以 信息增益 为特征选择的准则。
b. C4.5 在决策树生成过程中，以 信息增益比 为特征选择的准则。
c. CART 对回归树用 平方误差最小化准则 ，对分类树用 基尼指数 （Gini index） 最小化准则 ，进行特征选择，生成二叉树。
例：
图1左中的信息增益InfoGain1 及信息增益比 InfoRatio1为：
同理，图1右的信息增益 InfoGain2 及 InfoRatio2 分别为：
由于 InfoGain1 InfoGain2， 所以由ID3算法选择第一种方法；
由于InfoRatio1 InfoRatio2 ，所以根据C4.5算法选择第一种方法
当节点的数据量小于一个指定的数量时，不继续分裂。两个原因：一是数据量较少时，再做分裂容易强化噪声数据的作用；二是降低树生长的复杂性。提前结束分裂一定程度上有利于降低过拟合的影响。
由上述可知，熵和基尼值的大小表示数据的复杂程度，当熵或者基尼值过小时，表示数据的纯度比较大，如果熵或者基尼值小于一定程度数，节点停止分裂。
节点的深度可以理解为节点与决策树跟节点的距离，如根节点的子节点的深度为1，因为这些节点与跟节点的距离为1，子节点的深度要比父节点的深度大1。决策树的深度是所有叶子节点的最大深度，当深度到达指定的上限大小时，停止分裂。
按照1生成t个决策树之后，对于每个新的测试样例，综合多个决策树的分类结果来作为随机森林的分类结果。
（1）目标特征为 数字类型 ：取t个决策树的 平均值 作为分类结果。
（2）目标特征为 类别类型 ： 少数服从多数 ，取单棵树分类结果最多的那个类别作为整个随机森林的分类结果。
在随机森林中，无需交叉验证来评价其分类的准确性，随机森林自带 OOB（out-of-bag）错误估计 ：
OOB：在构造单棵决策树时我们只是随机有放回的抽取了N个样例，所以可以用没有抽取到的样例来测试这棵决策树的分类准确性，这些样例大概占总样例数目的三分之一。
所以对于每个样例j，都有大约三分之一的决策树（记为SetT（j））在构造时没用到该样例，我们就用这些决策树来对这个样例进行分类。我们对于所有的训练样例 j，用SetT（j）中的树组成的森林对其分类，然后看其分类结果和实际的类别是否相等，不相等的样例所占的比例就是OOB错误估计。OOB错误估计被证明是无偏的。
决策树与随机森林
决策树（decision tree）是一种基本的分类与回归方法，本文主要讨论用于分类的决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布，其主要优点是模型具有可读性，分类速度快。决策树学习通常包括三个步骤：特征选择，决策树的生成和决策树的修剪。而随机森林则是由多个决策树所构成的一种分类器，更准确的说，随机森林是由多个弱分类器组合形成的强分类器。
本文将先对决策树特征选择的算法ID3, C4.5和CART进行计算，然后介绍决策树的剪枝策略，最后介绍随机森林。
在 信息论 中， 条件熵 描述了在已知第二个随机变量X的前提下，随机变量Y的信息熵还剩多少。基于X条件的Y的信息熵，用H(Y|X)表示。
如果H(Y|X=x)为变数Y在变数X取特定值x条件下的熵，那么H(Y|X)就是H(Y|X=x)在X取遍所有可能的x后取平均的结果。
首先需要知道的是熵的公式：
条件熵的推导公式如下：
决策树分类从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点。每一个子节点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶节点，最后将实例分配到叶节点的类中。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行划分。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。通常特征选择的准则是信息增益或信息增益比，特征选择的常用算法有ID3，C4.5，CART。
信息增益表示得知特征A的信息而使得数据X的信息的不确定性的程度。
信息增益定义：特征A对训练数据集D的信息增益g(D, A)定义为集合D的经验熵H(D)与给定特征A的条件下D的经验条件熵H(D|A)之差，即：
根据信息增益选择特征的方法是：对于给定数据集D，计算其每个特征的信息增益，并比较他们的大小，选择信息增益最大的特征。使用信息增益选择特征的算法称为C3算法。
信息增益值的大小是相对于训练数据集而言的，并没有绝对意义。在分类为题困难时，也就是说在训练数据集的经验熵大的时候，信息增益值会偏大。反之，信息增益值会偏小。因此，使用信息增益比可以对这一问题进行校正，这是另一种特征选择算法，也即C4.5算法。
信息增益比定义 ：特征A对训练数据集D的信息增益比g R (D, A)定义为其信息增益g(D, A)与训练集D的经验熵之比：
基尼指数是CART分类树用来选择最优特征的算法，同时决定了该特征的最优二值切分点。
定义：假设有K个类，样本点属于第k类的概率为p k ，则概率分布的基尼指数定义：
对于给定的样本集合D，其基尼指数为：
一个特征的信息增益/基尼系数越大，表明特征对样本的熵减少的能力更强，这个特征使得数据由不确定性变成确定性的能力越强。
决策树生成算法产生的决策树对于训练数据的分类往往很准确，但对于未知数据的分类却没有这么准确，即容易出现过拟合情况。解决的办法便是考虑树的复杂度，对已生成的树进行剪枝简化。
决策树的剪枝往往通过极小化决策树整体的损失函数来实现。
设树T的叶节点个数为|T|，t是树T的叶节点，该叶节点有N t 个样本点，其中k类的样本点有N tk 个，k=1,2,3...K, H t (T)为叶节点t上的经验熵, α=0为参数，则决策树学习的损失函数可以定义为：
损失函数中C(T)表示模型对训练数据的预测误差，也即拟合程度。|T|表示模型复杂度，即节点越多模型越复杂，使用参数α来控制两者之间的影响。α越大模型越简单，对数据拟合差；α越小模型越复杂，对数据拟合性好；α=0时则不考虑模型复杂度。
因此，剪枝就是在确定了α时，选择损失函数最小的树。
参考：
《统计学习方法》李航
机器学习. 邹博
