TY - GEN

T1 - Poclustering

T2 - 7th SIAM International Conference on Data Mining

AU - Liu, Jinze

AU - Zhang, Qi

AU - Wang, Wei

AU - McMillan, Leonard

AU - Prins, Jan

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=70449100635&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70449100635&partnerID=8YFLogxK

U2 - 10.1137/1.9781611972771.61

DO - 10.1137/1.9781611972771.61

M3 - Conference contribution

AN - SCOPUS:70449100635

SN - 9780898716306

T3 - Proceedings of the 7th SIAM International Conference on Data Mining

SP - 557

EP - 562

BT - Proceedings of the 7th SIAM International Conference on Data Mining

Y2 - 26 April 2007 through 28 April 2007

ER -