NVE: A Separability and Coverage-Aware Internal Validation Metric for Biclustering
Machine Learning
Summary
The authors study a way to check how good biclustering results are, which means finding groups of rows and columns together in a data table. They focus on a new measure called Normalised Virtual Error (NVE) that not only looks at how tight each group is but also how distinct and non-overlapping the groups are compared to each other. They also introduce NVE_cov, which warns against picking groups that are very small and cover almost no data. Their tests show these measures add useful information beyond just measuring group quality alone, especially when considering how well groups cover the whole data and separate from each other.
Authors
Paritosh Tiwari, I Navin Kumar, James C. Bezdek, Punit Rathore
Abstract
Biclustering, or co-clustering, aims to discover coherent submatrices by grouping rows and columns of a data matrix simultaneously. This local two-dimensional structure makes validation more difficult than in ordinary clustering, where internal indices usually rely on compactness and separation in a single shared feature space. Existing popular internal biclustering measures such as Mean Squared Residue (MSR), and Virtual Error (VE) mainly evaluate within-bicluster coherence. Although useful, these measures do not directly assess whether the extracted biclusters are mutually distinct or whether they explain a meaningful portion of the data matrix. This paper investigates Normalised Virtual Error (NVE), an internal validation metric that extends VE using a super-bicluster normalization strategy. By comparing the VE of each bicluster with the VE obtained after merging it with other biclusters, NVE introduces a relative notion of separability and redundancy. We also study a coverage-adjusted variant, NVE\textsubscript{cov}, which penalizes solutions that obtain low error by selecting only very small submatrices. Through controlled synthetic benchmarks and yeast gene-expression datasets, we examine whether NVE and NVE\textsubscript{cov} provide information beyond standard coherence-based metrics. The results show that NVE is sensitive to redundant and poorly separated biclusters, while NVE\textsubscript{cov} changes solution rankings when low-error biclusters cover only a negligible part of the matrix. These findings suggest that NVE-based measures are useful complementary criteria for internal co-clustering validation, especially when coherence, separability, and coverage must be considered jointly.