Generating a catalog of unanticipated schemas in class hierarchies using Formal Concept Analysis

ContextInheritance is the cornerstone of object-oriented development, supporting conceptual modeling, subtype polymorphism and software reuse. But inheritance can be used in subtle ways that make complex systems hard to understand and extend, due to the presence of implicit dependencies in the inheritance hierarchy.ObjectiveAlthough these dependencies often specify well-known schemas (i.e., recurrent design or coding patterns, such as hook and template methods), new unanticipated dependency schemas arise in practice, and can consequently be hard to recognize and detect. Thus, a developer making changes or extensions to an object-oriented system needs to understand these implicit contracts defined by the dependencies between a class and its subclasses, or risk that seemingly innocuous changes break them.MethodTo tackle this problem, we have developed an approach based on Formal Concept Analysis. Our Formal Concept Analysis based-Reverse Engineering methodology (FoCARE) identifies undocumented hierarchical dependencies in a hierarchy by taking into account the existing structure and behavior of classes and subclasses.ResultsWe validate our approach by applying it to a large and non-trivial case study, yielding a catalog of hierarchy schemas, each one composed of a set of dependencies over methods and attributes in a class hierarchy. We show how the discovered dependency schemas can be used not only to identify good design practices, but also to expose bad smells in design, thereby helping developers in initial reengineering phases to develop a first mental model of a system. Although some of the identified schemas are already documented in existing literature, with our approach based on Formal Concept Analysis (FCA), we are also able to identify previously unidentified schemas.ConclusionsFCA is an effective tool because it is an ideal classification mining tool to identify commonalities between software artifacts, and usually these commonalities reveal known and unknown characteristics of the software artifacts. We also show that once a catalog of useful schemas stabilizes after several runs of FoCARE, the added cost of FCA is no longer needed.     

A semantic approach to concept lattice-based information retrieval

The volume of available information is growing, especially on the web, and in parallel the questions of the users are changing and becoming harder to satisfy. Thus there is a need for organizing the available information in a meaningful way in order to guide and improve document indexing for information retrieval applications taking into account more complex data such as semantic relations. In this paper we show that Formal Concept Analysis (FCA) and concept lattices provide a suitable and powerful support for such a task. Accordingly, we use FCA to compute a concept lattice, which is considered both a semantic index to organize documents and a search space to model terms. We introduce the notions of cousin concepts and classification-based reasoning for navigating the concept lattice and retrieve relevant information based on the content of concepts. Finally, we detail a real-world experiment and show that the present approach has very good capabilities for semantic indexing and document retrieval.     

Formal concept analysis in knowledge processing: A survey on applications

This is the second part of a large survey paper in which we analyze recent literature on Formal Concept Analysis (FCA) and some closely related disciplines using FCA. We collected 1072 papers published between 2003 and 2011 mentioning terms related to Formal Concept Analysis in the title, abstract and keywords. We developed a knowledge browsing environment to support our literature analysis process. We use the visualization capabilities of FCA to explore the literature, to discover and conceptually represent the main research topics in the FCA community. In this second part, we zoom in on and give an extensive overview of the papers published between 2003 and 2011 which applied FCA-based methods for knowledge discovery and ontology engineering in various application domains. These domains include software mining, web analytics, medicine, biology and chemistry data.     

Extending conceptualisation modes for generalised Formal Concept Analysis

Formal Concept Analysis (FCA) is an exploratory data analysis technique for boolean relations based on lattice theory. Its main result is the existence of a dual order isomorphism between two set lattices induced by a binary relation between a set of objects and a set of attributes. Pairs of dually isomorphic sets of objects and attributes, called formal concepts, form a concept lattice, but actually model only a conjunctive mode of conceptualisation.In this paper we augment this formalism in two ways: first we extend FCA to consider different modes of conceptualisation by changing the basic dual isomorphism in a modal-logic motivated way. This creates the three new types of concepts and lattices of extended FCA, viz., the lattice of neighbourhood of objects, that of attributes and the lattice of unrelatedness.Second, we consider incidences with values in idempotent semirings—concretely the completed max-plus or schedule algebra —and focus on generalising FCA to try and replicate the modes of conceptualisation mentioned above.To provide a concrete example of the use of these techniques, we analyse the performance of multi-class classifiers by conceptually analysing their confusion matrices.     

Characterizing functional dependencies in formal concept analysis with pattern structures

Computing functional dependencies from a relation is an important database topic, with many applications in database management, reverse engineering and query optimization. Whereas it has been deeply investigated in those fields, strong links exist with the mathematical framework of Formal Concept Analysis. Considering the discovery of functional dependencies, it is indeed known that a relation can be expressed as the binary relation of a formal context, whose implications are equivalent to those dependencies. However, this leads to a new data representation that is quadratic in the number of objects w.r.t. the original data. Here, we present an alternative avoiding such a data representation and show how to characterize functional dependencies using the formalism of pattern structures, an extension of classical FCA to handle complex data. We also show how another class of dependencies can be characterized with that framework, namely, degenerated multivalued dependencies. Finally, we discuss and compare the performances of our new approach in a series of experiments on classical benchmark datasets.     

