Khoảng cách Manhattan là gì?

Các thước đo khoảng cách là công cụ thiết yếu để đo mức độ xa gần giữa các đối tượng hoặc điểm trong không gian. Chúng đóng vai trò lớn trong nhiều lĩnh vực, bao gồm học máy, robot và hệ thống thông tin địa lý. Bằng cách định lượng khoảng cách, chúng ta có thể thực hiện các tác vụ như nhận dạng mẫu, phân cụm dữ liệu và phân tích không gian, vốn quan trọng đối với cả doanh nghiệp vì lợi nhuận lẫn giới nghiên cứu. 

Khoảng cách Manhattan, còn gọi là khoảng cách L1 hoặc khoảng cách “taxi”, nổi bật như một thước đo đặc biệt hữu ích để tính khoảng cách trên các đường đi dạng lưới hoặc giữa các điểm trong không gian đa chiều. Tại đây, chúng ta sẽ xem xét cả nền tảng toán học và cách triển khai khoảng cách Manhattan trong cả Python và R. 

"Manhattan distance." Ảnh bởi Dall-E.

Lưu ý rằng khoảng cách Manhattan chỉ là một phần của chủ đề rộng lớn hơn về các thước đo khoảng cách, vốn xuất hiện lặp đi lặp lại trong đủ loại lĩnh vực. Để trở thành chuyên gia trong học dựa trên khoảng cách, hãy cân nhắc khóa học Thiết kế quy trình làm việc học máy bằng Python của chúng tôi hoặc khóa Phân tích phân cụm trong R, tùy theo ngôn ngữ bạn ưa thích. 

Định nghĩa Khoảng cách Manhattan

Khoảng cách Manhattan là một thước đo dùng để xác định khoảng cách giữa hai điểm trên một đường đi dạng lưới. Khác với khoảng cách Euclid, đo đường thẳng ngắn nhất giữa hai điểm, khoảng cách Manhattan đo tổng các chênh lệch tuyệt đối giữa các tọa độ của hai điểm. Cách gọi "Manhattan" xuất phát từ việc, giống như một chiếc taxi chạy trên các con phố dạng lưới của Manhattan, nó phải di chuyển dọc theo các đường lưới. 

Về mặt toán học, khoảng cách Manhattan giữa hai điểm trong không gian n chiều là tổng các chênh lệch tuyệt đối của tọa độ Descartes của chúng. 

Công thức khoảng cách Manhattan sử dụng hàm giá trị tuyệt đối, đơn giản là chuyển mọi chênh lệch âm thành số dương. Điều này rất quan trọng khi tính khoảng cách, vì nó đảm bảo mọi phép đo đều không âm, phản ánh đúng độ lớn khoảng cách bất kể hướng di chuyển.

Tính toán và trực quan hóa Khoảng cách Manhattan

Như đã nói, khoảng cách Manhattan được tính bằng cách cộng các chênh lệch tuyệt đối giữa các tọa độ tương ứng của hai điểm. Giờ hãy minh họa bằng ví dụ trong không gian 2D và 3D.

Ví dụ 2D

Xét hai điểm: A(1, 1) và B(4, 5):

1. Tính |x₁ - x₂| = |1 - 4| = 3
2. Tính |y₁ - y₂| = |1 - 5| = 4
3. Cộng kết quả: 3 + 4 = 7

Do đó, khoảng cách Manhattan giữa A và B là 7 đơn vị. 

Khoảng cách Manhattan của hai véc-tơ. Ảnh bởi Tác giả.

Trong lưới 2D này, bạn có thể thấy khoảng cách Manhattan bám theo quãng đường một chiếc taxi sẽ đi, chỉ di chuyển theo phương ngang và dọc để đi từ điểm A đến điểm B.

Ví dụ 3D

Giờ xét hai điểm trong không gian 3D: A(1, 2, 3) và B(4, 5, 6):

