熟悉算法 -- 随机森林

本贴最后更新于 2637 天前,其中的信息可能已经时过境迁

随机森林算法原理(一)

随机森林是用随机的方式建立一个森林,森林里面有很多的决策树组成,随机森林的每一棵决策树之间是没有关联的。在得到森林之后,当有一个新的输入样本进入的时候,就让森林中的每一棵决策树分别进行一下判断,看看这个样本应该属于哪一类,然后看看哪一类被选择最多,就预测这个样本为那一类。
在建立每一棵决策树的过程中,有两点需要注意采样与完全分裂。首先是两个随机采样的过程,random forest 对输入的数据要进行行、列的采样。对于行采样,采用有放回的方式,也就是在采样得到的样本集合中,可能有重复的样本。假设输入样本为 N 个,那么采样的样本也为 N 个。这样使得在训练的时候,每一棵树的输入样本都不是全部的样本,使得相对不容易出现 over-fitting。然后进行列采样,从 M 个 feature 中,选择 m 个(m << M)。之后就是对采样之后的数据使用完全分裂的方式建立出决策树,这样决策树的某一个叶子节点要么是无法继续分裂的,要么里面的所有样本的都是指向的同一个分类。由于之前的两个随机采样的过程保证了随机性,所以就算不剪枝,也不会出现 over-fitting,当层数较低的时候。

随机森林原理和步骤(二):

随机森林,指的是利用多棵树对样本进行训练并预测的一种分类器。简单来说,随机森林就是由多棵 CART(Classification And Regression Tree)构成的。对于每棵树,它们使用的训练集是从总的训练集中有放回采样出来的,这意味着,总的训练集中的有些样本可能多次出现在一棵树的训练集中,也可能从未出现在一棵树的训练集中。在训练每棵树的节点时,使用的特征是从所有特征中按照一定比例随机地无放回的抽取的,根据 Leo Breiman 的建议,假设总的特征数量为 M,这个比例可以是 sqrt(M),1/2sqrt(M),2sqrt(M)。
1: 随机森林的 训练过程 如下:
(1)给定训练集 S,测试集 T,特征维数 F。确定参数:使用到的 CART 的数量 t,每棵树的深度 d,每个节点使用到的特征数量 f,终止条件:节点上最少样本数 s,节点上最少的信息增益 m;
对于第 1-t 棵树 i:
(2)从 S 中有放回的抽取大小和 S 一样的训练集 S(i),随机的选择作为根节点的样本,从根节点开始训练
(3)如果当前节点上达到终止条件,则设置当前节点为叶子节点,如果是分类问题,该叶子节点的预测输出为当前节点样本集合中数量最多的那一类 c(j),概率 p 为 c(j)占当前样本集的比例;如果是回归问题,预测输出为当前节点样本集各个样本值的平均值。然后继续训练其他节点。如果当前节点没有达到终止条件,则从 F 维特征中无放回的随机选取 f 维特征。利用这 f 维特征,寻找分类效果最好的一维特征 k 及其阈值 th,当前节点上样本第 k 维特征小于 th 的样本被划分到左节点,其余的被划分到右节点。继续训练其他节点。有关分类效果的评判标准在后面会讲。
(4)重复(2)(3)直到所有节点都训练过了或者被标记为叶子节点。
(5)重复(2),(3),(4)直到所有 CART 都被训练过。

2:随机森林的 预测过程 如下:
对于第 1-t 棵树 i:
(1)从当前树的根节点开始,根据当前节点的阈值 th,判断是进入左节点(<th)还是进入右节点(>=th),直到到达,某个叶子节点,并输出预测值。
(2)重复执行(1)直到所有 t 棵树都输出了预测值。如果是分类问题,则输出为所有树中预测概率总和最大的那一个类,即对每个 c(j)的 p 进行累计;如果是回归问题,则输出为所有树的输出的平均值。
注:有关分类效果的评判标准,因为使用的是 CART,因此使用的也是 CART 的平板标准,和 C3.0,C4.5 都不相同。

对于分类问题(将某个样本划分到某一类),也就是离散变量问题,CART 使用 Gini值 作为评判标准。定义为 Gini=1-∑(P(i)*P(i)),P(i)为当前节点上数据集中第 i 类样本的比例。例如:分为 2 类,当前节点上有 100 个样本,属于第一类的样本有 70 个,属于第二类的样本有 30 个,则 Gini=1-0.7×07-0.3×03=0.42,可以看出,类别分布越平均,Gini值越大,类分布越不均匀,Gini值越小,在寻找最佳的分类特征和阈值时。
1:评判标准为:argmax(Gini-GiniLeft-GiniRight),即寻找最佳的特征 f 和阈值 th,使得当前节点的 Gini 值减去左子节点的 Gini 和右子节点的 Gini 值最大。
2:对于回归问题,相对更加简单,直接使用 argmax(Var-VarLeft-VarRight)作为评判标准,即当前节点训练集的方差 Var 减去减去左子节点的方差 VarLeft 和右子节点的方差 VarRight 值最大。

