AN ORDER THEORETIC FRAMEWORK FOR OVERLAPPING CLUSTERING

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 phi which assign to each subcollection A subset of or equal to X of objects its internal degree of dissimilarity phi(A), subject only to the natural condition that A subset of or equal to B subset of or equal to X implies phi(A)less than or equal to phi(B), and we analyse on a rather abstract, purely order theoretic level how assumptions concerning the way such a mapping cp 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 phi as an arbitrary isotone mapping from a finite partially ordered set Q - e.g. the set P(X) of all subsets A of a finite set X - into a (partially) ordered set R - e.g. the nonnegative real numbers - and we study the correspondence between the two subsets C(phi) and D(phi) of Q, formed by the elements whose images are inaccessible from above and from below, respectively. While D(phi) constitutes the local data structure from which phi can be built up, C(phi) embodies the family of clusters associated with phi. Our results imply that in case Q:=P(X) and R:=R(greater than or equal to 0) one has #D less than or equal to n for all D is an element of D(phi) and some fixed n is an element of N if and only if [GRAPHICS] for all C-0,..., C-n is an element of C(phi) if and only if this holds for all subsets C-0,..., C-n subset of or equal to 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.