Attribute reduction in decision-theoretic rough set models. (English) Zbl 1156.68589

Yao, Yiyu; Zhao, Yan

Inf. Sci. 178, No. 17, 3356-3373 (2008).

Summary: Rough set theory can be applied to rule induction. There are two different types of classification rules, positive and boundary rules, leading to different decisions and consequences. They can be distinguished not only from the syntax measures such as confidence, coverage and generality, but also the semantic measures such as decision-monotocity, cost and risk. The classification rules can be evaluated locally for each individual rule, or globally for a set of rules. Both the two types of classification rules can be generated from, and interpreted by, a decision-theoretic model, which is a probabilistic extension of the Pawlak rough set model. As an important concept of rough set theory, an attribute reduct is a subset of attributes that are jointly sufficient and individually necessary for preserving a particular property of the given information table. This paper addresses attribute reduction in decision-theoretic rough set models regarding different classification properties, such as: decision-monotocity, confidence, coverage, generality and cost. It is important to note that many of these properties can be truthfully reflected by a single measure \(\gamma \) in the Pawlak rough set model. On the other hand, they need to be considered separately in probabilistic models. A straightforward extension of the \(\gamma \) measure is unable to evaluate these properties. This study provides a new insight into the problem of attribute reduction.

MSC:

68T30	Knowledge representation
68T37	Reasoning under uncertainty in the context of artificial intelligence

Keywords:

attribute reduction; decision-theoretic rough set model; Pawlak rough set model

References:

