Ma trận khoảng cách – Wikipedia

Trong toán học, khoa học máy tính và đặc biệt là lý thuyết đồ thị, 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, được ghép theo chiều ngang, giữa các phần tử của một tập hợp. Tùy thuộc vào ứng dụng liên quan, khoảng cách đang được sử dụng để xác định ma trận này có thể hoặc không thể là một số liệu. Nếu có các phần tử N ma trận này sẽ có kích thước N × N . Trong các ứng dụng lý thuyết đồ thị, các phần tử thường được gọi là điểm, nút hoặc đỉnh.

Khoảng cách số liệu [ chỉnh sửa ]

Khi khoảng cách được xác định là một số liệu, ví dụ như trong ma trận khoảng cách Euclide, ma trận khoảng cách thỏa mãn các thuộc tính liên quan trực tiếp đến các thuộc tính xác định của a số liệu. Đó là, nếu M = ( x ij ) với 1 ≤ i j N là ma trận khoảng cách cho khoảng cách hệ mét, sau đó

  • các mục trên đường chéo chính đều bằng 0 (nghĩa là ma trận là ma trận rỗng), tức là x ii = 0 cho tất cả 1 ≤ ] i N
  • tất cả các mục ngoài đường chéo đều dương ( x ij > 0 nếu i j ),
  • ma trận là ma trận đối xứng ( x ij = x ji ), và
  • bất kỳ i j x ij x ik + x 19659023] cho tất cả k (bất đẳng thức tam giác). Điều này có thể được nói theo cách nhân ma trận nhiệt đới

Một ví dụ phổ biến khác về ma trận khoảng cách phát sinh trong lý thuyết mã hóa khi trong mã khối, các phần tử là các chuỗi có độ dài cố định trên một bảng chữ cái và khoảng cách giữa chúng được đưa ra bởi khoảng cách Hamming số liệu. Mục nhập khác không nhỏ nhất trong ma trận khoảng cách đo khả năng sửa lỗi và phát hiện lỗi của mã.

Khoảng cách không theo số liệu [ chỉnh sửa ]

Trong một mạng, một đồ thị có hướng có trọng số được gán cho các cung, khoảng cách giữa hai nút của mạng có thể được xác định là tối thiểu tổng các trọng số trên các đường đi ngắn nhất nối hai nút. [1] Hàm khoảng cách này, trong khi được xác định rõ, không phải là một số liệu. Không cần phải có giới hạn về các trọng số ngoài nhu cầu có thể kết hợp và so sánh chúng, vì vậy các trọng số âm được sử dụng trong một số ứng dụng. Vì các đường dẫn được định hướng, tính đối xứng không thể được đảm bảo và nếu chu kỳ tồn tại, ma trận khoảng cách có thể không rỗng.

Một công thức đại số của những điều trên có thể thu được bằng cách sử dụng đại số cộng cực tiểu. Phép nhân ma trận trong hệ thống này được định nghĩa như sau: Cho hai ma trận

n × n { displaystyle n times n}

ma trận = ( a i j ) { displaystyle A = (a_ {ij})}

B = ( b i j ) { displaystyle B = (b_ {ij})}

sản phẩm khoảng cách của họ

C = ( c i j ) = A B { displaystyle C = (c_ {ij}) = A star B}

n × n { displaystyle n lần n}

sao cho

c i [19659047] j = min k = 1 n { a i k + [19659045] b k j } { displaystyle c_ {ij} = min _ {k = 1} ^ {n} {a_ {ik} + b_ {kj} }}

. Lưu ý rằng các phần tử nằm ngoài đường chéo không được kết nối trực tiếp sẽ cần được đặt thành vô cực hoặc giá trị lớn phù hợp để các hoạt động cộng tối thiểu hoạt động chính xác. Số 0 ở những vị trí này sẽ được hiểu không chính xác là một cạnh không có khoảng cách, chi phí, v.v.

Nếu

W { displaystyle W}

là một

n × n { displaystyle n times n}

ma trận chứa các trọng số cạnh của đồ thị sau đó

W k { displaystyle W ^ {k}}

k { displaystyle k}

cạnh và

W n [19659116] { displaystyle W ^ {n}}

là ma trận khoảng cách của đồ thị.

Một đồ thị tùy ý G trên n các đỉnh có thể được mô hình thành một đồ thị hoàn chỉnh có trọng số trên các đỉnh n bằng cách gán trọng số của một cho mỗi cạnh của mỗi cạnh của đồ thị hoàn chỉnh tương ứng với một cạnh của G và bằng không với tất cả các cạnh khác. W cho biểu đồ hoàn chỉnh này là ma trận kề của G . Ma trận khoảng cách của G có thể được tính từ W như trên, tuy nhiên, W n được tính bằng phép nhân ma trận thông thường chỉ mã hóa số lượng đường đi giữa hai đỉnh bất kỳ chiều dài nhiều nhất n .

Ứng dụng [ chỉnh sửa ]

Phân cụm theo phân cấp [ chỉnh sửa ]

Một ma trận khoảng cách là cần thiết để phân cụm.

Phân tích phát sinh gen [ chỉnh sửa ]

Ma trận khoảng cách được sử dụng trong phân tích phát sinh gen.

Các cách sử dụng khác [ chỉnh sửa ]

Trong tin sinh học, ma trận khoảng cách được sử dụng để biểu diễn các cấu trúc protein theo cách phối hợp độc lập, cũng như khoảng cách theo cặp giữa hai chuỗi trong không gian chuỗi . Chúng được sử dụng trong sự liên kết cấu trúc và tuần tự, và để xác định cấu trúc protein từ tinh thể học tia X hoặc tia X.

Đôi khi thuận tiện hơn để thể hiện dữ liệu dưới dạng ma trận tương tự.

Nó được sử dụng để xác định mối tương quan khoảng cách.

Ví dụ [ chỉnh sửa ]

Ví dụ: giả sử những dữ liệu này sẽ được phân tích, trong đó khoảng cách pixel Euclide là chỉ số khoảng cách.

Dữ liệu thô

Ma trận khoảng cách sẽ là:

a b c d e f
một 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ạng đồ họa dưới dạng bản đồ nhiệt. Trong ả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 tối đa.

Chế độ xem đồ họa

Xem thêm [ chỉnh sửa ]

Tài liệu tham khảo [ chỉnh sửa ]

visit site
site