Fast assignment reduction in inconsistent incomplete decision systems

Min Li, Shaobo Deng, Shengzhong Feng, Jianping FanJournal of Systems Engineering and Electronics 2014 · DOI

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.

Example of an inconsistent incomplete decision system where '*' represents missing values.

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:

  1. 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.
  2. 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.
  3. 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

Abstract

This paper focuses on 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 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.
BibTeX
@article{li2014fast,
  author = {Min Li and Shaobo Deng and Shengzhong Feng and Jianping Fan},
  title = {{Fast assignment reduction in inconsistent incomplete decision systems}},
  journal = {Journal of Systems Engineering and Electronics},
  year = {2014},
  doi = {10.1109/jsee.2014.00010},
}
Figure