Applications of Bipartite Graphs and their Adjacency Matrices to Covering-based Rough Sets

• Autorzy: Wang J. , Zhu W.

Identyfikatory

DOI

10.3233/FI-2017-1606

• Języki publikacji: EN

Abstrakty

EN

In this paper, bipartite graphs and their adjacency matrices are applied to equivalently represent covering-based rough sets through three sides, which are approximation operators, properties and reducible elements. Firstly, a bipartite graph is constructed through a covering. According to the constructed bipartite graph, two equivalent representations of a pair of covering upper and lower approximation operators are presented. And an algorithm is designed for computing the pair of covering approximation operators from the viewpoint of these equivalent representations. Some properties and reducible elements of covering-based rough sets are also investigated through the constructed bipartite graph. Finally, an adjacency matrix of the constructed bipartite graph is proposed, and reducible elements in the covering are obtained through the proposed adjacency matrix. Moreover, an equivalent representation of the covering upper approximation operator is presented through the proposed adjacency matrix. In a word, these results show two interesting views, which are graphs and matrices, to investigate covering-based rough sets.

Słowa kluczowe

EN

approximation operator; adjacency matrix; bipartite graph; covering; covering-based rough set

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 156, nr 2
• Strony: 237--254
• Opis fizyczny: Bibliogr. 49 poz., rys., tab.

Twórcy

autor

Wang J.

• Department of Basic Education, Shaanxi Fashion Engineering University, Xi’an 712046, China

autor

Zhu W.

• Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China, Chengdu 611731, China

Bibliografia

