It is difficult to calculate attribute reduct due to high time and space complexity of entire-granulation rough sets. To solve this problem, distinguishability in information systems is defined by equivalent class, and its properties are studied. It is proved that the attribute reduct based on distinguishability is equivalent to absolute reduct. The positive region distinguishability in decision systems is defined and its properties are discussed. It is also proved that positive region distinguishability reduct is a superset of entire-granulation Pawlak reduct, but in most cases it is equal to entire-granulation Pawlak reduct and it can be regarded as an approximation of entire-granulation Pawlak reduct. Theoretical analysis and experiments show that compared with other attribute reduction algorithms, positive region distinguishability reduct has great advantages in computational complexity and classification accuracy.
[1] PAWLAK Z. Rough Sets: Theoretical Aspect of Reasoning about Data. Dordrecht, The Netherlands: Kluwer Academic Publishers, 1991.
[2] PAWLAK Z. Vagueness and Uncertainty: A Rough Set Perspective. Computational Intelligence, 1995, 11(2): 227-232.
[3] PAWLAK Z, SKOWRON A. Rudiments of Rough Sets. Information Sciences, 2007, 177(1): 3-27.
[4] BAZAN G J. A Comparison of Dynamic Non-dynamic Rough Set Methods for Extracting Laws from Decision Tables // POLKOWSKI L, SKOWRON A, eds. Rough Sets in Knowledge Discovery 1: Methodology and Applications. Heidelberg, Germany: Physica-Verlag, 1998: 321-365.
[5] WANG J, WANG J. Reduction Algorithms Based on Discernibility Matrix: The Order Attributes Method. Journal of Computer Science and Technology, 2001, 16(6): 489-504.
[6] ZHEN Z, WANG G Y, WU Y. A Rough Set and Rule Tree Based Incremental Knowledge Acquisition Algorithm // Proc of the 9th International Conference of Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing. Berlin, Germany: Springer-Verlag, 2003: 122-129.
[7] DENG D Y, WANG J Y, LI X J. Parallel Reducts in a Series of Decision Subsystems // Proc of the 2nd International Joint Confe-rence on Computational Sciences and Optimization. Washington, USA: IEEE, 2009: 377-380.
[8] DENG D Y. Comparison of Parallel Reducts and Dynamic Reducts in Theory. Computer Science, 2009, 36(8A): 176-178.
[9] DENG D Y. Parallel Reducts and Its Properties // Proc of the IEEE International Conference on Granular Computing. Washington, USA: IEEE, 2009: 121-125.
[10] 邓大勇,卢克文,苗夺谦,等.知识系统中全粒度粗糙集及概念漂移的研究.计算机学报, 2019, 42(1): 85-97.
(DENG D Y, LU K W, MIAO D Q, et al. Study on Entire-Granulation Rough Sets and Concept Drifting in a Knowledge System. Chinese Journal of Computers, 2019, 42(1): 85-97)
[11] DENG D Y, YAN D X, CHEN L. Attribute Significance for F-Pa-rallel Reducts // Proc of the IEEE International Conference on Granular Computing. Washington, USA: IEEE, 2011: 156-161.
[12] 邓大勇,姚 坤,肖春水.全粒度粗糙集的不确定性.模式识别与人工智能, 2018, 31(9): 809-815.
(DENG D Y, YAO K, XIAO C S. Uncertainty of Entire-Granulation Rough Sets. Pattern Recognition and Artificial Intelligence, 2018, 31(9): 809-815.)
[13] 邓大勇.全粒度粗糙集属性约简.模式识别与人工智能, 2018, 31(3): 230-235
(DENG D Y. Attribute Reduction for Entire-Granulation Rough Sets. Pattern Recognition and Artificial Intelligence, 2018, 31(3): 230-235.)
[14] 邓大勇,薛欢欢,苗夺谦,等.属性约简准则与约简信息损失的研究.电子学报, 2017, 45(2): 401-407.
(DENG D Y, XUE H H, MIAO D Q, et al. Study on Criteria of Attribute Reduction and Information Loss of Attribute Reduction. Acta Electronica Sinica, 2017, 45(2): 401-407.)
[15] 苗夺谦,胡桂荣.知识约简的一种启发式算法.计算机研究与发展, 1999, 36(6): 681-684.
(MIAO D Q, HU G R. A Heuristic Algorithm for Reduction of Knowledge. Computer Research and Development, 1999, 36(6):681-684.)
[16] 王国胤,于 洪,杨大春.基于条件信息熵的决策表约简.计算机学报, 2002, 25(7): 759-766.
(WANG G Y, YU H, YANG D C. Decision Table Reduction Based on Conditional Information Entropy. Chinese Journal of Computers, 2002, 25(7): 759-766.)
2019, Vol. 32 