FUZZY CLUSTERING-BASED FORMAL CONCEPT ANALYSIS FOR ASSOCIATION RULES MINING

Formal Concept Analysis (FCA), in which data is represented as a formal context, offers a framework for Association Rules Mining (ARM) by handling functional dependencies in the data. However, with the size of the formal context, the number of rules grows exponentially. In this article, we apply Fuzzy K-Means clustering on the data set to reduce the formal context and FCA on the reduced data set for mining association rules. With experiments on two real-world healthcare data sets, we offer the evidence for performance of FKM-based FCA in mining association rules.     

Formal Concept Analysis in knowledge processing: A survey on models and techniques

This is the first part of a large survey paper in which we analyze recent literature on Formal Concept Analysis (FCA) and some closely related disciplines using FCA. We collected 1072 papers published between 2003 and 2011 mentioning terms related to Formal Concept Analysis in the title, abstract and keywords. We developed a knowledge browsing environment to support our literature analysis process. We use the visualization capabilities of FCA to explore the literature, to discover and conceptually represent the main research topics in the FCA community. In this first part, we zoom in on and give an extensive overview of the papers published between 2003 and 2011 on developing FCA-based methods for knowledge processing. We also give an overview of the literature on FCA extensions such as pattern structures, logical concept analysis, relational concept analysis, power context families, fuzzy FCA, rough FCA, temporal and triadic concept analysis and discuss scalability issues.     

Ontology-based concept similarity in Formal Concept Analysis

Both domain ontologies and Formal Concept Analysis (FCA) aim at modeling concepts, although with different purposes. In the literature, a promising research area concerns the role of FCA in ontology engineering, in particular, in supporting the critical task of reusing independently developed domain ontologies. With this regard, the possibility of evaluating concept similarity is acquiring an increasing relevance, since it allows the identification of different concepts that are semantically close. In this paper, an ontology-based method for assessing similarity between FCA concepts is proposed. Such a method is intended to support the ontology engineer in difficult activities that are becoming fundamental in the development of the Semantic Web, such us ontology merging and ontology mapping and, in particular, it can be used in parallel to existing semi-automatic tools relying on FCA.     

Fuzzy and rough formal concept analysis: a survey

Formal Concept Analysis (FCA) is a mathematical technique that has been extensively applied to Boolean data in knowledge discovery, information retrieval, web mining, etc. applications. During the past years, the research on extending FCA theory to cope with imprecise and incomplete information made significant progress. In this paper, we give a systematic overview of the more than 120 papers published between 2003 and 2011 on FCA with fuzzy attributes and rough FCA. We applied traditional FCA as a text-mining instrument to 1072 papers mentioning FCA in the abstract. These papers were formatted in pdf files and using a thesaurus with terms referring to research topics, we transformed them into concept lattices. These lattices were used to analyze and explore the most prominent research topics within the FCA with fuzzy attributes and rough FCA research communities. FCA turned out to be an ideal metatechnique for representing large volumes of unstructured texts.     

Mining gene expression data with pattern structures in formal concept analysis

This paper addresses the important problem of efficiently mining numerical data with formal concept analysis (FCA). Classically, the only way to apply FCA is to binarize the data, thanks to a so-called scaling procedure. This may either involve loss of information, or produce large and dense binary data known as hard to process. In the context of gene expression data analysis, we propose and compare two FCA-based methods for mining numerical data and we show that they are equivalent. The first one relies on a particular scaling, encoding all possible intervals of attribute values, and uses standard FCA techniques. The second one relies on pattern structures without a priori transformation, and is shown to be more computationally efficient and to provide more readable results. Experiments with real-world gene expression data are discussed and give a practical basis for the comparison and evaluation of the methods.     

Collaborative Recommending using Formal Concept Analysis

We show how Formal Concept Analysis (FCA) can be applied to Collaborative Recommenders. FCA is a mathematical method for analysing binary relations. Here we apply it to the relation between users and items in a collaborative recommender system. FCA groups the users and items into concepts, ordered by a concept lattice. We present two new algorithms for finding neighbours in a collaborative recommender. Both use the concept lattice as an index to the recommender’s ratings matrix. Our experimental results show a major decrease in the amount of work needed to find neighbours, while guaranteeing no loss of accuracy or coverage.     

Formal concept analysis for topic detection: A clustering quality experimental analysis

