In this paper we revisit the problem of computing the closure of a set of attributes given a basis of dependencies or implications. This problem is of main interest in logics, in the relational database model, in lattice theory, and in Formal Concept Analysis as well. A basis of dependencies may have different characteristics, among which being “minimal”, e.g., the DG-Basis, or being “direct”, e.g., the Canonical-Direct Unit Basis and the D -base. Here we propose an extensive and experimental study of the impacts of minimality and directness on the closure algorithms. The results of the experiments performed on real and synthetic datasets are analyzed in depth, and suggest a different and fresh look at computing the closure of a set of attributes w.r.t. a basis of dependencies.

Counterfactual visual explanations are aimed at identifying changes in an image that will modify the prediction of a classifier.Unlike adversarial images, counterfactuals are required to be realistic.For this reason generative models such as variational autoencoders (VAE) have been used to restrain the search of counterfactuals on the data manifold.However such gradient-based approaches remain limited even when they deal with simple datasets such as MNIST.Conjecturing that these limitations result from a plateau effect which makes the gradient noisy and less informative, we improve the gradient estimation by training an ensemble of classifiers directly in the latent space of VAEs.Several experiments show that the resulting method called Clarity delivers counterfactual images of high-quality, competitive with the state-of-the-art.

In this paper, we revisit pattern mining and study the distribution underlying a binary dataset thanks to the closure structure which is based on passkeys, i.e., minimum generators in equivalence classes robust to noise. We introduce △-closedness, a generalization of the closure operator, where △ measures how a closed set differs from its upper neighbors in the partial order induced by closure. A △-class of equivalence includes minimum and maximum elements and allows us to characterize the distribution underlying the data. Moreover, the set of △-classes of equivalence can be partitioned into the so-called △-closure structure. In particular, a △-class of equivalence with a high △ is supported by more observations and thus is more stable. In the experiments, we study the △-closure structure of several real-world datasets and show that this structure is very stable for large △ and does not substantially depend on the data sampling used for the analysis.

Abstract Pattern mining is well established in data mining research, especially for mining binary datasets. Surprisingly, there is much less work about numerical pattern mining and this research area remains under-explored. In this paper we proposeMint, an efficient MDL-based algorithm for mining numerical datasets. The MDL principle is a robust and reliable framework widely used in pattern mining, and as well in subgroup discovery. InMintwe reuse MDL for discovering useful patterns and returning a set of non-redundant overlapping patterns with well-defined boundaries and covering meaningful groups of objects.Mintis not alone in the category of numerical pattern miners based on MDL. In the experiments presented in the paper we show thatMintoutperforms competitors among which IPD,RealKrimp, andSlim.

Unintended biases in machine learning (ML) models are among the major concerns that must be addressed to maintain public trust in ML. In this paper, we address process fairness of ML models that consists in reducing the dependence of models on sensitive features, without compromising their performance. We revisit the framework FixOut that is inspired in the approach “fairness through unawareness” to build fairer models. We introduce several improvements such as automating the choice of FixOut's parameters. Also, FixOut was originally proposed to improve fairness of ML models on tabular data. We also demonstrate the feasibility of FixOut's workflow for models on textual data. We present several experimental results that illustrate the fact that FixOut improves process fairness on different classification settings.

Pattern Mining (PM) has a prominent place in Data Science and finds its application in a wide range of domains. To avoid the exponential explosion of patterns different methods have been proposed. They are based on assumptions on interestingness and usually return very different pattern sets. In this paper we propose to use a compression-based objective as a well-justified and robust interestingness measure. We define the description lengths for datasets and use the Minimum Description Length principle (MDL) to find patterns that ensure the best compression. Our experiments show that the application of MDL to numerical data provides a small and characteristic subsets of patterns describing data in a compact way.

