决策树，随机森林，boost小结

决策树（CvDTree）是最基础的，是CvForestTree和CvBoostTree的父类。

决策树的生成，一般资料中都是基于ID3算法（熵增益），即ID3算法在每个节点分裂时，选择使gain(A)最大的特征分裂。

Opencv中决策树的生成是基于吉尼不纯度最小的原则生成的。即选择 最小的分裂。其中，m为样本的种类，如只有正负样本，则m为2，p1,p2分别代表某个节点中正样本的比例和负样本的比例。j为使用特征A分裂出的节点数目，如二叉树，每次只分裂出左右两个节点，则j为2，D1，D2分别代表左右节点的样本个数。

决策树的训练接口中，核心是使用try_split_node函数进行递归，直至最终分裂出来的节点中样本的个数小于指定的个数，或者决策树的深度达到指定的最大深度，或者节点中的样本标签纯净（即节点中所有样本属于同一类）。

每调用一次try_split_node函数，会选择一个最优的特征，即找出所有特征中吉尼不纯度最小的特征（find_best_split）。

find_best_split函数会遍历所有特征（如果train函数指定了某些特征，则只遍历指定的特征），分别计算每个特征对应的吉尼不纯度（find_split_cat_class）。然后选择出吉尼不纯度最小的特征来分裂该节点。即find_best_split 函数会调用find_split_cat_class，后者用于计算指定的某个特征的吉尼不纯度。

那么，find_split_cat_class函数是如何计算某个指定特征的吉尼不纯度呢？

假设某个特征的取值有很多个（如颜色特征，对应的取值有红，黄，蓝，绿四种，则颜色特征对应的取值个数为4），则具体计算过程如下：

1．统计每个特征值对应的cjk。cjk为第j个特征值对应的k样本的个数。（如颜色特征,特征值总个数为4，j为0~3；二分类问题，分类总数为2，即k为正样本或负样本， cjk对应4*2矩阵）。

2．统计每个特征值对应的weight。weight[j]即为第 j个特征值对应的cjk中正样本个数和负样本个数分别和其权重的乘积再求和。

3．将cjk按照正样本的个数从大到小重新排序。

4．按照排序后的cjk顺序，依次按照不同的特征值进行分裂，并计算每次分裂对应的吉尼不纯度，最终选出吉尼不纯度最小时对应的特征值域的分裂。

为了更直观地说明如何求某一个指定特征的最小吉尼不纯度的过程，现在使用具体的例子展示，如指定颜色这个特征，同时颜色特征对应的取值有红，黄，蓝，绿四种）

（1）统计每个特征值对应的cjk，cjk为第j个特征值对应的k样本的个数。

更多文章请关注《万象专栏》