CART分类树例子讲解

CART分类树原理

二分思想：

* 将特征值等于切分点值的数据划分为左子树。
* 将特征值不等于切分点值的数据划分为右子树。

如此循环构造二叉分类树。

切分指标：

* 基尼指数

假设有N个类别，样本属于第n类的概率为$P_n$, 则基尼系数为：
$Gini(P) = \sum_{n=1}^{N}p_n(1-p_n)$
若数据集按特征值A取值是否等于切分点D1和D2两部分，则在特征A下，集合D的基尼指数为：
$Gini(D，A) = \frac{|D_1|}{D}Gini(D_1) + \frac{|D_2|}{D}Gini(D_2)$

那么，对于数据集D，存在特征A，B，C三个，我们就需要选取最优切分点。计算出Gini(D,A), Gini(D,B), Gini(D,C)。如此以来，我们就可以选取最大或者最小作为切分依据。
那到底是最大还是最小呢？请看基尼指数定义。

$Gini(D, A=1) = 3/5 * Gini(D_1) + 2/5 * Gini(D_2) = 3/5 * (1/3*2/3 + 2/3 * 1/3) + 2/5 * (0 * 1 + 1 * 0) = 0.266$

分界点B=1, 参考公式 $Gini(D, B=1) = 2/5 * Gini(D_1) + 3/5 * Gini(D_2) = 2/5 * (1/2 * 1/2 + 1/2 * 1/2) + 3/5 * (0 * 1 + 1 * 0) = 0.2$ 由此可见，Gini(D, B=1)数值更小，应当以特征B划分第一个节点。

$Gini(D, B=1, A=1) = 1/2* Gini(D_1) + 1/2 * Gini(D_2) = 1/2 * 0 + 1/2 * 0 = 0$

划分后，由于只剩下一个特征，其实是不用计算的，直接划分
那么决策树为：{“B=0”: “label=0”, “B=1”: {“A=1”: “label=1”, “B=0”: “label=0”}} }