熟悉算法 -- 随机森林

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

随机森林算法原理(一)

随机森林是用随机的方式建立一个森林,森林里面有很多的决策树组成,随机森林的每一棵决策树之间是没有关联的。在得到森林之后,当有一个新的输入样本进入的时候,就让森林中的每一棵决策树分别进行一下判断,看看这个样本应该属于哪一类,然后看看哪一类被选择最多,就预测这个样本为那一类。
在建立每一棵决策树的过程中,有两点需要注意采样与完全分裂。首先是两个随机采样的过程,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

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • B3log

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

    1063 引用 • 3455 回帖 • 167 关注
  • 服务器

    服务器,也称伺服器,是提供计算服务的设备。由于服务器需要响应服务请求,并进行处理,因此一般来说服务器应具备承担服务并且保障服务的能力。

    125 引用 • 585 回帖
  • Dubbo

    Dubbo 是一个分布式服务框架,致力于提供高性能和透明化的 RPC 远程服务调用方案,是 [阿里巴巴] SOA 服务化治理方案的核心框架,每天为 2,000+ 个服务提供 3,000,000,000+ 次访问量支持,并被广泛应用于阿里巴巴集团的各成员站点。

    60 引用 • 82 回帖 • 611 关注
  • Wide

    Wide 是一款基于 Web 的 Go 语言 IDE。通过浏览器就可以进行 Go 开发,并有代码自动完成、查看表达式、编译反馈、Lint、实时结果输出等功能。

    欢迎访问我们运维的实例: https://wide.b3log.org

    30 引用 • 218 回帖 • 639 关注
  • Outlook
    1 引用 • 5 回帖 • 2 关注
  • 反馈

    Communication channel for makers and users.

    125 引用 • 929 回帖 • 265 关注
  • SOHO

    为成为自由职业者在家办公而努力吧!

    7 引用 • 55 回帖 • 3 关注
  • SEO

    发布对别人有帮助的原创内容是最好的 SEO 方式。

    35 引用 • 200 回帖 • 17 关注
  • 钉钉

    钉钉,专为中国企业打造的免费沟通协同多端平台, 阿里巴巴出品。

    15 引用 • 67 回帖 • 293 关注
  • RIP

    愿逝者安息!

    8 引用 • 92 回帖 • 394 关注
  • GitLab

    GitLab 是利用 Ruby 一个开源的版本管理系统,实现一个自托管的 Git 项目仓库,可通过 Web 界面操作公开或私有项目。

    46 引用 • 72 回帖 • 1 关注
  • Tomcat

    Tomcat 最早是由 Sun Microsystems 开发的一个 Servlet 容器,在 1999 年被捐献给 ASF(Apache Software Foundation),隶属于 Jakarta 项目,现在已经独立为一个顶级项目。Tomcat 主要实现了 JavaEE 中的 Servlet、JSP 规范,同时也提供 HTTP 服务,是市场上非常流行的 Java Web 容器。

    162 引用 • 529 回帖 • 6 关注
  • Sphinx

    Sphinx 是一个基于 SQL 的全文检索引擎,可以结合 MySQL、PostgreSQL 做全文搜索,它可以提供比数据库本身更专业的搜索功能,使得应用程序更容易实现专业化的全文检索。

    1 引用 • 213 关注
  • Spark

    Spark 是 UC Berkeley AMP lab 所开源的类 Hadoop MapReduce 的通用并行框架。Spark 拥有 Hadoop MapReduce 所具有的优点;但不同于 MapReduce 的是 Job 中间输出结果可以保存在内存中,从而不再需要读写 HDFS,因此 Spark 能更好地适用于数据挖掘与机器学习等需要迭代的 MapReduce 的算法。

    74 引用 • 46 回帖 • 568 关注
  • React

    React 是 Facebook 开源的一个用于构建 UI 的 JavaScript 库。

    192 引用 • 291 回帖 • 379 关注
  • sts
    2 引用 • 2 回帖 • 222 关注
  • Quicker

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

    36 引用 • 155 回帖 • 2 关注
  • Rust

    Rust 是一门赋予每个人构建可靠且高效软件能力的语言。Rust 由 Mozilla 开发,最早发布于 2014 年 9 月。

    58 引用 • 22 回帖 • 1 关注
  • Vim

    Vim 是类 UNIX 系统文本编辑器 Vi 的加强版本,加入了更多特性来帮助编辑源代码。Vim 的部分增强功能包括文件比较(vimdiff)、语法高亮、全面的帮助系统、本地脚本(Vimscript)和便于选择的可视化模式。

    29 引用 • 66 回帖 • 1 关注
  • NGINX

    NGINX 是一个高性能的 HTTP 和反向代理服务器,也是一个 IMAP/POP3/SMTP 代理服务器。 NGINX 是由 Igor Sysoev 为俄罗斯访问量第二的 Rambler.ru 站点开发的,第一个公开版本 0.1.0 发布于 2004 年 10 月 4 日。

    315 引用 • 547 回帖 • 3 关注
  • 数据库

    据说 99% 的性能瓶颈都在数据库。

    345 引用 • 724 回帖
  • Shell

    Shell 脚本与 Windows/Dos 下的批处理相似,也就是用各类命令预先放入到一个文件中,方便一次性执行的一个程序文件,主要是方便管理员进行设置或者管理用的。但是它比 Windows 下的批处理更强大,比用其他编程程序编辑的程序效率更高,因为它使用了 Linux/Unix 下的命令。

    124 引用 • 74 回帖
  • 博客

    记录并分享人生的经历。

    273 引用 • 2388 回帖
  • BookxNote

    BookxNote 是一款全新的电子书学习工具,助力您的学习与思考,让您的大脑更高效的记忆。

    笔记整理交给我,一心只读圣贤书。

    1 引用 • 1 回帖
  • Sandbox

    如果帖子标签含有 Sandbox ,则该帖子会被视为“测试帖”,主要用于测试社区功能,排查 bug 等,该标签下内容不定期进行清理。

    425 引用 • 1250 回帖 • 598 关注
  • C++

    C++ 是在 C 语言的基础上开发的一种通用编程语言,应用广泛。C++ 支持多种编程范式,面向对象编程、泛型编程和过程化编程。

    107 引用 • 153 回帖
  • 京东

    京东是中国最大的自营式电商企业,2015 年第一季度在中国自营式 B2C 电商市场的占有率为 56.3%。2014 年 5 月,京东在美国纳斯达克证券交易所正式挂牌上市(股票代码:JD),是中国第一个成功赴美上市的大型综合型电商平台,与腾讯、百度等中国互联网巨头共同跻身全球前十大互联网公司排行榜。

    14 引用 • 102 回帖 • 321 关注