Boundary Region-Driven Feature Selection for Neighborhood Rough Sets

1  Introduction

The proliferation of high-dimensional datasets has rendered feature selection an indispensable preprocessing step across a broad spectrum of data-driven tasks, as it alleviates the curse of dimensionality and bolsters model generalization [1,2]. Rough set theory [3,4] provides a mathematically rigorous, assumption-free framework for feature selection that has attracted sustained research attention over the past decades. Classical rough set theory characterizes uncertainty via approximations over equivalence classes, but its reliance on label-matching of attributes limits its applicability to continuous data. To bridge this functional gap, a range of generalized rough set models have been proposed. Representative advancements include hybrid fuzzy-rough frameworks [5,6], probabilistic decision-theoretic approaches [7,8], bi-variable precision mechanisms [9], preference-driven dominance relations [10], covering approximation spaces [11,12], and the recently proposed overlapping containment and cardinality rough neighborhoods [13,14]. Among these, the neighborhood rough sets [15] replace equivalence classes with neighborhood granules defined over a distance metric, enabling principled handling of numerical attributes without discretization, and have become the most widely adopted foundation for feature selection on real-valued datasets.

In rough set environments, the attribute reduction process seeks the most compact combination of variables that retains the identical distinguishing capability of the entire feature space. Existing measures for guiding this search span several paradigms, including positive-region-based dependency [3,15], conditional entropy [16,17], mutual information [18,19], measures over compromised variable-granularity neighborhoods [20], neighborhood entropy [21,22], and fuzzy scale entropy [23]. Moreover, scholars have also explored composite uncertainty measures [24], self-information measure [25], local density-weighted criteria [26], three-way decision-based methods [27,28], and incremental reduction approaches for dynamic datasets [29,30].

Building on the neighborhood rough set model specifically, a series of algorithms with increasingly sophisticated criteria have been proposed. Chen et al. [31] combined overlap degree and conditional entropy under KNN granularity. Xu et al. [32] replaced the standard Euclidean neighborhood with a shared-neighbor similarity structure to improve robustness to local density variations. Zou and Dai [24] employed a composite measure over fuzzy β-covering neighborhoods. Gao et al. [33] weighted samples by their distributional proximity to decision boundaries within a neighborhood system. Sun et al. [34] proposed a multi-label feature selection method based on fuzzy C-means clustering and weighted neighborhood mutual information, integrating whale optimization for initialization and label enhancement to improve classification performance. Liu et al. [35] proposed a reliability-enhanced partial multi-label feature selection method based on neighborhood rough set. Chang et al. [36] proposed a fuzzy neighborhood rough set-based attribute reduction method over temporal information systems for clinical efficacy evaluation.

Despite this progress, a fundamental computational bottleneck still exists in almost all forward greedy feature selection algorithms of this type. At each iteration, these methods evaluate every candidate attribute by recomputing pairwise distances and updating approximations over the entire universe. Concretely, updating the distance matrix is the dominant cost. For a decision table containing n samples and m conditional features, extracting the final reduct requires a computational cost of O(n2m2). On large-scale or high-dimensional datasets, this design flaw leads to prohibitive runtimes, as confirmed by the empirical comparisons reported in [31–33].

To bypass this operational bottleneck, this study introduces a novel uncertainty evaluation metric driven by boundary object sets (BOS) and a corresponding accelerated feature selection algorithm. For a decision class, the BOS under attribute subset and radius δ is defined as the set of objects whose neighborhood intersects at least one other decision class. The BOS-based uncertainty measure is then defined as the ratio of the number of boundary objects to the universe size. This ratio decreases monotonically as informative attributes are added. Building on this measure, we propose the Boundary Object Set Feature Selection (BOSFS) algorithm, which embeds a double-contraction strategy. At each iteration, BOSFS shrinks both the candidate attribute pool and the active sample set. The latter is achieved by removing objects that have left the boundary and entered the positive region. Pairwise distance computation is thus confined to the monotonically shrinking BOS, reducing the effective complexity to O(m⋅n2).

The primary innovations presented in this work include the following:

•   A novel BOS-based uncertainty measure is formally introduced. Furthermore, its boundedness and monotonicity with respect to attribute subsets and neighborhood radius δ are rigorously established.

•   Unlike traditional positive-region or entropy-based metrics, our proposed measure specifically targets objects exhibiting genuine classification ambiguity, offering a more precise evaluation criterion.

•   The BOSFS algorithm restricts expensive O(n2) distance computations to the shrinking BOS by simultaneously contracting the candidate attribute space and the active sample set across iterations. This converts a constant-cost global search into a rapidly converging local refinement, lowering total complexity.

•   Extensive experiments on 10 benchmark datasets confirm that BOSFS achieves the highest accuracy in 15 out of 30 test cases, with an average runtime of only 25% compared to the second-fastest competitor.

In summary, the proposed BOSFS method offers three main advantages: computational efficiency, focused uncertainty modeling and empirical effectiveness.

The remainder of this paper is organized as follows. Foundational principles and definitions are revisited in Section 2. Section 3 formalizes the proposed BOS-driven uncertainty criterion and details its mathematical characteristics. Section 4 outlines the operational mechanics and theoretical time constraints of the BOSFS methodology. Empirical performance validations across multiple datasets are documented in Section 5, while Section 6 provides concluding remarks and outlines potential future research directions.

2  Preliminaries

This section outlines the fundamental mathematical preliminaries related to decision frameworks and neighborhood rough set theories. Beginning with decision information systems, it then covers neighborhood approximation spaces, neighborhood rough sets, and the dependency measure.

An information system (IS) is defined as a pair (U,A), where U is a non-empty finite object set, A is an attribute set. For x∈U and a∈A, xa denotes the value of object x on attribute a.

A decision information system (DIS) is a particular case in which the attribute set is split into a condition part C and a decision part L satisfying C∩L=∅, denoted as (U,C∪L), where L typically consists of a single label-type attribute. The decision label in L induces an equivalence relation that partitions U as U/L={L1,L2,…,Lr}.

To quantify the dissimilarity between objects, a distance metric is indispensable, particularly for numerical data prevalent in real-world applications.

Definition 1: Given a DIS (U,C∪L) and a conditional attribute subset 𝒢⊆C. For objects x,y∈U, the distance between x and y under 𝒢 is:

