港版牛栏牌
决策树--信息增益，信息增益⽐，Geni指数的理解
转⾃：
决策树 是表⽰基于特征对实例进⾏分类的树形结构
从给定的训练数据集中，依据特征选择的准则，递归的选择最优划分特征，并根据此特征将训练数据进⾏分割，使得各⼦数据集有⼀个最好的分类的过程。
决策树算法3要素：
特征选择
决策树⽣成
决策树剪枝
部分理解：
关于决策树⽣成
决策树的⽣成过程就是 使⽤满⾜划分准则的特征不断的将数据集划分为纯度更⾼，不确定性更⼩的⼦集的过程。
对于当前数据集D的每⼀次的划分，都希望根据某特征划分之后的各个⼦集的纯度更⾼，不确定性更⼩。
⽽如何度量划分数据集前后的数据集的纯度以及不确定性呢？
答案：特征选择准则，⽐如：信息增益，信息增益率，基尼指数
特征选择准则：
⽬的：使⽤某特征对数据集划分之后，各数据⼦集的纯度要⽐划分前的数据集D的纯度⾼（不确定性要⽐划分前数据集D的不确定性低。）注意：出征的诗句
1. 划分后的纯度为各数据⼦集的纯度的加和（⼦集占⽐*⼦集的经验熵）。
2. 度量划分前后的纯度变化 ⽤⼦集的纯度之和与划分前的数据集D的纯度 进⾏对⽐。
特征选择的准则就是 度量样本集合不确定性以及纯度的⽅法。本质相同，定义不同⽽已。
特征选择的准则主要有以下三种：信息增益，信息增益率，基尼指数
⾸先介绍⼀下熵的概念以及理解：
熵：度量随机变量的不确定性。（纯度）
定义：假设随机变量X的可能取值有x1，x2， ... , xn
对于每⼀个可能的取值xi，其概率 P(X=xi) = pi , ( i = 1,2, ... , n)
因此随机变量X的熵：
对于样本集合D来说，随机变量X是样本的类别，即，假设样本有k个类别，每个类别的概率是，其中|Ck|表⽰类别k的样本个数，|D|表⽰样本总数
则对于样本集合D来说熵（经验熵）为：
信息增益（ ID3算法 ）
定义： 以某特征划分数据集前后的熵的差值
在熵的理解那部分提到了，熵可以表⽰样本集合的不确定性，熵越⼤，样本的不确定性就越⼤。因此可以使⽤划分前后集合熵的差值来衡量使⽤当前特征对于样本集合D划分效果的好坏。
芦笋炒鸡蛋划分前样本集合D的熵是⼀定的 ，entroy(前)，
使⽤某个特征A划分数据集D，计算划分后的数据⼦集的熵 entroy(后)
信息增益 = entroy(前) - entroy(后)
书中公式:
做法：计算使⽤所有特征划分数据集D，得到多个特征划分数据集D的信息增益，从这些信息增益中选择最⼤的，因⽽当前结点的划分特征便是使信息增益最⼤的划分所使⽤的特征。
信息增益的理解：
对于待划分的数据集D，其 entroy(前)是⼀定的，但是划分之后的熵 entroy(后)是不定的，entroy(后)
越⼩说明使⽤此特征划分得到的⼦集的不确定性越⼩（也就是纯度越⾼），因此 entroy(前) - entroy(后)差异越⼤，说明使⽤当前特征划分数据集D的话，其纯度上升的更快。⽽我们在构建最优的决策树的时候总希望能更快速到达纯度更⾼的集合，这⼀点可以参考优化算法中的梯度下降算法，每⼀步沿着负梯度⽅法最⼩化损失函数的原因就是负梯度⽅向是函数值减⼩最快的⽅向。同理：在决策树构建的过程中我们总是希望集合往最快到达纯度更⾼的⼦集合⽅向发展，因此我们总是选择使得信息增益最⼤的特征来划分当前数据集D。
缺点：信息增益偏向取值较多的特征
让我敬佩的人原因：当特征的取值较多时，根据此特征划分更容易得到纯度更⾼的⼦集，因此划分之后的熵更低，由于划分前的熵是⼀定的，因此信息增益更⼤，因此信息增益⽐较 偏向取值较多的特征。
解决⽅法 : 信息增益⽐（ C4.5算法 ）
信息增益⽐ = 惩罚参数 * 信息增益
书中公式：
注意：其中的HA(D)，对于样本集合D，将当前特征A作为随机变量（取值是特征A的各个特征值），求得的经验熵。
（之前是把集合类别作为随机变量，现在把某个特征作为随机变量，按照此特征的特征取值对集合D进⾏划分，计算熵HA(D)）
信息增益⽐本质： 是在信息增益的基础之上乘上⼀个惩罚参数。特征个数较多时，惩罚参数较⼩；特征个数较少时，惩罚参数较⼤。
惩罚参数：数据集D以特征A作为随机变量的熵的倒数，即：将特征A取值相同的样本划分到同⼀个⼦集中（之前所说数据集的熵是依据类别进⾏划分的）
情人节送老婆礼物
缺点：信息增益⽐偏向取值较少的特征
原因： 当特征取值较少时HA(D)的值较⼩，因此其倒数较⼤，因⽽信息增益⽐较⼤。因⽽偏向取值较少的特征。
使⽤信息增益⽐：基于以上缺点，并不是直接选择信息增益率最⼤的特征，⽽是现在候选特征中找出信息增益⾼于平均⽔平的特征，然后在这些特征中再选择信息增益率最⾼的特征。
基尼指数（ CART算法 ---分类树）
定义：基尼指数（基尼不纯度）：表⽰在样本集合中⼀个随机选中的样本被分错的概率。
注意： Gini指数越⼩表⽰集合中被选中的样本被分错的概率越⼩，也就是说集合的纯度越⾼，反之，集合越不纯。
即 基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率
书中公式：
说明:
1. pk表⽰选中的样本属于k类别的概率，则这个样本被分错的概率是(1-pk)
2. 样本集合中有K个类别，⼀个随机选中的样本可以属于这k个类别中的任意⼀个，因⽽对类别就加和
3. 当为⼆分类是，Gini(P) = 2p(1-p)
样本集合D的Gini指数 ： 假设集合中有K个类别，则：
基于特征A划分样本集合D之后的基尼指数：
需要说明的是CART是个⼆叉树，也就是当使⽤某个特征划分样本集合只有两个集合：1. 等于给定的特征值 的样本集合D1 ， 2 不等于给定的特征值 的样本集合D2
实际上是对拥有多个取值的特征的⼆值处理。
子金举个例⼦：
假设现在有特征 “学历”，此特征有三个特征取值： “本科”，“硕⼠”， “博⼠”，
当使⽤“学历”这个特征对样本集合D进⾏划分时，划分值分别有三个，因⽽有三种划分的可能集合，划分后的⼦集如下：
1.
1. 划分点： “本科”，划分后的⼦集合 ： {本科}，{硕⼠，博⼠}酒名
2. 划分点： “硕⼠”，划分后的⼦集合 ： {硕⼠}，{本科，博⼠}
大便很粘稠是怎么回事3. 划分点： “硕⼠”，划分后的⼦集合 ： {博⼠}，{本科，硕⼠}
对于上述的每⼀种划分，都可以计算出基于 划分特征= 某个特征值 将样本集合D划分为两个⼦集的纯度：
因⽽对于⼀个具有多个取值（超过2个）的特征，需要计算以每⼀个取值作为划分点，对样本D划分之后⼦集的纯度Gini(D,Ai)，(其中Ai 表⽰特征A的可能取值)
然后从所有的可能划分的Gini(D,Ai)中找出Gini指数最⼩的划分，这个划分的划分点，便是使⽤特征A对样本集合D进⾏划分的最佳划分点。
