随机森林及CART的算法课件.ppt

1、 随机森林的基本思想：随机森林的基本思想： 通过自助法通过自助法(boot-strap)(boot-strap)重采样技术重采样技术, ,不断不断生成训练样本和测试样本生成训练样本和测试样本, ,由训练样本生成多个分由训练样本生成多个分类树组成随机森林类树组成随机森林, ,测试数据的分类结果按分类树测试数据的分类结果按分类树投票多少形成的分数而定。投票多少形成的分数而定。 随机森林有两个重要参数：随机森林有两个重要参数： 一是树节点预选的变量个数；一是树节点预选的变量个数； 二是随机森林中树的个数。二是随机森林中树的个数。随机森林随机森林 AdaBoosting(Adaptive Boosti

2、ng) 对每个样本赋予一个权重，代表该样本被当前分类器选入训练集的概率，并根据预测函数的输出与期望输出的差异调整权重：如某个样本点已被正确分类，则它的权重减小，否则，它的权重增大；通过这种方式，使得学习算法能集中学习较难判别的样本。 经过T轮训练，得到T个分类函数 f1,f2,fT及对应的权重1, 2, T，最终的分类规则为加权投票法 Bagging(Breiman,1996) 在训练的每一轮中，均从原始样本集S中有放回地随机抽取训练样本集T（T的样本个数同S），这样一个初始样本在某轮训练中可能出现多次或根本不出现（ S中每个样本未被抽取的概率为(1-1/|S|)|S|0.368，当|S|很大

3、时）。 最终的分类规则为简单多数投票法或简单平均法随机森林算法 随机森林算法是Leo Breiman于2001年提出的一种新型分类和预测模型,它具有需要调整的参数较少、不必担心过度拟合、分类速度很快, 能高效处理大样本数据、能估计哪个特征在分类中更重要以及较强的抗噪音能力等特点, 因此, 在基因芯片数据挖掘、代谢途径分析及药物筛选等生物学领域得到应用并取得了较好的效果。该方法是基于决策树（decision tree） 的分类器集成算法。 自助法重采样 在统计量重采样技术中，一种新方法是自助法（bootstrap）。自助法是从原始的样本容量为N的训练样本集合中随机抽取N个样本生成新的训练样本集，

4、抽样方法为有放回抽样，这样重新采样的数据集不可避免地存在着重复的样本。独立抽样k次，生成k个相互独立的自助样本集。随机森林算法基本原理 随机森林是通过一种新的自助法重采样技术生成很多个树分类器, 其步骤如下：1. 从原始训练数据中生成个自助样本集, 每个自助样本集是每棵分类树的全部训练数据。2. 每个自助样本集生长为单棵分类树。在树的每个节点处从个特征中随机挑选个特征 （）, 按照节点不纯度最小的原则从这个特征中选出一个特征进行分支生长。这棵分类树进行充分生长, 使每个节点的不纯度达到最小, 不进行通常的剪枝操作。 根据生成的多个树分类器对新的数据进行预测,分类结果按每个树分类器的投票多少而定

5、。 随机森林通过在每个节点处随机选择特征进行分支，最小化了各棵分类树之间的相关性，提高了分类精确度。因为每棵树的生长很快，所以随机森林的分类速度很快，并且很容易实现并行化。 森林中单颗树的分类强度（Strength）：每颗树的分类强度越大，则随机森林的分类性能越好。 森林中树之间的相关度（Correlation）：树之间的相关度越大，则随机森林的分类性能越差。 CART是L.Breiman等人在1984 年提出的决策树算法，其原理与ID3相似，在CART中提出了杂度削减的概念，按杂度削减最大分裂节点生长决策树，与ID3不同的是，CART最终生成二叉树，然后利用重采技术进行误差估计和树剪枝，然后

6、选择最优作为最终构建的决策树。这些算法均要求训练集全部或一部分在分类的过程中一直驻留在内存中。12v首先找出最有判别力的属性，把样例分成多个子集，每个子集又选择最有判别力的属性进行划分，一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树。vJ.R.Quinlan的工作主要是引进了信息论中的 信 息 增 益 ， 他 将 其 称 为 信 息 增 益（information gain），作为属性判别能力的度量，设计了构造决策树的递归算法。13二、二、ID3算法算法 对当前例子集合，计算各属性的信息增益； 选择信息增益最大的属性Ak； 把在Ak处取值相同的例子归于同一子集，Ak取几个值就得

