CART分类树例子讲解

CART分类树原理

二分思想：

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

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

切分指标：

* 基尼指数

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

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

G i n i (D, A = 1) = 3 / 5 * G i n i (D_{1}) + 2 / 5 * G i n i (D_{2}) = 3 / 5 * (1 / 3 * 2 / 3 + 2 / 3 * 1 / 3) + 2 / 5 * (0 * 1 + 1 * 0) = 0.266

分界点B=1, 参考公式 $G i n i (D, B = 1) = 2 / 5 * G i n i (D_{1}) + 3 / 5 * G i n i (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划分第一个节点。

G i n i (D, B = 1, A = 1) = 1 / 2 * G i n i (D_{1}) + 1 / 2 * G i n i (D_{2}) = 1 / 2 * 0 + 1 / 2 * 0 = 0

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