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.Weyenberg, G., & Yoshida, R. (2015). Reconstructing the phylogeny: Computational methods. In Algebraic and Discrete Mathematical methods for modern Biology (pp. 293-319). Academic Press. 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ó  phần tử thì ma trận này sẽ có kích thước . 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ụ

Giả 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 

Cho 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 
 Phân nhóm dữ liệu
 Thị giác máy tính
 Phép nhân ma trận cộng tối thiểu

 Tham khảo 

Thể loại:Hình học mêtric
Thể loại:Tin sinh học
Thể loại:Ma trận