A Metaheuristic-Based Subspace Search Approach for Outlier Detection in High-Dimensional Data Streams

The continuous progress in technology is leading to the widespread existence of data streams with high dimensions. Identifying outliers in this particular scenario presents a notably difficult task. The unique characteristics of data streams, combined with the effect of the dimensionality curse in high-dimensional space, create constrained mining requirements, and a current challenge is to simultaneously address them. A common approach to handle high dimensionality is to identify outliers only within subspaces of space of features that contain interesting knowledge, where outliers are typically found. However, in the realm of data streams, this area of study has not been well explored. In this article, our objective is to discover interesting subspaces for outlier detection while accommodating the needs of data streams, including limited time and memory, and addressing the adaptation to data changes (concept drift), as well as providing better performance than the closely related approaches. In this context, we used a metaheuristic-based approach (Adapted Binary Gravitational Search algorithm) to discover high-contrast subspaces comprised of independent features, within which the outlier detection will be performed. To deal with data streams, we adopted the sliding window structure together with a modified version of the N-Dimensional Kolmogorov–Smirnov WindoWin (NDKSWIN) concept drift detector. We conducted experiments on both synthetic and real-world data and the results demonstrated its effectiveness and superiority over the competitors.