How to cluster temporal pattern of users with k means

Question

I have data relating to the movement of travelers through a toll road based on a smart card. I have the ID of the individual and a datetime stamp for each time they pass through the toll (in either direction) for a period of 6 months. My aim is to cluster these individuals by their travel pattern, e.g. I imagine many will fit the traditional commuter pattern for 9 - 5 jobs, but I hope to discover if other clusters exist, e.g. night-shift workers, those active in the day and choosing to avoid peak-hours etc.. I'm not concerned with direction of travel at this stage.

I thought I would try a k means approach (in R), but I'm unsure if I am preparing the data correctly? I have split the number of trips by day of week and hour of day (so I have 7*24 = 168 categories for each row/customer).

Mon01,Mon02,Mon03...Sun22,Sun23
0,3,1...0,7
0,0,4...0,2

I also realize that there are well documented limitations to k means, so I'm considering testing other techniques. Would this data lend itself better to another cluster analysis method?

Answer 1

This could be done nicely if you had numerical data for your tolls (categorical data requires different algorithms - Gower distance etc.), for ex. if you had coordinates for each toll. Then you could use k-means to find clusters with paths that are very similar.

Otherwise you may have to delve into graph theory, they have some nice algorithms there, where points on a graph are tolls and the arcs are weights (time).

Answer 2

First of all, K means (including extended family) is a very robust choice to implement and handles wide range of data types in a clustering problem.

You seem to be on the right track. I would recommend to limit your use of categorical features and to start with a reduced dimension data set. It should be noted that a good feature set needs to be engineered in order to guide your ML algorithm better specially for high dimensional data. For eg, a good initial feature set would look like this after proper aggregation from raw data:

1. Number of trips in a category (7 day x 2 half days = 14 features):

Non-negative (numeric)

2. Travels on Weekend or not (1 feature):

0,1 (binary) 

Before the clustering part, you need to check the variation in data for identified features. For eg, check the variation of trips in a day for all observations, that will help you understand if you need more features for time of a day. When you figure out this information then you can implement k means and tweak different parameters like number of clusters and distance metrics etc.