scipy.spatial.distance.pdist圧縮された距離行列を返します。ドキュメントから：
凝縮された距離行列 Y を返します。それぞれの and (ここで ) について、メトリック dist(u=X[i], v=X[j]) が計算され、エントリ ij に格納されます。
私は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]2.8 ではなく 0 です。
iとが与えられた 2 つのベクトルの類似性にアクセスするために使用する式は何jですか?
このように見ることができます:xが m × n であるとします。m一度に 2 つずつ選択される可能性のある行のペアはitertools.combinations(range(m), 2)、たとえばm=3次のようになります。
>>> import itertools
>>> list(combinations(range(3),2))
[(0, 1), (0, 2), (1, 2)]
したがってd = pdist(x)、 のk番目のタプルは、 に関連付けられcombinations(range(m), 2))た の行のインデックスを提供します。xd[k]
例：
>>> x = array([[0,10],[10,10],[20,20]])
>>> pdist(x)
array([ 10. , 22.36067977, 14.14213562])
最初の要素はdist(x[0], x[1])、2 番目の要素は 、 dist(x[0], x[2])3 番目の要素は ですdist(x[1], x[2])。
または、平方距離行列の上三角部分の要素を 1D 配列にまとめて表示することもできます。
例えば
>>> 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])
pdist によって返される圧縮された距離行列は、以下を使用して完全な距離行列に変換できますscipy.spatial.distance.squareform。
>>> 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完全な行列に変換するために使用します。
>>> 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
正方行列の要素にアクセスするために使用されるインデックスを、圧縮された行列のインデックスに変換できます。
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)
>>> 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
squaureform の作成は非常に遅いことがわかります。
>>> dist_condensed = pdist(points)
>>> %timeit dist = squareform(dist_condensed)
1 loops, best of 3: 2.25 s per loop
最大距離で 2 点を検索する場合、完全な行列での検索が O(n) であるのに対し、圧縮された形式では O(n/2) であることは驚くべきことではありません。
>>> 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
どちらの場合も、2 つのポイントの inideces を取得するのにほとんど時間はかかりませんが、もちろん、圧縮されたインデックスを計算するためのオーバーヘッドがあります。
>>> 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
圧縮された行列のベクトルは、正方行列の下三角領域に対応します。その三角形領域の点に変換するには、三角形の左側の点の数と列の上の点の数を計算する必要があります。
次の関数を使用して変換できます。
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 ) ]
平方距離行列の (i,j) 番目の要素に対応する の要素にアクセスする場合、pdist計算は次のようになります。 i < ji == j
X = random((N,m))
dist_matrix = pdist(X)
次に、(i,j) 番目の要素は dist_matrix[ind] です。
ind = (N - array(range(1,i+1))).sum() + (j - 1 - i).