1. Tính |x₁ - x₂| = |1 - 4| = 3
2. Tính |y₁ - y₂| = |2 - 5| = 3
3. Tính |z₁ - z₂| = |3 - 6| = 3
4. Cộng kết quả: 3 + 3 + 3 = 9

Khoảng cách Manhattan giữa các điểm 3D này là 9 đơn vị.

So sánh với khoảng cách Euclid

Trong khi khoảng cách Manhattan đo quãng đường dọc theo các đường lưới, khoảng cách Euclid đo khoảng cách đường thẳng giữa hai điểm, hay như cách nói quen thuộc “đường chim bay”. 

Với ví dụ 2D của chúng ta:

• Khoảng cách Manhattan: 7 đơn vị
• Khoảng cách Euclid: √((1-4)^² + (1-5)^²) = 5 đơn vị

Dưới đây là so sánh trực quan giữa khoảng cách Manhattan và Euclid: 

Khoảng cách Manhattan so với Euclid. Ảnh bởi Tác giả.

Trong không gian Euclid, khoảng cách Euclid luôn nhỏ hơn hoặc bằng khoảng cách Manhattan. 

Lựa chọn giữa khoảng cách Manhattan và khoảng cách Euclid

Khoảng cách Manhattan đặc biệt hữu ích trong các tình huống khi:

1. Việc di chuyển bị giới hạn theo các đường dạng lưới (ví dụ: ô phố, bố trí bo mạch).
2. Di chuyển chéo không được phép hoặc tốn kém hơn.
3. Bạn làm việc với dữ liệu nhiều chiều trong học máy, nơi nó có thể hiệu quả tính toán hơn khoảng cách Euclid.
4. Bạn phân tích khác biệt trong dữ liệu rời rạc hoặc thứ bậc.

Ngược lại, khoảng cách Euclid phù hợp hơn khi:

1. Bạn đo khoảng cách vật lý trong không gian mở.
2. Bạn làm việc với dữ liệu liên tục, nơi các chuyển động theo đường chéo đều hợp lệ như nhau.

Ứng dụng của Khoảng cách Manhattan

Khoảng cách Manhattan được ứng dụng trong nhiều lĩnh vực khoa học máy tính, phân tích dữ liệu và công nghệ địa không gian. Dưới đây là một số mảng tiêu biểu nơi nó đặc biệt hữu ích.

Thuật toán tìm đường (ví dụ: thuật toán A*) 

Trong môi trường dạng lưới, khoảng cách Manhattan cung cấp một heuristic nhanh và hiệu quả để ước lượng khoảng cách giữa hai điểm. Nó đặc biệt hữu ích trong thuật toán A*, nơi có thể giúp dẫn hướng tìm kiếm tới mục tiêu hiệu quả hơn trong các kịch bản chỉ cho phép di chuyển theo chiều ngang và dọc. Hãy nghĩ đến việc định tuyến trên đường phố thành phố, thuật toán giải mê cung và một số dạng tìm đường trong AI trò chơi điện tử. 

Kỹ thuật phân cụm (ví dụ: phân cụm K-Means) 

Khoảng cách Manhattan có thể được dùng làm thước đo khoảng cách trong các thuật toán phân cụm, nhất là khi xử lý dữ liệu nhiều chiều. Trong phân cụm K-Means, dùng khoảng cách Manhattan thay vì Euclid có thể cho kết quả tốt hơn, đặc biệt với dữ liệu thưa nhiều chiều hoặc khi có ngoại lệ. Ngoài ra, nó thường được ưa chuộng trong phân loại văn bản và phân cụm tài liệu nhờ hiệu quả trong các không gian véc-tơ thưa. Độ nhạy thấp hơn của khoảng cách Manhattan đối với các giá trị cực đoan theo từng chiều có thể dẫn đến kết quả phân cụm cân bằng hơn trên một số bộ dữ liệu.

Nhận dạng ảnh 

