Khoảng cách euclid C++

Nhiều thuật toán, cho dù được giám sát hay không được giám sát, đều sử dụng các thước đo khoảng cách . Những thước đo này, chẳng hạn như khoảng cách euclid hoặc độ tương tự cosin, thường có thể được tìm thấy trong các thuật toán như k-NN, UMAP, HDBSCAN, v.v.

Hiểu biết về lĩnh vực đo khoảng cách quan trọng hơn bạn có thể nhận ra. Lấy k-NN làm ví dụ, một kỹ thuật thường được sử dụng để học có giám sát. Theo mặc định, nó thường sử dụng khoảng cách euclide. Tự nó, một thước đo khoảng cách tuyệt vời.

Tuy nhiên, nếu dữ liệu của bạn có nhiều chiều thì sao? Khoảng cách euclide sau đó có còn hoạt động không? Hoặc nếu dữ liệu của bạn chứa thông tin không gian địa lý thì sao? Có lẽ khoảng cách hasrsine sau đó sẽ là một lựa chọn thay thế tốt hơn!

Biết khi nào nên sử dụng thước đo khoảng cách nào có thể giúp bạn đi từ máy phân loại kém sang mô hình chính xác.

Trong bài viết này, chúng ta sẽ xem xét nhiều thước đo khoảng cách và khám phá cách thức và thời điểm chúng có thể được sử dụng tốt nhất. Quan trọng nhất, tôi sẽ nói về những nhược điểm của chúng để bạn có thể nhận ra khi nào nên tránh xa các biện pháp nhất định.

LƯU Ý : Đối với hầu hết các phép đo khoảng cách, các giấy tờ phức tạp dài có thể được viết về các trường hợp sử dụng, ưu điểm và nhược điểm của chúng. Tôi sẽ cố gắng trang trải nhiều nhất có thể nhưng có thể bị hụt hẫng! Vì vậy, hãy coi bài viết này là một tổng quan toàn cầu về các biện pháp này.

1. Khoảng cách Euclide

Chúng tôi bắt đầu với thước đo khoảng cách phổ biến nhất, đó là khoảng cách Euclide. Đó là một thước đo khoảng cách tốt nhất có thể được giải thích là độ dài của một đoạn nối hai điểm.

Công thức khá đơn giản vì khoảng cách được tính từ tọa độ Cartesian của các điểm bằng cách sử dụng định lý Pitago.

Nhược điểm

Mặc dù nó là một thước đo khoảng cách phổ biến, khoảng cách Euclide không phải là biến thể theo tỷ lệ, có nghĩa là khoảng cách được tính toán có thể bị sai lệch tùy thuộc vào đơn vị của các đối tượng địa lý. Thông thường, người ta cần chuẩn hóa dữ liệu trước khi sử dụng thước đo khoảng cách này.

Hơn nữa, khi kích thước dữ liệu của bạn tăng lên, khoảng cách Euclide càng trở nên ít hữu ích hơn. Điều này có liên quan đến lời nguyền về chiều liên quan đến khái niệm rằng không gian chiều cao hơn không hoạt động như chúng ta, theo trực giác, mong đợi từ không gian 2 hoặc 3 chiều. Để có một bản tóm tắt tốt, hãy xem bài đăng này .

Trường hợp sử dụng

Khoảng cách Euclid hoạt động hiệu quả khi bạn có dữ liệu chiều thấp và độ lớn của vectơ là điều quan trọng cần được đo. Các phương pháp như kNN và HDBSCAN cho kết quả tuyệt vời nếu sử dụng khoảng cách Euclid trên dữ liệu chiều thấp.

Mặc dù nhiều biện pháp khác đã được phát triển để giải quyết những nhược điểm của khoảng cách Euclide, nó vẫn là một trong những thước đo khoảng cách được sử dụng nhiều nhất vì những lý do chính đáng. Nó cực kỳ trực quan để sử dụng, đơn giản để thực hiện và cho thấy kết quả tuyệt vời trong nhiều trường hợp sử dụng.

2. Tương tự Cosine

Tương tự cosine thường được sử dụng như một cách để chống lại vấn đề khoảng cách Euclide với chiều cao. Tính tương tự cosin đơn giản là cosin của góc giữa hai vectơ. Nó cũng có cùng tích bên trong của các vectơ nếu chúng được chuẩn hóa để cả hai đều có độ dài bằng một.

Hai vectơ cùng hướng chính xác có độ tương đồng cosin là 1, trong khi hai vectơ đối đường kính với nhau có độ giống nhau là -1. Lưu ý rằng độ lớn của chúng không quan trọng vì đây là thước đo định hướng.

Nhược điểm

