第1个回答 2022-06-10
通俗来说，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：
女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。
这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，图1表示了女孩的决策逻辑。
如果你作为一个女生，你会优先考虑哪个条件：长相？收入？还是年龄。在考虑年龄条件时使用25岁为划分点，还是35岁为划分点。有这么多条件，用哪个条件特征先做if，哪个条件特征后做if比较优呢？还有怎么确定用特征中的哪个数值作为划分的标准。这就是决策树机器学习算法的关键了。
首先，我们需要熟悉信息论中熵的概念。熵度量了事物的不确定性，越不确定的事物，它的熵就越大。具体的，随机变量X的熵的表达式如下：
如抛一枚硬币为事件 ， ， ，
掷一枚骰子为事件 ， ，
，显然掷骰子的不确定性比投硬币的不确定性要高。
熟悉了单一变量的熵，很容易推广到多个个变量的联合熵，这里给出两个变量X和Y的联合熵表达式：
有了联合熵，又可以得到条件熵的表达式H(X|Y)，条件熵类似于条件概率,它度量了我们在知道Y以后X剩下的不确定性。表达式：
我们刚才提到 度量了 的不确定性，条件熵 度量了我们在知道 以后 剩下的不确定性，那么 呢？它度量了 在知道 以后不确定性减少程度，这个度量我们在信息论中称为互信息，记为 。
信息熵 ，联合熵 ，条件熵 ，互信息 之间的关系由图2所示：
在决策树的ID3算法中，互信息 被称为信息增益。ID3算法就是用信息增益来判断当前节点应该用什么特征来构建决策树。信息增益大，则越适合用来分类。
下面我们用SNS社区中不真实账号检测的例子说明如何使用ID3算法构造决策树。为了简单起见，我们假设训练集合包含10个元素：
设L、F、H和D表示日志密度、好友密度、是否使用真实头像和账号是否真实，下面计算各属性的信息增益：
因此日志密度的信息增益是0.276。用同样方法得到H和F的信息增益分别为0.033和0.553。因为F具有最大的信息增益，所以第一次分裂选择F为分裂属性，分裂后的结果图3表示：
在上图的基础上，再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。
但是ID3算法中还存在着一些不足之处：
1.ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
2.ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为 ，另一个变量为3个值，各为 ，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。（信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大）如河校正这个问题呢？为了解决这些问题我们有了C4.5算法。
对于第一个问题，不能处理连续特征， C4.5的思路是将连续的特征离散化。比如m个样本的连续特征A有m个，从小到大排列为 。则C4.5取相邻两样本值的平均数，一共取得m-1个划分点，其中第i个划分点 表示为： 。对于这m-1个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为 ，取大于 为类别1，小于 为类别2。这样我们就做到了连续特征的离散化。
对于第二个问题，信息增益作为标准容易偏向于取值较多的特征。C4.5中提出了信息增益比：
即特征 的对数据集 的信息增益与特征 信息熵的比，信息增益比越大的特征和划分点，分类效果越好。某特征中值得种类越多，特征对应的特征熵越大，它作为分母，可以校正信息增益导致的问题。
回到上面的例子：
同样可得： ， 。
因为F具有最大的信息增益比，所以第一次分裂选择F为分裂属性，分裂后的结果图3表示。
再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。
看完上述材料，我们知道在ID3算法中我们使用了信息增益来选择特征，信息增益大的优先选择。在C4.5算法中，采用了信息增益比来选择特征，以减少信息增益容易选择特征值种类多的特征的问题。但是无论是ID3还是C4.5,都是基于信息论的熵模型的，这里面会涉及大量的对数运算。能不能简化模型同时也不至于完全丢失熵模型的优点呢？有！CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。
在分类问题中，假设有 个类别，第 个类别的概率为 ,则基尼系数为：
对于给定的样本 ，假设有 个类别，第 个类别的数量为 ，则样本的基尼系数为:
特别的，对于样本D,如果根据特征A的某个值a,把D分成D1和D2两部分，则在特征A的条件下，D的基尼系数为：
回到上面的例子：
同理得： ， 。
因为L具有最小的基尼系数，所以第一次分裂选择L为分裂属性。
再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。
小伙伴们如果觉得文章还行的请点个赞呦！！同时觉得文章哪里有问题的可以评论一下 谢谢你！