Knowledge and Information Systems Взаимодействие человека и компьютера

Feature selection strategies for improving MinHash-based classifiers’ performance and generalization

Panker, Tomer, Nissim, Nir
Springer Nature · 2026-11-02 · DOI 10.1007/s10115-026-02922-y

Аннотация

MinHash is a sketching algorithm widely employed for estimating similarity in large-scale datasets, generating independent hash-based features that serve as unbiased estimators of the Jaccard similarity. While these properties offer advantages in terms of storage efficiency and computational cost, they also render many conventional feature selection (FS) methods ineffective. This paper presents the first systematic exploration of FS strategies tailored to MinHash-based classifiers. We propose four FS methods: statistical, inter-class dissimilarity, intra-class similarity, and a hybrid approach, explicitly designed to exploit the nominal and independent nature of MinHash. We also introduce a novel feature aggregation strategy combining MinHash outputs from multiple sketches to enhance classifier performance. While applying FS methods to MinHash-based datasets does not preserve the Jaccard similarity, in our case, rather than maintaining exact similarity properties, our sole objective is to improve machine-learning classifier performance through an intelligent selection of the most beneficial MinHash-based features, a relatively underexplored research direction in the existing literature. We perform evaluations on five diverse real-world tasks: (1) unknown malware detection in Linux volatile memory, (2) COVID-19 diagnosis from chest X-rays, (3) virus DNA categorization, (4) fake news detection, and (5) malicious PDF identification. The evaluation shows that our methods generally outperform widely used FS techniques for nominal data, with statistically significant improvements observed in the majority of experimental settings. These improvements are associated with improved generalization performance, reduced model complexity, and lower storage requirements. However, performance gains are not uniform across all datasets and configurations, indicating sensitivity to dataset characteristics and classifier choice. Our objective is to enhance the performance of MinHash-based classifiers for a given MinHash dataset, rather than to identify the optimal classifier for a given learning task. In other words, our focus lies in improving the applicability and effectiveness of existing learning algorithms when they leverage MinHash-derived features, rather than in pursuing the theoretical upper bound of classification performance. The experimental results show that our methods improve classifiers’ generalization capabilities under the MinHash hyperparameter settings evaluated across five domains, and that similar improvements are observed under the alternative sketch configurations tested in Experiment 2.

Читать у издателя →