# SOM clustering for nominal/circular variables

Just wondering if anyone is familiar with clustering nominal inputs. I've been looking at SOM as a solution but apparently it only works with numerical features. Are there any extensions for categorical features? Specifically I was wondering about 'Days of the Week' as a possible features. Of course it is possible to convert it into a numerical feature (i.e. Mon - Sun corresponding to nos 1-7) however then the Euclidean distance between Sun and Mon (1&7) would not be the same as the distance from Mon to Tues (1&2). Any suggestions or ideas would be much appreciated.

-
(+1) a very interesting question – steffen Jul 19 '11 at 9:22
Cyclic variables are best thought of as elements of the unit circle in the Complex plane. Thus, it would be natural to map the days of the week to (say) the points $\exp(2 j \pi i / 7)$, $j=0, \ldots, 6$; i.e., $(\cos(0), \sin(0))$, $(\cos(2 \pi/7), \sin(2\pi/7))$, ... $(\cos(12\pi/7),\sin(12\pi/7))$. – whuber Jul 19 '11 at 14:02
would i have to code up my own distance matrix then specific to cyclic variables? just wondering if there were already existing algorithms for this type of clustering. thx – Michael Jul 20 '11 at 3:48
@Michael: I believe you will want to specify your own distance metric that is appropriate for your application, and that is defined over all the dimensions in your data, not just the DOW. Formally, letting x, y denote points in your data space, you need to define a metric function d(x,y) with the usual properties: d(x,x)=0, d(x,y)=d(y,x), and d(x,z) <= d(x,y)+d(y,z). Once you've done that, creating the SOM is mechanical. The creative challenge is to define d() in a way that captures the notion of "similarity" appropriate to your application. – Arthur Small Dec 14 '12 at 14:48

Commonly nominal variables are dummy coded when used in SOM (e.g., one variable for with a 1 for Monday 0 for not Monday, another for Tuesday, etc.).

You can incorporate additional information by creating combined categories of adjacent days. For example: Monday&Tuesday, Tuesday&Wednesday, etc. However, if your data relates to human behaviour it is often more useful to use Weekday and Weekend as categories.

-

For nominal variables, the typical encoding in a neural network or electrical engineering context is called "one-hot" -- a vector of all 0s, with one 1 in the appropriate position for the value for the variable. For the days of the week, for example, there are seven days, so your one-hot vectors would be of length seven. Then Monday would be represented as [1 0 0 0 0 0 0], Tuesday as [0 1 0 0 0 0 0], etc.

As Tim hinted, this approach can be generalized easily to encompass arbitrary boolean feature vectors, where each position in the vector corresponds to a feature of interest in your data, and the position is set to 1 or 0 to indicate the presence or absence of that feature.

Once you have binary vectors, the Hamming distance becomes a natural metric, though Euclidean distance is used as well. For one-hot binary vectors, the SOM (or other function approximator) will naturally interpolate between 0 and 1 for each vector position. In this case, these vectors are often treated as the parameters of a Boltzmann or softmax distribution over the space of the nominal variable ; this treatment gives a way to use the vectors in some sort of KL divergence scenario as well.

Cyclic variables are much trickier. As Arthur said in the comments, you'd need to define a distance metric yourself that incorporates the cyclic nature of the variable.

-

Background:

The most logical way to transform hour is into two variables that swing back and forth out of sync. Imagine the position of the end of the hour hand of a 24-hour clock. The x position swings back and forth out of sync 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 whereas the (x,y) position varies smoothly as it travels around the unit circle.

Finally, consider whether it is worthwhile to add a third feature to trace linear time, which can be constructed as 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 phenomena like sleep cycles in people's movement and also linear growth like population vs. time.

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 let's 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 let's 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...

You can do this for time, or day of week, or week of month, or day of month, or season, or anything.

-
Helpful (+1). This is one application where graphs being square not oblong really is important. I don't know your software but I imagine you can set aspect ratio to 1, away from the default. – Nick Cox Nov 19 '15 at 9:12

Assuming day of week (dow) goes from [0, 6], instead of projecting data onto a circle another option is to use:

dist = min(abs(dow_diff), 7 - abs(dow_diff))


To understand why, consider the dow as a clock

  6  0
5      1
4      2
3


diff between 6 and 1 could be 6 - 1 = 5 (going clockwise from 1 to 6) or 7 - (6 - 1) = 2. Taking min of both options should do the trick.

In general you can use: min(abs(diff), range - abs(diff))

-

I have successfully encoded Days of the week (and Months of the year) as tuple of (cos,sin) as whuber highlighted in his comment. Than used Euclidean distance.

This is an example of code in r:

circularVariable = function(n, r = 4){
#Transform a circular variable (e.g. Month so the year or day of the week) into two new variables (tuple).
#n = upper limit of the sequence. E.g. for days of the week this is 7.
#r =  number of digits to round generated variables.
#Return
#
coord = function(y){
angle = ((2*pi)/n) *y
cs = round(cos(angle),r)
s = round(sin(angle),r)
c(cs,s)
}
do.call("rbind", lapply((0:(n-1)), coord))
}


Euclidean distance between 0 and 6 is equal to 0 and 1.

-