복붙노트

[PYTHON] N 포인트와 numpy / scipy에서의 참조 간의 효율적인 거리 계산

PYTHON

N 포인트와 numpy / scipy에서의 참조 간의 효율적인 거리 계산

방금 scipy / numpy를 사용하기 시작했습니다. 나는 100000 * 3 배열을 가지고 있으며, 각 행은 좌표이고 1 * 3 중심점입니다. 배열의 각 행의 중심까지의 거리를 계산하여 다른 배열에 저장하려고합니다. 가장 효율적인 방법은 무엇입니까?

해결법

  1. ==============================

    1.scipy.spatial.distance.cdist를 살펴 보겠습니다.

    scipy.spatial.distance.cdist를 살펴 보겠습니다.

    http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.cdist.html

    import numpy as np
    import scipy
    
    a = np.random.normal(size=(10,3))
    b = np.random.normal(size=(1,3))
    
    dist = scipy.spatial.distance.cdist(a,b) # pick the appropriate distance metric 
    

    dist는 기본 거리 메트릭이 다음과 같습니다.

    np.sqrt(np.sum((a-b)**2,axis=1))  
    

    cdist가 큰 배열에 대해 훨씬 더 효율적이긴하지만 (내 시스템에서 크기 문제에 대해 cdist는 ~ 35 배 더 빠름).

  2. ==============================

    2.나는 유클리드 거리의 스켈레톤 구현을 사용할 것이다. 장점은 행렬 곱셈을 사용하여보다 효율적인 표현식을 사용하는 것입니다.

    나는 유클리드 거리의 스켈레톤 구현을 사용할 것이다. 장점은 행렬 곱셈을 사용하여보다 효율적인 표현식을 사용하는 것입니다.

    dist(x, y) = sqrt(dot(x, x) - 2 * dot(x, y) + dot(y, y)
    

    간단한 스크립트는 다음과 같습니다.

    import numpy as np
    
    x = np.random.rand(1000, 3)
    y = np.random.rand(1000, 3)
    
    dist = np.sqrt(np.dot(x, x)) - (dot(x, y) + dot(x, y)) + dot(y, y)
    

    이 접근법의 장점은 sklearn 문서에 잘 설명되어 있습니다. http://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.euclidean_distances.html#sklearn.metrics.pairwise.euclidean_distances

    나는이 접근 방식을 사용하여 np.einsum 함수를 사용하는 것과 같은 사소한 수정으로 대규모 데이터 매트릭스 (10000, 10000)를 처리합니다.

  3. ==============================

    3.당신은 또한 표준의 발전을 사용할 수 있습니다 (주목할만한 정체성과 유사 함). 이것은 아마도 점들의 행렬의 거리를 계산하는 가장 효율적인 방법 일 것입니다.

    당신은 또한 표준의 발전을 사용할 수 있습니다 (주목할만한 정체성과 유사 함). 이것은 아마도 점들의 행렬의 거리를 계산하는 가장 효율적인 방법 일 것입니다.

    다음은 Octave에서 k- Nearest-Neighbor 구현에 원래 사용했던 코드 단편입니다.하지만 numpy.dot ()과 같은 행렬 곱셈 만 사용하므로 numpy에 쉽게 적용 할 수 있습니다.

    % Computing the euclidian distance between each known point (Xapp) and unknown points (Xtest)
    % Note: we use the development of the norm just like a remarkable identity:
    % ||x1 - x2||^2 = ||x1||^2 + ||x2||^2 - 2*<x1,x2>
    [napp, d] = size(Xapp);
    [ntest, d] = size(Xtest);
    
    A = sum(Xapp.^2, 2);
    A = repmat(A, 1, ntest);
    
    B = sum(Xtest.^2, 2);
    B = repmat(B', napp, 1);
    
    C = Xapp*Xtest';
    
    dist = A+B-2.*C;
    
  4. ==============================

    4.관심있는 거리 함수를보다 자세하게 지정해야 할 수도 있지만 내부 제품을 기반으로 한 Squared Euclidean Distance의 구현은 매우 간단하고 효율적입니다. (분명히 일반화되고 직설적 인 방식으로 다른 종류의 거리 측정) :

    관심있는 거리 함수를보다 자세하게 지정해야 할 수도 있지만 내부 제품을 기반으로 한 Squared Euclidean Distance의 구현은 매우 간단하고 효율적입니다. (분명히 일반화되고 직설적 인 방식으로 다른 종류의 거리 측정) :

    In []: P, c= randn(5, 3), randn(1, 3)
    In []: dot(((P- c)** 2), ones(3))
    Out[]: array([  8.80512,   4.61693,   2.6002,   3.3293,  12.41800])
    

    P는 당신의 포인트이고 C는 센터입니다.

  5. ==============================

    5.이 질문에 직접 대답하지 않을 수도 있습니다,하지만 만약 당신이 입자 쌍의 모든 순열 후에, 나는 다음과 같은 해결책을 때로는 pdist 기능보다 빠르다 발견했습니다.

    이 질문에 직접 대답하지 않을 수도 있습니다,하지만 만약 당신이 입자 쌍의 모든 순열 후에, 나는 다음과 같은 해결책을 때로는 pdist 기능보다 빠르다 발견했습니다.

    import numpy as np
    
    L   = 100       # simulation box dimension
    N   = 100       # Number of particles
    dim = 2         # Dimensions
    
    # Generate random positions of particles
    r = (np.random.random(size=(N,dim))-0.5)*L
    
    # uti is a list of two (1-D) numpy arrays  
    # containing the indices of the upper triangular matrix
    uti = np.triu_indices(100,k=1)        # k=1 eliminates diagonal indices
    
    # uti[0] is i, and uti[1] is j from the previous example 
    dr = r[uti[0]] - r[uti[1]]            # computes differences between particle positions
    D = np.sqrt(np.sum(dr*dr, axis=1))    # computes distances; D is a 4950 x 1 np array
    

    내 블로그 게시물에서이 문제에 대한 심층적 인 설명을 보려면이 부분을 참조하십시오.

  6. ==============================

    6.

    #is it true, to find the biggest distance between the points in surface?
    
    from math import sqrt
    
    n = int(input( "enter the range : "))
    x = list(map(float,input("type x coordinates: ").split()))
    y = list(map(float,input("type y coordinates: ").split()))
    maxdis = 0  
    for i in range(n):
        for j in range(n):
            print(i, j, x[i], x[j], y[i], y[j])
            dist = sqrt((x[j]-x[i])**2+(y[j]-y[i])**2)
            if maxdis < dist:
    
                maxdis = dist
    print(" maximum distance is : {:5g}".format(maxdis))
    
  7. from https://stackoverflow.com/questions/6430091/efficient-distance-calculation-between-n-points-and-a-reference-in-numpy-scipy by cc-by-sa and MIT license