|
57 |
|
|
|
|
second tree is quite different from the first, the nodes instead of representing clusters represent the individual objects to be clustered.
The MST is the tree of minimum length connecting the objects, where by 'length' I mean the sum of the weights of the connecting links in the tree.
Similarly we can define a maximum spanning tree as one of maximum length.
Whether we are interested in a minimum or maximum spanning tree depends entirely on the application we have in mind.
For convenience we will concentrate on the minimum spanning tree since it derives naturally from a dissimilarity coefficient and is more common anyway.
(In Chapter 6 we shall have cause to use a maximum spanning tree based on the expected mutual information measure.) Given the minimum spanning tree then the single-link clusters are obtained by deleting links from the MST in order of decreasing length; the connected sets after each deletion are the single-link clusters.
The order of deletion and the structure of the MST ensure that the clusters will be nested into a hierarchy.
The MST contains more information than the single-link hierarchy and only indirectly information about the single-link clusters. Thus, although we can derive the single-link hierarchy from it by a simple thresholding process, we cannot reverse this and uniquely derive the MST from the single-link hierarchy. It is interesting to consider in the light of this whether the MST would not be more suitable for document clustering than the single-link hierarchy. Unfortunately, it does not seem possible to update a spanning tree dynamically. To add a new object to a single-link hierarchy is relatively straightforward but to add one to an MST is much more complicated.
The representation of the single-link hierarchy through an MST has proved very useful in connecting single-link with other clustering techniques[51]. For example, Boulton and Wallace[52] have shown, using the MST representation, that under suitable assumptions the single-link hierarchy will minimise their information measure of classification. They see classification as a way of economically describing the original object descriptions, and the best classification is one which does it most economically in an information-theoretic sense. It is interesting that the MST has, independently of their work, been used to reduce storage when storing object descriptions, which amounts to a practical application of their result[53].
Implication of classification methods
It is fairly difficult to talk about the implementation of anautomatic classification method without at the same time referring tothe file |
|
|
57 |
|
|
|