第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为分裂属性。
再递归使用这个方法计算子节点的分裂属性,最终就可以得到整个决策树。
小伙伴们如果觉得文章还行的请点个赞呦!!同时觉得文章哪里有问题的可以评论一下 谢谢你!