nach oben

Erschienen in:

2022 | OriginalPaper | Buchkapitel

9. Formal Methods in FCA and Big Data

verfasst von : Domingo López-Rodríguez, Emilio Muñoz-Velasco, Manuel Ojeda-Aciego

Erschienen in: Complex Data Analytics with Formal Concept Analysis

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Formal Concept Analysis (FCA) plays an important role in knowledge representation and knowledge discovery, and has generated an increasingly growing research field. The use of FCA in the context of big data provides a basis for better interpretability and explainability of results, usually lacking in other statistical approaches to data analysis; however, scalability is an important issue for FCA logic-based tools and techniques, such as the generation and use of implicational systems. We survey the theoretical and technical foundations of some trends in FCA. Specifically, we present a summary of promising theoretical and practical applications of FCA that could be used to solve the problem of dealing with big data. Furthermore, we propose some directions for future research to solve this problem.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Scalable Visual Analytics in FCA

Nächstes Kapitel Towards Distributivity in FCA for Phylogenetic Data

Adaricheva, K.V., Nation, J.B., Rand, R.: Ordered direct implicational basis of a finite closure system. Discrete Applied Mathematics 161(6), 707–723 (2013)MathSciNetMATHCrossRef

Agrawal, R., Srikant, R.: Fast algorithms for mining association rules in large databases. In: VLDB, pp. 487–499. Morgan Kaufmann (1994)

Angluin, D.: Queries and concept learning. Mach. Learn. 2(4), 319–342 (1987)MathSciNetMATH

Armstrong, W.W.: Dependency structures of data base relationships. In: J.L. Rosenfeld (ed.) Information Processing, Proceedings of the 6th IFIP Congress 1974, Stockholm, Sweden, August 5–10, 1974., pp. 580–583. North-Holland (1974)

Atzeni, P., Antonellis, V.D.: Relational Database Theory. Benjamin/Cummings (1993)

Babin, M.A.: Models, methods, and programs for generating relationships from a lattice of closed sets. Ph.D. thesis, Higher School of Economics, Moscow (2012)

Babin, M.A., Kuznetsov, S.O.: Computing premises of a minimal cover of functional dependencies is intractable. Discrete Applied Mathematics 161(6), 742–749 (2013)MathSciNetMATHCrossRef

Bastide, Y., Pasquier, N., Taouil, R., Stumme, G., Lakhal, L.: Mining minimal non-redundant association rules using frequent closed itemsets. In: Computational Logic, Lecture Notes in Computer Science, vol. 1861, pp. 972–986. Springer (2000)

Belohlavek, R., Cordero, P., Enciso, M., Mora, Á., Vychodil, V.: Automated prover for attribute dependencies in data with grades. International Journal of Approximate Reasoning 70, 51–67 (2016)MathSciNetMATHCrossRef

10.

Belohlávek, R., Macko, J.: Selecting important concepts using weights. In: ICFCA, Lecture Notes in Computer Science, vol. 6628, pp. 65–80. Springer (2011)

11.

Belohlávek, R., Outrata, J., Trnecka, M.: Factorizing boolean matrices using formal concepts and iterative usage of essential entries. Inf. Sci. 489, 37–49 (2019)MathSciNetMATHCrossRef

12.

Belohlávek, R., Vychodil, V.: Formal concept analysis with constraints by closure operators. In: ICCS, Lecture Notes in Computer Science, vol. 4068, pp. 131–143. Springer (2006)

13.

Belohlávek, R., Vychodil, V.: Discovery of optimal factors in binary data via a novel method of matrix decomposition. J. Comput. Syst. Sci. 76(1), 3–20 (2010)MathSciNetMATHCrossRef

14.

Belohlávek, R., Vychodil, V.: Closure-based constraints in formal concept analysis. Discrete Applied Mathematics 161(13–14), 1894–1911 (2013)MathSciNetMATHCrossRef

15.

Benítez-Caballero, M.J., Medina, J., Ramírez-Poussa, E.: Attribute reduction in rough set theory and formal concept analysis. In: IJCRS (2), Lecture Notes in Computer Science, vol. 10314, pp. 513–525. Springer (2017)

16.

Benito-Picazo, F., Cordero, P., Enciso, M., Mora, A.: Minimal generators, an affordable approach by means of massive computation. The Journal of Supercomputing 75(3), 1350–1367 (2019)CrossRef

17.