Khoảng cách Manhattan có thể được dùng để so sánh các giá trị điểm ảnh hoặc véc-tơ đặc trưng. Nó đặc biệt hữu ích trong khớp mẫu (template matching), khi bạn cố tìm các xuất hiện của một ảnh nhỏ trong ảnh lớn. Nó cũng có giá trị trong hệ thống nhận diện khuôn mặt, phát hiện đối tượng trong luồng video, hoặc khớp mẫu trong các cơ sở dữ liệu ảnh lớn, nơi tốc độ là tối quan trọng và mức mất mát nhỏ về độ chính xác so với khoảng cách Euclid thường không đáng kể.

Phát hiện ngoại lệ 

Khoảng cách Manhattan có thể được dùng để xác định các điểm dữ liệu khác biệt đáng kể so với phần còn lại trong một tập dữ liệu vì nó kém nhạy với các giá trị cực đoan theo từng chiều hơn so với khoảng cách Euclid. Thuộc tính này giúp nó hữu ích trong các hệ thống phát hiện bất thường, như phát hiện gian lận hoặc an ninh mạng. Chẳng hạn, trong hệ thống tài chính, khoảng cách Manhattan có thể giúp nhận diện các mẫu giao dịch bất thường mà không bị ảnh hưởng quá mức bởi một giá trị cực đoan ở một thuộc tính đơn lẻ, từ đó có thể giảm sai sót.

Hệ thống thông tin địa lý (GIS) 

Trong ứng dụng GIS, khoảng cách Manhattan có thể mô hình hóa chuyển động dọc theo mạng lưới đường phố dạng lưới, hữu ích cho quy hoạch đô thị và logistics. Nó được dùng trong các bài toán vị trí–phân bổ, như xác định vị trí tối ưu cho cơ sở dựa trên việc tối thiểu hóa tổng quãng đường di chuyển trong thành phố. Khoảng cách Manhattan cũng có thể áp dụng trong các tác vụ phân tích không gian, như tạo vùng đệm quanh các đặc trưng tuyến tính như đường bộ hoặc sông ngòi. Các nhà quy hoạch đô thị có thể dùng nó để phân tích khả năng tiếp cận dịch vụ công, còn các công ty logistics có thể tận dụng để tối ưu lộ trình giao hàng trong thành phố.

Các tính chất toán học của Khoảng cách Manhattan

Khoảng cách Manhattan có một số tính chất toán học quan trọng khiến nó đặc biệt hữu ích. Hãy xem xét hai khía cạnh chính: các tính chất không gian metric và độ bền vững trước ngoại lệ.

Các tính chất của không gian metric

Khoảng cách Manhattan là một metric thực thụ, nghĩa là nó thỏa mãn cả bốn điều kiện cần cho một hàm khoảng cách trong không gian metric:

1. Không âm: Khoảng cách giữa bất kỳ hai điểm nào luôn không âm. d(x, y) ≥ 0 với mọi x và y.
2. Đồng nhất của phần không phân biệt: Khoảng cách từ một điểm đến chính nó bằng 0, và nếu khoảng cách giữa hai điểm bằng 0 thì hai điểm đó là một. d(x, y) = 0 khi và chỉ khi x = y.
3. Đối xứng: Khoảng cách từ điểm A đến điểm B bằng khoảng cách từ B đến A. d(x, y) = d(y, x) với mọi x và y.
4. Bất đẳng thức tam giác: Khoảng cách giữa hai điểm luôn nhỏ hơn hoặc bằng tổng khoảng cách từ các điểm đó tới một điểm thứ ba. d(x, z) ≤ d(x, y) + d(y, z) với mọi x, y và z.

Khác với khoảng cách cosine, vốn không thỏa mãn bất đẳng thức tam giác, việc khoảng cách Manhattan tuân thủ đầy đủ các tính chất này khiến nó hữu dụng trong nhiều ứng dụng toán học và tính toán. Ví dụ:

• Trong các thuật toán tối ưu, bất đẳng thức tam giác có thể dùng để cắt tỉa không gian tìm kiếm hiệu quả.
• Trong các cấu trúc dữ liệu như cây metric, các tính chất này cho phép tìm kiếm láng giềng gần nhất nhanh hơn.
• Trong học máy, các thuật toán dựa trên thước đo khoảng cách (như k-láng giềng gần nhất) có thể tận dụng các tính chất này cho đảm bảo lý thuyết và triển khai hiệu quả.

Khả năng phân biệt ngoại lệ tốt hơn 

Khoảng cách Manhattan, với cách cộng tuyến tính, thường cung cấp khả năng phân biệt ngoại lệ tốt hơn so với khoảng cách Euclid, vốn bình phương chênh lệch. Sự khác biệt này xuất phát từ việc khoảng cách Manhattan cộng dồn các chênh lệch tuyệt đối ở từng chiều một cách độc lập, giảm ảnh hưởng áp đảo của các sai khác lớn ở bất kỳ chiều đơn lẻ nào.

Xét hai điểm trong không gian 2D: A(0, 0) và B(10, 0). Giờ thêm một điểm ngoại lệ C có tọa độ (0, 100):

• Khoảng cách Manhattan giữa A và C: |0 - 0| + |0 - 100| = 100
• Khoảng cách Euclid giữa A và C: √((0 - 0)^² + (0 - 100)^²) = 100
• Khoảng cách Manhattan giữa B và C: |10 - 0| + |0 - 100| = 110
• Khoảng cách Euclid giữa B và C: √((10 - 0)^² + (0 - 100)^²) ≈ 100,5

Khoảng cách Manhattan vs Euclid với ngoại lệ. Ảnh bởi Tác giả

Trong ví dụ này, khoảng cách Manhattan phân biệt rõ giữa AC và BC, trong khi khoảng cách Euclid cho thấy chúng gần như bằng nhau do tác động chi phối của ngoại lệ ở tọa độ y.

Thuộc tính này khiến khoảng cách Manhattan đặc biệt hữu ích trong:

1. Không gian nhiều chiều, nơi ngoại lệ thường gặp, như xử lý ảnh hoặc phân tích văn bản.
2. Các thuật toán phân cụm khi bạn muốn giảm tác động của ngoại lệ lên trọng tâm cụm.
3. Các hệ thống phát hiện bất thường khi bạn muốn nhận diện ngoại lệ mà không phóng đại quá mức tầm quan trọng của chúng.

Nhờ kém nhạy với các giá trị cực đoan theo từng chiều, khoảng cách Manhattan có thể mang lại thước đo độ khác biệt cân bằng hơn cho nhiều bộ dữ liệu ngoài đời thực, đặc biệt là những bộ dữ liệu nhiễu hoặc không hoàn hảo.

Khoảng cách Manhattan trong Python và R

Tại đây, chúng ta sẽ tìm hiểu cách tính khoảng cách Manhattan bằng Python và R. Mỗi ví dụ sẽ minh họa các cách tiếp cận khác nhau, từ hàm tự viết đến phương thức trong thư viện.

Ví dụ Python

Python cung cấp vài cách để tính khoảng cách Manhattan. Hãy xem hai phương pháp khác nhau.

1. Tính toán bằng mảng NumPy:

import numpy as np
point_a_np = np.array([1, 1, 1])
point_b_np = np.array([4, 5, 6])
distance_numpy = np.sum(np.abs(point_a_np - point_b_np))
print(f"Manhattan distance (NumPy): {distance_numpy}")Được hỗ trợ bởi

Kết quả: 

Manhattan distance (NumPy): 12Được hỗ trợ bởi

Phương pháp này dùng trực tiếp các mảng NumPy, có thể rất hiệu quả, đặc biệt khi xử lý các tập dữ liệu lớn hoặc khi bạn đã làm việc với mảng NumPy trong phân tích của mình.

