「python机器学习：决策树分类回归树算法及代码实现」百家号Lite

「python机器学习：决策树分类回归树算法及代码实现」百家号Lite_作者自评：

如何评价百家号Lite小程序热议话题「python机器学习：决策树分类回归树算法及代码实现」
分类回归树算法（ClassificationAndRegressionTree）简称CART，也是机器学习中决策树算法的一种，它采用二分递归分割的技术，将样本集分为两个子集，从而保证生成的每个非叶节点都有两个分支。与ID3算法或C4.5算法相比，CART算法并无本质上的不同，都是选取特征对样本进行分类从而构建决策树。不同之处在于：一CART算法以Gini指数作为特征和划分点选取的指标，二CART算法生成的决策树其实是二叉树。
样本集介绍
下表是学习CART算法通常会用到的一个训练样本集，该样本集共有13个样本，每个样本都是对某种动物的特征描述；共有8个特征，包括体温、表面覆盖、胎生、产蛋、能飞、水生、有腿、冬眠，类标记分3种：哺乳类、爬行类和鱼类。这8个特征的取值虽然都是离散性，但并不意味着CART算法不能处理连续型的特征值。通过取相邻数的均值作为划分点的方法在上文有过介绍，这里不再赘述。
Gini指数
Gini指数表示一个被选中的随机样本被分错的概率，Gini指数越小表明样本被分错的概率越小，样本集的纯度越高，反之亦然。Gini指数的理论取值范围为0~1，当所有的样本都属于同一类时Gini=0，当所有的分类在样本中以相同概率分布时Gini=(C1)/C，C是分类的数量，此时Gini指数的值为最大值。决策树中的Gini指数的概念与信息熵类似，用来表示样本集的不确定性或不纯度，CART算法中取使Gini指数最小的特征和划分点。Gini指数的计算公式如下图。
假设样本集D被特征A=a（体温=恒温）划分为两个子集D1和D2，其中|D|=13，|D1|=5，|D2|=8；子集D1中所有样本同属一类，因此Gini(D1)=0；自己D2中样本又可以分为3类，其中|C1|=3，|C2|=3，|C3|=2，用第二个公式计算求得Gini(D2)，然后带入第一个公式得出样本集D在体温为恒温这一条件下的Gini指数。对所有特征循环以上的过程，最后取Gini指数最小值对应的特征对样本进行划分。
上面例子中“体温”特征只有两个取值“恒温”和“冷血”，因此只存在唯一的划分点；如果特征有多个取值应该如何处理呢？如“水生”特征共有3个取值“是”、“否”和“有时”，可以用集合的方法将取值划分为两个子集，如{{'是','有时'},{'否'}}或{{'否','有时'},{'是'}}，然后分别计算两种划分的Gini指数。从连续特征值中寻找最优划分点的思路和方法也是如出一辙的，这里不再赘述。
决策树的剪枝
利用分类回归树算法CART创建的决策树在训练样本集上表现很好，但在另外的测试集上表现得往往不尽如人意，原因是在递归建树的过程中存在过度拟合的问题。另外由于训练样本集中噪声数据或孤立点都会在决策树中的分枝上体现出来，这些多余的分枝使得决策树在对未知数据进行分类使准确性不高，因此需要对决策树进行剪枝处理。CART算法通常采用后剪枝的方法，由下至上计算每个子树剪枝前后的误差，如果剪枝后误差更小就执行剪枝操作，剪枝后的子树由叶节点代替，叶节点的分类采取多数表决的方法决定。
剪枝是决策树构建过程中非常重要的一步，直接关系到决策树的分类准确率和效率，剪枝的方法也很多，在接下来的文章我将详细介绍不同剪枝的思路和过程，请持续关注。CART算法的python实现已上传，需要的请在评论区留言。
相关搜索

常用算法