rambo

距离及相似性度量

距离是不相似性的一种度量。要把一个量称为距离应满足三条性质:

  • d_{xz}\ge 0,若x=z,则d_{xz}=0    反身性
  • d_{xz}=d_{zx}    对称性
  • d_{xz}\leq d_{xy}+d_{yz}   三角不等式

 

一、pdist

Pairwise distance between pairs of objects
Syntax
D = pdist(X)
D = pdist(X,distance)
Description
D = pdist(X)    计算 X 中各对行向量的相互距离(X是一个m\times n的矩阵). 这里D 要特别注意,D 是一个长为m(m-1)/2的行向量.
可以这样理解 D 的生成:首先生成一个 X 的距离方阵,由于该方阵是对称的,令对角线上的元素为0,所以取此方阵的下三角元素,按照Matlab中矩阵的按列存储原则,此下三角各元素的索引排列即为(2,1), (3,1), ..., (m,1), (3,2), ..., (m,2), ..., (m,m–1).可以用命令 squareform(D) 将此行向量转换为原距离方阵.(squareform函数是专门干这事的,其逆变换是也是squareform)
D = pdist(X,distance)     使用指定的距离
  • 欧几里德距离  Euclidean distance('euclidean')

d_{s,\;t}^2 = \left( {{x_s} - {x_t}} \right) \cdot \left( {{x_s} - {x_t}} \right)'

欧氏距离虽然很有用,但也有明显的缺点。
一:它将样品的不同属性(即各指标或各变量)之间的差别等同看待,这一点有时不能满足实际要求。
二:它没有考虑各变量的数量级(量纲),容易犯大数吃小数的毛病。所以,可以先对原始数据进行规范化处理再进行距离计算。

  • 标准欧几里德距离  Standardized Euclidean distance('seuclidean')

d_{s,\;t}^2 = \left( {{x_s} - {x_t}} \right){V^{ - 1}}\left( {{x_s} - {x_t}} \right)'

where V is the n\times n diagonal matrix whose jth diagonal element is S(j)^{2}, where S is the vector of standard deviations.
相比单纯的欧氏距离,标准欧氏距离能够有效的解决上述缺点。注意,这里的V在许多Matlab函数中是可以自己设定的,不一定非得取标准差,可以依据各变量的重要程度设置不同的值,如knnsearch函数中的Scale属性。

  • 马哈拉诺比斯距离  Mahalanobis distance('mahalanobis')
 d_{s,\;t}^2 = \left( {{x_s} - {x_t}} \right){C^{ - 1}}\left( {{x_s} - {x_t}} \right)'
where C is the covariance matrix.
马氏距离是由P. C. Mahalanobis提出的,表示数据的协方差距离。它是一种有效的计算两个未知样本集的相似度的方法。与欧式距离不同的是它考虑到各种特性之间的联系(例如:一条关于身高的信息会带来一条关于体重的信息,因为两者是有关联的)并且是尺度无关的(scale-invariant),即独立于测量尺度。

如果协方差矩阵为单位矩阵,那么马氏距离就简化为欧式距离,如果协方差矩阵为对角阵,则其也可称为正规化的欧氏距离.
马氏优缺点:

  1)马氏距离的计算是建立在总体样本的基础上的,因为C是由总样本计算而来,所以马氏距离的计算是不稳定的;
  2)在计算马氏距离过程中,要求总体样本数大于样本的维数
  3)协方差矩阵的逆矩阵可能不存在
  • 曼哈顿距离(城市区块距离)  City block metric('cityblock')

d_{s,\;t}^{} = \sum\limits_{j = 1}^n {\left| {{x_{{s_j}}} - {x_{{t_j}}}} \right|}

  • 切比雪夫距离  Chebychev distance('chebychev')

d_{s,\;t}^{} = {\max _j}\left| {{x_{{s_j}}} - {x_{{t_j}}}} \right|

  • 闵可夫斯基距离  Minkowski metric('minkowski')

d_{s,\;t}^{} = \sqrt[p]{{\sum\limits_{j = 1}^n {{{\left| {{x_{{s_j}}} - {x_{{t_j}}}} \right|}^p}} }}

