Converse approximation and rule extraction from decision tables in rough set theory. (English) Zbl 1147.68736

Summary: The concept of a granulation order is proposed in an information system. The converse approximation of a target concept under a granulation order is defined and some of its important properties are obtained, which can be used to characterize the structure of a set approximation. For a subset of the universe in an information system, its converge degree is monotonously increasing under a granulation order. This means that a proper family of granulations can be chosen for a target concept approximation according to user requirements. As an application of the converse approximation, an algorithm based on the converse approximation called REBCA is designed for decision-rule extraction from a decision table, which has a time complexity of \(O(\frac m 2 |C|^2 |U|\log _2|U|)\), and its practical applications are illustrated by two examples.


68T37 Reasoning under uncertainty in the context of artificial intelligence
Full Text: DOI


[1] Pawlak, Z., Rough sets: Theoretical Aspects of Reasoning about Data (1991), Kluwer Academic Publisher: Kluwer Academic Publisher London · Zbl 0758.68054
[2] Wang, G. Y.; Yu, H.; Dang, D. C., Decision table reduction based on conditional information entropy, Journal of Computers, 25, 7, 1-8 (2002), (in Chinese)
[3] Bazan, J.; Peters, J. F.; Skowron, A.; Nguyen, HS.; Szczuka, M., Rough set approach to pattern extraction from classifiers, Electronic Notes in Theoretical Computer Science, 82, 4, 1-10 (2003)
[4] Pawlak, Z.; Skowron, A., Rudiments of rough sets, Information Sciences, 177, 3-27 (2007) · Zbl 1142.68549
[5] Pawlak, Z.; Skowron, A., Rough sets: Some extensions, Information Sciences, 177, 28-40 (2007) · Zbl 1142.68550
[6] Zadeh, L. A., Fuzzy sets and Information Granularity, (Gupta, M.; Ragade, R.; Yager, R., Advances in Fuzzy Sets Theory and Application (1979), North-Holland: North-Holland Amsterdam), 3-18 · Zbl 0377.04002
[7] Zadeh, L. A., Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic, Fuzzy Sets and Systems, 90, 111-127 (1997) · Zbl 0988.03040
[8] Zadeh, L. A., Some reflections on soft computing, granular computing and their roles in the conception, design and utilization of information/intelligent systems, Soft Computing, 2, 1, 23-25 (1998)
[13] Lin, T. Y., Granular computing on binary relations I: Data mining and neighborhood systems, II: Rough set representations and belief functions, (Polkowski, L.; Skowron, A., Rough Sets in Knowledge Discovery, vol. 1 (1998)), 107-140 · Zbl 0927.68090
[14] Yao, Y. Y., Granular computing using neighborhood systems, (Roy, R.; Furuhashi, T.; Chawdhry, P. K., Advances in Soft Computing: Engineering Design and Manufacturing (1999)), 539-553
[16] Zhang, L.; Zhang, B., Theory of fuzzy quotient space (methods of fuzzy granular computing), Journal of Software, 14, 4, 770-776 (2003), (in Chinese) · Zbl 1025.68040
[17] Liang, J. Y.; Shi, Z. Z., The information entropy, rough entropy and knowledge granulation in rough set theory, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 12, 1, 37-46 (2004) · Zbl 1074.68072
[18] Liang, J. Y.; Qian, Y. H.; Chu, C. Y.; Li, D. Y.; Wang, J. H., Rough set approximation based on dynamic granulation, Lecture Notes in Computer Science, 3641, 701-708 (2005) · Zbl 1134.68542
[19] Qian, Y. H.; Liang, J. Y.; Wang, J., Rough set approximation under dynamic granulation, Computer Science, 32, 3, 219-222 (2005), (in Chinese)
[20] Ziarko, W., Acquisition of hierarchy-structured probabilistic decision tables and rules from data, Expert Systems, 20, 5, 305-310 (2003)
[21] Zhang, W. X.; Wu, W. Z.; Liang, J. Y.; Li, D. Y., Theory and Method of Rough Sets (2001), Science Press: Science Press Beijing, China
[22] Beynon, M., Reducts within the variable precision rough sets model: A further investigation, European Journal of Operational Research, 134, 3, 592-605 (2001) · Zbl 0984.90018
[23] Kryszkiewicz, M., Comparative study of alternative type of knowledge reduction in inconsistent systems, International Journal of Intelligent Systems, 16, 105-120 (2001) · Zbl 0969.68146
[24] Leung, Y.; Li, D. Y., Maximal consistent block technique for rule acquisition in incomplete information systems, Information Sciences, 153, 85-106 (2003) · Zbl 1069.68605
[25] Liang, J. Y.; Li, D. Y., Uncertainty and Knowledge Acquisition in Information Systems (2005), Science Press: Science Press Beijing, China
[26] Liang, J. Y.; Xu, Z. B., The algorithm on knowledge reduction in incomplete information systems, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 24, 1, 95-103 (2002) · Zbl 1085.68696
[27] Nguyen, HS.; Slezak, D., Approximation reducts and association rules correspondence and complexity results, Lecture Notes in Artificial Intelligence, 1711, 137-145 (1999) · Zbl 0954.68129
[28] Quafatou, M., \( \alpha \)-RST: A generalization of rough set theory, Information Sciences, 124, 301-316 (2000) · Zbl 0957.68114
[29] Skwwron, A.; Rauszer, C., The discernibility matrices and functions in information systems, (Slowinski, R., Intelligent Decision Support, Handbook of Applications and Advances of the Rough Sets Theory (1992), Kluwer Academic: Kluwer Academic Dordrecht), 331-362
[32] Zhang, W. X.; Mi, J. S.; Wu, W. Z., Knowledge reductions in inconsistent information systems, International Journal of Intelligent Systems, 18, 989-1000 (2003) · Zbl 1069.68606
[33] Wu, W. Z.; Zhang, M.; Li, H. Z.; Mi, J. S., Knowledge reduction in random information systems via dempster-shafer theory of evidence, Information Sciences, 174, 143-164 (2005) · Zbl 1088.68169
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.