# Weighted spatial clustering

I am pretty new to clustering, so please be patient.

I have a set of points, and each point has a weight. I need to group these points into N clusters (N is defined).

I need these clusters to satisfy two conditions:

• The points of a cluster must be spatially connected.
• If a cluster has points with high weights, it must be smaller (less points). On the contrary, if the sum of the weights is small, it must have more points.

I have read another post that did something very similar.

It defined the distance between points, inserting the weight as a forth dimension. Then it defined several parameters to give more importance to the distance or to the weights. I cannot define these parameters (I think this would change for each example I try).

Also, this other post did not recommend any clustering algorithm...and I don't know where to start.

Thanks for the help!

PS: By the way, it would help if the algorithm is very fast.

## migrated from stackoverflow.comAug 28 '11 at 11:54

This question came from our site for professional and enthusiast programmers.

• I'm hoping that some R experts will chime in - some of them are spatial statistics gurus. – Iterator Aug 25 '11 at 16:20
• Unfortunately nothing obvious springs to mind. If you can find a k-means clustering algorithm that allows a user-defined distance (the basic one in R is kmeans, but only allows sum-of-squares distances: look for others via library(sos); findFn("k-means") or findFn("k-means distance") then you might be able to hack your distance metric so that (say) distance was proportional to wt1*wt2 so that more strongly weighted points count as farther apart. (I hope you get better advice than this.) (I'm recommending k-means because it's simple and defines N a priori.) – Ben Bolker Aug 25 '11 at 16:30
• I'm not sure about the weighting strategy you're proposing. Say you have a 2d grid of points, and the weight is your third dimension. A clustering algorithm would cluster things with huge weights together regardless of their x,y coordinates (because all points with z>>x,y would be close together in 3d space). That's not what one usually thinks of as a weight, and I don't think that's what you want, from bullet point 2, right? – Ari B. Friedman Aug 25 '11 at 20:13
• Possibly of interest: r-bloggers.com/examples-on-clustering-with-r – Ari B. Friedman Aug 26 '11 at 8:50
• Sorry for not responding earlier, I was checking the answers, not the comments. @Ben Bloker, I decided to go with K-means, but I am finding it quite slow (maybe is my implementation) and was planning to use priorities (more importance to distance than to weight). – Sara Aug 26 '11 at 15:55

For anybody who wants to know the answer, this is what I finally did:

I implemented a normal K-Means algorithm, but with some modifications:

• The calculation of the centroid is site = Sum(p * weight^alpha) / Sum(weight^alpha) for all the points that belong to that site.

• The calculation of the squared distance between point p and site s is squareDistance(p,s)*weight^alpha where alpha is some constant > 0.

The only problem is that my implementation is very slow :(

• How do you define $\alpha$? (BTW, you can register here on CV and then associate your account with the other one on SO.) – chl Sep 1 '11 at 19:43
• It depends on the magnitud of the weights. My weights are big, so alpha is 0.15. – sara Sep 2 '11 at 7:41
• Can you please register your account? You will be able to reclaim your reputation and edit your stuff. Just go to stats.stackexchange.com/users/login . – user88 Sep 4 '11 at 10:38