Một nhược điểm chính của sự tương tự cosine là độ lớn của các vectơ không được tính đến, chỉ đơn thuần là hướng của chúng. Trong thực tế, điều này có nghĩa là sự khác biệt về giá trị không được tính đến đầy đủ. Ví dụ: nếu bạn lấy một hệ thống giới thiệu, thì sự tương đồng về cosin không tính đến sự khác biệt trong thang đánh giá giữa những người dùng khác nhau.

Trường hợp sử dụng

Chúng tôi sử dụng tính tương tự cosine thường xuyên khi chúng tôi có dữ liệu chiều cao và khi độ lớn của các vectơ không quan trọng. Đối với phân tích văn bản, biện pháp này được sử dụng khá thường xuyên khi dữ liệu được biểu diễn bằng số lượng từ. Ví dụ: khi một từ xuất hiện thường xuyên hơn trong tài liệu này so với tài liệu khác, điều này không nhất thiết có nghĩa là một tài liệu có liên quan nhiều hơn đến từ đó. Có thể là trường hợp tài liệu có độ dài không đồng đều và độ lớn của số lượng ít quan trọng hơn. Sau đó, tốt nhất chúng ta có thể sử dụng tính tương tự cosine không tính đến độ lớn.

3. Khoảng cách Hamming

Khoảng cách Hamming là số giá trị khác nhau giữa hai vectơ. Nó thường được sử dụng để so sánh hai chuỗi nhị phân có độ dài bằng nhau. Nó cũng có thể được sử dụng cho các chuỗi để so sánh mức độ tương tự của chúng với nhau bằng cách tính số ký tự khác nhau.

Nhược điểm

Như bạn có thể mong đợi, khoảng cách hamming rất khó sử dụng khi hai vectơ không có độ dài bằng nhau. Bạn muốn so sánh các vectơ cùng độ dài với nhau để hiểu vị trí nào không khớp.

Hơn nữa, nó không tính đến giá trị thực tế miễn là chúng khác nhau hoặc bằng nhau. Do đó, không nên sử dụng thước đo khoảng cách này khi độ lớn là một thước đo quan trọng.

Trường hợp sử dụng

Các trường hợp sử dụng điển hình bao gồm sửa / phát hiện lỗi khi dữ liệu được truyền qua mạng máy tính. Nó có thể được sử dụng để xác định số lượng bit bị bóp méo trong một từ nhị phân như một cách để ước tính lỗi.

Hơn nữa, bạn cũng có thể sử dụng khoảng cách Hamming để đo khoảng cách giữa các biến phân loại.

4. Khoảng cách Manhattan

Khoảng cách Manhattan, thường được gọi là khoảng cách Taxicab hoặc khoảng cách Khối Thành phố, tính toán khoảng cách giữa các vectơ có giá trị thực. Hãy tưởng tượng các vectơ mô tả các đối tượng trên một lưới đồng nhất chẳng hạn như bàn cờ vua. Khoảng cách Manhattan sau đó đề cập đến khoảng cách giữa hai vectơ nếu chúng chỉ có thể di chuyển theo góc vuông. Không có chuyển động theo đường chéo nào liên quan đến việc tính toán khoảng cách.

Nhược điểm

Mặc dù khoảng cách Manhattan có vẻ phù hợp với dữ liệu chiều cao , nhưng nó là một phép đo có phần kém trực quan hơn so với khoảng cách euclide, đặc biệt là khi sử dụng trong dữ liệu chiều cao.

Hơn nữa, nó có nhiều khả năng cho một giá trị khoảng cách cao hơn khoảng cách euclide vì nó không phải là đường đi ngắn nhất có thể. Điều này không nhất thiết đưa ra các vấn đề nhưng là điều bạn nên tính đến.

Trường hợp sử dụng

Khi tập dữ liệu của bạn có các thuộc tính rời rạc và / hoặc nhị phân, Manhattan dường như hoạt động khá tốt vì nó tính đến các đường dẫn mà thực tế có thể được thực hiện trong các giá trị của các thuộc tính đó. Lấy ví dụ, khoảng cách Euclide sẽ tạo ra một đường thẳng giữa hai vectơ trong khi thực tế điều này có thể không thực sự được.

5. Khoảng cách Chebyshev

Khoảng cách Chebyshev được định nghĩa là hiệu số lớn nhất giữa hai vectơ dọc theo bất kỳ chiều tọa độ nào. Nói cách khác, nó chỉ đơn giản là khoảng cách lớn nhất dọc theo một trục. Do tính chất của nó, nó thường được gọi là khoảng cách Bàn cờ vì số nước đi tối thiểu của nhà vua để đi từ ô vuông này sang ô vuông khác bằng khoảng cách Chebyshev.

