One approach to this is to create a distance measure between the items. If the distance measure represents distances along a tree, then that tree is a good estimate for the underlying, ``real'' tree. Normally, the distances do not represent a tree, so it is necessary to find a tree that accurately estimates the true distances. One approach to this, suggested by Barthélemy and Guénoche [11], creates a graph as follows: the nodes of the graph represent partitions of the items. These partitions are chosen because items within a partition are closer to each other than to those in the other side of the partition. Two nodes are adjacent if the partitions are consistent with coming from the same tree (which reduces to an inclusion condition). A clique in this graph represents a set of partitions that can be formed into a tree. Maximum cliques attempt to encapsulate as much of the partition data as possible. For more information, see Chapter 5 of [11].

Thu Oct 27 21:43:48 EDT 1994