CART (Classification And Regression Tree)

求 \(R_m\):

 

 

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

 

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)

 

 

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

 

当样本中每个类目下样本个数相同时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

 

 

 

 

随机森林

 

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

 

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

 

 

随机采样数据点

 

基于特征的子集分割节点

 

 

随机森林的构建过程

 

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

 

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

 

数据的随机选取

 

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

 

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注