Nhược điểm

Chebyshev thường được sử dụng trong các trường hợp sử dụng rất cụ thể, điều này gây khó khăn cho việc sử dụng làm thước đo khoảng cách cho mọi mục đích, như khoảng cách Euclide hoặc độ tương tự Cosine. Vì lý do đó, bạn chỉ nên sử dụng nó khi bạn hoàn toàn chắc chắn rằng nó phù hợp với trường hợp sử dụng của bạn.

Trường hợp sử dụng

Như đã đề cập trước đây, khoảng cách Chebyshev có thể được sử dụng để trích xuất số lượng nước đi tối thiểu cần thiết để đi từ ô vuông này sang ô vuông khác. Hơn nữa, nó có thể là một biện pháp hữu ích trong các trò chơi cho phép di chuyển 8 chiều không hạn chế.

Trong thực tế, khoảng cách Chebyshev thường được sử dụng trong hậu cần kho hàng vì nó gần giống với thời gian cần cẩu di chuyển một vật thể.

6. Minkowski

Khoảng cách Minkowski là một biện pháp phức tạp hơn một chút so với hầu hết. Nó là một số liệu được sử dụng trong không gian vectơ định mức [không gian thực n-chiều], có nghĩa là nó có thể được sử dụng trong một không gian mà khoảng cách có thể được biểu diễn dưới dạng vectơ có độ dài.

Biện pháp này có ba yêu cầu:

• Vectơ Zero - Vectơ 0 có độ dài bằng 0 trong khi mọi vectơ khác đều có độ dài dương. Ví dụ, nếu chúng ta đi từ nơi này đến nơi khác, thì khoảng cách đó luôn luôn là số dương. Tuy nhiên, nếu chúng ta đi từ một nơi đến chính nó, thì khoảng cách đó bằng không.
• Hệ số vô hướng - Khi bạn bội vectơ với một số dương thì độ dài của nó bị thay đổi trong khi vẫn giữ nguyên hướng của nó. Ví dụ, nếu chúng ta đi một khoảng cách nhất định theo một hướng và thêm một khoảng cách như nhau, thì hướng đó không thay đổi.
• Bất đẳng thức tam giác - Khoảng cách ngắn nhất giữa hai điểm là một đường thẳng.

Điều thú vị nhất về thước đo khoảng cách này là việc sử dụng tham số p. Chúng ta có thể sử dụng tham số này để điều khiển các chỉ số khoảng cách để gần giống với những người khác.

Giá trị chung của plà:

• p = 1 - Khoảng cách Manhattan
• p = 2 - Khoảng cách Euclide
• p = - Khoảng cách Chebyshev

Minkowski có những nhược điểm tương tự như các thước đo khoảng cách mà chúng đại diện, vì vậy hiểu biết tốt về các thước đo như Manhattan, Euclidean và khoảng cách Chebyshev là cực kỳ quan trọng.

Hơn nữa, tham số pthực sự có thể gây rắc rối khi làm việc vì việc tìm kiếm giá trị phù hợp có thể khá kém hiệu quả về mặt tính toán tùy thuộc vào trường hợp sử dụng của bạn.

Trường hợp sử dụng

Ưu điểm của nó plà khả năng lặp lại nó và tìm ra thước đo khoảng cách phù hợp nhất với trường hợp sử dụng của bạn. Nó cho phép bạn linh hoạt rất nhiều so với chỉ số khoảng cách của bạn, điều này có thể mang lại lợi ích to lớn nếu bạn đã quen thuộc với pvà nhiều thước đo khoảng cách.

7. Chỉ số Jaccard

Chỉ số Jaccard [hoặc Giao điểm trên Liên hợp] là một số liệu được sử dụng để tính toán mức độ giống nhau và đa dạng của các tập mẫu. Nó là kích thước của giao điểm chia cho kích thước của liên hiệp các tập mẫu.

Trong thực tế, nó là tổng số thực thể giống nhau giữa các tập hợp chia cho tổng số thực thể. Ví dụ: nếu hai tập hợp có 1 thực thể chung và có tổng cộng 5 thực thể khác nhau, thì chỉ số Jaccard sẽ là 1/5 = 0,2.

Để tính toán khoảng cách Jaccard, chúng ta chỉ cần trừ chỉ số Jaccard đi 1:

Nhược điểm

Một nhược điểm lớn của chỉ số Jaccard là nó bị ảnh hưởng nhiều bởi kích thước của dữ liệu. Các tập dữ liệu lớn có thể có tác động lớn đến chỉ số vì nó có thể làm tăng đáng kể sự liên kết trong khi vẫn giữ giao nhau.

