A computational formulation of distribution reducts in probabilistic rough set models

Conceptual and computational formulations are the two sides of the theory of rough sets. Conceptual formulation focuses on the meaning and interpretation of the concepts. Computational formulation focuses on procedures and algorithms for constructing these notions. In probabilistic rough set models, a distribution reduct is defined as a minimal subset of attributes that preserves the probabilistic lower or upper approximations of all decision classes. The definition is a conceptual formulation that provides an essential understanding of distribution reducts, but it does not directly give a computationally efficient method. In this paper, we study the computational formulation of distribution reducts in probabilistic rough set models by constructing monotonic measures, resulting in a more efficient computational method. We first construct two monotonic measures called the probabilistic low and upper approximation distribution measures, respectively, from which the computational formulation of distribution reducts can be obtained. We then propose the granularity-based probabilistic low and upper approximation distribution measures to evaluate the significance of attributes more effectively. On this basis, we develop two algorithms for finding distribution reducts based on addition–deletion method and deletion method, respectively. Finally, the experimental results show the effectiveness of the proposed measures.