3
$\begingroup$

I'm working on an anomaly detection task in Python.
Datasets regard a collection of time series coming from a sensor, so data are timestamps and the relative values.

In order to find anomalies, I'm using the k-means clustering algorithm. I've split data set into train and test, and the test part is split itself in days.
The training is done using the train part of the data set and the prediction is done day by day.
I'm going to do like this because this will be the usage in production.

To distinguish if a record is anomalous or not, I calculate the distance between each point and its nearest centroid.

_clusters = self.km.predict(day)
centroids = self.km.cluster_centers_

# calculate the distance between each record and each centroid.
# the result is a matrix which has as column the id of centroid and rows are records.
# so each value is the distance of between record and centroid
distance_matrix = spatial.distance_matrix(day, centroids)

# save in nearest_distances, for each record, distance between each point and its nearest centroid
nearest_distances = []
for distance_per_cluster in distance_matrix:
nearest_distances.append(min(distance_per_cluster))

nearest_distances = pd.Series(nearest_distances)

Then, using a threshold, I find anomalies

self.outliers_fraction = 0.01
number_of_outliers = int(self.outliers_fraction * len(nearest_distances))
threshold = nearest_distances.nlargest(number_of_outliers).min()

day_df['anomaly'] = (nearest_distances >= threshold).astype(int)

This code works, but I have a high number of false positive.
Data sets are not labeled, but analyzing results it's quite obvious.
This because the threshold is set using outliers_fraction that equals to 0.01, but it is completely arbitrary.

Since I cannot know in advance which is the "correct" threshold, I would like to ask you if there is a better way to find anomalies, in this contest, using k-means clustering algorithm.

$\endgroup$
3
  • 1
    $\begingroup$ I recently had to do an exercise that involved clustering time series. All the literature I could find suggested that KMeans was an inappropriate algorithm for doing so, and that I should rely on Dynamic Time Warping instead. You could try that and see if it's more useful for you? Fair warning; it's a pretty computationally heavy (I.E. slow as hell) algorithm. You can find a python implementation here: github.com/alexminnaar/… $\endgroup$
    – Dan Scally
    Jul 29, 2019 at 22:14
  • $\begingroup$ I'll look into it, thank you! $\endgroup$
    – Giordano
    Jul 30, 2019 at 8:26
  • $\begingroup$ You can also use an autoencoder to do this and it might (actually, it will) be much faster than DTW... PCA might be a solution as well... It all depends on your data, can you provide a plot with time as x-axis and sensor measurements as y-axis? Also, you might be interested in reading this: scikit-learn.org/stable/modules/outlier_detection.html $\endgroup$
    – qmeeus
    Jul 31, 2019 at 16:27

1 Answer 1

1
$\begingroup$

One approach you could try is to use the silhouette score to evaluate the quality of your clusters and determine the optimal number of clusters to use for your data. The silhouette score is a measure of how well each data point is assigned to its closest cluster. You can then use the silhouette score to determine the optimal number of clusters for your data, and use this number of clusters when performing k-means clustering on your data.

Once you have determined the optimal number of clusters, you can use the distances between data points and their closest centroids to identify anomalies. You could use a method such as the interquartile range (IQR) to determine the threshold for identifying anomalies. The IQR is the difference between the 75th and 25th percentiles of the distances between data points and their closest centroids. You can then use this threshold to identify data points that are considered anomalies.

Another approach you could try is to use a density-based clustering algorithm, such as DBSCAN, to identify anomalies in your data. DBSCAN is a clustering algorithm that identifies clusters based on the density of data points in a given area. Data points that do not belong to any cluster, or that belong to a cluster with low density, are considered anomalies.

Overall, it's worth experimenting with different approaches and evaluating the results to determine the best method for identifying anomalies in your data.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.