2011 ClusteringwithRelativeConstrain

• (Liu et al., 2011) ⇒ Eric Yi Liu, Zhaojun Zhang, and Wei Wang. (2011). “Clustering with Relative Constraints.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020564

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Clustering+with+Relative+Constraints
• http://dl.acm.org/citation.cfm?id=2020408.2020564&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; algorithms; constrained clustering; data mining; experimentation; hierarchical clustering; relative constraints

Abstract

Recent studies have suggested using relative distance comparisons as constraints to represent domain knowledge. A natural extension to relative comparisons is the combination of two comparisons defined on the same set of three instances. Constraints in this form, termed Relative Constraints, provide a unified knowledge representation for both partitional and hierarchical clusterings. But many key properties of relative constraints remain unknown. In this paper, we answer the following important questions that enable the broader application of relative constraints in general clustering problems: “Feasibility: Does there exist a clustering that satisfies a given set of relative constraints? (consistency of constraints) “Completeness: Given a set of consistent relative constraints, how can one derive a complete clustering without running into dead-ends? “ Informativeness: How can one extract the most informative relative constraints from given knowledge sources? We show that any hierarchical domain knowledge can be easily represented by relative constraints. We further present a hierarchical algorithm that finds a clustering satisfying all given constraints in polynomial time. Experiments showed that our algorithm achieves significantly higher accuracy than the existing metric learning approach based on relative comparisons.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 ClusteringwithRelativeConstrain	Wei Wang Eric Yi Liu Zhaojun Zhang			Clustering with Relative Constraints				10.1145/2020408.2020564		2011