Abstract
This paper introduces Coupled Biased Random Walks (CBRW), a novel unsupervised outlier detection method designed for categorical data. Traditional pattern-based methods often fail in complex scenarios characterized by diversified frequency distributions and high noise. CBRW addresses these challenges by modeling feature value level couplings—both intra-feature and inter-feature—using biased random walks. This approach allows for effective outlier scoring that can either directly identify anomalies or serve as a robust feature selection mechanism. Extensive experiments demonstrate that CBRW significantly outperforms state-of-the-art methods in accuracy while offering superior computational efficiency.
Introduction
Anomaly detection in categorical data (e.g., "Gender," "Job Type") is inherently difficult because standard distance metrics for numerical data do not apply. Most existing techniques rely on pattern-based detection, searching for rare combinations of values. However, real-world categorical data is often "complex," featuring inconsistent frequency distributions and noisy attributes that mislead traditional detectors. CBRW is proposed to overcome these limitations by shifting the focus to low-level value interactions.
The Challenge of Complex Categorical Data
The authors identify two primary hurdles in categorical outlier detection:
- Diversified Frequency Distributions: The semantic meaning of "rarity" varies across features. A rare value in one attribute might be normal, while in another, it indicates an anomaly. Simple frequency counts fail to capture this nuance.
- Noisy Features: Many datasets contain irrelevant features where normal objects exhibit random behavior, causing pattern-based methods to generate high false-positive rates.
- Computational Complexity: Searching for all possible feature combinations is often exponentially expensive, making traditional methods impractical for high-dimensional "big data."
Methodology: Coupled Biased Random Walks (CBRW)
CBRW models the "outlierness" of data objects by analyzing how feature values interact.
Coupling Mechanisms
- Intra-feature Couplings: CBRW calculates an outlier score for a value based on its deviation from the feature's mode (most frequent value). This standardizes the measure of rarity across different attributes.
- Inter-feature Couplings: The method constructs a "value-value" graph where nodes represent individual feature values. Edges represent conditional probabilities of co-occurrence between these values.
Biased Random Walks
To determine final outlier scores, the algorithm performs a random walk on this graph. The walk is biased, meaning the transition probabilities are weighted toward values that already exhibit high intra-feature outlierness. The stationary distribution of this walk provides the final outlier scores for each feature value.
Applications
- CBRW_OD (Outlier Detection): Directly sums the scores of an object's feature values to determine its overall outlierness.
- CBRW_FS (Feature Selection): Uses value scores to identify and prune noisy features, enhancing the performance of other outlier detection algorithms.
Experimental Evaluation
The researchers evaluated CBRW against state-of-the-art methods (e.g., FPOF, COMP, MarP) using 11 real-world datasets, including KDDCUP99, Census, and aPascal. These datasets were selected to represent varying levels of noise and complexity.
Key Results
Accuracy and Noise Robustness
CBRW outperformed competitors on 7 out of 11 datasets, showing an average AUC improvement of 12% to 19% on high-noise data. When used for feature selection (CBRW_FS), it significantly boosted the performance of other detectors by removing "junk" features.
Scalability
One of CBRW's most significant advantages is its efficiency. Its complexity is nearly linear relative to both the number of data objects and the number of features. In scalability tests, CBRW was 2 to 5 orders of magnitude faster than pattern-based competitors.
Conclusion
CBRW provides a scalable and accurate solution for outlier detection in complex categorical data. By modeling low-level feature value couplings, it effectively handles noise and varied frequency distributions that cripple traditional pattern-based approaches. While it excels at identifying anomalies driven by pairwise interactions, future work may explore incorporating higher-order dependencies to capture even more subtle behavioral patterns.
Summary updated