dist𝒢(x,y)=(∑a∈𝒢d(xa,ya)p)1/p(1)

where p≥1 (commonly p=2), d is typically the absolute difference |xa−ya|.

Proposition 1: Given a DIS (U,C∪L) and objects x,y∈U, if 𝒢1⊆𝒢2⊆C, then dist𝒢1(x,y)≤dist𝒢2(x,y).

Definition 2: Given a DIS (U,C∪L), a conditional attribute subset 𝒢⊆C and a parameter δ≥0. For object x∈U, the neighborhood of x under 𝒢 and δ can be defined as:

[x]𝒢δ={y∈U∣dist𝒢(x,y)≤δ}(2)

The parameter δ is termed the neighborhood radius.

For x,y∈U, if y∈[x]𝒢δ, then there exists a neighborhood relation from x to y, denoted as [x]𝒢δ(y). Let N𝒢δ be the family of all such relations under 𝒢 and δ. The pair (U,N𝒢δ) defines a neighborhood approximation space (NAS).

Proposition 2: Given a DIS (U,C∪L), 𝒢⊆C and δ≥0. The following conclusions hold:

(1)   self-inclusion: [x]𝒢δ(x) holds for any x∈U;

(2)   symmetry: if [x]𝒢δ(y)∈NAS, then [y]𝒢δ(x)∈NAS for any x,y∈U.

Proposition 3: Given a DIS (U,C∪L). For any x∈U, these statements hold:

(1)   if 𝒢1⊆𝒢2⊆C and δ≥0, then [x]G1δ⊇[x]G2δ;

(2)   if 𝒢⊆C and δ2≥δ1≥0, then [x]𝒢δ1⊆[x]𝒢δ2.

Definition 3: Given a NAS (U,N𝒢δ) and a subset X⊆U, the lower and upper approximations of X are defined as:

N_𝒢δ(X)={x∈U∣[x]𝒢δ⊆X}(3)

N¯𝒢δ(X)={x∈U∣[x]𝒢δ∩X≠∅}(4)

If N_𝒢δ(X)=N¯𝒢δ(X), then subset X is consistent in (U,N𝒢δ). Otherwise, it is called a neighborhood rough set.

Proposition 4: Given a NAS =(U,N𝒢δ) and a subset X⊆U, the following equivalences hold:

(1)   X is consistent in (U,N𝒢δ);

(2)   N_𝒢δ(X)=N¯𝒢δ(X);

(3)   N_𝒢δ(X)=X;

(4)   X=N¯𝒢δ(X).

Proposition 5: Let (U,C∪L) be a DIS and X⊆U. Then the following statements hold:

(1)   if 𝒢1⊆𝒢2⊆C and δ≥0, then N_G1δ(X)⊆N_G2δ(X);

(2)   if 𝒢⊆C and δ2≥δ1≥0, then N_𝒢δ1(X)⊇N_𝒢δ2(X);

(3)   if 𝒢1⊆𝒢2⊆C and δ≥0, then N¯𝒢1δ(X)⊇N¯𝒢2δ(X);

(4)   if 𝒢⊆C and δ2≥δ1≥0, then N¯𝒢δ1(X)⊆N¯𝒢δ2(X).

Proof:

(1)   According to Proposition 3 (1), for any x∈U, given that 𝒢1⊆𝒢2⊆C and δ≥0, we have [x]𝒢1δ⊇[x]𝒢2δ. Formula (3) dictates that if x∈N_𝒢1δ(X), then [x]𝒢1δ⊆X. Combining these two relationships yields, [x]𝒢2δ⊆[x]𝒢1δ⊆X, this inclusion implies x∈N_𝒢2δ(X). Consequently, it can be concluded that N_𝒢1δ(X)⊆N_𝒢2δ(X).

(2)   According to Proposition 3 (2), for any x∈U, given that 𝒢⊆C and δ2≥δ1≥0, we have [x]𝒢δ1⊆[x]𝒢δ2. Formula (3) dictates that if x∈N_𝒢δ2(X), then [x]𝒢δ2⊆X. Combining these two relationships yields, [x]𝒢δ1⊆[x]𝒢δ2⊆X, this inclusion implies x∈N_𝒢δ1(X). Consequently, it can be concluded that N_𝒢δ1(X)⊇N_𝒢δ2(X).

The proofs of (3) and (4) are similar to those of (1) and (2), and are therefore omitted here. □

The classic Pawlak rough set theory is shown in Fig. 1. The relationships between objects are represented by small grids; objects within the same grid are indistinguishable, while those in different grids are completely distinguishable. The irregular region X represents a target concept (decision class). The task is to determine whether each sample in U belongs to X. It is evident that objects belonging to N_(X) (the green region) definitively belong to the target concept X. Therefore, N_(X) is referred to as the positive region of X.

Figure 1: The N_(X) and N¯(X) in classical rough set theory.

Consider a DIS (U,C∪L). Decision attribute in L induces U into decision partitions, denoted as U/L={L1,L2,…,Lr}. For any decision partition Li∈U/L, its positive region under C is defined by:

POSC(Li)=N_C(Li)(5)

The dependency of the entire DIS is defined as:

γC(L)=|⋃Li∈U/LPOSC(Li)||U|(6)

Here, |⋅| indicates set cardinality.

γC(L) measures the uncertainty of the DIS. A larger value of γC(L) indicates lower uncertainty. As illustrated in Fig. 2, γC(L) calculates the proportion of objects within the positive region relative to the entire objects in U, under the conditional attribute set C. That is, the ratio of the green area to the total area in Fig. 2.

Figure 2: The positive regions of a DIS.

In forward greedy feature selection algorithms, adding a candidate attribute requires calculating the lower approximation for every decision class, resulting in O(n2) complexity. This computation must be repeated even for objects already consistent with the decision partition. Alternatively, the boundary region can also be used as a measure of uncertainty, corresponding to the yellow area in Fig. 2.

3  Boundary Region-Based Uncertainty Measure

Classical rough set theory defines the boundary region by BN(X)=N¯(X)−N_(X). It corresponds to the orange region in Fig. 1. According to Proposition 4, a DIS is consistent if and only if, the condition Li−N_(Li)=∅ holds for each decision class Li∈U/L. Conversely, the presence of any Li where Li−N_(Li)≠∅ renders the DIS inconsistent. Motivated by this principle, our proposed uncertainty measure focuses explicitly on the boundary objects within each decision class.

