14:31 提问
vc做基于傅里叶形状描述子的图像检索系统特征向量和距离算法该怎么写啊？
对图像进行快速傅里叶变换后得到的关于图片在频域空间的矩阵如何提取用于图像检索的特征向量，以及这些特征向量距离的计算方式。
按赞数排序
建议添加一个opencv的库，这个库里有很多图像处理函数。像傅里叶变换，这个库里就有接口，可以直接调用。
而特征向量的提取，要看你选择的是什么特征。距离的计算方式也有很多种，一般采用欧氏距离。这个可以表征两个特征向量的相似度
进行快速傅里叶变换需要进行边缘检测吗
为啥不用MATLAB
这在Matlab中编程相比比较简单
a=imread('kk.jpg');
%读取图像矩阵
b=fft2(a);
%将矩阵进行傅立叶变换
%提取频域空间矩阵b的特征向量为c，说明的是b必须为方阵
%矩阵的距离计算
找一些数学函数库，入门比较快
其他相似问题在机器学习和数据挖掘中，我们经常需要知道个体间差异的大小，进而评价个体的相似性和类别。最常见的是数据分析中的相关分析，数据挖掘中的分类和聚类算法，如 K 最近邻（KNN）和 K 均值（K-Means）等等。根据数据特性的不同，可以采用不同的度量方法。一般而言，定义一个距离函数 d(x,y), 需要满足下面几个准则：
1) d(x,x) = 0
// 到自己的距离为0
2) d(x,y) &= 0
// 距离非负
3) d(x,y) = d(y,x)
// 对称性: 如果 A 到 B 距离是 a，那么 B 到 A 的距离也应该是 a
4) d(x,k)+ d(k,y) &= d(x,y)
// 三角形法则: (两边之和大于第三边)
这篇博客主要介绍机器学习和数据挖掘中一些常见的距离公式，包括：
闵可夫斯基距离
欧几里得距离
曼哈顿距离
切比雪夫距离
余弦相似度
皮尔逊相关系数
杰卡德相似系数
1. 闵可夫斯基距离
闵可夫斯基距离（Minkowski distance）是衡量数值点之间距离的一种非常常见的方法，假设数值点 P 和 Q 坐标如下：
那么，闵可夫斯基距离定义为：
该距离最常用的 p 是 2 和 1, 前者是欧几里得距离（Euclidean distance），后者是曼哈顿距离（Manhattan distance）。假设在曼哈顿街区乘坐出租车从 P 点到 Q 点，白色表示高楼大厦，灰色表示街道：绿色的斜线表示欧几里得距离，在现实中是不可能的。其他三条折线表示了曼哈顿距离，这三条折线的长度是相等的。
当 p 趋近于无穷大时，闵可夫斯基距离转化成切比雪夫距离（Chebyshev distance）：
我们知道平面上到原点欧几里得距离（p = 2）为 1 的点所组成的形状是一个圆，当 p 取其他数值的时候呢？
注意，当 p & 1 时，闵可夫斯基距离不再符合三角形法则，举个例子：当 p & 1, (0,0) 到 (1,1) 的距离等于 (1+1)^{1/p} & 2, 而 (0,1) 到这两个点的距离都是 1。
闵可夫斯基距离比较直观，但是它与数据的分布无关，具有一定的局限性，如果 x 方向的幅值远远大于 y 方向的值，这个距离公式就会过度放大 x 维度的作用。所以，在计算距离之前，我们可能还需要对数据进行 z-transform 处理，即减去均值，除以标准差：
可以看到，上述处理开始体现数据的统计特性了。这种方法在假设数据各个维度不相关的情况下利用数据分布的特性计算出不同的距离。如果维度相互之间数据相关（例如：身高较高的信息很有可能会带来体重较重的信息，因为两者是有关联的），这时候就要用到马氏距离（Mahalanobis distance）了。
2. 马氏距离
考虑下面这张图，椭圆表示等高线，从欧几里得的距离来算，绿黑距离大于红黑距离，但是从马氏距离，结果恰好相反：马氏距离实际上是利用 Cholesky transformation 来消除不同维度之间的相关性和尺度不同的性质。假设样本点（列向量）之间的协方差对称矩阵是
通过 Cholesky Decomposition（实际上是对称矩阵 LU 分解的一种特殊形式，可参考之前的）可以转化为下三角矩阵和上三角矩阵的乘积： 消除不同维度之间的相关性和尺度不同，只需要对样本点 x 做如下处理：处理之后的欧几里得距离就是原样本的马氏距离：为了书写方便，这里求马氏距离的平方）：下图蓝色表示原样本点的分布，两颗红星坐标分别是（3, 3），（2, -2）:由于 x， y 方向的尺度不同，不能单纯用欧几里得的方法测量它们到原点的距离。并且，由于 x 和 y 是相关的（大致可以看出斜向右上），也不能简单地在 x 和 y 方向上分别减去均值，除以标准差。最恰当的方法是对原始数据进行 Cholesky 变换，即求马氏距离（可以看到，右边的红星离原点较近）：将上面两个图的绘制代码和求马氏距离的代码贴在这里，以备以后查阅：
# -*- coding=utf-8 -*-
# code related at: /daniel-D/
import numpy as np
import pylab as pl
import scipy.spatial.distance as dist
def plotSamples(x, y, z=None):
stars = np.matrix([[3., -2., 0.], [3., 2., 0.]])
if z is not None:
x, y = z * np.matrix([x, y])
stars = z * stars
pl.scatter(x, y, s=10) # 画 gaussian 随机点
pl.scatter(np.array(stars[0]), np.array(stars[1]), s=200, marker=’*’, color=’r’) # 画三个指定点
pl.axhline(linewidth=2, color=’g’) # 画 x 轴
pl.axvline(linewidth=2, color=’g’) # 画 y 轴
pl.axis(‘equal’)
pl.axis([-5, 5, -5, 5])
# 产生高斯分布的随机点
mean = [0, 0] # 平均值
cov = [[2, 1], [1, 2]] # 协方差
x, y = np.random.multivariate_normal(mean, cov, 1000).T
plotSamples(x, y)
covMat = np.matrix(np.cov(x, y)) # 求 x 与 y 的协方差矩阵
Z = np.linalg.cholesky(covMat).I # 仿射矩阵
plotSamples(x, y, Z)
# 求马氏距离
print ‘\n到原点的马氏距离分别是：’
print dist.mahalanobis([0,0], [3,3], covMat.I), dist.mahalanobis([0,0], [-2,2], covMat.I)
# 求变换后的欧几里得距离
dots = (Z * np.matrix([[3, -2, 0], [3, 2, 0]])).T
print ‘\n变换后到原点的欧几里得距离分别是：’
print dist.minkowski([0, 0], np.array(dots[0]), 2), dist.minkowski([0, 0], np.array(dots[1]), 2)
马氏距离的变换和 PCA 分解的白化处理颇有异曲同工之妙，不同之处在于：就二维来看，PCA 是将数据主成分旋转到 x 轴（正交矩阵的酉变换），再在尺度上缩放（对角矩阵），实现尺度相同。而马氏距离的 L逆矩阵是一个下三角，先在 x 和 y 方向进行缩放，再在 y 方向进行错切（想象矩形变平行四边形），总体来说是一个没有旋转的仿射变换。
3. 向量内积
向量内积是线性代数里最为常见的计算，实际上它还是一种有效并且直观的相似性测量手段。向量内积的定义如下：直观的解释是：如果 x 高的地方 y 也比较高， x 低的地方 y 也比较低，那么整体的内积是偏大的，也就是说 x 和 y 是相似的。举个例子，在一段长的序列信号 A 中寻找哪一段与短序列信号 a 最匹配，只需要将 a 从 A 信号开头逐个向后平移，每次平移做一次内积，内积最大的相似度最大。信号处理中 DFT 和 DCT 也是基于这种内积运算计算出不同频域内的信号组分（DFT 和 DCT 是正交标准基，也可以看做投影）。向量和信号都是离散值，如果是连续的函数值，比如求区间[-1, 1] 两个函数之间的相似度，同样也可以得到（系数）组分，这种方法可以应用于多项式逼近连续函数，也可以用到连续函数逼近离散样本点（最小二乘问题，OLS coefficients）中，扯得有点远了- -!。
向量内积的结果是没有界限的，一种解决办法是除以长度之后再求内积，这就是应用十分广泛的余弦相似度（Cosine similarity）：余弦相似度与向量的幅值无关，只与向量的方向相关，在文档相似度（TF-IDF）和图片相似性（）计算上都有它的身影。需要注意一点的是，余弦相似度受到向量的平移影响，上式如果将 x 平移到 x+1, 余弦值就会改变。怎样才能实现平移不变性？这就是下面要说的皮尔逊相关系数（Pearson correlation），有时候也直接叫相关系数: 皮尔逊相关系数具有平移不变性和尺度不变性，计算出了两个向量（维度）的相关性。不过，一般我们在谈论相关系数的时候，将 x 与 y 对应位置的两个数值看作一个样本点，皮尔逊系数用来表示这些样本点分布的相关性。由于皮尔逊系数具有的良好性质，在各个领域都应用广泛，例如，在推荐系统根据为某一用户查找喜好相似的用户,进而，优点是可以不受每个用户评分标准不同和观看影片数量不一样的影响。
4. 分类数据点间的距离
汉明距离（Hamming distance）是指，两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。举个维基百科上的例子：还可以用简单的匹配系数来表示两点之间的相似度——匹配字符数/总字符数。
在一些情况下，某些特定的值相等并不能代表什么。举个例子，用 1 表示用户看过该电影，用 0 表示用户没有看过，那么用户看电影的的信息就可用 0,1 表示成一个序列。考虑到电影基数非常庞大，用户看过的电影只占其中非常小的一部分，如果两个用户都没有看过某一部电影（两个都是 0），并不能说明两者相似。反而言之，如果两个用户都看过某一部电影（序列中都是 1），则说明用户有很大的相似度。在这个例子中，序列中等于 1 所占的权重应该远远大于 0 的权重，这就引出下面要说的杰卡德相似系数（Jaccard similarity）。
在上面的例子中，用 M11 表示两个用户都看过的电影数目，M10 表示用户 A 看过，用户 B 没看过的电影数目，M01 表示用户 A 没看过，用户 B 看过的电影数目，M00 表示两个用户都没有看过的电影数目。Jaccard 相似性系数可以表示为：Jaccard similarity 还可以用集合的公式来表达，这里就不多说了。
如果分类数值点是用树形结构来表示的，它们的相似性可以用相同路径的长度来表示，比如，“/product/spot/ballgame/basketball” 离“product/spot/ballgame/soccer/shoes” 的距离小于到 “/product/luxury/handbags” 的距离，以为前者相同父节点路径更长。
5. 序列之间的距离
上一小节我们知道，汉明距离可以度量两个长度相同的字符串之间的相似度，如果要比较两个不同长度的字符串，不仅要进行替换，而且要进行插入与删除的运算，在这种场合下，通常使用更加复杂的编辑距离（Edit distance, Levenshtein distance）等算法。编辑距离是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离求的是最少编辑次数，这是一个动态规划的问题，有兴趣的同学可以自己研究研究。
时间序列是序列之间距离的另外一个例子。DTW 距离（Dynamic Time Warp）是序列信号在时间或者速度上不匹配的时候一种衡量相似度的方法。神马意思？举个例子，两份原本一样声音样本A、B都说了“你好”，A在时间上发生了扭曲，“你”这个音延长了几秒。最后A:“你~~~好”，B：“你好”。DTW正是这样一种可以用来匹配A、B之间的最短距离的算法。
DTW 距离在保持信号先后顺序的限制下对时间信号进行“膨胀”或者“收缩”，找到最优的匹配，与编辑距离相似，这其实也是一个动态规划的问题:
实现代码（转自 McKelvin’s Blog ）:
#!/usr/bin/python2
# -*- coding:UTF-8 -*-
# code related at: http://blog.mckelv.in/articles/1453.html
import sys
distance = lambda a,b : 0 if a==b else 1
def dtw(sa,sb):
”’
&&&dtw(u”干啦今今今今今天天气气气气气好好好好啊啊啊”, u”今天天气好好啊”)
”’
MAX_COST = 1&&32
#初始化一个len(sb) 行(i)，len(sa)列(j)的二维矩阵
len_sa = len(sa)
len_sb = len(sb)
# BUG:这样是错误的(浅拷贝): dtw_array = [[MAX_COST]*len(sa)]*len(sb)
dtw_array = [[MAX_COST for i in range(len_sa)] for j in range(len_sb)]
dtw_array[0][0] = distance(sa[0],sb[0])
for i in xrange(0, len_sb):
for j in xrange(0, len_sa):
if i+j==0:
if i & 0: nb.append(dtw_array[i-1][j])
if j & 0: nb.append(dtw_array[i][j-1])
if i & 0 and j & 0: nb.append(dtw_array[i-1][j-1])
min_route = min(nb)
cost = distance(sa[j],sb[i])
dtw_array[i][j] = cost + min_route
return dtw_array[len_sb-1][len_sa-1]
def main(argv):
s1 = u’干啦今今今今今天天气气气气气好好好好啊啊啊’
s2 = u’今天天气好好啊’
d = dtw(s1, s2)
if __name__ == ‘__main__’:
sys.exit(main(sys.argv))
6. 概率分布之间的距离
前面我们谈论的都是两个数值点之间的距离，实际上两个概率分布之间的距离是可以测量的。在统计学里面经常需要测量两组样本分布之间的距离，进而判断出它们是否出自同一个 population，常见的方法有卡方检验（Chi-Square）和 KL 散度（ KL-Divergence），下面说一说 KL 散度吧。
先从信息熵说起，假设一篇文章的标题叫做“黑洞到底吃什么”，包含词语分别是 {黑洞, 到底, 吃什么}, 我们现在要根据一个词语推测这篇文章的类别。哪个词语给予我们的信息最多？很容易就知道是“黑洞”，因为“黑洞”这个词语在所有的文档中出现的概率太低啦，一旦出现，就表明这篇文章很可能是在讲科普知识。而其他两个词语“到底”和“吃什么”出现的概率很高，给予我们的信息反而越少。如何用一个函数 h(x) 表示词语给予的信息量呢？第一，肯定是与 p(x) 相关，并且是负相关。第二，假设 x 和 y 是独立的（黑洞和宇宙不相互独立，谈到黑洞必然会说宇宙）,即 p(x,y) = p(x)p(y), 那么获得的信息也是叠加的，即 h(x, y) = h(x) + h(y)。满足这两个条件的函数肯定是负对数形式：
对假设一个发送者要将随机变量 X 产生的一长串随机值传送给接收者， 接受者获得的平均信息量就是求它的数学期望：这就是熵的概念。另外一个重要特点是，熵的大小与字符平均最短编码长度是一样的（shannon）。设有一个未知的分布 p(x), 而 q(x) 是我们所获得的一个对 p(x) 的近似，按照 q(x) 对该随机变量的各个值进行编码，平均长度比按照真实分布的 p(x) 进行编码要额外长一些，多出来的长度这就是 KL 散度（之所以不说距离，是因为不满足对称性和三角形法则），即：KL 散度又叫相对熵（relative entropy）。了解机器学习的童鞋应该都知道，在 Softmax 回归（或者 Logistic 回归），最后的输出节点上的值表示这个样本分到该类的概率，这就是一个概率分布。对于一个带有标签的样本，我们期望的概率分布是：分到标签类的概率是 1， 其他类概率是 0。但是理想很丰满，现实很骨感，我们不可能得到完美的概率输出，能做的就是尽量减小总样本的 KL 散度之和（目标函数）。这就是 Softmax 回归或者 Logistic 回归中 Cost function 的优化过程啦。（PS：因为概率和为 1，一般的 logistic 二分类的图只画了一个输出节点，隐藏了另外一个）
待补充的方法：
卡方检验 Chi-Square
衡量 categorical attributes 相关性的 mutual information
Spearman’s rank coefficient
Earth Mover’s Distance
SimRank 迭代算法等。
参考资料：
Via：来源 daniel-D
转载请注明来自36大数据（)： &
除非特别注明，本站所有文章均不代表本站观点。报道中出现的商标属于其合法持有人。请遵守理性，宽容，换位思考的原则。EMD算法简介
该部分引用自[1]
Earth Mover’s Distance (EMD)，和欧氏距离一样，他们都是一种距离度量的定义，可以用来测量某分布之间的距离。EMD主要应用在图像处理和语音信号处理领域。
EMD问题如下图所示
给定两个签名(或者叫分布、特征量集合)P和Q，P为m个特征量Pi和其权重wPi的集合，记作P={(P1,wP1),(P2,wP2),...(Pm,wPm)}，如图左侧部分。同样的，还有一个分布Q，Q=(Q1,wQ1),(Q2,wQ2),...(Qn,wQn)，即上图右侧部分。在计算这个这两个签名的Earth
Mover's Distance(EMD)前，我们要先定义好P、Q中任意取一个特征量(&Pi&and&Qj&)之间的距离（这个距离叫ground
distance，两个签名之间EMD依赖于签名中特征量之间的ground distance）。当这两个特征量是向量时得到的是欧式距离，当这两个特征量是概率分布时得到的是相对熵(KL距离/)。现在，给定两个签名(P和Q)，只要计算好每两个特征量之间的距离，系统就能给出这两个签名之间的距离了。
EMD&实际上是中的最优解。首先，简要描述下运输问题。我们假设这个例子是从多个工厂运输货物到多个仓库。在上图左侧，P从在P1&到&Pm代表m座工厂，工厂Pi有重量为wPi的货物。在上图右侧，Q从Q1到Qn代表n个仓库，仓库Qj最大容量为wQj。货物之间没有什么区别，都是同一类东西。每个仓库都希望装尽可能多的货物。如何尽可能高效把所有货物(实际上不一定是所有货物，部分也OK)从P运送到Q，就是运输问题的优化目标。在本例中，P、Q都是离散的，那么EMD可以用运输问题的Hungarian算法来计算它们之间的距离。挖个坑而已，这里不具体讨论。
这里定义，货物从工厂Pi运到仓库Qj，距离是，运送货物的重量为。这样一次运输需要的工作量为*。显然，距离越远、或货物越重，工作量就越大。(注：运输可能是多对多的，即一个工厂运输货物到多个仓库，或者一个仓库接收多个工厂的货物。)货物从工厂运到仓库需要很多次这样的运输，经过一些计算和优化，这时我们得到了工作量总和的最小值W。
距离是事先定义的，所以运输量fij是式中唯一的变量，对作如下4个约束：
(1)&运输过程从工厂P到仓库Q，不能反向。
≥ 0 (1≤i≤m,1≤j≤n)
(2)&从工厂Pi一次次运出去的所有货物重量的和不可能超过该工厂中所有货物的总重量wPi
&≤ wPi (1≤i≤m)
(3)&仓库Qj接收的所有货物总重量不可能超过其总容量wQj。
≤ wQj (1≤j≤n)
(4)&总运输量的上限是工厂中货物总重、仓库总容量中的最小值。
当仓库的总容量和工厂货物总重不一样时，我们才需要上述第4个限制条件。仓库总容量比货物总量大的话就可以全部运输了，所以这时候呢，运输量的上限就是货物总量。但如果货物总量比仓库总容量大的话，就不能全部运输了，这时候，运输量的上限就是仓库的总容量啦。方便起见，本例中当仓库的总容量和工厂货物总重是一样的。
运输问题的具体解答此处省略不讨论，假设这个时候我们已经得到了最优解。为了使EMD不会随着总运输量的变化而变化，每一次的运输量还要除以总运输量，以达到归一化的目的。（in
order to avoid favoring smaller signatures in the case of partial matching.）在后面的具体例子中会对它进行详细描述。
很自然可以想到，给定两个签名，把一个变成另一个所需要的最小工作量，就是EMD对距离的定义，这里的「工作量」要基于用户对ground distance的定义，即特征量之间的距离的定义。然而，当特征量非常多的时候，由于要做一一匹配，其计算量是非常大的。因此，有人提出了一种将多个特征量组合起来做向量量化编码(Vector
Quantization)后再组成签名的方法。
EMD算法在自然语言处理领域的应用
通过词嵌入（Word Embedding），我们可以得到词语的分布式低维实数向量表示，我们可以计算词语之间的距离，即我们可以得到dij，因此可以将EMD引入自然语言处理领域。
Matt等人[2]将词嵌入与EMD相联系，用来度量文档距离。提出了WMD（word
mover’s distance）算法，以及WCD（word centroid distance）、RWMD（relaxed
word mover’s distance）两种牺牲精度降低复杂度的算法。
如何将一个文档变为分布P这种形式？
用归一化的词袋模型（nBOW，&normalized bag-of-words）表示。其中P1表示词语，用计算该词的权重，其中表示词语i在文档中出现了次，P1的特征量用该词语的词向量表示。一个nBOW文档向量是比较稀疏的，因为大部分的词语不会出现在该文档中，且在生成文档向量时，去掉的停用词。用欧式距离计算词语与词语之间的距离。
假定数据集中只有两个文档，则这两个文档生成的归一化nBOW向量如下图所示。
转移量用矩阵T表示，生成的矩阵T如下图所示
表示词语i有多少转移到了词语j，
综上，Matt等人提出了WMD算法，WMD是EMD的一个特殊形式。
由于文档向量是经过归一化的，与EMD算法相比，WMD没有
WMD算法的复杂度是，其中p表示nBOW模型的长度，即数据集中不同词语的数目（去处停用词）。该算法已经有成熟的解决方法，详情参考[3]
算法的改进
为了降低模型的计算复杂度，Matt等人提出了WCD和RWMD两个算法，这两个算法是WMD的两个不同下限，通过降低精度来降低计算复杂度。
Word centroid distance(WCD)
将作为WCD。其中X是一个的矩阵，d表示词向量的维度，p表示nBOW模型的长度。d表示一个nBOW文档向量。如下图所示
WCD的复杂度度是
Relaxed word moving distance(RWMD)
通过放松限制条件，得到WMD的下限。通过去掉条件2，保留条件1，我们得到
通过去掉条件2，其实是去掉了仓库容量的限制，我们可以将货物全部运到离其最近的仓库，而不需要考虑仓库的容量。我们在运某个货物时，往离该货物最近的仓库运送，即在转移词语i时，我们只向与词语i距离最近的词语j转移。
当我们去掉条件1，保留条件2时，我们得到，与基本相同。去掉条件1，其实是去掉了货物量的限制，我们可以将货物源源不断的运到仓库中，直到仓库满了为止。我们在为填满某个仓库选择运送的货物时，选择离该仓库距离最近的货物，即在词语j接收时，我们选择接收与词语j距离近词语i。
我们将作为RWMD。在计算文档距离时，我们可以事先计算该数据集中，每个词语之间的相似度，复杂度为，之后计算两个文档的时，只需要。
WCD vs. RWMD
RWMD相比WCD更紧，具体的验证可以参考论文[2]。
读完论文[2]后，有些问题：
对比实验使用的是欧式距离，欧式距离是否适用于所有的文本表示方式？譬如LDA得到的应该是一个主题概率分布向量，对于概率分布KL距离是否更合适？
Reference:
[2] From word embeddings to document distances, Matt J. kusner et al.
[3] Fast and robust earth mover’s distance, Pele et al.
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：5156次
排名：千里之外
转载：14篇
(1)(1)(1)(4)(1)(3)(2)(3)后使用快捷导航没有帐号？
查看: 1623|回复: 0
机器学习中距离和相似性度量方法【转】
中级会员, 积分 448, 距离下一级还需 52 积分
论坛徽章:4
在和数据挖掘中，我们经常需要知道个体间差异的大小，进而评价个体的相似性和类别。最常见的是数据分析中的相关分析，数据挖掘中的分类和聚类，如 K 最近邻（KNN）和 K 均值（K-Means）等等。根据数据特性的不同，可以采用不同的度量方法。一般而言，定义一个距离函数 d(x,y), 需要满足下面几个准则：1) d(x,x) = 0& && && && && && &&&// 到自己的距离为0
2) d(x,y) &= 0& && && && && && &// 距离非负
3) d(x,y) = d(y,x)& && && && && && & // 对称性: 如果 A 到 B 距离是 a，那么 B 到 A 的距离也应该是 a
4) d(x,k)+ d(k,y) &= d(x,y)& & // 三角形法则: (两边之和大于第三边)这篇博客主要介绍机器学习和数据挖掘中一些常见的距离公式，包括：闵可夫斯基距离欧几里得距离曼哈顿距离切比雪夫距离马氏距离余弦相似度皮尔逊相关系数汉明距离杰卡德相似系数编辑距离DTW 距离KL 散度
1. 闵可夫斯基距离闵可夫斯基距离（Minkowski distance）是衡量数值点之间距离的一种非常常见的方法，假设数值点 P 和 Q 坐标如下：
那么，闵可夫斯基距离定义为：
该距离最常用的 p 是 2 和 1, 前者是欧几里得距离（Euclidean distance），后者是曼哈顿距离（Manhattan distance）。假设在曼哈顿街区乘坐出租车从 P 点到 Q 点，白色表示高楼大厦，灰色表示街道：
绿色的斜线表示欧几里得距离，在现实中是不可能的。其他三条折线表示了曼哈顿距离，这三条折线的长度是相等的。
当 p 趋近于无穷大时，闵可夫斯基距离转化成切比雪夫距离（Chebyshev distance）：
我们知道平面上到原点欧几里得距离（p = 2）为 1 的点所组成的形状是一个圆，当 p 取其他数值的时候呢？
注意，当 p & 1 时，闵可夫斯基距离不再符合三角形法则，举个例子：当 p & 1, (0,0) 到 (1,1) 的距离等于 (1+1)^{1/p} & 2, 而 (0,1) 到这两个点的距离都是 1。
闵可夫斯基距离比较直观，但是它与数据的分布无关，具有一定的局限性，如果 x 方向的幅值远远大于 y 方向的值，这个距离公式就会过度放大 x 维度的作用。所以，在计算距离之前，我们可能还需要对数据进行 z-transform 处理，即减去均值，除以标准差：
: 该维度上的均值
: 该维度上的标准差可以看到，上述处理开始体现数据的统计特性了。这种方法在假设数据各个维度不相关的情况下利用数据分布的特性计算出不同的距离。如果维度相互之间数据相关（例如：身高较高的信息很有可能会带来体重较重的信息，因为两者是有关联的），这时候就要用到马氏距离（Mahalanobis distance）了。
2. 马氏距离考虑下面这张图，椭圆表示等高线，从欧几里得的距离来算，绿黑距离大于红黑距离，但是从马氏距离，结果恰好相反：
马氏距离实际上是利用 Cholesky transformation 来消除不同维度之间的相关性和尺度不同的性质。假设样本点（列向量）之间的协方差对称矩阵是
， 通过 Cholesky Decomposition（实际上是对称矩阵 LU 分解的一种特殊形式，可参考之前的）可以转化为下三角矩阵和上三角矩阵的乘积：
。消除不同维度之间的相关性和尺度不同，只需要对样本点 x 做如下处理： 。处理之后的欧几里得距离就是原样本的马氏距离：为了书写方便，这里求马氏距离的平方）：
下图蓝色表示原样本点的分布，两颗红星坐标分别是（3, 3），（2, -2）:
由于 x， y 方向的尺度不同，不能单纯用欧几里得的方法测量它们到原点的距离。并且，由于 x 和 y 是相关的（大致可以看出斜向右上），也不能简单地在 x 和 y 方向上分别减去均值，除以标准差。最恰当的方法是对原始数据进行 Cholesky 变换，即求马氏距离（可以看到，右边的红星离原点较近）：
将上面两个图的绘制代码和求马氏距离的代码贴在这里，以备以后查阅：
马氏距离的变换和 PCA 分解的颇有异曲同工之妙，不同之处在于：就二维来看，PCA 是将数据主成分旋转到 x 轴（正交矩阵的酉变换），再在尺度上缩放（对角矩阵），实现尺度相同。而马氏距离的 L逆矩阵是一个下三角，先在 x 和 y 方向进行缩放，再在 y 方向进行错切（想象矩形变平行四边形），总体来说是一个没有旋转的仿射变换。
3. 向量内积向量内积是线性代数里最为常见的计算，实际上它还是一种有效并且直观的相似性测量手段。向量内积的定义如下：
直观的解释是：如果 x 高的地方 y 也比较高， x 低的地方 y 也比较低，那么整体的内积是偏大的，也就是说 x 和 y 是相似的。举个例子，在一段长的序列信号 A 中寻找哪一段与短序列信号 a 最匹配，只需要将 a 从 A 信号开头逐个向后平移，每次平移做一次内积，内积最大的相似度最大。信号处理中 DFT 和 DCT 也是基于这种内积运算计算出不同频域内的信号组分（DFT 和 DCT 是正交标准基，也可以看做投影）。向量和信号都是离散值，如果是连续的函数值，比如求区间[-1, 1] 两个函数之间的相似度，同样也可以得到（系数）组分，这种方法可以应用于多项式逼近连续函数，也可以用到连续函数逼近离散样本点（最小二乘问题，）中，扯得有点远了- -!。
向量内积的结果是没有界限的，一种解决办法是除以长度之后再求内积，这就是应用十分广泛的余弦相似度（Cosine similarity）：
余弦相似度与向量的幅值无关，只与向量的方向相关，在文档相似度（）和图片相似性（）计算上都有它的身影。需要注意一点的是，余弦相似度受到向量的平移影响，上式如果将 x 平移到 x+1, 余弦值就会改变。怎样才能实现平移不变性？这就是下面要说的皮尔逊相关系数（Pearson correlation），有时候也直接叫相关系数:
皮尔逊相关系数具有平移不变性和尺度不变性，计算出了两个向量（维度）的相关性。不过，一般我们在谈论相关系数的时候，将 x 与 y 对应位置的两个数值看作一个样本点，皮尔逊系数用来表示这些样本点分布的相关性。
由于皮尔逊系数具有的良好性质，在各个领域都应用广泛，例如，在根据为某一用户查找喜好相似的用户,进而，优点是可以不受每个用户评分标准不同和观看影片数量不一样的影响。
4. 分类数据点间的距离汉明距离（Hamming distance）是指，两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。举个维基百科上的例子：还可以用简单的匹配系数来表示两点之间的相似度——匹配字符数/总字符数。在一些情况下，某些特定的值相等并不能代表什么。举个例子，用 1 表示用户看过该电影，用 0 表示用户没有看过，那么用户看电影的的信息就可用 0,1 表示成一个序列。考虑到电影基数非常庞大，用户看过的电影只占其中非常小的一部分，如果两个用户都没有看过某一部电影（两个都是 0），并不能说明两者相似。反而言之，如果两个用户都看过某一部电影（序列中都是 1），则说明用户有很大的相似度。在这个例子中，序列中等于 1 所占的权重应该远远大于 0 的权重，这就引出下面要说的杰卡德相似系数（Jaccard similarity）。在上面的例子中，用 M11 表示两个用户都看过的电影数目，M10 表示用户 A 看过，用户 B 没看过的电影数目，M01 表示用户 A 没看过，用户 B 看过的电影数目，M00 表示两个用户都没有看过的电影数目。Jaccard 相似性系数可以表示为：
Jaccard similarity 还可以用集合的公式来表达，这里就不多说了。
如果分类数值点是用树形结构来表示的，它们的相似性可以用相同路径的长度来表示，比如，“/product/spot/ballgame/basketball” 离“product/spot/ballgame/soccer/shoes” 的距离小于到 “/product/luxury/handbags” 的距离，以为前者相同父节点路径更长。
5. 序列之间的距离上一小节我们知道，汉明距离可以度量两个长度相同的字符串之间的相似度，如果要比较两个不同长度的字符串，不仅要进行替换，而且要进行插入与删除的运算，在这种场合下，通常使用更加复杂的编辑距离（Edit distance, Levenshtein distance）等算法。编辑距离是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离求的是最少编辑次数，这是一个动态规划的问题，有兴趣的同学可以自己研究研究。时间序列是序列之间距离的另外一个例子。DTW 距离（Dynamic Time Warp）是序列信号在时间或者速度上不匹配的时候一种衡量相似度的方法。神马意思？举个例子，两份原本一样声音样本A、B都说了“你好”，A在时间上发生了扭曲，“你”这个音延长了几秒。最后A:“你~~~好”，B：“你好”。DTW正是这样一种可以用来匹配A、B之间的最短距离的算法。DTW 距离在保持信号先后顺序的限制下对时间信号进行“膨胀”或者“收缩”，找到最优的匹配，与编辑距离相似，这其实也是一个动态规划的问题:
实现代码（转自
6. 概率分布之间的距离前面我们谈论的都是两个数值点之间的距离，实际上两个概率分布之间的距离是可以测量的。在统计学里面经常需要测量两组样本分布之间的距离，进而判断出它们是否出自同一个 population，常见的方法有卡方检验（Chi-Square）和 KL 散度（ KL-Divergence），下面说一说 KL 散度吧。先从信息熵说起，假设一篇文章的标题叫做“黑洞到底吃什么”，包含词语分别是 {黑洞, 到底, 吃什么}, 我们现在要根据一个词语推测这篇文章的类别。哪个词语给予我们的信息最多？很容易就知道是“黑洞”，因为“黑洞”这个词语在所有的文档中出现的概率太低啦，一旦出现，就表明这篇文章很可能是在讲科普知识。而其他两个词语“到底”和“吃什么”出现的概率很高，给予我们的信息反而越少。如何用一个函数 h(x) 表示词语给予的信息量呢？第一，肯定是与 p(x) 相关，并且是负相关。第二，假设 x 和 y 是独立的（黑洞和宇宙不相互独立，谈到黑洞必然会说宇宙）,即 p(x,y) = p(x)p(y), 那么获得的信息也是叠加的，即 h(x, y) = h(x) + h(y)。满足这两个条件的函数肯定是负对数形式：
对假设一个发送者要将随机变量 X 产生的一长串随机值传送给接收者， 接受者获得的平均信息量就是求它的数学期望：
[img]/gif.latex?H[x]%20=%20-\sum%20_x{p(x)\ln%20p(x)}[/img][img]/gif.latex?H[x]%20=%20-\int%20{%20p(x)\ln%20{%20p(x)%20}%20dx%20}[/img]这就是熵的概念。另外一个重要特点是，熵的大小与字符平均最短编码长度是一样的（shannon）。设有一个未知的分布 p(x), 而 q(x) 是我们所获得的一个对 p(x) 的近似，按照 q(x) 对该随机变量的各个值进行编码，平均长度比按照真实分布的 p(x) 进行编码要额外长一些，多出来的长度这就是 KL 散度（之所以不说距离，是因为不满足对称性和三角形法则），即：
KL 散度又叫相对熵（relative entropy）。了解机器学习的童鞋应该都知道，在 Softmax 回归（或者 Logistic 回归），最后的输出节点上的值表示这个样本分到该类的概率，这就是一个概率分布。对于一个带有标签的样本，我们期望的概率分布是：分到标签类的概率是 1， 其他类概率是 0。但是理想很丰满，现实很骨感，我们不可能得到完美的概率输出，能做的就是尽量减小总样本的 KL 散度之和（目标函数）。这就是 Softmax 回归或者 Logistic 回归中 Cost function 的优化过程啦。（PS：因为概率和为 1，一般的 logistic 二分类的图只画了一个输出节点，隐藏了另外一个）
扫一扫加入本版微信群