准备工作
如果我们要把样本画成一棵树（这棵树可以用来查找最近邻或者是分类），那我们最想知道的就是：拿哪个特征去拆分样本，并且要具体到拿哪个特征的哪个值去拆分样本？
我们最希望的结果是：通过某种手段（数学公式）来选择特征（以及该特征的某个具体值），然后拿着这个千辛万苦得到的特征（值），把一堆样本"一分为二"。以此类推，最后，把样本劈成了一棵树。
以前博客里提到的信息增益，信息增益率，都是为了选出特征（用来划分样本）。
下面即将要说的基尼系数，也是这个作用。
基尼系数，能够帮助Cart树选择特征。用选出来的特征，可以更好的将样本画成一颗树，最终分类。
事实上，要了解的顺序是 ：不纯度==》基尼系数==》Cart树
方差不纯度
不纯度值越小，说明样本越"纯"，越能说明大家是"一类人"。
当样本点均来自同一类别时不纯度为0，当两个样本点属于不同类别时不纯度如下：
i(N)=p(w1)p(w2)
推广到多分类问题的不纯度：
多分类的不纯度
基尼系数
基尼系数本质上是：样本被选中的概率 × 样本被分错的概率，当然它的计算公式不完全长这个样子，只是大体思路是这个样子。
所以基尼系数越小越好。
基尼系数：假设有K个类别，样本点属于第k类的概率为Pk，则基尼系数如下：
基尼系数
其中Dk表示的是第k类样本子集的个数。
NOTE：如果是二分类的情况，第一个类别的概率是P1=p，P2=1-p
Gini(p)=2P1P2=2p(1-p)
Cart分类树
例子
计算Gini系数：
Gini(贷款,青年)
Gini(贷款,中年)=0.48
Gini(贷款,老年)=0.44
Gini(贷款,有工作)=0.32
Gini(贷款,有房子)=0.27
其中0.27最小，所以选择特征为房子，最优切分点为有房子
以此类推，即可通过Gini系数选择特征以及切分点，将样本画为一棵树，最终分类成功。
