Hướng dẫn calculate euclidean distance matrix python - tính toán python ma trận khoảng cách euclid

Ma trận khoảng cách là một cấu trúc dữ liệu thực sự hữu ích lưu trữ thông tin theo cặp về cách các vectơ từ bộ dữ liệu liên quan đến nhau. Trong học máy, chúng được sử dụng cho các nhiệm vụ như phân cụm phân cấp của cây phát sinh (nhìn vào tổ tiên di truyền) và trong các mô hình xử lý ngôn ngữ tự nhiên (NLP) để khám phá mối quan hệ giữa các từ (với các từ nhúng như Word2VEC, găng tay, fasttext, v.v.). Ở đây, chúng tôi sẽ ngắn gọn về cách thực hiện một chức năng trong Python có thể được sử dụng để tính toán hiệu quả các khoảng cách cặp cho một bộ/hoặc bộ vectơ.

• Nếu bạn quan tâm đến việc theo dõi, hãy kích hoạt ipython trong một phiên cuối cùng (hoặc tạo một máy tính xách tay Jupyter mới). Ngoài ra, hãy chắc chắn rằng bạn đã cài đặt gói Numpy.

Đánh giá ngắn gọn về khoảng cách Euclide

Hãy nhớ lại rằng khoảng cách Euclide bình phương giữa hai vectơ A và B bất kỳ chỉ đơn giản là tổng của sự khác biệt về thành phần vuông. (Chúng tôi đang bỏ qua bước cuối cùng, lấy căn bậc hai, chỉ để làm cho các ví dụ dễ dàng)a and b is simply the sum of the square component-wise differences. (we are skipping the last step, taking the square root, just to make the examples easy)

Chúng ta có thể thực hiện tính toán này một cách ngây thơ với Vanilla Python như thế này:

a = [i + 1 for i in range(0, 500)]
b = [i for i in range(0, 500)]
dist_squared = sum([(a_i - b_i)**2 for a_i, b_i in zip(a, b)])
dist_squared
500

Trên thực tế, chúng tôi có thể thực hiện tất cả các toán học mà chúng tôi sẽ làm việc theo cách này, nhưng nó sẽ chậm và tẻ nhạt. Numpy, thư viện số dứt khoát cho Python, cung cấp cho chúng tôi việc triển khai nhanh chóng cho mọi thứ chúng tôi cần ở đây. Để minh họa lợi thế tốc độ, hãy để sử dụng cùng một vectơ như các mảng numpy, thực hiện tính toán giống hệt nhau và sau đó thực hiện so sánh tốc độ với %timeit

import numpy as np
a_numpy = np.array(a)
b_numpy = np.array(b)
dist_squared = np.sum(np.square(a_numpy - b_numpy))
dist_squared
500

# using pure python
%timeit dist_squared = sum([(a_i - b_i)**2 for a_i, b_i in zip(a, b)])
119 µs ± 1.02 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

# using numpy
%timeit dist_squared = np.sum(np.square(a_numpy - b_numpy))
6.32 µs ± 2.11 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Như bạn có thể thấy, phiên bản Numpy nhanh hơn 20 lần so với triển khai ban đầu của chúng tôi!

Có một công thức tương đương của khoảng cách Euclide bình phương cho các vectơ sử dụng & nbsp; Dot Products:

Giữ điều này trong tâm trí của bạn vì chúng tôi sẽ mở rộng công thức vector này đến ma trận trong triển khai ma trận khoảng cách cuối cùng của chúng tôi.

Ma trận khoảng cách

Giả sử rằng chúng ta có một nhóm ba quan sát trong đó mỗi quan sát là một vector có ba thành phần. Chúng ta có thể viết tập hợp các quan sát này dưới dạng ma trận 3 x 3 A trong đó mỗi hàng đại diện cho một quan sát.A where each row represents one observation.

Ma trận khoảng cách cho A, mà chúng ta sẽ gọi D, cũng là ma trận 3 x 3 trong đó mỗi phần tử trong ma trận biểu thị kết quả của việc tính toán khoảng cách cho hai trong số các hàng (vectơ) trong A. Lưu ý rằng D là đối xứng và có Tất cả các số không trên đường chéo của nó. (Khoảng cách giữa một vectơ và chính nó bằng không)A, which we will call D, is also a 3 x 3 matrix where each element in the matrix represents the result of a distance calculation for two of the rows (vectors) in A. Note that D is symmetrical and has all zeros on its diagonal. (The distance between a vector and itself is zero)

Điều gì sẽ xảy ra nếu tôi có hai nhóm quan sát mà tôi muốn so sánh khoảng cách cho? Chúng ta cũng có thể nhận được một ma trận khoảng cách trong trường hợp này. Hãy giữ ma trận A đầu tiên của chúng tôi và so sánh nó với ma trận 2 x 3 mới B. Ở đây, ma trận khoảng cách mới & nbsp; , kích thước của ma trận mới là M X N.A and compare it with a new 2 x 3 matrix B. Here, our new distance matrix D is 3 x 2. In general, for any distance matrix between two matrices of size M x K and N x K, the size of the new matrix is M x N.

