MONOTONE LINKAGE CLUSTERING AND QUASI-CONCAVE SET-FUNCTIONS

Greedily seriating objects one by one is implicitly employed in many h euristic clustering procedures which can be described in terms of a li nkage function measuring entity-to-set dissimilarities. A well-known c lustering technique, single linkage clustering, can be considered as a n example of the seriation procedures (based actually on the minimum s panning tree construction) leading to the global maximum of a correspo nding ''minimum split'' set function. The purpose of this work is to e xtend this property to the wide class of so-called monotone linkages. It is shown that the minimum split functions of monotone linkages can be maximized greedily. Moreover, this class of set functions is proven to coincide with the class of so-called quasi-concave set functions.