Rough Set Characterization for 2-circuit Matroid

• Autorzy: Wang S. , Zhu Q. , Zhu W. , Min F.

Identyfikatory

DOI

10.3233/FI-2013-977

• Języki publikacji: EN

Abstrakty

EN

Rough sets are efficient to extract rules from information systems. Matroids generalize the linear independency in vector spaces and the cycle in graphs. Specifically, matroids provide well-established platforms for greedy algorithms, while most existing algorithms for many rough set problems including attribute reduction are greedy ones. Therefore, the combination between rough sets and matroids may bring new efficient solutions to those important and difficult problems. In this paper, 2-circuit matroids, abstracted from matroidal characteristics of rough sets, are studied and axiomatized. A matroid is induced by an equivalence relation, and its characteristics including the independent set and duality are represented with rough sets. Based on these rough set representations, this special type of matroid is defined as 2-circuit matroids. Conversely, an equivalence relation is induced by a matroid, and its relationship with the above induction is further investigated. Finally, a number of axioms of the 2-circuit matroid are obtained through rough sets. These interesting and diverse axioms demonstrate the potential for the connection between rough sets and matroids.

Słowa kluczowe

EN

rough set; matroid; 2-circuit matroid; duality; restriction; contraction

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 129, nr 4
• Strony: 377--393
• Opis fizyczny: Bibliogr. 48 poz.

Twórcy

autor

Wang S.

• School of Computer Science and Engineering University of Electronic Science and Technology of China, Chengdu 611731, China

autor

Zhu Q.

• School of Computer Science and Engineering University of Electronic Science and Technology of China, Chengdu 611731, China

autor

Zhu W.

• Lab of Granular Computing Minnan Normal University, Zhangzhou 363000, China

autor

Min F.

• Lab of Granular Computing Minnan Normal University, Zhangzhou 363000, China

Bibliografia