• [1] Bartol W, Miro J, Pioro K, Rossello F. On the coverings by tolerance classes. Information Sciences 2004;166(1-4):193–211. URL https://doi.org/10.1016/j.ins.2003.12.002.
• [2] Bianucci D, Cattaneo G, Ciucci D. Entropies and co-entropies of coverings with application to incomplete information systems. Fundamenta Informaticae 2007;75:77–105.
• [3] Bonikowski Z, Bryniarski E, Wybraniec-Skardowska U. Extensions and intentions in the rough set theory. Information Sciences 1998;107(1-4):149–167. URL https://doi.org/10.1016/S0020-0255(97)10046-9.
• [4] Chen J, Li J. An application of rough sets to graph theory. Information Sciences 2012;201:114–127. doi:10.1016/j.ins.2012.03.009.
• [5] Chen J, Lin Y, Lin G, Li J. et al. The relationship between attribute reducts in rough sets and minimal vertex covers of graphs. Information Sciences 2015;325(C):87–97. doi:10.1016/j.ins.2015.07.008.
• [6] Chen J, Lin Y, Li J, Lin G. et al. A rough set method for the minimum vertex cover problem of graphs. Applied Soft Computing 2016;42:360–367. URL https://doi.org/10.1016/j.asoc.2016.02.003.
• [7] Chiaselotti G, Ciucci D, Gentile T. et al. Generalizations of rough set tools inspired by graph theory. Fundamenta Informaticae 2016;148(1-2):207–227. doi:10.3233/FI-2016-1431.
• [8] Davvaz B. Roughness based on fuzzy ideals. Information Sciences 2006;176(16):2417–2437. doi:10.1016/j.ins.2005.10.001.
• [9] Dai J, Wang W, Xu Q, Tian H. Uncertainty measurement for interval-valued decision systems based on extended conditional entropy. Knowledge-Based Systems 2012;27:443–450. doi:10.1016/j.knosys.2011.10.013.
• [10] Du Y, Hu Q, Zhu P, Ma P. Rule learning for classification based on neighborhood covering reduction. Information Sciences 2011;181(24):5457–5467. URL https://doi.org/10.1016/j.ins.2011.07.038.
• [11] Xu G, Wang Z. A rough set approach to the characterization of transversal matroids. International Journal of Approximate Reasoning 2016;70:1–12. URL https://doi.org/10.1016/j.ijar.2015.12.001.
• [12] Johnsonbaugh R. Discrete Mathematics. Publishing House of Electronics Industry (2009). ISBN-10:712109729X, 13:978-7121097294.
• [13] Kondo M. On the structure of generalized rough sets. Information Sciences 2005;176(5):589–600. doi:10.1016/j.ins.2005.01.001.
• [14] Lang G, Miao D, Yang T, Cai M. Knowledge reduction of dynamic covering decision information systems when varying covering cardinalities. Information Sciences 2016;346(C):236–260. doi:10.1016/j.ins.2016.01.09.
• [15] Lang G, Miao D, Cai M, Zhang Z. Incremental approaches for updating reducts in dynamic covering information systems. Knowledge-Based Systems 2017;134:85–104. URL https://doi.org/10.1016/j.knosys.2017.07.020.
• [16] Li X, Yi H, Liu S. Rough sets and matroids from a lattice-theoretic viewpoint. Information Sciences 2016;342(C):37–52. doi:10.1016/j.ins.2016.01.029.
• [17] Liu G, Sai Y. Invertible approximation operators of generalized rough sets and fuzzy rough sets. Information Sciences 2010;180(11):2221–2229. doi:10.1016/j.ins.2010.01.033.
• [18] Liu G. The relationship among different covering approximations. Information Sciences 2013;250:178–183. URL http://dx.doi.org/10.1016/j.ins.2013.07.019.
• [19] Li F, Yin Y. Approaches to knowledge reduction of covering decision systems based on information theory. Information Sciences 2009;179(11):1694–1704. doi:10.1016/j.ins.2008.12.025.
• [20] Li J. Topological methods on the theory of covering generalized rough sets. Pattern Recognition and Artificial Intelligence (in Chinese) 2004;17:7–10.
• [21] Ma L. Two fuzzy covering rough set models and their generalizations over fuzzy lattices. Fuzzy Sets and Systems, 2016;294:1–17. URL https://doi.org/10.1016/j.fss.2015.05.002.
• [22] Pawlak Z. Rough sets. International Journal of Computer and Information Sciences 1982;11:341–356.
• [23] Pawlak Z, Skowron A. Rough sets: some extensions. Information Sciences 2007;177:28–40. doi:10.1016/j.ins.2006.06.006.
• [24] Pomykala, J.A.: Approximation operations in approximation space. Bulletin of the Polish Academy of Sciences 35 (1987) 653–662.
• [25] Qian Y, Liang J, Pedrycz W, Dang C. Positive approximation: An accelerator for attribute reduction in rough set theory. Artificial Intelligence 2010;174(9-10):597–618. URL https://doi.org/10.1016/j.artint.2010.04.018.
• [26] Rajagopal P, Masone J. Discrete mathematics for computer science. Saunders College, Canada (1992).
• [27] Skowron A, Stepaniuk J, Swiniarski R. Modeling rough granular computing based on approximation spaces. Information Sciences 2012;184(1):20–43. URL https://doi.org/10.1016/j.ins.2011.08.001.
• [28] Thuan ND. Covering rough sets from a topological point of view. International Journal of Computer Theory and Engineering 2009;1(5):606–609. doi:10.7763/IJCTE.2009.V1.98.
• [29] Tan A, Li J, Lin Y, Lin G. Matrix-based set approximations and reductions in covering decision information systems. International Journal of Approximate Reasoning 2015;59(C):68–80. doi:10.1016/j.ijar.2015.01.006.
• [30] Tan A, Li J, Lin G, Lin Y. Fast approach to knowledge acquisition in covering information systems using matrix operations. Knowledge-Based Systems 2015;79(C):90–98. doi:10.1016/j.knosys.2015.02.003.
• [31] Wang C, Chen D, Wu C, Hu Q. Data compression with homomorphism in covering information systems. International Journal of Approximate Reasoning 2011;52(4):519–525. URL https://doi.org/10.1016/j.ijar.2010.11.009.
• [32] Wang S, Zhu W. Matroidal structure of covering-based rough sets through the upper approximation number. International Journal of Granular Computing, Rough Sets and Intelligent Systems 2011;2:141–148. URL https://doi.org/10.1504/IJGCRSIS.2011.043369.
• [33] Wang S, Zhu W, Min F. Bipartite graphs and coverings. In: Rough Sets and Knowledge Technology 2011, pp. 722–727. URL https://doi.org/10.1007/978-3-642-24425-4_90.
• [34] Wang S, Zhu W, Zhu Q, Min F. Characteristic matrix of covering and its application to boolean matrix decomposition. Information Sciences 2013;263:186–197.
• [35] Wang J, Zhu W. Applications of matrices to a matroidal structure of rough sets. Journal of Applied Mathematics, 2013. Article ID 493201. URL http://dx.doi.org/10.1155/2013/493201.
• [36] Wang J, Zhu W. Contraction to matroidal structure of rough sets. In: Rough Sets and Knowledge Technology. Volume 8171 of LNAI. 2013, pp. 75–86. URL https://doi.org/10.1007/978-3-642-41299-8_8.
• [37] Wang J, Zhu W, Wang F, Liu G. Conditions for coverings to induce matroids. International Journal of Machine Learning and Cybernetics 2014;5(6):947–954. URL https://doi.org/10.1007/s13042-014-0236-2.
• [38] West DB. Introduction to graph theory. Pearson Education (2002).
• [39] Wu W. Attribute reduction based on evidence theory in incomplete decision systems. Information Sciences 2008;178(5):1355–1371. doi:10.1016/j.ins.2007.10.006.
• [40] Yao Y, Zhao Y. Attribute reduction in decision-theoretic rough set models. Information Sciences 2008;178(17):3356–3373.
• [41] Yao Y, Yao B. Covering based rough set approximations. Information Sciences 2012;200:91–107. doi:10.1016/j.ins.2012.02.065.
• [42] Yang T, Li Q. Reduction about approximation spaces of covering generalized rough sets. International Journal of Approximate Reasoning 2010;51(3):335–345. URL https://doi.org/10.1016/j.ijar.2009.11.001.
• [43] Yang T, Li Q, Zhou B. A new method for attribute reduction of covering information systems. Information Sciences 2013;228:175–191. URL https://doi.org/10.1016/j.ins.2012.11.005.
• [44] Yang B, Hu B. On some types of fuzzy covering-based rough sets. Fuzzy sets and Systems 2016;312:36–65. URL https://doi.org/10.1016/j.fss.2016.10.009.
• [45] Zhang Y, Li J, Wu W. On axiomatic characterizations of three pairs of covering based approximation operators. Information Sciences 2010;180(2):274–287. URL doi>10.1016/j.ins.2009.08.031.
• [46] Zhu P. An axiomatic approach to the roughness measure of rough sets. Fundamenta Informaticae 2011;109(4):463–480. URL http://dl.acm.org/citation.cfm?id=2361347.2361353.
• [47] Zhu W, Wang F. Reduction and axiomization of covering generalized rough sets. Information Sciences 2003;152:217–230. doi:10.1016/S0020-0255(03)00056-2.
• [48] Zhu W. Topological approaches to covering rough sets. Information Sciences 2007;177(6):1499–1508. doi:10.1016/j.ins.2006.06.009.
• [49] Zhu W. Relationship among basic concepts in covering-based rough sets. Information Sciences 2009;179(4):2478–2486. doi:10.1016/j.ins.2009.02.013.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).