Definition 4: Given a NAS (U,N𝒢δ) and a subset X⊆U, the boundary object set (BOS) of X in the NAS is defined as:

BOS𝒢δ(X)={x∈X∣∃y∈[x]𝒢δ, y∉X}(7)

Remark 1: BOS differs from the classical rough set boundary region in two key aspects: (i) it considers only objects inside X, avoiding redundant counting across decision classes; (ii) it directly measures classification ambiguity at the object level. This design aligns naturally with forward greedy feature selection, where the goal is to progressively eliminate uncertainty by shrinking the BOS.

Fig. 3 illustrates the BOS of X, where objects in the red region constitute its boundary. As Fig. 1 shows, the BOS is conceptually distinct from the classical boundary region. In Fig. 1, the grids containing objects outside the subset Li are also treated as part of the boundary region of Li; however, in Fig. 3, only samples in Li are checked to determine whether they are boundary objects. This is because, in a DIS, objects outside Li will be evaluated within other decision classes, and Definition 4 avoids repeated judgment of the same object.

Figure 3: A schematic diagram of a boundary object.

Proposition 6: Let (U,C∪L) be a DIS, the following conclusions hold, for any Li∈U/L:

(1)   if 𝒢1⊆𝒢2⊆C and 0≤δ≤1, then BOS𝒢1δ(Li)⊇BOS𝒢2δ(Li);

(2)   if 0≤δ1≤δ2≤1 and 𝒢⊆C, then BOS𝒢δ1(Li)⊆BOS𝒢δ2(Li).

Definition 5: Let (U,C∪L) be a DIS, 𝒢⊆C and δ≥0. The BOS of the entire DIS is defined as:

BOS𝒢δ(L)=⋃Li∈U/LBOS𝒢δ(Li)(8)

The BOS definition of the entire DIS in Definition 5 is completely consistent with the orange region in Fig. 2.

Proposition 7: For a DIS (U,C∪L), the following conclusions hold:

(1)   if 𝒢1⊆𝒢2⊆C and 0≤δ≤1, then BOS𝒢1δ(L)⊇BOS𝒢2δ(L);

(2)   if 0≤δ1≤δ2≤1 and 𝒢⊆C, then BOS𝒢δ1(L)⊆BOS𝒢δ2(L).

Since U/L={L1,L2,…,Lr} is a decision partition, for any 0≤i,j≤r, if i≠j, then Li∩Lj=∅. Therefore, it follows that |BOS𝒢δ(L)|=∑Li∈U/L|BOS𝒢δ(Li)|.

Definition 6: Let (U,C∪L) be a DIS, 𝒢⊆C and δ≥0. The uncertainty of the DIS can be defined as:

ρ𝒢δ(L)=|BOS𝒢δ(L)||U|=∑Li∈U/L|BOS𝒢δ(Li)||U|(9)

ρ𝒢δ(L) is essentially the proportion of boundary objects in the DIS under the attribute subset 𝒢 and parameter δ relative to the total number of objects. A larger value of ρ𝒢δ(L) indicates that a greater proportion of objects fall into the boundary set relative to the total sample size, implying higher uncertainty of the DIS.

Existing measures evaluate uncertainty from the global perspective of the entire universe. The BOS-based uncertainty directly targets classification-ambiguous boundary objects, with higher pertinence for feature selection.

Proposition 8: Let (U,C∪L) be a DIS, 𝒢⊆C and δ≥0, the following properties hold:

(1)   0≤ρ𝒢δ(L)≤1;

(2)   ρ∅δ(L)=1.

Proposition 9: For a DIS (U,C∪L), the following conclusions hold:

(1)   if 𝒢1⊆𝒢2⊆C and 0≤λ≤1, then ρ𝒢1δ(L)≥ρ𝒢2δ(L);

(2)   if 0≤δ1≤δ2≤1 and 𝒢⊆C, then ρ𝒢δ1(L)≤ρ𝒢δ2(L).

Proposition 10: For a DIS (U,C∪L), for any Li∈U/L, BOS𝒢δ(Li)⊆N¯𝒢δ(Li)−N_𝒢δ(Li).

Example 1: Take a DIS (U,C∪L), where the universe is U={p1,p2,p3,p4,q1,q2,q3}. For a given 𝒢⊆C, the distances dist𝒢 on U are reported in Table 1. The decision attribute in L induces a partition: L1={p1,p2,p3,p4} and L2={q1,q2,q3}.

Representing the above DIS graphically yields Fig. 4. In Fig. 4, vertices represent objects and the radius δ=0.5, with red square points and blue circular points representing objects in L1 and L2, respectively. The set of objects falling within the yellow area constitutes the BOS of this DIS.

Figure 4: Visualization of the DIS: the yellow area indicates the overlap of circles with radius δ centered on objects of different classes, and the objects within this area form the BOS of the DIS.

For L1, BOS𝒢δ(L1)={p4} because [p4]𝒢δ={p2,p3,p4,q1,q2}, and the objects q1 and q2 do not belong to L1. Similarly, BOS𝒢δ(L2)={q1,q2}. Thus, BOS𝒢δ(L)={p4,q1,q2} and ρ𝒢δ(L)=3/7≈0.43.

4  BOS-Based Feature Selection Algorithm

Feature selection aims to find a compact and informative attribute subset that maintains the discriminative ability of the complete feature space. For DISs, the fundamental objective of feature selection is to quantify the impact of varying attribute combinations on object discriminability with respect to a target partition. This section introduces a novel feature selection methodology utilizing the boundary region of the DIS—as formalized in Definition 6—as the primary uncertainty measure.

4.1 The BOS-Based Feature Selection Algorithm

Definition 7: Let (U,C∪L) be a DIS, 𝒢⊆C and δ≥0. A feature subset 𝒢⊆C is a reduct of C if it meets the following conditions:

(1)   ρ𝒢δ(L)=ρCδ(L);

(2)   for any a∈G, ρG−{a}δ(L)>ρ𝒢δ(L).

Condition (1) ensures that the reduced attribute set 𝒢 maintains the same degree of uncertainty as the full attribute set C. Condition (2) guarantees the minimality of subset 𝒢, indicating that no further attributes can be removed without increasing uncertainty.

The contribution of a single attribute to uncertainty reduction during forward selection is captured by the following significance measure.