The Topic Detection task is focused on discovering the main topics addressed by a series of documents (e.g., news reports, e-mails, tweets). Topics, defined in this way, are expected to be thematically similar, cohesive and self-contained. This task has been broadly studied from the point of view of clustering and probabilistic techniques. In this work, we propose for this task the application of Formal Concept Analysis (FCA), an exploratory technique for data analysis and organization. In particular, we propose an extension of FCA-based methods for topic detection applied in the literature by applying the stability concept for the topic selection. The hypothesis is that FCA will enable the better organization of the data and stability the better selection of topics based on this data organization, thus better fulfilling the task requirements by improving the quality and accuracy of the topic detection process. In addition, the proposed FCA-based methodology is able to cope with some well-known drawbacks that clustering and probabilistic methodologies present, such as: the need to set a predefined number of clusters or the difficulty in dealing with topics with complex generalization-specialization relationships. In order to prove this hypothesis, the FCA operation is compared to other established techniques — Hierarchical Agglomerative Clustering (HAC) and Latent Dirichlet Allocation (LDA). To allow this comparison, these approaches have been implemented by the authors in a novel experimental framework. The quality of the topics detected by the different approaches in terms of their suitability for the topic detection task is evaluated by means of internal clustering validity metrics. This evaluation demonstrates that FCA generates cohesive clusters, which are less subject to changes in cluster granularity. Driven by the quality of the detected topics, FCA achieves the best general outcome, improving the experimental results for Topic Detection Task at the 2013 Replab Campaign.     

The Chu construction and generalized formal concept analysis

We continue studying the connections between the Chu construction on the category ChuCors of formal contexts and Chu correspondences, and generalizations of Formal Concept Analysis (FCA). All the required constructions like categorical product, tensor product, together with its bifunctor properties are introduced and proved. The final section focuses on how the second-order generalization of FCA can be built up in terms of the Chu construction.     

Gene interaction – An evolutionary biclustering approach

DNA Microarray experiments form a powerful tool for studying gene expression patterns, in large scale. Sharing of the regulatory mechanism among genes, in an organism, is predominantly responsible for their co-expression. Biclustering aims at finding a subset of similarly expressed genes under a subset of experimental conditions. A small number of genes participate in a cellular process of interest. Again, a gene may be simultaneously involved in a number of cellular processes. In cellular environment, genes interact among themselves to produce enzymes, metabolites, proteins, etc. responsible for a particular function(s).In this study, a simple and novel correlation-based approach is proposed to extract gene interaction networks from biclusters in microarray data. Local search strategy is employed to add (remove) relevant (irrelevant) genes for finer tuning, in multi-objective biclustering framework. Preprocessing is done to preserve strongly correlated gene interaction pairs. Experimental results on time-series gene expression data from Yeast are biologically validated using benchmark databases and literature.     

A new FCA algorithm enabling analyzing of complex and dynamic data sets

Analyzing data with the use of Formal Concept Analysis (FCA) enables complex insights into hidden relationships between objects and features in a studied system. Several improvements in this research area, such as Fuzzy FCA or L-Fuzzy Concepts, bring the possibility to analyze data with a certain rate of indeterminacy. However, the usage of FCA on larger complex data brings several problems relating to the time-complexities of FCA algorithms and the size of generated concept lattices. The fuzzyfication of FCA emphasizes the mentioned problems. This article describes significant improvements of a selected FCA algorithm. The primary focus was given on the system of an effective data storage. The binary data was stored with the use of finite automata that leads to the lower memory consumption. Moreover, the better querying performance was achieved. Next, we focused on the inner process of the computation of all formal concepts. All improvements were integrated into a new FCA algorithm that can be used to analyze more complex data sets.     

Similarity reasoning for the semantic web based on fuzzy concept lattices: An informal approach

Similarity Reasoning in the presence of vague information is becoming fundamental in several research areas and, in particular, in the Semantic Web. Fuzzy Formal Concept Analysis (FFCA) is a generalization of Formal Concept Analysis (FCA) for modeling uncertainty information. Although FFCA has become very interesting for supporting different activities for the development of the Semantic Web, in the literature it is usually addressed at a technical level and intended for a restricted audience. This paper proposes a similarity measure for FFCA concepts. The key notions underlying the proposed approach are presented informally, in order to reach a broad audience of readers.     

Design principles for the General Data Protection Regulation (GDPR): A formal concept analysis and its evaluation

Data and software are nowadays one and the same: for this very reason, the European Union (EU) and other governments introduce frameworks for data protection — a key example being the General Data Protection Regulation (GDPR). However, GDPR compliance is not straightforward: its text is not written by software or information engineers but rather, by lawyers and policy-makers. As a design aid to information engineers aiming for GDPR compliance, as well as an aid to software users’ understanding of the regulation, this article offers a systematic synthesis and discussion of it, distilled by the mathematical analysis method known as Formal Concept Analysis (FCA). By its principles, GDPR is synthesised as a concept lattice, that is, a formal summary of the regulation, featuring 144372 records — its uses are manifold. For example, the lattice captures so-called attribute implications, the implicit logical relations across the regulation, and their intensity. These results can be used as drivers during systems and services (re-)design, development, operation, or information systems’ refactoring towards more GDPR consistency.     

Generalized pattern extraction from concept lattices

In this paper, we show how the existence of taxonomies on objects and/or attributes can be used in Formal Concept Analysis to help discover generalized concepts. To that end, we analyze three generalization cases ( ?, ?, and α) and present different scenarios of a simultaneous generalization on both objects and attributes. We also discuss the cardinality of the generalized pattern set against the number of simple patterns produced from the initial data set.