A Framework for Outlier Description Using Constraint Programming

Chia-Tung Kuo, Ian DavidsonAAAI 2016 · DOI

Introduction

While outlier detection—identifying anomalous data points—is a well-studied field, the task of outlier description remains a significant challenge. In critical domains such as medical diagnosis or fraud detection, knowing that a case is an outlier is often insufficient; experts require an explanation of why it is anomalous. This paper proposes a flexible framework based on Constraint Programming (CP) to automatically discover the feature subspaces that best distinguish known outliers from normal data.

The Subspace Outlier Description Problem

The authors define outlier description as finding a concise, human-readable set of features (a subspace) where outliers are clearly separated from the majority. Unlike "black box" models like Neural Networks, this approach prioritizes interpretability.

The core methodology utilizes Constraint Programming (CP), a declarative paradigm where the desired properties of a solution are defined as constraints. The framework seeks a subspace where:

  1. Normal points are dense: Most normal instances have many neighbors within a specified radius $r$.
  2. Outliers are isolated: Outliers have few or no neighbors within that same radius.

Three Formulations for Diverse Scenarios

The framework is adaptable to various real-world complexities through three distinct formulations:

  • Single Subspace: Finds the optimal feature set maximizing the "density gap" between normal and outlier groups.
  • Multiple Subspaces: Addresses heterogeneous outliers by finding a disjunction of subspaces (e.g., explaining different "types" of fraud).
  • Human-in-the-Loop: Accounts for potential noise in the "normal" dataset by allowing the model to flag suspected hidden outliers for expert review.

Experimental Validation

The framework was tested on two diverse datasets: fMRI medical imaging and the 20 Newsgroups text corpus.

fMRI Medical Imaging

In a study of 61 elderly subjects (Healthy, Mildly Cognitively Impaired, and Demented), the goal was to identify which correlations between brain regions explained the "Demented" status. The CP model identified a subspace of 17 feature pairings (out of 351 possible) that perfectly separated the groups: every healthy subject had at least three neighbors in this subspace, while every demented subject had zero.

Anatomical regions identified in the fMRI outlier description task. (a) Reference map of brain regions. (b) The top 3 regions most frequently appearing in the selected outlier-describing pairs.

Text Classification

Using the 20 Newsgroups dataset, the authors designated "Hardware" as the normal class and "Baseball" and "Religion" as outliers. The model successfully isolated these outliers using a minimal set of topical words (e.g., "season," "bible"), demonstrating its ability to find precise global explanations for group-level anomalies.

Key Insights and Limitations

The primary advantage of this CP-based approach is its expressive power. By using logical operators and discrete variables, it can handle complex feature selection tasks that are difficult for standard mathematical programming. Furthermore, it provides "global" explanations for entire groups of outliers, rather than the "local" point-by-point explanations offered by methods like LIME.

However, the framework faces scalability challenges. The combinatorial nature of the optimization leads to a quadratic growth in auxiliary variables ($O(n^2)$) relative to the number of data instances. Future research will focus on improving solver efficiency and developing specialized propagators to handle neighborhood constraints more effectively.

Conclusion

By shifting the focus from detection to description, this framework provides a vital tool for domain experts who need interpretable justifications for anomalies. The use of Constraint Programming offers the flexibility required to incorporate domain knowledge and handle the nuances of real-world data.

Summary updated

BibTeX
@inproceedings{kuo2016framework,
  author = {Chia-Tung Kuo and Ian Davidson},
  title = {{A Framework for Outlier Description Using Constraint Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2016},
  doi = {10.1609/aaai.v30i1.10174},
}
Figure