6
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ I'm hoping that some R experts will chime in - some of them are spatial statistics gurus. $\endgroup$
    – Iterator
    Commented Aug 25, 2011 at 16:20
  • $\begingroup$ 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.) $\endgroup$
    – Ben Bolker
    Commented Aug 25, 2011 at 16:30
  • $\begingroup$ 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? $\endgroup$
    – Ari B. Friedman
    Commented Aug 25, 2011 at 20:13
  • $\begingroup$ Possibly of interest: r-bloggers.com/examples-on-clustering-with-r $\endgroup$
    – Ari B. Friedman
    Commented Aug 26, 2011 at 8:50
  • $\begingroup$ 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). $\endgroup$
    – Sara
    Commented Aug 26, 2011 at 15:55

1 Answer 1

Reset to default
2
$\begingroup$

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 :(

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ How do you define $\alpha$? (BTW, you can register here on CV and then associate your account with the other one on SO.) $\endgroup$
    – chl
    Commented Sep 1, 2011 at 19:43
  • $\begingroup$ It depends on the magnitud of the weights. My weights are big, so alpha is 0.15. $\endgroup$
    – sara
    Commented Sep 2, 2011 at 7:41
  • $\begingroup$ 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 . $\endgroup$
    – user88
    Commented Sep 4, 2011 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.