paper 85：机器统计学习方法——CART, Bagging, Random Forest, Boosting

本文从统计学角度讲解了CART（Classification And Regression Tree）, Bagging(bootstrap aggregation), Random Forest Boosting四种分类器的特点与分类方法，参考材料为密歇根大学Ji Zhu的pdf与组会上王博的讲解。

CART（Classification And Regression Tree）

Breiman, Friedman, Olshen & Stone (1984), Quinlan (1993)

思想：递归地将输入空间分割成矩形

优点：可以进行变量选择，可以克服missing data，可以处理混合预测

缺点：不稳定

example:

对于下面的数据，希望分割成红色和绿色两个类，原本数据生成是这样的：

Red class: x1^2+x2^2>=4.6

Green class: otherwise

paper 85：机器统计学习方法——CART, Bagging, Random Forest, Boosting

经过不断分割可以得到最后的分类树：

那么怎么分割才是最好的呢？即怎样将输入空间分割成矩形是最佳策略呢？这里一般采用三中评价标准策略：

分裂时，找到使不纯度下降最快的分裂变量和分裂点。

从结果可以看出CART可以通过变量选择迭代地建立一棵分类树，使得每次分类平面能最好地将剩余数据分为两类。
classification tree非常简单，但是经常会有noisy classifiers. 于是引入ensemble classifiers: bagging, random forest, 和boosting。

一般的， Boosting > Bagging > Classification tree(single tree)

Bagging (Breiman1996): 也称bootstrap aggregation

Bagging的策略：

- 从样本集中用Bootstrap采样选出n个样本

- 在所有属性上，对这n个样本建立分类器（CART or SVM or ...）

- 重复以上两步m次，i.e.build m个分类器（CART or SVM or ...）

- 将数据放在这m个分类器上跑，最后vote看到底分到哪一类

Fit many large trees to bootstrap resampled versions of the training data, and classify by majority vote.

下图是Bagging的选择策略，每次从N个数据中采样n次得到n个数据的一个bag，总共选择B次得到B个bags，也就是B个bootstrap samples.

Random forest(Breiman1999):

随机森林在bagging基础上做了修改。

- 从样本集中用Bootstrap采样选出n个样本，预建立CART

- 在树的每个节点上，从所有属性中随机选择k个属性，选择出一个最佳分割属性作为节点

- 重复以上两步m次，i.e.build m棵CART

- 这m个CART形成Random Forest

随机森林可以既可以处理属性为离散值的量，比如ID3算法，也可以处理属性为连续值的量，比如C4.5算法。

这里的random就是指

1. Bootstrap中的随机选择子样本

2. Random subspace的算法从属性集中随机选择k个属性，每个树节点分裂时，从这随机的k个属性，选择最优的

结果证明有时候Random Forest比Bagging还要好。今天微软的Kinect里面就采用了Random Forest，相关论文Real-time Human Pose Recognition in Parts from Single Depth Images是CVPR2011的best paper。