# Boundary conditions for clustering

I have some data that I would like to cluster with k-means.

One of the features is the hour of the day.

The problem is that the hour '23' is considered far from the hour '0'.

How can I map the data so that the boundary will be cyclic?

• I don't have an answer myself but this question seems to be related. Nov 11, 2015 at 14:36
• Can you pass a function or method for calculating the difference? Min of (larger - smaller), (smaller + 24 - larger) Nov 11, 2015 at 14:44
• I'm using R's kmeans, I don't see such an option. What languages/packages would allow me to do that?
– scf
Nov 11, 2015 at 15:42

Since you accepted another answer, which says this can't be done, I am editing this to include an example of it being done. Hope this helps!

The most logical way to transform hour is into two variables that swing back and forth out of sink. Imagine the position of the end of the hour hand of a 24-hour clock. The x position swings back and forth out of sink with the y position. For a 24-hour clock you can accomplish this with x=sin(2pi*hour/24),y=cos(2pi*hour/24).

You need both variables or the proper movement through time is lost. This is due to the fact that the derivative of either sin or cos changes in time where as the (x,y) position varies smoothly as it travels around the unit circle.

This method works really well for clustering and for keeping the distance between 15 minutes after midnight and 5 minutes before midnight "close" in Euclidean space. All of the modulo suggestions don't accomplish this and the cyclic representation that they do accomplish is pretty clumsy.

Finally, consider whether it is worthwhile to add a third feature to trace linear time, which can be constructed by hours (or minutes or seconds) from the start of the first record or a Unix time stamp or something similar. These three features then provide proxies for both the cyclic and linear progression of time e.g. you can pull out cyclic phenomenon like sleep cycles in people's movement and also linear growth like population vs. time.

Hope this helps!

Example of if being accomplished:

# Enable inline plotting
%matplotlib inline

#Import everything I need...

import numpy as np
import matplotlib as mp

import matplotlib.pyplot as plt
import pandas as pd

# Grab some random times from here: https://www.random.org/clock-times/
# put them into a csv.
df['hourfloat']=df.hour+df.minute/60.0
df['x']=np.sin(2.*np.pi*df.hourfloat/24.)
df['y']=np.cos(2.*np.pi*df.hourfloat/24.)

df


def kmeansshow(k,X):

from sklearn import cluster
from matplotlib import pyplot
import numpy as np

kmeans = cluster.KMeans(n_clusters=k)
kmeans.fit(X)

labels = kmeans.labels_
centroids = kmeans.cluster_centers_
#print centroids

for i in range(k):
# select only data observations with cluster label == i
ds = X[np.where(labels==i)]
# plot the data observations
pyplot.plot(ds[:,0],ds[:,1],'o')
# plot the centroids
lines = pyplot.plot(centroids[i,0],centroids[i,1],'kx')
# make the centroid x's bigger
pyplot.setp(lines,ms=15.0)
pyplot.setp(lines,mew=2.0)
pyplot.show()
return centroids


Now lets try it out:

kmeansshow(6,df[['x', 'y']].values)


You can just barely see that there are some after midnight times included with the before midnight green cluster. Now lets reduce the number of clusters and show that before and after midnight can be connected in a single cluster in more detail:

kmeansshow(3,df[['x', 'y']].values)


See how the blue cluster contains times that are from before and after midnight that are clustered together in the same cluster...

QED!

• Hands down the best answer I got to any of my questions.
– scf
Nov 23, 2015 at 9:08

## K-means uses the mean.

K-means is designed for least-squares. It only works reliably with (variants of) squared Euclidean distance (= sum of squared deviations).

### Counterexample:

Assume you have the two hours 0 and 23.

If they get assigned to the same cluster, k-means will compute the mean.

The mean of the two values is 11.5. It is not 23.5.

Abusing k-means with a cyclic "distance" may no longer converge, and will return nonsense results.

But there are more cases where the concept of a cluster center is not viable on cyclic data. For example, given an event on every full hour, what is the center? The arithmetic mean is 12 - but if you take cyclic space into account every hour is an equally good choice in cyclic space. Therefore, the concept of a "center" in cyclic space is fragile.

## Alternate clustering algorithms

You can try e.g. PAM or DBSCAN instead, with an appropriate similarity measure.

## Projection techniques

As pointed out by other answers, you can project the time to the unit circle via sin/cos(time/24*2pi). By computing the angle of the centroids, you can map this back to a point in time. But once you want additional attributes it gets hard to meaningfully normalize the data (to combine attributes), and you can get undefined time (e.g. if there are two points in a cluster, one at 6 and one at 18). I didn't discuss this because I wanted to point out that modifying the distance function is not a good idea for k-means.

• this isn't true. Your just not engineering your features carefully enough. The method I describe below works perfectly fine. the centroid locations lie along arcs of the unit circle. The mean of 23 and 0 in my Sin/Cos space is just the 23:30 location. When I get a minute I'll show you in an example. Nov 19, 2015 at 4:42
• I'm not trying to say it cannot be done with good feature transformations. What you are suggesting is a transformation into a space where squared Euclidean and the mean can be used. My answer is tailored to the suggestions of using "distances" like (x-y) mod 24. Nov 19, 2015 at 7:27
• But the question was "How can I map the data so that the boundary will be cyclic?". Your answer said that this is "abusing k-means". You should just delete the answer as it misleads all but the cognoscenti. Nov 19, 2015 at 8:05

Modular arithmetic. Generally you would do end - start mod 24

julia> mod(-23,24)
1


I seem to recall some programming languages treat mod of negative numbers in a different way, so check your implementation first.