<h2>压缩距离矩阵到全距离矩阵</h2>
<p>pdist返回的压缩距离矩阵可以通过使用<code>scipy.spatial.distance.squareform</code>转换为全距离矩阵:</p>
<pre><code>>>> 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. ])
</code></pre>
<p>使用<code>squareform</code>转换为完整矩阵:</p>
<pre><code>>>> 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. ]])
</code></pre>
<p>点i,j之间的距离存储在dist[i,j]中:</p>
<pre><code>>>> dist[2, 0]
5.0
>>> np.linalg.norm(points[2] - points[0])
5.0
</code></pre>
<h2>指数到凝聚指数</h2>
<p>可以将用于访问平方矩阵元素的索引转换为压缩矩阵中的索引:</p>
<pre><code>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
</code></pre>
<p>示例:</p>
<pre><code>>>> square_to_condensed(1, 2, len(points))
3
>>> dist_condensed[3]
4.4721359549995796
>>> dist[1,2]
4.4721359549995796
</code></pre>
<h2>索引的压缩索引</h2>
<p>另外,如果没有sqaureform(在运行时和内存消耗方面更好),另一个方向也是可能的:</p>
<pre><code>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
</code></pre>
<p>示例:</p>
<pre><code>>>> condensed_to_square(3, 4)
(1.0, 2.0)
</code></pre>
<h2>运行时与squareform的比较</h2>
<pre><code>>>> 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
</code></pre>
<p>创建sqaureform的过程非常缓慢:</p>
<pre><code>>>> dist_condensed = pdist(points)
>>> %timeit dist = squareform(dist_condensed)
1 loops, best of 3: 2.25 s per loop
</code></pre>
<p>如果我们用最大距离搜索两点,在全矩阵中搜索是O(n),而在压缩形式中搜索只有O(n/2),这并不奇怪:</p>
<pre><code>>>> 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
</code></pre>
<p>在这两种情况下,获取两点的最小值几乎不需要时间,但计算压缩索引当然会有一些开销:</p>
<pre><code>>>> 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
</code></pre>