距離測定とPython実装

この記事の内容は距離測定とPythonの実装に関するものです。必要な友達は記事の内容を参照してください

転載元: http://www.cnblogs.com/denny402/ p /7027954.html

denny402/p/p/7028 832.html

1. ユークリッド距離 (Euclidean Distance)

ユークリッド空間で。 (1) 二次元平面上の 2 点 a(x1,y1) と b(x2,y2) 間のユークリッド距離:

(2) 2 点 a(x1,y1,z1) と b( ユークリッド距離x2, y2, z2) 間の距離:

(3) 2 つの n 次元ベクトル a(x11,x12,…,x1n) と b(x21,x22,…,x2n) 間のユークリッド距離:

(4) ) はベクトル演算の形式でも表現できます:


Python での実装:

方法 1:

import numpy as np
x=np.random.random(10)
y=np.random.random(10)#方法一：根据公式求解d1=np.sqrt(np.sum(np.square(x-y)))#方法二：根据scipy库求解from scipy.spatial.distance import pdistX=np.vstack([x,y])
d2=pdist(X)

2. マンハッタン ディスタンス (マンハッタン ディスタンス)

この距離の計算方法は名前から推測できます。マンハッタンのある交差点から別の交差点まで運転していると想像してください。走行距離は 2 点間の直線距離ですか?どうやら、建物を通り抜けられない限り、そうではないようです。実際の走行距離はこの「マンハッタン距離」です。そして、これがマンハッタン距離の名前の由来でもあり、マンハッタン距離は

City Block distanceとも呼ばれます。 (1) 2次元平面上の2点a(x1,y1)とb(x2,y2)間のマンハッタン距離
(2) 2つのn次元ベクトルa(x11,x12,…,x1n)とb( x21 間のマンハッタンの距離


, Distance )
チェスをしたことがありますか?キングは 1 回の移動で隣接する 8 マスのいずれかに移動できます。それでは、王がグリッド (x1, y1) からグリッド (x2, y2) に移動するには何歩かかりますか?自分で歩き回ってみてください。最小ステップ数は常に max( | x2-x1 | , | y2-y1 | ) ステップであることがわかります。チェビシェフ距離と呼ばれる同様の距離測定方法があります。

(1) 2次元平面上の2点a(x1,y1)とb(x2,y2)の間のチェビシェフ距離

(2) 2つのn次元ベクトルa(x11,x12,…,x1n) ) と b(x21,x22,…,x2n) チェビシェフ距離

この式の別の等価形式は

です。2 つの式が等価であることがわかりませんか?これがヒントです。それを証明するために、スケーリングとピンチの方法を使用してみてください。

Pythonでの実装:

import numpy as np
x=np.random.random(10)
y=np.random.random(10)#方法一：根据公式求解d1=np.sum(np.abs(x-y))#方法二：根据scipy库求解from scipy.spatial.distance import pdistX=np.vstack([x,y])
d2=pdist(X,'cityblock')

4. 闵可夫斯基距离(Minkowski Distance)
闵氏距离不是一种距离，而是一组距离的定义。
(1) 闵氏距离的定义
       两个n维变量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的闵可夫斯基距离定义为：

也可写成

其中p是一个变参数。
当p=1时，就是曼哈顿距离
当p=2时，就是欧氏距离
当p→∞时，就是切比雪夫距离
       根据变参数的不同，闵氏距离可以表示一类的距离。
(2)闵氏距离的缺点
　　闵氏距离，包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点。
　　举个例子：二维样本(身高,体重)，其中身高范围是150~190，体重范围是50~60，有三个样本：a(180,50)，b(190,50)，c(180,60)。那么a与b之间的闵氏距离（无论是曼哈顿距离、欧氏距离或切比雪夫距离）等于a与c之间的闵氏距离，但是身高的10cm真的等价于体重的10kg么？因此用闵氏距离来衡量这些样本间的相似度很有问题。
       简单说来，闵氏距离的缺点主要有两个：(1)将各个分量的量纲(scale)，也就是“单位”当作相同的看待了。(2)没有考虑各个分量的分布（期望，方差等)可能是不同的。

python中的实现：

import numpy as np
x=np.random.random(10)
y=np.random.random(10)#方法一：根据公式求解,p=2d1=np.sqrt(np.sum(np.square(x-y)))#方法二：根据scipy库求解from scipy.spatial.distance import pdistX=np.vstack([x,y])
d2=pdist(X,'minkowski',p=2)

5. 标准化欧氏距离 (Standardized Euclidean distance )
(1)标准欧氏距离的定义
　　标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。标准欧氏距离的思路：既然数据各维分量的分布不一样，好吧！那我先将各个分量都“标准化”到均值、方差相等吧。均值和方差标准化到多少呢？这里先复习点统计学知识吧，假设样本集X的均值(mean)为m，标准差(standard deviation)为s，那么X的“标准化变量”表示为：

