2024年10月信息增益比的理解（决策树与随机森林）
⑴信息增益比的理解（决策树与随机森林
⑵决策树（decisiontree是一种基本的分类与回归方法，本文主要讨论用于分类的决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布，其主要优点是模型具有可读性，分类速度快。决策树学习通常包括三个步骤：特征选择，决策树的生成和决策树的修剪。而随机森林则是由多个决策树所构成的一种分类器，更准确的说，随机森林是由多个弱分类器组合形成的强分类器。
⑶本文将先对决策树特征选择的算法ID,C.和CART进行计算，然后介绍决策树的剪枝策略，最后介绍随机森林。
⑷在信息论中，条件熵描述了在已知第二个随机变量X的前提下，随机变量Y的信息熵还剩多少。基于X条件的Y的信息熵，用H(Y|X)表示。
⑸如果H(Y|X=x)为变数Y在变数X取特定值x条件下的熵，那么H(Y|X)就是H(Y|X=x)在X取遍所有可能的x后取平均的结果。
⑹首先需要知道的是熵的公式：
⑺条件熵的推导公式如下：
⑻决策树分类从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点。每一个子节点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶节点，最后将实例分配到叶节点的类中。
⑼决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行划分。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。通常特征选择的准则是信息增益或信息增益比，特征选择的常用算法有ID，C.，CART。
⑽信息增益表示得知特征A的信息而使得数据X的信息的不确定性的程度。信息增益定义：特征A对训练数据集D的信息增益g(D,A)定义为集合D的经验熵H(D)与给定特征A的条件下D的经验条件熵H(D|A)之差，即：
⑾根据信息增益选择特征的方法是：对于给定数据集D，计算其每个特征的信息增益，并比较他们的大小，选择信息增益最大的特征。使用信息增益选择特征的算法称为C算法。
⑿信息增益值的大小是相对于训练数据集而言的，并没有绝对意义。在分类为题困难时，也就是说在训练数据集的经验熵大的时候，信息增益值会偏大。反之，信息增益值会偏小。因此，使用信息增益比可以对这一问题进行校正，这是另一种特征选择算法，也即C.算法。
⒀信息增益比定义：特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练集D的经验熵之比：
⒁基尼指数是CART分类树用来选择最优特征的算法，同时决定了该特征的最优二值切分点。
⒂定义：假设有K个类，样本点属于第k类的概率为pk，则概率分布的基尼指数定义：
⒃对于给定的样本集合D，其基尼指数为：
⒄一个特征的信息增益/基尼系数越大，表明特征对样本的熵减少的能力更强，这个特征使得数据由不确定性变成确定性的能力越强。
⒅决策树生成算法产生的决策树对于训练数据的分类往往很准确，但对于未知数据的分类却没有这么准确，即容易出现过拟合情况。解决的办法便是考虑树的复杂度，对已生成的树进行剪枝简化。
⒆决策树的剪枝往往通过极小化决策树整体的损失函数来实现。设树T的叶节点个数为|T|，t是树T的叶节点，该叶节点有Nt个样本点，其中k类的样本点有Ntk个，k=,,...K,Ht(T)为叶节点t上的经验熵,α》=为参数，则决策树学习的损失函数可以定义为：
⒇损失函数中C(T)表示模型对训练数据的预测误差，也即拟合程度。|T|表示模型复杂度，即节点越多模型越复杂，使用参数α来控制两者之间的影响。α越大模型越简单，对数据拟合差；α越小模型越复杂，对数据拟合性好；α=时则不考虑模型复杂度。
⒈因此，剪枝就是在确定了α时，选择损失函数最小的树。
⒉参考：《统计学习方法》李航机器学习.邹博
⒊在了解树模型之前，自然想到树模型和线性模型，他们有什么区别呢？决策树与逻辑回归的分类区别也在于此。树形模型更加接近人的思维方式，可以产生可视化的分类规则，产生的模型具有可解释性。树模型拟合出来的函数其实是分区间的阶梯函数。决策树（decisiontree是一种基本的分类与回归方法，此处主要讨论分类的决策树。决策树是一种十分常用的分类方法，属于有监督学习（SupervisedLearning。所谓有监督学习，就是给出一堆样本，每个样本都有一组属性和一个分类结果，也就是分类结果已知，那么通过学习这些样本得到一个决策树，这个决策树能够对新的数据给出正确的分类。决策树是一种树形结构，它主要有三种不同的节点：决策树算法主要包括三个部分：特征选择、树的生成、树的剪枝。比较常用的决策树算法有ID，C.和CART（ClassificationAndRegressionTree，CART的分类效果一般优于其他决策树。样本数量，特征数量上面，一开始需要注意的：当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵(empiricalentropy)。什么叫由数据估计？比如有个数据，一共有两个类别，A类和B类。其中有个数据属于A类，则该A类的概率即为十分之七。其中有个数据属于B类，则该B类的概率即为十分之三。浅显的解释就是，这概率是我们根据数据数出来的。训练数据集D，则训练数据集D的经验熵为H(D)，|D|表示其样本容量，及样本个数。设有K个类Ck，k=,,,···,K，|Ck|为属于类Ck的样本个数，这经验熵公式可以写为：信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵(conditionalentropy)H(Y|X)，定义X给定条件下Y的条件概率分布的熵对X的数学期望：当熵和条件熵中的概率由数据估计（特别是极大似然估计得到时，所对应的分别为经验熵和经验条件熵，此时如果有概率，令log=。信息增益一般地，熵H(D)与条件熵H(D|A)之差成为互信息(mutualinformation)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。信息增益比Gini指数举例计算Gini指数（不纯度这个分类结果明显并不是很好，因为它没有将见面与不见面完全的分开，在算法中，当然不能凭我们的“感觉”去评价分类结果的好坏。我们需要用一个数去表示。（具体数值代入上面的基尼指数计算公式信息增益vs信息增益比Gini指数vs熵ID算法的核心是在决策树各个结点上对应信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点(rootnode)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征。由该特征的不同取值建立子节点，再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止；最后得到一个决策树。ID相当于用极大似然法进行概率模型的选择。与ID算法相似，但是做了改进，将信息增益比作为选择特征的标准。CART的全称是分类与回归树。从这个名字中就应该知道，CART既可以用于分类问题，也可以用于回归问题。回归树中，使用平方误差最小化准则来选择特征并进行划分。每一个叶子节点给出的预测值，是划分到该叶子节点的所有样本目标值的均值，这样只是在给定划分的情况下最小化了平方误差。要确定最优化分，还需要遍历所有属性，以及其所有的取值来分别尝试划分并计算在此种划分情况下的最小平方误差，选取最小的作为此次划分的依据。由于回归树生成使用平方误差最小化准则，所以又叫做最小二乘回归树。ID熵表示的是数据中包含的信息量大小。熵越小，数据的纯度越高，也就是说数据越趋于一致，这是我们希望的划分之后每个子节点的样子。信息增益=划分前熵-划分后熵。信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大**。也就是说，用属性a机器学习实战（三——决策树
⒋-决策树节点划分时的特征选择依据
⒌依据不同的决策树算法，在划分子节点时进行特征选择的依据有信息增益、信息增益比（又称信息增益率、基尼系数三种。依次阐述如下：.什么是信息熵？如果没有学过信息论等与信息理论相关的书，初看信息熵是会有点懵逼的。在机器学习领域，信息熵的定义如下：信息熵是度量样本集合纯度的一种最常用的指标，假设样本集合D的样本数一共有D个，一共有K类（标签，其中第k类样本所占的比例为pk，则该样本集的信息熵为：有两点可以加强理解：①信息熵是一个与类别标签相关，而与特征无关的量；②其实际反映的就是这个样本集中不同类别的样本的占比情况，也就是前面所说的纯度。如何直观的理解信息熵？可以从熵的最初概念出发，熵是表示体系混乱程度的度量，熵越大自然纯度就越小。吊诡的地方在哪里呢？在于前面的信息二字，信息熵越大到底代表信息量越大还是信息量越小？如果我们把信息量理解的直观一点，两者是反着的，信息熵越大，能给我们利用的信息就越少。举个简单的栗子，样本集D有个人。如果是个好人个坏人，信息熵就会大于个好人个坏人的情况。为什么呢？因为:的比例确实带不来任何信息，假设我们现在就只有这么个样本集，然后来一个新样本，我们判断这个新样本是个好人还是坏人？:的样本集告诉我们，有.的概率是好人.的概率是坏人，也就是跟随机抛硬币一样，无论我们最后给新样本定什么标签，都有%的错误率。但假设我们的样本集是:，其它什么特征都不用，我们可以判断，这个新样本%的概率是好人，%的概率是坏人，所以我们应该无脑的把所有人都判断为好人，这样我们预计只有%的错误率。这就是信息熵发挥的作用，样本类别越均衡，就是纯度越小，信息熵越大，可用的信息就越少。.信息增益前面扯了这么多废话把信息熵弄明白，信息增益就简单多了。如果我们按照某个特征的取值，把原始样本集划分为若干个子集，然后用某种方式求一下这些子集的信息熵“之和”，我们希望什么，我们希望划分后的信息熵要减小得尽可能的多，这个信息熵的减小量，就是信息增益。第一个问题：划分后的子集信息熵之和怎么算？按照信息熵定义，每个子集都能算一个信息熵出来，简单求个和吗？那肯定不行，毕竟还有个样本量的问题，把样本量考虑进去，就相当于给每个子集的信息熵配一个权重，这个权重就是这个子集的样本数占样本总数的比例，然后加权求个和，这就是划分子集后的信息熵求法。用原始的信息熵减去上面这个划分后的信息熵，就是信息增益咯。再说一遍，信息增益就是信息熵的减小量。补充点废话：信息增益大意味着什么？意味着划分后的样本集们普遍的信息熵较小，也就是纯度较大，纯度较大意味着什么，意味着划分后的各个子集有可能这个子集全是好人，那个子集全是坏人，这不正是我们想要的吗，我们要的恰恰就就是根据特征来有效判断人的好坏，所以选信息增益大的特征进行样本划分也就是理所当然的了。使用信息增益来划分节点的决策树算法叫ID算法.信息增益比（率信息增益有什么问题？假设我们有两个特征可供选择，性别与年龄，其中性别的取值只有男和女两种，而年龄的取值有、、、...、、几十个。这会带来什么问题呢？定性想一下，特征取值越多，划分后的各个子集就会越小，而越小的子集其分布就越有可能偏。还是按前面的栗子来说，个人按性别划分成个男人个女人，而这两个子集里有分别都有好人和坏人，信息增益可能justsoso，但如果按年龄分，假设个人恰好是个不同的年龄，那划分后每个子集里要么是一个好人要么是一个坏人，纯度杠杠的，信息增益杠杠的。但这是否代表年龄真的是个更好用得特征？并不是，这是因为我们的样本集终究是有限个样本构成的，当特征取值很多时，子集越小，越小就越有可能出现统计学意义上的偏差，从而使其信息增益看起来大。废话了这么多，想说明什么问题呢？就是“依据信息增益划分子集”这个标准会偏爱可取值数多的特征，而这个特征在刻画样本时不一定强。为了平衡这一点，我们要设法对信息增益做个类似归一化的操作，让不同特征间能有可比性。归一化肯定要考虑特征取值数了，但直接把信息增益除以特征取值数就太简单粗暴了，因此我们再定义一个指标，这个指标称之为特征的固有值，整体上与特征的可取值数会正相关，定义如下：使用特征a的信息增益除以特征a的固有值，就是信息增益比了，使用信息增益比来划分节点的决策树算法叫C.算法。前面说过，信息增益会偏爱取值数较多的特征，那么信息增益比是不是一视同仁了呢？没有，信息增益比会偏爱取值数较少的特征（捂脸哭。所以最机智的做法应该是设法结合两者。.基尼系数其实决策树的节点划分这个事儿吧，搞这么多指标出来自然有它的理由，但这些指标说来说去呢，为的都是一件事儿，那就是我们要找到最有用的特征来划分节点。那什么是最有用呢？就是能最有效的区分样本的类别。不管什么指标，本质上度量的都是这个事儿。基尼系数自然也是如此了，基尼系数反映了从样本集中随机抽取两个样本，其类别标记不一致的概率，原始样本集的基尼系数这么算：为毛说基尼系数反映了随机选取的两个样本类别不一致的概率呢？pk是不同类别的样本所占的比例，因此它们的和为，一堆介于~之间的pk的平方和，什么时候最小？当所有的pk相等的时候平方和最小，这个可以用初中数学知识证明。而当每个类别所占的比例都一样的时候，随机抽取的两个样本不一样的概率最大。比如，在个好人个坏人里随机抽俩人，这俩人一个是好人一个是坏人的概率还是蛮大的，但如果在个好人个坏人里抽俩人，这俩人就有更大概率是两个好人。因此基尼系数度量的也是纯度，由于前面有个-，基尼系数越大，意味着纯度越小（也意味着信息熵越大。理解了基尼系数和信息熵反应的本质是一样的之后，这事就好说了，信息增益是信息熵的减小量，对比想一下这儿就是用划分后基尼系数减小量咯？差不多，但不完全一样，这里是直接用了划分后基尼系数，哪个特征最小就用哪个。为毛呢？因为划分前大家都是一个基尼系数啊，划分后基尼系数最小，可不就是划分后基尼系数减小量最大嘛，所以是一回事。从这个角度来说，前面用信息增益最大也没必要，直接用划分后信息熵最小的那个就行了，效果是一样一样的。使用基尼系数划分特征的决策树算法叫CART算法。CART的全称是classifyandregressiontree（分类和回归树，回归树是什么玩意，以后再说了。以上就是决策树节点划分时特征选择所用的三个指标。
⒍决策树有哪些常用的启发函数
⒎ID——最大信息增益、C.——最大信息增益比、CART——最大基尼指数(Gini)
⒏对于样本集合D，类别数为K，数据集D的经验熵表示为
⒐有时候我们会发现，当特征为ID或者有某一个特征有很多值的时候，ID就不起作用，举个栗子，当特征值为ID的时候，每个样本是一类，那么所求出来的最大信息增益，肯定是最大的。由此可见，其他特征有很多值的情况。因此引入最大信息增益比来减少某个特征类别过多带来的影响。特征A对于数据集D的信息增益比定义为
⒑Gini描述的是数据的纯度，与信息熵含义类似。
⒒数据挖掘中，属性A的信息增益比属性B的信息增益大,说明了什么
⒓说明A更能决定训练集的分类，也就是A比B更重要。举个极端的例子，以学生买电脑为例，如下所示：=======================================性别学历专业是否买电脑=======================================男研究生计算机买女研究生非计算机不买男本科计算机买女研究生非计算机买男大专非计算机买男本科计算机买========================================设A属性为专业，B属性为学历，计算得到A属性的信息增益比B的大，也就是说在分类时，A属性比B属性更具参考价值。事实也正是这样，从上表可得到：只要是计算机专业的学生都买电脑的结论，而通过学历并不能得出任何结论，以为哪种学历的学生都可能买或不买。不知道这样你能否懂。信息收益可以定义为样本按照某属性划分时造成熵减少的期望。也即是否能由该属性直接判断处分类，而不用在考虑其他属性。
⒔决策树（DecisionTree
⒕??决策树（DecisionTree是一种基本的分类与回归方法，其模型呈树状结构，在分类问题中，表示基于特征对实例进行分类的过程。本质上，决策树模型就是一个定义在特征空间与类空间上的条件概率分布。决策树学习通常包括三个步骤：特征选择、决策树的生成和决策树的修剪。
⒖??分类决策树模型是一种描述对实例进行分类的树形结构，决策树由节点（node和有向边（directededge组成。节点有两种类型：内部节点（internalnode和叶节点（leafnode。内部节点表示一个特征或属性，叶节点表示一个类。
⒗??利用决策树进行分类，从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点；这时，每一个子节点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶节点。最后将实例分到叶节点的类中。
⒘??决策树是给定特征条件下类的条件概率分布，这一条件概率分布定义在特征区间的一个划分（partiton上。将特征空间划分为互不相交的单元（cell或区域（region，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应划分中的一个单元，决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设X为表示特征的随机变量，Y为表示类的随机变量，那么这个条件概率分布可以表示成P(Y|X)。X取值于给定划分下单元的集合，Y取值于类的集合，各叶节点（单元上的条件概率往往偏向于某一个类，即属于某一类的概率较大，决策树分类时将该节点的实例分到条件概率大的那一类去。也就以为着决策树学习的过程其实也就是由数据集估计条件概率模型的过程，这些基于特征区间划分的类的条件概率模型由无穷多个，在进行选择时，不仅要考虑模型的拟合能力还要考虑其泛化能力。
⒙??为了使模型兼顾模型的拟合和泛化能力，决策树学习使用正则化的极大似然函数来作为损失函数，以最小化损失函数为目标，寻找最优的模型。显然从所有可能的决策树中选取最优决策树是NP完全问题，所以在实际中通常采用启发式的方法，近似求解这一最优化问题：通过递归的选择最优特征，根据该特征对训练数据进行划分直到使得各个子数据集有一个最好的分类，最终生成特征树。当然，这样得到的决策树实际上是次最优（sub-optimal的。进一步的，由于决策树的算法特性，为了防止模型过拟合，需要对已生成的决策树自下而上进行剪枝，将树变得更简单，提升模型的泛化能力。具体来说，就是去掉过于细分的叶节点，使其退回到父节点，甚至更高的节点，然后将父节点或更高的节点改为新的叶节点。如果数据集的特征较多，也可以在进行决策树学习之前，对数据集进行特征筛选。
⒚??由于决策树是一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型，决策树的生成对应模型的局部选择，决策树的剪枝对应着模型的全局选择。
⒛??熵（Entropy的概念最早起源于物理学，最初物理学家用这个概念度量一个热力学系统的无序程度。在年，克劳德·艾尔伍德·香农将热力学的熵，引入到信息论，因此它又被称为香农熵。在信息论中，熵是对不确定性的量度，在一条信息的熵越高则能传输越多的信息，反之，则意味着传输的信息越少。
??如果有一枚理想的硬币，其出现正面和反面的机会相等，则抛硬币事件的熵等于其能够达到的最大值。我们无法知道下一个硬币抛掷的结果是什么，因此每一次抛硬币都是不可预测的。因此，使用一枚正常硬币进行若干次抛掷，这个事件的熵是一比特，因为结果不外乎两个——正面或者反面，可以表示为,编码，而且两个结果彼此之间相互独立。若进行n次独立实验，则熵为n，因为可以用长度为n的比特流表示。但是如果一枚硬币的两面完全相同，那个这个系列抛硬币事件的熵等于零，因为结果能被准确预测。现实世界里，我们收集到的数据的熵介于上面两种情况之间。
??另一个稍微复杂的例子是假设一个随机变量X，取三种可能值，概率分别为，那么编码平均比特长度是：。其熵为。因此《u》熵实际是对随机变量的比特量和顺次发生概率相乘再总和的《/u》数学期望。
??依据玻尔兹曼H定理，香农把随机变量X的熵定义为：
??其中是随机变量X的信息量，当随机变量取自有限样本时，熵可以表示为：
??同理可以定义条件熵:??很容易看出，条件熵（conditionalentropy就是X给定条件下Y的条件概率分布的熵对X的数学期望。当熵和条件熵中的概率有极大似然估计得到时，所对应的熵和条件熵分别称为检验熵（empiricalentropy和经验条件熵（empiricalconditionalentropy.
??熵越大，随机变量的不确定性就越大，从定义可以验证:??当底数时，熵的单位是；当时，熵的单位是;而当时，熵的单位是.
??如英语有个字母，假如每个字母在文章中出现的次数平均的话，每个字母的信息量为：
??同理常用汉字有个，假设每个汉字在文章中出现的次数平均的话，每个汉字的信息量为：??事实上每个字母和汉字在文章中出现的次数并不平均，少见字母和罕见汉字具有相对较高的信息量，显然，由期望的定义，熵是整个消息系统的平均消息量。
??熵可以用来表示数据集的不确定性，熵越大，则数据集的不确定性越大。因此使用划分前后数据集熵的差值量度使用当前特征对于数据集进行划分的效果（类似于深度学习的代价函数。对于待划分的数据集，其划分前的数据集的熵是一定的，但是划分之后的熵是不定的，越小说明使用此特征划分得到的子集的不确定性越小（也就是纯度越高。因此越大，说明使用当前特征划分数据集时，纯度上升的更快。而我们在构建最优的决策树的时候总希望能更快速到达纯度更高的数据子集，这一点可以参考优化算法中的梯度下降算法，每一步沿着负梯度方法最小化损失函数的原因就是负梯度方向是函数值减小最快的方向。同理：在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集合方向发展，因此我们总是选择使得信息增益最大的特征来划分当前数据集。
??显然这种划分方式是存在弊端的，按信息增益准则的划分方式，当数据集的某个特征B取值较多时，依此特征进行划分更容易得到纯度更高的数据子集，使得偏小，信息增益会偏大，最终导致信息增益偏向取值较多的特征。
??设是个数据样本的集合，假定类别属性具有个不同的值：,设是类中的样本数。对于一个给定样本，它的信息熵为：??其中，是任意样本属于的概率，一般可以用估计。
??设一个属性A具有个不同的值，利用属性A将集合划分为个子集，其中包含了集合中属性取值的样本。若选择属性A为测试属性，则这些子集就是从集合的节点生长出来的新的叶节点。设是子集中类别为的样本数，则根据属性A划分样本的信息熵为：
??其中,是子集中类别为的样本的概率。最后，用属性A划分样本子集后所得的信息增益(Gain)为：
??即，《u》属性A的信息增益=划分前数据的熵-按属性A划分后数据子集的熵《/u》。信息增益（informationgain又称为互信息（matualinformation表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。信息增益显然越小，的值越大，说明选择测试属性A对于分类提供的信息越多，选择A之后对分类的不确定程度越小。
??经典算法ID使用的信息增益特征选择准则会使得划分更偏相遇取值更多的特征，为了避免这种情况。ID的提出者J.RossQuinlan提出了C.,它在ID的基础上将特征选择准则由信息增益改为了信息增益率。在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大（类似于正则化。这个惩罚参数就是分裂信息度量的倒数。
??不同于ID和C.,CART使用基尼不纯度来作为特征选择准则。基尼不纯度也叫基尼指数,表示在样本集合中一个随机选中的样本被分错的概率则《u》基尼指数（基尼不纯度=样本被选中的概率*样本被分错的概率《/u》。Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。
样本集合的基尼指数：样本集合有m个类别，表示第个类别的样本数量,则的Gini指数为：基于某个特征划分样本集合S之后的基尼指数：??CART是一个二叉树，也就是当使用某个特征划分样本集合后，得到两个集合：a.等于给定的特征值的样本集合；b.不等于给定特征值的样本集合。实质上是对拥有多个取值的特征的二值处理。
对于上述的每一种划分，都可以计算出基于划分特=某个特征值将样本集合划分为两个子集的纯度：因而对于一个具有多个取值（超过个的特征，需要计算以每个取值为划分点，对样本集合划分后子集的纯度(表示特征的可能取值)然后从所有的划分可能中找出Gini指数最小的划分，这个划分的划分点，就是使用特征对样本集合进行划分的最佳划分点。
决策树--信息增益，信息增益比，Geni指数的理解
【机器学习】深入理解--信息熵（InformationEntropy
统计学习方法（李航
??为了便于理解，利用以下数据集分别使用三种方法进行分类：
??在进行具体分析之前，考虑到收入是数值类型，要使用决策树算法，需要先对该属性进行离散化。??在机器学习算法中，一些分类算法（ID、Apriori等要求数据是分类属性形式，因此在处理分类问题时经常需要将一些连续属性变换为分类属性。一般来说，连续属性的离散化都是通过在数据集的值域内设定若干个离散的划分点，将值域划分为若干区间，然后用不同的符号或整数数值代表落在每个子区间中的数据值。所以，离散化最核心的两个问题是：如何确定分类数以及如何将连续属性映射到这些分类值。常用的离散化方法有等宽法，等频法以及一维聚类法等。
在实际使用时往往使用Pandas的cut()函数实现等宽离散化:
??可以看到与手工计算的离散化结果相同，需要注意的是，《u》等宽法对于离群点比较敏感，倾向于不均匀地把属性值分布到各个区间，导致某些区间数据较多，某些区间数据很少，这显然不利用决策模型的建立。《/u》
使用四个分位数作为边界点，对区间进行划分：
《u》等频率离散化虽然避免了等宽离散化的数据分布不均匀的问题,却可能将相同的数据值分到不同的区间以满足每个区间具有相同数量的属性取值的要求。《/u》
使用一维聚类的离散化方法后得到数据集为：
??在本次实例中选择使用基于聚类的离散化方法后得到的数据集进行指标计算。为了预测客户能否偿还债务，使用A（拥有房产、B（婚姻情况、C（年收入等属性来进行数据集的划分最终构建决策树。
显然，由B属性取值’已婚’划分得到的子数据集属于同一个叶节点，无法再进行分类。接下来，对由B属性取值’单身’划分得到的子数据集再进行最优特征选择：
计算数据集总的信息熵，其中个数据中，能否偿还债务为’是’数据有，’否’数据有,则总的信息熵：
对于A(拥有房产)属性，其属性值有’是’和’否’两种。其中，在A为’是’的前提下，能否偿还债务为’是’的有、’否’的有；在A为’否’的前提下，能否偿还债务为’是’的有、为’否’的有，则A属性的信息熵为：
对于B（婚姻情况属性，由于已被确定，在这个数据子集信息熵为
对于C（年收入属性，其属性值有’中等输入’、’低收入’两种。在C为’中等收入’的前提下，能否偿还作为为’是’的有,为’否’的有；在C为’低收入’的前提下，能否偿还作为为’是’的有,为’否’的有;则C属性的信息熵为：
最后分别计算两个属性的信息增益值：信息增益值相同，说明以两个属性对数据子集进行划分后决策树的纯度上升是相同的，此时任选其一成为叶节点即可。同理，对数据子集进行最优特征选择，发现信息熵为：整理得到最终的决策树：
c.为什么使用信息增益比来选择特征
对于取值多的属性，尤其一些连续型数值，比如两条地理数据的距离属性，这个单独的属性就可以划分所有的样本，使得所有分支下的样本集合都是“纯的”（最极端的情况是每个叶子节点只有一个样本。一个属性的信息增益越大，表明属性对样本的熵减少
信息增益与信息增益比
那么，为什么用这个公式来定义熵，我们看下熵随概率的变化曲线便会一目了然也就是说，熵把特征概率转换成了特征对结果的说明程度，例如，一个人贷款是不是会逾期，p=.表明这个特征针对是否会逾期的概率是.，也就相当于这个特征对是否逾期的度量相当于投硬币，正反概率都是.，说明程度很差，熵为，达到最大，所以说熵是随机变量不确定性的度量，也是熵公式的含义及来源这个就很好理解了，就是对熵加一个条件，相当于概率中的联合分布g(D,A)=H(D)－H(D|A)什么意思呢，就是说对一个确定的数据集来说，H(D)是确定的，那H(D|A)在A特征一定的情况下，随机变量的不确定性越小，信息增益越大，这个特征的表现就越好继续上公式在信息增益的基础上除A特征的熵是因为信息增益偏向于选择取值较多的特征，容易过拟合，不过多解释，直接上案例上面案例可以一目了然的看出信息增益偏向于选择取值较多的特征，但根据熵的公式可知，特征越多，熵越大，所以除A特征的熵正好抵消了特征变量的复杂程度，避免了过拟合的存在在写的第一篇文章，把自己对算法的理解口语化讲解给大家，也希望能与算法和机器学习爱好者多多交流，希望大家支持ps（认真写一篇文章挺费精力哈哈蛤
信息的大小跟随机事件的概率有关。越小概率的事情发生了产生的信息量越大。因此一个具体事件的信息量应该是随着其发生概率而递减的，且不能为负。信息量公式.为什么使用对数形式有两个不相关的事件x和y，则信息量满足h(x,y)=h(x)+h(y)，概率满足p(x,y)=p(x)*p(y)可以看出h(x)与p(x)的对数有关。.使用负号，保证.使用以为底，遵循信息论的普遍传统考虑随机变量的所有可能取值，所带来的信息量的期望衡量随机变量或整个系统的不确定性。如果随机变量不确定性越大，出现不同情况越多，那么信息熵越大。假如一个随机变量X的真实分布是（/，/,/，/，则信息熵H(x)=/*+/*+/*+/*=.。如果忽略真实分布，认为X的分布是（/，/，/，/，则这个分布就是非真实分布。根据非真实分布计算信息熵，H(x)=/*+/*+/*+/*=，大于.。因此，根据系统的真实分布计算系统信息熵是最小的。交叉熵，衡量在给定的真实分布下，使用非真实分布计算系统的不确定性。公式：，其中表示真实分布，?表示非真实分布。最低交叉熵是用真实分布计算的信息熵，此时，交叉熵=信息熵。因此在机器学习中的分类算法中，总是最小化交叉熵。因为交叉熵越低，就证明算法所算出的非真实分布越接近真实分布。衡量两个取值为正的函数或概率分布之间的差异，比如某个策略和最优策略之间的差异。相对熵=某个策略的交叉熵-信息熵（根据系统真实分布计算而得的信息熵，为最优策略公式：KL(p||q)=H(p,q)-H(p)=?=所以上述例子，所产生的相对熵为-.=..给定X的条件下，Y的不确定性。在X每一个小类里，计算一个小熵，再每一个小熵乘X各个类别的概率，求和。信息熵与条件熵之差，因为新增了X的信息，Y的不确定性减少的程度。信息增益比，因为取值多的X的信息增益比较大，对此进行校正。参考：通俗理解信息熵通俗理解条件熵如何通俗的解释交叉熵与相对熵？