Outlier Detection in Complex Categorical Data by Modeling the Feature Value Couplings

Guansong Pang, Longbing Cao, Ling Chen

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:

  1. 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.
  2. Noisy Features: Many datasets contain irrelevant features where normal objects exhibit random behavior, causing pattern-based methods to generate high false-positive rates.
  3. 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.

AUC performance on Census and aPascal datasets across different numbers of selected 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.

Scalability of CBRW compared to other methods relative to data size and number of features.

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

Abstract

This paper introduces a novel unsupervised outlier detection method, namely Coupled Biased Random Walks (CBRW), for identifying outliers in categorical data with diversified frequency distributions and many noisy features. Existing pattern-based outlier detection methods are ineffective in handling such complex scenarios, as they misfit such data. CBRW estimates outlier scores of feature values by modelling feature value level couplings, which carry intrinsic data characteristics, via biased random walks to handle this complex data. The outlier scores of feature values can either measure the outlierness of an object or facilitate the existing methods as a feature weighting and selection indicator. Substantial experiments show that CBRW can not only detect outliers in complex data significantly better than the state-of-the-art methods, but also greatly improve the performance of existing methods on data sets with many noisy features.
BibTeX
@inproceedings{pang2016outlier,
  author = {Guansong Pang and Longbing Cao and Ling Chen},
  title = {{Outlier Detection in Complex Categorical Data by Modeling the Feature Value Couplings}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=HkVz-7MubB},
}
Figure