2. Tính toán bằng hàm cityblock() của SciPy: 

from scipy.spatial.distance import cityblock
point_a = (1, 1, 1)
point_b = (4, 5, 6)
distance_scipy = cityblock(point_a, point_b)
print(f"Manhattan distance (SciPy): {distance_scipy}")Được hỗ trợ bởi

Kết quả:

Manhattan distance (SciPy): 12Được hỗ trợ bởi

SciPy cung cấp hàm cityblock() để tính khoảng cách Manhattan. Cách này đơn giản và hiệu quả, đặc biệt khi bạn đang dùng SciPy trong dự án. 

Ví dụ R

R cũng cung cấp nhiều cách để tính khoảng cách Manhattan. Hãy xem hai cách tiếp cận.

1. Tạo hàm tùy chỉnh

manhattan_distance <- function(x1, y1, x2, y2) {
  abs(x1 - x2) + abs(y1 - y2)
}
# Example points 
point1 <- c(3, 5) # (x1, y1) 
point2 <- c(1, 9) # (x2, y2) 
# Calculate Manhattan distance between point1 and point2 
distance <- manhattan_distance(point1[1], point1[2], point2[1], point2[2]) 
print(paste("Manhattan distance (custom function):", distance))Được hỗ trợ bởi

Kết quả:

"Manhattan distance (custom function): 6"Được hỗ trợ bởi

Trong ví dụ này, chúng ta tạo một hàm tùy chỉnh tên manhattan_distance. Hàm nhận tọa độ của hai điểm làm đầu vào và tìm khoảng cách Manhattan bằng cách cộng các chênh lệch tuyệt đối của từng tọa độ tương ứng.

2. Dùng thư viện stats

point_a <- c(1, 1, 1)
point_b <- c(4, 5, 6)
distance_builtin <- stats::dist(rbind(point_a, point_b), method = "manhattan")
print(paste("Manhattan distance:", distance_builtin))Được hỗ trợ bởi

Kết quả: 

"Manhattan distance: 12"Được hỗ trợ bởi

Trong ví dụ thứ hai, chúng ta sử dụng hàm dist() từ gói stats để tính khoảng cách Manhattan. Cách tiếp cận này hữu ích khi làm việc với ma trận hoặc nhiều điểm, vì nó đơn giản hóa quy trình đáng kể.

Kết luận

Tầm quan trọng của khoảng cách Manhattan nằm ở sự đơn giản, hiệu quả tính toán và độ bền vững trước ngoại lệ trong một số kịch bản. Khác với khoảng cách Euclid, khoảng cách Manhattan thường cho kết quả trực quan hơn trong các hệ thống dạng lưới và có thể tính toán hiệu quả hơn, đặc biệt trong không gian nhiều chiều. 

Hơn nữa, khoảng cách Manhattan và các thước đo khoảng cách khác xuất hiện trong rất nhiều bối cảnh. Bên cạnh khóa Thiết kế quy trình làm việc học máy bằng Python của chúng tôi, có một chương về học dựa trên khoảng cách, và khóa Phân tích phân cụm trong R, sử dụng các thước đo dựa trên khoảng cách cho phân loại và giảm chiều, bạn cũng có thể xem khóa Phát hiện bất thường trong Python, sử dụng thước đo khoảng cách để phát hiện ngoại lệ và chuẩn hóa đặc trưng.  

Hãy nhớ rằng lựa chọn thước đo khoảng cách có thể ảnh hưởng đáng kể đến hiệu năng và kết quả của thuật toán. Khi hiểu được thời điểm và cách sử dụng khoảng cách Manhattan, bạn đang bổ sung một công cụ mạnh mẽ vào bộ công cụ khoa học dữ liệu của mình. Tiếp tục thử nghiệm, học hỏi và mở rộng giới hạn những gì có thể với các thuật toán dựa trên khoảng cách!