BACKGROUND: Pharmacogenomics (PGx) studies how genomic variations impact variations in drug response phenotypes. Knowledge in pharmacogenomics is typically composed of units that have the form of ternary relationships gene variant - drug - adverse event. Such a relationship states that an adverse event may occur for patients having the specified gene variant and being exposed to the specified drug. State-of-the-art knowledge in PGx is mainly available in reference databases such as PharmGKB and reported in scientific biomedical literature. But, PGx knowledge can also be discovered from clinical data, such as Electronic Health Records (EHRs), and in this case, may either correspond to new knowledge or confirm state-of-the-art knowledge that lacks "clinical counterpart" or validation. For this reason, there is a need for automatic comparison of knowledge units from distinct sources. RESULTS: In this article, we propose an approach, based on Semantic Web technologies, to represent and compare PGx knowledge units. To this end, we developed PGxO, a simple ontology that represents PGx knowledge units and their components. Combined with PROV-O, an ontology developed by the W3C to represent provenance information, PGxO enables encoding and associating provenance information to PGx relationships. Additionally, we introduce a set of rules to reconcile PGx knowledge, i.e. to identify when two relationships, potentially expressed using different vocabularies and levels of granularity, refer to the same, or to different knowledge units. We evaluated our ontology and rules by populating PGxO with knowledge units extracted from PharmGKB (2701), the literature (65,720) and from discoveries reported in EHR analysis studies (only 10, manually extracted); and by testing their similarity. We called PGxLOD (PGx Linked Open Data) the resulting knowledge base that represents and reconciles knowledge units of those various origins. CONCLUSIONS: The proposed ontology and reconciliation rules constitute a first step toward a more complete framework for knowledge comparison in PGx. In this direction, the experimental instantiation of PGxO, named PGxLOD, illustrates the ability and difficulties of reconciling various existing knowledge sources.

A scalable method for mining graph patterns stable under subsampling is proposed. The existing subsample stability and robustness measures are not antimonotonic according to definitions known so far. We study a broader notion of antimonotonicity for graph patterns, so that measures of subsample stability become antimonotonic. Then we propose gSOFIA for mining the most subsample-stable graph patterns. The experiments on numerous graph datasets show that gSOFIA is very efficient for discovering subsample-stable graph patterns.

With an increased interest in machine processable data, many datasets are now published in RDF (Resource Description Framework) format in Linked Data Cloud. These data are distributed over independent resources which need to be centralized and explored for domain specific applications. This paper proposes a new approach based on interactive data exploration paradigm using Pattern Structures, an extension of Formal Concept Analysis, to provide exploration and navigation over Linked Data through concept lattices. It takes RDF triples and RDF Schema based on user requirements and provides one navigation space resulting from several RDF resources. This navigation space allows user to navigate and search only the part of data that is interesting for her.

In this work we present a novel technique for exhaustive bicluster enumeration using formal concept analysis (FCA). Particularly, we use pattern structures (an extension of FCA dealing with complex data) to mine similar row/column biclusters, a specialization of biclustering when attribute values have coherent variations. We show how biclustering can benefit from the FCA framework through its robust theoretical description and efficient algorithms. Finally, we evaluate our bicluster mining approach w.r.t. a standard biclustering technique showing very good results in terms of bicluster quality and performance.

All domains of science and technology produce large and heterogeneous data. Although much work has been done in this area, mining such data is still a challenge. No previous research targets the mining of heterogeneous multidimensional sequential data. In this work, we present a new approach to extract heterogeneous multidimensional sequential patterns with different levels of granularity by relying on external taxonomies. We show the efficiency and interest of our approach with the analysis of trajectories of care for colorectal cancer using data from the French casemix information system.

The problem addressed in this paper is the merging of numerical information provided by several sources. Merging conflicting pieces of information into an interpretable and useful format is a tricky task even when an information fusion method is chosen. The use of formal concept analysis and pattern structures enables us to associate subsets of sources to combination results obtainable from consistent subsets of pieces of information. This provides a lattice of arguments where the reliability of sources can be taken into account. Instead of providing a unique fusion result, the method yields a structured view of partial results labelled by subsets of sources and allows us to argue about the most appropriate evaluation. The approach is illustrated with an experiment on a real-world application to decision aid in agricultural practices.

HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci-entific research documents, whether they are pub-lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et a ̀ la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

This paper shows how to embed a similarity relation between complex descriptions in concept lattices. We formalize similarity by a tolerance relation: objects are grouped within a same concept when having similar descriptions, extending the ability of FCA to deal with complex data. We propose two different approaches.~A first classical manner defines a discretization procedure. A second way consists in representing data by pattern structures, from which a pattern concept lattice can be constructed directly. In this case, considering a tolerance relation can be mathematically defined by a projection in a meet-semi-lattice. This allows to use concept lattices for their knowledge representation and reasoning abilities without transforming data. We show finally that resulting lattices are useful for solving information fusion problems.

