|
Traditional hierarchical clustering algorithms require the calculation of a dissimilarity matrix which is mapped to a binary tree or 'dendogram' based upon some predetermined criterion. Although 'optimally efficient' algorithms requiring O(N2) time and O(N) storage are known for several clustering methods, with few exceptions these algorithms are relatively inefficient in practice as many pairwise distance are measured which are not necessary for generation of the binary tree. We describe here a novel 'almost single link' algorithm which is efficient both theoretically and in practice, and which can be extended to provide fast algorithms for centroid, medium and single link clustering of large data sets. Generalization to other related clustering methods is expected to be straightforward. Our algorithm also suggests a fairly efficient method for generating minimal spanning trees. In performing the segmentation we employ a particular representation of the binary tree which simplifies the task of manual investigation of the hierarchy. A customized graphical user interface including a 2D scatter plot, a visual display of the dendogram, and a false color image with overlayered clusters makes the clustering procedure a highly interactive one. By suggesting, for each of the clustering methods, possible criteria which might be useful for extracting relevant clusters from the tree information, we are able to fully automate the cluster selection procedure and thereby further reduce the effort required to segment an image. The algorithms described have been transcribed into C code and combined into a single package, the 'hierarchical agglomerative clusterer', which has been applied to the analysis of hyperspectral image data of various forest and desert scenes acquired by the HYDICE sensor. The analyses were performed on a 266 Mhz Pentium PC platform running Windows NT 4.0. Typical segmentation times for the fastest algorithm ranged form 17 seconds for a 15232-pixel image to 2833 seconds for a 209840-pixel image, each pixel representing a 210-band spectrum. These initial studies suggest that the HAC package will provide a sound framework for making detailed comparisons of the effects of different clustering algorithms or dissimilarity measures. Its overall speed makes it a promising tool not only for hyperspectral image processing applications but for multivariate data analysis as a whole.
|
