Poclustering: Lossless clustering of dissimilarity data

Given a set of objects V with a dissimilarity measure between pairs of objects in V, a PoGluster is a collection of sets P c powerset(V) partially ordered by the C relation such that S C T if the maximal dissimilarity among objects in S is less than the maximal dissimilarity among objects in T. PoChisters capture categorizations of objects that are not strictly hierarchical, such as those found in ontologies. PoChisters can not, in general, be constructed using hierarchical clustering algorithms. In this paper, we examine the relationship between PoChisters and dissimilarity matrices and prove that PoChisters are in one-to-one correspondence with the set of dissimilarity matrices. The PoChistering problem is NP-Complete, and we present a heuristic algorithm for it in this paper. Experiments on both synthetic and real datasets demonstrate the quality and scalability of the algorithms.