Boundary Region-Driven Feature Selection for Neighborhood Rough Sets

Feature selection grounded in neighborhood rough sets has attracted sustained research attention owing to its principled treatment of classification uncertainty. However, existing forward greedy algorithms typically evaluate uncertainty over the entire object universe at each iteration, resulting in prohibitive computational complexity on large-scale datasets. To address this inefficiency, we introduce a new uncertainty index built upon Boundary Object Sets (BOS). BOS are defined as objects whose neighborhood granules intersect with multiple decision classes, thereby capturing intrinsic classification ambiguity. The proposed measure quantifies the proportion of these boundary objects relative to the total universe size. Grounded in this measure, we develop the Boundary Object Set Feature Selection (BOSFS) algorithm. BOSFS employs a double-contraction strategy that simultaneously reduces the candidate attribute pool and eliminates consistent objects from the active working set. Consequently, the algorithm restricts computationally expensive distance calculations to the monotonically shrinking BOS. Experiments on ten benchmark datasets, evaluated against six competing algorithms under three classifiers, confirm that BOSFS achieves the highest classification accuracy in 15 of 30 test cases while consuming only 25% of the runtime of the second-fastest competitor.