Re: Clustering as constraint solving
- To: mathgroup at smc.vnet.net
- Subject: [mg67953] Re: Clustering as constraint solving
- From: "Steve Luttrell" <steve_usenet at _removemefirst_luttrell.org.uk>
- Date: Tue, 18 Jul 2006 05:50:40 -0400 (EDT)
- References: <e9frm8$2m7$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
The standard approach to solving your problem is to use the LBG (Linde-Buzo-Gray) algorithm for optimising a vector quantiser. This is an iterative algorithm that optimises precisely the 4 conditions that you specify. Overall, this optimisation process is highly non-linear, so I don't think you will find a closed-form solution except in highly symmetric cases. Steve Luttrell West Malvern, UK "Bonny Banerjee" <banerjee at cse.ohio-state.edu> wrote in message news:e9frm8$2m7$1 at smc.vnet.net... > 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. > > > >