本文共 1667 字，大约阅读时间需要 5 分钟。
CART算法
基尼系数
信息熵可以用来衡量某事的不确定性，还有一个指标叫做基尼系数，也可以用来衡量不确定性。
G i n i = 1 − ∑ i K p i 2 Gini = 1-\sum_i^Kp_i^2 Gini=1−i∑Kpi2
K代表类别，p代表概率。
拿投硬币来说，如果是正常的硬币，那么正反两面的概率都是二分之一。如果硬币做了手脚，使得正面的概率变为0.8，那么可以说对于投一次硬币这件事而言，它的不确定性变小了。
我们算一下这两件事的基尼系数：
1 − 0. 5 2 − 0. 5 2 = 0.5 1-0.5^2-0.5^2=0.5 1−0.52−0.52=0.5
1 − 0. 8 2 − 0. 2 2 = 0.32 1-0.8^2-0.2^2=0.32 1−0.82−0.22=0.32
可以看出一件事的不确定越小，它的基尼系数越小，在这一点上和信息熵是相同的。
如果对于只有两个类别的话，设其中一件事的概率为p，我们可以算出：
H ( X ) = − ∑ i K p i l o g 2 p i = − p l o g 2 p − ( 1 − p ) l o g 2 ( 1 − p ) H(X)=-\sum_i^Kp_ilog_2p_i=-plog_2p-(1-p)log_2(1-p) H(X)=−i∑Kpilog2pi=−plog2p−(1−p)log2(1−p)
G i n i ( X ) = 1 − ∑ i K p i 2 = 1 − p 2 − ( 1 − p ) 2 = − 2 p 2 + 2 p Gini(X)=1-\sum_i^Kp_i^2=1-p^2-(1-p)^2=-2p^2+2p Gini(X)=1−i∑Kpi2=1−p2−(1−p)2=−2p2+2p
我们用matplotlib画一下这两个曲线的图：
import numpy as npimport matplotlib.pyplot as pltp = np.linspace(0,1)gini = 2*p*(1-p)entropy = -(1-p)*np.log2(1-p)-p*np.log2(p)plt.plot(p,gini,'r',label='gini')plt.plot(p,entropy,'b',label='entropy')plt.legend()plt.show()
可以看到走势完全一样，这也就是为什么可以用基尼系数代替信息熵了。
CART
CART要求是二叉树，我们可以把每个特征的类别转化为是和否判断的新的特征就行了。
对于每一个特征，计算其基尼系数，这里就和条件概率差不多，和前面的条件熵基本一样。
已知特征Y(只有两个类别，概率为p1，p2)，则结果X的基尼指数就是：
G i n i ( X , Y ) = p 1 G i n i 1 + p 2 G i n i 2 Gini(X,Y)=p_1Gini_1+p_2Gini_2 Gini(X,Y)=p1Gini1+p2Gini2
然后我们对每一个特征下结果的基尼系数进行排序，从小到大，把最小的也就是使得不确定性性最小的那个特征作为第一个。
自此数据被分成了两边，然后对于左右子树分别再进行CART算法直至完成整棵树。
sklearn的实现
sklearn默认就是使用CART完成决策树，代码如下：
from sklearn import treeimport numpy as np# 读数据data = np.genfromtxt('../data/cart.csv',delimiter=',')x_data = data[1:,1:-1]y_data = data[1:,-1]# 构建模型model = tree.DecisionTreeClassifier()model.fit(x_data,y_data)# 看下结果print('实际值：',y_data)print('预测值：',model.predict(x_data))
