Thumbnail
Access Restriction
Open

Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Sat-based Framework ♦ Intuitive Objective Function ♦ Polynomial Time Algorithm ♦ Cluster-level Constraint ♦ Intractable Constraint Satisfaction Sub-problems ♦ Poor Clustering Solution ♦ Global Optimum ♦ Several Difficulty ♦ Large Constraint Set ♦ Additional Advantage ♦ Large Set ♦ Several Popular Algorithm ♦ Present Experimental Result ♦ Data Mining Community ♦ Several Objective Function ♦ Much Attention
Abstract The area of clustering under constraints has recently received much attention in the data mining community. However, most work involves adding constraints to existing algorithms which, although being quite pragmatic, raises several difficulties. Examples of these difficulties include creating intractable constraint satisfaction sub-problems and constrained clustering algorithms that are easily over-constrained so they may not converge or converge to a poor clustering solution. In this paper we show how both instance and cluster-level constraints can be expressed as instances of the 2SAT problem and how multiple calls to a 2SAT solver can be used to construct algorithms that are guaranteed to satisfy all the constraints and converge to a global optimum for a number of intuitive objective functions. Our approach provides two additional advantages. Firstly, it leads to polynomial time algorithms for the k = 2 case for several objective functions. Secondly, one can specify large sets of constraints without fear of over-constraining the problem: if one or more solutions satisfying all constraints exist, our algorithm is guaranteed to find a best such solution. We present experimental results to show that our approach outperforms several popular algorithms particularly for large constraint sets, where these algorithms are over-constrained and fair poorly. 1
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article