1
$\begingroup$

My data coordinates are degrees so each axis has values [-180, 180]. Therefore it's easy to spot that in fact the scatter plot on the right end continues on the left side and the same thing for up and down. It can be assumed that the points are on the torus. enter image description here

I need to use k-means algorithm and I wonder how can I modify it (different distance metrics maybe?) so it can work with my torus (so the points from x=-180 will be treated as they are next to the ones from x=180). Is there any nice solution for that or it's not that easy?

$\endgroup$
  • $\begingroup$ I do not know of an implementation of kmeans that lets you use another distance metric. However, the closely related pam (k-medoids) does let you provide a distance matrix. Then you could use something like isomap to get distances along the toroidal surface,. $\endgroup$ – G5W Sep 21 at 20:51
  • 1
    $\begingroup$ One of the easiest solution which seems feasible with your particular data shown is simplty to find void bands and cut the canvas there. On your picture, I would cut horizontally at Y= -120 and vertically at X= 0. Then the canvas borders will not dismember any important (big, tight) clusters/clouds of yours and you may use usual k-means effectively. $\endgroup$ – ttnphns Sep 22 at 9:49
  • $\begingroup$ In principle don't need to modify the algorithm at all: simply replicate your data across nine panels in the plane in a 3 x 3 array, apply k-means, and project its solution (which ought to be doubly periodic) onto the torus. Problems could arise with randomized algorithms, so you might want to check the results for consistency. $\endgroup$ – whuber Sep 23 at 15:20
0
$\begingroup$

The crucial point - why you can't just use other distances in k-means - is that k-means uses the mean to represent a cluster. It is easy to see that the mean of -180 and +180 is 0, but that this is the worst possible choice as a cluster center here.

I'm not saying that you can't get this to work. You'd probably need to integrate some data rotation logic into the method...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.