RF是一种基于bagging的机器学习方法,通过某种规则综合多个弱分类器的分类结果,比如投票(对于分类问题)、加权(对于回归问题),得到一个比较理想的强分类器。在RF中采用的弱分类器是一颗颗决策树,所以让我们从决策树开始说起。
决策树(DT)
首先,DT是一种树形结构,树中的每个分支表示属性组中的某个属性的一种取值。如何构建DT?DT学习是一种无回溯的贪心过程。对于给定的属性组和待预测变量,DT学习会每次从属性组中选取"与待预测变量关联最大的属性"(贪心),根据该属性的不同取值生成树分支,并且已经被选中过的属性将在后面的决策过程中不再被考虑(无回溯)。
了解了决策树的整体思想,那么通过哪种方式找到的"与待预测变量关联最大的属性"才是合理的?换句话说,”属性与预测变量之间的关联度“在数学上怎么计算?这个问题,其实也就是现在比较常见的几种决策树算法之间的最大区别。
天气 | 温度 | 湿度 | 大风 | 去玩 |
晴天 | 热 | 高 | 否 | 否 |
晴天 | 热 | 高 | 是 | 否 |
多云 | 热 | 高 | 否 | 是 |
下雨 | 适度 | 高 | 否 | 是 |
下雨 | 冷 | 适度 | 否 | 是 |
下雨 | 冷 | 适度 | 是 | 否 |
多云 | 冷 | 适度 | 是 | 是 |
晴天 | 适度 | 高 | 否 | 否 |
晴天 | 冷 | 适度 | 否 | 是 |
下雨 | 适度 | 适度 | 否 | 是 |
晴天 | 适度 | 适度 | 是 | 是 |
多云 | 适度 | 高 | 是 | 是 |
多云 | 热 | 适度 | 否 | 是 |
下雨 | 适度 | 高 | 是 | 否 |
信息熵
ID3算法
信息增益
C4.5算法
信息增益率
CART算法
纯度
完全生长的决策树停止条件
节点上的所有样本具有相同的标记
属性组里面所有的属性都已经被选取过了
训练误差:对应于停止条件二,具体表现为多个样本的属性组值完全相同,但是标记却不同
测试误差:一般比训练误差大,如果测试误差远大于训练误差,说明存在过拟合
过拟合
原因:训练数据集存在噪声
优化方案
剪枝
前置剪枝——定义合适的停止条件
后置剪枝——先生成完全生长的决策树,在剪去关联性不强的分支,主要方法有卡方检验
随机森林
假设现在有一个训练集,其中训练样本的个数为
,每个样本由特征集
和标记
组成,其中特征的个数为
,随机森林的训练过程如下:
从训练集X中有放回的随机选择与总体样本数量相同的个样本作为新的样本集训练决策树
在训练决策树的过程中,节点每次分裂时随机从特征集中选
个特征,在这
个特征中选择一个分裂,提出者在论文中使用CART树
重复节点的分裂,生成完全生长的决策树
重复步骤1~步骤3 k次,则生成k颗决策树,最终的结果由这些决策树投票得出
原文:http://www.cnblogs.com/summerautumn/p/5128486.html