【经典算法】随机森林

之前都是弄深度学习，没想到工作后，没有找到和深度学习强相关的，机器学习还是在客户那边挺认可，就学习一下机器学习里的知识咯。

决策树

讲随机森林，怎么也绕不开决策树，因为森林嘛，森林就是由树构成的，那就先看看树是怎么形成的。

决策树，看名字就是帮助我们决策的，大都是用在分类里。就比如西瓜书里，爱举啥样的西瓜是好的，我觉得这个过程就是把我们认可的分类经验一步步翻译成计算机可阅读的语言，但是光看规则的话，怎么也都能划分好（比如我给的限定条件越来越多，就差报身份证号了），但是如何用最短的规则去划分好，这就是比较有挑战的。还好大牛们已经给我们想了好多算法，来衡量决策树到底怎么画。

比如我们就有下面这个表格的数据，该怎么生成一颗决策树呢？

性别	年龄	职业	是否喜欢看电影
女	46	医生	是
男	37	学生	是
女	23	程序员	否
女	49	律师	是
男	21	教师	是

1. 选一个节点判断条件。比如选中了性别，可以把数据集分成男的一堆，女的一堆
2. 分别在男、女两堆里再选别的节点（性别这个特征用过了就不能再用了），再分
3. 重复1，2 两步，直到子集里只包含单一特征，则为分支叶子节点

总结起来就是从根节点开始，对特征进行测试，然后根据测试结果将数据集划分为两个子集，每个子集对应一个分支。这个过程在树的每个节点重复进行，直到达到叶子节点。叶子节点通常代表一个类别或决策结果。

那么问题来了，我怎么选这个节点判断条件划分数据呢？

不同的决策树算法有不同的特征选择准则。例如，ID3算法使用信息增益作为特征选择的标准，C4.5算法使用增益率，而CART算法使用基尼指数。这些准则的目的都是为了找到一个能够最大程度地将数据集划分为纯度较高的子集的特征。

那这个衡量的标准到底是怎么个事儿？

信息量

当一个事情发生的概率越小，那么它的信息量就越大，那就找个概率越小值越大的公式。

下面这个公式就是当$X=x_0$时，它的信息量多少。

$I(x_0)=?log(p(x_0))$

信息熵

信息是不确定性的解 – 克劳德·香农(Claude Shannon)

我的理解就是把这个事情发生的期望信息量给算出来，熵越大，不确定性就越大，公式如下：

$H(X)=?{\sum }_{i=0}^{n}p(x_i)log(p(x_i))$

一个事情发生的类别表现，如果概率相同，而且类别又多，那么熵就是最大的。

信息增益

一个事情原始的熵是所有类别的信息量期望，如果我能把这个事情发生的类别按照某个属性去将类别分开，那么分开后的信息熵和没分开之前的信息熵的差距就是信息增益。

一般就是数据集分类问题，比如说一个班里有50个小朋友，男生25个，女生25个。随机拿出来一个为女孩的概率就是50%。如果我按照他们是否去男厕所的属性划分，那么这个随机给我一个小朋友，我依据他/她是否去了男厕所很容易地分清楚，到底是男是女。这个信息增益就很大。

公式如下：

$Gain(D,a)=H(D)?{\sum }_{v=1}^V\frac{|D^v|}{|D|}H(D^v)$

但是这个数字会收到类别的数量影响。

信息增益率

为了消除信息增益的绝对影响，用一个相对的值来衡量

$g_r=\frac{H(D)?H(D|X)}{H(X)}$

其中$H(X)$就是按照特征划分的，固有特征值。

基尼系数

在计算的时候，上面的熵什么的，对数运算特别多，所以想了个近似的衡量方法，用基尼系数来衡量。

基尼指数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。这和信息增益（率）正好相反。

基尼指数反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。

公式如下：

$Gini(D)={\sum }_{k=1}^K\frac{C_k}{D}(1?\frac{C_k}{D})=1?{\sum }_{k=1}^K(\frac{C_k}{D}{)}^2$

其实基尼系数就是熵的一阶泰勒展开式。

补充

当然还有好多智慧，比如决策树的剪枝策略、处理缺失值等等。

随机森林

在了解了上述的一些标准后，那么我们就已经知道了该如何去生成一个决策树，既然知道了，为啥还要森林呢？因为上述的一棵树泛化性不太好，所以为了防止过拟合，就多一些树。规则是一样的，怎么生成不相同的树呢？

很简单，每棵树生成的数据集不相同，特征也不相同，这样整出来的树都不一样，而且泛化性也最好。最后这么多的树出来直接投票，得票最多的就是最终结果了。

参考

熵 条件熵 交叉熵 信息增益 基尼系数
【机器学习】决策树（上）——ID3、C4.5、CART（非常详细）