Saturation of the Global Radius in Neighbourhood Rough-Set Attribute Reduction for High-Dimensional Small-Sample Data

Abstract Neighbourhood rough-set (NRS) attribute reduction counts the samples whose neighbourhood of a fixed radius contains no sample of another class. We analyse why this count fails as a search criterion when attributes far outnumber samples. We show that it depends on the data only through the distance of each sample to its nearest sample of another class. Once all these distances exceed the radius, the dependency saturates and the search stops. With a radius large enough to avoid this, every small subset has an empty positive region, so greedy search cannot start. As a reference without a distance radius, we use the published maximal homogeneous metric granules (MHMG), whose energy compares distances only with each other and bounds the training leave-one-out nearest-neighbour accuracy. On seventeen gene-expression datasets, even random attribute subsets saturated NRS after a few attributes. With 3-NN, MHMG was more accurate than NRS at every radius where NRS returned a reduct, also at equal size, and than random subsets and two nearest-neighbour variants of NRS. Against the best of eight radii chosen on the test folds, its margin was small. This evaluator favours MHMG, whose energy is tied to nearest-neighbour accuracy. With an SVM, fuzzy NRS with 50 attributes was more accurate than MHMG, and the full attribute set beat every subset of at most ten attributes. Tuned L1-regularised logistic regression (L1) was as accurate as MHMG, more stable and about 158 times faster. The rounding in its stopping rule changes the reduct size of MHMG.