Clustering as constraint solving
- To: mathgroup at smc.vnet.net
- Subject: [mg67940] Clustering as constraint solving
- From: "Bonny Banerjee" <banerjee at cse.ohio-state.edu>
- Date: Mon, 17 Jul 2006 06:51:59 -0400 (EDT)
- Organization: Ohio State University
- Sender: owner-wri-mathgroup at wolfram.com
Hi,
I am interested to know whether the problem of clustering a data set can be
posed as a constraint satisfaction problem and solved by solving those
constraints. Given a set of data, P={p1, p2, ...pn}, the problem of
clustering is to find a set of clusters, S={C1, C2,...Cm}, such that
1. For all i, Ci=/=null
2. For all i, j, i=/=j => Intersection(Ci, Cj)==null
3. Union(C1, C2,...Cm)==P
4. Minimize( f(C1, C2,...Cm) )
where f is a function of the clusters to be minimized, for example the sum
of variances of the clusters.
The above formulation of the clustering problem is simpler in the sense it
is already specified that "m" clusters are desired. The harder version of
the problem would be to figure out the "m" (0<m<n+1) that minimizes the
function f.
Is there any constraint satisfaction formulation of any of the above
versions of the clustering problem? Any information would be appreciated.
Thanks,
Bonny.