In this paper we present a novel approach to handle querying over a concept lattice of documents and annotations. We focus on the problem of “nonmatching documents”, which are those that, despite being semantically relevant to the user query, do not contain the query's elements and hence cannot be retrieved by typical string matching approaches. In order to find these documents, we modify the initial user query using the concept lattice as a guide. We achieve this by identifying in the lattice a formal concept that represents the user query and then by finding potentially relevant concepts, identified as such through the proposed notion of cousin concepts. Finally, we use a concept semantic similarity metric to order and present retrieved documents. The main contribution of this paper is the introduction of the notion of cousin concepts of a given formal concept followed by a discussion on how this notion is useful for lattice-based information indexing and retrieval.
As the amount of information grows, the ability to retrieve documents relevant to the needs of the user increasingly becomes more important. Several applications have been proposed, regarding this task, in the field of Information Retrieval (IR). However, as the information becomes more complex (not only text, but also multimedia documents) and specific (domain-oriented), the capacity to organize it becomes as important as the capacity to retrieve it.
Formal Concept Analysis (FCA) is a robust and widely used framework to organize
objects based on their relations through their attributes in a concept lattice [
In this work, we present an approach to retrieve documents from a document-term concept lattice, considering that concepts can be close with respect to their position within the lattice and semantically similar to one another. We use both of these notions to find which are the most relevant documents for a given user query.
The rest of this paper is organized as follows: Section 2 presents the related research literature. Section 3 briefly introduces FCA and presents our proposed approach for navigating the lattice using the notion of cousin concepts, as well as for ranking the selected concepts with respect to their semantic similarity. Section 4 presents and discusses the experimental results and finally section 5 presents the conclusions of our work. 2
2.1
Formal concept analysis is a data representation, organization and management
technique with applications in many fields of information science, ranging from knowledge
representation and discovery to logic and AI [
The CLR method consists of three main steps: i) construction of the formal context of documents-terms and building of the corresponding concept lattice ii) insertion in the lattice of a new concept that represents the user query, using a subset of the attributes of the formal context and iii) retrieval and ranking of the relevant concepts using a nearest-neighbour approach, which depends on their topological path distance, within the lattice, from the original concept. The topological path metric used is called distance ”ring”, and it measures the radius of distance between two concepts, using as distance metric the length of the shortest path between them. The ring metric provides a partially ordered retrieval output, according to which all the documents that are equally distant from the original concept, i.e. belong to the same distance ring, are given the same ranking score.
Carpineto and Romano, also compare the CLR method with two other
Information retrieval methods, namely Hierarchical Clustering-based Ranking (HCR)[
The limitations of the traditional CLR method include firstly, the need to build the
whole lattice before retrieving the related concepts. This issue determines the
complexity and computational time required to address the problem, and it may result in
nonrealistic solutions for large document collections, like for instance the TREC dataset
([
To address these limitations, in this paper we propose a novel approach, which seeks
to ensure semantic similarity with the original user query, both through the way that
the lattice is traversed and through the way that the concepts are ranked. In particular,
we introduce a new topological-based concept characteristic, called cousin concepts,
to navigate the lattice and retrieve candidate related concepts. In parallel, for ranking
the retrieved concepts we do not rely only on structural concept similarity features,
but instead we use a metric that allows the weighting of both structural and semantic
similarity aspects [
In order to present our approach, first we present a brief description to Formal Concept
Analysis (FCA). The basics of FCA are introduced in [
Data is encoded in a formal context K = (G, M, I ), i.e. a binary table where G is a set of objects, M a set of attributes, and I ⊆ G × M an incidence relation. Two derivation operators, both denoted by ′, formalize the sharing of attributes for objects, and, in a dual way, the sharing of objects for attributes: ′ : ℘(G) −→ ℘(M ) with A′ = {m ∈ M | ∀g ∈ A, gI m} ′ : ℘(M ) −→ ℘(G) with B′ = {g ∈ G | ∀m ∈ B, gI m}, where ℘(G) and ℘(M ) respectively denote the powersets of G and M . The two derivation operators ′ form a Galois connection between ℘(G) and ℘(M ). The maximal sets of objects which are related to the maximal sets of attributes correspond to closed sets of the composition of both operators ′, denoted ′′, for ℘(G) and ℘(M ) respectively. A pair (A, B) ∈ ℘(G) × ℘(M ), where A = B′ and B = A′, is a formal concept, A being the extent and B being the intent of the concept. The set CK of all concepts from K is ordered by extent inclusion, denoted by ≤K, i.e. (A1, B1) ≤K (A2, B2) when A1 ⊆ A2 (or dually B2 ⊆ B1). Then, LK = hCK, ≤Ki forms the concept lattice of K.
Typically, a concept lattice to index documents is created from a formal context
Kindex = (G, M, I) where G is a set of documents and M is a set of terms. Thus, the
set I represents document annotations (i.e. gIm indicates that the document g is
annotated with the term m). In a nutshell, to retrieve documents given a conjunctive query3
q = {mi}, mi ∈ M (mi in the query are hereafter referred as keywords), the goal is
to find those formal concepts (A, B) where B ∼ q and to retrieve the documents in A.
The usual approach is to insert into the lattice a query concept Cq = ({∅}, q) [
The first disadvantage with the navigating in the hierarchy of Cq refers to the generalization of the query. By obtaining the super-concepts of the query concept inserted in the lattice, a level of granularity already provided by the user is lost. For example, for a query of the form “complications, arthroscopy”, a query concept Cq = (Aq = {∅}, Bq = {complications, arthroscopy}) is created within the lattice. Any superconcept Csup = (Asup, Bsup) of the query concept has to comply with Bsup ⊂ Bq. In this case, only three super-concepts can be obtained: Csup1 = (Asup1, {complications}), Csup2 = (Asup2, {arthroscopy}) and Csup3 = (Asup3, {∅}). However, Asup1 contains documents about complications in any aspect leading to a decrease in precision. The same happens with documents in Asup2 containing documents about arthroscopy in general whether the user had already specified a restriction for them. Csup3 represents the supremum where Asup3 contains every possible document, this, of course, is the worst case scenario where the system has no restrictions to retrieve documents.
The second disadvantage is about the specification of the query. By obtaining the
whole set of sub-concepts of the query concept the system assumes restrictions not
provided by the user. While this is the main idea behind query expansion [
Regarding these problems we propose a technique to improve information retrieval based on concept lattices using the idea of “concept similarity” provided by Formica. We combine this idea with a novel heuristic to navigate the lattice in order to find those concepts holding relevant documents for a given query. 3.1
Given the formal context Kindex and the query q = mi at the beginning of this section,
a very simplistic approach to retrieve documents relevant to the query is to find those
concepts (Aj , Bj ) where mi ∈ Bj : ∀mi ∈ q defined in [
It should be noted here that, for a given query q, the matching concept Cq may not exist. This is more likely to happen if the number of keywords is high. In a complete concept lattice (not filtered through any means and constructed using the total amount of information), such a case would actually mean that there are no documents which comply with all the restrictions provided in the user’s query. While some strategies can be implemented to overcome this issue (asking the user to provide a simpler query or manipulating the query in order to answer) for the scope of this work we do not elaborate on this and we rather consider the case of an existing matching concept.
Once the matching concept Cq = (Aq , Bq) is found, all documents in Aq can be retrieved to the user. Since the number of documents in Aq may be not sufficient, what is important, in the following, is how to complete the answer with more documents using the lattice.
A simple strategy would involve the hierarchy of Cq, however every sub-concept (Asq , Bsq) ≤K (Aq , Bq) will provide no different documents than those in Aq since Asq ⊂ Aq. Super-concepts of Cq are not useful either because of the problems described in the beginning of this section regarding generalization. Hence, in order to complete the answer with more documents, it is necessary to obtain from the concept lattice some formal concepts which are neither super- nor sub-concepts of (Aq, Bq). To achieve this, we use the notion of cousin concepts defined as follows.
Definition of cousin concepts: Two concepts (A1, B1) and (A2, B2) which are not comparable for ≤K are said to be cousins iff there exists (A3, B3) 6=⊥ such that (A3, B3) ≤K (A1, B1) and (A3, B3) ≤K (A2, B2) and dK((A2, B2), (A3, B3)) = 1 (where ⊥ is the bottom concept and dK measures the minimal distance between two formal concepts in the lattice K). Intuitively, this means that (A1, B1) and (A2, B2) do not subsume each other and that (A3, B3) can be either the lower bound or be subsumed by the lower bound (A1, B1) ⊓ (A2, B2) (where (A1, B1) ⊓ (A2, B2) denotes the lower bound of (A1, B1) and (A2, B2).
The use of cousin concepts allows us to move in the lattice from one concept to another using the relations that the elements in their intents possess and that are expressed through their common subsumer. In the example on Figure 1, C2 is a cousin concept of C1 because of concept C3. The attributes “arthroscopy”, “complication” and “infection” are all related through the intent of concept C3. In this small example, if C1 is the matching concept, moving from it to concept C2 is the same as replacing the word “complication” with the word “infection” in the query. The extent of concept C2 will contain documents, some of which are different from those of C1 and therefore they can be used to complete the answer provided by C1.
We may also notice that the use of C3 works as a query expansion, adding attributes to the original user query, while the use of C2 works as a query modification, since its attributes are a subset of the attributes of C3.
Using the entire sub-hierarchy of the matching concept (excluding the infimum) allows us to retrieve several cousin concepts which can be used to complete the answer far beyond the initial set of documents contained in the matching concept’s extent. Each cousin concept is a possible query modification obtained from a query expansion, represented by the sub-concepts of the matching concept.
Although cousin concepts are useful to expand the answer by representing query modifications, their use may entail the same problem described in the beginning of this section, as the second disadvantage of structure-based concept retrieval. In the same example on Figure 1 concepts C2 and C4 are cousin concepts of C1. However, in this scenario the system cannot decide which set of documents, between those of C2 and C4, should be retrieved first.
A way to rank cousin concepts is therefore necessary in order to decide which
documents should be retrieved to the user first. In this paper we do so using the measure of
concept similarity proposed by Formica [
|A1 ∩ A2| max(|A1|, |A2|) ∗ w +
M(B1, B2)
max(|B1|, |B2|)
∗ (1 − w)
where 0 ≤ w ≤ 1 is a weighting parameter and M(B1, B2) is the maximization
of the sum of the information content similarities between each possible pair of terms
created using one term from B1 and another from B2. Information content similarity
between two terms is measured using their distance in a lexical hierarchy and/or their
co-occurrence in a text corpus. The full explanation of this metric is beyond the scope of
this paper. For further information, the reader is referred to the original work of Formica
[
Consider the example of Figure 1: Concepts C2 and C4 are both cousin concepts of the matching concept C1, and they have the exact same structural features, i.e. the cardinalities of the intersections of their extents/intents with the matching concept are the same, as well as their extent/intent cardinalities. However, when using the semantic similarity metric defined above with w = 0.5 and Wordnet4 as the external lexical hierarchy, we observe that sim(C1, C2) = 0.7275, while sim(C1, C4) = 0.45, because the pair (complication, infection) has a higher semantic relation than the pair (complication, practice). In this way, we may rank and retrieve the documents of concept C2, higher than those of concept C4. Differentiations in the weight value w allow for differentiations in the preference over the structural (from the extents) and semantic (from the intents) similarities of the compared concepts. 4
We applied our approach using the MuchMore5 dataset, which contains annotated
medical document abstracts (7822 documents, 9485 single or multi-word terms). In order to
answer a given user query we follow a 3-step knowledge discovery process, as follows.
Step 1 - Data preprocessing: Pre-filter the set of documents and terms Since the
creation of a lattice containing the full set of documents/terms would be
computationally expensive, we create a reduced lattice for each given user query. To do so, we
implement a simple pre-filtering strategy of iterative expansion similar to the one described
in [
Unfortunately, this strategy yields more than 95% of the corpus’ documents
because of highly frequent terms. To avoid this, documents with a number of terms below
the average (in the above example, 7 terms) are not included in the expanded set of
documents (3485 documents for the example). It should be noted that the pre-filtering
strategy can be further improved considering weighting techniques such as tf.idf,
pivoted normalized document length [
is straightforward since we rely on a fixed framework (Coron Toolkit6). For the example of query qs we obtain 134718 formal concepts without using support pruning.
retrieval step consists of three sub-steps, described in the following.
1. Find the matching concept. We search for the matching concept Cq in the lattice
using a level-wise algorithm, starting from the supremum. The matching concept
Cq is the closer concept to the supremum which contains in its intent all the
keywords provided in the query. The existence of the matching concept is predicated in
the assumption of a conjunctive query to pre-filter the dataset and create the formal
context. In the case that there are no documents containing at least all the keywords,
the query is consider unsuccessful and the retrieval process is stopped at step 1. The
documents in the extent of the matching concept are retrieved to the user and they
are hereafter referred to as exact answer.
2. Find the cousin concepts of the matching concept. Cousin concepts are obtained
for the matching concept and for each of its sub-concepts Ci. A list called candidate
answers is created storing the pair (Ci, Cj ) where Ci ≤ Cq and Cj is a cousin
concept of Ci. For qs, the candidate answers list contains 2301 (concept, cousin
concepts) pairs.
3. Rank the cousin concepts. The ranking process is performed using the
similarity measure described in section 3.2. Every pair (concept, cousin concept) from
the candidate answers list is compared, or what is the same, each query expansion
is compared to its correspondent query modification. Formica’s concept similarity
was implemented using Wordnet [
Table 2 shows the results for two queries executed using the described approach. For qs = {“arthroscopy”,“complication”} the exact answer retrieved 11 documents of which 7 are relevant to the user. The close answer, composed of the documents retrieved from the ranked cousin concepts, contains 100 documents of which 6 are relevant to the user. Therefore, out of the 21 documents relevant to the user the approach was able to retrieve 13.
It is of special interest to analyse the characteristics of the obtained results. The cousin concept with intent joints, surgical aspects, complication, diagnostic has a similarity of 0.71 with the concept with intent arthroscopy, surgical aspects, complication, diagnostic which is a sub-concept of the matching concept created for qs and hence, does not have additional documents than those already retrieved. What can be appreciated here is that the algorithm works firstly by expanding the original query with related 6 http://coron.loria.fr/site/index.php 7 Wordnet is a dictionary where terms are grouped by synonymia (synset) and ordered in a hierarchical tree by the hypernym relation. 8 The Hungarian algorithm minimizes the sum of values in the diagonal of a square matrix. terms (from arthroscopy to surgical aspects9) and secondly by modifying the expanded query with a semantically similar term (from arthroscopy to joints). The above process is illustrated in Table 1.
The second query in Table 2 is also of interest in the sense that it indicates algorithm robustness. The word laparoscopic is not present in Wordnet, making it not suitable for the comparison in the similarity measure. This means that laparoscopic can be replaced with any other term since the algorithm is not able to measure the difference. However, since the similarity measure relies also in extent intersection, the algorithm will try to replace laparoscopic with terms used by documents similar to those in the exact answer. In that way, the first ranked close answer is correct and its intent is complication, risk, cholecystectomy. Notice that in this case the algorithm does not conclude that the term risk is semantically close to the term laparoscopic, but that it is the best term to replace the latter in the query.
Query arthroscopy, complication complication, laparoscopic cholecystectomy In this paper we present a technique to use a concept lattice for the retrieval of documents from a given user query. The proposed technique differs from previous approaches in two main aspects: the lattice navigation algorithm is not restricted to the
hierarchy of the query concept and the ranking algorithm is based on the semantic similarity, rather than on the structural characteristics of the compared concepts.
In terms of navigation, we introduce the notion of cousin concepts, which represents query modifications that can be used to retrieve documents different from those directly related to the query. In terms of ranking, we use external knowledge sources (a lexical hierarchy and a text corpus) to measure semantic similarity and order the retrieved cousin concepts by relevance to the initial query.
We illustrate our approach using two examples from a dataset of medical document abstracts. We also explain certain limitations of the proposed approach, mainly regarding the performance the concept lattice construction and the availability of the terms of the user query in the dataset. Currently, we are applying this approach on the same dataset but on a full scale, in order to measure precision and recall, as well as to compare the proposed technique with other Information Retrieval state-of-the-art techniques.