　　标准化后的值 =  ( 标准化前的值  － 分量的均值 ) /分量的标准差
　　经过简单的推导就可以得到两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的标准化欧氏距离的公式：

　　如果将方差的倒数看成是一个权重，这个公式可以看成是一种加权欧氏距离(Weighted Euclidean distance)。

python中的实现：

import numpy as np
x=np.random.random(10)
y=np.random.random(10)

X=np.vstack([x,y])#方法一：根据公式求解sk=np.var(X,axis=0,ddof=1)
d1=np.sqrt(((x - y) ** 2 /sk).sum())#方法二：根据scipy库求解from scipy.spatial.distance import pdistd2=pdist(X,'seuclidean')

6. 马氏距离(Mahalanobis Distance)
（1）马氏距离定义
       有M个样本向量X1~Xm，协方差矩阵记为S，均值记为向量μ，则其中样本向量X到u的马氏距离表示为：

       而其中向量Xi与Xj之间的马氏距离定义为：

       若协方差矩阵是单位矩阵（各个样本向量之间独立同分布）,则公式就成了：

       也就是欧氏距离了。
　　若协方差矩阵是对角矩阵，公式变成了标准化欧氏距离。
python 中的实现：

import numpy as np
x=np.random.random(10)
y=np.random.random(10)#马氏距离要求样本数要大于维数，否则无法求协方差矩阵#此处进行转置，表示10个样本，每个样本2维X=np.vstack([x,y])
XT=X.T#方法一：根据公式求解S=np.cov(X)   #两个维度之间协方差矩阵SI = np.linalg.inv(S) #协方差矩阵的逆矩阵#马氏距离计算两个样本之间的距离，此处共有10个样本，两两组合，共有45个距离。n=XT.shape[0]
d1=[]for i in range(0,n):    for j in range(i+1,n):
        delta=XT[i]-XT[j]
        d=np.sqrt(np.dot(np.dot(delta,SI),delta.T))
        d1.append(d)        
#方法二：根据scipy库求解from scipy.spatial.distance import pdist
d2=pdist(XT,'mahalanobis')

马氏优缺点：

1）马氏距离的计算是建立在总体样本的基础上的，这一点可以从上述协方差矩阵的解释中可以得出，也就是说，如果拿同样的两个样本，放入两个不同的总体中，最后计算得出的两个样本间的马氏距离通常是不相同的，除非这两个总体的协方差矩阵碰巧相同；

2）在计算马氏距离过程中，要求总体样本数大于样本的维数，否则得到的总体样本协方差矩阵逆矩阵不存在，这种情况下，用欧式距离计算即可。

3）还有一种情况，满足了条件总体样本数大于样本的维数，但是协方差矩阵的逆矩阵仍然不存在，比如三个样本点（3，4），（5，6）和（7，8），这种情况是因为这三个样本在其所处的二维空间平面内共线。这种情况下，也采用欧式距离计算。

4）在实际应用中“总体样本数大于样本的维数”这个条件是很容易满足的，而所有样本点出现3）中所描述的情况是很少出现的，所以在绝大多数情况下，马氏距离是可以顺利计算的，但是马氏距离的计算是不稳定的，不稳定的来源是协方差矩阵，这也是马氏距离与欧式距离的最大差异之处。

