CART算法采用的是基尼系数作为划分依据。 ID3、C4.5算法生成的决策树都是多叉树，而CART算法生成的决策树为二叉树。

基尼系数代表了信息的不纯度，基尼系数越小，不纯度越低，特征越好。 在分类问题中，假设有 K K K个类别，第 k k k个类别的概率为 P k P_{k} Pk​，则基尼系数为： G i n i ( P ) = ∑ k = 1 K P k ( 1 − P k ) = 1 − ∑ k = 1 K P k 2 Gini(P)=\sum_{k=1}^{K}P_{k}(1-P_{k})=1-\sum_{k=1}^{K}P_{k}^{2} Gini(P)=k=1∑K​Pk​(1−Pk​)=1−k=1∑K​Pk2​ 在二分类问题中，如果第一个类别的概率为 P P P，则基尼系数为： G i n i ( P ) = 2 P ( 1 − P ) Gini(P)=2P(1-P) Gini(P)=2P(1−P)

数据集 D D D，输出有 K K K个类别，第 k k k个类别的样本集合为 C k C_{k} Ck​，则数据集 D D D的基尼系数为： G i n i ( D ) = 1 − ∑ k = 1 K ( ∣ C k ∣ ∣ D ∣ ) 2 Gini(D)=1-\sum_{k=1}^{K}(\frac{|C_{k}|}{|D|})^{2} Gini(D)=1−k=1∑K​(∣D∣∣Ck​∣​)2

根据某个特征 A A A的某个取值 A i A_{i} Ai​，将样本分为两个子集 D 1 , D 2 D_{1},D_{2} D1​,D2​，则数据集 D D D在对于特征 A A A的基尼系数为： G i n i ( D , A ) = ∣ D 1 ∣ ∣ D ∣ G i n i ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ G i n i ( D 2 ) = ∣ D 1 ∣ ∣ D ∣ ( 1 − ∑ k = 1 K ( ∣ C 1 k ∣ ∣ D 1 ∣ ) 2 ) + ∣ D 2 ∣ ∣ D ∣ ( 1 − ∑ k = 1 K ( ∣ C 2 k ∣ ∣ D 2 ∣ ) 2 ) \begin{aligned} Gini(D,A) &=\frac{|D_{1}|}{|D|}Gini(D_{1})+\frac{|D_{2}|}{|D|}Gini(D_{2})\\ &= \frac{|D_{1}|}{|D|}(1-\sum_{k=1}^{K}(\frac{|C_{1k}|}{|D_{1}|})^{2})+\frac{|D_{2}|}{|D|}(1-\sum_{k=1}^{K}(\frac{|C_{2k}|}{|D_{2}|})^{2}) \end{aligned} Gini(D,A)​=∣D∣∣D1​∣​Gini(D1​)+∣D∣∣D2​∣​Gini(D2​)=∣D∣∣D1​∣​(1−k=1∑K​(∣D1​∣∣C1k​∣​)2)+∣D∣∣D2​∣​(1−k=1∑K​(∣D2​∣∣C2k​∣​)2)​ 其中， C 1 k C_{1k} C1k​为数据集 D 1 ∣ D_{1}| D1​∣中输出类别为 C k C_{k} Ck​的集合； C 2 k C_{2k} C2k​为数据集 D 2 ∣ D_{2}| D2​∣中输出类别为 C k C_{k} Ck​的集合。

连续特征的处理方式采用离散化。 数据集 D D D的特征 A A A有 m m m个取值，从小到大排列为： ( A 1 , A 2 , A 3 , . . . , A m ) (A_{1},A_{2},A_{3},...,A_{m}) (A1​,A2​,A3​,...,Am​) 划分出 m − 1 m-1 m−1个取值点： ( T 1 , T 2 , T 3 , . . . , T m − 1 ) (T_{1},T_{2},T_{3},...,T_{m-1}) (T1​,T2​,T3​,...,Tm−1​) 其中： T i = A i + A i + 1 2 T_{i}=\frac{A_{i}+A_{i+1}}{2} Ti​=2Ai​+Ai+1​​ 将小于 T i T_{i} Ti​的样本划分到集合 D T − D_{T}^{-} DT−​，大于 T i T_{i} Ti​的样本划分到集合 D T + D_{T}^{+} DT+​， 计算其作为二元离散值时的基尼系数。 在选择分裂特征时，要遍历样本所有特征的所有分割点，选择基尼系数最小的作为分裂依据，其余的分割点会在接下来的计算中继续参与选择。

CART回归树会枚举离散特征的所有二元组合，选择基尼系数最小的进行分裂，剩余组合会在接下来的分裂中继续计算。 例如离散特征 A A A有三个取值 ( A 1 , A 2 , A 3 ) (A_{1},A_{2},A_{3}) (A1​,A2​,A3​)，可以将其二元分类为三种情况： ( A 1 ) , ( A 2 , A 3 ) ( A 1 , A 2 ) , ( A 3 ) ( A 1 , A 3 ) , ( A 2 ) (A_{1}),(A_{2},A_{3})\\ (A_{1},A_{2}),(A_{3})\\ (A_{1},A_{3}),(A_{2}) (A1​),(A2​,A3​)(A1​,A2​),(A3​)(A1​,A3​),(A2​) 计算这三种组合的二元基尼系数，如果最终选择的分裂组合为 ( A 1 ) , ( A 2 , A 3 ) (A_{1}),(A_{2},A_{3}) (A1​),(A2​,A3​)，则剩余的两个取值 A 2 , A 3 A_{2},A_{3} A2​,A3​会在接下来的分裂中继续参与计算。

参考C4.5缺失值处理方式。

输入：训练集 D D D，基尼系数阈值，样本个数阈值，深度阈值。 输出：决策树 T T T。 a.分别计算当前节点的样本数，当前数据集的基尼系数，当前树的深度，如果小于阈值，则停止递归。 b.遍历当前节点的所有样本的所有特征的所有取值，计算出每一个分割点的基尼系数，选择基尼系数最小的进行二分裂。 c.重复以上步骤，知道达到要求。

与分类树相比，回归树主要有一下两点不同。

分类树采用的分裂依据为基尼数，而回归树采用了方差来度量。 对于特征 A A A，遍历其所有的划分点 T T T，根据划分点将样本分为 D 1 , D 2 D_{1},D_{2} D1​,D2​两个子集，计算其方差，选择方差最小的某个特征的划分点进行分裂。 min ⁡ A , T [ ∑ x i ∈ D 1 ( x i − c 1 ) 2 + ∑ x i ∈ D 2 ( x i − c 2 ) 2 ] \min_{A,T}[\sum_{\mathbf{x}^{i}\in D_{1}}(\mathbf{x}^{i}-\mathbf{c}_{1})^{2}+\sum_{\mathbf{x}^{i}\in D_{2}}(\mathbf{x}^{i}-\mathbf{c}_{2})^{2}] A,Tmin​[xi∈D1​∑​(xi−c1​)2+xi∈D2​∑​(xi−c2​)2] 其中， c 1 , c 2 {c}_{1},{c}_{2} c1​,c2​为 D 1 , D 2 {D}_{1},{D}_{2} D1​,D2​的均值。

在CART分类树中，叶节点的输出会根据该节点样本类别进行多数表决。 回归树则将叶节点的均值或者中位数作为样本的预测值。

输出：

输出：

输出：