Random Forest与Bagging的区别 在于:Bagging 每次生成决策树的时候从全部的属性 Attributes 里面选择,而 Random Forest 是随机从全部 Attributes 的集合里面生成一个大小固定的子集,相对而言需要的计算量更小一些。 == TODO bagging

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • uTools

    uTools 是一个极简、插件化、跨平台的现代桌面软件。通过自由选配丰富的插件,打造你得心应手的工具集合。

    7 引用 • 27 回帖
  • DevOps

    DevOps(Development 和 Operations 的组合词)是一组过程、方法与系统的统称,用于促进开发(应用程序/软件工程)、技术运营和质量保障(QA)部门之间的沟通、协作与整合。

    56 引用 • 25 回帖 • 5 关注
  • IPFS

    IPFS(InterPlanetary File System,星际文件系统)是永久的、去中心化保存和共享文件的方法,这是一种内容可寻址、版本化、点对点超媒体的分布式协议。请浏览 IPFS 入门笔记了解更多细节。

    21 引用 • 245 回帖 • 232 关注
  • 安装

    你若安好,便是晴天。

    132 引用 • 1184 回帖
  • Latke

    Latke 是一款以 JSON 为主的 Java Web 框架。

    71 引用 • 535 回帖 • 816 关注
  • 电影

    这是一个不能说的秘密。

    122 引用 • 608 回帖 • 1 关注
  • WiFiDog

    WiFiDog 是一套开源的无线热点认证管理工具,主要功能包括:位置相关的内容递送;用户认证和授权;集中式网络监控。

    1 引用 • 7 回帖 • 603 关注
  • jQuery

    jQuery 是一套跨浏览器的 JavaScript 库,强化 HTML 与 JavaScript 之间的操作。由 John Resig 在 2006 年 1 月的 BarCamp NYC 上释出第一个版本。全球约有 28% 的网站使用 jQuery,是非常受欢迎的 JavaScript 库。

    63 引用 • 134 回帖 • 735 关注
  • 国际化

    i18n(其来源是英文单词 internationalization 的首末字符 i 和 n,18 为中间的字符数)是“国际化”的简称。对程序来说,国际化是指在不修改代码的情况下,能根据不同语言及地区显示相应的界面。

    8 引用 • 26 回帖
  • frp

    frp 是一个可用于内网穿透的高性能的反向代理应用,支持 TCP、UDP、 HTTP 和 HTTPS 协议。

    20 引用 • 7 回帖 • 3 关注
  • RESTful

    一种软件架构设计风格而不是标准,提供了一组设计原则和约束条件,主要用于客户端和服务器交互类的软件。基于这个风格设计的软件可以更简洁,更有层次,更易于实现缓存等机制。

    30 引用 • 114 回帖 • 4 关注
  • OnlyOffice
    4 引用 • 24 关注
  • Laravel

    Laravel 是一套简洁、优雅的 PHP Web 开发框架。它采用 MVC 设计,是一款崇尚开发效率的全栈框架。

    20 引用 • 23 回帖 • 738 关注
  • Quicker

    Quicker 您的指尖工具箱!操作更少,收获更多!

    36 引用 • 155 回帖 • 1 关注
  • Postman

    Postman 是一款简单好用的 HTTP API 调试工具。

    4 引用 • 3 回帖 • 4 关注
  • 开源中国

    开源中国是目前中国最大的开源技术社区。传播开源的理念,推广开源项目,为 IT 开发者提供了一个发现、使用、并交流开源技术的平台。目前开源中国社区已收录超过两万款开源软件。

    7 引用 • 86 回帖
  • 音乐

    你听到信仰的声音了么?

    61 引用 • 512 回帖
  • Sym

    Sym 是一款用 Java 实现的现代化社区(论坛/BBS/社交网络/博客)系统平台。

    下一代的社区系统,为未来而构建

    524 引用 • 4601 回帖 • 698 关注
  • 职场

    找到自己的位置,萌新烦恼少。

    127 引用 • 1707 回帖
  • Firefox

    Mozilla Firefox 中文俗称“火狐”(正式缩写为 Fx 或 fx,非正式缩写为 FF),是一个开源的网页浏览器,使用 Gecko 排版引擎,支持多种操作系统,如 Windows、OSX 及 Linux 等。

    7 引用 • 30 回帖 • 401 关注
  • OAuth

    OAuth 协议为用户资源的授权提供了一个安全的、开放而又简易的标准。与以往的授权方式不同之处是 oAuth 的授权不会使第三方触及到用户的帐号信息(如用户名与密码),即第三方无需使用用户的用户名与密码就可以申请获得该用户资源的授权,因此 oAuth 是安全的。oAuth 是 Open Authorization 的简写。

    36 引用 • 103 回帖 • 27 关注
  • flomo

    flomo 是新一代 「卡片笔记」 ,专注在碎片化时代,促进你的记录,帮你积累更多知识资产。

    6 引用 • 140 回帖
  • Hprose

    Hprose 是一款先进的轻量级、跨语言、跨平台、无侵入式、高性能动态远程对象调用引擎库。它不仅简单易用,而且功能强大。你无需专门学习,只需看上几眼,就能用它轻松构建分布式应用系统。

    9 引用 • 17 回帖 • 617 关注
  • OpenStack

    OpenStack 是一个云操作系统,通过数据中心可控制大型的计算、存储、网络等资源池。所有的管理通过前端界面管理员就可以完成,同样也可以通过 Web 接口让最终用户部署资源。

    10 引用 • 2 关注
  • Access
    1 引用 • 3 回帖 • 5 关注
  • SendCloud

    SendCloud 由搜狐武汉研发中心孵化的项目,是致力于为开发者提供高质量的触发邮件服务的云端邮件发送平台,为开发者提供便利的 API 接口来调用服务,让邮件准确迅速到达用户收件箱并获得强大的追踪数据。

    2 引用 • 8 回帖 • 488 关注
  • B3log

    B3log 是一个开源组织,名字来源于“Bulletin Board Blog”缩写,目标是将独立博客与论坛结合,形成一种新的网络社区体验,详细请看 B3log 构思。目前 B3log 已经开源了多款产品:SymSoloVditor思源笔记

    1063 引用 • 3455 回帖 • 165 关注