Normalization of the minimum spanning tree.

Abstract

A problem of considerable interest in pattern recognition and data analysis is that of describing the spatial structure of a data set. In the field of biology this could be based on graph construction. Although the minimum spanning tree (MST), contains less information than the Relative Neighbourhood, Gabriel and Delaunay graphs [16], this graph has been frequently used [3-9]. The MST is a subgraph of all the preceding graphs. Two main types of parameters can be derived from a graph. Some of the parameters are derived from the structure of the graph (topological parameters), whereas others are based on the Euclidean metrics of the graph (edge lengths). Since these parameters are used to characterize the spatial structure of data sets, they have to be normalized so that different biological structures may be compared. A model for the normalization of the most common parameters derived from the MST is thus presented here. Two aspects of the problem are considered: (i) omission of the metrics associated dimension of the Euclidean parameters in order to compare biological structures at different scale factors and (ii) elimination of border effects to avoid border artefacts.