熵与分类

「熵」这个字，又难念又难记更难理解。「人工智能」课中学习「决策树」时用信息熵增益作为属性的优劣判断标准。下面结合这门课里所学的内容，简单地讲解一下什么叫做熵。

这里，我们把「熵」的概念局限在「信息论」领域里，物理学中所说的熵其实也类似，我们不加考虑。

熵，表征的是状态的混乱程度，或者说是信息的不确定性。熵的值越大，信息的不确定性越大。如等概率的时候熵最大，为1，为什么呢，既然选择 a 和选择 b 是等概率的，就相当于没有一点有用的信息，跟透支骰子似的；如果 a 的概率大一点，b 的小一点，说明我们的信息是有用的，不再是完全随机了，这时候熵就会小点，即不确定性就会小点。

下面给出熵的计算公式，很简单：

其中 S 是一个数据集，这些数据一共分为 m 类。Pi 为每个类别的数据个数/S 中总的数据个数，即比例。熵是一个介于0和1之间的数。

什么意思呢？我们来举例说明。

e.g.S={a,b,c,d}，其中 a,b 属于类1，c,d 属于类2。则，这时候的熵：

Entropy(S)=- 2/4 log(2/4) - 2/4 log(2/4) =1/2 + 1/2 = 1.

可见这时熵为1，即不确定性最大。什么叫不确定性大呢？就是说这个数据集的数据是均匀的，越均匀代表信息越少，选任何一个的概率都是相等的。就像掷骰子，我们要预测投出的骰子点数，根本没法预测，因为六种点数的概率是一样的，这就是很大的不确定性。与此相反，如果数据集中只有一个类别，即每个数据属于这个类别的概率为1，这时候熵是多少呢？简单计算一下就知道，熵是0.概率为1，就是百分百地确定它属于这个类别，可见这时候的不确定性是最小的，为0.

熵的这个特性，可以用于分类问题。

e.g.若想购买商品，有这样几个属性可以考虑：喜欢程度、价格、替代物和是否急用。那么优先选用哪个属性判断是否购买呢？（亦即分为两类：买和不买）

给定一个训练数据集，如图：

最好的属性，要有最好的分类能力。怎么说呢？如果对于价格来说，价格高就不买，价格低就买，确定性很高，价格的属性值就能把数据正确的分为两类，这就是好的属性。如果价格高时，买和不买的概率都是0.5，价格低时，买和不买的概率也都是0.5，那么这个属性根本没有任何区分力，应该丢弃不用。

我们用信息增益来表示某个属性对数据的分类能力。

首先，用属性 A 分类 S 后，熵为：

信息增益，即：

即不确定性的减少量，或确定性的增加程度。

对于上例来说，我们计算一下「急用」的信息增益：

类似地，可以计算其他属性的信息增益，选择增益最大的属性作为首选属性。

用这种方式设计的分类器叫做基于信息增益的决策树，也就是大名鼎鼎的 ID3.