Notice that for the special case of p = 1, the Minkowski metric gives the city block metric, for the special case of p = 2, the Minkowski metric gives the Euclidean distance, and for the special case of p = ∞, the Minkowski metric gives the Chebychev distance.
闵可夫斯基距离由于是欧氏距离的推广,所以其缺点与欧氏距离大致相同。

  • 夹角余弦距离  Cosine distance('cosine')

d_{s,\;t}^{} = 1 - \frac{{{x_s}{x_t}'}}{{{{\left\| {{x_s}} \right\|}_2} \cdot {{\left\| {{x_t}} \right\|}_2}}}

与Jaccard距离相比,Cosine距离不仅忽略0-0匹配,而且能够处理非二元向量,即考虑到变量值的大小

  • 相关距离   Correlation distance('correlation')  特别有用

d_{s,\;t}^{} = 1 - \frac{{{x_s}{x_t}'}}{{\sqrt {\left( {{x_s} - \overline {{x_s}} } \right) \cdot \left( {{x_s} - \overline {{x_s}} } \right)'} \cdot \sqrt {\left( {{x_t} - \overline {{x_t}} } \right) \cdot \left( {{x_t} - \overline {{x_t}} } \right)'} }}

 Correlation距离主要用来度量两个向量的线性相关程度。

  • 汉明距离  Hamming distance('hamming')

d_{s,\;t}^{} = \left( {\frac{{\# ({x_{{s_j}}} \ne {x_{{t_j}}})}}{n}} \right)

 两个向量之间的汉明距离的定义为两个向量不同的变量个数所占变量总数的百分比。

  • 杰卡德距离   Jaccard distance('jaccard')

d_{s,\;t}^{} = \left( {\frac{{\# \left[ {({x_{{s_j}}} \ne {x_{{t_j}}}) \cap \left( {({x_{{s_j}}} \ne 0) \cup ({x_{{t_j}}} \ne 0)} \right)} \right]}}{{\# \left[ {({x_{{s_j}}} \ne 0) \cup ({x_{{t_j}}} \ne 0)} \right]}}} \right)

   Jaccard距离常用来处理仅包含非对称的二元(0-1)属性的对象。很显然,Jaccard距离不关心0-0匹配,而Hamming距离关心0-0匹配。

  • Spearman distance  ('spearman')

d_{s,\;t}^{} = 1 - \frac{{\left( {{r_s} - \overline {{r_s}} } \right)\left( {{r_t} - \overline {{r_t}} } \right)'}}{{\sqrt {\left( {{r_s} - \overline {{r_s}} } \right)\left( {{r_s} - \overline {{r_s}} } \right)'} \sqrt {\left( {{r_t} - \overline {{r_t}} } \right)\left( {{r_t} - \overline {{r_t}} } \right)'} }}

  • where
    • rsj is the rank of xsj taken over x1j, x2j, ...xmj, as computed by tiedrank
    • rs and rt are the coordinate-wise rank vectors of xs and xt, i.e., rs = (rs1, rs2, ... rsn)
    • \overline {{r_s}} = \frac{1}{n}\sum\limits_j {{r_{{s_j}}}} = \frac{{n + 1}}{2}
    • \overline{{r_t}} = \frac{1}{n}\sum\limits_j {{r_{{t_j}}}} = \frac{{n + 1}}{2}

二、pdist2

Pairwise distance between two sets of observations
Syntax
D = pdist2(X,Y)
D = pdist2(X,Y,distance)
D = pdist2(X,Y,'minkowski',P)
D = pdist2(X,Y,'mahalanobis',C)
D = pdist2(X,Y,distance,'Smallest',K)
D = pdist2(X,Y,distance,'Largest',K)
[D,I] = pdist2(X,Y,distance,'Smallest',K)
[D,I] = pdist2(X,Y,distance,'Largest',K)
Description
这里 X 是 mx-by-n 维矩阵,Y 是 my-by-n 维矩阵,生成 mx-by-my 维距离矩阵 D。
[D,I] = pdist2(X,Y,distance,'Smallest',K)    生成 K-by-my 维矩阵 D 和同维矩阵 I,其中D的每列是原距离矩阵中最小的元素,按从小到大排列,I 中对应的列即为其索引号。注意,这里每列各自独立地取 K 个最小值。
   例如,令原mx-by-my 维距离矩阵为A,则 K-by-my 维矩阵 D 满足 D(:,j)=A(I(:,j),j).
参考:
2、模式识别