Discernibility matrix simplification for constructing attribute reducts. (English) Zbl 1162.68704

Summary: This paper proposes a reduct construction method based on discernibility matrix simplification. The method works in a similar way to the classical Gaussian elimination method for solving a system of linear equations. Elementary matrix simplification operations are introduced. Each operation transforms a matrix into a simpler form. By applying these operations a finite number of times, one can transform a discernibility matrix into one of its minimum (i.e., the simplest) forms. Elements of a minimum discernibility matrix are either the empty set or singleton subsets, in which the union derives a reduct. With respect to an ordering of attributes, which is either computed based on a certain measure of attributes or directly given by a user, two heuristic reduct construction algorithms are presented. One algorithm attempts to exclude unimportant attributes from a reduct, and the other attempts to include important attributes in a reduct.


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


[1] J.G. Bazan, H.S. Nguyen, S.H. Nguyen, P. Synak, J. Wroblewski, Rough set algorithms in classification problem, in: L. Polkowski, S. Tsumoto, T.Y. Lin (Eds.), Rough Set Methods and Applications, 2000, pp. 49-88. · Zbl 0992.68197
[2] 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)
[3] Bhatt, R.B.; Gopal, M., On the compact computational domain of fuzzy-rough sets, Pattern recognition letters, 6, 1632-1640, (2005)
[4] Chen, D.G.; Wang, C.Z.; Hu, Q.H., A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets, Information sciences, 177, 3500-3518, (2007) · Zbl 1122.68131
[5] Fishburn, P.C., Utility theory for decision-making, (1970), John Wiley & Sons New York · Zbl 0213.46202
[6] Guan, J.W.; Bell, D.A., Rough computational methods for information systems, Artificial intelligence, 105, 77-103, (1998) · Zbl 0909.68047
[7] Han, S.Q.; Wang, J., Reduct and attribute order, Journal of computer science and technology, 19, 429-449, (2004)
[8] Hu, F.; Wang, G.Y., Quick reduction algorithm based on attribute order, Chinese journal of computers, 30, 1429-1435, (2007)
[9] Hu, Q.H.; Xie, Z.X.; Yu, D.R., Hybrid attribute reduction based on a novel fuzzy-rough model and information granulation, Pattern recognition, 40, 3509-3521, (2007) · Zbl 1129.68073
[10] Hu, Q.H.; Yu, D.R.; Xie, Z.X., Information-preserving hybrid data reduction based on fuzzy-rough techniques, Pattern recognition letters, 27, 414-423, (2006)
[11] Jensen, R.; Shen, Q., Semantics-preserving dimensionality reduction: rough and fuzzy-rough-based approaches, IEEE transactions on knowledge and data engineering, 16, 1457-1471, (2004)
[12] Leung, Y.; Wu, W.Z.; Zhang, W.X., Knowledge acquisition in incomplete information systems: a rough set approach, European journal of operational research, 168, 164-180, (2006) · Zbl 1136.68528
[13] Liang, H.L.; Wang, J.; Yao, Y.Y., User-oriented feature selection for machine learning, Computer journal, 50, 421-434, (2007)
[14] 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)
[15] 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
[16] Nguyen, H.S., On the decision table with maximal number of reducts, Electronic notes in theoretical computer science, 82, 198-205, (2003) · Zbl 1270.68319
[17] Nguyen, H.S., Approximate Boolean reasoning: foundations and applications in data mining, Transactions on rough sets, 5, 334-506, (2006), LNCS 4100 · Zbl 1136.68497
[18] S.H. Nguyen, H.S. Nguyen, Some efficient algorithms for rough set methods, in: Proceedings of the International Conference on Information Processing and Management of Uncertainty on Knowledge Based Systems, 1996, pp. 1451-1456.
[19] Pawlak, Z., Rough sets, International journal of computer information and science, 11, 341-356, (1982) · Zbl 0501.68053
[20] Pawlak, Z., Rough sets: theoretical aspects of reasoning about data, (1991), Kluwer Academic Publishers Dordrecht, MA · Zbl 0758.68054
[21] Pawlak, Z.; Skowron, A., Rudiments of rough sets, Information sciences, 177, 3-27, (2007) · Zbl 1142.68549
[22] Pawlak, Z.; Skowron, A., Rough sets and Boolean reasoning, Information sciences, 177, 41-73, (2007) · Zbl 1142.68551
[23] Quafafou, M., \(\alpha\)-RST: a generalization of rough set theory, Information sciences, 124, 301-316, (2000) · Zbl 0957.68114
[24] Roberts, F.S., Measurement theory, (1976), Academic Press New York
[25] RSES. <http://alfa.mimuw.edu.pl/ rses>.
[26] Skowron, A.; Rauszer, C., The discernibility matrices and functions in information systems, ()
[27] 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
[28] Wang, G.Y.; Yu, H.; Yang, D., Decision table reduction based on conditional information entropy, Chinese journal of computers, 25, 759-766, (2002)
[29] Wang, J.; Miao, D.Q., Analysis on attribute reduction strategies of rough set, Chinese journal of computer science and technology, 13, 189-192, (1998) · Zbl 0902.68049
[30] Wang, J.; Wang, J., Reduction algorithms based on discernibility matrix: the ordered attributes method, Journal of computer science and technology, 16, 489-504, (2001) · Zbl 1014.68160
[31] Wong, S.K.M.; Ziarko, W., On optimal decision rules in decision tables, Bulletin of Polish Academy of sciences, 33, 693-696, (1985) · Zbl 0606.68091
[32] 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
[33] Y.Y. Yao, Y. Zhao, J. Wang, S.Q. Han, A model of machine learning based on user preference of attributes, in: Proceedings of International Conference on Rough Sets and Current Trends in Computing, 2006, pp. 587-596. · Zbl 1162.68588
[34] Zhao, K.; Wang, J., A reduction algorithm meeting users’ requirements, Journal of computer science and technology, 17, 578-593, (2002) · Zbl 1057.68026
[35] Zhu, W.; Wang, F.Y., Reduction and axiomization of covering generalized rough sets, Information sciences, 152, 217-230, (2003) · Zbl 1069.68613
[36] Zhu, W.; Wang, F.Y., On three types of covering-based rough sets, IEEE transactions on knowledge and data engineering, 19, 1131-1144, (2007)
[37] W. Ziarko, Rough set approaches for discovering rules and attribute dependencies, in: W. Klösgen, J.M. Żytkow (Eds.), Handbook of Data Mining and Knowledge Discovery, Oxford, 2000, pp. 328-339.
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.