A fast anomaly network traffic detection method based on the constrained k-nearest neighbor

The k-nearest neighbor algorithm has been widely used in network anomaly detection works, but its query efficiency decreases significantly when the number of samples and feature dimensions increase. To meet the demand for real-time detection, an accurate and timely anomaly detection solution is particularly important. This paper proposes a fast anomaly traffic detection method based on the constrained k-nearest neighbor (CKNN) algorithm. The method uses equilibrium modified k-means and randomized incremental method to optimize the ball tree construction scheme. Specifically, randomized incremental method is used to solve the minimum coverage ball, which optimizes the selection process of the centeroid and radius while reducing the depth of the ball tree. And the equilibrium modified k-means method replaces the original k-center principle used in the division of subtrees, which solves the problem of unbalanced search binary tree division. Meanwhile, by reducing the required number of backtracking to search the K nearest neighbors, which reduces the classification time overhead of the algorithm. We validate the effectiveness of the method on several benchmark datasets. The experimental results show that the CKNN maintains a higher query rate without loss of detection accuracy when dealing with high-dimensional, massive sample data compared with the traditional KNN algorithm. And with the growth ratio of up to 99.68% for some samples, our method also exhibits higher detection accuracy and less time consumption compared with other machine learning algorithms.