# Clustering based anomaly detection

I'm trying to implement anomaly detection based on clustering. I'm hopping for confirmation of my approach, and I'm exposing my idea, being aware that I could have miss something in my analysis, so any suggestions would also be very appreciated. I'm a beginner in this area, so any help would be great.

I must also add that the data is in the time series form, and that there is a number of parameters considered.

My approach is next:

Let's say that there are 3 parameters, a, b and c. Since parameters are in time series form, I'm using sliding window, lets assume that size of the window is 4.

My representation of point is

[a1, a2, a3, a4, b1, b2, b3, b4, c1, c2, c3, c4]

[a2, a3, a4, a5, b2, b3, b4, b5, c2, c3, c4, c5]

And so on.

Then I'm using clustering (K means clustering, where I use some kind of automatized elbow method to determine the number of clusters), which gives me centroids that represent what normal signals (normal values of parameters in a window) look like.

Based on that centroids and the distance of points to its nearest centroid (concretely certain number of points farthest from centroid) when a new measurement arrives, I assign it to nearest centroid and its distance to centroid, I determine weather a signal is anomalous.

Is my approach sound, if not, what should I consider to make it work.

I have tried it on data that I have synthesized and got "good" results, by testing on injected anomalies. But I'm still not sure in this approach, because of my lack of experience.

Any comment would be great.

Thanks

This has, of course, been tried before.

In fact, there is an implementation in ELKI, based on k-means.

The problem is, this isn't as easy as it sounds.

• k-means itself is sensitive to outliers.
• the points inbetween clusters aren't necessarily outliers, but may have a high score
• the points away from all clusters can be more easily found by computing the distance from the data set center.

So in the end, it simply doesn't work.

DBSCAN is a clustering algorithm that has a concept of "noise". Which are primitive outliers - objects in regions of low density.

There are many more - more advanced - outlier detection methods available in ELKI; which worked much better for me than the k-means based thing.

• Ok, thank your for sharing your experience and thanks for recommendation of what to use. Can you tell me your opinion about the fact that time series are considered? How does that reflect to the concept that I have given? Commented Oct 9, 2014 at 7:56
• I should also mention that I'm using Streaming K Means as a variant, hopping to get a bit better clusters and avoid - -means itself is sensitive to outliers - point you mentioned, since it is comprised of K-means++ and Ball K Means... Commented Oct 9, 2014 at 8:18
• K-means is using squared Euclidean distance. If you have time series, you will want to use e.g. DTW - which won't work with k-means. I'm not at all convinced by streaming k-means, because k is a critical parameter for this algorithm, too. Commented Oct 9, 2014 at 14:06