2011 IncorporatingSATSolversIntoHier

• (Gilpin & Davidson, 2011) ⇒ Sean Gilpin, and Ian Davidson. (2011). “Incorporating SAT Solvers Into Hierarchical Clustering Algorithms: An Efficient and Flexible Approach.” 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.2020585

Subject Headings: Constrained Clustering.

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Incorporating+SAT+Solvers+Into+Hierarchical+Clustering+Algorithms%3A+An+Efficient+and+Flexible+Approach
• http://dl.acm.org/citation.cfm?id=2020408.2020585&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; clustering; constrained clustering; data mining; experimentation; hierarchical clustering

Abstract

The area of constrained clustering has been actively pursued for the last decade. A more recent extension that will be the focus of this paper is constrained hierarchical clustering which allows building user-constrained dendrograms / trees. Like all forms of constrained clustering, previous work on hierarchical constrained clustering uses simple constraints that are typically implemented in a procedural language. However, there exists mature results and packages in the fields of constraint satisfaction languages and solvers that the constrained clustering field has yet to explore. This work marks the first steps towards introducing constraints satisfaction languages / solvers into hierarchical constrained clustering. We make several significant contributions. We show how many existing and new constraints for hierarchical clustering, can be modeled as a Horn-SAT problem that is easily solvable in polynomial time and which allows their implementation in any number of declarative languages or efficient solvers. We implement our own solver for efficiency reasons. We then show how to formulate constrained hierarchical clustering in a flexible manner so that any number of algorithms, whose output is a dendrogram, can make use of the constraints.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 IncorporatingSATSolversIntoHier	Ian Davidson Sean Gilpin			Incorporating SAT Solvers Into Hierarchical Clustering Algorithms: An Efficient and Flexible Approach				10.1145/2020408.2020585		2011