In this paper we propose an approach which combines semantic resources and formal concept analysis to deal with heterogenous data sets represented as many-valued (MV) formal contexts. We define a new Galois connection considering the semantic relationships between attribute values in a MV context. The semantic relationships are used to calculate the similarity between attribute values to decide whether an attribute is shared by a set of objects or not. Then, based on this Galois connection, we define MV formal concepts and MV concept lattices. Depending on a chosen similarity threshold, MV concept lattices may have different levels of precision. We take advantage of this feature to browse the content of a biological databases repository in a dynamic and progressive way. The browsing process combines the navigation in several MV concept lattices and allows zooming operations by switching between MV concept lattices with higher or lower precision.

BACKGROUND: The Gene Ontology (GO) is a well known controlled vocabulary describing the biological process, molecular function and cellular component aspects of gene annotation. It has become a widely used knowledge source in bioinformatics for annotating genes and measuring their semantic similarity. These measures generally involve the GO graph structure, the information content of GO aspects, or a combination of both. However, only a few of the semantic similarity measures described so far can handle GO annotations differently according to their origin (i.e. their evidence codes). RESULTS: We present here a new semantic similarity measure called IntelliGO which integrates several complementary properties in a novel vector space model. The coefficients associated with each GO term that annotates a given gene or protein include its information content as well as a customized value for each type of GO evidence code. The generalized cosine similarity measure, used for calculating the dot product between two vectors, has been rigorously adapted to the context of the GO graph. The IntelliGO similarity measure is tested on two benchmark datasets consisting of KEGG pathways and Pfam domains grouped as clans, considering the GO biological process and molecular function terms, respectively, for a total of 683 yeast and human genes and involving more than 67,900 pair-wise comparisons. The ability of the IntelliGO similarity measure to express the biological cohesion of sets of genes compares favourably to four existing similarity measures. For inter-set comparison, it consistently discriminates between distinct sets of genes. Furthermore, the IntelliGO similarity measure allows the influence of weights assigned to evidence codes to be checked. Finally, the results obtained with a complementary reference technique give intermediate but correct correlation values with the sequence similarity, Pfam, and Enzyme classifications when compared to previously published measures. CONCLUSIONS: The IntelliGO similarity measure provides a customizable and comprehensive method for quantifying gene similarity based on GO annotations. It also displays a robust set-discriminating power which suggests it will be useful for functional clustering. AVAILABILITY: An on-line version of the IntelliGO similarity measure is available at: http://bioinfo.loria.fr/Members/benabdsi/intelligo_project/

In this paper we present an extension of the Galois connection to deal with many-valued formal contexts. We define a many-valued Galois connection with respect to similarity between attribute values in a many-valued context. Then, we define many-valued formal concepts and many-valued concept lattices. Depending on a similarity threshold, many-valued concept lattices may have different levels of precision. This feature makes them very useful for multilevel conceptual clustering. Many-valued concept lattices are also used in a new lattice-based information retrieval approach for efficiently answering complex queries.

The article proposes a generic method to classify vertices or edges of a labeled graph. More precisely the method computes a confidence index for each vertex v or edge e to be a member of a target class by mining the topological environments of v or e. The method contributes to knowledge discovery since it exhibits for each edge or vertex an informative environnement that explains the found confidence. When applied to the problem of discovering strategic bonds in molecules, the method correctly classifies most of the bonds while providing relevant explanations to chemists. The developed algorithm GemsBond outperforms both speed and scalability of the learning method that has previously been applied to the same application while giving similar results.

Building a domain ontology usually requires several resources of different types, e.g. thesaurus, object taxonomies, terminologies, data-bases, sets of documents, etc. where objects are described in terms of attributes and relations with other objects. One important and hard problem is to be able to combine and merge knowledge units extracted from these different resources within the representation formalism supporting the ontology. The purpose of this paper is to show which kinds of resources can be taken as starting points for building an ontology, using FCA and its extension RCA. A real-world example in microbiology is proposed, detailing the interaction with domain experts during the ontology design process. Finally, an evaluation based on recall and precision gives an idea of the efficiency of the approach and points out several research perspectives.

