Abstract
Discovering meaningful conceptual structures is a substantial task in data mining and knowledge discovery applications. While off-the-shelf interestingness indices defined in Formal Concept Analysis may provide an effective relevance evaluation in several situations, they frequently give inadequate results when faced with massive formal contexts (and concept lattices), and in the presence of irrelevant concepts. In this paper, we introduce the Conceptual Relevance (\(\mathcal {CR}\)) score, a new scalable interestingness measure for the identification of relevant concepts. From a conceptual perspective, minimal generators provide key information about their associated concept intent. Furthermore, the relevant attributes of a concept are those that maintain the satisfaction of its closure condition. Thus, \(\mathcal {CR}\) exploits the fact that minimal generators and relevant attributes can be efficiently used to assess concept relevance. As such, the \(\mathcal {CR}\) index quantifies both the amount of conceptually relevant attributes and the number of the minimal generators per concept intent. Our experiments on synthetic and real-world datasets show the efficiency of this measure over the well-known stability index.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Available: https://github.com/tomhanika/conexp-clj/tree/dev/testing-data.
A dataset description is given between parenthesis, where \(|\mathcal {G}|\) (resp. \(|\mathcal {M}|\)) is the number of objects (resp. attributes). |L| and n are the lattice size and the number of shared concepts respectively.
References
Buzmakov, A., Kuznetsov, S.O., Napoli, A.: Is concept stability a measure for pattern selection? Procedia Comput. Sci. 31, 918–927 (2014)
Czerniak, J., Zarzycki, H.: Application of rough sets in the presumptive diagnosis of urinary system diseases. In: Sołdek, J., Drobiazgiewicz, L. (eds.) Artificial Intelligence and Security in Computing Systems. SECS, vol. 752, pp. 41–51. Springer, Heidelberg (2003). https://doi.org/10.1007/978-1-4419-9226-0_5
Felde, M., Hanika, T.: Formal context generation using Dirichlet distributions. In: Endres, D., Alam, M., Şotropa, D. (eds.) ICCS 2019. LNCS (LNAI), vol. 11530, pp. 57–71. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-23182-8_5
Felde, M., Hanika, T., Stumme, G.: Null models for formal contexts. Information 11(3), 135 (2020)
Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations. Springer, New York (1999). https://doi.org/10.1007/978-3-642-59830-2Translator-C. Franzke
Klimushkin, M., Obiedkov, S., Roth, C.: Approaches to the selection of relevant concepts in the case of noisy data. In: Kwuida, L., Sertkaya, B. (eds.) ICFCA 2010. LNCS (LNAI), vol. 5986, pp. 255–266. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11928-6_18
Kuznetsov, S.O.: On stability of a formal concept. Ann. Math. Artif. Intell. 49(1), 101–115 (2007). https://doi.org/10.1007/s10472-007-9053-6
Kuznetsov, S.O., Makhalova, T.: On interestingness measures of formal concepts. Inf. Sci. 442, 202–219 (2018)
Lusseau, D., Schneider, K., Boisseau, O.J., Haase, P., Slooten, E., Dawson, S.M.: The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behav. Ecol. Sociobiol. 54(4), 396–405 (2003). https://doi.org/10.1007/s00265-003-0651-y
Morsey, M., Lehmann, J., Auer, S., Stadler, C., Hellmann, S.: Dbpedia and the live extraction of structured data from wikipedia. Program 46(2), 157–181 (2012)
Pfaltz, J.L., Taylor, C.M.: Closed set mining of biological data. In: BIOKDD: Workshop on Data Mining in Bioinformatics, pp. 43–48 (2002)
Pfaltz, J.L., Taylor, C.M.: Scientific knowledge discovery through iterative transformation of concept lattices. In: SIAM Workshop on Discrete Mathematics and Data Mining, Arlington, VA, USA, pp. 1–10 (2002)
Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: AAAI (2015). http://networkrepository.com
Szathmary, L., Valtchev, P., Napoli, A., Godin, R., Boc, A., Makarenkov, V.: A fast compound algorithm for mining generators, closed itemsets, and computing links between equivalence classes. Ann. Math. Artif. Intell. 70(1), 81–105 (2014). https://doi.org/10.1007/s10472-013-9372-8
Acknowledgment
The authors acknowledge the financial support of the Natural Sciences and Engineering Research Council of Canada (NSERC).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Ibrahim, MH., Missaoui, R., Vaillancourt, J. (2021). Conceptual Relevance Index for Identifying Actionable Formal Concepts. In: Braun, T., Gehrke, M., Hanika, T., Hernandez, N. (eds) Graph-Based Representation and Reasoning. ICCS 2021. Lecture Notes in Computer Science(), vol 12879. Springer, Cham. https://doi.org/10.1007/978-3-030-86982-3_9
Download citation
DOI: https://doi.org/10.1007/978-3-030-86982-3_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-86981-6
Online ISBN: 978-3-030-86982-3
eBook Packages: Computer ScienceComputer Science (R0)