A New Description of Transversal Matroids Through Rough Set Approach

• Autorzy: Wang Zhaohao

Identyfikatory

DOI

10.3233/FI-2021-2030

• Języki publikacji: EN

Abstrakty

EN

Matroid theory is a useful tool for the combinatorial optimization issue in data mining, machine learning and knowledge discovery. Recently, combining matroid theory with rough sets is becoming interesting. In this paper, rough set approaches are used to investigate an important class of matroids, transversal matroids. We first extend the concept of upper approximation number functions in rough set theory and propose the notion of generalized upper approximation number functions on a set system. By means of the new notion, we give some necessary and sufficient conditions for a subset to be a partial transversal of a set system. Furthermore, we obtain a new description of a transversal matroid by the generalized upper approximation number function. We show that a transversal matroid can be induced by the generalized upper approximation number function which can be decomposed into the sum of some elementary generalized upper approximation number functions. Conversely, we also prove that a generalized upper approximation number function can induce a transversal matroid. Finally, we apply the generalized upper approximation number function to study the relationship among transversal matroids.

Słowa kluczowe

EN

matroid; rough set; approximation number function; set system; multset

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 179, nr 4
• Strony: 399--416
• Opis fizyczny: Bibliogr. 41 poz., tab.

Twórcy

autor

Wang Zhaohao

• School of Mathematics and Computer Science, Shanxi Normal University, Shanxi, Linfen, 041000, P.R. China

Bibliografia