• [1] U. Alon, N. Barkai, D. A. Notterman, K. Gish, S. Ybarra, D. Mack, A. J. Levine, Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays, The National Academy of Sciences 96 (12) (1999) 6745–6750.
• [2] W. Bartol, J. Miro, K. Pioro, F. Rossello, On the coverings by tolerance classes, Information Sciences 166 (1-4) (2004) 193–211.
• [3] G. Cattaneo, D. Ciucci, A quantitative analysis of preclusivity vs. similarity based rough approximations, in: Rough Sets and Current Trends in Computing, vol. 2475 of LNCS, 2002, pp: 69–76.
• [4] Y. Chen, D. Miao, R. Wang, K. Wu, A rough set approach to feature selection based on power set tree, Knowledge-Based Systems 24 (2011) 275–281.
• [5] M. Dash, H. Liu, Consistency-based search in feature selection, Artificial Intelligence 151 (2003) 155–176.
• [6] K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, A fast and elitist multiobjective genetic algorithm: Nsga-ii, IEEE Transactions on Evolutionary Computation 6 (2) (2002) 182–197.
• [7] T. Deng, Y. Chen, W. Xu, Q. Dai, A novel approach to fuzzy rough sets based on a fuzzy covering, Information Sciences 177 (11) (2007) 2308–2326.
• [8] M. Diker, Textural approach to generalized rough sets based on relations, Information Sciences 180 (8) (2010) 1418–1433.
• [9] Y. Du, Q. Hu, P. Zhu, P. Ma, Rule learning for classification based on neighborhood covering reduction, Information Sciences 181 (24) (2011) 5457–5467.
• [10] J. Edmonds, Matroids and the greedy algorithm, Mathematical Programming 1 (1) (1971) 127–136.
• [11] Z. Gong, B. Sun, D. Chen, Rough set theory for the interval-valued fuzzy information systems, Information Sciences 178 (8) (2008) 1968–1985.
• [12] M. Hall, G. Holmes, Benchmarking attribute selection techniques for discrete class data mining, IEEE Transactions on Knowledge and Data Engineering 15 (6) (2003) 1437–1447.
• [13] Q. Hu, J. Liu, D. Yu, Mixed feature selection based on granulation and approximation, Knowledge-Based Systems 21 (4) (2007) 294–304.
• [14] Q. Hu, L. Zhang, D. Zhang, W. Pan, S. An, W. Pedrycz, Measuring relevance between discrete and continuous features based on neighborhood mutual information, Expert Systems with Applications 38 (8) (2011) 10737–10750.
• [15] R. Jensen, Q. Shen, Semantics-preserving dimensionality reduction: rough and fuzzy-rough-based approaches, IEEE Transactions on Knowledge and Data Engineering 16 (12) (2004) 1457–1471.
• [16] M. Kondo, On the structure of generalized rough sets, Information Sciences 176 (5) (2005) 589–600.
• [17] M. Kryszkiewicz, Rules in incomplete information systems, Information Sciences 113 (1998) 271–292.
• [18] X. Li, S. Liu, Matroidal approaches to rough set theory via closure operators, International Journal of Approximate Reasoning 53 (4) (2012) 513–527.
• [19] G. Liu, W. Zhu, The algebraic structures of generalized rough set theory, Information Sciences 178 (21) (2008) 4105–4113.
• [20] H. Mao, The relation between matroid and concept lattice, Advance in Mathematics 35 (3) (2006) 361–365.
• [21] F. Min, H. He, Y. Qian, W. Zhu, Test-cost-sensitive attribute reduction, Information Sciences 181 (2011) 4928–4942.
• [22] F. Min, W. Zhu, Attribute reduction of data with error ranges and test costs, Information Sciences 211 (2012) 48–67.
• [23] Y. Ouyang, Z. Wang, H. Zhang, On fuzzy rough sets based on tolerance relations, Information Sciences 180 (4) (2010) 532–542.
• [24] J. G. Oxley, Matroid theory, Oxford University Press, New York, 1993.
• [25] S. Pal, S. Mitra, P. Mitra, Rough-fuzzy mlp: modular evolution, rule generation, and evaluation, IEEE Transactions on Knowledge and Data Engineering 15 (1) (2003) 15–24.
• [26] Z. Pawlak, Rough sets, International Journal of Computer and Information Sciences 11 (1982) 341–356.
• [27] Z. Pawlak, Rough sets: theoretical aspects of reasoning about data, Kluwer Academic Publishers, Boston, 1991.
• [28] Y. Qian, J. Liang, W. Pedrycz, C. Dang, Positive approximation: An accelerator for attribute reduction in rough set theory, Artificial Intelligence 174 (9-10) (2010) 597–618.
• [29] K. Qin, J. Yang, Z. Pei, Generalized rough sets based on reflexive and transitive relations, Information Sciences 178 (21) (2008) 4138–4141.
• [30] H. Rowley, S. Baluja, T. Kanade, Neural network-based face detection, IEEE Transactions on Pattern Analysis and Machine Intelligence 20 (1) (1998) 23–38.
• [31] A. Skowron, J. Stepaniuk, Tolerance approximation spaces, Fundamenta Informaticae 27 (1996) 245–253.
• [32] A. Skowron, J. Stepaniuk, R. Swiniarski, Modeling rough granular computing based on approximation spaces, Information Sciences 184 (2012) 20–43.
• [33] R. Slowinski, D. Vanderpooten, A generalized definition of rough approximations based on similarity, IEEE Transactions on Knowledge and Data Engineering 12 (2) (2000) 331–336.
• [34] S. Tsumoto, Rule and matroid theory, in: Proceedings of the 26th Annual International Computer Software and Applications Conference, 2002, pp: 1176–1181.
• [35] S. Tsumoto, H. Tanaka, Characterization of relevance and irrelevance in empirical learning methods based on rough sets and matroid theory, in: AAAI Technical Report FS-94-02, 1994, pp: 183–186.
• [36] S. Tsumoto, H. Tanaka, A common algebraic framework of empirical learning methods based on rough sets and matroid theory, Fundamenta Informaticae 27 (1996) 273–288.
• [37] S. Wang, Q. Zhu, W. Zhu, F. Min, Matroidal structure of rough sets and its characterization to attribute reduction, Knowledge-Based Systems 36 (2012) 155–161.
• [38] S. Wang, Q. Zhu, W. Zhu, F. Min, Quantitative analysis for covering-based rough sets through the upper approximation number, Information Sciences 220 (2013) 483–491.
• [39] S.Wang,W. Zhu, Matroidal structure of covering-based rough sets through the upper approximation number, International Journal of Granular Computing, Rough Sets and Intelligent Systems 2 (2) (2011) 141–148.
• [40] X. Wang, E. C. Tsang, S. Zhao, D. Chen, D. S. Yeung, Learning fuzzy rules from fuzzy samples based on rough set technique, Information Sciences 177 (20) (2007) 4493–4514.
• [41] Y. Yao, Three-way decisions with probabilistic rough sets, Information Sciences 180 (3) (2010) 341–353.
• [42] Y. Yao, The superiority of three-way decisions in probabilistic rough set models, Information Sciences 181 (2011) 1080–1096.
• [43] W. Zhu, Generalized rough sets based on relations, Information Sciences 177 (22) (2007) 4997–5011.
• [44] W. Zhu, Topological approaches to covering rough sets, Information Sciences 177 (6) (2007) 1499–1508.
• [45] W. Zhu, Relationship among basic concepts in covering-based rough sets, Information Sciences 179 (14) (2009) 2478–2486.
• [46] W. Zhu, Relationship between generalized rough sets based on binary relation and covering, Information Sciences 179 (3) (2009) 210–225.
• [47] W. Zhu, F. Wang, On three types of covering rough sets, IEEE Transactions on Knowledge and Data Engineering 19 (8) (2007) 1131–1144.
• [48] W. Zhu, S.Wang, Matroidal approaches to generalized rough sets based on relations, International Journal of Machine Learning and Cybernetics 2 (2011) 273–279.