Ma trận khoảng cách
Trong toán học, khoa học máy tính, và đặc biệt là lý thuyết đồ thị, một ma trận khoảng cách là một ma trận vuông (mảng hai chiều) chứa các khoảng cách, theo cặp, giữa các phần tử của một tập hợp.[1] Tùy theo ứng dụng, khoảng cách được dùng để định nghĩa ma trận này có thể/không có thể là một mêtric. Nếu có N phần tử thì ma trận này sẽ có kích thước N×N. Một số mêtric thường sử dụng là khoảng cách Euclid, khoảng cách cosine hay khoảng cách Manhattan.
Trong các ứng dụng lý thuyết đồ thị, các phần tử thường là điểm, nút hoặc đỉnh.
Ví dụ
sửaGiả sử các dữ liệu đã được phân tích, với khoảng cách Euclid theo pixel là mêtric.
Ma trận khoảng cách sẽ là:
| a | b | c | d | e | f | |
|---|---|---|---|---|---|---|
| a | 0 | 184 | 222 | 177 | 216 | 231 |
| b | 184 | 0 | 45 | 123 | 128 | 200 |
| c | 222 | 45 | 0 | 129 | 121 | 203 |
| d | 177 | 123 | 129 | 0 | 46 | 83 |
| e | 216 | 128 | 121 | 46 | 0 | 83 |
| f | 231 | 200 | 203 | 83 | 83 | 0 |
Những dữ liệu này sau đó có thể được xem dưới dạng đồ họa dưới dạng bản đồ nhiệt. Trong hình ảnh này, màu đen biểu thị khoảng cách bằng 0 và màu trắng là khoảng cách cực đại.
Tính ma trận khoảng cách bằng Python
sửaCho 3 điểm A(0,10), B(10,10) và C(20,20) trên không gian hai chiều. Hàm pdist() (thư viện scipy) được dùng để tính ma trận khoảng cách của 3 điểm này. Kết quả hàm này là một mảng khoảng cách (rút gọn từ ma trận khoảng cách, bỏ bớt số 0) theo thứ tự: [khoảng cách giữa B và A, khoảng cách giữa C và A, khoảng cách giữa C và B].
>>>x = array([[0,10],[10,10],[20,20]])
>>>pdist(x)
array([ 10., 22.36067977, 14.14213562]) // kết quả
Xem thêm
sửaTham khảo
sửa- ^ Weyenberg, G., & Yoshida, R. (2015). Reconstructing the phylogeny: Computational methods. In Algebraic and Discrete Mathematical methods for modern Biology (pp. 293-319). Academic Press.