机械学习远距离和相似性衡量方法

 

在机械学习和数据挖掘中,大家平时要求精晓个体间距离的尺寸,进而评价个体的相似性和类型。最普遍的是数额解析中的相关分析,数据挖掘中的分类和聚类算法,如
K 近期邻(KNN)和 K
均值(K-Means)等等。依据数据个性的差别,可以动用分裂的心路方法。一般而言,定义一个离开函数
d(x,y), 必要满足上边几个准则:

一) d(x,x) = 0                    // 到自身的离开为0
二) d(x,y) >= 0                  // 距离非负
3) d(x,y) = d(y,x)                   // 对称性: 如若 A 到 B 距离是
a,那么 B 到 A 的偏离也应有是 a
四) d(x,k)+ d(k,y) >= d(x,y)    // 三角形法则: (两边之和超出第二边)

那篇博客首要介绍机器学习和多少挖掘中有个别广大的距离公式,包含:

  1. 闵可夫斯基距离
  2. 欧几里得距离
  3. 曼哈顿相距
  4. 切比雪夫距离
  5. 马氏距离
  6. 余弦相似度
  7. Pearson相关周详
  8. 汉明距离
  9. 杰卡德相似周密
  10. 编写距离
  11. DTW 距离
  12. KL 散度

 

一. 闵可夫斯基距离

闵可夫斯基距离(Minkowski
distance)是度量数值点之间距离的一种相当广阔的章程,要是数值点 P 和 Q
坐标如下:

图片 1

那正是说,闵可夫斯基距离定义为:

图片 2

该距离最常用的 p 是 2 和 1, 前者是欧几里得距离(Euclidean
distance),后者是曼哈顿相距(Manhattan
distance)。借使在曼哈顿街区乘坐出租汽车车从 P 点到 Q
点,白灰代表高堂大厦,黛青表示街道:

图片 3

宝石红的斜线表示欧几里得距离,在切切实实中是非常小概的。别的三条折线表示了曼哈顿相距,那三条折线的尺寸是很是的。

当 p 趋近于无穷大时,闵可夫斯基距离转化成切比雪夫距离(Chebyshev
distance):

图片 4

大家精晓平面上到原点欧几里得距离(p = 贰)为 1的点所组成的样子是三个圆,当 p 取其他数值的时候吧?

图片 5

注意,当 p < 一 时,闵可夫斯基距离不再符合三角形法则,举个例证:当
< 1, (0,0) 到 (壹,一) 的偏离等于 (1+壹)^{1/p} > 2, 而 (0,一)
到那八个点的相距都以 一。

闵可夫斯基距离比较直观,可是它与数据的分布非亲非故,具有自然的局限性,如若 x
方向的幅值远远出乎 y 方向的值,那几个距离公式就会超负荷放大 x
维度的成效。所以,在总括距离以前,大家或者还索要对数据开始展览 z-transform 处理,即减去均值,除以标准差:

图片 6%5Cmapsto%20(%5Cfrac%7Bx_1%20-%20%5Cmu%20_x%7D%7B%5Csigma%20_x%7D,%20%5Cfrac%7By_1%20-%20%5Cmu%20_y%7D%7B%5Csigma%20_y%7D))

图片 7 : 该维度上的均值
图片 8 : 该维度上的标准差

能够观看,上述处理起来反映数据的总计本性了。那种艺术在假若数据各种维度不相干的情事下利用数据分布的特色总结出不相同的离开。即使维度相互之间数据有关(例如:身高较高的音讯很有希望会拉动体重较重的音信,因为两者是有涉嫌的),那时候就要动用马氏距离(Mahalanobis
distance)了。

 

二. 马氏距离

设想下边那张图,椭圆代表等高线,从欧几里得的相距来算,绿黑距离超过红黑距离,可是从马氏距离,结果恰好相反:

图片 9

