# Modifying k-means for points on torus

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. 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?

• 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,. – G5W Sep 21 at 20:51
• 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. – ttnphns Sep 22 at 9:49
• 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. – whuber Sep 23 at 15:20