DIMACS TR: 95-44

Monotone Linkage Clustering and Quasi-Convex Set Functions



Authors: Yulia Kempner, Boris Mirkin

ABSTRACT

Selecting subsets with adding the elements one by one is implicitely employed in many heuristical clustering procedures. Such a procedure, seriation, can be described generally in terms of a linkage function measuring entity-to-set similarities.

A quite known clustering technique, Single linkage, can be considered an example of the seriation procedure (actually, based on the minimum spanning tree construction) leading to the global maximum of a corresponding "minimum split" set function. The purpose of this work is to have the property extended to a class of the linkage functions called monotone linkages. It is proved that the monotone linkage functions are minimum split functions for the quasi-convex set functions (and only for them). This allows to prove that the global optima of the quasi-convex set functions can be found with the multiple seriation algorithm based on corresponding linkage function.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-44.ps.gz

DIMACS Home Page