“Distance matrix”的意思、由来-开放百科全书

词条

Distance matrix

释义

Metric distance
Non-metric distance
Comparison with related matrices
Comparison with adjacency matrix Comparison with Euclidean distance matrix
Applications
Hierarchical clustering Phylogenetic analysis Other uses
Examples
See also
References

In mathematics, computer science and especially graph theory, a distance matrix is a square matrix (two-dimensional array) containing the distances, taken pairwise, between the elements of a set. Depending upon the application involved, the distance being used to define this matrix may or may not be a metric. If there are {{mvar|N}} elements, this matrix will have size {{math|N×N}}. In graph-theoretic applications the elements are more often referred to as points, nodes or vertices.

Metric distance

When distance is defined as a metric, as for example in the Euclidean distance matrix, the distance matrix satisfies properties directly related to the defining properties of a metric. That is, if {{math|1=M = (x_ij)}} with {{math| 1 ≤ i, j ≤ N}} is a distance matrix for a metric distance, then

the entries on the main diagonal are all zero (that is, the matrix is a hollow matrix), i.e. {{math|1=x_ii = 0}} for all {{math|1 ≤ i ≤ N}},
all the off-diagonal entries are positive ({{math|x_ij > 0}} if {{math|i ≠ j}}),
the matrix is a symmetric matrix ({{math|1=x_ij = x_ji}}), and
for any {{math|i}} and {{math|j}}, {{math|x_ij ≤ x_ik + x_kj}} for all {{math|k}} (the triangle inequality). This can be stated in terms of tropical matrix multiplication

Another common example of a distance matrix arises in coding theory when in a block code the elements are strings of fixed length over an alphabet and the distance between them is given by the Hamming distance metric. The smallest non-zero entry in the distance matrix measures the error correcting and error detecting capability of the code.

Non-metric distance

In a network, a directed graph with weights assigned to the arcs, the distance between two nodes of the network can be defined as the minimum of the sums of the weights on the shortest paths joining the two nodes.^[1] This distance function, while well defined, is not a metric. There need be no restrictions on the weights other than the need to be able to combine and compare them, so negative weights are used in some applications. Since paths are directed, symmetry can not be guaranteed, and if cycles exist the distance matrix may not be hollow.

An algebraic formulation of the above can be obtained by using the min-plus algebra. Matrix multiplication in this system is defined as follows: Given two matrices and , their distance product is defined as an matrix such that . Note that the off-diagonal elements that are not connected directly will need to be set to infinity or a suitable large value for the min-plus operations to work correctly. A zero in these locations will be incorrectly interpreted as an edge with no distance, cost, etc.

If is an matrix containing the edge weights of a graph, then (using this distance product) gives the distances between vertices using paths of length at most edges, and is the distance matrix of the graph.

An arbitrary graph {{mvar|G}} on {{mvar|n}} vertices can be modeled as a weighted complete graph on {{mvar|n}} vertices by assigning a weight of one to each edge of the complete graph that corresponds to an edge of {{mvar|G}} and zero to all other edges. {{mvar|W}} for this complete graph is the adjacency matrix of {{mvar|G}}. The distance matrix of {{mvar|G}} can be computed from {{mvar|W}} as above, however, {{math|Wⁿ}} calculated by the usual matrix multiplication only encodes the number of paths between any two vertices of length at most {{mvar|n}}.

Applications

Hierarchical clustering

A distance matrix is necessary for hierarchical clustering.

Phylogenetic analysis

Distance matrices are used in phylogenetic analysis.

Other uses

In bioinformatics, distance matrices are used to represent protein structures in a coordinate-independent manner, as well as the pairwise distances between two sequences in sequence space. They are used in structural and sequential alignment, and for the determination of protein structures from NMR or X-ray crystallography.

Sometimes it is more convenient to express data as a similarity matrix.

It is used to define the distance correlation.

Examples

For example, suppose these data are to be analyzed, where pixel Euclidean distance is the distance metric.

The distance matrix would be:

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

These data can then be viewed in graphic form as a heat map. In this image, black denotes a distance of 0 and white is maximal distance.

References

1. ^Frank Harary, Robert Z. Norman and Dorwin Cartwright (1965) Structural Models: An Introduction to the Theory of Directed Graphs, pages 134–8, John Wiley & Sons {{mr|id=0184874}}

3 : Metric geometry|Bioinformatics|Matrices

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。