Definition 8: Let (U,C∪L) be a DIS, 𝒢⊆C, δ≥0, and a∈C−G. The contribution significance of adding attribute a to subset 𝒢 with respect to decision attribute L is defined as:

SIGδ(a,G,L)=ρ𝒢δ(L)−ρG∪{a}δ(L)(10)

Specifically, when the selected 𝒢=∅, BOS𝒢δ(L)=U, ρ𝒢δ(L) reaches its maximum value 1. Adding an attribute a to 𝒢 reduces ρG∪{a}δ(L). Thus, SIGδ(a,G,L) quantifies the reduction in uncertainty contributed by a. Building upon Definitions 7 and 8, we propose the Boundary Object Set Feature Selection (BOSFS) algorithm.

Given a DIS with m attributes and n objects. In addition, k is a reduction factor, where |BOS𝒢∪{a}δ(L)|=k⋅|BOS𝒢δ(L)|; l is the final number of selected attributes in 𝒢 and t is the iteration number. The step-by-step complexity analysis of Algorithm 1 is as follows: The outer loop (step 2): runs l times. The distance calculation (step 4): the cost per iteration decreases quadratically: O(m⋅(n⋅kt−1)2). The BOS check (step 5–7): the cost is O(m⋅n⋅kt−1). The total time complexity is the sum of the geometric series across l iterations: T(n,m,l)=∑t=1lm⋅(n⋅kt−1)2≤m⋅n21−k2. Because k<1, the square of the reduction factor k2 makes the series converge extremely quickly. The simplified complexity is O(m⋅n2).

Example 2: To intuitively illustrate the reduction of the BOS in Algorithm 1 as conditional attributes are added, suppose that an additional conditional attribute a is introduced after Example 1. According to Proposition 1, it is straightforward to conclude that the distances between objects increase. Fig. 5 visually depicts the shrinkage of the BOS as the distances among samples become larger.

Figure 5: The green region represents the overlapping area, under radius δ, among samples from different classes after selecting attribute a.

To provide a more intuitive illustration of the change in the overlapping area shown in Figs. 4 and 5, Fig. 6 directly compares the corresponding overlap regions in these two figures. It can be observed that the overlapping area decreases as more attributes are introduced.

Figure 6: Comparison of the overlapping regions in Figs. 4 and 5, showing that the BOS shrinks after attribute a is added.

It should be noted that Algorithm 1 measures the size of the BOS by the number of objects contained in the overlapping region, rather than by the area of the region itself. In this example, after adding attribute a, the distance between q2 and p4 becomes greater than δ. Consequently, the BOS changes from {p4,q1,q2} to {p4,q1}, indicating that the number of objects in the set is also reduced.

4.2 Computational Efficiency of BOSFS

Traditional forward greedy selection algorithms reliant on the positive region suffer from computational bottlenecks due to repeated scanning of the entire universe U. In contrast, the BOSFS algorithm achieves superior efficiency via a “double-contraction” strategy targeting both attributes and samples.

The key efficiency gain stems from replacing global universe scans with targeted BOS evaluation. Traditional methods recompute distances and update approximations over all n objects at every iteration, including those that have been correctly classified, which is redundant and increases with dataset size. In BOSFS, once an object exits the boundary and enters the positive region, it will no longer be involved in subsequent iterations, so the effective working set shrinks monotonically.

A second source of speedup is the quadratic contraction of distance computation costs. Conventional algorithms incur O(n2) distance calculations per candidate attribute per iteration, yielding a per-iteration cost of approximately O(m⋅n2). Since BOSFS restricts these computations to the shrinking BOS, if the boundary set contracts by a factor k<1 per iteration, the distance cost at iteration t is O(m⋅(n⋅k(t−1))2), which converges rapidly as a geometric series. Highly discriminative attributes speed up the reduction of BOS, further reducing the effective computation load.

The above algorithm analysis is based on the assumption that k<1. Proposition 7 (1) theoretically guarantees that k≤1. In the worst case, k=1, which indicates that the number of samples in the BOS does not decrease after adding any unselected attribute. In this situation, SIG=0, and Algorithm 1 terminates the attribute selection process at Line 13. Therefore, whenever Algorithm 1 performs more than one iteration of attribute selection, the average value of k is strictly less than 1.

Compared with existing acceleration methods [37,38], the main differences of BOSFS lie in both the reduction procedure and the reduction objects.

Zhang et al. [37] achieves acceleration through object selection, which differs from BOSFS in two aspects. First, in [37], object selection and attribute selection are conducted separately: object selection is performed first, followed by attribute selection on the selected object subset. In contrast, BOSFS alternates between boundary object selection and attribute selection, during which the number of samples in the boundary object set continuously decreases. Second, the object selection strategy in [37] mainly removes noisy and atypical objects, whereas BOSFS removes objects that do not contribute to uncertainty. Consequently, BOSFS eliminates more objects, leading to a more significant acceleration effect.

The difference between Yu et al. [38] and BOSFS mainly lies in the research perspective. The acceleration strategy in [38] is achieved by controlling the number of pairwise similarity relations, whereas BOSFS accelerates the process by reducing the number of involved objects.

By dynamically filtering out “solved” data and focusing exclusively on the shrinking boundary, BOSFS effectively converts a high-cost global search into a low-cost local refinement. The inclusion of highly informative attributes accelerates the depletion of the BOS, further expediting algorithm execution.

5  Experiments

This section compares BOSFS with six state-of-the-art feature selection methods. The compared algorithms are briefly described below.

•   IOFS [37] (2022): An attribute reduction algorithm based on the sum of instance importance degrees.

•   RCE [31] (2024): Utilizes KNN granularity, applying overlap degree for pre-sorting attributes and conditional entropy for uncertainty measurement.

•   SNRS [32] (2024): Employs shared-neighbor similarity for neighborhood calculation, using positive-domain dependence degree as the uncertainty metric.

•   ARBCM [24] (2025): Calculates neighborhoods based on a multi-β covering dataset, using a composite measure driven by lower-to-upper approximation ratios.

•   AMG [33] (2025): Computes sample weights based on distribution, utilizing the average margin of weighted samples as the uncertainty criterion.

•   CSFS [38] (2025): An attribute selection algorithm based on the sum of fuzzy similarities between objects from different decision classes.

