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

Yao, Yiyu; Zhao, Yan

Inf. Sci. 179, No. 7, 867-882 (2009).

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.

MSC:

68T37

Reasoning under uncertainty in the context of artificial intelligence

Keywords:

rough sets; attribute reduction; discernibility matrix; matrix simplification; algorithms

References:

[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.