相似度就是比较两个事物的相似性。一般通过计算事物的特征之间的距离,如果距离小,那么相似度大;如果距离大,那么相似度小。

问题定义:有两个对象X,Y,都包含N维特征,X=(x1,x2,x3,...,xn),Y=(y1,y2,y3,...,yn),计算X和Y的相似性。

闵可夫斯基距离(Minkowski Distance)

曼哈顿距离(Manhattan Distance)

p=1时,闵可夫斯基距离就是曼哈顿距离。

又称城市街区距离,在方正的北京大街打车,行车距离就是曼哈顿距离,如果在山城重庆就不是了。

欧氏距离(Euclidean Distance)

p=2时,闵可夫斯基距离就是欧氏距离。

在平面几何或者立体几何中的距离,通常就是欧氏距离,所以欧氏距离也最容易理解。

Copynp.sqrt(np.sum(np.square(x-y)))

切比雪夫距离(Chebyshev Distance)

p等于无穷大时,闵可夫斯基距离就是切比雪夫距离。

Copydef twoQBXFdis(a,b):
    return max( abs(a[0]-b[0]), abs(a[1]-b[1]))

若将国际象棋棋盘放在二维直角坐标系中,格子的边长定义为1,座标的x轴及y轴和棋盘方格平行,原点恰落在某一格的中心点,则王从一个位置走到其他位置需要的最少步数恰为二个位置的切比雪夫距离,因此切比雪夫距离也称为棋盘距离

"加权(weighted)"闵可夫斯基距离

当样本中不同属性的重要性不同时,可使用"加权距离"(weighted distance)

余弦相似度(Cosine Similarity)

Copynp.dot(x,y)/(np.linalg.norm(x)*np.linalg.norm(y))

余弦相似性取值[-1,1],值越趋于1,表示两个向量的相似度越高。余弦相似度与向量的幅值无关,只与向量的方向相关,在文档相似度(TF-IDF)和图片相似性(histogram)计算上都有它的身影。

二维平面上两向量a(x1,y1),b(x2,y2)之间的夹角余弦公式:

也可直接通过向量运算:

n维空间上两点a(x1,x2……..xn),b(y1,y2……..yn)的夹角余弦公式:

皮尔逊相关系数(Pearson Correlation)

余弦相似度会受到向量的平移影响,怎样才能实现平移不变性?在余弦相似度的基础上,每个向量减去这个向量均值组成的向量,也就是皮尔逊相关系数,有时候也直接叫相关系数。

Copyx_=x-np.mean(x)
y_=y-np.mean(y)
d1=np.dot(x_,y_)/(np.linalg.norm(x_)*np.linalg.norm(y_))

当两个向量均值都为0时,皮尔逊相对系数等于余弦相似性。

马氏距离(Mahalanobis Distance)

一个向量的不同维度如果是不同的量纲,更有甚者,维度之间是相关的,比如身高和体重组成的向量,在闵可夫斯基距离中等同对待,有时,这样是不恰当的。马氏距离利用 Cholesky transformation 消除了不同维度之间的相关性和尺度不同。

其中,S为样本的协方差矩阵。当S是单位阵的时候,马氏距离就是欧式距离;当S是对角阵的时候,马氏距离是加权欧式距离。

很多时候,一个事物的有点也可能会构成它的缺点。这里马氏距离可以消除不同维度之间的不同尺度,就可能放大了变化细微维度的作用。

我们可以按照连续性将属性分为“连续属性”和“离散属性”;也可以按照有序性将属性分为“有序属性”和“无序属性”[1]。上面的相似性度量都是关于“连续”并“有序”属性的,下面给出几个关于“离散属性”和“无序属性”的相似性度量。

汉明距离(Hamming Distance)

两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。

例如:字符串“11110011”与“10010010”之间的汉明距离为3。

汉明距离可以在通信中累计定长二进制字中发生翻转的错误数据位,所以它也被称为信号距离。汉明重量分析在包括信息论、编码理论、密码学等领域都有应用。

如果要比较两个不同长度的字符串,不仅要进行替换,而且要进行插入与删除的运算,在这种场合下,通常使用更加复杂的编辑距离等算法。

杰卡德相似系数(Jaccard Similarity)

杰卡德相似系数是衡量两个集合的相似度一种指标。

Copyup=np.double(np.bitwise_and((x != y),np.bitwise_or(x != 0, y != 0)).sum())
down=np.double(np.bitwise_or(x != 0, y != 0).sum())
d1=(up/down)

杰卡德相似系数是从相似性度量的角度来表述的,从距离度量的角度,则有杰卡德距离(Jaccard Distance)。

杰卡德相似系数和杰卡德距离本质上是一样的,只是表述角度不同。

在聚类中,杰卡德相似系数可以作为聚类的性能度量。在推荐系统中,杰卡德相似系数可以度量两个购买若干商品的用户之间的相似性。

KL散度(Kullback-Leibler Divergence)

又叫相对熵,表示两个随机分布之间的相似性。

可以证明,KL散度大于等于0,当p=q时等于0;KL散度不满足对称性。

Hellinger距离(Hellinger Distance)

Hellinger距离是与KL散度类似的距离,表示随机分布之间的相似性。

当α=0时

这时,Hellinger距离就是两个随机分布取平方根之后的欧式距离,符合距离度量的四个性质,是严格的距离度量。

总结

  • 如果数据存在“分数膨胀“问题,就使用皮尔逊相关系数
  • 如果数据比较密集,变量之间基本都存在共有值,且这些距离数据都是非常重要的,那就使用欧几里得或者曼哈顿距离
  • 如果数据是稀疏的,就使用余弦相似度