Algorithm performance is evaluated along three dimensions:

•   The cardinality of the chosen attribute subset.

•   The time cost incurred during the reduction process.

•   The classification efficacy of the resulting subset.

All experiments were carried out using Python 3.8 with the scikit-learn library. The hardware environment consisted of an Intel Xeon Gold 5318Y processor, 128 GB of RAM.

5.1 Experiment Setup

In our experimental study, ten publicly accessible datasets were adopted as benchmarks for algorithm evaluation. Among them, six datasets came from the UCI [39], while the remaining were obtained from the KRBD [40]. Table 2 provides detailed descriptions of these datasets.

To compare and assess the quality of the reducts, we selected three classic classifiers that utilize the selected subsets as their feature set for training and testing the data. The performance of the feature subsets was evaluated using KNN, SVM, and DT (Decision Tree) classifiers. All classifier training and testing were conducted using ten-fold cross-validation. Statistical performance was quantified using the mean accuracy alongside its corresponding standard deviation.

It is necessary to specify the parameter settings for the models. Except for AMG, the other comparative algorithms require the setting of certain hyperparameters. To ensure a fair comparison in the experiments, considering efficiency and the number of parameters, Table 3 provides the detailed hyperparameter configuration scheme.

5.2 Experimental Analysis

Using the three previously defined metrics, we compare our algorithm with the benchmark methods in this subsection. These results confirm that BOSFS reliably identifies compact, high-quality feature subsets with substantially lower computational cost.

The reduct sizes of the seven algorithms across the ten datasets are presented in Table 4. Cross-referencing Table 4 with the original dimensions in Table 2, all seven algorithms achieve substantial dimensionality reduction: the mean selected subset sizes range from 2.2 to 48.6, corresponding to a dimensionality reduction rate of about 98.7%–99.9%.

The peak classification performance attained by the feature subsets extracted via the seven competitive algorithms is summarized in Tables 5–7. These results span multiple benchmark datasets and are validated across three classifiers. The bold entries indicate the highest classification accuracy reached by the features selected by the corresponding algorithm. Across all three tables, BOSFS consistently achieves competitive or leading classification accuracy. Among the 30 experimental settings (10 datasets × 3 classifiers), BOSFS attains the highest classification accuracy in 15 instances. SNRS leads by securing the top accuracy in 8 experimental scenarios, closely followed by AMG and CSFS with 7 instances of optimal results. IOFS, RCE and ARBCM achieve the highest accuracy in only 5, 3 and 1 case(s), respectively. Overall, compared to the other six feature selection algorithms, BOSFS shows clearly superior performance across the three classifiers.

The temporal costs associated with each selection method are documented in Table 8. These durations correspond to the specific parameter configurations that yielded maximum precision for each classifier. Figs. 7–9 provide a more intuitive comparison of the performance of various feature selection algorithms. Note that the vertical axis in Figs. 7–9 uses a logarithmic scale to accommodate the wide range of runtimes. Among all compared methods, BOSFS is the fastest by a substantial margin. CSFS ranks second, yet BOSFS’s average runtime is only 25% of CSFS’s—a gap that persists consistently across all 10 datasets, as detailed in Table 8 and illustrated in Figs. 7–9.

Figure 7: The runtime using optimal parameters for KNN.

Figure 8: The runtime using optimal parameters for SVM.

Figure 9: The runtime using optimal parameters for DT.

Among all compared algorithms, BOSFS exhibits the most stable performance in terms of both classification accuracy and runtime. Its standard deviations are consistently low across datasets, and its runtime remains nearly constant regardless of dataset dimensionality, whereas other methods show high variability.

5.3 Statistical Test

To ensure the reliability of our findings, we conduct a statistical analysis to comprehensively evaluate the superiority of algorithm BOSFS in classification accuracy and runtime. During the upcoming statistical tests, we employ three widely used statistical testing methods: the Friedman test, the Bonferroni-Dunn test and the pairwise Wilcoxon signed-rank test [41], to thoroughly assess the significance of our findings.

Initially, drawing from Tables 5–7, we present the rankings of all algorithms across each dataset as outlined in Table 9.

We set the significance level α to 0.05 for rigorous statistical testing. With 7 algorithms and 10 datasets, the threshold for Friedman test is F0.05(6,54)=2.266. By consulting Table 9, we are able to determine the values of the Friedman test statistics for Classifiers KNN, SVM, and DT, which are 5.31, 5.73, and 15.75, respectively. Clearly, these statistical values are all greater than the threshold, indicating significant differences in performance among these algorithms.

To demonstrate the statistical superiority of Algorithm BOSFS over other algorithms, we further conduct a Bonferroni-Dunn test. Given the presence of 7 algorithms and 10 datasets, we can determine the critical value for the Bonferroni-Dunn test to be CDα=2.489. Fig. 10 presents the CD diagram for the three classifiers, with the red line indicating the value of CD.

Figure 10: CD diagram of seven algorithms. (a) KNN; (b) SVM; (c) DT.

The differences between BOSFS and ARBCM, IOFS, and AMG exceed the CD threshold on at least one classifier, confirming that BOSFS significantly outperforms ARBCM on all three classifiers, significantly outperforms IOFS on the SVM and DT classifiers, and significantly outperforms AMG on the DT classifier. Although there is no significant statistical difference between BOSFS and SNRS, CSFS and RCE in terms of feature selection quality, BOSFS still holds a clear advantage over them when considering the feature selection required time.

To further validate the superiority of BOSFS at the dataset level, we conduct pairwise one-sided Wilcoxon signed-rank tests between BOSFS and each of the six competitors. To control the family-wise error rate across six simultaneous comparisons per classifier, Holm–Bonferroni correction is applied. The effect size is quantified by Cliff’s d, with thresholds |d|<0.147 (negligible), 0.147≤|d|<0.330 (small), 0.330≤|d|<0.474 (medium), and |d|≥0.474 (large). The results of the pairwise one-sided Wilcoxon signed-rank tests conducted on classification accuracy and running time are shown in Figs. 11 and 12, respectively.

Figure 11: Accuracy: Cliff’s d (BOSFS vs. competitor). **Holm p<0.01, *Holm p<0.05.

Figure 12: Runtime: Cliff’s d, BOSFS vs. competitor. **Holm p<0.01.

