Rough Set Theory and Digraphs

• Autorzy: Chiaselotti G. , Ciucci D. , Gentile T. , Infusino F.

Identyfikatory

DOI

10.3233/FI-2017-1542

• Języki publikacji: EN

Abstrakty

EN

In this paper we apply rough set theory to information tables induced from finite directed graphs without loops and multiples arcs (digraphs). Specifically, we use the adjacency matrix of a digraph as a particular type of information table. In this way, we are able to explore on digraphs the notions of indiscernibility partitions, lower and upper approximations, generalized core, reducts and discernibility matrix. All these ideas will be exemplified on standard digraph families as well on examples from social networks and patterns of flight routes between airports.

Słowa kluczowe

EN

attribute dependency; digraph; hypergraph minimal transversal; rough set theory

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 153, nr 4
• Strony: 291--325
• Opis fizyczny: Bibliogr. 80 poz., rys., tab.

Twórcy

autor

Chiaselotti G.

• Department of Mathematics and Informatics, University of Calabria, Via Pietro Bucci Cubo 30B, 87036 Arcavacata di Rende (CS), Italy

autor

Ciucci D.

• Department of Informatics Systems and Communication, Università di Milano - Bicocca, Viale Sarca 336/14, 20126 Milano, Italy

autor

Gentile T.

• Department of Mathematics and Informatics, University of Calabria, Via Pietro Bucci Cubo 30B, 87036 Arcavacata di Rende (CS), Italy

autor

Infusino F.

• Department of Mathematics and Informatics, University of Calabria, Via Pietro Bucci Cubo 30B, 87036 Arcavacata di Rende (CS), Italy

Bibliografia

