开发者学堂课程【高校精品课-北京理工大学-数据仓库与数据挖掘（上）：Measure for evaluating the goodness of a test（一）】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/921/detail/15643
Measure for evaluating the goodness of a test（一）
内容介绍：
一、information gain
二、信息增益率
三、基尼指标
四、三种指标比较
今天向大家介绍决策树模型中对决策树测属性测试条件的评估方法。在决策树模型中，对属性测试条件进行评估的主要指标有三种，一种是 information gain 信息增益，一种是 Gain Ratio 信息争议率，还有一种是 Gini index 基尼指标。
一、information gain
1.熵的概念
对于 information gain 来说，它是基于熵理论的，熵是对一个随机变量不确定性的度量标准，对于一个随机变量Y，如果取值有M种情况，分别为Y1、 Y2直到YM。可以用下图公式来计算随机变量的熵，熵值越大，就意味着随机变量确定性越高，值越小，就意味着它的不确定性越低。
通过M=2解释熵对不确定性的度量，当 M=2时，就意味着 Y 的取值只有两种情况，假设分别是 Y 取值为1，或者是Y取值为0，
（1）、当P（X=1）的概率为0.5的时候，也就意味着P（X=0）的概率也是0.5，也就是 Y 这个随机变量取值和0和取值为1的概率是一样的，这时它的不确定性是最高的，不确定性的熵值取值为1，达到最大。
（2）、再看一下两个极端的情况，极端情况指的是P（X=1）取值为0的情况，及P（X=0）的取值为1的情况。也就是随机变量 Y，它的取值一定是零。这时用公式去计算熵的值就是零，是很确定的。
那么类似于当 X=1 的概率为1时，意味着随机变量Y的取值一定是1，它的熵值也是零，因为Y的取值是确定的。
对于熵来说，熵值越高，随机变量不确定性就越高，熵值越低，它的不确定性就越低。
2.条件熵
（1）、条件熵就是 givenX 下 Y 的熵，指的是在已知一个随机变量 X 的情况下，熵 Y 的值是多少，。对于H（Y）的熵的含义可以理解为，弄清楚随机变量 Y 所需要的信息量，而 given X y 的熵的含义，指的是知道随机变量Y的信息的条件下，再去弄清楚Y的值所需要的信息量。很显然，given X y的值要小于H（Y）的值。
（2）、下面是条件熵的计算公式，
其中假设 X 取值有多种取值情况，P（X)代表的是某一种X取值的概率，后面的 given (X=x)Y 的熵指的是在 X=x 的情况下，随机变量 Y 的熵。
3.计算熵和条件熵例子
下面通过一个具体的例子介绍是怎么样计算熵和条件熵的。
（1）、有两个随机变量 X 和 Y，Y有 两种取值，是1和0，在五个数据对象中有两个是1三个是0，所以根据熵的计算公式随机变量 Y 的计算就应该是 -2/5 log₂（2/5）-3/5log₂（3/5）。
（2）、对于随机变量 X 来说，也有两种取值，一种是 T 一种是 F，两个取值的概率分别是2/5和3/5。对于2/5部分包含两个数据对象所对应的 Y 的取值是1和0。也就是说每一种取值各占一半，图中下面的公式，
也就是H(X=T)下Y的熵的计算公式是-1/2 log₂(1/2)-1/2log₂(1/2)，同理对的X取值为F的情况。有三个数据对象，Y取值分别是1、0、0，也就是有1/3取值为1，有2/3取值为0，所以熵就是I（1，2），也就是等于-1/3 log₂（1/3）-2/3 log₂（2/3)。这就是熵和条件熵的计算方法。
4.信息增益
如果在计算熵和条件熵之后。把它做减法，也就是 HY 减去 H given X y，那么它的含义是什么？就是属性X，对于弄清楚Y随机变量的取值的贡献，信息增益主要就是根据这一思想来做的。
（1）、在属性中，对属性测试条件的选择是选择具有最大的信息增益的属性作为属性测试条件，这一种方法主要是用在决策数经典算法 ID3 和 C4.5 中。
（2）、类标签的熵。假设数据集为 D，也就是它里面有 D 个数据对象，用 Pi 代表每一个类别出现的概率。Pi就指的是 Ci 出现的概率，对于这样一组数据集，可以计算它的类标签的熵的计算公式跟条件熵的计算公式是一样的。
其中pi指的是每一个类别的概率，而M指的是数据对象的类别是有多少种。
（3）、属性的条件熵。在计算熵之后，就可以计算每一个属性的条件熵，把每一个属性的条件熵代表为 Infoa(D)，知道属性 a 的条件下，再去弄清楚数据集中类标签所需要的信息量，计算公式像条件熵的计算公式，
其中 Dj 代表的是属性 a 的一个取值，假设的属性 a 的取值有 V 种情况，那么 Dj 就是代表它的属性为 vj 时候的数据对象的个数。相除就代表的是属性a取值为vj时候的比例，然后再乘以这一部分数据集的熵,把它累加起来，就得到了Infoa(D)。
（4）、信息增益计算。用 Info(D) 也就是熵，减去 Infoa(D) 也就是条件熵，得到的值叫 Gain(A)，就是属性 a 的信息增益，含义就是知道属性a之后，可以对认识类标签所提供的贡献。
5.种类属性计算例子
（1）、属性的熵计算。在下图这个例子中，数据集一共有14条数据对象。类别主要是测试是否买电脑，类别是两种，一种是 no，一种是 yes，在14个数据对象中，有九个是 yes，有五个是 no，所以可以计算 buys computer 属性的熵。也就是 info(D)=0.94，这利用熵的公式就可以计算了。
（2）、属性条件熵计算。在计算了我们的熵之后，就可以计算各个属性的条件熵。以属性 age 为例，对于 age 它是一个标称属性，主要有三种取值情况，根据这三种取值情况，可以得到三部分的熵。
第一部分就指的是 age 小于等于30，一共有五个记录，所以对于属性 age 小于等于30这一部分的比率概率就是5/14，同理，age 在31和40之间是4个，它的比率就是4/14。还有一部分就是大于40是5个数据对象，它的概率就是5/4。
在年龄小于等于30部分的五个数据对象中，有两个是 yes，有三个是 no，所以它的熵就是(2,3)，这个计算很简单，就是-2/5 log₂(2/5)-3/5 log₂(3/5)，
（3）、信息增益计算。在计算 info age (D)之后，用 info (D)也就是商减去属性 age 的条件熵，得到的值0.246就是属性 age 的信息增益。
它的含义是在知道 age 属性下，认识类标签可以少用0.246的信息量。
类似的可以计算 Income 的信息增益属性，Student 的信息增益和属性 increating 的信息增益。
（4）、比较信息增益。得到每个属性的信息增益之后，进行比较，会发现 Age 属性的信息增益值是最大的，也就是意味着 age 对认识内标签的贡献最大，所以可以选择 age 作为属性测试条件。
这个例子中，属性是种类属性。对于连续属性该怎么样去处理？
6.连续属性
（1）、对于连续属性有两种方式，第一种方式，就是进行离散化，把连续属性值离散化成若干个离散值，这时候连续属性就变成了种类属性，可以利用种类属性的处理方法来进行处理。
第二种方法，就是去选择属性的一个最佳分裂点。然后将属性进行一分为二。
（2）、怎么样选择连续属性的最佳分裂点？首先把属性值按照特定的顺序，比如按照增序，以年龄为例对它进行排序，在排序之后就要得到属性的候选分裂点。候选分裂点一般是以两个连续取值的平均值作为候选分裂点。对于每一个分裂点，把属性划分为 a 大于 V 值和 a 小于等于V值两部分，利用这样的一个属性测试条件，可以计算每一个在这样属性测试条件下的信息增益。最佳的分裂值就是具有最大信息增益的点。得到最佳的分裂值之后，就可以将属性a分裂成 a 小于等于 P 和 a 大于 P，两个部分。
上面已经介绍完信息增益的计算方法，以及如果属性是连续值，或者如果属性是标称属性时属性测试条件该怎么去处理。
7.信息增益的缺点
（1）、对于信息增益来说是有一个缺陷的，信息增益会比较倾向于去选择属性取值比较多的属性。
举例，比如属性 Gender 只有两种取值，car type 有三种取值，很显然对于同一种数据集，利用 car type 作为属性测试条件计算出来的信息增益会比利用 gender 作为属性测试条件得到的信息增益的值要大。
举一个非常极端的情况，假设用顾客的 ID 作为属性测试条件，属性的 ID 是为了区分每一个顾客，每一个数据对象都有一个 ID，利用 ID 对落入节点的数据集进行划分的结果就是每一个节点都只有一个数据对象。
也就是数据对节点的纯度是非常高的，在这样的一种极端的情况下，每一个节点的熵的值就最小为零，在这种情况下，可以得到属性的最大的信息增益，很显然并不希望去选择类似于 costume ID 这种具有大量属性取值的属性作为属性测试条件。