Accuracy results show that BOSFS significantly outperforms ARBCM across all three classifiers. Under the DT classifier, BOSFS is significantly superior to five of the six competitors. Under SVM, BOSFS significantly outperforms RCE, SNRS, IOFS, and ARBCM. Although no significant difference is found between BOSFS and AMG/CSFS under KNN and SVM, all Cliff’s d values are non-negative, indicating that BOSFS never performs worse in expectation.

Runtime results are even more decisive. The one-sided Wilcoxon test rejects H0 at p<0.01 for every competitor. The effect sizes are large against RCE, ARBCM, AMG, and IOFS, with mean speedup ratios of 86×, 119×, 100×, and 76×, respectively. Even against the second-fastest competitor CSFS, the test is significant with a mean speedup of 4.7×. These results provide statistically rigorous confirmation that the computational advantage of BOSFS is not a dataset-specific artifact but a consistent, significant property.

5.4 Analysis of the Size of the BOS

In Section 4.1, an attribute reduction factor k was introduced, and the time complexity of the algorithm was analyzed based on this factor. In this section, we further conduct a statistical analysis of the empirical values of k on real-world datasets. Since the parameter δ influences the value of k, we uniformly adopt the value of δ that yields the highest classification accuracy under the SVM classifier for the estimation of k.

Fig. 13 illustrates the relationship between the iteration rounds of feature selection and the ρ value for each dataset. As observed from Fig. 13, the size of the BOS exhibits an exponential decreasing trend with respect to the feature selection iterations. Consequently, as the number of iterations increases, the number of objects involved in the computation of ρ rapidly declines, leading to a significant reduction in computational cost.

Figure 13: The relationship between the ρ value and the feature selection rounds.

Table 10 reports the value of k at each iteration, along with the average k value for each dataset. As observed from Table 10, the average values of k across different datasets range from 0.21 to 0.64, with an overall mean of 0.495 over the ten datasets. According to the analysis in Section 4.1, the size of the BOS exhibits an exponential relationship with respect to k as the iterations proceed. Specifically, a smaller value of k leads to a faster reduction in the size of the BOS.

The above two observations, derived from empirical data statistics, validate the theoretical complexity analysis presented in Section 4.1 as well as the efficiency analysis of the BOSFS algorithm in Section 4.2.

5.5 Analysis of the Hyperparameter δ

The radius parameter δ, which controls neighborhood granularity, significantly affects both the reduct size and the final classification accuracy. To explore how δ affects selection results across datasets with different dimensionalities, we tested δ values from 0.005 to 0.4 in increments of 0.005 for each dataset. Based on dimensionality, the datasets were divided into two groups for analysis: low-dimensional datasets (dimensionality <1000: D1, D2, …, D6) and high-dimensional datasets (dimensionality ≥1000: D7, D8, D9, and D10). We analyzed both the cardinality of the attribute subsets obtained under different δ values and the attribute subsets’ performance in three classifiers.

5.5.1 Influence on Reduct Cardinality

To analyze the relationship linking δ to the cardinality of the reduct, we employed the selection ratio, defined as the ratio of the selected attribute subset to the complete attribute set. Fig. 14 illustrates the relationship between δ and the selection ratios for low-dimensional and high-dimensional datasets. Fig. 14 reveals several consistent patterns:

(1)   The neighborhood radius δ exhibits an overall positive correlation with the selection ratio, which is consistent with theoretical expectations. As δ increases, the neighborhood sample sets of individual objects expand, leading to an increase in the BOS of the target partition, which correspondingly increases the DIS uncertainty. Consequently, more condition attributes are required to reduce the DIS uncertainty.

(2)   The relationship between δ and the selection ratio does not uniformly exhibit the expected positive correlation. In certain limiting cases—for example, D5 yields an empty attribute subset when δ is in the interval [0.2,0.4]—this occurs because in Algorithm 1, when δ takes an excessively large value, SIGδ(a,G,L) equals zero for any newly added condition attribute, as selecting any condition attribute fails to decrease the value of ρ𝒢δ(L). Consequently, the attribute selection algorithm terminates.

(3)   Compared with low-dimensional datasets, the BOSFS algorithm exhibits more effective attribute selection for high-dimensional datasets. Even when δ=0.4, the selection ratio remains within the range of 0.05%–2%.

Figure 14: Attribute selection rate vs. δ on (a) low-dimensional and (b) high-dimensional datasets.

5.5.2 Influence on Classification Accuracy

A comparative analysis of classification accuracies relative to δ is presented in Fig. 15. Unlike the monotonic trend seen for selection ratio, classifier accuracy shows no consistent relationship with δ for either low- or high-dimensional datasets.

Figure 15: Classification accuracy vs. δ on (a) low-dimensional and (b) high-dimensional datasets.

Based on the above analysis, the influence of δ on the BOSFS algorithm can be summarized as follows:

(1)   A larger value of δ generally leads to a higher feature selection rate, i.e., a larger number of selected features.

(2)   The value of δ shows no clear positive or negative correlation with the classification performance of the selected feature subset.

(3)   An excessively large δ may cause the algorithm to terminate prematurely.

(4)   For the same δ interval, the feature selection rate on high-dimensional datasets is significantly lower than that on low-dimensional datasets, indicating that the feature selection benefit is more pronounced for high-dimensional data.

Based on these observations, the practical guidelines for choosing δ are summarized as follows:

Tip 1: The dataset should first be normalized to the range [0,1] using Min-Max normalization to eliminate the influence of different attribute scales.

Tip 2: Setting δ within the interval [0.01,0.1] is generally appropriate, as it prevents the selected feature subset from becoming excessively large while maintaining stable performance in downstream models.

Tip 3: If the feature selection rate is of particular concern, we recommend δ=0.05 as a suitable choice.

6  Conclusion