• [1] Pawlak Z. Rough sets, International Journal of Computer and Information Science, 11 (1982) 341-356. doi:10.1007/BF01001956.
• [2] Yao Y. Relational interpretations of neighborhood operators and rough set approximation operators, Information Sciences, 111 (1-4) (1998) 239-259. doi:10.1016/S0020-0255(98)10006-3.
• [3] Yao Y. Constructive and algebraic methods of theory of rough sets, Information Sciences, 109 (1998) 21-47. doi:10.1016/S0020-0255(98)00012-7.
• [4] Zhu W. Relationship among basic concepts in covering-based rough sets, Information Sciences, 179(2009)2478-2486. doi:10.1016/j.ins.2009.02.013.
• [5] Zhu W. Relationship between generalized rough sets based on binary relation and covering, Information Sciences, 179(2009)210-225. doi:10.1016/j.ins.2008.09.015.
• [6] Zhu W, and Wang F. Reduction and axiomization of covering generalized rough sets, Information Sciences, 152 (2003) 217-230. doi:10.1016/S0020-0255(03)00056-2.
• [7] Zhu W. Topological approaches to covering rough sets, Information Sciences, 177 (6) (2007) 1499-1508. doi:10.1016/j.ins.2006.06.009.
• [8] Polkowski L, Skowron A (Eds.). Rough Sets in Knowledge Discovery, vol. 1, Physica-Verlag, Heidelberg, 1998. ISBN: 3-7908-1119-X.
• [9] Polkowski L, Skowron A (Eds.). Rough Sets in Knowledge Discovery, vol. 2, Physica-Verlag, Heidelberg, 1998. ISBN: 978-3-7908-2459-9.
• [10] Zhong N, Yao Y, and Ohshima M. Peculiarity oriented multidatabase mining, IEEE Transactions on Knowledge and Data Engineering, 15 (4) (2003) 952-960. doi:10.1109/TKDE.2003.1209011.
• [11] Qian Y, Liang J, Pedrycz W, and Dang C. Positive approximation: an accelerator for attribute reduction in rough set theory, Artificial Intelligence, 174 (2010) 597-618. doi:10.1016/j.artint.2010.04.018.
• [12] Yao Y, and Zhao Y. Attribute reduction in decision-theoretic rough set models, Information Sciences, 178 (2008) 3356-3373. doi:10.1016/j.ins.2008.05.010.
• [13] Tsumoto S. An approach to statistical extention of rough set rule induction, in: Rough Sets and Current Trends in Computing, volume 2005 of LNCS, 2000, pp. 362-369. doi:10.1007/3-540-45554-X_44.
• [14] Hall M, and Holmes G. Benchmarking attribute selection techniques for discrete class data mining, IEEE Transactions on Knowledge and Data Engineering, 15 (2003) 1437-1447. doi:10.1109/TKDE.2003.1245283.
• [15] Hu Q, Yu D, Liu J, and Wu C. Neighborhood rough set based heterogeneous feature subset selection, Information Sciences, 178 (2008) 3577-3594. doi:10.1016/j.ins.2008.05.024.
• [16] Wang S, Zhu Q, Zhu W, and Fan M. Matroidal structure of rough sets and its characterization to attribute reduction, Knowledge-Based Systems, 36 (2012) 155-161. doi:10.1016/j.knosys.2012.06.006.
• [17] Li X, and Liu S. Matroidal approaches to rough sets via closure operators, International Journal of Approximate Reasoning, 53 (2012) 513-527. doi:/10.1016/j.ijar.2011.12.005.
• [18] Li X, Yi H, and Liu S. Rough sets and matroids from a lattice-theoretic viewpoint, Information Sciences, 342 (2016) 37-52. doi:10.1016/j.ins.2016.01.029.
• [19] Li X, Sun B, and She Y. Generalized matroids based on three-way decision models, International Journal of Approximate Reasoning, 90 (2017) 192-207. doi:10.1016/j.ijar.2017.07.012.
• [20] Li X. Three-way fuzzy matroids and granular computing, International Journal of Approximate Reasoning, 114 (2019) 44-50. doi:10.1016/j.ijar.2019.08.003.
• [21] Wang S, Zhu Q, Zhu W, and Min F. Quantitative analysis for covering-based rough sets through the upper approximation number, Information Sciences, 220 (2013) 483-491. doi:10.1016/j.ins.2012.07.030.
• [22] Wang S, Zhu Q, Zhu W, and Min F. Matroidal structure of rough sets and its characterization to attribute reduction, Knowledge-Based Systems, 36 (2012) 155-161. doi:10.1016/j.knosys.2012.06.006.
• [23] Zhu W, and Wang S. Matroidal approaches to generalized rough sets based on relations, International Journal of Machine Learning and Cybernetics, 2 (2011) 273-279. doi:10.1007/s13042-011-0027-y.
• [24] Zhu W, and Wang S. Rough matroids based on relations, Information Sciences, 232 (2013) 241-252. doi:10.1016/j.ins.2012.12.029.
• [25] Wang Z, Wang H, Feng Q, and Shu L. The approximation number function and the characterization of covering approximation space, Information Sciences, 305(2015)196-207. doi:10.1016/j.ins.2015.02.002.
• [26] Xu G, and Wang Z. A rough set approach to the characterization of transversal matroids, International Journal of Approximate Reasoning, 70 (2016) 1-12. doi:10.1016/j.ijar.2015.12.001.
• [27] Tang J, She K, Min F, and Zhu W. A matroidal approach to rough set theory, Theoretical Computer Science, 471 (2013) 1-11. doi:10.1016/j.tcs.2012.10.060.
• [28] Wang S, Zhu W, and Min F. Matroidal structure of covering-based rough sets through the upper approximation number, International Journal of Granular Computing, Rough Sets and Intelligent Systems, 2(2011)141-148. doi:10.1504/IJGCRSIS.2011.043369.
• [29] Edmonds J, and Fulkerson DR. Transversals and matroid partition, Journal of Research of the National Bureau of Standards, 69(1965) 147-153. doi:10.6028/jres.069B.016.
• [30] Brualdi RA, and Dinolt GW. Characterizations of transversal matroids and their presentations, Journal of combinatorial theory series B, 12(1972)268-286. doi:10.1016/0095-8956(72)90041-X.
• [31] Brylawski TH. An affine representation for transversal geometries, Studies in Applied Mathematics, 54(1975)143-160. doi:10.1002/sapm1975542143.
• [32] Mirsky L, and Perfect H. Applications of the notion of independence to problems in combinatorial analysis, Journal of combinatorial theory series B, 2(1967)327-357. doi:10.1016/S0021-9800(67)80034-6.
• [33] Hall P. On representatives of subsets, Journal London Mathematical Society, 10(1935)26-30. doi:10.1007/978-0-8176-4842-8_4.
• [34] D.J.A. Welsh, Combinatorial problems in matroid theory, in: Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press, London, 1971, pp. 291-306.
• [35] Sivaraman V. Bicircular signed-graphic matroids, Discrete Mathematics, 328(2014)1-4. doi:10.1016/j.disc.2014.03.022.
• [36] Restrepo M, Cornelis C, and Gómez J. Duality, conjugacy and adjointness of approximation operators in covering-based rough sets, International Journal of Approximate Reasoning, 55 (1) (2014) 469-485. doi:10.1016/j.ijar.2013.08.002.
• [37] Zakowski W. Approximations in the space (u, π), Demonstratio Mathematica, 16 (1983) 761-769. doi:10.1515/dema-1983-0319.
• [38] Oxley J. Matroid Theory, 2ndedition, Oxford Graduate Texts in Mathematics, vol.21, Oxford University Press, Oxford, 2011. ISBN: 139780199603398.
• [39] Jena SP, Ghosh SK, and Tripathy BK. On the theory of bags and lists, Information Sciences, 132 (2001) 241-254. doi:10.1016/S0020-0255(01)00066-4.
• [40] Sayed E, and Abo-Tabl A. Topological approximations of multisets, Journal of the Egyptian Mathematical Society, 21(2013)123-132. doi:/10.1016/j.joems.2012.12.001.
• [41] Yang B, Hu B, and Qiao J. Three-way decisions with rough membership functions in covering approximation space, Fundamenta Informaticae, 165 (2019) 157-191. doi:10.3233/FI-2019-1747.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).