7、几个子集； 对既含正例又含反例的子集，递归调用建树算法； 若子集仅含正例或反例，对应分枝标上P或N，返回调用处。ID3在建树时，每个节点仅含一个属性，是一种单变元的算法，属性间的相关性强调不够。虽然它将多个属性用一棵树连在一起，但联系还是松散的。14 （4）ID3对噪声较为敏感。关于什么是噪声，Quinlan的定义是训练例子中的错误就是噪声。它包含两方面，一是属性值取错，二是类别给错。当训练集增加时，ID3的决策树会随之变化。在建树过程中，各属性的信息增益会随例子的增加而改变，从而使决策树也变化。这对渐近学习（即训练例子不断增加）是不方便的。 二元划分 二叉树不易产生数据碎片，精确度往往也会高

8、于多叉树，所以在CART算法中，采用了二元划分 不纯性度量 分类目标：Gini指标、Towing、order Towing 连续目标：最小平方残差、最小绝对残差 剪枝： 用独立的验证数据集对训练集生长的树进行剪枝 样本： (X, y) y为分类 = 分类树 y为实数 = 回归树 设t代表树的某个节点，t中的样本集合为：(X1,y1), (X2,y2) ，应变量为实数，N(t)是节点t中的样本个数。节点t的应变量的均值： 节点t内的平方残差最小化 (squared residuals minimization algorithm)：( )1,1( )iN tiiXtyyN t( )21,( )(

9、 )iN tiiXtSS tyy tCART_regression(DataSet, featureList, alpha, delta)： 创建根节点R 如果当前DataSet中的数据的值都相同，则标记R的值为该值 如果最大的phi值小于设定阈值delta，则标记R的值为DataSet应变量均值 如果其中一个要产生的节点的样本数量小于alpha，则不再分解，标记R的值为DataSet应变量均值CART 方法是由Breiman 等人在1984 年提出的一种决策树分类方法2。其采用基于最小距离的基尼指数估计函数, 这是因为基尼指数可以单独考虑子数据集中类属性的分布情况, 用来决定由该子数据集生成

10、的决策树的拓展形状。CART 创建简单二叉树结构对新事例进行分类, 这样可以有效地处理缺失数据, 尤其对于分类与预测时更好。并且CART方法中有贝叶斯分类的特征, 使用者可以提供主观的分类先验概率作为选择分类的权重, 则CART 在获得最终选择树前使用交叉检验来评估候选树的误分类率, 这对分析复杂样本数据非常有用。CART 处理离散变量与连续变量同样容易, 这是由于它使用了或形状的几乎不依靠无关变量的分支。而且, 被CART 考虑到的分支在任何单调转换下是不变的,如对一个或更多的特征取对数、平方根等都是不变的。CART (Classification and Regression Tree,

11、CART)二叉树由根结点, 中间结点和叶( 终) 结点组成。每个 CART 有良好的优越性, 但是, 并不是说在任何 情况下CART 方法都好。对于许多数据集, CART 方 法产生的树并不稳定。训练样本集的一点轻微改变 都可能完全改变树的结构, 这些特点存在于具有显 著相关特征的数据集中。在CART 中, 问题就转换为 在单个结点处存在几个分支, 而这几个分支在减少 子结点的所有复杂度方面几乎是等价的。从而一个 特定的分支选择是比较随意的, 但是它将导致更多 可能不同的树。这种不稳定性意味着使用者必须十分清楚由CART 产生的树中特定特征的充分解释。另 一方面, 这一特点暗含着具有相似判别能力的不同树 的有用性, 它允许通过树的使用改变特征的选择。CART的全称是分类和回归树，既可以做分类算法，也可以做回归。决策树的优缺点：优点：1.可以生成可以理解的规则。2.计算量相对来说不是很大。3.可以处理连续和种类字段。4.决策树可以清晰的显示哪些字段比较重要缺点：1. 对连续性的字段比较难预测。2.对有时间顺序的数据，需要很多预处理的工作。3.当类别太多时，错误可能就会增加的比较快。4.一般的算法分类的时候，只是根据一个字段来分类。