In this paper, we addressed the computational inefficiency of neighborhood rough set-based feature selection caused by repeatedly scanning the entire object universe. A novel BOS-based uncertainty measure is proposed, together with a corresponding forward greedy feature selection algorithm called BOSFS. The BOS-based uncertainty measure ρ𝒢δ(L) quantifies the proportion of boundary objects relative to the total sample size. The core innovation of BOSFS lies in its “double-contraction” strategy, which restricts computation exclusively to the shrinking boundary object sets across iterations, reducing the effective computational cost from O(m2⋅n2) down to O(m⋅n2). Experiments on ten benchmark datasets, conducted against six state-of-the-art algorithms under three classifiers, show that BOSFS achieves the highest classification accuracy in 15 of 30 cases while running in only 25% of the time required by the second-fastest competitor. Nevertheless, several limitations remain. The performance of BOSFS is sensitive to the neighborhood radius δ, and an adaptive selection strategy for this parameter warrants further investigation. When δ is excessively large, the algorithm may terminate prematurely with a suboptimal reduct, requiring a more robust mechanism. Furthermore, the current framework relies on a fixed Minkowski distance metric, and extending it to fuzzy relations or adaptive distance measures for heterogeneous data is a valuable future direction. Integrating BOSFS with wrapper-based strategies and evaluating its scalability on large-scale datasets are also open issues for subsequent research.

Acknowledgement: None.

Funding Statement: This work was supported by the Anhui Provincial Department of Education University Research Project (2024AH051375, 2024AH051368) and industry-sponsored research project from Nanjing Wenstone Information Technology Co., Ltd. (2025HX0249).

Author Contributions: The authors confirm their contribution to the paper as follows: study conception and design: Wenchang Yu; analysis and interpretation of results: Xiaoqin Ma, Zheqing Zhang; draft manuscript preparation: Kezhong Lu. All authors reviewed and approved the final version of the manuscript.

Availability of Data and Materials: Not applicable.

Ethics Approval: Not applicable.

Conflicts of Interest: The authors declare no conflicts of interest.

References

1. Wang C, Wang C, Qian Y, Leng Q. Feature selection based on weighted fuzzy rough sets. IEEE Trans Fuzzy Syst. 2024;32(7):4027–37. doi:10.1109/TFUZZ.2024.3387571. [Google Scholar] [CrossRef]

2. Xia S, Bai X, Wang G, Cheng Y, Meng D, Gao X, et al. An efficient and accurate rough set for feature selection, classification, and knowledge representation. IEEE Trans Knowl Data Eng. 2022;35(8):7724–35. doi:10.1109/TKDE.2022.3220200. [Google Scholar] [CrossRef]

3. Pawlak Z. Rough sets. Int J Comput Inf Sci. 1982;11(5):341–56. doi:10.1007/BF01001956. [Google Scholar] [CrossRef]

4. Pawlak Z. Rough sets: theoretical aspects of reasoning about data. Dordrecht, The Netherlands: Kluwer Academic Publishers; 1991. doi:10.1007/978-94-011-3534-4. [Google Scholar] [CrossRef]

5. Fatima S, Akram M, Zafar F. A hybrid decision-making technique based on extended entropy and trapezoidal fuzzy rough number. J Appl Math Comput. 2024;70(5):4755–92. doi:10.1007/s12190-024-02150-z. [Google Scholar] [CrossRef]

6. Kumar A, Prasad PS. Scalable feature subset selection with fuzzy rough sets and fuzzy min-max neural network in hybrid decision system. IEEE Trans Fuzzy Syst. 2024;33(2):669–79. doi:10.1109/TFUZZ.2024.3488074. [Google Scholar] [CrossRef]

7. Chen L, Deng Y. GDTRSET: a generalized decision-theoretic rough sets based on evidence theory. Artif Intell Rev. 2023;56(3):3341–62. doi:10.1007/s10462-023-10605-1. [Google Scholar] [CrossRef]

8. Ali W, Shaheen T, Toor HG, Alballa T, Alburaikan A, Khalifa HA. An improved intuitionistic fuzzy decision-theoretic rough set model and its application. Axioms. 2023;12(11):1003. doi:10.3390/axioms12111003. [Google Scholar] [CrossRef]

9. Yu B, Hu Y, Dai J. A bi-variable precision rough set model and its application to attribute reduction. Inf Sci. 2023;645(1):119368. doi:10.1016/j.ins.2023.119368. [Google Scholar] [CrossRef]

10. Sang B, Chen H, Yang L, Wan J, Li T, Xu W. Feature selection considering multiple correlations based on soft fuzzy dominance rough sets for monotonic classification. IEEE Trans Fuzzy Syst. 2022;30(12):5181–95. doi:10.1109/TFUZZ.2022.3169625. [Google Scholar] [CrossRef]

11. Dai J, Zou X, Qian Y, Wang X. Multi-fuzzy β-covering approximation spaces and their information measures. IEEE Trans Fuzzy Syst. 2022;31(3):955–69. doi:10.1109/TFUZZ.2022.3193448. [Google Scholar] [CrossRef]

12. Zhang K, Dai J. Redefined fuzzy rough set models in fuzzy β-covering group approximation spaces. Fuzzy Sets Syst. 2022;442(8):109–54. doi:10.1016/j.fss.2021.10.012. [Google Scholar] [CrossRef]

13. Al-shami TM, Mhemdi A. Overlapping containment rough neighborhoods and their generalized approximation spaces with applications. J Appl Math Comput. 2025;71(1):869–900. doi:10.1007/s12190-024-02261-7. [Google Scholar] [CrossRef]

14. Al-shami TM, Hosny RA, Mhemdi A, Hosny M. Cardinality rough neighborhoods with applications. AIMS Math. 2024;9(11):31366–92. doi:10.3934/math.20241511. [Google Scholar] [CrossRef]

15. Hu Q, Yu D, Xie Z. Neighborhood classifiers. Expert Syst Appl. 2008;34(2):866–76. doi:10.1016/j.eswa.2006.10.043. [Google Scholar] [CrossRef]

16. Yang L, Sang B, Xu W, Chen H, Yuan Z, Qin K. QFIG: a novel attribute reduction method using conditional entropy in quantified fuzzy approximation space. Fuzzy Sets Syst. 2025;516(2):109443. doi:10.1016/j.fss.2025.109443. [Google Scholar] [CrossRef]

17. Hu Q, Yu D, Xie Z, Liu J. Fuzzy probabilistic approximation spaces and their information measures. IEEE Trans Fuzzy Syst. 2006;14(2):191–201. doi:10.1109/TFUZZ.2005.864086. [Google Scholar] [CrossRef]

18. Xu J, Meng X, Qu K, Sun Y, Hou Q. Feature selection using relative dependency complement mutual information in fitting fuzzy rough set model. Appl Intell. 2023;53(15):18239–62. doi:10.1007/s10489-022-04445-9. [Google Scholar] [CrossRef]

