机器学习漫谈（2）：空间与距离

（6）汉明距离(Hamming distance)：定义为两个等长字符串之间对应位置不同字符的个数。

例如字符串“1011101”与“1001001”之间的汉明距离为2。

根据汉明距离还引申出一个概念，就是汉明重量。它定义为一个字符串相对于同样长度的零字符串的汉明距离。对于二进制字符串x和y，可以用x和y的汉明重量对应的二进制数做异或运算，结果就是x和y的汉明距离。

汉明距离也等于一个n维超立方体上两个顶点之间的曼哈顿距离。

汉明距离的形式化定义为：

d(x,y)=∑x[i]⊕y[i]

这里i=0,1,..n-1，x,y都是n位的编码，⊕表示异或。

汉明距离用于信号处理时，表明一个信号变成另一个信号需要的最小操作（替换位）；在图像处理领域则是比较二进制图像非常有效的手段。

（7）巴氏距离（Bhattacharyya Distance），用于测量两个离散或连续概率分布的相似性。在分类中，它是用来测量类的可分离性。对于在X数域上的两个离散概率分布p和q，巴氏距离定义为：

其中：被称作巴氏系数。

对于连续概率分布，巴氏系数被定义为：

。

在0=B=B不满足三角不等式.

巴氏距离在图像识别中经常会用到，比如在人脸识别中，用来作为图片之间的距离定义（用直方图作为图像特征时，做直方图匹配）。

这儿需要特别指出，对于不满足距离定义中某些条件的“距离”，我们不能当成严格数学意义上的距离，因此这样的也引导不出一个“距离空间”，或者只能存在一个平凡空间。假设我们所定义的距离不满足三角不等式，可能会引发什么结果呢？下面一些结果其实是等价的。

A）导致距离无法在所定义的集合X上诱导一个拓扑，也无法研究与距离相关的极限和连续；

B）导致集合X中的一个“柯西列”会收敛于两个距离不为0的点，也就意味着点列的极限不唯一；极限不唯一是大问题，它直接会导致在该空间上的微分学没法进行。

C）广泛应用于KNN、DBSCAN、层次聚类等聚类方法中的“动态时间伸缩”距离（Dynamic timewarping, DTW）不满足三角不等式，在一定条件下虽然可用，但很明显会导致奇怪的结果。比如应用KNN时，假设有甲乙丙三个对象，如果甲乙分属两类（先验知识），利用KNN判断丙与甲是一类；但可能当以丙作为类模板时，甲乙同时都归属于丙这类中。其本质的原因就在于这三者之间的距离不满足三角不等式。

D）以上面巴氏距离进一步说明，假设用在人脸识别中，可能会出现甲乙不像，甲丙像，乙丙也像，这样有违直观的结果。

那么为什么在距离定义不满足上述三条性质的时候仍旧可用呢？我的理解是：在某些条件下，该距离具有一定的物理意义，并且可能是在一个有限空间上（我理解的就是完整空间的一部分），所定义的距离在这些地方近似满足了上述三条性质，只是无法进行严格的数学证明。

（8）K-L距离（Kullback–Leibler divergence），也叫KL散度，常用来衡量两个概率分布之间的距离。

根据shannon的信息论，给定一个字符集的概率分布，我们可以设计一种编码，使得表示该字符集组成的字符串平均需要的比特数最少。假设这个字符集是X，对x∈X，其出现概率为P(x)，那么其最优编码平均需要的比特数等于这个字符集的熵：

H(X)=∑x∈XP(x)log[1/P(x)]

在同样的字符集上，假设存在另一个概率分布Q(X)。如果用概率分布P(X)的最优编码（即字符x的编码长度等于log[1/P(x)]），来为符合分布Q(X)的字符编码，那么表示这些字符就会比理想情况多用一些比特数。KL-divergence就是用来衡量这种情况下平均每个字符多用的比特数，因此可以用来衡量两个分布的距离。即：

DKL(Q||P)=∑x∈XQ(x)[log(1/P(x))]-∑x∈XQ(x)[log[1/Q(x)]] =∑x∈XQ(x)log[Q(x)/P(x)]。

由于-log(x)是凸函数，因此：DKL(Q||P)≥

即KL-divergence始终是大于等于的。当且仅当两分布相同时，KL-divergence等于。

KL散度是不对称的，当然，如果希望把它变对称，可作变换：

Ds(P, Q) = [D(P, Q) + D(P, Q)] / 2

Ps：特别感谢笑言同学的提醒，我之前是注意到了机器学习中的某些距离不完全满足距离定义的要求，但没有特别深入去考虑其影响。以前研究KNN时，对于DTW距离就觉得特别奇怪，但没有深究其数学的原因何在，只是认为在应用上有效即可。这次经过梳理和思考，觉得这样的距离还是存在很大的局限，而应用该种距离的方法必定难以推广。在数学上的矛盾如果无法调和，我们除非是创造另外一些不符合现实直觉，但在理论上可以自洽的空间，比如非欧空间。今天就到这儿，下回分解。