CART (Classification And Regression Tree)

求 \(R_m\)：

1. 扩张树：用贪心，上至下递归分区方法

2. split function 选择最好的特征 \(j*\) 和该特征最好的值 \(t*\)

   

Split s divide the current node into two children.

比如，对于 t，\(\text{Left-Child }= {(y_i, x_i) : x_{ij} ≤ t}\ 而\ \times ext{Right-Child }= {(y_i, x_i) : x_{ij} > t}\)

2D 的例子

Splitting 规则

1. Regression

2. Classification

不纯度函数(impurity function)

1. 当所有样本都属于同一类时候 \(I\) 取最小值. 即 \(I\) 在点 \((1,0,…,0),(0,1,…,0),…,(0,..,0,1)\) 取最小值.

2. 当样本中每个类目下样本个数相同时I取最大值. 即 \(I\) 在点 \((1/k,..,1/k)\) 取最大值.

Prunning 剪枝

代价复杂性剪枝 (cost complexity pruning)

$$min \ \ \frac {1}{N} \sum^{\vert T \vert}_{m=1} \sum_{x_i \in {R_m}} L(y_i, w_m) + \alpha \vert T\vert$$

\(\vert T \vert\) 是 termainal nodes 的总数

\(L(·, ·)\) 是 loss function, 例如 \(L(yi, f (x_i)) = L(x_i,w_m) = (y_i − w_m)^2\)

\(w_m\) 是与 \(R_m\) 对应的预测值 \(\rightarrow\) 也就是 \(R_m\) 中训练集的平均值

算法

Multiple trees:

• bagging 袋装法
• random forests 随机森林
• boosting 提升法

boosting

基本思想：

在分类问题中，通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类器的性能。

历史：

• PAC learning framework (1990)
• AdaBoost methods (1996)
• gradient boosting (2000)

weak learner:

classifiers whose error rate is slightly better than random guessing

Boosting 改变训练样本的权重，产生一系列的分类器：

最终的分类器可以表示为：

\(\alpha_m\)：分类系数（由 boosting 算法计算得出）

AdaBoost

随机森林

你可能会问为什么不直接使用一个决策树？这种分类器堪称完美，因为根本不会犯任何错误！但要记住一个重点：决策树只是不会在训练数据上犯错。

随机森林是由许多决策树构成的模型。这不仅仅是森林，而且是随机的，这涉及到两个概念：

1. 随机采样数据点

2. 基于特征的子集分割节点

随机森林的构建过程

决策树相当于一个大师，通过自己在数据集中学到的知识对于新的数据进行分类。但是俗话说得好，一个诸葛亮，玩不过三个臭皮匠。随机森林就是希望构建多个臭皮匠，希望最终的分类效果能够超过单个大师的一种算法。

那随机森林具体如何构建呢？有两个方面：数据的随机性选取，以及待选特征的随机选取。

数据的随机选取

首先，从原始的数据集中采取有放回的抽样，构造子数据集，子数据集的数据量是和原始数据集相同的。不同子数据集的元素可以重复，同一个子数据集中的元素也可以重复。第二，利用子数据集来构建子决策树，将这个数据放到每个子决策树中，每个子决策树输出一个结果。最后，如果有了新的数据需要通过随机森林得到分类结果，就可以通过对子决策树的判断结果的投票，得到随机森林的输出结果了。

假设随机森林中有3棵子决策树，2棵子树的分类结果是A类，1棵子树的分类结果是B类，那么随机森林的分类结果就是A类。