马氏距离实际上是利用 Cholesky transformation
来解除区别维度之间的相关性标准不1的性质。若是样本点(列向量)之间的协方差对称矩阵是 图片 10 ,
通过 Cholesky Decomposition(实际上是对称矩阵 LU
分解的1种格外格局,可参看此前的博客)可以转化为下三角矩阵和上三角矩阵的乘积: 图片 11 。化解分歧维度之间的相关性和规范不1,只须要对样本点
x
做如下处理:图片 12) 。处理未来的欧几里得距离正是样子本的马氏距离:为了书写方便,那里求马氏距离的平方):

图片 13

下图铁黄代表原样本点的遍布,两颗红星坐标分别是(三, 三),(二, -贰):

图片 14

鉴于 x, y
方向的准绳不1,无法单纯用欧几里得的不贰法门衡量它们到原点的距离。并且,由于
x 和 y 是连锁的(大约能够见见斜向右上),也无法大致地在 x 和 y
方向上分别减去均值,除以标准差。最相宜的点子是对本来数据开始展览 Cholesky
变换,即求马氏距离(能够看到,右边的红星离原点较近):

图片 15

将方面四个图的绘图代码和求马氏距离的代码贴在此间,以备未来翻看:

图片 16图片 17

 1 # -*- coding=utf-8 -*-
 2 
 3 # code related at: http://www.cnblogs.com/daniel-D/
 4 
 5 import numpy as np
 6 import pylab as pl
 7 import scipy.spatial.distance as dist
 8 
 9 
10 def plotSamples(x, y, z=None):
11 
12     stars = np.matrix([[3., -2., 0.], [3., 2., 0.]])
13     if z is not None:
14         x, y = z * np.matrix([x, y])
15         stars = z * stars
16 
17     pl.scatter(x, y, s=10)    # 画 gaussian 随机点
18     pl.scatter(np.array(stars[0]), np.array(stars[1]), s=200, marker='*', color='r')  # 画三个指定点
19     pl.axhline(linewidth=2, color='g') # 画 x 轴
20     pl.axvline(linewidth=2, color='g')  # 画 y 轴
21 
22     pl.axis('equal')
23     pl.axis([-5, 5, -5, 5])
24     pl.show()
25 
26 
27 # 产生高斯分布的随机点
28 mean = [0, 0]      # 平均值
29 cov = [[2, 1], [1, 2]]   # 协方差
30 x, y = np.random.multivariate_normal(mean, cov, 1000).T
31 plotSamples(x, y)
32 
33 covMat = np.matrix(np.cov(x, y))    # 求 x 与 y 的协方差矩阵
34 Z = np.linalg.cholesky(covMat).I  # 仿射矩阵
35 plotSamples(x, y, Z)
36 
37 # 求马氏距离 
38 print '\n到原点的马氏距离分别是:'
39 print dist.mahalanobis([0,0], [3,3], covMat.I), dist.mahalanobis([0,0], [-2,2], covMat.I)
40 
41 # 求变换后的欧几里得距离
42 dots = (Z * np.matrix([[3, -2, 0], [3, 2, 0]])).T
43 print '\n变换后到原点的欧几里得距离分别是:'
44 print dist.minkowski([0, 0], np.array(dots[0]), 2), dist.minkowski([0, 0], np.array(dots[1]), 2)

View Code

 

马氏距离的变换和 PCA
分解的白化处理颇有异曲同工之妙,不一致之处在于:就贰维来看,PCA
是将数据主成分旋转到 x
轴(正交矩阵的酉变换),再在标准化上缩放(对角矩阵),达成标准化相同。而马氏距离的
L逆矩阵是三个下三角,先在 x 和 y 方向拓展缩放,再在 y
方向拓展错切(想象矩形变平行四边形),总体来说是四个从未有过转动的仿射变换。

 

3. 向量内积

向量内积是线性代数里极其广泛的盘算,实际上它如故1种有效并且直观的相似性衡量手段。向量内积的定义如下:

图片 18%20=%20%5Clangle%20x,%20y%20%5Crangle%20=%20%5Csum_i%20x_i%20y_i)

