分类算法 -- 决策数CART算法

决策树常用的有ID3，C4.5和CART算法，在得到决策树之后还要对树进行剪枝。

ID3算法：https://blog.****.net/weixin_43216017/article/details/87474045
C4.5算法：https://blog.****.net/weixin_43216017/article/details/87609780
决策树的剪枝：https://blog.****.net/weixin_43216017/article/details/87534496

正如之前所说，ID3/C4.5/CART算法的区别在于选择特征作为判断节点时的数据纯度函数（标准）不同。ID3算法使用的是信息增益，C4.5算法使用的是信息增益比，CART算法使用的是基尼系数(GINI)。

CART算法思想

CART算法是一种二分递归分割方法，把当前样本划分为两个子样本，不断递归分割使得生成的每个非叶子结点都有两个分支。所以，CART算法生成的决策树是一个二叉树。由于二叉树的每个节点的选择都只有“是”和“否”两种，所以即使一个节点下需要多分类，也是把数据分成两部分。

假设数据有$x_1,x_2,...,x_n$x1​,x2​,...,xn​共n个自变量（维度），$y$y是其标签。算法步骤为：

Step 1： 在n个自变量中，找出一个$x_i$xi​，设定一个阈值$a_i$ai​，将数据按照$x_i &lt; a_i$xi​<ai​和$x_i≥a_i$xi​≥ai​划分为两部分
Step 2： 将上一步得到的两部分重新选取一个属性继续划分
Step 3： 重复Step 2，直至n个维度完全划分结束

那么我们按照怎样的顺序选择变量呢？CART算法使用的标准是GINI系数。

GINI系数

总体内包含的类别越杂乱，GINI指数就越大。这个概念跟熵的概念很相似。

假设$p_i$pi​为某一类别所占总体的概率，共有n类，则GINI系数定义：
$GINI = 1-\sum_{i=1}^{n}p_i^2$GINI=1−i=1∑n​pi2​
当我们按照变量A对数据集D进行分类时，假设变量A将数据D分成了m类，则划分后的GINI系数为：
$GINI_A(D)=\sum_{j=1}^{m}\dfrac{|D_j|}{|D|}GINI_j(D_j)$GINIA​(D)=j=1∑m​∣D∣∣Dj​∣​GINIj​(Dj​)

此时，GINI系数的增加值为：
$\Delta(A) = GINI(D)-GINI_A(D)$Δ(A)=GINI(D)−GINIA​(D)

我们依次计算每一个变量的基尼系数增加值$\Delta$Δ，并选取最大的那个变量划分数据集。

实例

整个数据的GINI系数为：$GINI(D) = 1-(\dfrac{9}{15})^2-(\dfrac{6}{15})^2 = 0.48$GINI(D)=1−(159​)2−(156​)2=0.48

当按照 A3是否有房子（二分类） 来划分，GINI系数增加值的计算过程：

$GINI(A3=是) = 1 -1^2 = 0$GINI(A3=是)=1−12=0

$GINI(A3=否) = 1 -(\dfrac{1}{3})^2- (\dfrac{2}{3})^2= 0.4444$GINI(A3=否)=1−(31​)2−(32​)2=0.4444

那么$GINI_3(D) = \dfrac{2}{5}*0+\dfrac{3}{5}*0.4444 = 0.2667$GINI3​(D)=52​∗0+53​∗0.4444=0.2667
$\Delta(A3) = 0.48 - 0.2667=0.2133$Δ(A3)=0.48−0.2667=0.2133

当按照 A1年龄（三分类） 来划分，GINI系数增加值的计算过程：
由于CART算法本质上是一个二叉树，所以我们要将数据分成一下三种情况：
{青年} ，{中年，老年}；
{中年}， {青年，老年}；
{老年}， {青年，中年}
这里，我们以{青年} ，{中年，老年}为例计算GINI系数增加值

$GINI(A1=青年) = 1-(\dfrac{3}{5})^2 - (\dfrac{2}{5})^2 = 0.48$GINI(A1=青年)=1−(53​)2−(52​)2=0.48

$GINI(A1=中年老年) = 1-(\dfrac{7}{10})^2 - (\dfrac{3}{10})^2 = 0.42$GINI(A1=中年老年)=1−(107​)2−(103​)2=0.42

那么$GINI_1(D) = \dfrac{1}{3}*0.48+\dfrac{2}{3}*0.42 = 0.44$GINI1​(D)=31​∗0.48+32​∗0.42=0.44

$\Delta(A3) = 0.48 - 0.44=0.04$Δ(A3)=0.48−0.44=0.04

之后在依次计算剩下两种分组的GINI系数增加值。

综上： 虽然在原始数据中只有4个分类，但是在计算GINI系数增加值时，需要计算（3+1+1+3）中分组可能。（即A1和A4有三个分类，即有三种划分情况；A2和A3只有两个分类，即有一种划分情况）。

按照这种计算方式依次计算，每次都选取GINI系数增加最大的划分可能，直至数据没有在划分的可能或者数据已经完全分开。

值得注意的是，当数据是连续型时，我们将数据从小到大排列，去相邻两个取值的均值作为划分点。例如，数据为(60,70,80,90)，我们分别取65，75，85作为划分点，并且计算划分之后的GINI增加值。