19. Chen Y, Zhang Z, Zheng J, Ma Y, Xue Y. Gene selection for tumor classification using neighborhood rough sets and entropy measures. J Biomed Inform. 2017;67:59–68. doi:10.1016/j.jbi.2017.02.007. [Google Scholar] [PubMed] [CrossRef]

20. Song S, Zhang X. Feature selections using systematic and optimal algebra-information fusion measures based on compromised variable-granularity neighborhoods. Expert Syst Appl. 2026;304(1):131973. doi:10.1016/j.eswa.2026.131973. [Google Scholar] [CrossRef]

21. Hu Q, Zhang L, Chen D, Pedrycz W, Yu D. Gaussian kernel based fuzzy rough sets: model, uncertainty measures and applications. Int J Approx Reason. 2010;51(4):453–71. doi:10.1016/j.ijar.2010.01.004. [Google Scholar] [CrossRef]

22. Wang X, Tsang ECC, Zhao S, Chen D, Yeung DS. Learning fuzzy rules from fuzzy samples based on rough set technique. Inf Sci. 2007;177(20):4493–514. doi:10.1016/j.ins.2007.04.010. [Google Scholar] [CrossRef]

23. Wang J, Huang Z, Weng Z, Li J. Feature subset selection using fuzzy scale entropy-based uncertainty measures for multi-scale fuzzy relation decision systems. Fuzzy Sets Syst. 2026;526:109665. doi:10.1016/j.fss.2025.109665. [Google Scholar] [CrossRef]

24. Zou X, Dai J. A fuzzy β-covering rough set model for attribute reduction by composite measure. Fuzzy Sets Syst. 2025;507:109314. doi:10.1016/j.fss.2025.109314. [Google Scholar] [CrossRef]

25. Wang C, Huang Y, Shao M, Hu Q, Chen D. Feature selection based on neighborhood self-information. IEEE Trans Cybern. 2020;50(9):4031–42. doi:10.1109/TCYB.2019.2923430. [Google Scholar] [PubMed] [CrossRef]

26. Ma Q, Zhu X, Zhao X, Zhao B, Fu G, Zhang R. An equidistance index intuitionistic fuzzy c-means clustering algorithm based on local density and membership degree boundary. Appl Intell. 2024;54(4):3205–21. doi:10.1007/s10489-024-05297-1. [Google Scholar] [CrossRef]

27. Gao C, Hu J, Zhou J, Ding W, Pedrycz W. Average weight margin-based feature selection with three-way decision. Pattern Recogn. 2025;174(6):113009. doi:10.1016/j.patcog.2025.113009. [Google Scholar] [CrossRef]

28. Chen Z, Chen G, Gao C, Zhou J, Wen J. Robust weighted fuzzy margin-based feature selection with three-way decision. Int J Approx Reason. 2024;173(9):109253. doi:10.1016/j.ijar.2024.109253. [Google Scholar] [CrossRef]

29. Li Y, Wu X, Wang X. Incremental reduction methods based on granular ball neighborhood rough sets and attribute grouping. Int J Approx Reason. 2023;160(8):108974. doi:10.1016/j.ijar.2023.108974. [Google Scholar] [CrossRef]

30. Pan Y, Xu W, Ran Q. An incremental approach to feature selection using the weighted dominance-based neighborhood rough sets. Int J Mach Learn Cybern. 2023;14(4):1217–33. doi:10.1007/s13042-022-01695-4. [Google Scholar] [CrossRef]

31. Chen J, Zhang X, Yuan Z. Feature selection based on overlap degrees and granulation measures for k-NN rough sets. Pattern Recogn. 2024;156(18):110837. doi:10.1016/j.patcog.2024.110837. [Google Scholar] [CrossRef]

32. Xu F, Cai M, Li Q, Wang H, Fujita H. Shared neighbors rough set model and neighborhood classifiers. Expert Syst Appl. 2024;244(1):122965. doi:10.1016/j.eswa.2023.122965. [Google Scholar] [CrossRef]

33. Gao C, Zhou J, Wang X, Pedrycz W. Granule margin-based feature selection in weighted neighborhood systems. IEEE Trans Cybern. 2025;55(4):2151–64. doi:10.1109/TCYB.2025.3544693. [Google Scholar] [PubMed] [CrossRef]

34. Sun L, Guo J, Wu X, Xu J. Fuzzy C-means clustering-based multi-label feature selection via weighted neighborhood mutual information. Inf Sci. 2025;718:122389. doi:10.1016/j.ins.2025.122389. [Google Scholar] [CrossRef]

35. Liu J, Huang S, Fan Y, Zhang H, Gou J, Lin Y. Reliability-enhanced partial multi-label feature selection based on neighborhood rough set. Pattern Recogn. 2026;179:113762. doi:10.1016/j.patcog.2026.113762. [Google Scholar] [CrossRef]

36. Chang X, Sun B, Liu X, Ye J, Chu X. Fuzzy neighborhood rough set-based attribute reduction over temporal information systems with application to clinical efficacy evaluation. Inf Process Manag. 2026;63(6):104730. doi:10.1016/j.ipm.2026.104730. [Google Scholar] [CrossRef]

37. Zhang X, Mei C, Li J, Yang Y, Qian T. Instance and feature selection using fuzzy rough sets: a bi-selection approach for data reduction. IEEE Trans Fuzzy Syst. 2023;31(6):1981–94. doi:10.1109/TFUZZ.2022.3216990. [Google Scholar] [CrossRef]

38. Yu W, Ma X, Zhang Z, Zhang Q. A method for fast feature selection utilizing cross-similarity within the context of fuzzy relations. Comput Mater Contin. 2025;83(1):1195–218. doi:10.32604/cmc.2025.060833. [Google Scholar] [CrossRef]

39. Dua D, Graff C. UCI machine learning repository [Internet]. Irvine, CA, USA: University of California, School of Information and Computer Science; 2019 [cited 2026 Jan 13]. Available from: https://archive.ics.uci.edu/. [Google Scholar]

40. Cano A, Masegosa A, Moral S. Kent ridge biomedical data set [Internet]; 2005 [cited 2026 Jan 13]. Available from: http://leo.ugr.es/elvira/DBCRepository/. [Google Scholar]

41. Demšar J. Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res. 2006;7:1–30. [Google Scholar]