决策树和随机森林
首先，明白两个概念：Bagging和Boosting。两者都是将现有的分类或者回归算法组合在一起，行程一个更强大的分类器的一种方法。
Bagging(bootstrap aggregating)：
算法过程：
1、从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（k个训练集之间是相互独立的）。
2、每次使用一个训练集得到一个模型，k个训练集共得到k个模型。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）。
3、对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）。
Boosting：把弱分类器组合成强分类器。
核心思想：
1、在每一轮如何改变训练数据的权值或概率分布？
通过提高那些在前一轮被弱分类器分错样例的权值，减小前一轮分对样例的权值，来使得分类器对误分的数据有较好的效果。
2、通过什么方式来组合弱分类器？
通过加法模型将弱分类器进行线性组合，比如AdaBoost通过加权多数表决的方式，即增大错误率小的分类器的权值，同时减小错误率较大的分类器的权值。
提升树通过拟合残差的方式逐步减小残差，将每一步生成的模型叠加得到最终模型。
两者区别：
1、样本选择：
Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。
Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。
2、样例权重：
Bagging：使用均匀取样，每个样例的权重相等。
Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。
3、预测函数：
Bagging：所有预测函数的权重相等。
Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
4、并行计算：
Bagging：各个预测函数可以并行生成。
Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。
总结：
1）Bagging + 决策树 = 随机森林
2）AdaBoost + 决策树 = 提升树
3）Gradient Boosting + 决策树 = GBDT
通过上面分析，我们大体理解了决策树和随机森林之间的关系。
我们先来分析下决策树。
决策树
分类树：
核心思想：在数据集中找到最优的特征，从该特征的值中选出最优的取值，根据这个值将数据集分成两个子集，递归操作，直到满足条件为止。
1、如何找最优特征？
常用的方法是根据信息增益或者信息增益率来寻找最优特征。
信息增益是什么？
首先，考虑熵，熵越大数据的不确定性就越高。决策树的目的就是利用数据的一些规则来尽可能的降低数据集的不确定性。给定一批数据集，我们可以很容易得到它的不确定性(熵)。
然后，我们要想办法降低这个不确定性，我们需要挖掘数据集中有用的特征，在某个特征的限制下，我们又能得到数据集的不确定性（这个其实就是书上的条件熵）。我们用两次的值作差，这个结果的含义很明了，给定了这个特征，让我们数据集的不确定性降低了多少，当然降低的越多这个特征肯定就越好了。而我们讲了这么多就是要找到那一个让数据集不确定性降低最多的特征。我们认为这个特征是当前特征中最好的一个。
2、有了最优特征，为什么还需要最有特征的最优值？
一般的二分类问题确实没必要找最优值，但对于多分类问题，需要最优值。
分析一下：假如我们的某个最优特征有三个类别：我们如果不找就直接分为三个子节点了。这样会出现一个问题，就是我们的这个分类对特征值会变得敏感，为什么这么说，我们来讲一个很简答的例子：我们平时考试规定了60分及格，这个控制对于大多数学生很好把控，因为就一个条件，相当于一个二分类。但是如果我们把条件控制严格一些，比如超过60分，不超过80分为优秀学生。这个控制很多学霸就不好控制了，对于多分类问题也是这个道理，如果我们一下子从父节点直接分了多个子节点，那么我们的数据肯定会对这个控制很敏感，敏感就会导致出错。出错不是我们希望看到的，所以我们建议对多分类问题找最优候选值来转化为二分类问题，同样多个二分类问题其实也是一个多分类问题，只是多了几个递归过程而已。
3、递归如何停止？
当我们检测到数据的分类效果已经够好了，我们其实就可以停止了。当然我们常用的是控制叶节点，比如控制叶节点的样本数目，比如当某个子节点内样本数目小于某一个指定值，我们就决定不再分了。还有叶节点的纯度，我们规定叶节点样本必须属于同一类才停止，这也是一个停止条件。还有最大树的深度，比如我们规定树的最大深度为某一个值，当树深度到达这个值我们也要停止。还有比如：分裂次数，最大特征数等等。可以自己灵活选择和处理。
分类和度量
使用ID3和C4.5的分类树
ID3算法其实就是我们一般所理解的决策树算法，其基本步骤就是我们上面所讲的步骤，这个算法的核心思想就是用信息增益来选择最优分类特征，信息增益的公式上面也给出了，这个公式我们仔细分析一下会发现一个问题：我们需要找到 g(D,A) 最大的特征，对于一个数据集entropy(D)是给定的，也就是说我们需要 entropy(D,A) 最小，意思就是我们所选的特征是那些分完后子节点的纯度最高的特征，什么样的特征分完后子节点的特征纯度比较高(熵比较小)，该特征的子类别很多，即可取值很多的这一类特征。总结一下就是信息增益偏向于去那些拥有很多子类的特征。这也是这个算法的一大致命缺点，任何带有主观偏向性的算法都不是一个好的算法，当然ID3算法的另一个缺点也显而易见，它只能处理那些分类的特征，对于连续值特征毫无办法（其实我们可以人为的把连续属性给离散化，但是人为必然会导致可能不准确）。
C4.5是对ID3算法的一个改进，主要改进点就是解决了ID3的几个缺点。首先C4.5算法用的是信息增益率来代替ID3中的信息增益。从表达式可以看出来，这么做其实就是弱化那些偏向，让选择最优特征时更加公平。可以处理连续值。
1、首先对于连续值属性的值进行排序(A1,A2......An);
2、我们可以在每两个值之间取一个点，用这个点就可以把该组连续值分为两部分，比如我们去一个点a1(A1<a1<A2),则小于a1的部分（A1）大于a1的部分（A2......An）。但是这个a1好吗？不知道呀！那我们loop一下所有这样的a(共有n-1个)，每一个ai我们可以算出分裂前后的信息增益率，然后我们求一个max即可。很简单吧！思路很好，但是呀很显然有个问题，时间开销有点大。
3、缺失值的处理，ID3不能直接处理(需要我们人工处理，比如单独赋值或赋一个平均值)，C4.5给出了一个很优雅的方式，为什么说优雅，这样讲吧！我们每一个特征的取值都有若干个，根据训练集每个可能的取值都有一个概率，我们用这个概率来表示这个确实值得可能取值。这样就显得很合理了。
C4.5各方面完胜ID3，所以C4.5一出现就被广泛应用，后面为了解决这个算法的时间开销问题，推出了这个算法的改进版C5.0。国外有一篇比较C4.5和C5.0性能的blog写的很好，可以搜一下。大体上C5.0的速度是C4.5的10倍以上。
使用基尼指数的回归树
CART树既可以用于分类问题也可以用于回归问题，用于分类问题的思想和我们上面介绍的ID3，C4.5其实是一样的，唯一的不同就是CART树用的是基尼指数来确定最优划分点的。
基尼指数:
基尼指数的通俗解释就是：表示一件事物的不确定性，基尼指数越大不确定性越大。我们要找基尼指数小的特征，这样的特征对于划分数据集的准确性会更高(不确定性低嘛)
类似的有一个条件基尼指数：
对于回归问题：
首先简单描述一下决策树处理回归问题的流程：
对于一个数据集我们可以将其分为m个子区间(R1,R2......Rm)对于每一区间我们可以产生一个对应的输出cm。对于一个给定的回归树我们用平方误差来表示每个单元的损失，那么我们每个单元的最优输出就是使该单元的损失函数最小。
对于回归问题，我们面临的问题也是如何确定划分点(决策树的核心)。这里CART树的处理方式和C4.5处理连续变量的方式有点类似。
这里我们必须强调一下，我们在使用决策树寻找每一步的最优切分点时，常用的是贪心算法，贪心算法有一个问题就是局部最优，而不是全局最优。所以我们一定要记住，决策树在选择特征及切分点时考虑的是一个局部最优问题。
剪枝
决策树的剪枝就是最大程度的保证泛化能力。
我们的优化目标就是保证树的整体不确定性尽量低，同时树模型的复杂度也要低。
思路，分析如何降低树整体的损失函数：
1.减少第一部分树的不确定性：我们可以增加一些特征，增加特征，意味着约束条件变强了，决策树的分类效果自然而然的会变好。但是对于给定的数据集我们是很难再继续添加新特征了，所以这个方式虽然可取但不可行。
2.减少第二部分树的整体复杂度：我们需要对生成的树进行剪枝。剪枝完后树的规模剪小了，但是树整体的不确定性可能会增大，这时我们就要寻找一个比较优雅的剪枝策略，在降低树模型复杂度的情况下，尽量小的增加树的不确定性。
上图，所有叶子节点的熵加权求和得到误差评价函数C(T)。
α 用来平衡误差评价函数和树的大小。
剪枝方法
第二种方式讲解：
小写的tr相当于把大写Tr的大树拆成一个小树，所以小tr的误差要大。
脑图：
随机森林
次优树是Gini指数评估的CART树。不需要剪枝了，弄很多树，对结果投票，通常树的数目是奇数。
随机森林是一种应用很广泛的方法。
随机森林不用交叉验证。OOB错误率：oob误分率是随机森林泛化误差的一个无偏估计，它的结果近似于需要大量计算的k折交叉验证。
具体步骤：对于已经生成的随机森林,用袋外数据测试其性能,假设袋外数据总数为O,用这O个袋外数据作为输入,带进之前已经生成的随机森林分类器,分类器会给出O个数据相应的分类,因为这O条数据的类型是已知的,则用正确的分类与随机森林分类器的结果进行比较,统计随机森林分类器分类错误的数目,设为X,则袋外数据误差大小=X/O;这已经经过证明是无偏估计的,所以在随机森林算法中不需要再进行交叉验证或者单独的测试集来获取测试集误差的无偏估计。
脑图：