Biological databases are blooming today at an increasing rate to deal with the huge amount of data produced by genomic and post-genomic research. The need for a well-maintained searchable directory is therefore an important issue for a good exploitation of these databases. The BioRegistry repository is automatically generated from a publicly available list of biological databases (The Molecular Biology Database Collection published in Nucleic Acids Research) and aims at associating content metadata with each database in view of database retrieval and/or discovery. Such content metadata are either simple keywords or terms belonging to a medical thesaurus. Querying modalities including a search by semantic similarity are described. The use of conceptual clustering methods is proposed to build a semantic classification of biological databases enabling browsing through the BioRegistry repository and discovering previously unknown databases.

BACKGROUND: Complexity and amount of post-genomic data constitute two major factors limiting the application of Knowledge Discovery in Databases (KDD) methods in life sciences. Bio-ontologies may nowadays play key roles in knowledge discovery in life science providing semantics to data and to extracted units, by taking advantage of the progress of Semantic Web technologies concerning the understanding and availability of tools for knowledge representation, extraction, and reasoning. RESULTS: This paper presents a method that exploits bio-ontologies for guiding data selection within the preparation step of the KDD process. We propose three scenarios in which domain knowledge and ontology elements such as subsumption, properties, class descriptions, are taken into account for data selection, before the data mining step. Each of these scenarios is illustrated within a case-study relative to the search of genotype-phenotype relationships in a familial hypercholesterolemia dataset. The guiding of data selection based on domain knowledge is analysed and shows a direct influence on the volume and significance of the data mining results. CONCLUSIONS: The method proposed in this paper is an efficient alternative to numerical methods for data selection based on domain knowledge. In turn, the results of this study may be reused in ontology modelling and data integration.

We describe here a general approach for rare itemset mining. While mining literature has been almost exclusively focused on frequent itemsets, in many practical situations rare ones are of higher interest (e.g., in medical databases, rare combinations of symptoms might provide useful insights for the physicians). Based on an examination of the relevant substructures of the mining space, our approach splits the rare itemset mining task into two steps, i.e., frequent itemset part traversal and rare itemset listing. We propose two algorithms for step one, a naive and an optimized one, respectively, and another algorithm for step two. We also provide some empirical evidence about the performance gains due to the optimized traversal.

This paper presents a methodology for the semantic annotation of Web pages with individuals of a domain ontology. While most semantic annotation systems can recognize knowledge units, they usually do not establish explicit relations between them. The method presented identifies the individuals which should be related among the whole set of individuals and codes them as role instances within an OWL ontology. This is done by using a correspondence between the tree structure of a Web page and the semantics of the information it contains

Kasimir is a case‐based decision support system in the domain of breast cancer treatment. For this system, a problem is given by the description of a patient and a solution is a set of therapeutic decisions. Given a target problem, Kasimir provides several suggestions of solutions, based on several justified adaptations of source cases. Such adaptation processes are based on adaptation knowledge. The acquisition of this kind of knowledge from experts is presented in this paper. It is shown how the decomposition of adaptation processes by introduction of intermediate problems can highlight simple and generalizable adaptation steps. Moreover, some adaptation knowledge units that are generalized from those acquired for Kasimir are presented. This knowledge can be instantiated in other case‐based decision support systems, in particular in medicine.

This paper presents an original approach to qualitative spatial representation and reasoning with topological relations based on the use of lattices of relations. This approach has been developed for spatial reasoning in the domain of agricultural landscape analysis. The paper describes first the motivation of the present research work and the general framework of topological relations. Four different lattices of topological relations, including two Galois lattices, are introduced. The choices made for spatial representation and reasoning with these lattices are discussed, together with a thorough study and comparison of the four lattices. The implementation of one of the Galois lattices within an object-based representation system, as well as spatial lattice-based reasoning with topological relations in this system are then detailed.

This paper is concerned with the representation and classification of spatial relations and structures in an object-based knowledge representation system. In this system, spatial structures are defined as sets of spatial entities connected with topological relations. Relations are represented by objects with their own properties. We propose to define two types of properties: the first are concerned with relations as concepts while the second are concerned with relations as links between concepts. In order to represent the second type of properties, we have defined facets that are inspired from the constructors of description logics. We describe these facets and how they are used for classifying spatial structures and relations on land-use maps. Links between the present work and related work in description logics are also discussed.