Tree Based Classification 基于树的分类算法

标签: 未分类 | 发表时间:2013-11-17 12:03 | 作者:xlvector
出处:http://xlvector.net/blog

非线性分类问题向来是分类问题中最有挑战性的问题,这主要是因为线性分类问题已经可以完美的解决了。
解决非线性分类问题基本有如下的思路:

1. 多层神经网络
2. 非线性Kernel的SVM:其实是将原空间的非线性分类问题转化成了距离空间的线性分类问题
3. Mixture Model : 这种其实只能解决一类特殊的非线性分类问题,即样本分成不同的簇,而不同的簇有不同的类标
4. 决策树: 可以解决那些由于特征的组合带来的非线性问题

决策树是机器学习领域最为古老的算法之一,从最早的ID3,到C4.5再到CART。

CART诞生之后,基于单棵树的分类器已经发展到了顶峰。

决策树有一个缺陷,就是它的构建完全是基于贪心的。所以它永远也达不到最优解,特别在树的深度很深之后,这种近似就非常严重了。

贪心算法是在解一个非凸的全局优化问题的有效方法。单它只能找到一个比较好的局部最优解。为了找到更好的局部最优解,往往需要引入随机性,MCMC就是这方面的代表算法。

所以,当一棵树发展到瓶颈之后,基于多棵树的分类器就登场了。下面是一些比较著名的基于多棵树的分类器:

1. Random Forest:这个算法的思想很简单。它对数据集进行Bootstrap 采样,然后随机选取一个特征的子集,然后用CART训练出一颗树。然后重复这个过程N次,就可以得到N棵树,而最终的预测结果是这N棵树的平均值。所以,RF如果去掉随机选取特征子集,就是一个基于Bagging的树融合算法
2. GBDT:Gradient Boosting Decision Tree。这是一个基于Boosting的树融合算法,主要用来解回归问题。它的主要思想是每棵树都去学习前面的树组成的预测器的残差,直到从残差中学不到什么东西为止。

我们知道,早期的决策树有一个缺点,就是不太能够特征很多很稀疏,样本很多的数据集。比如一个问题有100万个特征,那要把所有的特征都用上,如果用一棵树的化,那么必然深度就很深,而深度深不仅带来计算复杂度和存储的问题,也会因为过分贪心而导致精度下降。而GBDT可以解决这个问题,所以GBDT甚至可以用到广告点击率预估的问题中。

相关的资源

CART http://www.stat.cmu.edu/~cshalizi/350/lectures/22/lecture-22.pdf
GBDT http://docs.salford-systems.com/GreedyFuncApproxSS.pdf
GBDT的并行实现 http://www.cslu.ogi.edu/~zak/cs506-pslc/sgradboostedtrees.pdf
RandomForest http://oz.berkeley.edu/~breiman/randomforest2001.pdf

CART 分类树的实现 https://github.com/xlvector/hector/blob/master/src/hector/cart.go
CART 回归树的实现 https://github.com/xlvector/hector/blob/master/src/hector/regression_tree.go
RandomForest 的实现 https://github.com/xlvector/hector/blob/master/src/hector/random_forest.go
GBDT 的实现 https://github.com/xlvector/hector/blob/master/src/hector/gbdt.go

您可能也喜欢:
An improved item-based KNN predictor
item-based方法无法搞定的用户
user-based和item-based算法,谁能产生多样化的结果
item-based top-N问题中的一个公式
my solutions of github contest – item based KNN
无觅

相关 [tree based classification] 推荐:

Tree Based Classification 基于树的分类算法

- - xlvector
非线性分类问题向来是分类问题中最有挑战性的问题,这主要是因为线性分类问题已经可以完美的解决了. 解决非线性分类问题基本有如下的思路:. 非线性Kernel的SVM:其实是将原空间的非线性分类问题转化成了距离空间的线性分类问题. Mixture Model : 这种其实只能解决一类特殊的非线性分类问题,即样本分成不同的簇,而不同的簇有不同的类标.

XML to tree XML 树

- Bloger - 博客园-首页原创精华区
前面发了一个 html to tree 再发一个 xml to tree. 版权所有:版权所有(C) 2009. 文件名称:xml2tree.js. 完成日期:2009-12-22. 页:http://www.chaige.net */ var XML2Tree = function (ini) {.

Django class-based view 基础

- Ken - python.cn(jobs, news)
自从Django在1.3中新增了class-based view以来,还没有仔细研究它,开始感觉这个东西是否有点多余. 因为Django已经有了Generic veiws了啊, 可是仔细看过class-based veiw之后, 这种想法打消了, 因为你完全可以用类方法实现你所有的视图, 而代码阅读起来却更容易!.

Django class-based view 深入

- Ken - python.cn(jobs, news)
上一篇我们粗略介绍了Django中的class-based view基础知识, 本篇我们继续来看关于class-based view的高级应用.. 我们继续沿用上篇中的model:. 我们来看看如何对一个Book实例进行更新, 我们要做的只是在视图类中更新 :.     template_name = 'updatebook.html'  #这里是你的模板文件名.

露天小便器P-tree

- Haitao - 设计|生活|发现新鲜
2011年丹麦洛斯基尔德音乐节吸引超过10万的游客,强大的人流量对城市的公共厕所的需求也提出了考验. 但丹麦的AANDEBOOM公司却巧妙的解决了这一问题. 他们设计了50个露天小便器,分别放在主会场附近的2个不同街道. 事实证明,它确实是成功的,有大量游客乐意使用它. 这小便器还有个可爱的名字,P-Tree,向大树尿尿,顿时想到小公狗,翘起腿朝树上尿尿哦.

emacs 新手必看: undo-tree

- leafduo - LinuxTOY
火星人都知道,emacs 只有 undo ,没有 redo ……或者说它有 redo,但是相当的诡异,套用一句经典台词就是: 猥琐,非常的猥琐. 简单的说,emacs 的 redo 就是 undo undo ,也就是传说中的负负得正. 可能有些 emacs 新手,还不知道怎么去操作,因为一般情况下,无论你 undo 多少次,都不会发生 redo 的现象.

GitHub - GruppoFilippetti/vertx-mqtt-broker: Vert.x based MQTT Broker

- -

[转][转]TokuDB中的COLA-Tree和TokuMax中的Fractal tree(分形树)

- - heiyeluren的blog(黑夜路人的开源世界)
TokuDB中的COLA-Tree.       目前无论是商业的SQL Server,还是开源的MySQL,都基本上还在用比较老的 B+Tree(SQL Server用的是标准的B-Tree)的索引结构. 从原理来说,B系列树在查询过程中应该是不会慢的,而主要问题就是出现在插入. B-Tree在插入的时候,如果是最后一个node,那么速度非常快,因为是顺序写.

zTree v2.6.03 发布,JQuery Tree插件

- pathfinder - ITeye资讯频道
JQuery Tree插件zTree v2.6.03 发布了. zTree 是利用 JQuery 的核心代码,实现一套能完成大部分常用功能的 Tree 插件. 该版本修正了一些重要的bug:. 【修正】使用自定义图标功能时,异步加载无法切换为loading图标的bug. 【修正】loading 图标定义中的1像素差异,否则会导致高级异步加载中loading跳动(更新 zTreeStyle.css 和 bigDataDemo_super.html).

js Tree - 树形菜单插件

- We_Get - 博客园-首页原创精华区
      js Tree - 树形菜单.       1)DTree是 JQuery 著名树形插件Dynatree的包装类,增加右键菜单,添加、删除、更新接口.     2)jquery treeList widget 这是一个利用jQuery UI Widget Factory创建的轻量级,可换肤树形列表控件.