机器学习——CRAT算法

机器学习——CRAT算法

1、CART算法引入

1.1 从ID3算法到CART算法

在之前的文章机器学习——决策树(ID3)算法，我们主要介绍了使用信息增益来构建决策树的算法。在ID3算法中，我们使用信息增益来选择特征，信息增益大的优先选择，通过信息增益的计算公式我们不难看出，信息增益的计算会涉及到大量的对数计算，计算量大，并且在计算的过程中容易丢失信息，那么我们应该如何对此进行改进呢？这里我们介绍CRAT算法，其使用基尼指数作为特征选择的评价标准，基尼指数的计算不需要对数，计算量小，并且不容易丢失信息。

1.2 基尼指数

首先，我们给出基尼指数的计算公式：
$$Gini(p)=\sum _{k=1}^K{p}_k(1-p_k)=1-\sum _{k=1}^K{p}_k^2$$

我们对上面的公式进行一下解释，首先假设有K个类别，每一个类别的概率为$p_k$，则整个样本集合的基尼指数为上面所示。对于基尼指数，网上流传的最为常见的理解方式是某个事件被分类错误的概率，比如某个事件$x_i$属于第k类的概率为$p_k$，在这个基础上被分类错误的概率就是$p_k(1-p_k)$，则对于整个事件集合而言，其所有样本被分类错的概率就是基尼指数，基尼指数可以表示样本集合的不纯度，基尼指数越小，说明样本被分类错误的概率越小，样本集合的纯度越高，否则样本集合的纯度越低。

对于K分类问题，计算可以表示为：
$$Gain(p)=\sum _{k=1}^K{p}_k(1-p_k)=1-\sum _{k=1}^K(\frac{|C_k|}{|D_k|}{)}^2$$
其中$|C_k|$表示第k个分类的样本数量，D表示总的样本数量。

同理，对于样本D，如果根据特征A的某个值a，将样本集合D分成$D_1$和$D_2$两个部分，则在特征A的条件下，D的基尼系数的表达式为：

$$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$$

为了进一步的简化模型，CART分类树算法每次仅仅对某个特征进行二分，而不是多分，也就是分为满足特征值和不满足特征值的两种情况。

2 CART算法构建决策 树

在上面的叙述中，我们已经了解了CART算法中对于特征选择的方法，那么下面我们就来介绍如何构建一棵CART分类树。

2.1 CART分类树对于连续特征处理

在CART算法中，对于连续特征的处理方式如下，首先假设当前树节点中的样本集合D有m个样本，则对于连续特征A而言就有m个特征值。

我们首先将特征值按照从大到小的规则进行排序，$a_1,a_2,...a_m$，则CART算法取相邻的两个特征值的中位数。，这样就获得了m-1个划分点，其中第i个划分点$T_i$表示为：
$$T_i=\frac{a_i+a_{i+1}}{2}$$
我们用一张图来展示一下：

如上图所示，$a_i$表示各个属性值，$b_i$表示各个切分点。对于这m-1个值的切分点，我们分别计算以每一个切分点作为二分类点的时候的基尼指数，选择基尼指数最最小的点作为连续特征的二分类点。分类的过程就是满足特征值的为$C_1$类，不满足的称为$C_2$类别。这样我们就对连续的特征进行了离散化，这里需要注意的是，与离散的属性不同的是，对于连续的属性，在使用其划分完一次之后并不丢弃，后续的子节点仍然需要对这个属性进行评估，如果仍然满足基尼指数最小，则仍然使用这个属性进行划分。举个例子来说：

某个属性的属性值是(1~100)的连续属性值，假设第一次我们选择了该属性，将集合划分成了(1-50)和(50-100)的集合，那么下一次划分的时候，我们仍考虑到了该属性，并且计算出来该属性的基尼指数最小，所以我们进一步可以将该属性划分成(50-75)，(75-100)的两个子集。

2.2 对于离散属性的处理

CART算法与ID3算法不同的是，对于离散属性的使用不是一次就结束的，假设属性A包含三个属性值$A_1$,$A_2$,$A_3$，那么通过一次的划分可以将样本集合划分成 { A 1 } \{A_1\} {A1​}， { A 2 , A 3 } \{A_2,A_3\} {A2​,A3​}和 { A 2 } \{A_2\} {A2​}， { A 1 , A 3 } \{A_1,A_3\} {A1​,A3​}和 { A 3 } \{A_3\} {A3​}， { A 1 , A 2 } \{A_1,A_2\} {A1​,A2​}三种情况，无论是哪一种，都会有一个集合中包含两个属性值，那么在接下来的划分中，我们就可以在继续考虑对于包含两个属性值的属性A的划分，而不是丢弃这个属性。不难发现，对于离散属性A而言，其有n个取值，则可能的组合有$\frac{n(n-1)}{2}$。

2.3 CART构建分类树

1. 对于当前的数据集合D，如果样本的个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归。
2. 计算样本集D 的基尼指数，如果基尼指数小于阈值，则返回决策子树，当前节点停止递归。
3. 计算当前节点集合中的各个特征的各个特征值对于D的基尼指数，选择基尼指数最小的特征和对应的特征值a。根据最优属性和属性值进行划分。建立决策树的左右子节点。
4. 递归调用1-3步生成决策树。

