×

The granular partition lattice of an information table. (English) Zbl 1429.68270

Summary: In this paper we study the lattice of all indiscernibility partitions induced from attribute subsets of a knowledge representation system (information table in the finite case). This lattice, that we here call granular partition lattice, is a very well studied order structure in granular computing and data base theory and it provides a complete hierarchical classification of the knowledge obtained from all possible choices of attribute subsets. We show that it has a lattice structure also in the infinite case and we provide several isomorphic characterizations for this lattice. We discuss the potentiality of this order structure from both a micro-granular and a macro-granular perspective. Furthermore, the sub-poset of all the indiscernibility closures needed to determine when an arbitrary partition is an indiscernibility one is studied. Finally, we show the monotonic behaviour of the granular partition lattice with respect to entropy of partitions and attribute dependency in decision tables.

MSC:

68T30 Knowledge representation
68T37 Reasoning under uncertainty in the context of artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Baixeries, J.; Kaytoue, M.; Napoli, A., Characterizing functional dependencies in formal concept analysis with pattern structures, Ann. Math. Artif. Intell., 72, 1-2, 129-149 (2014)
[2] Balla, I.; Bollobás, B.; Eccles, T., Union-closed families of sets, J. Comb. Theory Ser. A, 120, 3, 531-544 (2013)
[3] Bianucci, D.; Cattaneo, G., Information entropy and granulation co-entropy of partitions and coverings: A summary, Trans. Rough Sets X, 5656, 15-66 (2009)
[4] Bianucci, D.; Cattaneo, G.; Ciucci, D., Entropies and co-entropies for incomplete information systems, (Yao, J.; Lingras, P.; Wu, W.-Z.; Szczuka, M. S.; Cercone, N.; Slezak, D., RSKT Proceedings. RSKT Proceedings, LNCS, 4481 (2007)), 84-92
[5] Bianucci, D.; Cattaneo, G.; Ciucci, D., Entropies and co-entropies of coverings with application to incomplete information systems, Fundam. Inform., 75, 1-4, 77-105 (2007)
[6] Cattaneo, G.; Chiaselotti, G.; Ciucci, D.; Gentile, T., On the connection of hypergraph theory with formal concept analysis and rough set theory, Inf. Sci., 330, 342-357 (2016)
[7] Chen, C., Ranked highly-arc-transitive digraphs as colimits, Order, 31, 2, 143-158 (2014)
[8] Chen, G.; Zhong, N.; Yao, Y., A hypergraph model of granular computing, The 2008 IEEE International Conference on Granular Computing, GrC 2008, Proceedings, 130-135 (2008), IEEE
[9] Chiaselotti, G.; Ciucci, D.; Gentile, T., Simple undirected graphs as formal contexts, (Baixeries, J.; Sacarea, C.; Ojeda-Aciego, M., Proceedings of ICFCA 2015. Proceedings of ICFCA 2015, Lecture Notes in Computer Science, 9113 (2015), Springer), 287-302
[10] Chiaselotti, G.; Ciucci, D.; Gentile, T., Simple graphs in granular computing, Inf. Sci., 340-341, 279-304 (2016)
[13] Chiaselotti, G.; Ciucci, D.; Gentile, T.; Infusino, F., Rough set theory applied to simple undirected graphs, (Ciucci, D.; Wang, G.; Mitra, S.; Wu, W., Proceedings of RSKT 2015. Proceedings of RSKT 2015, Lecture Notes in Computer Science, 9436 (2015), Springer), 423-434
[14] Chiaselotti, G.; Ciucci, D.; Gentile, T.; Infusino, F., Generalizations of rough set tools inspired by graph theory, Fundam. Inform. (2016)
[15] Chiaselotti, G.; Gentile, T.; Infusino, F.; Oliverio, P., Rough sets for \(n\)-cycles and \(n\)-paths, Appl. Math. Inf. Sci., 10, 1, 117-124 (2016)
[16] Dai, J.; Huang, D.; Su, H.; Tian, H.; Yang, T., Uncertainty measurement for covering rough sets, Int. J. Uncertainty Fuzziness Knowl.-Based Syst., 22, 2, 217-234 (2014)
[17] Dai, J.; Tian, H., Entropy measures and granularity measures for set-valued information systems, Inf. Sci., 240, 72-82 (2013)
[18] Date, C., An Introduction to Database Systems (2004), Pearson
[19] Davey, B. A.; Priestley, H. A., Introduction to Lattices and Order (2002), Cambridge University Press: Cambridge University Press New York
[20] Chiaselotti, G.; Ciucci, D.; Gentile, T., Simple graphs in granular computing, Inf. Sci., 340-341, 279-304 (2016)
[21] Ganter, B.; Wille, R., Formal Concept Analysis: Mathematical Foundations (1999), Springer-Verlag: Springer-Verlag Berlin, Heidelberg
[22] Gaume, B.; Navarro, E.; Prade, H., Clustering bipartite graphs in terms of approximate formal concepts and sub-contexts, Int. J. Comput. Intell. Syst., 6, 6, 1125-1142 (2013)
[23] Honko, P., Description and classification of complex structured objects by applying similarity measures, Int. J. Approx. Reasoning, 49, 3, 539-554 (2008)
[24] Honko, P., Relational pattern updating, Inf. Sci., 189, 208-218 (2012)
[25] Honko, P., Association discovery from relational data via granular computing, Inf. Sci., 234, 136-149 (2013)
[26] Hu, X.; Lin, T. Y.; Han, J., A new rough sets model based on database systems, (Verlag, S., Lecture Notes on Artificial Intelligence (2003))
[27] Huang, A.; Lin, Z.; Zhu, W., Matrix approaches to rough sets through vector matroids over fields, IJGCRSIS, 3, 3, 179-194 (2014)
[28] Huang, A.; Zhao, H.; Zhu, W., Nullity-based matroid of rough sets and its application to attribute reduction, Inf. Sci., 263, 153-165 (2014)
[29] Kang, X.; Li, D.; Wang, S.; Qu, K., Formal concept analysis based on fuzzy granularity base for different granulations, Fuzzy Sets Syst., 203, 33-48 (2012)
[31] Lee, T., An information-theoretic analysis of relational databases - part i: data dependencies and metric, IEEE Trans. Softw. Eng., SE-13, 1049-1061 (1987)
[32] Liang, J.; Shi, Z., The information entropy, rough entropy and knowledge granulation in rough set theory, Int. J. Uncertainty Fuzziness Knowl.-Based Syst., 12, 37-46 (2004)
[33] Liau, C. J.; Lin, T. Y., Granular computing and rough sets, The Data Mining and Knowledge Discovery Handbook, 535-561 (2005)
[34] Liau, C. J.; Lin, T. Y., Granular computing and rough sets - an incremental development, Data Mining and Knowledge Discovery Handbook, 445-468 (2010)
[35] Lin, G.; Liang, J.; Qian, Y., Topological approach to multigranulation rough sets, Int. J. Mach. Learn. Cybern., 5, 2, 233-243 (2014)
[36] Lin, T. Y., Data mining: granular computing approach, Methodologies for Knowledge Discovery and Data Mining. Methodologies for Knowledge Discovery and Data Mining, Lecture Notes in Computer Science, 1574, 24-33 (1999)
[37] Lin, T. Y., Data mining and machine oriented modeling: a granular approach, Appl. Intell., 13, 113-124 (2000)
[38] Lin, T. Y., Database mining on derived attributes: granular and rough computing approach, (Alpigini, Z.e.; Skowron, Peters, Lecture Notes on Artificial Intelligence (2002)), 14-32
[39] Lin, T. Y., Fuzzy sets, rough set and probability, (Keller, J.; Nasraoui, O., Annual Meeting of the North American Fuzzy Information Processing Society Proceedings (2002)), 302-305
[40] Lin, T. Y.; Liu, Y.; Huang, W., Unifying rough set theories via large scaled granular computing, Fundam. Inform., 127 (1-4), 413-428 (2013)
[41] Pawlak, Z., Rough Sets. Theoretical Aspects of Reasoning about Data (1991), Kluwer: Kluwer Dordrecht
[42] Pedrycz, A.; Hirota, K.; Pedrycz, W.; Dong, F., Granular representation and granular computing with fuzzy sets, Fuzzy Sets Syst., 203, 17-32 (2012)
[43] Polkowski, L., Mathematical morphology of rough sets, Bull. Polish Acad. Sci. Math., 41, 241-273 (1993)
[44] Polkowski, L., Approximation mathematical morphology. rough set approach, (Skowron, A.; Pal, S., Rough Fuzzy Hybridization. A New Trend in Decision-Making (1999), Springer-Verlag Singapore), 151-162
[45] Polkowski, L., On fractal dimension in information systems. toward exact sets in infinite information systems, Fundam. Inform., 50 (3-4), 305-314 (2002)
[46] Polkowski, L.; Tsumoto, S.; Lin, T. Y., Rough Set Methods and Applications, New Developments in Knowledge Discovery in Information Systems (2000), Springer-Verlag
[47] Qian, Y.; Liang, J.; Yao, Y.; Dang, C., MGRS: a multi-granulation rough set, Inf. Sci., 180, 6, 949-970 (2010)
[48] Qiu, T.; Chen, X.; Liu, Q.; Huang, H., Granular computing approach to finding association rules in relational database, Int. J. Intell. Syst., 25, 2, 165-179 (2010)
[49] Sanahuja, S. M., New rough approximations for \(n\)-cycles and \(n\)-paths, Appl. Math. Comput., 276, 96-108 (2016)
[51] Simmons, H., An Introduction to Category Theory (2011), Cambridge University Press
[52] Simovici, D.; Djeraba, C., Mathematical Tools for Data Mining (2014), Springer-Verlag: Springer-Verlag London
[53] Skowron, A.; Rauszer, C., The discernibility functions matrices and functions in information systems, (Slowinski, R., Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory (1992), Kluwer Academic Publishers), 331-362
[54] Skowron, A.; Wasilewski, P., Information systems in modeling interactive computations on granules, Theor. Comput. Sci., 412, 42, 5939-5959 (2011)
[55] Stanley, R., Enumerative combinatorics. Vol.1, Cambridge Studies in Advanced Mathematics, 49 (2012), Cambridge University Press: Cambridge University Press Cambridge
[56] Stell, J. G., Granulation for graphs, (Freksa, C.; Mark, D. M., Spatial Information Theory: Cognitive and Computational Foundations of Geographic Information Science, International Conference COSIT ’99, Proceedings. Spatial Information Theory: Cognitive and Computational Foundations of Geographic Information Science, International Conference COSIT ’99, Proceedings, Lecture Notes in Computer Science, 1661 (1999), Springer), 417-432
[57] Stell, J. G., Relations in mathematical morphology with applications to graphs and rough sets, (Winter, S.; Duckham, M.; Kulik, L.; Kuipers, B., Spatial Information Theory, 8th International Conference, COSIT 2007, Proceedings. Spatial Information Theory, 8th International Conference, COSIT 2007, Proceedings, Lecture Notes in Computer Science, 4736 (2007), Springer), 438-454
[58] Stell, J. G., Relational granularity for hypergraphs, (Szczuka, M. S.; Kryszkiewicz, M.; Ramanna, S.; Jensen, R.; Hu, Q., Rough Sets and Current Trends in Computing - 7th International Conference, RSCTC 2010, Proceedings. Rough Sets and Current Trends in Computing - 7th International Conference, RSCTC 2010, Proceedings, Lecture Notes in Computer Science, 6086 (2010), Springer), 267-276
[59] Stell, J. G., Relations on hypergraphs, (Kahl, W.; Griffin, T. G., Relational and Algebraic Methods in Computer Science - 13th International Conference, RAMiCS 2012, Proceedings. Relational and Algebraic Methods in Computer Science - 13th International Conference, RAMiCS 2012, Proceedings, Lecture Notes in Computer Science, 7560 (2012), Springer), 326-341
[60] Stell, J. G., Formal concept analysis over graphs and hypergraphs, (Croitoru, M.; Rudolph, S.; Woltran, S.; Gonzales, C., Graph Structures for Knowledge Representation and Reasoning - Third International Workshop, GKR 2013, Revised Selected Papers. Graph Structures for Knowledge Representation and Reasoning - Third International Workshop, GKR 2013, Revised Selected Papers, Lecture Notes in Computer Science, 8323 (2014), Springer), 165-179
[61] Stell, J. G., Symmetric heyting relation algebras with applications to hypergraphs, J. Log. Algebr. Methods Program., 84, 3, 440-455 (2015)
[62] Syau, Y. R.; Fan, J.; Lin, T. Y., Generalized infinitive rough sets based on reflexive relation, IEEE International Conference on Granular Computing (2012)
[63] Tang, J.; She, K.; Min, F.; Zhu, W., A matroidal approach to rough set theory, Theor. Comput. Sci., 471, 1-11 (2013)
[64] Trotter, W. T.; Moore, J. I., Characterization problems for graphs, partially ordered sets, lattices, and families of sets, Discrete Math., 16, 4, 361-381 (1976)
[65] Wang, S.; Zhu, Q.; Zhu, W.; Min, F., Graph and matrix approaches to rough sets through matroids, Inf. Sci., 288, 1-11 (2014)
[66] Wang, S.; Zhu, Q.; Zhu, W.; Min, F., Rough set characterization for 2-circuit matroid, Fundam. Inform., 129, 4, 377-393 (2014)
[67] Wierman, M., Measuring uncertainty in rough set theory, Int. J. Gen. Syst., 28, 283-297 (1999)
[68] Wong, S. K.M.; Ziarko, W.; Ye, R. L., Comparison of rough-set and statistical methods in inductive learning, Int. J. Man-Mach. Stud., 25, 1, 53-72 (1986)
[69] Wu, W.; Leung, Y.; Mi, J., Granular computing and knowledge reduction in formal contexts, IEEE Trans. Knowl. Data Eng., 21, 10, 1461-1474 (2009)
[70] Wu, W.-Z., On some mathematical structures of t-fuzzy rough set algebras in infinite universes of discourse, Fundam. Inform., 108, 337-369 (2011)
[71] Wu, W.-Z.; Xu, Y.-H., On fuzzy rough set algebras in infinite universes, (Wen, P.; Li, Y.; Polkowski, L.; Yao, Y.; Tsumoto, S.; Wang, G., Proceedings of RSKT 2009 (2009)), 312-319
[72] Xie, J.; Lin, T. Y.; Zhu, W., Granular and rough computing on covering, IEEE International Conference on Granular Computing (2012)
[73] Yang, X.; Qian, Y.; Yang, J., Hierarchical structures on multigranulation spaces, J. Comput. Sci. Technol., 27, 6, 1169-1183 (2012)
[74] Yao, J. T.; Yao, Y. Y., A granular computing approach to machine learning, (Wang, L.; Halgamuge, S. K.; Yao, X., FSDK’02, Proceedings of the 1st International Conference on Fuzzy Systems and Knowledge Discovery: Computational Intelligence for the E-Age (2002)), 732-736
[75] Yao, Y., On modeling data mining with granular computing, 25th International Computer Software and Applications Conference (COMPSAC 2001), 638 (2001), IEEE Computer Society
[76] Yao, Y., A partition model of granular computing, Trans. Rough Sets I, I, 232-253 (2004)
[77] (Yao, Y.; Hu, Q.; Yu, H.; Grzymala-Busse, J. W., Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, RSFDGrC 2015, Proceedings. Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, RSFDGrC 2015, Proceedings, Lecture Notes in Computer Science, 9437 (2015), Springer)
[79] Zadeh, L. A., Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic, Fuzzy Sets Syst., 90, 2, 111-127 (1997)
[80] Zhu, W.; Wang, S., Rough matroids based on relations, Inf. Sci., 232, 241-252 (2013)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.