Batch discovery of recurring rare classes toward identifying anomalous samples

Murat Dundar, Halid Ziya Yerebakan, Bartek RajwaKDD 2014 · DOI

In fields ranging from clinical diagnostics to astronomy, researchers often search for "anomalous" samples—those containing extremely rare, recurring classes of data that do not appear in "normal" samples. Identifying these "needles in a haystack" is exceptionally difficult due to the inherent scarcity of the target classes and the "random effects" (inter-sample variability) that arise from different experimental conditions. The authors introduce ASPIRE (Anomalous Sample Phenotype Identification with Random Effects), a non-parametric Bayesian clustering algorithm designed to overcome these hurdles by modeling classes as flexible mixtures and accounting for sample-specific shifts.

The Challenge of Rare Class Discovery

Traditional clustering methods often struggle with two primary issues in multi-sample datasets:

  1. Rareness: Target classes may represent less than 1% of the total data points.
  2. Random Effects: Data collected across different samples (e.g., blood samples from 15 different labs) often exhibits systematic shifts due to equipment calibration, reagents, or biological variability.

When data is pooled, inter-sample noise can wash out rare classes. Conversely, clustering samples individually makes it nearly impossible to match rare clusters across the dataset because they contain so few points. ASPIRE addresses this by performing clustering and class-matching simultaneously within a unified framework.

The ASPIRE Framework

ASPIRE builds upon the Hierarchical Dirichlet Process (HDP) but introduces several key innovations to improve flexibility and robustness:

  • Classes as Mixtures: Unlike previous models that assume a class follows a single Gaussian distribution, ASPIRE models each class as a Dirichlet Process Mixture (DPM). This allows the model to capture complex, non-Gaussian shapes (such as "banana" or "donut" shapes) without over-splitting a single biological entity into multiple artificial clusters.
  • Hierarchical Sharing and Random Effects: The model uses a global prior to link DPMs across samples, creating a sharing mechanism that learns global class characteristics while allowing for "local realizations." It explicitly models random effects ($κ_1$), allowing cluster centers to shift slightly between samples.
  • Inference via Collapsed Gibbs Sampling: The authors utilize an iterative algorithm to learn the number of classes, their shapes, and point assignments simultaneously, removing the need for users to pre-specify the number of clusters.

Experimental Evaluation

The model was evaluated on two distinct datasets to prove its efficacy:

  1. Artificial Data: A 2D dataset with 20 samples containing three classes, two of which were rare (0.3% and 1%). ASPIRE achieved near-perfect F1 scores (0.90 to 1.00) and correctly identified the three classes, whereas competing models over-clustered the data into 5 to 11 classes.
  2. Flow Cytometry (FC) Data: Using the FlowCAP 2012 competition dataset (202 samples, 6-dimensional features), ASPIRE sought to identify two extremely rare cell populations. ASPIRE achieved F1 scores of 0.59 and 0.77. In comparison, the standard HDPM model, which lacks random effects modeling, failed almost entirely with scores of 0.01 and 0.02. Notably, ASPIRE's unsupervised performance was comparable to supervised Support Vector Machines (SVMs) trained on labeled data.

Discussion and Future Work

ASPIRE demonstrates that unified learning—clustering and matching across samples simultaneously—is superior for identifying rare patterns that might appear as noise in isolation. By incorporating random effects, the model remains robust to the technical noise inherent in multi-site data collection.

However, challenges remain regarding computational complexity. Gibbs sampling is computationally intensive; processing 1.9 million data points took approximately 11 hours on a standard workstation. Additionally, while ASPIRE excels at rare class detection, it may perform less effectively than supervised methods on "normal" (abundant) classes, as it attempts to partition the broad "normal" category into distinct biological phenotypes. Future work may involve semi-supervised approaches to better distinguish known normal classes from unknown anomalies.

Summary updated

BibTeX
@inproceedings{dundar2014batch,
  author = {Murat Dundar and Halid Ziya Yerebakan and Bartek Rajwa},
  title = {{Batch discovery of recurring rare classes toward identifying anomalous samples}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2014},
  doi = {10.1145/2623330.2623695},
}
Figure