浓缩距离matrix如何工作？ （pdist）
scipy.spatial.distance.pdist返回一个浓缩距离matrix。 从文档 ：
返回一个压缩的距离matrixY.对于每个和（其中），度量dist（u = X [i]，v = X [j]）被计算并存储在条目ij中。
我以为我的意思是i*j 。 但是我想我可能是错的。 考虑
X = array([[1,2], [1,2], [3,4]]) dist_matrix = pdist(X)
那么文档说dist(X[0], X[2])应该是dist_matrix[0*2] 。 然而， dist_matrix[0*2]是0 – 不应该是2.8。
给定i和j ，我应该用什么公式来访问两个向量的相似性？
你可以这样看：假设x是m乘n。 每次select两个的可能的m行对是itertools.combinations(range(m), 2) ，例如对于m=3 ：
>>> import itertools >>> list(combinations(range(3),2)) [(0, 1), (0, 2), (1, 2)]
因此，如果d = pdist(x) ， combinations(range(m), 2))第k个元组combinations(range(m), 2))给出与d[k]相关联的x的行的索引。
例：
>>> x = array([[0,10],[10,10],[20,20]]) >>> pdist(x) array([ 10. , 22.36067977, 14.14213562])
第一个元素是dist(x[0], x[1]) ，第二个元素是dist(x[0], x[1]) ，第三个元素是dist(x[0], x[1]) dist(x[1], x[2]) 。
或者，您可以将其视为矩形距离matrix的上三angular部分中的元素，串成一维数组。
例如
>>> squareform(pdist(x)) array([[ 0. , 10. , 22.361], [ 10. , 0. , 14.142], [ 22.361, 14.142, 0. ]]) >>> y = array([[0,10],[10,10],[20,20],[10,0]]) >>> squareform(pdist(y)) array([[ 0. , 10. , 22.361, 14.142], [ 10. , 0. , 14.142, 10. ], [ 22.361, 14.142, 0. , 22.361], [ 14.142, 10. , 22.361, 0. ]]) >>> pdist(y) array([ 10. , 22.361, 14.142, 14.142, 10. , 22.361])
压缩matrix的向量对应于方阵的底三angular区域。 要转换为三angular形区域中的一个点，需要计算三angular形左边的点数，以及列中上面的数字。
你可以使用下面的函数来转换：
q = lambda i,j,n: n*j - j*(j+1)/2 + i - 1 - j
检查：
import numpy as np from scipy.spatial.distance import pdist, squareform x = np.random.uniform( size = 100 ).reshape( ( 50, 2 ) ) d = pdist( x ) ds = squareform( d ) for i in xrange( 1, 50 ): for j in xrange( i ): assert ds[ i, j ] == d[ q( i, j, 50 ) ]
压缩距离matrix到全距离matrix
由pdist返回的压缩距离matrix可以通过使用scipy.spatial.distance.squareform转换为全距离matrix：
>>> import numpy as np >>> from scipy.spatial.distance import pdist, squareform >>> points = np.array([[0,1],[1,1],[3,5], [15, 5]]) >>> dist_condensed = pdist(points) >>> dist_condensed array([ 1. , 5. , 15.5241747 , 4.47213595, 14.56021978, 12. ])
使用squareform转换为全matrix：
>>> dist = squareform(dist_condensed) array([[ 0. , 1. , 5. , 15.5241747 ], [ 1. , 0. , 4.47213595, 14.56021978], [ 5. , 4.47213595, 0. , 12. ], [ 15.5241747 , 14.56021978, 12. , 0. ]])
点i，j之间的距离存储在dist [i，j]中：
>>> dist[2, 0] 5.0 >>> np.linalg.norm(points[2] - points[0]) 5.0
指数以压缩指数
可以将用于访问方阵元素的索引转换为压缩matrix中的索引：
def square_to_condensed(i, j, n): assert i != j, "no diagonal elements in condensed matrix" if i < j: i, j = j, i return n*j - j*(j+1)/2 + i - 1 - j
例：
>>> square_to_condensed(1, 2, len(points)) 3 >>> dist_condensed[3] 4.4721359549995796 >>> dist[1,2] 4.4721359549995796
指数的简明指数
另外，如果没有sqaureform，在运行时和内存消耗方面则更好：
import math def calc_row_idx(k, n): return int(math.ceil((1/2.) * (- (-8*k + 4 *n**2 -4*n - 7)**0.5 + 2*n -1) - 1)) def elem_in_i_rows(i, n): return i * (n - 1 - i) + (i*(i + 1))/2 def calc_col_idx(k, i, n): return int(n - elem_in_i_rows(i + 1, n) + k) def condensed_to_square(k, n): i = calc_row_idx(k, n) j = calc_col_idx(k, i, n) return i, j
例：
>>> condensed_to_square(3, 4) (1.0, 2.0)
运行时与squareform进行比较
>>> import numpy as np >>> from scipy.spatial.distance import pdist, squareform >>> points = np.random.random((10**4,3)) >>> %timeit dist_condensed = pdist(points) 1 loops, best of 3: 555 ms per loop
创buildsqaureform变得非常缓慢：
>>> dist_condensed = pdist(points) >>> %timeit dist = squareform(dist_condensed) 1 loops, best of 3: 2.25 s per loop
如果我们用最大距离search两个点，那么在全matrix中search为O（n）而仅以O（n / 2）的浓缩formssearch并不奇怪：
>>> dist = squareform(dist_condensed) >>> %timeit dist_condensed.argmax() 10 loops, best of 3: 45.2 ms per loop >>> %timeit dist.argmax() 10 loops, best of 3: 93.3 ms per loop
在这两种情况下获得这两个点的信息几乎没有时间，但是计算精简指数当然会有一些开销：
>>> idx_flat = dist.argmax() >>> idx_condensed = dist.argmax() >>> %timeit list(np.unravel_index(idx_flat, dist.shape)) 100000 loops, best of 3: 2.28 µs per loop >>> %timeit condensed_to_square(idx_condensed, len(points)) 100000 loops, best of 3: 14.7 µs per loop
如果要访问对应于平方距离matrix（i，j）元素的pdist元素，math如下：假设i < j （否则翻转索引）如果i == j ，答案是0。
X = random((N,m)) dist_matrix = pdist(X)
那么第（i，j）个元素是dist_matrix [ind]
ind = (N - array(range(1,i+1))).sum() + (j - 1 - i).
这是上三angular版本（ 我<j ），这对一些人来说一定是有趣的：
condensed_idx = lambda i,j,n: i*n + j - i*(i+1)/2 - i - 1
这很容易理解：
- 用
i*n + j你可以到正方形matrix中的位置; - 与
- i*(i+1)/2你删除在我之前的所有行中的下三angular形（包括对angular线）; - 与
- i在对angular线之前删除线我的位置; - 用
- 1你删除对angular线上我的位置。
检查：
import scipy from scipy.spatial.distance import pdist, squareform condensed_idx = lambda i,j,n: i*n + j - i*(i+1)/2 - i - 1 n = 50 dim = 2 x = scipy.random.uniform(size = n*dim).reshape((n, dim)) d = pdist(x) ds = squareform(d) for i in xrange(1, n-1): for j in xrange(i+1, n): assert ds[i, j] == d[condensed_idx(i, j, n)]