Bertet, K., Monjardet, B.: The multiple facets of the canonical direct unit implicational basis. Theoretical Computer Science 411(22–24), 2155–2166 (2010)MathSciNetMATHCrossRef

18.

Bertet, K., Nebut, M.: Efficient algorithms on the moore family associated to an implicational system. Discrete Mathematics and Theoretical Computer Science 6(315–338), 107 (2004)MathSciNetMATH

19.

Borchmann, D.: Learning terminological knowledge with high confidence from erroneous data. Ph.D. thesis, Saechsische Landesbibliothek-Staats-und Universitaetsbibliothek Dresden (2014)

20.

Borchmann, D., Hanika, T., Obiedkov, S.: On the usability of probably approximately correct implication bases. In: ICFCA, Lecture Notes in Computer Science, vol. 10308, pp. 72–88. Springer (2017)

21.

Boulicaut, J., Bykowski, A., Rigotti, C.: Free-sets: A condensed representation of boolean data for the approximation of frequency queries. Data Min. Knowl. Discov. 7(1), 5–22 (2003)MathSciNetCrossRef

22.

Caruana, R., Lou, Y., Gehrke, J., Koch, P., Sturm, M., Elhadad, N.: Intelligible models for healthcare: Predicting pneumonia risk and hospital 30-day readmission. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1721–1730. ACM (2015)

23.

Cheung, K.S.K., Vogel, D.R.: Complexity reduction in lattice-based information retrieval. Inf. Retr. 8(2), 285–299 (2005)CrossRef

24.

Codocedo, V., Taramasco, C., Astudillo, H.: Cheating to achieve formal concept analysis over a large formal context. In: CLA, CEUR Workshop Proceedings, vol. 959, pp. 349–362. CEUR-WS.org (2011)

25.

Cordero, P., Enciso, M., López, D., Mora, A.: A conversational recommender system for diagnosis using fuzzy rules. Expert Systems with Applications p. 113449 (2020)

26.

Cordero, P., Enciso, M., Mora, A.: Directness in fuzzy formal concept analysis. In: Proc. of the 17th Intl Conf on Information Processing and Management of Uncertainty in Knowledge-Bases IPMU’18, Communications in Computer and Information Science, vol. 853, pp. 585–595 (2018)CrossRef

27.

Cordero, P., Enciso, M., Mora, A., de Guzmán, I.P.: SL_FD logic: Elimination of data redundancy in knowledge representation. In: Ibero-American Conference on Artificial Intelligence, pp. 141–150. Springer (2002)

28.

Cordero, P., Enciso, M., Mora, A., Ojeda-Aciego, M.: Computing minimal generators from implications: a logic-guided approach. In: CLA, vol. 2012, pp. 187–198. Citeseer (2012)

29.

Cordero, P., Enciso, M., Mora, A., Ojeda-Aciego, M.: Computing left-minimal direct basis of implications. In: CLA, vol. 2013, pp. 293–298 (2013)

30.

Cordero, P., Enciso, M., Mora, A., Ojeda-Aciego, M., Rossi, C.: Knowledge discovery in social networks by using a logic-based treatment of implications. Knowl.-Based Syst. 87, 16–25 (2015)CrossRef

31.

Dias, S.M., Vieira, N.J.: Concept lattices reduction: Definition, analysis and classification. Expert Syst. Appl. 42(20), 7084–7097 (2015)CrossRef

32.

Dias, S.M., Z’arate, L.E., Vieira, N.J.: Using iceberg concept lattices and implications rules to extract knowledge from ANN. Intelligent Automation & Soft Computing 19(3), 361–372 (2013)CrossRef

33.

Distel, F.: Hardness of enumerating pseudo-intents in the lectic order. In: International Conference on Formal Concept Analysis, pp. 124–137. Springer (2010)

34.

Distel, F., Sertkaya, B.: On the complexity of enumerating pseudo-intents. Discrete Applied Mathematics 159(6), 450–466 (2011)MathSciNetMATHCrossRef

35.

Dong, G., Jiang, C., Pei, J., Li, J., Wong, L.: Mining succinct systems of minimal generators of formal concepts. In: DASFAA, Lecture Notes in Computer Science, vol. 3453, pp. 175–187. Springer (2005)

36.

Dumbill, E.: What is big data? an introduction to the big data landscape. Strata 2012: Making Data Work (2012)

37.

