Cluster analysis deals with procedures which
given a finite collection X of objects together with some kind of local dissimilarity information --identify those subcollections C of objects from X, called clusters, which exhibit a comparatively low degree of internal dissimilarity. In this note we study arbitrary mappings ~0 which assign to each subcollection A _~X of objects its internal degree of dissimilarity ~0(A), subject only to the natural condition that A _c B_ X implies ~0(A)~< ~o(B), and we analyse on a rather abstract, purely order theoretic level how assumptions concerning the way such a mapping q~ might be constructed from local data (that is, data involving only a few objects at a time) influence the degree of overlapping observed within the resulting family of clusters, --and vice versa.
Hence, unlike previous order theoretic approaches to cluster analysis, we do not restrict our attention to nonoverlapping, hierarchical clustering. Instead, we regard a dissimilarity function ~o as an arbitrary isotone mapping from a finite partially ordered set ,q --e.g. the set 9~(X) of all subsets A of a finite set X --into a (partially) ordered set 9~--e.g. the nonnegative real numbers and we study the correspondence between the two subsets ff(~0) and @(~0) of~, formed by the elements whose images are inaccessible from above and from below, respectively. While ~(~p) constitutes the local data structure from which ~0 can be built up, cg(q~) embodies the family of clusters associated with ~p.
Our results imply that in case ~.:=9~(X) and ~:= ~>0 one has #D<<.n for all De~(qg) and some fixed ne~ if and only if (~ Ci <~ max ~o(Ci) j i#j i=0 ..... n for all C o ..... C, eC~(~0) if and only if this holds for all subsets C o ..... C,=_X, generalizing a well-known criterion for n-conformity of hypergraphs as well as corresponding results due to Batbedat, dealing with the case n = 2.