[1]	An, A.; Shan, N.; Chan, C.; Cercone, N.; Ziarko, W., Discovering rules for water demand prediction: an enhanced rough-set approach, Engineering Application and Artificial Intelligence, 9, 645-653 (1996)
[3]	Beaubouef, T.; Petry, F. E.; Arora, G., Information-theoretic measures of uncertainty for rough sets and rough relational databases, Information Sciences, 109, 185-195 (1998)
[4]	Beynon, M., Reducts within the variable precision rough sets model: a further investigation, European Journal of Operational Research, 134, 592-605 (2001) · Zbl 0984.90018
[6]	Duda, R. O.; Hart, P. E., Pattern Classification and Scene Analysis (1973), Wiley: Wiley New York · Zbl 0277.68056
[7]	Düntsch, I.; Gediga, G., Uncertainty measures of rough set prediction, Artificial Intelligence, 106, 77107 (1998)
[8]	Greco, S.; Matarazzo, B.; Slowinski, R., Rough membership and Bayesian confirmation measures for parameterized rough sets, LNAI, 3641, 314-324 (2005) · Zbl 1134.68531
[9]	Greco, S.; Pawlak, Z.; Slowinski, R., Can Bayesian confirmation measures be useful for rough set decision rules?, Engineering Applications of Artificial Intelligence, 17, 4, 345-361 (2004)
[11]	Hu, Q.; Yu, D.; Xie, Z., Information-preserving hybrid data reduction based on fuzzy-rough techniques, Pattern Recognition Letters, 27, 414-423 (2006)
[12]	Hu, Q.; Yu, D.; Xie, Z.; Liu, J., Fuzzy probabilistic approximation spaces and their information measures, Transactions on Fuzzy Systems, 14, 191-201 (2006)
[13]	Inuiguch, M., Several approaches to attribute reduction in variable precision rough set model, Modeling Decisions for Artificial Intelligence, 215-226 (2005)
[14]	Katzberg, J. D.; Ziarko, W., Variable precision rough sets with asymmetric bounds, (Ziarko, W., Rough Sets, Fuzzy Sets and Knowledge Discovery (1994), Springer: Springer London), 67-177 · Zbl 0819.68041
[15]	Klir, J.; Wierman, M. J., Uncertainty Based Information: Elements of Generalized Information Theory (1999), Physica-Verlag: Physica-Verlag New York · Zbl 0935.68023
[18]	Li, H.; Zhou, X.; Huang, B., Attribute reduction in incomplete information systems based on connection degree rough set, Computer Science (Ji Suan Ji Ke Xue), 34, 39-42 (2007)
[19]	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, 3746 (2004)
[20]	Liu, J.; Hu, Q.; Yu, D., A weighted rough set based method developed for class imbalance learning, Information Science, 178, 4, 1235-1256 (2008) · Zbl 1134.68047
[21]	Mi, J. S.; Wu, W. Z.; Zhang, W. X., Approaches to knowledge reduction based on variable precision rough set model, Information Sciences, 159, 255-272 (2004) · Zbl 1076.68089
[22]	Pawlak, Z., Rough sets, International Journal of Computer and Information Sciences, 11, 341-356 (1982) · Zbl 0501.68053
[23]	Pawlak, Z., Rough classification, International Journal of Man-Machine Studies, 20, 469-483 (1984) · Zbl 0541.68077
[24]	Pawlak, Z., Rough Sets: Theoretical Aspects of Reasoning About Data (1991), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 0758.68054
[25]	Pawlak, Z.; Skowron, A., Rough membership functions, (Yager, R. R.; Fedrizzi, M.; Kacprzyk, J., Advances in the Dempster-Shafer Theory of Evidence (1994), John Wiley and Sons: John Wiley and Sons New York), 251-271 · Zbl 0794.03045
[26]	Pawlak, Z.; Skowron, A., Rudiments of rough sets, Information Sciences, 177, 3-27 (2007) · Zbl 1142.68549
[27]	Pawlak, Z.; Skowron, A., Rough sets: some extensions, Information Sciences, 177, 28-40 (2007) · Zbl 1142.68550
[28]	Pawlak, Z.; Wong, S. K.M.; Ziarko, W., Rough sets: probabilistic versus deterministic approach, International Journal of Man-Machine Studies, 29, 81-95 (1988) · Zbl 0663.68094
[29]	Skowron, A.; Rauszer, C., The discernibility matrices and functions in information systems, (Slowiński, R., Intelligent Decision Support, Handbook of Applications and Advances of the Rough Sets Theory (1992), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht)
[30]	Skowron, A.; Stepaniuk, J., Tolerance approximation spaces, Fundamenta Informaticae, 27, 245-253 (1996) · Zbl 0868.68103
[31]	Slezak, D., Normalized decision functions and measures for inconsistent decision tables analysis, Fundamenta Informaticae, 44, 291-319 (2000) · Zbl 0970.68171
[32]	Slezak, D., Rough sets and Bayes factor, LNAI, 3400, 202-229 (2005) · Zbl 1117.68072
[33]	Slezak, D.; Ziarko, W., Attribute reduction in the Bayesian version of variable precision rough set model, Electronic Notes in Theoretical Computer Science, 82, 263-273 (2003) · Zbl 1270.68323
[34]	Su, C. T.; Hsu, J. H., Precision parameter in the variable precision rough sets model: an application, Omega-International Journal of Management Science, 34, 149-157 (2006)
[35]	Swiniarski, R. W., Rough sets methods in feature reduction and classification, International Journal of Applied Mathematics and Computer Science, 11, 565-582 (2001) · Zbl 0990.68130
[36]	Swiniarski, R. W.; Skowron, A., Rough set methods in feature selection and recognition, Pattern Recognition Letters, 24, 833-849 (2003) · Zbl 1053.68093
[37]	Wang, G.; Yu, H.; Yang, D., Decision table reduction based on conditional information entropy, Chinese Journal of Computers, 25, 759-766 (2002)
[38]	Wang, G. Y.; Zhao, J.; Wu, J., A comparative study of algebra viewpoint and information viewpoint in attribute reduction, Foundamenta Informaticae, 68, 1-13 (2005)
[39]	Wierman, M. J., Measuring uncertainty in rough set theory, International Journal of General Systems, 28, 283297 (1999)
[40]	Wong, S. K.M.; Ziarko, W., Comparison of the probabilistic approximate classification and the fuzzy set model, Fuzzy Sets and Systems, 21, 357-362 (1987) · Zbl 0618.60002
[41]	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
[43]	Yao, Y. Y., Information granulation and approximation in a decision-theoretical model of rough sets, (Polkowski, L.; Pal, S. K.; Skowron, A., Rough-neuro Computing: Techniques for Computing with Words (2003), Springer: Springer Berlin), 491-516
[44]	Yao, Y. Y., Probabilistic approaches to rough sets, Expert Systems, 20, 287-297 (2003)
[47]	Yao, Y. Y.; Wong, S. K.M., A decision theoretic framework for approximating concepts, International Journal of Man-machine Studies, 37, 793-809 (1992)
[48]	Yao, Y. Y.; Wong, S. K.M.; Lingras, P., A decision-theoretic rough set model, (Ras, Z. W.; Zemankova, M.; Emrich, M. L., Methodologies for Intelligent Systems, vol. 5 (1990), North-Holland: North-Holland New York), 17-24
[50]	Zhang, W. X.; Mi, J. S.; Wu, W. Z., Knowledge reduction in inconsistent information systems, Chinese Journal of Computers, 1, 12-18 (2003)
[52]	Ziarko, W., Variable precision rough set model, Journal of Computer and System Sciences, 46, 39-59 (1993) · Zbl 0764.68162
[53]	Ziarko, W., Acquisition of hierarchy-structured probabilistic decision tables and rules from data, Expert Systems, 20, 305-310 (2003)
[54]	Ziarko, W., Probabilistic rough sets, LNAI, 3641, 283-293 (2005) · Zbl 1134.68567