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. 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ụ

Giả sử các dữ liệu đã được phân tích, với khoảng cách Euclid theo pixel là mêtric.

Raw data

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.

Chế độ xem đồ họa

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