DIMACS Technical Report 95-44

September 1995

Monotone Linkage Clustering and Quasi-Convex Set Functions (pdf)

Yulia Kempner, Boris Mirkin and Ilya Muchnik

Greedy selection of subsets with adding the elements one by one is implicitly employed in many heuristically clustering procedures. Such a serialization procedure can be described generally in terms of a linkage function measuring entity-to-set dissimilarities. A quite known clustering technique, single linkage clustering, can be considered an example of the serialization procedure (actually, based on the minimum spanning tree construction) leading to the global maximum of corresponding "minimum split" set function. The purpose of this work is to have the property extended to a much wider class of so call monotone linkage functions. It is proved that the minimum split functions of monotone linkage functions can be maximized greedy-wisely, with the linkage function seriating. Moreover, it appears that this class of set functions coincides with the class of so called quasi-convex set functions. Thus, a class of set functions is characterized 'analytically', and a greedily maximizing format for it is indicated.