优点：它不受量纲的影响，两点之间的马氏距离与原始数据的测量单位无关；由标准化数据和中心化数据(即原始数据与均值之差）计算出的二点之间的马氏距离相同。马氏距离还可以排除变量之间的相关性的干扰。缺点：它的缺点是夸大了变化微小的变量的作用。

7. 夹角余弦(Cosine)

コサイン類似度とも呼ばれます。 幾何学における角度の余弦は、2 つのベクトルの方向間の差を測定するために使用できます。この概念は、サンプル ベクトル間の差を測定するために 機械学習 で借用されています。
(1) 2 次元空間におけるベクトル A(x1, y1) とベクトル B(x2, y2) の間の角度のコサイン公式:

(2) 2 つの n 次元サンプル点 a(x11,x12, …, x1n) と b(x21,x22,…,x2n) の間の角度の余弦 同様に、2 つの n 次元サンプル点 a (x11, それらの間の類似度は、余弦と同様の概念を使用して測定できます)内角の。

つまり、

コサインの値の範囲は[-1,1]です。 2 つのベクトル間の角度を見つけ、その角度に対応するコサイン値を取得すると、2 つのベクトルの類似性を特徴付けることができます。角度が小さくなり、0 度に近づくほど、コサイン値は 1 に近づき、方向が一貫しているほど、類似性が高くなります。 2 つのベクトルの方向が完全に逆の場合、それらの間の角度の余弦は最小値 -1 となります。コサイン値が 0 の場合、2 つのベクトルは直交し、夾角は 90 度になります。したがって、コサイン類似度はベクトルの大きさとは関係がなく、ベクトルの方向のみに関係していることがわかります。

import numpy as np
x=np.random.random(10)
y=np.random.random(10)#方法一：根据公式求解d1=np.dot(x,y)/(np.linalg.norm(x)*np.linalg.norm(y))#方法二：根据scipy库求解from scipy.spatial.distance import pdist
X=np.vstack([x,y])
d2=1-pdist(X,'cosine')

两个向量完全相等时，余弦值为1，如下的代码计算出来的d=1。

d=1-pdist([x,x],'cosine')

8. 皮尔逊相关系数（Pearson correlation）

(1) 皮尔逊相关系数的定义

前述のコサイン類似度はベクトルの方向にのみ関係しますが、角度のコサインの式では、x を x+1 に変換すると、そのコサイン値が影響を受けます。変更されます。翻訳の不変性はどのようにして実現できるのでしょうか?これには、ピアソン相関係数 (ピアソン相関) を使用する必要があり、直接相関係数と呼ばれることもあります。

角度の余弦公式が次のように書かれている場合:

がベクトルxとベクトルyの間の角度の余弦を表す場合、ピアソン相関係数表現できる対象:

皮尔逊相关系数具有平移不变性和尺度不变性，计算出了两个向量（维度）的相关性。

 在python中的实现：

import numpy as np
x=np.random.random(10)
y=np.random.random(10)#方法一：根据公式求解x_=x-np.mean(x)
y_=y-np.mean(y)
d1=np.dot(x_,y_)/(np.linalg.norm(x_)*np.linalg.norm(y_))#方法二：根据numpy库求解X=np.vstack([x,y])
d2=np.corrcoef(X)[0][1]

相関係数は、確率変数XとYの間の相関を測定する方法です。相関係数の値の範囲は[-1,1]です。相関係数の絶対値が大きいほど、X と Y の相関が高くなります。 X と Y が線形関係にある場合、相関係数は 1 (正の線形相関) または -1 (負の線形相関) の値を取ります。

9. ハミング距離(ハミング距離)
(1) ハミング距離の定義
2つの等しい長さの文字列s1とs2の間のハミング距離は、一方を他方に変化させることとして定義されます。必要な交換回数。たとえば、文字列「1111」と「1001」の間のハミング距離は 2 です。
用途: 情報符号化 (耐障害性を高めるために、符号間の最小ハミング距離をできるだけ大きくする必要があります)。

Pythonでの実装:

import numpy as npfrom scipy.spatial.distance import pdist
x=np.random.random(10)>0.5y=np.random.random(10)>0.5x=np.asarray(x,np.int32)
y=np.asarray(y,np.int32)#方法一：根据公式求解d1=np.mean(x!=y)#方法二：根据scipy库求解X=np.vstack([x,y])
d2=pdist(X,'hamming')

10. 杰卡德相似系数(Jaccard similarity coefficient)
(1) 杰卡德相似系数
       两个集合A和B的交集元素在A，B的并集中所占的比例，称为两个集合的杰卡德相似系数，用符号J(A,B)表示。

　　杰卡德相似系数是衡量两个集合的相似度一种指标。
(2) 杰卡德距离
       与杰卡德相似系数相反的概念是杰卡德距离(Jaccard distance)。杰卡德距离可用如下公式表示：

　　杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。
(3) 杰卡德相似系数与杰卡德距离的应用
       可将杰卡德相似系数用在衡量样本的相似度上。
　　样本A与样本B是两个n维向量，而且所有维度的取值都是0或1。例如：A(0111)和B(1011)。我们将样本看成是一个集合，1表示集合包含该元素，0表示集合不包含该元素。

 在python中的实现：

import numpy as npfrom scipy.spatial.distance import pdist
x=np.random.random(10)>0.5y=np.random.random(10)>0.5x=np.asarray(x,np.int32)
y=np.asarray(y,np.int32)#方法一：根据公式求解up=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)           

#方法二：根据scipy库求解X=np.vstack([x,y])
d2=pdist(X,'jaccard')

11. 布雷柯蒂斯距离(Bray Curtis Distance)

Bray Curtis距离主要用于生态学和环境科学，计算坐标之间的距离。该距离取值在[0,1]之间。它也可以用来计算样本之间的差异。

 

サンプルデータ:

計算:

Python で:

import numpy as npfrom scipy.spatial.distance import pdist
x=np.array([11,0,7,8,0])
y=np.array([24,37,5,18,1])#方法一：根据公式求解up=np.sum(np.abs(y-x))
down=np.sum(x)+np.sum(y)
d1=(up/down)           
#方法二：根据scipy库求解X=np.vstack([x,y])
d2=pdist(X,'braycurtis')

 相关推荐：

python实现简单的图片文字识别脚本

python实现kMeans算法的详解

以上が距離測定とPython実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。