Hướng dẫn euclidean distance python math - toán khoảng cách euclide trong python

Ảnh của Bruno trên unsplash

Trong nhiều ứng dụng học máy, chúng ta cần tính toán khoảng cách giữa hai điểm trong không gian Euclide. Ví dụ, trong thuật toán hàng xóm K-Newest (K-NN), chúng ta cần tìm khoảng cách giữa mỗi điểm trong bộ dữ liệu thử nghiệm đến tất cả các điểm trong bộ dữ liệu tàu và chọn các điểm tàu ​​có khoảng cách nhỏ nhất. Trong phân cụm K-MEAN, khoảng cách giữa mỗi lần quan sát và tất cả các trung tâm cụm nên được tính toán trong giai đoạn gán (liên kết). Do đó, một thuật toán tính toán khoảng cách nhanh và hiệu quả là rất cần thiết.

Khoảng cách trong không gian Euclide

Khoảng cách giữa hai điểm trong không gian Euclide có thể được tính toán bằng cách sử dụng hoạt động P-Norm. Đặt x = (x1, x2, xông, xn) và y = (y1, y2, triệt, yn) là hai điểm trong không gian Euclide. Dưới đây là các chức năng khoảng cách được sử dụng phổ biến nhất:x =(x1, x2, …,xn) and y=(y1, y2, …,yn) be two points in Euclidean space. Below are the most commonly used distance functions:

1. Khoảng cách 1 bình thường (khoảng cách Manhattan):

2. Khoảng cách 2 bình thường (khoảng cách Euclide):

3. Khoảng cách-bình thường (khoảng cách Chebyshev):

Về cơ bản, bạn có thể tính toán khoảng cách bằng bất kỳ p-Norm (p> 1) nào như:

Ở đây, chúng tôi chỉ tập trung vào khoảng cách 2 bình thường vì nó là cái phổ biến nhất, nhưng việc khái quát hóa các chỉ tiêu khác có thể dễ dàng thực hiện.

Thực hiện Python

Mục tiêu là tìm tất cả các khoảng cách theo cặp giữa hai bộ điểm trong Rⁿ trong Python nhanh và hiệu quả nhất có thể. Đặt X và Y lần lượt là hai ma trận với kích thước M × N và K × N. Chúng tôi muốn tính toán ma trận khoảng cách D với kích thước của m × k trong đó phần tử (i, j) của d là khoảng cách giữa điểm ith trong x và điểm thứ j trong Y. Để bắt đầu, hãy tạo ra ma trận của chúng tôi một cách ngẫu nhiên bằng cách sử dụng Thư viện Numpy:X and Y be two matrices with sizes of m × n and k × n, respectively. We would like to calculate the distance matrix D with size of m × k where (i,j)th element of D is the distance between the ith point in X and the jth point in Y. To start, let’s generate our matrices randomly using NumPy library:

Bây giờ, chúng ta cần tạo chức năng khoảng cách của mình để tính toán tất cả các khoảng cách theo cặp giữa tất cả các điểm trong X và Y. Cách dễ nhất để làm điều này là tạo hai vòng lặp; Một vòng lặp đi qua mỗi hàng x, một vòng đi qua mỗi hàng y và tính khoảng cách của chúng bằng phương trình khoảng cách Euclide được mô tả ở trên:X and Y. The easiest way to do this is to create two for-loops; one loop going over each row of X, one loop going over each row of Y and calculate their distance using Euclidean distance equation described above:

Lưu ý rằng trên dòng 5 của mã trên, trước tiên chúng ta cần khởi tạo ma trận khoảng cách của mình và sau đó bắt đầu điền nó với các giá trị khoảng cách bằng hai vòng lặp. Chức năng này rõ ràng và dễ hiểu. Tuy nhiên, vấn đề chính là sử dụng các vòng lặp rất tốn kém trong các ngôn ngữ được giải thích như Python. Khi kích thước ma trận tăng lên, độ phức tạp và thời gian chạy của mã này tăng theo cấp số nhân khiến nó không thực tế. Để tránh các vòng lặp trong Python, chúng ta có thể có những lợi thế của việc xử lý vector trong Numpy:

Trong mã trên, chúng tôi đã loại bỏ khởi tạo ma trận khoảng cách và hai vòng lặp đắt tiền. Việc trừ giữa tất cả các điểm dữ liệu trong X và Y được thực hiện bằng cách sử dụng hoạt động ma trận phát sóng và phần tử khôn ngoan. Sau này chúng tôi sẽ hiển thị phiên bản vectorized đang chạy nhanh hơn ít nhất 100 lần so với phiên bản for-loop. Nhược điểm duy nhất là phiên bản vector hóa không dễ hiểu như phiên bản for-loop. May mắn thay, cũng có một cách để tối ưu hóa phiên bản for-loop:D initialization and two expensive for-loops. The subtraction between all data points in X and Y is done using broadcasting and element-wise matrix operation. We will later show the vectorized version is running at least 100x faster than the for-loop version. The only downside is that the vectorized version is not as easy to understand as the for-loop version. Fortunately, there is also a way to optimize the for-loop version:

Bí quyết là sử dụng thư viện numba. Numba là trình biên dịch chỉ trong thời gian (JIT) cho Python tối ưu hóa các mảng và chức năng và các vòng lặp. Tất cả những gì bạn cần làm là sử dụng JIT Decorator trước chức năng Numpy của bạn. Công việc trang trí là cơ bản biên dịch chức năng được trang trí sao cho nó chạy mà không có sự tham gia của trình thông dịch Python, dẫn đến hiệu suất cao hơn nhiều. Sau đó, trong bài kiểm tra điểm chuẩn của chúng tôi, chúng tôi sẽ chỉ ra rằng phiên bản for-loop của Numba nhanh như phiên bản vector hóa numpy.Numba library. Numba is a just-in-time (JIT) compiler for Python that optimizes NumPy arrays and functions, and loops. All you need to do is to use jit decorator before your NumPy function. The decorator job is to basically compile the decorated function such that it runs without the Python interpreter involvement, leading to much higher performance. Later, in our benchmark test, we will show that the Numba for-loop version is as fast as NumPy vectorized version.

Chúng ta vẫn có thể làm tốt hơn phiên bản vector hóa numpy? Đúng. Thật thú vị, thư viện Scipy có chức năng khoảng cách có thể làm tốt hơn:SciPy library has a distance function which can do better:SciPy library has a distance function which can do better:

Bạn có thể thấy chức năng khoảng cách của chúng tôi ngày càng nhỏ hơn và thực sự hiệu quả hơn. Sau đó, chúng tôi sẽ chỉ ra rằng chức năng CDIST trong SCIPY nhanh hơn nhiều so với phiên bản vector hóa numpy của chúng tôi. CDIST sử dụng hàm ngôn ngữ C (ngôn ngữ biên dịch) với trình bao bọc Python. Do đó, khi bạn gọi CDIST trong Python, một hàm C thực sự được gọi là cực kỳ nhanh.

Do sự xuất hiện của các ứng dụng học tập sâu và tiến bộ trong công nghệ phần cứng, việc xử lý GPU đã trở nên phổ biến hơn. GPU hoạt động ở tần số thấp hơn CPU. Tuy nhiên, GPU có nhiều lõi hơn đáng kể cho phép chúng xử lý dữ liệu với tốc độ nhanh hơn nhiều (bằng cách khai thác xử lý song song). Ví dụ, CPU Intel i7 Tiết1160G7 chỉ có 4 lõi trong khi Nvidia Tesla V100 có 640 lõi. Tin tốt là Thư viện Cupy cho phép chúng tôi sử dụng điện toán tăng tốc GPU trong Python. Cupy được viết dựa trên Numpy và chúng có cú pháp tương tự:GPU processing has become more popular. GPUs operate at lower frequencies than CPUs. However, GPUs have significantly more cores which allow them to process data at much faster rate (by exploiting parallel processing). For example, Intel i7–1160G7 CPU has only 4 cores while Nvidia Tesla V100 has 640 cores. The good news is CuPy library allows us to use GPU accelerated computing in Python. CuPy is written based on NumPy and they have similar syntax:GPU processing has become more popular. GPUs operate at lower frequencies than CPUs. However, GPUs have significantly more cores which allow them to process data at much faster rate (by exploiting parallel processing). For example, Intel i7–1160G7 CPU has only 4 cores while Nvidia Tesla V100 has 640 cores. The good news is CuPy library allows us to use GPU accelerated computing in Python. CuPy is written based on NumPy and they have similar syntax:

Bạn có thể thấy chức năng này rất giống với hàm numpy_vectorized của chúng tôi và chúng tôi chỉ thay thế các hàm numpy bằng các chức năng tương ứng. Chúng tôi cũng cần thay đổi loại dữ liệu từ Numpy sang Cupy và ngược lại. Nhược điểm duy nhất của việc sử dụng Cupy là chi phí chuyển dữ liệu giữa CPU và GPU.

Điểm chuẩn hiệu suất

Chúng tôi đã giới thiệu 5 phương pháp khác nhau để tính khoảng cách theo cặp. Các câu hỏi là ai là người chiến thắng! Chúng tôi có một tập lệnh chạy các phương thức này cho các kích thước mảng khác nhau và so sánh thời gian chạy của chúng. Bạn có thể tải xuống tập lệnh tại đây.

Thời gian chạy của các phương thức khác nhau so với kích thước ma trận [hình ảnh của tác giả]

Hình trên cho thấy thời gian chạy tính bằng giây cho các phương thức và kích thước ma trận khác nhau. Lưu ý rằng trục y ở quy mô log để hiển thị sự khác biệt giữa các phương thức tốt hơn. Dưới đây là một bản tóm tắt các quan sát:

1. Chức năng Numpy For-Loop có thời gian chạy tồi tệ hơn.
2. Phiên bản Vectorized Numpy có thể cải thiện đáng kể thời gian chạy và chạy nhanh hơn 100 lần so với phiên bản for-loop.
3. Bằng cách sử dụng numba (tức là, JIT), bạn có thể đạt được thời gian chạy gần như giống như phiên bản vector hóa numpy. Do đó, Numba rất có lợi nếu bạn vẫn thích sử dụng các vòng lặp đơn giản.
4. Scipy CDIST là người chiến thắng rõ ràng trong số các phương pháp này cho tất cả các kích thước ma trận do giao diện sạch/dễ dàng và xương sống ngôn ngữ C.
5. Cupy sử dụng GPU nhanh như SCIPY trên các kích thước ma trận lớn. Đối với các kích thước ma trận nhỏ (ví dụ: 10), Cupy không có lợi do chi phí truyền dữ liệu giữa các thiết bị (CPU và GPU).