The paper presents conceptual modelling technique on natural language texts. This technique combines the usage of two conceptual modeling paradigms: conceptual graphs and Formal Concept Analysis. Conceptual graphs serve as semantic models of text sentences and the data source for concept lattice - the basic conceptual model in Formal Concept Analysis. With the use of conceptual graphs the Text Mining problems of Named Entity Recognition and Relations Extraction are solved. Then these solutions are applied for creating concept lattice. The main problem investigated in the paper is the problem of creating formal contexts on a set of conceptual graphs. Its solution is based on the analysis of semantic roles and conceptual patterns in conceptual graphs. Concept lattice built on textual data is applied for knowledge extraction. Knowledge, sometimes interpreted as facts, can be extracted by using navigation in the lattice and interpretation its concepts and hierarchical links between them. Experimental investigation of the proposed technique is performed on the annotated textual corpus consisted of descriptions of biotopes of bacteria. †The paper concerns the work which is partially supported by Russian Foundation of Basic Research, grant № 15-07-05507
Knowledge extraction from textual data requires more in-depth intensive analysis of this data. In the area of Text Mining, some variants of knowledge extraction have been realized by solving such problems as sentiment analysis, fact extraction and decision making support. To solve these problems it is necessary to have models that reflect semantics of textual data. It is especially urgent when this data is presented as unstructured natural language texts.
Conceptual modeling is one of the ways of modeling
semantics in the Natural Language Processing (NLP)
[
Conceptual modeling has long been applied for
databases and software modeling [
Formal Concept Analysis (FCA) [
The main problem in creating concept lattice on
textual data is building so called formal contexts on this
data. Formal context is matrix representation of the
relation on the sets of objects and attributes. So it is
needed to acquire words or word combinations from
texts which are interpreted as objects and attributes. To
restrict all possible combinations of words of such
meanings we need to select from them those ones which
are valued for solving concrete problem or the class of
problems. As a result a concept lattice created on texts
becomes domain specific. This is similar to the design of
ontologies and concept lattice is often considered as
framework of ontology [
Another paradigm of conceptual modeling is
Conceptual Graphs (CGs) [
Conceptual graphs have been applied for modeling
many real life objects including texts. Acquiring
conceptual graphs from natural language texts is
nontrivial problem but it is quite solvable [
The main purpose of this paper is to show how two
paradigms of conceptual modeling - Conceptual Graphs
and Formal Concept Analysis - can be united in one
modeling technique. The idea of joining these two
paradigms seems very attractive but not elaborated much
enough [
Proposed technique is used in on-going project of creating fact extraction system working on biomedical data. Experimental investigation of it is performed on the annotated textual corpus consisted of descriptions of biotopes of bacteria.
The proposed modeling technique named briefly as CGsFCA modeling is based on using conceptual graphs and concept lattice. It may be applied for knowledge extraction from textual data. In CGs-FCA modeling conceptual graphs serve as semantic models of text sentences and the data source for formal context of concept lattice. Concept lattice built on textual data is applied for knowledge extraction. Knowledge, sometimes interpreted as facts, can be extracted by using navigation in the lattice and interpretation its concepts and hierarchical links between them.
To illustrate CGs-FCA modeling, consider some FCA basics.
There are two basic notions FCA deals with: formal
context and concept lattice [
By other words, a formal concept is a pair (A, B) of subsets of objects and attributes which are connected so that every object in A has every attribute in B, for every object in G that is not in A, there is an attribute in B that the object does not have and for every attribute in M that is not in B, there is an object in A that does not have that attribute.
The partial orders established by relations ф and Р on the set G and M induce a partial order ≤ on the set of formal concepts. If for formal concepts (A1, B1) and (A2, B2), A1 ф A2 and B2 Р B1 then (A1, B1) ≤ (A2, B2) and formal concept (A1, B1) is less general than (A2, B2). This order is represented by concept lattice. A lattice consists of a partially ordered set in which every two elements have a unique supremum (also called a least upper bound or join) and a unique infimum (also called a greatest lower bound or meet).
According to the central theorem of FCA [
Figure 1 Example of formal context and concept lattice.
To illustrate these abstract definitions consider an example. Figure 1 shows simple formal context and concept lattice composed on the sets G = {DNA, Virus, Prokaryotes, Eukaryotes, Bacterium} and M = {Membrane, Nucleus, Replication, Recombination}. The set G is ordered according to sizes of its elements: DNA is smallest and bacterium is biggest ones. The set M has relative order: one part (Membrane, Nucleus) characterizes microbiological structure of objects from G, but another part (Replication, Recombination) characterizes the way of breeding, and these parts are incomparable. In the concept lattice the bacterium is placed in the concept C1 = ({Prokaryotes, Eukaryotes, Bacterium}, {Membrane, Replication}). In this concept, three objects {Prokaryotes, Eukaryotes, Bacterium} constitute the extent of the concept; they are united by their mutual attribute {Membrane, Replication} which constitute the intent of the concept. The concept C1 is more general concept than the concept C2 = ({Eukaryotes}, {Nucleus}).
Also on the Fig. 1 there are two different branches of
concepts characterizing two families: the viruses and
DNA and prokaryotes, eukaryotes and bacteria. This
concept demonstrates the fact of separation of objects
from the set G into two important branches. The link
between them is the attribute “Membrane”. It is known
[
This example demonstrates specific ways of extracting knowledge from conceptual lattice: analyzing formal concepts in concept lattice; analyzing conceptual structures in concept lattice – its sub lattices in the general case.
The main problem in applying FCA on textual data is the problem of building formal context. If textual data is represented as natural language texts then this problem becomes acute.
There are several approaches to the construction of
formal contexts on the textual data, presented as separate
documents, as data corpora. One, mostly applied variant
is the context in which the objects are text documents and
the attributes are the terms from these documents.
Another variant is building formal context directly on the
texts and the formal context may represent various
features of textual data:
semantic relations (synonymy, hyponymy,
hypernymy) in a set of words for semantic
matching [
We apply the second approach and use conceptual graphs for representing semantics of individual sentences of a text.
Consider in general the process of CGs – FCA modeling.
It includes the following steps.
1. Acquiring a set of conceptual graphs from input
texts. As it is mentioned above conceptual graphs can be
acquired from texts by existing information systems. For
example they can be created by our system CGs Maker
1. Some details about it can be found in [
According to this approach, a conceptual graph is constructed so that there is the central concept in it which is realized as a verb. If there are no verbs in a sentence then method also creates conceptual graph. Verbcentered approach is important for us since it provides predicate forms in the structures of conceptual graphs.
These forms are mostly used for representing conceptual graph semantics.
2. Aggregating the set of conceptual graphs.
Aggregation is needed to exclude excessive dimension of conceptual models, not related to useful information. We have tested following ways of conceptual graphs aggregation: conceptual graphs clustering and using corpus tagging together with support of concept types in conceptual graphs. Clusters of conceptual graphs need to be semantically interpreted which may lead to additional investigations. The second method is more constructive since it selects those conceptual graphs which concepts have mappings to certain domain. Such domain of terms may be presented by corpus tagging or by thesaurus.
Some details of aggregation are below.
3. Creating formal contexts. This is the central point of CGs – FCA modeling. One or several formal contexts have been built on the aggregated conceptual graphs. The number of formal concepts and the method of building them depend on the problem being solved with CGs – FCA modeling.
4. Building concept lattice. Having a formal context
as input data, a concept lattice may be created by using
various algorithms. There is a field of research in FCA
devoted to creating and developing algorithms for
concept lattice creation [
5. Knowledge extraction from concept lattice. In concept lattice it is possible to identify connections 1 The lightweight online version of CGs Maker for simple English and Russian texts can be found at http://85.142.138.156:8888 . between its concepts according to the principle of "common – particular". Each concept may be interpreted as the set of potential facts of certain level, which is associated with other facts. So the knowledge extracted from concept lattice may be interpreted a s facts.
In the theory of conceptual graphs aggregation means
replacing conceptual graphs by more general graphs [
Clustering is a way of aggregation of conceptual graphs. Graphs which are the nearest ones to the centers of clusters have been treated as general graphs.
We have studied several approaches for clustering
conceptual graphs [
2n( c ) sc n( 1) n( 2 ) similar “semantically”. That means that their concepts have the same type. For example different names of bacteria belong to the type “bacterium” or the type “the name of bacteria”.
The second way of conceptual graphs aggregation is based on supporting types of concepts by using external resources. Thesaurus or corpus tagging may be such resource. Section 3 contains additional details.
The crucial step in the described process of CGs – FCA modeling is creating formal contexts on the set of conceptual graphs.
At 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.
Fig. 2 shows an example of conceptual graph for the sentence “Burkholderia phytofirmans belongs to the beta-proteobacteria and was isolated from surfacesterilized glomus vesiculiferum-infected onion roots.” and relative similarity sr
2m( c ) m c ( 1) m c ( 2 ) .
Here 1 , 2 - conceptual graphs, c 1 2 is their common sub graph, n( i ) - number of concepts of graph i , m ( i ) - number of relations of graph i , m ( i ) c is the number of relations of conceptual graph i , at least one of which belongs to the common sub graph c .
If two conceptual graphs have identical concepts then their conceptual similarity has non zero value. Relative similarity is non-zero when two conceptual graphs have identical structures of patterns of conceptual relations.
We used conceptual and relative similarities (1), (2)
and their combination in the experiments of conceptual
graphs clustering [
All numerical characteristics of conceptual graphs clustering results (number of clusters, dimensions of clusters, etc.) are not informative. Clusters of conceptual graphs need to be semantically interpreted. The way of that interpretation depends on the nature of the problem to be solved with conceptual graphs.
Both conceptual and relative similarity measures share a common sub graph c . But two conceptual graphs may have no common sub graph but may be (1) (2)
Figure 2 Conceptual graph for the sentence “Burkholderia phytofirmans belongs to the betaproteobacteria and was isolated from surface-sterilized glomus vesiculiferum-infected onion roots.”
This graph has five conceptual relations “attribute”
but only four of them indicate the objects and attributes
valid for formal context. Using “phytofirman” as object
and “Burkholderia” as attribute in the formal context is
wrong way because “Burkholderia phytofirmans” is
known full name of this bacterium [
Remaining elements of conceptual graph on the Fig. 2 are not useless and play significant roles in creating formal context. Conceptual graph on the Fig. 2 represents two facts: 1. bacterium Burkholderia phytofirmans belongs to beta-proteobacteria; 2. this bacterium infects the onion.
To provide the presence information about those and other facts in the formal contexts the following rules are implemented as mostly important when creating formal contexts. 1. Not only individual concepts and relations, but also patterns of connections between concepts in conceptual graphs represented as sub graphs have been analyzed and processed. These patterns are predicate forms <object> - <predicate> - <subject> which in conceptual graphs look as the template <concept>- (patient) - < verb > - (agent) <concept>. Not only agent and patient semantic roles but also other similar to them (goal on the Fig. 2) roles are allowed in templates. 2. The hierarchy of conceptual relations in conceptual graphs is fixed and taken into account when creating formal context. This hierarchy exists on the Fig.2: relations “agent”, “goal”, “from”, “modificator” are on the top level and relations "attribute" belong to underlying levels. Using this hierarchy of conceptual relations we can select for formal contexts more or less details from conceptual graphs.
These empirical rules are related to the principle of
pattern structures which was introduced in FCA in the
work [
Conceptual graph is a pattern for the object it represents. A sub graph of conceptual graph is projection of a pattern. Namely projections are often used for creating formal contexts. Similarity operation on conceptual graphs is a measure of similarity which is applied in clustering. The relative similarity (2) is mostly close to be similarity operation for patterns.
The CGs – FCA modeling technique was tested in
various levels of its realization for classification
messages in technical support services [
Bioinformatics is the field where Data Mining and Text
Mining applications are growing up rapidly. New term of
“Biomedical Natural Language Processing” (BioNLP)
has been appeared there [
So called “research community around PubMed” [
Our experiments have been carried out using text corpus
of bacteria biotopes which is used in the innovation
named as BioNLP Shared Task [
A BioNLP data is always domain-specific. All the texts in the corpus are about bacteria themselves, their areal and pathogenicity. Not every text contains these three topics but if some of them are in the text then they are presented as separate text fragments. This simplifies text processing.
The CGs – FCA modeling environment has DBMS for storing and managing data used in experiments. We use relational database on the SAP-Sybase platform. Database stores texts, conceptual graphs, formal contexts and concept lattices. Special indexing is applied on textual data.
According to the BioNLP Shared Task initiative [
The task of Named Entity Recognition on the corpus of bacteria descriptions is formulated as seeking bacteria names presented directly in the texts or as co-references (anaphora).
Relations Extraction means seeking links between bacteria and their habitat and probably diseases it causes.
The task of Named Entity Recognition has direct solution with conceptual graphs. The only problem which is here is anaphora resolution.
Anaphora resolution is the problem of resolving references to earlier or later items in the text. These items are usually noun phrases representing objects called referents but can also be verb phrases, whole sentences or paragraphs. Anaphora resolution is the standard problem in NLP.
Biotopes texts we work with contain several types of anaphora: hyperonym definite expressions (“bacterium” “organism”, “cell” - “bacterium”), higher level taxa often preceded by a demonstrative determinant (“this bacteria”, “this organism”), sortal anaphors (“genus”, “species”, “strain”).
For anaphora detection and resolution we use a pattern-based approach. It is based on fixing anaphora items in texts and establishing relations between these items and bacteria names. We use double-pass algorithm for anaphora resolution which controls so called isolated concepts appeared on the first pass of the algorithm. Isolated concepts are those concepts which are not connected by relation with any other concepts. As a rule they appear when a sentence contains abbreviations or code of bacterium. For example, in the sentence “Streptococcus thermophilus strain LMG 18311” there is code of bacterium strain. This code will be presented as isolated concept in conceptual graph. Later in another sentence there is text fragment “…two yogurt strains of S. thermophiles …” which has abbreviation of the name of bacterium. Having isolated concept with strain code we can identify it with bacterium using corpus tagging. For resolving abbreviations programming triggers which react to the second word after abbreviation are applied.
To evaluate the quality of this solution of NER the
standard characteristics of recall, precision and F-score
were calculated. To obtain them it was needed to mark
named entities manually in the texts used in experiments.
The table 1 contains values of recall, precision and
Fscore compared with corresponding values from the
work [
Recall Precision F-score Alvis 0,52 0,46 0,59 SemText 0,42 0,53 0,47 The ratio of the values of recall and precision is more informative than their individual ones and is shown on the Fig. 3. According to the table 1 and Fig. 3 we resume that there is medium quality of our solution of NER. It is explained by disability of our algorithm to interpret all possible isolated concepts in conceptual graph. As a result approximately half of marked lexical elements were not recognized as entities.
Conceptual graphs represent relations between words. Therefore they can be applied for relations extraction but only in one sentence. For extracting relations between bacteria on several texts we applied concept lattices.
We had selected 130 mostly known bacteria and have processed corresponding corpus texts about them. All the texts were preliminary filtered for excluding stop words and other non-informative lexical elements.
Three formal contexts of “Entity”, “Areal” and “Pathogenicity” were built on the texts. They have the names of bacteria as objects and corresponding concepts from conceptual graphs as attributes. Table 2 shows numerical characteristics of created contexts.
Figure 3 Recall and precision ratio for NER solution on 60 objects Table 2 Numerical characteristics of created contexts Context Number Number Number of name of of formal objects attributes concepts Entity 130 26 426 Areal 130 18 127 Pathogenicity 130 28 692
Among attributes there are bacteria properties (gramnegative, rod-shaped, etc.) for “Entity” context, mentions of water, soil and other environment parameters for “Areal” context and names and characteristics of diseases for “Pathogenicity” context
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.
For extracting relations we use visualization on the current stage of modeling technique. It allows getting results only for relatively small lattices.
Often relations between concepts in concept lattice may be treated as facts. Extracting facts from concept lattices is realized by forming special views constructed on the lattice and corresponded to certain property (intent in the lattice) or entity (extent in the lattice) on the set of bacteria. Every view is a sub lattice. It shows the links between concrete bacterium and its properties.
An example of such view as the fragment of lattice is shown on Fig. 4. The lattice on the Fig. 4 contains formal concepts related to the following bacteria: Borrelia turicatae, Frankia, Legionella, Clamydophila, Thermoanaerobacter tengcongensis, Xanthomonas oryzae. Highlighted view on the figure illustrates gramnegative property of bacteria. Such bacteria are resistant to conventional antibiotics.
Using this view, some facts about bacteria can be extracted: only three bacteria from the set, Thermoanaerobacter tengcongensis, Clamydophila and Xanthomonas oryzae, are gramnegative; two gram-negative bacteria, Thermoanaerobacter tengcongensis and Xanthomonas oryzae, have the shape as rod; one of gram-negative bacteria, Clamydophila, is obligately pathogenic.
Note that attribute obligately pathogenic was formed directly from the two words in the text according to the rule of marking words denoting extreme situation.
Comparing our results of relations extraction with the
known ones from [
This paper describes the idea of joining two paradigms of conceptual modeling - conceptual graphs and concept lattices. Current results of realizing this idea as CGs – FCA modeling on textual data show its good potential for knowledge extraction.
In spite of advantage of CGs – FCA modeling there are some problems which need to be solved for improving the quality of modeling technique. 1. Conceptual graphs acquired from texts contain many noise elements. Noise is constituted by the text elements that contain no useful information or cannot be interpreted as facts. Noise elements significantly decrease efficiency of algorithms of CGs – FCA modeling. To exclude noise we need to distinguish textual data that can be excluded from consideration, for example, information about when and by whom a bacterium was first identified. 2. Empirical rules which we use for creating formal contexts cannot embrace all configurations of conceptual graphs. More formal approach to creating formal contexts on the set of conceptual graphs will guarantee the completeness of solution. We guess that using patterns structures and their projections is that way of formalizing CGs – FCA modeling technique. 3. The next stage of developing CGs – FCA modeling is creating fledged information system which process user queries and produce 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.