Với hầu hết các nền được bảo hiểm, hãy để cho biết vấn đề mà chúng tôi muốn giải quyết rõ ràng. Chúng tôi muốn tạo một số chức năng trong Python sẽ lấy hai ma trận làm đối số và trả lại ma trận khoảng cách. Trong các ví dụ của chúng tôi, chúng tôi đã xem xét khoảng cách bình phương, vì vậy chúng tôi cũng sẽ thêm khả năng trả lại khoảng cách bình phương nếu muốn.

Cài đặt

Đầu tiên, hãy để Lôi tạo các ma trận mẫu A và B từ phía trên để sử dụng làm dữ liệu thử nghiệm.A and B from above to use as test data.

A = np.array([[1,2,3],[2,3,4],[0,1,2]])
A
array([[1, 2, 3],
       [2, 3, 4],
       [0, 1, 2]])      
B = np.array([[1,2,3],[4,3,2]])
B
array([[1, 2, 3],
       [4, 3, 2]])

Thực hiện

Bây giờ, hãy để xem lại công thức khoảng cách thay thế từ trên cao và xem xét cách nó có thể được áp dụng hai ma trận A và B. của chúng tôiA and B.

Ma trận khoảng cách ở bên trái, mục tiêu của chúng tôi, có thể được xây dựng từ ba ma trận theo công thức trên. Hãy dành một chút thời gian để đảm bảo bạn nhìn thấy mô hình. Bây giờ, hãy để Lôi xây dựng ma trận đầu tiên của các sản phẩm DOT cho A.A.

M = A.shape[0]
N = B.shape[0]

A_dots = (A*A).sum(axis=1).reshape((M,1))*np.ones(shape=(1,N))
array([[14., 14.],
       [29., 29.],
       [ 5.,  5.]])

Trước tiên, chúng tôi tìm thấy số lượng hàng

import numpy as np
a_numpy = np.array(a)
b_numpy = np.array(b)
dist_squared = np.sum(np.square(a_numpy - b_numpy))
dist_squared
500

# using pure python
%timeit dist_squared = sum([(a_i - b_i)**2 for a_i, b_i in zip(a, b)])
119 µs ± 1.02 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

# using numpy
%timeit dist_squared = np.sum(np.square(a_numpy - b_numpy))
6.32 µs ± 2.11 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

import numpy as np
a_numpy = np.array(a)
b_numpy = np.array(b)
dist_squared = np.sum(np.square(a_numpy - b_numpy))
dist_squared
500

# using pure python
%timeit dist_squared = sum([(a_i - b_i)**2 for a_i, b_i in zip(a, b)])
119 µs ± 1.02 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

# using numpy
%timeit dist_squared = np.sum(np.square(a_numpy - b_numpy))
6.32 µs ± 2.11 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

import numpy as np
a_numpy = np.array(a)
b_numpy = np.array(b)
dist_squared = np.sum(np.square(a_numpy - b_numpy))
dist_squared
500

# using pure python
%timeit dist_squared = sum([(a_i - b_i)**2 for a_i, b_i in zip(a, b)])
119 µs ± 1.02 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

# using numpy
%timeit dist_squared = np.sum(np.square(a_numpy - b_numpy))
6.32 µs ± 2.11 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

import numpy as np
a_numpy = np.array(a)
b_numpy = np.array(b)
dist_squared = np.sum(np.square(a_numpy - b_numpy))
dist_squared
500

# using pure python
%timeit dist_squared = sum([(a_i - b_i)**2 for a_i, b_i in zip(a, b)])
119 µs ± 1.02 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

# using numpy
%timeit dist_squared = np.sum(np.square(a_numpy - b_numpy))
6.32 µs ± 2.11 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

import numpy as np
a_numpy = np.array(a)
b_numpy = np.array(b)
dist_squared = np.sum(np.square(a_numpy - b_numpy))
dist_squared
500

# using pure python
%timeit dist_squared = sum([(a_i - b_i)**2 for a_i, b_i in zip(a, b)])
119 µs ± 1.02 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

# using numpy
%timeit dist_squared = np.sum(np.square(a_numpy - b_numpy))
6.32 µs ± 2.11 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

import numpy as np
a_numpy = np.array(a)
b_numpy = np.array(b)
dist_squared = np.sum(np.square(a_numpy - b_numpy))
dist_squared
500

# using pure python
%timeit dist_squared = sum([(a_i - b_i)**2 for a_i, b_i in zip(a, b)])
119 µs ± 1.02 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

# using numpy
%timeit dist_squared = np.sum(np.square(a_numpy - b_numpy))
6.32 µs ± 2.11 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

import numpy as np
a_numpy = np.array(a)
b_numpy = np.array(b)
dist_squared = np.sum(np.square(a_numpy - b_numpy))
dist_squared
500