Gajdos, P., Moravec, P., Snásel, V.: Concept lattice generation by singular value decomposition. In: CLA, CEUR Workshop Proceedings, vol. 110. CEUR-WS.org (2004)

38.

Ganter, B., Wille, R.: Formal Concept Analysis - Mathematical Foundations. Springer (1999)

39.

Geerts, F., Missier, P., Paton, N.W.: Editorial: Special issue on improving the veracity and value of big data. J. Data and Information Quality 9(3), 13:1–13:2 (2018)

40.

Grünwald, P.D., Grunwald, A.: The minimum description length principle. MIT press (2007)

41.

Guigues, J.L., Duquenne, V.: Familles minimales d’implications informatives résultant d’un tableau de données binaires. Mathématiques et Sciences humaines 95, 5–18 (1986)

42.

Hanika, T., Koyda, M., Stumme, G.: Relevant attributes in formal contexts. In: ICCS, Lecture Notes in Computer Science, vol. 11530, pp. 102–116. Springer (2019)

43.

Ibaraki, T., Kogan, A., Makino, K.: Inferring minimal functional dependencies in horn and q-horn theories. Ann. Math. Artif. Intell. 38(4), 233–255 (2003)MathSciNetMATHCrossRef

44.

Kauer, M., Krupka, M.: Removing an incidence from a formal context. In: CLA, CEUR Workshop Proceedings, vol. 1252, pp. 195–206. CEUR-WS.org (2014)

45.

Khardon, R.: Translating between horn representations and their characteristic models. Journal of Artificial Intelligence Research 3, 349–372 (1995)MATHCrossRef

46.

Kim, B.: Interactive and interpretable machine learning models for human machine collaboration. Ph.D. thesis, Massachusetts Institute of Technology (2015)

47.

Kim, B., Khanna, R., Koyejo, O.O.: Examples are not enough, learn to criticize! criticism for interpretability. In: Advances in Neural Information Processing Systems, pp. 2280–2288 (2016)

48.

Konecny, J.: On attribute reduction in concept lattices: Methods based on discernibility matrix are outperformed by basic clarification and reduction. Inf. Sci. 415, 199–212 (2017)MATHCrossRef

49.

Konecny, J., Krajca, P.: On attribute reduction in concept lattices: The polynomial time discernibility matrix-based method becomes the cr-method. Inf. Sci. 491, 48–62 (2019)MathSciNetMATHCrossRef

50.

Kumar, C.A., Dias, S.M., Vieira, N.J.: Knowledge reduction in formal contexts using non-negative matrix factorization. Mathematics and Computers in Simulation 109, 46–63 (2015)MathSciNetMATHCrossRef

51.

Kuznetsov, S.O.: On the intractability of computing the duquenne-guigues basis. J. UCS 10(8), 927–933 (2004)MathSciNetMATH

52.

Kuznetsov, S.O., Makhalova, T.P.: On interestingness measures of formal concepts. Inf. Sci. 442–443, 202–219 (2018)MathSciNetMATHCrossRef

53.

Lorenzo, E.R., Cordero, P., Enciso, M., Bonilla, A.M.: Canonical dichotomous direct bases. Inf. Sci. 376, 39–53 (2017)MATHCrossRef

54.

Maier, D.: The Theory of Relational Databases. Computer Science Press (1983)

55.

Medina, J.: Relating attribute reduction in formal, object-oriented and property-oriented concept lattices. Computers & Mathematics with Applications 64(6), 1992–2002 (2012)MathSciNetMATHCrossRef

56.

Miller, T.: Explanation in artificial intelligence: Insights from the social sciences. Artificial Intelligence 267, 1–38 (2019)MathSciNetMATHCrossRef

57.

Missaoui, R., Nourine, L., Renaud, Y.: An inference system for exhaustive generation of mixed and purely negative implications from purely positive ones. In: M. Kryszkiewicz, S.A. Obiedkov (eds.) Proceedings of the 7th International Conference on Concept Lattices and Their Applications, Sevilla, Spain, October 19–21, 2010, CEUR Workshop Proceedings, vol. 672, pp. 271–282. CEUR-WS.org (2010)

58.

Missaoui, R., Nourine, L., Renaud, Y.: Computing implications with negation from a formal context. Fundam. Inform. 115(4), 357–375 (2012)MathSciNetMATHCrossRef

59.

