Concept lattices reduction: definition, analysis and classification

Abstract

Formal concept analysis (FCA) is currently considered an important formalism for knowledge representation, extraction and analysis with applications in different areas. A problem identified in several applications is the computational cost due to the large number of formal concepts generated. Even when that number is not very large, the essential aspects, those effectively needed, can be immersed in a maze of irrelevant details. In fact, the problem of obtaining a concept lattice of appropriate complexity and size is one of the most important problems of FCA. In literature, several different approaches to control the complexity and size of a concept lattice have been described, but so far they have not been properly analyzed, compared and classified. We propose the classification of techniques for concept lattice reduction in three groups: redundant information removal, simplification, and selection. The main techniques to reduce concept lattice are analyzed and classified based on seven dimensions, each one composed of a set of characteristics. Considerations are made about the applicability and computational complexity of approaches of different classes.

Keywords

  • Formal concept analysis;
  • Concept lattices;
  • Reduction

Dias, Sérgio M.; Vieira, N. J. Concept lattices reduction: Definition, analysis and classification. Expert Systems with Applications, v. 42, p. 7084-7097, 2015. DOI: http://dx.doi.org/10.1016/j.eswa.2015.04.044

Advertisements

Author: Sérgio M Dias

Dr. Sérgio M. Dias is a computer analyst of Federal Service of Data Processing (SERPRO) and Postdoc in Computer Science of Pontifical Catholic University of Minas Gerais (PUC Minas). He is Phd and MSc in Computer Science from Federal University of Minas Gerais (UFMG) in 2016 and 2010. B.S. degree in Computer Science from PUC Minas in 2007.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s