直观的阐述是:假若 x 高的地方 y 也相比较高, x 低的地点 y
也正如低,那么全部的内积是偏大的,约等于说 x 和 y
是相似的。举个例子,在一段长的队列复信号 A 中追寻哪1段与短类别时限信号 a
最匹配,只须要将 a 从 A
复信号起头每种向后运动,每趟运动做贰次内积,内积最大的相似度最大。能量信号处理中
DFT 和 DCT 也是依照那种内积运算总计出区别频域内的功率信号组分(DFT 和 DCT
是正交标准基,也足以用作投影)。向量和复信号都以离散值,假如是接二连三的函数值,比如求区间[-1, 1] 多个函数之间的相似度,同样也能够取得(周全)组分,那种艺术能够应用于多项式逼近一连函数,也足以用到三番五次函数逼近离散样本点(最小贰乘难点,OLS
coefficients
)中,扯得有点远了-
-!。

向量内积的结果是不曾界限的,1种消除办法是除以长度之后再求内积,那便是选取尤其普遍的余弦相似度(Cosine
similarity):

图片 19%20=%20%5Cfrac%7B%5Csum_i%20x_i%20y_i%7D%7B%20%5Csqrt%7B%20%5Csum_i%20x_i%5E2%7D%20%5Csqrt%7B%20%5Csum_i%20y_i%5E2%20%7D%20%7D%20%0D%0A=%20%5Cfrac%7B%20%5Clangle%20x,y%20%5Crangle%20%7D%7B%20%7C%7Cx%7C%7C%5C%20%7C%7Cy%7C%7C%20%7D)

余弦相似度与向量的幅值非亲非故,只与向量的趋势相关,在文书档案相似度(TF-IDF)和图表相似性(histogram)总计上都有它的身影。须求留意一点的是,余弦相似度受到向量的活动影响,上式假设将
x 平移到 x+1,
余弦值就会改变。怎样才能达成活动不变性?那正是上面要说的Pearson相关周密(Pearsoncorrelation),有时候也一直叫相关周密:

图片 20%20&=%20%5Cfrac%7B%20%5Csum_i%20(x_i-%5Cbar%7Bx%7D)%20(y_i-%5Cbar%7By%7D)%20%7D%7B%20%5Csqrt%7B%5Csum%20(x_i-%5Cbar%7Bx%7D)%5E2%7D%20%5Csqrt%7B%20%5Csum%20(y_i-%5Cbar%7By%7D)%5E2%20%7D%20%7D%20&=%20%5Cfrac%7B%5Clangle%20x-%5Cbar%7Bx%7D,%5C%20y-%5Cbar%7By%7D%20%5Crangle%7D%7B%20%7C%7Cx-%5Cbar%7Bx%7D%7C%7C%5C%20%7C%7Cy-%5Cbar%7By%7D%7C%7C%7D%20%20%20&=%20CosSim(x-%5Cbar%7Bx%7D,%20y-%5Cbar%7By%7D)%20%5Cend%7Balign%7D)

Pearson相关周到具有活动不变性和规格不变性,计算出了八个向量(维度)的相关性。可是,1般大家在商讨相关周密的时候,将
x 与 y
对应地方的多少个数值作为一个样本点,Pearson周详用来表示这一个样本点分布的相关性。

图片 21

出于Pearson全面具有的好好性质,在种种领域都接纳广泛,例如,在推荐系统基于为某1用户查找喜好相似的用户,进而提供推荐,优点是足以不受种种用户评分标准区别和阅览影视数量不平等的震慑。

 

4. 分拣数据点间的距离

汉明距离(Hamming
distance)是指,多少个等长字符串s1与s贰之间的汉明距离定义为将中间3个变成此外1个所须求作的微乎其微替换次数。举个维基百科上的事例:

图片 22

还是能用简短的万分全面来代表两点之间的相似度——匹配字符数/总字符数。

