# Anomaly detection using k-means clustering in Python

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.

• 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/… Jul 29, 2019 at 22:14
• I'll look into it, thank you! Jul 30, 2019 at 8:26
• 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 Jul 31, 2019 at 16:27