Median topographic maps for biomedical data sets

Barbara Hammer, Alexander Hasenfuß, Fabrice Rossi

Abstract

Median clustering extends popular neural data analysis methods such as the self-organizing map or neural gas to general data structures given by a dissimilarity matrix only. This offers flexible and robust global data inspection methods which are particularly suited for a variety of data as occurs in biomedical domains. In this chapter, we give an overview about median clustering and its properties and extensions, with a particular focus on efficient implementations adapted to large scale data analysis.

Introduction

In the realm of biomedical data analysis, researchers frequently encounter complex data structures—such as DNA sequences, EEG signals, or protein structures—that do not naturally reside in a Euclidean vector space. Traditional clustering and visualization algorithms, like K-means or the standard Self-Organizing Map (SOM), rely on the ability to calculate arithmetic means to define cluster prototypes. When data is defined solely by a dissimilarity matrix (e.g., alignment scores or edit distances), these standard approaches fail.

This paper presents "median" adaptations of the Self-Organizing Map and Neural Gas (NG) algorithms. By restricting cluster prototypes to actual data points within the set, these methods enable the analysis of non-vectorial data while maintaining the topological preservation and interpretability required for biomedical discovery.

Methodology

Median Clustering Framework

The core innovation of Median SOM and Median Neural Gas is the restriction of the prototype set. Instead of allowing prototypes to move freely through a continuous space, the algorithm identifies the most representative data point—the "median"—for each cluster. This approach ensures that every prototype is a real-world biological entity (e.g., a specific protein sequence) rather than a "virtual average" that may not exist in nature.

To enhance the utility of these maps, the authors introduce a semi-supervised component. By incorporating a mixing parameter, $\beta$, the algorithm can utilize known class labels during the training process. This allows the topographic map to "bend" and better represent biological categories in regions where data distributions overlap.

Computational Efficiency

A significant hurdle for median clustering is its computational complexity, typically $O(N^2K)$ per epoch. To make these methods viable for large-scale biomedical datasets, two primary optimizations are introduced:

  1. Block Summing (for SOM): By exploiting the fixed lattice structure of the SOM, the authors pre-calculate distance sums, reducing the complexity to $O(N^2 + NK^2)$.
  2. Branch and Bound: Using combinatorial optimization, the algorithm can prune the search space for new prototypes. By calculating lower bounds on potential costs, the system can skip candidate prototypes that are mathematically guaranteed to be inferior to the current best candidate.

Experimental Evaluation

The researchers evaluated the median algorithms across four distinct datasets to test both baseline performance and non-Euclidean applicability:

  • Iris: A standard benchmark for initial behavior verification.
  • Wisconsin Breast Cancer: A dataset with 30 real-valued features used to compare median versions against standard Euclidean versions.
  • Copenhagen Chromosomes: 4,200 human chromosomes represented as strings, compared using edit distance.
  • Globin Proteins: 226 protein sequences compared via evolutionary alignment distance.

Key Results and Insights

Performance and Accuracy

On the Copenhagen Chromosome dataset, the supervised median Neural Gas achieved an accuracy of 89–93%. This performance is comparable to complex K-nearest neighbor classifiers but offers the advantage of a much more compact representation, using only 100 to 500 prototypes to summarize thousands of data points.

Algorithmic Speedup

The optimization techniques proved transformative. For the Chromosome dataset ($N=4200, K=100$), the standard median implementation required 5.74 seconds per epoch. The combination of Block Summing and Branch and Bound reduced this to 0.14 seconds—a 40x speedup that significantly lowers the barrier for interactive data exploration.

Interpretability and Topology

Because the prototypes are actual members of the dataset, domain experts can inspect them directly to understand the characteristics of a cluster. Furthermore, unlike simple K-medoids, these algorithms preserve the data's topology; similar clusters are positioned near each other on the map, facilitating intuitive visual inspection of the global data structure.

Limitations and Future Outlook

Despite the efficiency gains, the requirement for a full dissimilarity matrix imposes an $O(N^2)$ initial cost, which remains a bottleneck for datasets containing millions of points. Additionally, the performance of these methods is highly sensitive to the choice of dissimilarity measure. Future work involves refining "patch clustering" techniques to handle massive datasets that exceed RAM capacity and exploring automated ways to select optimal metrics for specific biological contexts.

Summary updated

Abstract

Median clustering extends popular neural data analysis methods such as the self-organizing map or neural gas to general data structures given by a dissimilarity matrix only. This offers flexible and robust global data inspection methods which are particularly suited for a variety of data as occurs in biomedical domains. In this chapter, we give an overview about median clustering and its properties and extensions, with a particular focus on efficient implementations adapted to large scale data analysis.
BibTeX
@inproceedings{hammer2009median,
  author = {Barbara Hammer and Alexander Hasenfuß and Fabrice Rossi},
  title = {{Median topographic maps for biomedical data sets}},
  booktitle = {Similarity-Based Clustering},
  year = {2009},
  url = {https://openreview.net/forum?id=x9Ljls8zQzN},
}
Figure