쌍으로 된 거리의 응축 된 형태를 직접 얻는 방법은 무엇입니까?

Question

나는 매우 큰 scipy 스파 스 csr 매트릭스를 가지고 있습니다. 그것은 100,000x2,000,000 차원 매트릭스입니다. X이라고합시다. 각 행은 2,000,000 차원 공간의 샘플 벡터입니다.

각 샘플 쌍 간의 코사인 거리를 매우 효율적으로 계산해야합니다. 나는 X에있는 벡터의 서브셋과 함께 sklearn pairwise_distances 함수를 사용하여 조밀 한 행렬 D를 얻었습니다. 중복 된 엔트리를 포함하는 pairwise distance의 사각형 형태입니다. sklearn pairwise_distances을 사용하면 응축 된 폼을 직접 얻을 수 있습니까? 응축 된 형태가 무엇인지 보려면 http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.pdist.html을 참조하십시오. scipy pdist의 출력입니다.

메모리 제한이 있기 때문에 사각형 형식을 계산할 수없고 응축 된 양식을 얻을 수 없습니다. 메모리 제한으로 인해 다시 메모리에 맞지 않는 밀도 매트릭스 X이 필요하므로 scipy pdist을 사용할 수 없습니다. X의 다른 덩어리를 반복하면서 각 덩어리에 대해 응축 된 형태를 계산하고 함께 결합하여 응축 된 전체 형태를 얻는 방법에 대해 생각했습니다. 그러나 이것은 상대적으로 성가신 일입니다. 더 좋은 아이디어?

도움을 주시면 감사하겠습니다. 미리 감사드립니다.

다음은 (X 훨씬 작은 데모 용 물론) 재현 예입니다

from scipy.sparse import rand 
from scipy.spatial.distance import pdist 
from sklearn.metrics.pairwise import pairwise_distances 
X = rand(1000, 10000, density=0.01, format='csr') 
dist1 = pairwise_distances(X, metric='cosine') 
dist2 = pdist(X.A, 'cosine') 

당신이 dist2이 응축 된 형태이며, 499,500 차원 벡터이다시피

. 그러나 dist1은 대칭 사각형 형태이며 1000x1000 매트릭스입니다.

Answer 1

두 버전의 코드를 모두 파헤쳐서 두 기능이 모두 무엇을하는지 이해하고 있다고 생각합니다. 작은 간단한 X (밀도)와

시작 :

X = np.arange(9.).reshape(3,3) 

pdist 코사인을 수행합니다 _row_norms은 행 점이다

norms = _row_norms(X) 
_distance_wrap.pdist_cosine_wrap(_convert_to_double(X), dm, norms) 

-einsum를 사용하여 : 그래서

norms = np.sqrt(np.einsum('ij,ij->i', X,X) 

가 이 첫 번째 장소는입니다.은 배열이어야합니다. 생산

(아마 사이 썬에서) 나는 cosine_wrap 파고하지 않은,하지만 그것을 할 것으로 보인다

xy = np.dot(X, X.T) 
# or xy = np.einsum('ij,kj',X,X) 

d = np.zeros((3,3),float) # square receiver 
d2 = []      # condensed receiver 
for i in range(3): 
    for j in range(i+1,3): 
     val=1-xy[i,j]/(norms[i]*norms[j]) 
     d2.append(val) 
     d[j,i]=d[i,j]=val 

print('array') 
print(d) 
print('condensed',np.array(d2)) 

from scipy.spatial import distance 
d1=distance.pdist(X,'cosine') 
print(' pdist',d1) 

:

array 
[[ 0.   0.11456226 0.1573452 ] 
[ 0.11456226 0.   0.00363075] 
[ 0.1573452 0.00363075 0.  ]] 

condensed [ 0.11456226 0.1573452 0.00363075] 
    pdist [ 0.11456226 0.1573452 0.00363075] 

distance.squareform(d1) 내 d 배열로 같은 일을 생성합니다.

I는 해당 norm 외적으로 xy 내적 나누어 동일한 정방형 어레이를 생성 할 수

dd=1-xy/(norms[:,None]*norms) 
dd[range(dd.shape[0]),range(dd.shape[1])]=0 # clean up 0s 

또는 내적을 찍기 전에 X를 정규화한다.이것은 scikit 버전이하는 것처럼 보입니다.

Xnorm = X/norms[:,None] 
1-np.einsum('ij,kj',Xnorm,Xnorm) 

scikit 빨리 스파 스 계산을 할 몇 가지 사이 썬 코드 추가 (sparse.sparse에서 제공하는 이상을,하지만 같은 csr 형식 사용)했습니다

from scipy import sparse 
Xc=sparse.csr_matrix(X) 

# csr_row_norm - pyx of following 
cnorm = Xc.multiply(Xc).sum(axis=1) 
cnorm = np.sqrt(cnorm) 
X1 = Xc.multiply(1/cnorm) # dense matrix 
dd = 1-X1*X1.T 

스파 스 매트릭스와 빠른 압축 된 양식을 얻으려면을 I X1*X1.T의 빠른 압축 버전을 구현해야한다고 생각합니다. 즉, 희소 행렬 곱셈이 구현되는 방식을 이해해야합니다 (c 코드). scikit cython '빠른 스파 스'코드도 아이디어를 줄 수 있습니다.

numpy에는 직설적 인 파이썬 코드 인 일부 tri... 기능이 있습니다. 트라이 계산을 직접 구현하여 시간이나 공간을 절약하려고하지 않습니다. 삼각형 배열의보다 복잡한 가변 길이 단계를 수행하는 것보다 모양과 스트라이드가있는 nd 배열의 사각형 레이아웃을 반복하는 것이 더 쉽습니다. 응축 된 형태 만 공간과 계산 단계를 절반으로 줄입니다.

============는

여기 i 상부 j, 반복 처리가 dot(x[i],y[j])/(norm[i]*norm[j]) 산출 cpdist_cosine 기능의 주요 부분이다.

for (i = 0; i < m; i++) { 
    for (j = i + 1; j < m; j++, dm++) { 
     u = X + (n * i); 
     v = X + (n * j); 
     cosine = dot_product(u, v, n)/(norms[i] * norms[j]); 
     if (fabs(cosine) > 1.) { 
      /* Clip to correct rounding error. */ 
      cosine = npy_copysign(1, cosine); 
     } 
     *dm = 1. - cosine; 
    } 
} 

https://github.com/scipy/scipy/blob/master/scipy/spatial/src/distance_impl.h

당신은 구체적인 예를 추가해야합니다