2.4 CART构建回归树

首先，CART回归树中对于连续值的处理方式和分类树是不同的，在分类树中，我们的目标是分类之后各个子集的基尼指数最小，但是在回归树中，我们对于连续值的处理使用的是方差的度量方式，对于某个连续属性而言，我们计算的是划分成两个集合之后，形成的子集$D_1,D_2$中各自集合的方差之和最小。用下面的公式表示就是：
$$min[min\sum _{x\in D_1}(y_i-C_1{)}^2+min\sum _{x\in D_2}(y_i-C_2{)}^2]$$
其中$C_1,C_2$分布为两个子集和的均值。我们使用p表示当前选择的属性，q表示当前属性的属性值上的切分点。则有
$$R_1(p,q)=x|x_p<=q$$
$$R_2(p,q)=x|x_p>q$$
$R_1$表示左子节点的数据集，$R_2$表示右子节点的数据集。每一个子节点均值为：
$$C_k=\frac{1}{N}\sum _{x_i\in R_k(p,q)}y，i\in [1,N]，k\in [1,2]$$
递归的对于生成的子数据集进行上述的操作，指的满足某个阈值停止。最终将空间划分成M个子数据集，$R_1,R_2,...R_M$，由这些子数据集构成CART树结构。最终CART的表示式为：
$$f(x)=\sum _{i=1}^K{C}_{k}I(x\in R_k)$$

3、CART剪枝

3.1、基本思想

CART采用的是后剪枝的方式，首先构建出来CRAT树，然后使用交叉验证的方式对树进行检验。在剪枝的过程中，任意时刻的子树T，其损失函数为：
$$C_a(T_t)=C(T_t)+\alpha |T_t|$$
其中α表示的是正则化的参数，$|T_t|$表示的是子树的节点个数，$C(T_t)$为训练数据的预测误差，一般来说，α越大，则CART树的剪枝越厉害，最优树的结构越小。

在确定损失的度量之后，我们来确定剪枝的思路：
对于任意时刻的一棵子树而言，如果其没有剪枝，则有：
$$C_a(T_t)=C(T_t)+\alpha |T_t|$$
如果将其减掉，仅仅保留根节点，则有：
$$C_a(T)=C(T)+\alpha$$
其中T表示当前子树的根节点。

很容易的，我们可以想到，一开始剪枝掉少量的节点的时候，会造成训练误差增大，也就是当α=0或者α很小的时候，有：
$$C_a(T_t)[没有剪枝]<C_a(T)[剪枝]$$

随着α的不断增大，最后可能出现的时候
$$C_a(T_t)<C_a(T)$$
随着α的不断增加，则一定存在一个α使得：
$$C_a(T_t)=C(T_t)+\alpha |T_t|=C_a(T)=C(T)+\alpha$$
此时可以推导出来：
$$C(T_t)+\alpha |T_t|=C(T)+\alpha$$
则可以求出来：
$$\alpha =\frac{C(T)-C(T_t)}{|T_t|-1}$$
并且随着α的再次增大，必然就有$C_a(T_t)>C_a(T)$，当T和$T_t$拥有相同的损失的时候，T所拥有的节点的个数更少，所以可以进行剪枝操作。将其变成一个叶子节点T。我们对于每一个非叶子节点计算出来是否剪枝的α，如果我们把所有的叶子节点是否剪枝的阈值α都计算出来，然后对于每一个α利用交叉验证的方法进行检验，最终确定最好的α，按照最优的α进行剪枝操作。

3.2 CART算法剪枝过程

1. 初始化α=∞，最优的子树集合{T}
2. 从下到上开始计算各个内部积淀t的训练误差损失函数$C_{\alpha }(T_t)$，叶子节点的个数$|T_t|$，以及正则化阈值$\alpha =min\frac{C(T)-C(T_t)}{|T_t|-1}$，更新α值。
3. 得到所有节点的α值的集合M。
4. 从M中选择最大的${\alpha }_{max}$，从上到小的访问节点，当前计算出来的值α小于等于${\alpha }_{max}$的时候就进行剪枝操作。得到一个最优的子树Tk。
5. 迭代M集合，根据各个α值执行第4步，最终生成一个子树的集合W。
6. 采用交叉验证法在最庸子树集合中选择最优的子树。

4 决策树算法总结

无论是ID3，C4.5还是CART算法，都是决策树算法的一种，都具有一些相同的有点和局限性，在这里，我们做一些总结。

4.1 优点

1. 简单直观，算法的可解释性强。
2. 不需要预处理，不需要归一化操作。
3. 既可以处理离散值，也可以处理连续值(ID3算法除外)。
4. 可以采用交叉验证来选择模型，提高泛化能力。

4.2 缺点

1. 不使用某种剪枝策略的话，非常容易过拟合。
2. 树结构容易因为样本的一点点变动，导致结构的发生很大的改变。
3. 不容易找到一棵最优的决策树。
4. 对于样本不均衡的问题，处理的比较差。