A Feature-based Sampling Method to Detect Anomalous Patterns in High Dimensional Datasets
Minh Quoc Nguyen, Leo Mark, Edward R. Omiecinski · SMARTech Repository (Georgia Institute of Technology) · 2008
We introduce a feature-based sampling method to detect anomalous patterns. By recognizing that an observation is considered normal because there are many observations similar to it, we formally define the problem of anomalous pattern detection. The properties of normal and anomalous patterns allow us to devise a generic framework using the sampling method to quickly prune the normal observations. Observations that can not form significant patterns are anomalous. Rules that are learned from the dataset are used to construct the patterns for which we compute a score function to measure the interestingness of the anomalous patterns. Experiments using the KDD Cup 99 dataset show that our approach can discover most of the attack patterns. Those attacks are in the top set of anomalous patterns and have a higher score than the patterns of normal connections. The experiments also show that the algorithm can run in near linear time.