决策树（Decision Tree）
决策树（Decision Tree）是一种基本的分类与回归方法，其模型呈树状结构，在分类问题中，表示基于特征对实例进行分类的过程。本质上，决策树模型就是一个定义在特征空间与类空间上的条件概率分布。决策树学习通常包括三个步骤： 特征选择 、 决策树的生成 和 决策树的修剪 。 分类决策树模型是一种描述对实例进行分类的树形结构，决策树由节点（node）和有向边（directed edge）组成。节点有两种类型：内部节点（internal node）和叶节点（leaf node）。内部节点表示一个特征或属性，叶节点表示一个类。 利用决策树进行分类，从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点；这时，每一个子节点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶节点。最后将实例分到叶节点的类中。 决策树是给定特征条件下类的条件概率分布，这一条件概率分布定义在特征区间的一个划分（partiton）上。将特征空间划分为互不相交的单元（cell）或区域（region），并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应划分中的一个单元，决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设X为表示特征的随机变量，Y为表示类的随机变量，那么这个条件概率分布可以表示成P(Y|X)。X取值于给定划分下单元的集合，Y取值于类的集合，各叶节点（单元）上的条件概率往往偏向于某一个类，即属于某一类的概率较大，决策树分类时将该节点的实例分到条件概率大的那一类去。也就以为着决策树学习的过程其实也就是由数据集估计条件概率模型的过程，这些基于特征区间划分的类的条件概率模型由无穷多个，在进行选择时，不仅要考虑模型的拟合能力还要考虑其泛化能力。 为了使模型兼顾模型的拟合和泛化能力，决策树学习使用正则化的极大似然函数来作为损失函数，以最小化损失函数为目标，寻找最优的模型。显然从所有可能的决策树中选取最优决策树是NP完全问题，所以在实际中通常采用启发式的方法，近似求解这一最优化问题： 通过递归的选择最优特征，根据该特征对训练数据进行划分直到使得各个子数据集有一个最好的分类，最终生成特征树 。当然，这样得到的决策树实际上是次最优（sub-optimal）的。进一步的，由于决策树的算法特性，为了防止模型过拟合，需要对已生成的决策树自下而上进行剪枝，将树变得更简单，提升模型的泛化能力。具体来说，就是去掉过于细分的叶节点，使其退回到父节点，甚至更高的节点，然后将父节点或更高的节点改为新的叶节点。如果数据集的特征较多，也可以在进行决策树学习之前，对数据集进行特征筛选。 由于决策树是一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型，决策树的生成对应模型的局部选择，决策树的剪枝对应着模型的全局选择。 熵（Entropy） 的概念最早起源于物理学，最初物理学家用这个概念度量一个热力学系统的无序程度。在1948年， 克劳德·艾尔伍德·香农 将热力学的熵，引入到 信息论 ，因此它又被称为 香农熵 。在信息论中，熵是对不确定性的量度，在一条信息的熵越高则能传输越多的信息，反之，则意味着传输的信息越少。 如果有一枚理想的硬币，其出现正面和反面的机会相等，则抛硬币事件的熵等于其能够达到的最大值。我们无法知道下一个硬币抛掷的结果是什么，因此每一次抛硬币都是不可预测的。因此，使用一枚正常硬币进行若干次抛掷，这个事件的熵是一 比特 ，因为结果不外乎两个——正面或者反面，可以表示为 0, 1 编码，而且两个结果彼此之间相互独立。若进行 n 次 独立实验 ，则熵为 n ，因为可以用长度为 n 的比特流表示。但是如果一枚硬币的两面完全相同，那个这个系列抛硬币事件的熵等于零，因为 结果能被准确预测 。现实世界里，我们收集到的数据的熵介于上面两种情况之间。 另一个稍微复杂的例子是假设一个 随机变量 X ，取三种可能值 ，概率分别为 ，那么编码平均比特长度是： 。其熵为 。因此熵实际是对随机变量的比特量和顺次发生概率相乘再总和的 数学期望 。 依据玻尔兹曼H定理，香农把随机变量X的熵 定义为： 其中 是随机变量X的信息量，当随机变量取自有限样本时，熵可以表示为： 若 ，则定义 。 同理可以定义条件熵 : 很容易看出，条件熵（conditional entropy） 就是X给定条件下Y的条件概率分布的熵对X的数学期望。当熵和条件熵中的概率有极大似然估计得到时，所对应的熵和条件熵分别称为检验熵（empirical entropy）和经验条件熵（empirical conditional entropy）. 熵越大，随机变量的不确定性就越大，从定义可以验证: 当底数 时，熵的单位是 ；当 时，熵的单位是 ;而当 时，熵的单位是 . 如英语有26个字母，假如每个字母在文章中出现的次数平均的话，每个字母的信息量 为： 同理常用汉字2500有个，假设每个汉字在文章中出现的次数平均的话，每个汉字的信息量 为： 事实上每个字母和汉字在文章中出现的次数并不平均，少见字母和罕见汉字具有相对较高的信息量，显然，由期望的定义，熵是整个消息系统的平均消息量。 熵可以用来表示数据集的不确定性，熵越大，则数据集的不确定性越大。因此使用 划分前后数据集熵的差值 量度使用当前特征对于数据集进行划分的效果（类似于深度学习的代价函数）。对于待划分的数据集 ，其划分前的数据集的熵 是一定的，但是划分之后的熵 是不定的， 越小说明使用此特征划分得到的子集的不确定性越小（也就是纯度越高）。因此 越大，说明使用当前特征划分数据集 时，纯度上升的更快。而我们在构建最优的决策树的时候总希望能更快速到达纯度更高的数据子集，这一点可以参考优化算法中的梯度下降算法，每一步沿着负梯度方法最小化损失函数的原因就是负梯度方向是函数值减小最快的方向。同理：在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集合方向发展，因此我们总是选择使得信息增益最大的特征来划分当前数据集 。 显然这种划分方式是存在弊端的，按信息增益准则的划分方式，当数据集的某个特征B取值较多时，依此特征进行划分更容易得到纯度更高的数据子集，使得 偏小，信息增益会偏大，最终导致信息增益偏向取值较多的特征。 设 是 个数据样本的集合，假定类别属性具有 个不同的值： ,设 是类 中的样本数。对于一个给定样本，它的信息熵为： 其中， 是任意样本属于 的概率，一般可以用 估计。 设一个属性A具有 个不同的值 ，利用属性A将集合 划分为 个子集 ，其中 包含了集合 中属性 取 值的样本。若选择属性A为测试属性，则这些子集就是从集合 的节点生长出来的新的叶节点。设 是子集 中类别为 的样本数，则根据属性A划分样本的信息熵为： 其中 , 是子集 中类别为 的样本的概率。最后，用属性A划分样本子集 后所得的 信息增益(Gain) 为： 即，属性A的信息增益=划分前数据的熵-按属性A划分后数据子集的熵。 信息增益（information gain）又称为互信息（matual information）表示得知特征X的信息而使得类Y的信息的不确定性减少的程度 。信息增益显然 越小， 的值越大，说明选择测试属性A对于分类提供的信息越多，选择A之后对分类的不确定程度越小。 经典算法 ID3 使用的信息增益特征选择准则会使得划分更偏相遇取值更多的特征，为了避免这种情况。ID3的提出者 J.Ross Quinlan 提出了 C4.5 ,它在ID3的基础上将特征选择准则由 信息增益 改为了 信息增益率 。在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大（类似于正则化）。这个惩罚参数就是 分裂信息度量 的倒数 。 不同于 ID3 和 C4.5 , CART 使用基尼不纯度来作为特征选择准则。基尼不纯度也叫基尼指数 , 表示在样本集合中一个随机选中的样本被分错的概率 则基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率。Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。 样本集合的基尼指数： 样本集合 有m个类别， 表示第 个类别的样本数量,则 的Gini指数为： 基于某个特征划分样本集合S之后的基尼指数： CART是一个二叉树，也就是当使用某个特征划分样本集合后，得到两个集合：a.等于给定的特征值的样本集合 ；b.不等于给定特征值的样本集合 。实质上是对拥有多个取值的特征的二值处理。 对于上述的每一种划分，都可以计算出基于划分特=某个特征值将样本集合划分为两个子集的纯度： 因而对于一个具有多个取值（超过2个）的特征，需要计算以每个取值为划分点，对样本集合划分后子集的纯度 ( 表示特征 的可能取值)然后从所有的划分可能 中找出Gini指数最小的划分，这个划分的划分点，就是使用特征 对样本集合 进行划分的最佳划分点。 参考文献 ： 决策树--信息增益，信息增益比，Geni指数的理解 【机器学习】深入理解--信息熵（Information Entropy） 统计学习方法 （李航） 为了便于理解，利用以下数据集分别使用三种方法进行分类： 在进行具体分析之前，考虑到收入是数值类型，要使用决策树算法，需要先对该属性进行离散化。 在机器学习算法中，一些分类算法（ID3、Apriori等）要求数据是分类属性形式，因此在处理分类问题时经常需要将一些连续属性变换为分类属性。一般来说，连续属性的离散化都是通过在数据集的值域内设定若干个离散的划分点，将值域划分为若干区间，然后用不同的符号或整数数值代表落在每个子区间中的数据值。所以，离散化最核心的两个问题是：如何确定分类数以及如何将连续属性映射到这些分类值。常用的离散化方法有 等宽法 ， 等频法 以及 一维聚类法 等。 在实际使用时往往使用Pandas的 cut() 函数实现等宽离散化: 可以看到与手工计算的离散化结果相同，需要注意的是， 等宽法对于离群点比较敏感，倾向于不均匀地把属性值分布到各个区间，导致某些区间数据较多，某些区间数据很少，这显然不利用决策模型的建立。 使用四个分位数作为边界点，对区间进行划分： 等频率离散化虽然避免了等宽离散化的数据分布不均匀的问题,却可能将相同的数据值分到不同的区间以满足每个区间具有相同数量的属性取值的要求。 使用一维聚类的离散化方法后得到数据集为： 在本次实例中选择使用基于聚类的离散化方法后得到的数据集进行指标计算。为了预测客户能否偿还债务，使用A（拥有房产）、B（婚姻情况）、C（年收入）等属性来进行数据集的划分最终构建决策树。 单身 ： 离婚 ： 已婚 ： 显然，由B属性取值'已婚'划分得到的子数据集属于同一个叶节点，无法再进行分类。 接下来，对由B属性取值'单身'划分得到的子数据集 再进行最优特征选择： 1）计算数据集 总的信息熵，其中4个数据中，能否偿还债务为'是'数据有3，'否'数据有1,则总的信息熵： 2）对于A(拥有房产)属性，其属性值有'是'和'否'两种。其中，在A为'是'的前提下，能否偿还债务为'是'的有1、'否'的有0；在A为'否'的前提下，能否偿还债务为'是'的有2、为'否'的有1，则A属性的信息熵为： 3)对于B（婚姻情况）属性，由于已被确定，在这个数据子集信息熵为0 4)对于C（年收入）属性，其属性值有'中等输入'、'低收入'两种。在C为'中等收入'的前提下，能否偿还作为为'是'的有1,为'否'的有0；在C为'低收入'的前提下，能否偿还作为为'是'的有2,为'否'的有1;则C属性的信息熵为： 5）最后分别计算两个属性的信息增益值： 信息增益值相同，说明以两个属性对数据子集进行划分后决策树的纯度上升是相同的，此时任选其一成为叶节点即可。 同理，对数据子集 进行最优特征选择，发现信息熵为0： 整理得到最终的决策树：
决策树（Decision Tree）
通俗来说，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：
女儿：多大年纪了？
母亲：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为分裂属性。
再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。
小伙伴们如果觉得文章还行的请点个赞呦！！同时觉得文章哪里有问题的可以评论一下 谢谢你！
