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

Qian, Yuhua; Liang, Jiye; Dang, Chuangyin

Comput. Math. Appl. 55, No. 8, 1754-1765 (2008).

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.

MSC:

68T37

Reasoning under uncertainty in the context of artificial intelligence

Keywords:

rough set theory; converse approximation; decision table; decision rules; rule extracting

References:

[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