# using pure python
%timeit dist_squared = sum([(a_i - b_i)**2 for a_i, b_i in zip(a, b)])
119 µs ± 1.02 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

# using numpy
%timeit dist_squared = np.sum(np.square(a_numpy - b_numpy))
6.32 µs ± 2.11 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

import numpy as np
a_numpy = np.array(a)
b_numpy = np.array(b)
dist_squared = np.sum(np.square(a_numpy - b_numpy))
dist_squared
500

# using pure python
%timeit dist_squared = sum([(a_i - b_i)**2 for a_i, b_i in zip(a, b)])
119 µs ± 1.02 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

# using numpy
%timeit dist_squared = np.sum(np.square(a_numpy - b_numpy))
6.32 µs ± 2.11 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

import numpy as np
a_numpy = np.array(a)
b_numpy = np.array(b)
dist_squared = np.sum(np.square(a_numpy - b_numpy))
dist_squared
500

# using pure python
%timeit dist_squared = sum([(a_i - b_i)**2 for a_i, b_i in zip(a, b)])
119 µs ± 1.02 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

# using numpy
%timeit dist_squared = np.sum(np.square(a_numpy - b_numpy))
6.32 µs ± 2.11 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

import numpy as np
a_numpy = np.array(a)
b_numpy = np.array(b)
dist_squared = np.sum(np.square(a_numpy - b_numpy))
dist_squared
500

# using pure python
%timeit dist_squared = sum([(a_i - b_i)**2 for a_i, b_i in zip(a, b)])
119 µs ± 1.02 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

# using numpy
%timeit dist_squared = np.sum(np.square(a_numpy - b_numpy))
6.32 µs ± 2.11 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

B_dots = (B*B).sum(axis=1)*np.ones(shape=(M,1))
B_dots
array([[14., 29.],
       [14., 29.],
       [14., 29.]])

Điều duy nhất cần lưu ý ở đây là trong ma trận B cuối cùng của chúng tôi được thể hiện trên các cột, vì vậy các sản phẩm DOT của chúng tôi cũng được sắp xếp colunnwise. Ma trận cuối cùng của các sản phẩm DOT được xây dựng với:B is represented on the columns, so our dot products are also arranged colunnwise. The last matrix of dot products is constructed with:

-2*A.dot(B.T)
array([[-28, -32],
       [-40, -50],
       [-16, -14]])

D_squared =  A_dots + B_dots -2*A.dot(B.T)
D_squared
array([[ 0., 11.],
       [ 3.,  8.],
       [ 3., 20.]])

Chức năng cuối cùng

Và đây là mã được gói thành một chức năng với chuỗi Doc phong cách Numpy đẹp.

def distance_matrix(A, B, squared=False):
    """
    Compute all pairwise distances between vectors in A and B.

    Parameters
    ----------
    A : np.array
        shape should be (M, K)
    B : np.array
        shape should be (N, K)

    Returns
    -------
    D : np.array
        A matrix D of shape (M, N).  Each entry in D i,j represnets the
        distance between row i in A and row j in B.

    See also
    --------
    A more generalized version of the distance matrix is available from
    scipy (https://www.scipy.org) using scipy.spatial.distance_matrix,
    which also gives a choice for p-norm.
    """
    M = A.shape[0]
    N = B.shape[0]

    assert A.shape[1] == B.shape[1], f"The number of components for vectors in A \
        {A.shape[1]} does not match that of B {B.shape[1]}!"

    A_dots = (A*A).sum(axis=1).reshape((M,1))*np.ones(shape=(1,N))
    B_dots = (B*B).sum(axis=1)*np.ones(shape=(M,1))
    D_squared =  A_dots + B_dots -2*A.dot(B.T)

    if squared == False:
        zero_mask = np.less(D_squared, 0.0)
        D_squared[zero_mask] = 0.0
        return np.sqrt(D_squared)

    return D_squared

Sự kết luận

Và bạn có nó rồi đấy! Một chức năng hiệu quả để tính toán ma trận khoảng cách trong Python bằng cách sử dụng Numpy. Trước khi tôi rời bỏ bạn, tôi nên lưu ý rằng SCIPY có chức năng tích hợp (

import numpy as np
a_numpy = np.array(a)
b_numpy = np.array(b)
dist_squared = np.sum(np.square(a_numpy - b_numpy))
dist_squared
500

# using pure python
%timeit dist_squared = sum([(a_i - b_i)**2 for a_i, b_i in zip(a, b)])
119 µs ± 1.02 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

# using numpy
%timeit dist_squared = np.sum(np.square(a_numpy - b_numpy))
6.32 µs ± 2.11 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

distance_matrix(A, B)
array([[0.        , 3.31662479],
       [1.73205081, 2.82842712],
       [1.73205081, 4.47213595]])

import scipy
scipy.spatial.distance_matrix(A, B)
array([[0.        , 3.31662479],
       [1.73205081, 2.82842712],
       [1.73205081, 4.47213595]])