Exploration of Heterogeneous Data Using Robust Similarity

Mahsa Mirzargar, Ross T. Whitaker, Robert M. KirbyarXiv 2017 · arXiv

Introduction

Modern data analysis frequently encounters "heterogeneous" datasets—collections of information that mix numerical values, categorical labels, and complex geometric shapes like curves or streamlines. Traditional statistical tools often struggle with this diversity, typically requiring data to be forced into a single numerical format or reduced in dimensionality. Such transformations can obscure subtle structures, such as multiple distinct clusters (modes) or rare anomalies (outliers). This paper introduces a generic, robust similarity measure based on Band Inclusion Signatures, providing a universal language for data similarity that preserves these critical structures without requiring prior knowledge of the data's distribution.

Methodology: Band Inclusion Signatures

The core innovation of this framework is the shift from distance-based metrics to containment-based signatures. The process follows a simple intuition:

  1. Band Inclusion: In a one-dimensional space, a "band" is defined as the line segment between two randomly selected points. We determine if a third point falls within this segment. This concept generalizes to higher dimensions and complex data types (e.g., functions or sets) by defining what it means for one object to be "between" others.
  2. The Signature: By repeating this process across numerous random subsets of the data, each point is assigned a binary string—a signature. A bit is set to 1 if the point falls within the randomly generated band and 0 otherwise.
  3. Robust Similarity: Points that are spatially or structurally "near" each other will consistently fall into the same random bands. Similarity is then calculated using the Hamming distance between these binary signatures.
Figure 1: Illustration of band inclusion signatures for a bimodal distribution. The matrix (b) represents the signature where rows are data points and columns are bands defined by pairs of points.

The Resolution Knob (τ)

A key feature of this method is the introduction of a threshold parameter, τ, which acts as a "resolution knob." By limiting the size of the bands used to generate the signature, researchers can tune the analysis to different scales:

  • Large τ (Global): Large bands capture global trends and help identify the "center" or median of the entire dataset.
  • Small τ (Local): Small bands focus on local details, making the tool highly effective at identifying multiple clusters (multimodality) and outliers.
Figure 2: The effect of reducing the band size threshold (τ). The resulting signature matrix is sparser, focusing on local similarities and revealing finer structural details.

Applications and Results

The authors validated this approach on two distinct datasets:

  • Mushroom Dataset: Using 23 categorical and numerical attributes, the tool successfully clustered mushrooms by "ring type" and "edibility." Unlike standard Multidimensional Scaling (MDS), which is sensitive to arbitrary thresholds, this method provided clear separation based on inherent data structures.
  • Hurricane Sandy Ensemble: Analyzing 21 predicted hurricane tracks (multivariate curves), the method identified the "global median" track and flagged the "left-turn" tracks as outliers. These outliers eventually proved to be the most accurate predictions for Hurricane Sandy’s actual path.

Conclusion

The Band Inclusion framework offers a "Swiss Army knife" for data scientists dealing with complex, mixed-type data. By focusing on containment rather than traditional distance, it provides a robust, parallelizable, and highly interpretable way to explore hidden patterns in messy, real-world datasets. Future work aims to extend this model to handle missing data and improve the visualization of high-density similarity graphs.

Summary updated

BibTeX
@misc{mirzargar2017exploration,
  author = {Mahsa Mirzargar and Ross T. Whitaker and Robert M. Kirby},
  title = {{Exploration of Heterogeneous Data Using Robust Similarity}},
  year = {2017},
  eprint = {1710.02862},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1710.02862},
}
Figure