• [1] Bang-Jensen J, Gutin G. Digraphs. Theory, algorithms and applications. Second edition. Springer Monographs in Mathematics. Springer-Verlag London, Ltd., London, 2009. ISBN-10: 085729041X.
• [2] Berge C. Hypergraphs: Combinatorics of Finite Sets, Elsevier, Amsterdam, 1984. ISBN-0080880231, 9780080880235.
• [3] Bianucci D, Cattaneo G, Ciucci D. Entropies and co-entropies of coverings with application to incomplete information systems. Fund. Inform., 2007;75(1–4):77–105.
• [4] Bianucci D, Cattaneo G. Information entropy and granulation Co-entropy of partitions and coverings: a summary, Transactions on Rough Sets 10, Lecture Notes in Computer Science, vol. 5656, 2009, pp. 15–66. doi:10.1007/978-3-642-03281-3_2.
• [5] Bisi C, Chiaselotti G. A class of lattices and boolean functions related to the Manickam-Miklös-Singhi Conjecture, Advances in Geometry, 2013;13(1):1–27. URL https://doi.org/10.1515/advgeom-2012-0027.
• [6] Bisi C, Chiaselotti G, Ciucci D, Gentile T, Federico T, Infusino G. Indistinguishability Structures as Micro and Macro Models of Granular Computing, Information Sciences, 2017;388(C):247–273. doi:10.1016/j.ins.2017.01.023.
• [7] Bisi C, Chiaselotti G, Marino G, Oliverio PA. A natural extension of the Young partition lattice. Advances in Geometry 2015;15(3):263–280. URL https://doi.org/10.1515/advgeom-2015-0017.
• [8] Cattaneo G. Generalized Rough Sets (Preclusivity Fuzzy-Intuitionistic (BZ) Lattices), Studia Logica, 1997;58(1):47–77. doi:10.1023/A:1004939914902.
• [9] Cattaneo G, Ciucci D, Bianucci D. Entropy and Co-entropy of Partitions and Coverings with Applications to Roughness Theory, in: Granular Computing: At the Junction of Rough Sets and Fuzzy sets. Series: Studies on Fuzziness and Soft Computing. R. Bello, R. Falcon, W Pedrycz and J. Kacprzyk, Eds., vol. 224, Springer-Verlag, 2008, pp. 55-77. doi:10.1007/978-3-540-76973-6_4.
• [10] Cattaneo G. An investigation about rough set theory: some foundational and mathematical aspects, Fundamenta Informaticae, 2011;108(3-4):197–221. doi:10.3233/FI-2011-420.
• [11] Cattaneo G, Chiaselotti G, Ciucci D, Gentile T. On the connection of Hypergraph Theory with Formal Concept Analysis and Rough Set Theory. Information Sciences, 2016;330:342–357. URL https://doi.org/10.1016/j.ins.2015.09.054.
• [12] Cattaneo G, Chiaselotti G, Oliverio PA, Stumbo F. A New Discrete Dynamical System of Signed Integer Partitions. European Journal of Combinatorics, 2016;55:119–143. URL https://doi.org/10.1016/j.ejc.2016.02.003.
• [13] Chen J, Li J. An application of rough sets to graph theory, Information Sciences, 2012;201:114–127. URL https://doi.org/10.1016/j.ins.2012.03.009.
• [14] Chiaselotti G, Ciucci D, Gentile T. Simple Graphs in Granular Computing. Information Sciences, 2016;340–341:279–304. URL https://doi.org/10.1016/j.ins.2015.12.042.
• [15] Chiaselotti G, Ciucci D, Gentile T. Simple Undirected Graphs as Formal Contexts. Proc. ICFCA, Lecture Notes in Computer Science, vol. 9113, Springer 2015, pp. 287–302. doi:10.1007/978-3-319-19545-2_18.
• [16] Chiaselotti G, Ciucci D, Gentile T, Infusino F. Rough Set Theory Applied to Simple Undirected Graphs. Proc. RSKT 2015, Lecture Notes in Computer Science, vol. 9436, Springer 2015, pp. 423–434. doi:10.1007/978-3-319-25754-9_37.
• [17] Chiaselotti G, Ciucci D, Gentile T, Infusino F. Preclusivity and Simple Graphs. Proc. RSFDGrC 2015, Lecture Notes in Computer Science, vol. 9437, Springer 2015, pp. 127–137. doi:10.1007/978-3-319-25783-9_12.
• [18] Chiaselotti G, Ciucci D, Gentile T, Infusino F. Preclusivity and Simple Graphs: the n–cycle and n–path Cases. Proc. RSFDGrC 2015, Lecture Notes in Computer Science, vol. 9437, Springer 2015, pp. 138–148. doi: 10.1007/978-3-319-25783-9_13.
• [19] Ciucci D. Temporal Dynamics in Information Tables, Fundamenta Informaticae, 2012;115(1):57–74. doi:10.3233/FI-2012-640.
• [20] Cornelis C, Verbiest N, Jensen R. Ordered Weighted Average Based Fuzzy Rough Sets, Proc. RSKT, Lecture Notes in Computer Science, vol. 6401, Springer 2010, pp. 78–85. doi:10.1007/978-3-642-16248-0_16.
• [21] Doreian P, Batagelj V, Ferligoj A. Generalized Blockmodeling. Cambridge University Press, 2005. ISBN-13:9780521840859, 10:0521840856.
• [22] Dubois D, Prade H. Possibility theory and formal concept analysis: Characterizing independent subcontexts, Fuzzy Sets and Systems, 2012;196:4–16. URL https://doi.org/10.1016/j.fss.2011.02.008.
• [23] Eiter T, and Gottlob G. Identifying the Minimal Transversals of a Hypergraph and Related Problems, Siam Journal on Computing, 1995;24(6):1278–1304. doi:10.1137/S0097539793250299.
• [24] Eiter T, and Gottlob G. Hypergraph transversal computation and related problems in logic and AI, Proc. JELIA, Lecture Notes in Computer Science, vol. 2424, Springer 2002, pp. 549–564. doi:10.1007/3-540-45757-7_53.
• [25] Elbassioni K. On the complexity of monotone dualization and generating minimal hypergraph transversals, Discrete Applied Mathematics, 2008;156(11): 2109-2123. URL https://doi.org/10.1016/j.dam. 2007.05.030.
• [26] Ganter B, Wille R. Formal Concept Analysis. Mathematical Foundations, Springer-Verlag, 1999. doi:10.1007/978-3-642-59830-2.
• [27] Gaume B, Navarro E, Prade H. Clustering bipartite graphs in terms of approximate formal concepts and sub-contexts, Int. J. Computational Intelligence Systems, 2013;6(6):1125–1142. URL http://dx.doi.org/10.1080/18756891.2013.819179.
• [28] Greco S, Matarazzo B, Slowinski R. Rough Sets methodology for sorting problems in presence of multiple attributes and criteria, European Journal of Operational Research, 2002;138(2):247–259. URL https://doi.org/10.1016/S0377-2217(01)00244-2.
• [29] Grzymala-Busse JW. Rule Induction from Rough Approximations, in [38], 2015, pp. 371–385. doi:10.1007/978-3-662-43505-2_23.
• [30] Guo L, Huang F, Lia Q, Zhang G. Power contexts and their concept lattices, Discrete Mathematics, 2011;311(18-19):2049–2063. doi:10.1016/j.disc.2011.04.033.
• [31] Gyárfás A, Lehel J. Hypergraph families with bounded edge cover or transversal number; Combinatorica, 1983;3(3–4):351–358. doi:10.1007/BF02579191.
• [32] Hagen M. Lower bounds for three algorithms for transversal hypergraph generation; Discrete Applied Mathematics, 2009;157(7):1460–1469. URL https://doi.org/10.1016/j.dam.2008.10.004.
• [33] Hońko P. Description and classification of complex structured objects by applying similarity measures, International Journal of Approximate Reasoning, 2008;49(3):539–554. URL https://doi.org/10.1016/j.ijar.2008.05.002.
• [34] Hońko P. Relational pattern updating, Information Sciences, 2012;189:208–218. doi:10.1016/j.ins.2011.12.004.
• [35] Hońko P. Association discovery from relational data via granular computing, Information Sciences, 2013;234:136–149. URL https://doi.org/10.1016/j.ins.2013.01.004.
• [36] Huang A, Lin Z, Zhu W. Matrix approaches to rough sets through vector matroids over fields, IJGCRSIS, 2014;3(3):179–194. URL https://doi.org/10.1504/IJGCRSIS.2014.060840.
• [37] Huang A, Zhao H, Zhu W. Nullity-based matroid of rough sets and its application to attribute reduction, Information Sciences, 2014;263:153–165. URL https://doi.org/10.1016/j.ins.2013.11.014.
• [38] Kacprzyk J, Pedrycz W (editors). Springer Handbook of Computational Intelligence, 2015 ISBN:978-3-662-43504-5.
• [39] Khachiyan L, Boros L, Elbassioni K, Gurvich V. A global parallel algorithm for the hypergraph transversal problem; Information Processing Letters, 2007;101(4):148–155. URL https://doi.org/10.1016/j.ipl.2006.09.006.
• [40] Kreinovich V. Interval Computation as an Important Part of Granular Computing: An Introduction, in [48], 2008, pp. 3–32
• [41] Liang M, Liang B, Wei L, Xu X. Edge rough graph and its application. IEEE Fuzzy Systems and Knowledge Discovery (FSKD), vol. 1, 2011, pp. 335–338. doi: 10.1109/FSKD.2011.6019588.
• [42] Midelfart H, Komorowski J. A rough set framework for learning in a directed acyclic graph, In: J.J. Alpigini, J.F. Peters, J. Skowronek, N. Zhong (Eds.), Proc. RSCTC, Lecture Notes in Computer Science, vol. 2475, Springer 2002, pp. 144–155. doi: 10.1007/3-540-45813-1_18.
• [43] Pawlak Z. Information systems theoretical foundations, Information Sciences, 1981;6(3):205–218.
• [44] Pawlak Z. Rough sets. Theoretical Aspects of Reasoning about Data. Kluwer Academic Publisher, 1991. ISBN:978-0-7923-1472-1.
• [45] Pawlak Z, Skowron A. Rudiments of rough sets, Information Sciences, 2007;177(1):3–27. doi:10.1016/j.ins.2006.06.003.
• [46] Pawlak Z, Skowron A. Rough sets: Some extensions, Information Sciences, 2007;177(1):28–40. URL https://doi.org/10.1016/j.ins.2006.06.006.
• [47] Pawlak Z, Skowron A. Rough sets and Boolean reasoning, Information Sciences, 2007;177(1):41–73. URL https://doi.org/10.1016/j.ins.2006.06.007.
• [48] Pedrycz W, Skowron A, Kreinovich V. Handbook of Granular Computing,Wiley, 2008. ISBN:978-0-470-03554-2.
• [49] Pedrycz A, Hirota K, Pedrycz W, Dong F. Granular representation and granular computing with fuzzy sets, Fuzzy Sets and Systems, 2012;203:17–32. URL https://doi.org/10.1016/j.fss.2012.03.009.
• [50] Pedrycz W. Granular computing : analysis and design of intelligent systems, CRC Press, 2013. ISBN: 9781439886816.
• [51] 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.
• [52] Qiu T, Chen X, Liu Q, Huang H. Granular Computing Approach to Finding Association Rules in Relational Database, International Journal of Intelligent Systems, 2010;25:165–179. doi:10.1002/int.20394.
• [53] Radwan AAE, Nayle MS, Nasir AI. New rough sets properties on graph theory, Int. J. Contemp. Math. Sciences, 2012;7(25-28):1217–1232.
• [54] Rainer RK, Prince B, Cegielski CG. Introduction to Information Systems, Wiley, 2014. ISBN-10:1118779649.
• [55] Skowron A, Jankowski A, Swiniarski RW. Foundations of Rough Sets, in [38], 2015, pp. 331–348
• [56] Skowron A, Rauszer C. The Discernibility Matrices and Functions in Information Systems, Intelligent Decision Support, Theory and Decision Library series , vol. 11, Springer Netherlands, 1992, pp. 331–362. doi:10.1007/978-94-015-7975-9_21.
• [57] Skowron A, Wasilewski P. Information systems in modeling interactive computations on granules, Theoretical Computer Science, 2011;412(42):5939–5959. URL https://doi.org/10.1016/j.tcs.2011.05.045.
• [58] Skowron A,Wasilewski P. Interactive information systems: Toward perception based computing, Theoretical Computer Science, 2012;454:240–260. URL https://doi.org/10.1016/j.tcs.2012.04.019.
• [59] Stell JG. Granulation for Graphs, Proc. Sp. Inf. Th., Lecture Notes in Computer Science, vol. 1661, Springer 1999, pp. 417–432. doi:10.1007/3-540-48384-5_27.
• [60] Stell JG. Relations in Mathematical Morphology with Applications to Graphs and Rough Sets, Proc. Sp. Inf. Th., Lecture Notes in Computer Science, vol. 4736, Springer 2007, pp. 438–454. doi:10.1007/978-3-540-74788-8_27.
• [61] Stell JG. Relational Granularity for Hypergraphs, Proc. RSCTC, Lecture Notes in Computer Science, vol. 6086, Springer 2010, pp. 267–276. doi:10.1007/978-3-642-13529-3_29.
• [62] Stell JG. Relational on Hypergraphs, Proc. RAMiCS, Lecture Notes in Computer Science, vol. 7560, Springer 2012, pp. 326–341. doi:10.1007/978-3-642-33314-9_22.
• [63] Stell JG. Formal concept analysis over graphs and hypergraphs, Proc. GKR2013, Lecture Notes in Computer Science, vol. 8323, Springer 2014, pp. 165–179. doi:10.1007/978-3-319-04534-4_11.
• [64] Stell JG. Symmetric Heyting relation algebras with applications to hypergraphs, Journal of Logical and Algebraic Methods in Programming, 2015;84(3):440–455. URL https://doi.org/10.1016/j.jlamp.2014.12.001.
• [65] Slowinski R, Greco S, Matarazzo B. Rough Set Methodology for Decision Aiding, in [38], 2015, pp. 349–370. doi:10.1007/978-3-662-43505-2_22.
• [66] Stepaniuk J. Rough - Granular Computing in Knowledge Discovery and Data Mining, Studies in Computational Intelligence, vol. 152, Springer-Verlag Berlin-Heidelberg, 2008. ISBN:978-3-540-70800-1.
• [67] Tanga J, Shea K, Min F, ZhuW. A matroidal approach to rough set theory, Theoretical Computer Science, 2013;471:1–11. URL https://doi.org/10.1016/j.tcs.2012.10.060.
• [68] Wang S, Zhu Q, Zhu W, Min F. Rough Set Characterization for 2-circuit Matroid, Fundamenta Informaticae, 2014;129(4):377–393. doi:10.3233/FI-2013-977.
• [69] Wang S, Zhu Q, Zhu W, Min F. Graph and matrix approaches to rough sets through matroids, Information Sciences, 2014;288:1–11. URL https://doi.org/10.1016/j.ins.2014.07.023.
• [70] Wu WZ, Leung Y, Mi JS. Granular Computing and Knowledge Reduction in Formal Contexts, IEEE Trans. on Knowledge and Data Engineering, 2009;21:1461–1474. doi:10.1109/TKDE.2008.223.
• [71] Yao YY. On modeling data mining with granular computing, Proc. COMPSAC 2001 IEEE, 2001, pp.638–643. doi:10.1109/CMPSAC.2001.960680.
• [72] Yao YY. Information granulation and rough set approximation, International Journal of Intelligent Systems, 2001;16(1):87–104. doi:10.1002/1098-111X(200101)16:1:87::AID-INT7;3.0.CO;2-S.
• [73] Yao YY, Zhong N. Granular Computing using Information Tables, in Data Mining, Rough Sets and Granular Computing, Physica-Verlag, 2002, pp. 102–124. doi:10.1007/978-3-7908-1791-1_5.
• [74] Yao JT, Yao YY. A Granular Computing Approach to Machine Learning, Proc. of the 1st International Conference on Fuzzy Systems and Knowledge Discovery, 2002, pp. 732–736.
• [75] Yao YY. A Partition Model of Granular Computing, in Transactions on Rough Sets, 1, Lecture Notes in Computer Science, vol. 3100, Springer-Verlag, 2004, pp. 232–253. doi: 10.1007/978-3-540-27794-1_11.
• [76] Yao YY, Zhao Y. Discernibility matrix simplification for constructing attribute reducts, Information Sciences, 2009;179(7):867–882. doi:10.1016/j.ins.2008.11.020.
• [77] Yao YY, Yao BX. Covering based rough set approximations, Information Sciences, 2012;200:91–107. URL https://doi.org/10.1016/j.ins.2012.02.065.
• [78] Yao YY. The two sides of the theory of rough sets, Knowledge-Based Systems, 2015;80(C):67–77. doi:10.1016/j.knosys.2015.01.004.
• [79] Zadeh LA. Towards a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic, Fuzzy Sets and Systems, 1997;19(2):111–127. doi:10.1016/S0165-0114(97)00077-8.
• [80] Zhu W, Wang S. Rough matroids based on relations, Information Sciences, 2013;232:241–252. URL https://doi.org/10.1016/j.ins.2012.12.029.