在有的处境下,某个特定的值十三分并不可能表示如何。举个例子,用 1表示用户看过该摄像,用 0 表示用户并未有看过,那么用户看电影的的消息就可用
0,一代表成二个队列。考虑到影视基数越发巨大,用户看过的影视只占当中年老年大小的一有个别,假诺多少个用户都不曾看过某1部影片(八个都以0),并不可能证实二者相似。反而言之,若是三个用户都看过某壹部影片(类别中都是一),则评释用户有非常的大的相似度。在那几个例子中,类别中分外 一所占的权重应该远远出乎 0
的权重,那就引出下面要说的杰Card相似周到(Jaccard similarity)。

在上边的事例中,用 M11 表示四个用户都看过的影视多少,M10 表示用户 A
看过,用户 B 没看过的电影多少,M0一 表示用户 A 没看过,用户 B
看过的影片多少,M00 表示多少个用户都并未看过的影视多少。Jaccard
相似性周全能够表示为:

图片 23

Jaccard similarity 还足以用集合的公式来表明,那里就不多说了。

假如分类数值点是用树形结构来表示的,它们的相似性能够用平等路线的长度来代表,比如,“/product/spot/ballgame/basketball”
离“product/spot/ballgame/soccer/shoes” 的相距小于到
“/product/luxury/handbags” 的距离,以为前者一样父节点路径更长。

 

五. 行列之间的离开

上一小节大家领会,汉明距离能够衡量五个长度相同的字符串之间的相似度,如果要相比两个例外交市长短的字符串,不仅要实行轮换,而且要开始展览插队与删除的运算,在那种场所下,平时选用进一步错综复杂的编写距离(艾德it
distance, Levenshtein
distance)等算法。编辑距离是指四个字串之间,由二个转成另二个所需的最少编辑操作次数。许可的编辑操作蕴涵将贰个字符替换到另1个字符,插入一个字符,删除1个字符。编辑距离求的是至少编辑次数,那是一个动态规划的标题,有趣味的校友能够自身研商研究。

时光系列是系列之间相距的其余1个例证。DTW 距离(Dynamic Time
Warp)是类别能量信号在时间照旧速度上不匹配的时候1种度量相似度的法子。神马意思?举个例子,两份原本一样声音样本A、B都说了“你好”,A在时光上发生了扭转,“你”这几个音延长了几秒。最终A:“你~~~好”,B:“你好”。DTW就是那样一种可以用来匹配A、B之间的最短距离的算法。

DTW
距离在维系模拟信号先后顺序的范围下对时间实信号进行“膨胀”或许“缩短”,找到最优的格外,与编辑距离相似,那实在也是一个动态规划的标题:

图片 24

落到实处代码(转自 McKelvin’s
Blog
 ):

图片 25图片 26

 1 #!/usr/bin/python2
 2 # -*- coding:UTF-8 -*-
 3 # code related at: http://blog.mckelv.in/articles/1453.html
 4  
 5 import sys
 6  
 7 distance = lambda a,b : 0 if a==b else 1
 8  
 9 def dtw(sa,sb):
10     '''
11     >>>dtw(u"干啦今今今今今天天气气气气气好好好好啊啊啊", u"今天天气好好啊")
12     2
13     '''
14     MAX_COST = 1<<32
15     #初始化一个len(sb) 行(i),len(sa)列(j)的二维矩阵
16     len_sa = len(sa)
17     len_sb = len(sb)
18     # BUG:这样是错误的(浅拷贝): dtw_array = [[MAX_COST]*len(sa)]*len(sb)
19     dtw_array = [[MAX_COST for i in range(len_sa)] for j in range(len_sb)]
20     dtw_array[0][0] = distance(sa[0],sb[0])
21     for i in xrange(0, len_sb):
22         for j in xrange(0, len_sa):
23             if i+j==0:
24                 continue
25             nb = []
26             if i > 0: nb.append(dtw_array[i-1][j])
27             if j > 0: nb.append(dtw_array[i][j-1])
28             if i > 0 and j > 0: nb.append(dtw_array[i-1][j-1])
29             min_route = min(nb)
30             cost = distance(sa[j],sb[i])
31             dtw_array[i][j] = cost + min_route
32     return dtw_array[len_sb-1][len_sa-1]
33  
34  
35 def main(argv):
36     s1 = u'干啦今今今今今天天气气气气气好好好好啊啊啊'
37     s2 = u'今天天气好好啊'
38     d = dtw(s1, s2)
39     print d
40     return 0
41  
42 if __name__ == '__main__':
43     sys.exit(main(sys.argv))

