Breaking the Deadlock: Simultaneously Discovering Attribute Matching and Cluster Matching with Multi-Objective Metaheuristics

Haishan Liu, Dejing Dou, Hao Wang

Abstract

This paper addresses the "circular causality" problem in data integration, where attribute matching and cluster matching are mutually dependent. We propose a multi-objective metaheuristic approach, specifically Multi-Objective Simulated Annealing (MOSA), to simultaneously discover optimal mappings across heterogeneous datasets. Evaluated on synthetic and real-world neuroscience datasets, our method demonstrates superior performance over traditional single-objective baselines by identifying a Pareto front of high-quality solutions that balance attribute and cluster alignment.

Introduction: The Deadlock of Data Integration

In scientific research, integrating datasets from different laboratories is often hindered by heterogeneous naming conventions and varying observed patterns. This creates a "deadlock": to match attributes (features) accurately, one needs a segmented view of the data provided by clusters. Conversely, to define clusters across datasets, one must know which attributes correspond to each other. Traditional integration methods typically assume one of these problems is already solved, which is rarely the case in complex scientific domains like neuroscience.

Interdependence of attribute matching (x, y) and cluster matching (c, c').

Methodology

The core innovation of this work is treating attribute and cluster matching as a Multi-Objective Optimization Problem (MOOP). Instead of seeking a single "perfect" answer, the system searches for a Pareto front—a set of solutions where the attribute match cannot be improved without worsening the cluster match.

Key Techniques

  • Data Representation: Attributes are represented by "segmented statistical characterization" (a vector of mean values for that attribute across different clusters). Clusters are represented by "density profiles," which describe how many data points fall into specific discretized bins for each attribute.
  • Optimization Algorithms: The study primarily utilizes Multi-Objective Simulated Annealing (MOSA). This metaheuristic explores the solution space by starting with random guesses and gradually becoming more selective as the system "cools."
  • The Hungarian Method: Within each iteration of the metaheuristic, the Hungarian Method—a classic $O(n^3)$ algorithm—is used to solve the specific assignment problem (the actual mapping of attributes) efficiently.

Results and Discussion

The proposed method was evaluated against synthetic datasets, neuroscience Event-Related Potentials (ERP) data, and the UCI Wine Quality dataset.

A Pareto front showing the trade-off between the attribute matching objective ($f_a$) and the cluster matching objective ($f_c$).

Performance Highlights

  • Synthetic Success: The MOSA approach achieved 100% accuracy on synthetic data designed to mislead standard global-statistic matchers by having identical global means but different internal distributions.
  • Neuroscience Benchmarks: In complex ERP datasets involving different subjects and data decomposition methods (sICA and tPCA), the method significantly outperformed the "Whole-attribute Statistics" (WS) baseline. It achieved perfect matches in several test cases, proving its utility in real-world scientific data integration.
  • MOSA vs. MOGA: While both metaheuristics performed well, MOSA was generally faster and more robust than the Multi-Objective Genetic Algorithm (MOGA) approach.

Limitations and Future Work

While effective, the $O(n^3)$ complexity of the Hungarian Method may limit scalability for massive datasets, such as those found in genomics. Future work will explore parallelism and approximation techniques to handle these cases. Additionally, the current model assumes a bijective (one-to-one) mapping; future iterations may relax this to support partial or many-to-many matches, reflecting the reality where one laboratory may measure features that another ignores.

Summary updated

Abstract

In this paper, we present a data mining approach to address challenges in the matching of heterogeneous datasets. In particular, we propose solutions to two problems that arise in integrating information from different results of scientific research. The first problem, attribute matching, involves discovery of correspondences among distinct numeric features (attributes) that are used to characterize datasets that have been collected and analyzed in different research labs. The second problem, cluster matching, involves discovery of matchings between patterns (clusters) across datasets. We treat both of these problems together as a multi-objective optimization problem. A multi-objective simulated annealing algorithm is described to find the optimal solution and compared with the genetic algorithm. The utility of this approach is demonstrated in a series of experiments using synthetic and realistic datasets that are designed to simulate heterogeneous data from different sources.
BibTeX
@article{liu2012breaking,
  author = {Haishan Liu and Dejing Dou and Hao Wang},
  title = {{Breaking the Deadlock: Simultaneously Discovering Attribute Matching and Cluster Matching with Multi-Objective Metaheuristics}},
  journal = {J. Data Semant.},
  year = {2012},
  doi = {10.1007/s13740-012-0010-0},
}
Figure