3
$\begingroup$

After conducting a cluster analysis using K-means, I have new data coming online that I need to detect anomalies with. Anomalies are assumed to not be within the clusters.

So, how is one to define "inside a cluster" in K-means?

$\endgroup$
  • $\begingroup$ Although it is a bit offtopic, but it looks like OP is trying to solve outlier detection problem. I would suggest Isolation Trees, the method is pretty mature and is used in production systems. $\endgroup$ – Vladislavs Dovgalecs Aug 27 '15 at 15:54
3
$\begingroup$

Strictly speaking, the k-means algorithm does not have a definition for "inside the cluster" and is therefore not a great candidate for anomaly detection. In k-means, every point is assigned to one of k clusters and then a new cluster centroid is calculated.

But as previous uses have pointed out, you could construct some sort of ad-hoc system where you process a set of data and then define new data as anomalous when its extends beyond 2 standard deviations of the centroid location. DON'T DO THIS!

K-Means will not work well for this ad-hoc method. If k is poorly chosen, then the distribution within a cluster will not be normally distributed. You very, very frequently see natural distributions of points which are split between two clusters. For instance, take a look at the ad-hoc segmentation of points in this location data for a cell phone user's location over a month: enter image description here

I suggest you use another clustering method. The first option that comes to mind is DBSCAN. This allows one to set a threshold for noise and the cluster numbers are not set a-priori. DBSCAN is therefor much more likely to return normal distributions within a cluster. Here is a single DBSCAN cluster of the same data: enter image description here

Finally, I'll point out that the method you are proposing is not as good as other novelty and anomaly detection methods. You should consider doing novelty detection using a single (or possibly even multiple) class support vector machine (SVM) with a nonlinear kernel. The nonlinear kernel will allow you to recover multiple "clusters" while the SVM will do much better at predicting which points are inside the class.

|improve this answer|||||
$\endgroup$
1
$\begingroup$

It's inside a cluster if it is part of the partition of the respective Voronoi diagram. This is a visual explanation that translates to "a point is inside cluster A if it is closest to the centroid of A (compared to all other centroids)."

If your clusters don't have infinite boundaries and outliers shouldn't be in any cluster at all, you might need to refine your approach to something else than k-means that detects outliers.

|improve this answer|||||
$\endgroup$
0
$\begingroup$

With the Voronoi cells that runDosrun brings, it is true that they are likely unbounded, so your new data that is "outside of the cluster" isn't actually outside the cluster. You should probably look at a different clustering algorithm if that is indeed what you are looking to do.

If you are intent on using k-means, you could attempt to classify anomalous data into its own cluster.

There are libraries out there that you can use to constrain the boundaries of the k-means during cluster analysis to the initial domain. Without knowing what environment you are trying to do this in or what the context of the data is, it would be really difficult to define "inside a cluster" with out you specifically choosing certain boundaries.

|improve this answer|||||
$\endgroup$
0
$\begingroup$

I'm going to agree with AN6U5 in general. However, in practice what I've done in the past is used k-means with cross validation and and Silhouetting to find a 'good' clustering of historical data.

What I then did was take the clusters and calculated their covariance matrix so I could use the Mahalanobis distance. This allows me to take into account the actual shape of the distribution along each dimension in determining whether a point lies to far outside my previous examples. Since the Mahalanobis distance is in standard deviations, if its say 3 sigma outside each cluster its usually flagged for further study.

I've been able to get away with this since I know the general process for whats generating my data from testing and I have a rather large amount of data for known operating conditions, so I have pretty good faith in my historical data clusters.

|improve this answer|||||
$\endgroup$

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.