View Code

 

陆. 概率分布之间的偏离

日前大家斟酌的都是多个数值点之间的偏离,实际上四个概率分布之间的相距是足以衡量的。在总结学里面常常必要度量两组样本分布之间的偏离,进而判断出它们是不是来自同三个population,常见的点子有卡方检测(Chi-Square)和 KL 散度
KL-Divergence),上面说一说 KL 散度吧。

先从音信熵提及,假若一篇小说的标题叫做“黑洞到底吃什么样”,包涵词语分别是
{黑洞, 到底, 吃什么样},
我们今天要依据一个用语猜测那篇小说的门类。哪个词语给予大家的音信最多?很不难就明白是“黑洞”,因为“黑洞”那几个词语在全数的文书档案中出现的票房价值太低啦,一旦出现,就标明那篇小说很也许是在讲科学普及知识。而其余七个词语“到底”和“吃哪些”出现的票房价值很高,给予大家的新闻反而越少。怎样用2个函数
h(x) 表示词语给予的音讯量呢?第3,肯定是与 p(x)
相关,并且是负连带。第3,假诺 x 和 y
是单身的(黑洞和大自然不彼此独立,聊起黑洞必然会说宇宙),即 p(x,y) =
p(x)p(y), 那么得到的消息也是增大的,即 h(x, y) = h(x) +
h(y)。满意那五个规范的函数肯定是负对数情势:

图片 27%20=%20-ln%5C%20p(x))

对借使3个发送者要将随意变量 X 发生的一长串随机值传送给接收者,
接受者获得的平分音信量正是求它的数学期望:

图片 28%5Cln%20p(x)%7D)

图片 29%5Cln%20%7B%20p(x)%20%7D%20dx%20%7D)

那正是熵的概念。其它2个珍视特色是,熵的大大小小与字符平均最短编码长度是1律的(shannon)。设有2个茫然的分布
p(x), 而 q(x) 是我们所收获的2个对 p(x) 的切近,依据 q(x)
对该随机变量的逐条值举办编码,平均长度比根据实际分布的 p(x)
举行编码要额外交参谋长1些,多出去的尺寸那便是 KL
散度(之所以不说距离,是因为不满足对称性和三角形法则),即:

图片 30

KL 散度又叫相对熵(relative
entropy)。通晓机器学习的童鞋应该都知情,在 Softmax 回归(或许 Logistic
回归),最终的出口节点上的值表示这几个样本分到此类的几率,那就是3个可能率分布。对于2个含有标签的样本,大家盼望的几率分布是:分到标签类的票房价值是
一, 其余类可能率是
0。不过杰出很充实,现实很骨感,大家不容许取得周到的概率输出,能做的正是竭尽减小总样本的
KL 散度之和(目的函数)。那正是 Softmax 回归或然 Logistic 回归中 Cost
function 的优化进程啦。(PS:因为概率和为 一,一般的 logistic
二分拣的图只画了二个输出节点,隐藏了其余2个)

 


 

待补充的方法:

卡方检查实验 Chi-Square

度量 categorical attributes 相关性的 mutual information

Spearman’s rank coefficient

Earth Mover’s Distance

SimRank 迭代算法等。

 

参考资料:

  1. 相距和相似性衡量
  2. Machine Learning: Measuring Similarity and
    Distance
  3. What is Mahalanobis
    distance?
  4. Cosine similarity, Pearson correlation, and OLS
    coefficients
  5. 机械学习中的相似性度量
  6. 动态时间归整 | DTW | Dynamic Time
    Warping

 

You can leave a response, or trackback from your own site.

Leave a Reply

网站地图xml地图