My data features look like this:

 Date and Hour -- Lane-Number -- Volume of traffic -- Speed

 (This is one month of data (30 days x 24 hours of rows))

And in total I have data extending to three years each year having two months.

I am trying to apply K-means to find outliers. What I am trying to figure out is on what basis do I cluster the data.

What I came up with was applying K-means for just one day. (So, X-axis would be 00:00 - 23:00 and Y-axis would be the traffic volume.)

But Is it advised to make 30 graphs for one month of data? Considering the whole data I would end up with a lot of graphs.

If not, is there another way to do it?

  • $\begingroup$ how about adding in some features for time, like eg sin(dayofyear/365*pi), cos(dayofyear/365*pi), etc? $\endgroup$ – Hugh Perkins Oct 9 '17 at 12:49
  • $\begingroup$ @HughPerkins Could you please explain how exactly will adding those extra features be helpful? Thanks in advance. $\endgroup$ – RPT Oct 9 '17 at 14:14
  • $\begingroup$ then you only need a single graph, over all data, and these features will handle cyclical trends over time $\endgroup$ – Hugh Perkins Oct 9 '17 at 14:18

I know of three possible problem settings:
1. Detecting contextual anomalies in the time series - the anomalies are individual instances of the time series which are anomalous in a specific context, but not otherwise. For example: low temperature in the winter is cool but in the summer is anomalous.
2. Detecting anomalous sub sequence within a given time series(discord) - anomalous sub sequence with respect to a given long sequence.
3. Detecting anomalous time series with respect to a time series data base - when we have a lot of normal time series and we wish to compare one time series to them in order to decide if its normal.

If you wish to use K-Means, I can think of these possible detection anomaly methods for each setting:
* Define each series as 24 points time series.
* Construct a 24*3 representing vector per each series.
* Cluster all series.
* Per each cluster, cluster the instance(vectors of length 3).
* Look for outlying clusters, instances who are far from their respective cluster centroid.
* Decide on discord length(number of consecutive instances), say n.
* Construct n*3 representing vector per each subsequence(window).
* Cluster these n*3 vector per each series separably. * Compare different cluster/instances distance to cluster, between series and decide on a anomaly heuristic(if distance > X, if cluster inner variance is Y, etc..). 3.
* Define each series as 24 points time series.
* Construct a 24*3 representing vector per each series.
* Cluster all series.
* Identify series which are anomalous, based on their distance to cluster, etc..

Depends on the metric you use for distance computing you might need to add normalization/scaling steps.

By the way, there are other ways detecting anomalies in a time series. Using prediction models, Hidden Markov models and FSA.

In continuation to comment - elaborating on method 1: Say we have fast-driving days and slow-driving days(low traffic/heavy traffic days) then an hour of driving at 10MPH has different meaning.
In fast days it might be an anomaly and in slow days it wont.

First we split our driving days into relevant clusters. Then at each cluster(sets the driving context) we look if a specific instance is an anomaly.

Goal - identifying rows where driving instance diverged from normal.
Driving instance is described by volume of traffic, line number and speed(possible hour of the day).
Meaning, all driving instances "live" in 3(4) dimensional space.
X - 0:1, Y - [1:max(line_number], Z - [0: max(speed)].
Under the assumption that each driving instance is depended on previous driving instance(time series structure) we cant "just" cluster all the instances.
If we assume that one day(24 hours) driving instances are independent from next day driving instance(change of driver/car/long break/etc..) we can cluster each such bulk of 24 hours instances(described as the 24*3 vector).
Using this clustering we can identify similar driving days.
Under the assumption that in similar driving days, differences between driving instances describe real attributes of the in-day driving events, we can re cluster and look for instances with diverged attributes.

  • $\begingroup$ Thanks for your reply. I think I am looking to implement something like your method-1. But I guess I am not fully understanding what you said. Why construct a 24 * 3 vector? Can you please, explain a bit more in detail? Thanks a lot. $\endgroup$ – RPT Oct 9 '17 at 13:35
  • $\begingroup$ Im using too many words here :) $\endgroup$ – yoav_aaa Oct 9 '17 at 14:57
  • $\begingroup$ Is there a way to chat or something then? $\endgroup$ – RPT Oct 9 '17 at 15:01
  • $\begingroup$ Thanks very much for the detailed explanation. But my concern here is, is it a good idea to perform outlier detection on my data for just one day? As in take each day (24 hour time series) apply K means. Do the same for all instances. Does that make sense? Or say, you take the average of all the traffic volume for each day and find find out which day had too much traffic in the month. (X : 0 - 31 days; Y : traffic volume). Does that seem like a thing to do? I'm sorry for the stupid questions btw, I'm completely new to this. Thanks in advance :) $\endgroup$ – RPT Oct 9 '17 at 17:17
  • $\begingroup$ Not stupid at all - IT all depends on what do you define as an Anomaly in the real world? What does the the data depicts? single driver behavior? A fleet? - What would a real life occasion be considered an anomaly? $\endgroup$ – yoav_aaa Oct 10 '17 at 7:47

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.