| All publications sorted by year |
| 2010 |
| Dans le domaine des bases de données, les outils de calcul de règles d'association et de dépendances fonctionnelles affichent traditionnellement les résultats sous forme d'une liste de règles, difficiles à lire. Nous proposons ici de projeter une relation d'une base de données sur un cube de données OLAP, afin d'afficher ces règles de manière plus structurée et plus intuitive. De plus, nous montrons que les liens de navigation d'OLAP peuvent aider l'utilisateur à naviguer dans ces règles produites. |
| Concept lattices have been successfully used for information retrieval and browsing. They offer the advantage of combining querying and navigation in a consistent way. Conceptual navigation is more flexible than hierarchical navigation, and easier to use than plain querying. It has already been applied to formal, logical, and relational contexts, but its application to the semantic web is a challenge because of inference mechanisms and expressive query languages such as SPARQL. The contribution of this paper is to extend conceptual navigation to the browsing of RDF graphs, where concepts are accessed through SPARQL-like queries. This extended conceptual navigation is proved consistent w.r.t. the context (i.e., never leads to an empty result set), and complete w.r.t. the conjunctive fragment of the query language (i.e., every query can be reached by navigation only). Our query language has an expressivity similar to SPARQL, and has a more natural syntax close to description logics. |
| We explore different perspectives on how categorial grammars can be considered as Logical Information Systems (LIS) both theoretically, and practically. Categorial grammars already have close connections with logic. We discuss the advantages of integrating both approaches. We consider more generally different ways of connecting computational linguistic data and LIS as an application of Formal Concept Analysis. |
| 2009 |
| Since the arrival of digital cameras, many people are faced to the challenge of organizing and browsing the overwhelming flood of photos their life produces. The same is true for all sorts of documents, e.g.~emails, audio files. Existing systems either let users fill query boxes without any assistance, or drive them through rigid navigation structures (e.g., hierarchies); or they do not let users put annotations on their documents, even when this would support the organization and retrieval of any documents on customized criteria. We present a tool, {\sc Camelis}, that offers users with an organization that is dynamically computed from documents and their annotations. {\sc Camelis} is designed along the lines of Logical Information Systems (LIS), which are founded on logical concept analysis. Hence, (1) an expressive language can be used to describe photos and query the collection, (2) manual and automatic annotations can be smoothly integrated, and (3) expressive querying and flexible navigation can be mixed in a same search and in any order. This presentation is illustrated on a real collection of more than 5,000 photos. |
| De nombreuses décisions sont prises en commission, par exemple pour affecter des ressources. Les critères de décision sont difficiles à exprimer et la situation globale est en général trop complexe pour que les participants puissent l'appréhender pleinement. Dans cet article, nous décrivons un processus de décision où l'analyse de concepts est utilisée pour faire face à ces problèmes. Grâce à l'analyse de concepts, les personnes fair play ont la possibilité d'être équitables envers les candidats et de faire preuve de cohérence dans leurs jugements sur toute la durée de la réunion. |
| Formal concept analysis is recognized as a good paradigm for browsing data sets. Besides browsing, update and complex data are other important aspects of information systems. To have an efficient implementation of concept-based information systems is difficult because of the diversity of complex data and the computation of conceptual structures, but essential for the scalability to real-world applications. We propose to decompose contexts into simpler and specialized components: logical context functors. We demonstrate this allows for scalable implementations, updatable ontologies, and richer navigation structures, while retaining genericity. |
| 2008 |
| Today, the thematic layer is still the prevailling structure in geomatics for handling geographical information. However, the layer model is rigid: it implies partitionning geographical data in predefined categories and using the same description schema for all elements of a layer. Recently, Logical Information Systems (LIS) introduced a new paradigm for information management and retrieval. Using LIS, we propose a more flexible organisation of vectorial geographical data at a thiner level since it is centered on the geographical feature. LIS do not rely on a hierarchical organisation of information, and enable to tightly combine querying and navigation. In this article, we present the use of LIS to handle geographical data. In particular, we detail a data model for geographical features and the corresponding querying and navigation model. These models have been implemented in the GEOLIS prototype, which has been used to lead experiments on real data. |
| Formal Concept Analysis (FCA) is a natural framework to learn from examples. Indeed, learning from examples results in sets of frequent concepts whose extent contains mostly these examples. In terms of association rules, the above learning strategy can be seen as searching the premises of rules where the consequence is set. In its most classical setting, FCA considers attributes as a non-ordered set. When attributes of the context are partially ordered to form a taxonomy, Conceptual Scaling allows the taxonomy to be taken into account by producing a context completed with all attributes deduced from the taxonomy. The drawback, however, is that concept intents contain redundant information. In this article, we propose a parameterized algorithm, to learn rules in the presence of a taxonomy. It works on a non-completed context. The taxonomy is taken into account during the computation so as to remove all redundancies from intents. Simply changing one of its operations, this parameterized algorithm can compute various kinds of concept-based rules. We present instantiations of the parameterized algorithm to learn rules as well as to compute the set of frequent concepts. |
| The semantic web aims at enabling the web to understand and answer the requests from people and machines. It relies on several standards for representing and reasoning about web contents. Among them, the Web Ontology Language (OWL) is used to define ontologies, i.e. knowledge bases, and is formalized with description logics. In this paper, we demonstrate how dynamic taxonomies and their benefits can be transposed to browse OWL~DL ontologies. We only assume the ontology has an assertional part, i.e. defines objects and not only concepts. The existence of relations between objects in OWL leads us to define new navigation modes for crossing these relations. A prototype, Odalisque, has been developed on top of well-known tools for the semantic web. |
| Because of the expansion of geo-positioning tools and the democratization of geographical information, the amount of geo-localized data that is available around the world keeps increasing. So, the ability to efficiently retrieve informations in function of their geographical facet is an important issue. In addition to individual properties such as position and shape, spatial relations between objects are an important criteria for selecting and reaching objects of interest: e.g., given a set of touristic points, selecting those having a nearby hotel or reaching the nearby hotels. In this paper, we propose Logical Concept Analysis (LCA) and its handling of relations for representing and reasoning on various kinds of spatial relations: e.g., Euclidean distance, topological relations. Furthermore, we present an original way of navigating in geolocalized data, and compare the benefits of our approach with traditional Geographical Information Systems (GIS). |
| Recent work in fault localization crosschecks traces of correct and failing execution traces. The implicit underlying technique is to search for association rules which indicate that executing a particular source line will cause the whole execution to fail. This technique, however, has limitations. In this article, we first propose to consider more expressive association rules where several lines imply failure. We then propose to use Formal Concept Analysis (FCA) to analyze the resulting numerous rules in order to improve the readability of the information contained in the rules. The main contribution of this article is to show that applying two data mining techniques, association rules and FCA, produces better results than existing fault localization techniques. |
| In academia, many decisions are taken in committee, for example to hire people or to allocate resources. Genuine people often leave such meetings quite frustrated. Indeed, it is intrinsically hard to make multi-criteria decisions, selection criteria are hard to express and the global picture is too large for participants to embrace it fully. In this article, we describe a recruiting process where logical concept analysis and formal concept analysis are used to address the above problems. We do not pretend to totally eliminate the arbitrary side of the decision. We claim, however, that, thanks to concept analysis, genuine people have the possibility to 1) be fair with the candidates, 2) make a decision adapted to the circumstances, 3) smoothly express the rationales of decisions, 4) be consistent in their judgements during the whole meeting, 5) vote (or be arbitrary) only when all possibilities for consensus have been exhausted, and 6) make sure that the result, in general a total order, is consistent with the partial orders resulting from the multiple criteria. |
| taux acceptation 19/70 = 27\% |
| Dynamic taxonomies and faceted search are increasingly used to organize and browse document collections. The main function of dynamic taxonomies is to start with the full collection, and zoom-in to a small enough subset of items for direct inspection. In this paper, we present other navigation modes than zoom-in for less directed and more exploratory browsing of a document collection. The presented navigation modes are zoom-out, shift, pivot, and querying by examples. These modes correspond to query transformations, and make use of boolean operators. Therefore, the current focus is always clearly specified by a query. |
| 2007 |
| Geographical data are mainly structured in layers of information. However, this model of organisation is not convenient for navigation inside a dataset, and so limits geographical data exploration to querying. We think information retrieval could be made easier in GIS by the introduction of a navigation based on geographical object properties. For this purpose, we propose a prototype, GEOLIS1, which tightly combines querying and navigation in the search process of geographical data. GEOLIS relies on Logical Information Systems (LIS), which are based on Formal Concept Analysis (FCA) and logics. In this paper, we detail data organisation and navigation process in GEOLIS. We also present the results of an experimentation led on a real dataset. |
| Formal Concept Analysis (FCA) is a natural framework for learning from positive and negative examples. Indeed, learning from examples results in sets of frequent concepts whose extent contains only these examples. In terms of association rules, the above learning strategy can be seen as searching the premises of exact rules where the consequence is fixed. In its most classical setting, FCA considers attributes as a non-ordered set. When attributes of the context are ordered, Conceptual Scaling allows the related taxonomy to be taken into account by producing a context completed with all attributes deduced from the taxonomy. The drawback, however, is that concept intents contain redundant information. In this article, we propose a parameterized generalization of a previously proposed algorithm, in order to learn rules in the presence of a taxonomy. The taxonomy is taken into account during the computation so as to remove all redundancies from intents. Simply changing one component, this parameterized algorithm can compute various kinds of concept-based rules. We present instantiations of the parameterized algorithm for learning positive and negative rules. |
| Since the arrival of digital cameras, many people are faced to the challenge of organizing and retrieving the overwhelming flow of photos their life produces. Most people put no metadata on their photos, and we believe this is because existing tools make a very limited use of them. We present a tool, Camelis, that offers users with an organization of photos that is dynamically computed from the metadata, making worthwhile the effort to produce it. Camelis is designed along the lines of Logical Information Systems (LIS), which are founded on logical concept analysis. Hence, (1) an expressive language can be used to describe photos and query the collection, (2) manual and automatic metadata can be smoothly integrated, and (3) expressive querying and flexible navigation can be mixed in a same search and in any order. This presentation is illustrated by experiences on a real collection of more than 5000 photos. |
| Strings are an important part of most real application multi-valued contexts. Their conceptual treatment requires the definition of substring scales, i.e., sets of relevant substrings, so as to form informative concepts. However these scales are either defined by hand, or derived in a context-unaware manner (e.g., all words occuring in string values). We present an efficient algorithm based on suffix trees that produces complete and concise substring scales. Completeness ensures that every possible concept is formed, like when considering the scale of all substrings. Conciseness ensures the number of scale attributes (substrings) is less than the cumulated size of all string values. This algorithm is integrated in Camelis, and illustrated on the set of all ICCS paper titles. |
| Dynamic taxonomies have been proposed as a solution for combining querying and navigation, offering both expressivity and interactivity. Navigation is based on the filtering of a multidimensional taxonomy w.r.t. query answers, which helps users to focus their search. We show that properties that are commonly used only in queries can be integrated in taxonomies, and hence in navigation, by the use of so-called logics. Hand-designed taxonomies and concrete domains (e.g., dates, strings) can be combined so as to form complex taxonomies. For instance, valued attributes can be handled, and different roles between documents and locations can be distinguished. Logical Information Systems (LIS) are characterized by the combination of querying and navigation, and the systematic use of logics. |
| 2006 |
| Today, the thematic layer is still the prevailling structure in geomatics for handling geographical information. However, the layer model is rigid: it implies partitionning geographical data in predefined categories and using the same description schema for all elements of a layer. Recently, Logical Information Systems (LIS) introduced a new paradigm for information management and retrieval. Using LIS, we propose a more flexible organisation of vectorial geographical data at a thiner level since it is centered on the geographical feature. LIS does not rely on a hierarchical organisation of information, and enable to tightly combine querying and navigation in a same search. In this article, we present a work in progress about the use of LIS model to handle geographical data. In particular, we detail a data model for geographical features and the corresponding querying and navigation model. These models have been implemented in the GEOLIS prototype, which has been used to lead experiments with real data. |
| Logic Functors form a framework for specifying new logics, and deriving automatically theorem provers and consistency/completeness diagnoses. Atomic functors are logics for manipulating symbols and concrete domains, while other functors are logic transformers that may add connectives or recursive structures, or may alter the semantics of a logic. The semantic structure of the framework is model theoretic as opposed to the verifunctional style often used in classical logic. This comes close to the semantics of description logics, and we show indeed that the logic~${\cal ALC}$ can be rebuilt using logic functors. This offers the immediate advantage that variants of~${\cal ALC}$ can be explored and implemented almost for free. This report comes with extensive appendices describing in detail a toolbox of logic functors (definitions, algorithms, theorems, and proofs). |
| 2005 |
| Many application domains make use of specific data structures such as sequences and graphs to represent knowledge. These data structures are ill-fitted to the standard representations used in machine learning and data-mining algorithms: propositional representations are not expressive enough, and first order ones are not efficient enough. In order to efficiently represent and reason on these data structures, and the complex patterns that are related to them, we use domain-specific logics. We show these logics can be built by the composition of logical components that model elementary data structures. The standard strategies of top-down and bottom-up search are ill-suited to some of these logics, and lack flexibility. We therefore introduce a dichotomic search strategy, that is analogous to a dichotomic search in an ordered array. We prove this provides more flexibility in the search, while retaining completeness and non-redundancy. We present a novel algorithm for learning using domain specific logics and dichotomic search, and analyse its complexity. We also describe two applications which illustrates the search for motifs in sequences; where these motifs have arbitrary length and length-constrained gaps. In the first application sequences represent the trains of the East-West challenge; in the second application they represent the secondary structure of Yeast proteins for the discrimination of their biological functions. |
| A logical view of formal concept analysis considers attributes of a formal context as unary predicates. In a first part, we propose an augmented definition that handles {\em binary relations} between objects. A Galois connection is defined on augmented contexts. It represents concept inheritance as usual, but also relations between concepts. As usual, labeling operators are also defined. In particular, concepts and relations are visible and labeled in a single structure. In a second part, we show how relations can be used for navigating in an augmented concept lattice. This part augments the theory of Logical Information Systems. An implementation is sketched, and first experimental results are presented. |
| We present Logical Information Systems (LIS). A LIS can be viewed as a schema-less database whose objects are described by logical formulas. Objects are automatically organized according to their logical description, and logical formulas can be used for representing both queries and navigation links. The key feature of a LIS is that it answers a query with a set of navigation links expressed in the same logic as the query. As navigation links are dynamically computed from any query, and can be used as query increments, it follows that querying and navigation steps can be combined in any order. We then present LISFS, a file-system implementation of a LIS, where objects are files or parts of files. This has the benefit to make LIS features available right now to existing applications. This implementation can easily be extended and specialized through a plug-in mechanism. Finally, we present some applications in the field of personal databases (e.g., music, images, emails), and demonstrate that building specialized interfaces for visualizing databases can be done easily through LISFS navigation. |
| 2004 |
| Logical information systems (LIS) use logic in a uniform way to describe their contents, to query it, to navigate through it, to analyze it, and to maintain it. They can be given an abstract specification that does not depend on the choice of a particular logic, and concrete instances can be obtained by instantiating this specification with a particular logic. In fact, a logic plays in a LIS the role of a schema in databases. We present the principles of LIS, the constraints they impose on the expression of logics, and hints for their effective implementation. |
| BLID (Bio-Logical Intelligent Database) is a bioinformatic system designed to help biologists extract new knowledge from raw genome data by providing high-level facilities for both data browsing and analysis. We describe BLIDrsquos novel data browsing system which is based on the idea of Logical Information Systems. This enables combined querying and navigation of data in BLID (extracted from public bioinformatic repositories). The browsing language is a logic especially designed for bioinformatics. It currently includes sequence motifs, taxonomies, and macromolecule structures, and it is designed to be easily extensible, as it is composed of reusable components. Navigation is tightly combined with this logic, and assists users in browsing a genome through a form of human-computer dialog. |
| 2003 |
| 2002 |
| Les deux principaux paradigmes de recherche d'information, la navigation et l'interrogation, sont souvent dissociés. Les syst~mes hiérarchiques offrent une structure de navigation figée qui ne convient pas ~ toutes les utilisations ; ce qu'ils compensent par des outils de recherche. Ceux-ci, fondés sur l'interrogation, sont plus souples mais sont plus difficiles ~ utiliser pour les non-initiés et rendent délicat le contr~le du volume des réponses. Il appara~t donc comme nécessaire de combiner étroitement navigation et interrogation. Pour réaliser cette combinaison, nous nous fondons sur l'Analyse de concepts (AC) qui permet de construire automatiquement, ~ partir d'une description des objets, une structure de navigation appelée ~treillis de concepts~, o~ les concepts jouent ~ la fois le r~le de répertoire et de requ~te. Comme dans l'AC les descriptions se limitent ~ des ensembles d'attributs, nous avons généralisé l'AC pour les remplacer par des formules d'une logique arbitraire. Ceci nous semble important pour traiter des applications diverses. Les Syst~mes d'information logiques (SIL) se définissent donc par la combinaison navigation/interrogation, l'emploi de la logique (descriptions, requ~tes et liens de navigation) et la généricité. Sur cette base, nous avons développé plusieurs mécanismes pour faciliter l'expression et la découverte de connaissances. Les connaissances d'un domaine peut ~tre exprimées par une terminologie. Un dialogue homme-machine, fondé sur le treillis de concepts, permet de retrouver des objets (navigation) et de découvrir des régularités entre les objets (extraction de connaissances). Un mécanisme d'apprentissage offre une assistance ~ la classification des objets. Enfin, un prototype a été développé pour d'expérimenter ces mécanismes. Il est générique dans le sens o~ il ne dépend pas de la logique employée. Ces logiques peuvent ~tre assemblés ~ l'aide d'un jeu de composants logique, que nous avons constitué. |
| Logic-based applications often use customized logics which are composed of several logics. These customized logics are also often embedded as a black-box in an application. Their implementation requires the specification of a well-defined interface with common operations such as a parser, a printer, and a theorem prover. In order to be able to compose these logics, one must also define composition laws, and prove their properties. We present the principles of logic functors and their compositions for constructing customized logics. An important issue is how the operations of different sublogics inter-operate. We propose a formalization of the logic functors, their semantics, implementations, and their composition. |
| A formal context associates to objects a description that combines automatically extracted properties (intrinsic) and manually assigned ones (extrinsic). The extrinsic properties are expressed by users according to intentions that are often subjective and changing, and determine the classification and retrieval of objects. So, we find it important to assist users in this task through the automatic suggestion of extrinsic properties to be assigned and even the discovery of rules to automate these assignements. The principle is to learn from the description of existing objects the extrinsic description of a new object. Because of the changing nature of users' intentions, the assistance given in the incremental building of a logical context must be interactive. We present formal principles, and an application to the classification of email messages. |
| Formal Concept Analysis (FCA) is interested in the formation of concept lattices from binary relations between objects and attributes, a.k.a. contexts. Many algorithms have been proposed to generate the set of all concepts, and also the edges of the lattice between these concepts. We develop the principle and the code of a new algorithm combining two existing ones, Godin's and Bordat's algorithms. Then, we show by both a theoretical and practical study that it is the most efficient algorithm for sparse contexts, which are usually found in real applications. |
| Logical Information Systems (LIS) use logic in a uniform way to describe their contents, to query it, to navigate through it, to analyze it, and to maintain it. They can be given an abstract specification that does not depend on the choice of a particular logic, and concrete instances can be obtained by instantiating this specification with a particular logic. In fact, a logic plays in a LIS the role of a schema in data-bases. We present the principles of logical information systems, the constraints they impose on the expression of logics, and hints for their effective implementation. |
| Logic-based applications often use customized logics which are composed of several logics. These customized logics are also often embedded as a black-box in an application. So, implementing them requires the specification of a well-defined interface with common operations such as a parser, a printer, and a theorem prover. In order to be able to compose these logic, one must also define composition laws, and prove their properties. We present the principles of logic functors and their compositions for constructing logics that are ad-hoc, but sound. An important issue is how the operations of different sublogics inter-operate. We propose a formalization of the logic functors, their semantics, implementations, proof-theoretic properties, and their composition. |
| 2001 |
| We present a generalization of logic All I Know by presenting it as an extension of standard modal logics. We study how this logic can be used to represent complete and incomplete knowledge in Logical Information Systems. In these information systems, a knowledge base is a collection of objects (e.g., files, bibliographical items) described in the same logic as used for expressing queries. We show that usual All I Know (transitive and euclidean accessibility relation) is convenient for representing complete knowledge, but not for incomplete knowledge. For this, we use \emph{serial} All I Know (serial accessibility relation). |
| Logical Concept Analysis is Formal Concept Analysis where logical formulas replace sets of attributes. We define a Logical Information System that combines navigation and querying for searching for objects. Places and queries are unified as formal concepts represented by logical formulas. Answers can be both extensional (objects belonging to a concept) and intensional (formulas refining a concept). Thus, all facets of navigation are formalized in terms of Logical Concept Analysis. We show that the definition of being a refinement of some concept is a specific case of Knowledge Discovery in a formal context. It can be generalized to recover more classical KD~operations like machine-learning through the computation of necessary or sufficient properties (modulo some confidence), or data-mining through association rules. |
| 2000 |
| We present the design of a file system whose organization is based on Concept Analysis \u201c~ la Wille-Ganter\u201d. The aim is to combine querying and navigation facilities in one formalism. The file system is supposed to offer a standard interface but the interpretation of common notions like directories is new. The contents of a file system is interpreted as a Formal Context, directories as Formal Concepts, and the sub-directory relation as Formal Concepts inclusion. We present an organization that allows for an efficient implementation of such a Conceptual File System. |
| We propose a generalization of Formal Concept Analysis (FCA) in which sets of attributes are replaced by expressions of an almost arbitrary logic. We prove that all FCA can be reconstructed on this basis. We show that from any logic that is used in place of sets of attributes can be derived a contextualized logic that takes into account the formal context and that is isomorphic to the concept lattice. We then justify the generalization of FCA compared with existing extensions and in the perspective of its application to information systems. |
| We present the design of a file system whose organization is based on Concept Analysis ~~ la Wille-Ganter~. The aim is to combine querying and navigation facilities in one formalism. The file system is supposed to offer a standard interface but the interpretation of common notions like directories is new. The contents of a file system is interpreted as a Formal Context, directories as Formal Concepts, and the sub-directory relation as Formal Concepts inclusion. We present an organization that allows for an efficient implementation of such a Conceptual File System. |
| 1999 |
| Nous proposons une généralisation de l'analyse de concepts formels (ACF) dans laquelle les ensembles d'attributs sont remplacés par des expressions d'une logique presque arbitraire. Nous prouvons que toute l'ACF peut ~tre reconstruite sur cette base. Nous montrons qu'~ partir de toute logique utilisée ~ la place des ensembles d'attributs, on peut dériver une logique contextualisée qui prend en compte le contexte formel et qui est isomorphe au treillis de concepts. Nous comparons ensuite la généralisation de l'ACF aux extensions qui y ont déj~ été apportées. Enfin, nous présentons nos perspectives d'application aux syst~mes d'information. |
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All person copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Les documents contenus dans ces répertoires sont rendus disponibles par les auteurs qui y ont contribué en vue d'assurer la diffusion à temps de travaux savants et techniques sur une base non-commerciale. Les droits de copie et autres droits sont gardés par les auteurs et par les détenteurs du copyright, en dépit du fait qu'ils présentent ici leurs travaux sous forme électronique. Les personnes copiant ces informations doivent adhérer aux termes et contraintes couverts par le copyright de chaque auteur. Ces travaux ne peuvent pas être rendus disponibles ailleurs sans la permission explicite du détenteur du copyright.
This document was translated from BibTEX by bibtex2html