掌握机器学习数学基础之信息论及其他（二）

这篇文章继续讲述信息论和距离量度的基础知识，下面是目录：

信息熵

条件熵

相对熵 (KL散度)

互信息

几种常用的距离度量

图论

树论

互信息

测量训练数据中x与y的相关度。是度量两个事件集合之间的相关性(mutual dependence)的标准。意义就是：由于事件A发生与事件B发生相关联而提供的信息量。而在机器学习中，该算法可能会使得我们选择的都是与标签y强相关的特征值，从而进行特征选择，数学公式：

应该不难理解，但这里有一个问题

：问：《数学之美》 上面 互信息 的公式是：；又看到 《统计学习方法》 上有一个 信息增益 的公式：

。这不是一样吗？难道互信息就是信息增益？

答：一般IG（信息增益）是指KL散度（相对熵） 但在Desicion Tree（决策树）的IG一般是指KL散度的期望，然后正好就是互信息了，其实我想就简单理解并记住计算互信息的公式，然后在机器学习中信息增益是一种特殊的情况，就是它是KL散度的期望。 先看p对q的相对熵为

然后是KL散度的期望=互信息

互信息在特征选择时也有重要的作用，总之，对于信息论，重要的是理解，区分和应用。

几种常用的距离度量

设有两个n维变量和，则下面可以定义一些常用的距离公式：

曼哈顿距离：曼哈顿距离也称为城市街区距离，出租车距离，不好理解看下图，数学定义如下：

欧氏距离：欧氏距离其实就是L2范数，或者说简单理解为直线距离，数学定义如下：

如图中红线代表曼哈顿距离，绿色代表欧氏距离，也就是直线距离，而蓝色和黄色代表等价的曼哈顿距离。曼哈顿距离——两点在南北方向上的距离加上在东西方向上的距离，即。对于一个具有正南正北、正东正西方向规则布局的城镇街道，从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离，因此，曼哈顿距离又称为出租车距离。

闵可夫斯基距离:从严格意义上讲，闵可夫斯基距离不是一种距离，而是一组距离的定义,或者说，它是距离的推广：

当p=1时，就是曼哈顿距离；当p=2时，就是欧式距离。

切比雪夫距离：切比雪夫距离就是，即无穷范数，数学表达式如下：

夹角余弦：夹角余弦的取值范围为[-1,1]，可以用来衡量两个向量方向的差异；夹角余弦越大，表示两个向量的夹角越小；当两个向量的方向重合时，夹角余弦取最大值1；当两个向量的方向完全相反时，夹角余弦取最小值-1。机器学习中用这一概念来衡量样本向量之间的差异，其数学表达式如下：

上面常见的距离度量方式是有必要记住的，比如在机器学习中的聚类，在推荐系统，都起着其重要的作用。