一. 决策树

1.1决策树概述

决策树既能做分类，又能做回归。
输入数据后，根据构建的树，逐步向下决策，最后得到结果。
决策树算法以树状结构表示数据分类的结果，每个决策点 实现一个具有离散输出的测试函数，记为分支。
决策树由以下几部分组成：

决策树通常划分为两个阶段：

• 训练阶段
  从给定的训练数据集中，构造出一棵决策树
• 分类阶段
  从根节点开始，按照决策树的分类属性逐层往下划分，直到叶结点，获得概念（决策、分类）结果。

1.2决策树-熵

对于下图中的决策树，有个疑问，就是为什么第一个选择是“年龄”这个特征，我选择“长相”特征作为第一分类的标准可以嘛？下面我们就对构建决策树选择特征的问题进行讨论

熵代表信息的不确定性，信息的不确定性越大，熵越大；比如“明天太阳从东方升起”这一句话代表的信息我们可以认为为0；因为太阳从东方升起是个特定的规律，我们可以把这个事件的信息熵约等于0；说白了，信息熵和事件发生的概率成反比：数学上把信息熵定义如下：

1.3 决策树-基本想法

构造树的基本想法是随着树深度的增加，节点的熵迅速地降低。
熵降低的速度越快越好，这样我们有望得到一颗高度最矮的决策树。
举个例子：
现在我们有四个特征 outlook、temperature、humidity、windy，用这四个特征来预测play，很明显是个分类问题。

要解决这个问题，首先我们要构建一个决策树，那我们该选择哪个特征当作根节点呢？
1.在没有给定任何天气信息时，根据历史数据，也就是统计yes、no的数量，我们得知，新的一天打球的概率为9/14，不打的概率为5/14。
此时的熵为：

2.我们可以根据每个特征进行一下划分：

接下来要对这些属性都进行一下尝试：


综上，信息增益越大越好，使得信息增益最大的属性，就当做根节点。
根节点选出来了，接下来的节点怎么选择呢？

上面的这种方法就是ID3方法
注：对于那些存在很多属性，但是每个属性对应的样本个数很少的特征，我们该怎样解决呢？
对于这样的特征我们需要使用C4.5
信息增益率（C4.5）：就是用求得的信息增益==/==一个自身的熵值。
当然还有GiNi系数方法，也可以解决决策树的分类特征选择问题。

那我们该怎样评价我们决策树的好坏呢？
这里可以用评价函数来评价。。。。。

H（t）：当前叶子节点的熵值或GiNi系数值
N_t：当前叶子结点的样本数

当我们面临的特征值不再是单纯的离散值，而是连续值，如年龄，我们又该如何处理呢？
显然我们就需要把连续型属性离散化，一句分裂点的熵值，把连续型属性的值分成不同的区间。

1.4 决策树-剪枝

剪枝其实就是为了防止过拟合

• 预剪枝：在构建决策树的过程中，提前停止
• 后剪枝：决策树构建好后，然后才开始裁剪
  对于后剪枝操作，我们需要比较其剪枝前后评价函数的大小
  eg：X[2]
  

二.随机森林

2.1概念

2.1.1 Bootstraping

Bootstraping 是一种有放回的采样方式
何为有放回呢？
现在有一个集合{1,2,3,4,5,6,7,8,9,10}，每次在集合中取值，有放回就是第一次取了1，接下来的几次还可以取到1。
随机森林顾名思义，是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类；对于回归问题，就是去所有预测值的平均。
接下来说一下什么是随机
可以把随机森林的随机看成双重的随机，一个是数据选择的随机，就是不选全部的数据，而是按有放回选择一定比例的数据；另一个就是特征选择的随机，就是按比例选取特征。