Mora, A., Cordero, P., Enciso, M., Fortes, I., Aguilera, G.: Closure via functional dependence simplification. International Journal of Computer Mathematics 89(4), 510–526 (2012)MathSciNetMATHCrossRef

60.

Mora, A., Enciso, M., Cordero, P., de Guzmán, I.P.: An efficient preprocessing transformation for functional dependencies sets based on the substitution paradigm. In: Conference on Technology Transfer, pp. 136–146. Springer (2003)

61.

Nishio, N., Mutoh, A., Inuzuka, N.: On computing minimal generators in multi-relational data mining with respect to θ-subsumption. In: ILP (Late Breaking Papers), CEUR Workshop Proceedings, vol. 975, pp. 50–55. CEUR-WS.org (2012)

62.

Osicka, P., Trnecka, M.: Boolean matrix decomposition by formal concept sampling. In: CIKM, pp. 2243–2246. ACM (2017)

63.

Pawlak, Z.: Rough sets. Int. J. Parallel Program. 11(5), 341–356 (1982)MATH

64.

Pfaltz, J.L.: Incremental transformation of lattices: A key to effective knowledge discovery. In: ICGT, Lecture Notes in Computer Science, vol. 2505, pp. 351–362. Springer (2002)

65.

Polanyi, M.: The Tacit Dimension. Doubleday, Garden City, NY (1966)

66.

Portugal, I., Alencar, P.S.C., Cowan, D.D.: The use of machine learning algorithms in recommender systems: A systematic review. Expert Syst. Appl. 97, 205–227 (2018)CrossRef

67.

Qi, J.J.: Attribute reduction in formal contexts based on a new discernibility matrix. Journal of applied mathematics and computing 30(1–2), 305–314 (2009)MathSciNetMATHCrossRef

68.

Rodríguez-Lorenzo, E., Adaricheva, K.V., Cordero, P., Enciso, M., Mora, A.: Formation of the d-basis from implicational systems using simplification logic. Int. J. General Systems 46(5), 547–568 (2017)MathSciNetCrossRef

69.

Rodríguez-Lorenzo, E., Bertet, K., Cordero, P., Enciso, M., Mora, Á.: Direct-optimal basis computation by means of the fusion of simplification rules. Discrete Applied Mathematics 249, 106–119 (2018)MathSciNetMATHCrossRef

70.

Rodríguez-Lorenzo, E., Bertet, K., Cordero, P., Enciso, M., Mora, A., Ojeda-Aciego, M.: From implicational systems to direct-optimal bases: A logic-based approach. Applied Mathematics & Information Sciences. L 2, 305–317 (2015)MathSciNet

71.

Rudolph, S.: Using FCA for encoding closure operators into neural networks. Lecture Notes in Computer Science 4604, 321–332 (2007)MATHCrossRef

72.

Stumme, G., Taouil, R., Bastide, Y., Pasquier, N., Lakhal, L.: Computing iceberg concept lattices with Titanic. Data Knowl. Eng. 42(2), 189–222 (2002)MATHCrossRef

73.

Valverde-Albacete, F.J., Peláez-Moreno, C., Cordero, P., Ojeda-Aciego, M.: Formal equivalence analysis. In: 2019 Conference of the International Fuzzy Systems Association and the European Society for Fuzzy Logic and Technology (EUSFLAT 2019). Atlantis Press (2019)

74.

Wei, W., Wu, X., Liang, J., Cui, J., Sun, Y.: Discernibility matrix based incremental attribute reduction for dynamic data. Knowl.-Based Syst. 140, 142–157 (2018)CrossRef

75.

Zhang, S., Guo, P., Zhang, J., Wang, X., Pedrycz, W.: A completeness analysis of frequent weighted concept lattices and their algebraic properties. Data Knowl. Eng. 81–82, 104–117 (2012)CrossRef

76.

Zhang, W., Wei, L., Qi, J.: Attribute reduction theory and approach to concept lattice. Science in China Series F: Information Sciences 48(6), 713–726 (2005)MathSciNetMATH

Titel: Formal Methods in FCA and Big Data
verfasst von: Domingo López-Rodríguez
Emilio Muñoz-Velasco
Manuel Ojeda-Aciego
Verlag: Springer International Publishing
Buch: Complex Data Analytics with Formal Concept Analysis
Print ISBN: 978-3-030-93277-0

Electronic ISBN: 978-3-030-93278-7

Copyright-Jahr: 2022
DOI: https://doi.org/10.1007/978-3-030-93278-7_9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"