Building conceptual lattices from conceptual graphs looks as natural way in Formal Concept Analysis but still is not discovered at length. If conceptual graphs are acquired from natural language texts then they contain specific material for knowledge discovery. Conceptual graphs serve as semantic models of text sentences and the data source for concept lattice. With the use of concept lattice it is possible to extract information which can be treated as facts. Facts can be extracted by using navigation in the lattice and interpretation its concepts and hierarchical links between them. Experimental investigation of this knowledge discovery technique is performed on the annotated textual corpus consisted of descriptions of biotopes of bacteria.
In the Formal Concept Analysis (FCA) community there is growing interest in the application FCA to textual data. Such interest corresponds to the overall popularity of Text Mining methods due to the prevalence of textual data, especially in the Internet.
There is certain number of works concerned with FCA and Text Mining devoted as
to linguistic applications of FCA [
The actual problem here is the problem of building formal contexts on textual data.
If textual data is represented as natural language texts then this problem becomes acute.
There are several approaches to the solution of this problem. One, mostly applied
variant, is the context in which the objects are text documents and the attributes are the
terms from these documents [
In addition to the direct use of text for building formal contexts, semantic models of text and textual corpora tagging tools are used. We apply this approach and use conceptual graphs (CGs) for representing semantics of individual sentences of a text.
One of the early mentions of applications of conceptual graphs in FCA can be
found in [
Although the join of two paradigms of conceptual modeling - conceptual graphs
and concept lattices - looks attractive it is still not discovered at length. In this paper
we present some results of knowledge discovery which were obtained by using our
framework for conceptual modeling on natural language texts [
Briefly recall the main FCA notions and consider some links between concept lattices and conceptual graphs. 2.1
There are two basic notions FCA deals with: formal context and concept lattice [
A conceptual graph is a finite oriented connected bipartite graph [
These two parameters of the CG model – the type of concept and valence of
relation – are used in our algorithms of CGs processing. Concept types constitute
hierarchically ordered set St, not necessarily a lattice [
Here and henceforth we consider conceptual graphs have been acquired from texts
only. Those conceptual graphs become labeled graphs when types of concepts are
supported. In the previous example “Human” is the label for “John”. In the labeled
concept (g, l) with concept name g and its label l gG as possible element of the set
of objects in the formal context and l St. There is the pattern structure introduced in
[
The method of acquiring conceptual graphs from natural language texts is considered
in [
Filtering sentences. Except of using standard lexicographic operations on the set of sentences (stemming, part-of-speech tagging, etc.) it is needed to filter sentences according with previously established topics which will be represented in formal context. Filtering means excluding some sentences from the set from which CGs have been acquired. The simplest criterion for filtering is checking existence of key words from the set St in the sentences of processing texts. Filtering is important for the texts having free subject area. Problem–oriented texts usually have high determined topics which makes them free from filtering. But filtering is needed if the number of topics in a text is greater than ones were established for representing in formal contexts.
Creating formal contexts. To construct formal context on the set of conceptual graphs it is necessary to select one set of concepts as objects and other set of concepts as object’s attributes. At the first glance, this problem seems simple: those concepts of conceptual graphs which are connected by "attribute" relation have been put into formal context as its objects and attributes. Actually the solution is much more complex.
To illustrate this, consider an example of processing the sentence which is typical in the learning of bacteria biotopes: B. cenocepacia strain HI2424 was recovered from agricultural soil in upstate NY. Conceptual graph for this sentence is shown on Fig. 1
The sentence being analyzed is about bacterium named as Burkholderia cenocepacia. Its name is used in the text in abbreviated form as B. cenocepacia and HI2424 is the code of its strain. The decision that this sentence is about Burkholderia cenocepacia may be found on the stage of analyzing and filtering sentences by learning the algorithm to recognize bacteria names. If the context which has the names of bacteria as an objects is creating, then the sub graph <strain> - (attribute) - < cenocepacia > and two isolated concepts <b.> and <hi2424> do not participate in forming that context.
The verb “recover” is the key word which marks the predicate in conceptual graph to be processed for creating formal context. The main meaningful attribute of Burkholderia cenocepacia in the sentence is that it inhabits in the soil, more concrete – in agricultural soil. The key word “soil” must be in the thesaurus containing information about habitats of bacteria for marking the sub graph <soil> - (attribute) - <agricultural > for using in the context. Then although the “attribute” conceptual relation plays significant role in creating formal context it is not always applied in it. Another conceptual relations - “location” and “patient” on Fig. 1 - also belong to the list of important semantic roles. These relations produce possible attributes to formal context (“upstate” and “NY”) which are not informative.
Another problem in creating formal contexts is linking in one context objects and
attributes from different sentences. Its solution is connected with anaphora resolution
and described in [
Bioinformatics is one of the fields where Data Mining and Text Mining applications
are growing up rapidly. New term of “Biomedical Natural Language Processing”
(BioNLP) has been introduced here. This term is stipulated by huge amount of
scientific publications in Bioinformatics and organizing them into textual databases and
corpora with access to full texts of articles via such systems as PubMed [
There are several solutions of BB-Task presented mainly in the BioNLP Shared Task
workshops; the recent proceedings of such workshops are in [
BB-Subtasks. There are three subtasks in which the whole BB-Task is divided.
The first subtask is named as Bacteria and habitat detection and categorization. In this subtask biotope entities (names of bacteria) need to be detected in a given biological text and must be mapped onto a given ontology.
The second subtask, Entity and event extraction is devoted to event extraction from texts. In this case the term “event extraction” corresponds to the Text Mining term “fact extraction”. This subtask is focused on the single event “Lives_In” which denotes the fact of living bacteria in certain environment (habitat): water, soil or other organisms.
The third subtask is named as Knowledge Base extraction. Here text processing systems are evaluated for their capacity to build a knowledge base from the textual corpus. Actually, as names of bacteria as its relations to the habitat must be detected and enrich given ontology.
All the diversity of BB-Task can be often transformed to two standard problems of Named Entity Recognition (NER) and Relations Extraction (RE) on textual data.
Information resources. Textual corpora, databases and ontologies have been
applied for storing data in BB-Task. Large ontology of biotopes called OntoBiotope [
Methods. The current trend in solving BB-Task is using methods from Data
Mining and Text Mining areas of research. Subtasks of BB-Task is reformulated as the
tasks of data clustering or data classifying for applying appropriate methods of Data
Mining. Among these methods there are Support Vector Machine classifier [
Now any new solution of BB-Task may be classified in accordance to considered framework of BB-Subtasks –Information Resources – Methods from previous section. Our solution is classified by the following way.
BB-Subtasks. Solving the first subtask of BB-Task, we extract the names of
bacteria from the textual corpus [
We formulate the second subtask as Relations Extraction (RE) one. Using conceptual graphs not only “Lives_In” relation but some others may be extracted. We construct three formal contexts of “Entity”, “Areal” and “Pathogenicity”. In the “Areal” context there is “Lives_In” relation linking objects and attributes. In other contexts of “Entity” and “Pathogenicity” the “Attribute”, “Instrument”, “Location”, etc. semantic roles are applied as relations for constructing these contexts – see examples above.
Concept lattices which we create as data storage for our fact extraction system together with the software of this system constitute the basis for constructing knowledge base. So the elements of all three subtasks are presented in the FCA based solution of BB-Task.
Information resources. We had selected 130 mostly known bacteria and have
processed data from corresponding corpus [
Context name Entity Areal Pathogenicity
Number of objects 130 130 130
Number of attributes
As it is followed from the table there is relatively small number of formal concepts in the contexts. This is due to the sparse form of all contexts generated by conceptual graphs.
Methods. One of the problems in learning bacteria biotopes is the problem of
bacteria classification: it is needed to classify bacteria according with their properties
characterizing them as entities, characterizing their areal and pathogenicity. Various
bacteria may have similar properties or may not. It is interesting to find clusters of
bacteria containing ones having similar properties. This clustering task may be solved
with concept lattice. Every concept in concept lattice being the set of one or several
names of bacteria and their properties may be treated as fact. Facts can be extracted
by using navigation in the lattice and interpretation its concepts and hierarchical links
between them. For extracting facts and clustering we use visualization together with
database technique of processing input queries. Special functionality was created in
our system to visualize sub lattices of concept lattice to form special views consisted
of sub lattices corresponding to certain property (intent in the lattice) or entity (extent
in the lattice) of bacteria. We applied open source tool [
Fig. 2 shows a fragment of the formal context with the attributes related to some properties of bacteria: Gram staining, the property of being aerobic, etc.
It is evident directly from the context that these 20 bacteria constitute two clusters according to the Gram staining: there is no bacterium which is simultaneously Grampositive and Gram-negative. Lattice diagrams on the Fig. 3 confirm this fact.
Interpreting views on Fig. 3 we resolve that bacteria are clustered according with their Gram staining because the views on Fig. 3 a) and b) do not intersect. a) b)
Clustering bacteria according with the property of being aerobic is not evident from the context on Fig. 2. Lattice diagrams on the Fig. 4 confirm the clustering bacteria according with this property by the same manner as for Fig. 3.
a) b) However, the number of bacteria in Fig. 3 and 4 is not the same: Fig. 3 contains all 20 bacteria (10 in Figure 3-a and 10 in Figure 3-b.) and Fig. 4 - contains only 9 bacteria. This is due to the fact that the relevant texts do not contain information about the property of being aerobic for some bacteria.
We can compare our results with two known similar solutions related to fact
extraction problem. The first solution of extracting events is presented in [
The second solution [
0.52 0.42 The Precision / Recall ratio is more informative for evaluating the quality of solution of many problems in Data Mining. On the Fig. 5 it is shown such ratio calculated for 62 bacteria names extracted from texts in one of our experiments.
As it is followed from the Fig. 5, approximately half of the total number of objects has Precision / Recall ratio equal to unity that characterizes our solution as not bad.
Comparing our current results of fact extraction with the known ones we also have to resume that using concept lattice provides principally another variant of solution of fact extraction problem. The main difference of this solution is that it is not realized in the processed text by highlighting its lexical elements but it is realized with new external resource, conceptual model in the form of concept lattice. 4
This paper describes the idea of joining two paradigms of conceptual modeling conceptual graphs and concept lattices. Current results of realizing this idea on textual data show its good potential for knowledge extraction. Concept lattice may serve as a frame of ontology constructed on texts. Its data which may or may not be interpreted as facts constitutes a knowledge stored in concept lattice being ready to extract.
In spite of certain useful features of presented technology there are some problems which need to be solved for improving the quality of modeling technique. 1. Conceptual graphs acquired from texts contain many noisy elements. Noise is constituted by the text elements that contain no useful information or cannot be interpreted as facts. Noisy elements significantly decrease efficiency of algorithms of fact extraction. 2. The next stage of developing current technology is creating of fledged information system which processes user queries and produces solutions of certain tasks on textual data. Not only visualization but also special user oriented interfaces to concept lattice will be created in this system.
Acknowledgments. The paper concerns with the work partially supported by the Russian Foundation for Basic Research, grant № 15-07-05507.