Abstract
This paper focuses on a fast algorithm for computing the assignment reduct in inconsistent incomplete decision systems. It is quite inconvenient to judge the assignment reduct directly according to its definition. We propose the judgment theorem for the assignment reduct in the inconsistent incomplete decision system, which greatly simplifies judging this type of reduct. On such basis, we derive a novel attribute significance measure and construct the fast assignment reduction algorithm (F-ARA), intended for computing the assignment reduct in inconsistent incomplete decision systems. Finally, we make a comparison between F-ARA and the discernibility matrix-based method by experiments on 13 University of California at Irvine (UCI) datasets, and the experimental results prove that F-ARA is efficient and feasible.
Introduction
In the field of Rough Set Theory—a mathematical framework for dealing with imprecise or uncertain data—"attribute reduction" is a critical preprocessing step. The goal is to find the smallest subset of features (attributes) that retains the same decision-making power as the full dataset. However, real-world data is rarely clean; it is often incomplete (containing missing values) and inconsistent (where identical attribute sets lead to different outcomes).
Traditional algorithms for these "inconsistent incomplete decision systems" typically rely on discernibility matrices. While accurate, these matrices are computationally expensive, with complexity scaling quadratically ($O(n^2)$) relative to the number of objects. For large-scale data mining, these methods often become impractical due to memory limits or extreme processing times.
The Challenge of Inconsistent Data
Inconsistent incomplete decision systems present a unique challenge because the relationship between attributes and decisions is not one-to-one. Missing values, often denoted by an asterisk (*), further complicate the ability to discern between objects.
As shown in the example above, objects like $x_3$ and $x_5$ have multiple missing values across different attributes. Determining which attributes are truly necessary to maintain the system's decision logic requires a robust mathematical foundation that can handle these gaps without exhaustive pairwise comparisons.
Methodology: The F-ARA Algorithm
The authors propose a shift from exhaustive matrix searches to a greedy heuristic approach called the Fast Assignment Reduction Algorithm (F-ARA). Their methodology rests on three pillars:
- The Judgment Theorem: The authors prove that an "assignment reduct" (which preserves the possible decisions for every object) is mathematically equivalent to an "upper approximation reduct." This theoretical breakthrough simplifies the criteria needed to verify if a feature subset is sufficient.
- Assignment Approximation Sets: They introduce a fuzzy-set-inspired way to measure how well a subset of attributes approximates a decision. Instead of a binary membership, they use the reciprocal of the number of possible decisions to weight an object's significance.
- Greedy Search Strategy: F-ARA starts with an empty set of features and iteratively adds the attribute providing the highest "assignment significance." To maintain speed, the algorithm uses a "tolerance cover" technique and quick-sorting to group similar objects, avoiding the $O(n^2)$ bottleneck.
Experimental Validation
The researchers evaluated F-ARA using 13 datasets from the UCI Machine Learning Repository, covering various data pathologies including inconsistent/complete (e.g., Sonar, Glass), consistent/incomplete (e.g., Audiology), and inconsistent/incomplete (e.g., Voting, Soybean) systems.
Key Results
The experimental results demonstrated a massive performance gap between F-ARA and standard matrix-based methods:
- Speed: On the "Wdbc" dataset, the Matrix algorithm took over 13,500 seconds, while F-ARA finished in just 2.3 seconds.
- Scalability: For larger datasets like "Sonar" and "Sat," the Matrix algorithm failed to finish within 24 hours or crashed due to memory limits. F-ARA processed them in 0.3 seconds and 82.9 seconds, respectively.
- Complexity: By using sorting techniques to create "tolerance granules," the algorithm's complexity effectively drops to $O(n \log n)$ relative to the number of objects.
Conclusion
F-ARA represents a significant advancement in rough set-based feature selection. By proving the equivalence between assignment and upper approximation reducts, the authors enabled a transition from computationally heavy matrix calculations to efficient heuristic searches. While F-ARA is a heuristic and may not find the absolute global minimum subset in every case, its speed and scalability make it a superior choice for practical, large-scale data mining applications.
Summary updated