# Cluster Representatives Selection in Non-Metric Spaces for Nearest Prototype Classification

arXiv: https://arxiv.org/abs/2107.01345 · HTML: https://mlsanity.com/paper/2107.01345/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 20 references that are in the map.
- First posted on arXiv 3 Jul 2021.

## Builds on (most cited first, 4 of 4)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Dissimilarity-based Sparse Subset Selection](https://mlsanity.com/paper/1407.6810/) (2014)
- [Good Recognition is Non-Metric](https://mlsanity.com/paper/1302.4673/) (2013)
- [Representative Selection in Non Metric Datasets](https://mlsanity.com/paper/1502.07428/) (2015)

## Abstract (arXiv)

The nearest prototype classification is a less computationally intensive replacement for the k-NN method, especially when large datasets are considered. In metric spaces, centroids are often used as prototypes to represent whole clusters. The selection of cluster prototypes in non-metric spaces is more challenging as the idea of computing centroids is not directly applicable. In this paper, we present CRS, a novel method for selecting a small yet representative subset of objects as a cluster prototype. Memory and computationally efficient selection of representatives is enabled by leveraging the similarity graph representation of each cluster created by the NN-Descent algorithm. CRS can be used in an arbitrary metric or non-metric space because of the graph-based approach, which requires only a pairwise similarity measure. As we demonstrate in the experimental evaluation, our method outperforms the state of the art techniques on multiple datasets from different domains.