Trường hợp sử dụng

Chỉ số Jaccard thường được sử dụng trong các ứng dụng sử dụng dữ liệu nhị phân hoặc nhị phân. Khi bạn có mô hình học sâu dự đoán các phân đoạn của một hình ảnh, chẳng hạn như ô tô, thì chỉ số Jaccard có thể được sử dụng để tính toán độ chính xác của phân đoạn được dự đoán đó cho các nhãn thực.

Tương tự, nó có thể được sử dụng trong phân tích độ tương tự văn bản để đo lường mức độ trùng lặp lựa chọn từ giữa các tài liệu. Do đó, nó có thể được sử dụng để so sánh các bộ mẫu.

8. Haversine

Khoảng cách Haversine là khoảng cách giữa hai điểm trên một hình cầu cho trước các kinh độ và vĩ độ của chúng. Nó rất giống với khoảng cách Euclide ở chỗ nó tính đường ngắn nhất giữa hai điểm. Sự khác biệt chính là không thể có đường thẳng nào vì giả thiết ở đây là hai điểm nằm trên một mặt cầu.

Nhược điểm

Một nhược điểm của phương pháp đo khoảng cách này là người ta cho rằng các điểm nằm trên một hình cầu . Trong thực tế, trường hợp này hiếm khi xảy ra, chẳng hạn như trái đất không tròn hoàn hảo, điều này có thể làm cho việc tính toán trong một số trường hợp trở nên khó khăn. Thay vào đó, sẽ rất thú vị khi nhìn về phía khoảng cách Vincenty mà thay vào đó, giả sử là một ellipsoid.

Trường hợp sử dụng

Như bạn có thể mong đợi, khoảng cách Haversine thường được sử dụng trong điều hướng. Ví dụ, bạn có thể sử dụng nó để tính khoảng cách giữa hai quốc gia khi bay giữa chúng. Lưu ý rằng nó sẽ ít phù hợp hơn nếu khoảng cách của bản thân chúng đã không quá lớn. Độ cong sẽ không có tác động lớn như vậy.

9. Chỉ số Sørensen-Dice

Chỉ số Sørensen-Dice rất giống với chỉ số Jaccard ở chỗ nó đo mức độ giống nhau và đa dạng của các tập mẫu. Mặc dù chúng được tính toán tương tự, chỉ số Sørensen-Dice trực quan hơn một chút vì nó có thể được xem là phần trăm trùng lặp giữa hai tập hợp, là giá trị từ 0 đến 1.

Trực giác quan trọng trong các phép đo khoảng cách vì nó cho phép sử dụng số liệu tốt hơn mà không cần v

Chỉ số Jaccard [hoặc Giao điểm trên Liên hợp] là một số liệu được sử dụng để tính toán mức độ giống nhau và đa dạng của các tập mẫu. Nó là kích thước của giao điểm chia cho kích thước của liên hiệp các tập mẫu.

Trong thực tế, nó là tổng số thực thể giống nhau giữa các tập hợp chia cho tổng số thực thể. Ví dụ: nếu hai tập hợp có 1 thực thể chung và có tổng cộng 5 thực thể khác nhau, thì chỉ số Jaccard sẽ là 1/5 = 0,2.

Để tính toán khoảng cách Jaccard, chúng ta chỉ cần trừ chỉ số Jaccard đi 1:

Nhược điểm

Giống như chỉ số Jaccard, cả hai đều phóng đại tầm quan trọng của các tập hợp có ít hoặc không có tập xác định chân lý căn bản. Kết quả là, nó có thể chiếm ưu thế về điểm số trung bình được thực hiện qua nhiều bộ. Nó có trọng số tỷ lệ nghịch với kích thước của tập hợp có liên quan hơn là coi chúng như nhau.

Trường hợp sử dụng

Các trường hợp sử dụng tương tự, nếu không giống nhau, như chỉ mục Jaccard. Bạn sẽ thấy nó thường được sử dụng trong các tác vụ phân đoạn hình ảnh hoặc phân tích độ tương tự văn bản.

LƯU Ý: Có nhiều thước đo khoảng cách hơn 9 thước đo được đề cập ở đây. Nếu bạn đang tìm kiếm các số liệu thú vị hơn, tôi khuyên bạn nên xem xét một trong những số liệu sau: Mahalanobis, Canberra, Braycurtis và KL-divergence.

Cảm ơn bạn đã đọc!

Nếu bạn cũng như tôi, đam mê AI, Khoa học Dữ liệu hoặc Tâm lý học, vui lòng thêm tôi trên LinkedIn hoặc theo dõi tôi trên Twitter .

Video liên quan