In this paper we introduce a novel approach to information retrieval (IR) based on Formal Concept Analysis (FCA). The use of concept lattices to support the task of document retrieval in IR has proven effective since they allow querying in the space of terms modelled by concept intents and navigation in the space of documents modelled by concept extents. However, current approaches use binary representations to illustrate the relations between documents and terms (“document D contains term T”) and disregard useful information present in document corpora (“document D contains X references to term T”). We propose using pattern structures, an extension of FCA on multi-valued and numerical data, to address the above. Given a set of weighted document-term relations, a concept lattice based on pattern structures is built and explored to find documents satisfying a given user query. We present the meaning and capabilities of this approach, as well as results of its application over a classic IR document corpus.
Information retrieval (IR), is a problem of lasting interest for the research community.
Among the tasks comprising the IR domain, document retrieval (i.e. the search and
ranking of documents that are relevant to an original user query from a given document
corpus) is one of the most popular in the field given its importance in everyday routines.
In the wide spectrum of techniques applied to support document retrieval, formal
concept analysis (FCA) has gained interest in the last years [
Formal concept analysis (FCA) is a mathematical formalism used for data analysis
and classification, which relies on the dualistic understanding of concepts as consisting
of an extent (the objects that belong to the concept) and an intent (the attributes that
those objects share) organized in a lattice structure called a concept lattice [
In a typical CL4IR approach, a binary table of documents and terms is created
and then, using FCA algorithms, the respective concept lattice is created. This lattice
contains several formal concepts, each defined by a set of documents (extent) and the
set of terms that they share (intent). Thus, the lattice provides a multiple hierarchical
classification of documents and terms which can be navigated and searched as an index,
to retrieve concepts that are “close” or “similar” to the original query concept. In this
way a CL4IR system exploits the connections of concepts within the lattice to find
relevant documents for a given query and takes advantage of the lattice structure to
enrich the answer in different ways: by navigating the lattice to look for approximate
answers through generalizations and specifications of the original query concept’s intent
[
In this article we present a novel CL4IR approach, which deals with numerical
datasets, i.e. document-term relations, where a document is annotated by a term with a
certain weight. This approach provides CL4IR systems with an extended query space,
on which vector-space ranking methods can be adapted and applied. In parallel, this
approach retains the main advantage of using lattices as the document search index,
which is the provision and exploration potential of the complete query space. Our
approach is based on the pattern structures framework, an extension of FCA to deal with
complex data [
The setting of a typical concept lattice for information retrieval (CL4IR) application is given by a formal context K = (D; T; I) made of a set of documents D, set of terms T and an incidence relation I = f(di; tj )g indicating that document di contains term tj . Table 1 illustrates a document-term formal context created from a corpus of 9 documents and 12 terms.
anhum itfraceen trecupom rseu tsseym rseonp tiem PSE rsuv tree rapgh irnom e s y
e
Given a user query q = ft1; t2:::tjqjg , the document retrieval task consists in returning a set of documents ordered by “relevance” w.r.t. the query q. In CL4IR systems a query can be represented as a virtual document containing the set of terms ft1; t2:::tjqjg. Then, the query is inserted in the formal context as another object and the incidence relation set I is updated to include the relations of the virtual query-document and its terms. The formal context becomes Kq = (D + fqg; T; I + f(q; ti)i::jqjg).
The standard procedure to find “relevant” documents within the concept lattice
consists in identifying the query concept (which is defined as the object concept of the
virtual object q and denoted by (q) = ((q0)0; q0)) and concepts related to the query
concept (for example, its superconcepts) which can provide further results. We refer to
the later concepts as “answer concepts”. For the formal context in Table 1, consider the
query q with terms “graph” and “tree” (grey row). Figure 1 shows the concept lattice
derived from this formal context (including the query). The query concept corresponds
to concept 17 and contains in its extent documents d7 and d8 which satisfy the query
and can be retrieved to the user. The superconcepts of the query concept (concepts 7
and 8) contain documents d6 and d9 which can also be retrieved. Different relevance
measures can be used to rank the retrieved documents. For example, the topological
distance within the lattice between the query concept and the “answer concepts” (i.e.
concepts partially satisfying the query) can be calculated and in this case documents d7
and d8 are at distance 0 (more relevant), while d6 and d9 are at distance 1 (less
relevant). Other such measures include semantic distance, extent intersection, and Jaccard
similarity [
More generally, the concept lattice defines a query space where each formal concept
C can be considered as a conjunctive Boolean query (i.e. a query where the constraint
is given by the conjunction of the attributes in the intent of C) and a combination of
formal concepts provides disjunction and negation (e.g. The union of concepts 7 and 8
in Figure 1 satisfies the disjunctive query “graph” or “tree”). Unfortunately, the binary
case is the “ideal world”. In most real-world datasets the relation between a document
and a term is built w.r.t. a measure such as frequency, distance or weight involving a
range of numerical values [
A document corpus can be defined as a term-document matrix A = [aij ], where
terms ti 2 T are in rows, documents dj 2 D in columns and each cell aij of the matrix
represents the “value” of the term ti in the document dj , given by a function val(dj ; ti)
(weight, frequency, etc.). In order to work with this kind of datasets, a CL4IR system
can resort to interordinal scaling [
Here, we introduce the pattern structure framework firstly described in [
A pattern structure K = (G; (P; u); ) is a generalization of a formal context. In K, G is a set of objects, (P; u) is a semi-lattice of object descriptions and : G ! P is a mapping associating a description to an object. The description of an object g 2 G is a vector of intervals v = h[li; ri]ii2f1::jMjg, where v 2 P , li; ri 2 R and li ri .
In (P; u) the similarity operator u applied to va = h[li1; ri1]i and vb = h[li2; ri2]i yields the convex hull va u vb = h[min(li1; li2); max(ri1; ri2)]i where i 2 f1::jM jg. The associated subsumption relation is defined as va u vb = va () va v vb.
A Galois connection between }(G) (powerset of G) and (P; u) is defined as follows:
X
= dg2X (g) ; v
= fg 2 Gjv v (g)g
where X represents the common description to all objects in X while v represents
the set of objects respecting the description v. A pair (X; v) such as X = v and
v = X is called a interval pattern concept (ip-concept) with extent X and pattern
intent v. Ip-concepts can be ordered in an interval pattern concept lattice (ip-concept
lattice). Algorithms for computing ip-concepts from an interval pattern structure are
proposed in [
A document corpus or a term-document matrix, as described at the end of Section 2, can
naturally be represented as a many-valued context [
To deal with Kq, we define the pattern structure as (D + fqg; (P; u); ) where interval patterns in P contain the interval-vector representation of documents in jT j dimensions (one for each term). The mapping (d) = h[val(d; ti); val(d; ti)]i2[1::jT j]i assigns an interval pattern representation to a document (or the virtual query-document) consisting of a zero-length interval for each term existing in T at the value of the term in the document (e.g. in Table 2, (d1) = h[0:33; 0:33][0:33; 0:33][0:33; 0:33][0; 0] : : : [0; 0]i, where [0; 0] is represented by [ ]). The similarity operator u applied to two interval patterns returns the convex hull between their document representations. From the pattern structure we construct the ip-concept lattice representing the query space which will be used to retrieve documents in a similar way as binary approaches.
The query concept is still considered as the object concept of q. However the semantic of the query space changes. While in the binary case the query space represents a pool of Boolean query possibilities, here the query space can be considered as a vector space where the query is grouped with documents having similar representations. For example, consider the first three columns in Table 3 where each row represents an ip-concept. Concept 1 is the query concept which in its extent includes documents d7 and its interval pattern (intent) only includes zero-length intervals in all 12 dimensions, making the description of the query identical to the description of d7. Concept 2 is a superconcept of 1, whose extent contains d7 and d8. This time, there are only 9 zerolength intervals in all 12 dimensions. Concept 2 is less similar to the query than concept 1 w.r.t 3 dimensions. Following with concept 3, we can see that the later is less similar to the query than concept 1 w.r.t. 4 dimensions. We get in this way a “natural” ranking of the concepts.
In order to rank ip-concepts we rely on the notion of maximal distance within an
interval pattern. For illustrating this notion, we will use the geometrical interpretation
of patterns already introduced in [
0 0.408 0.704 0.707 0.808 0.866 0.909 0.909 0.935 * Grey row represents the query concept. between its edges ([ ] represents the zero-length interval [0; 0]). Calculating a concept lattice is an expensive task which can yield a large amount of concepts making it prohibitive for large document corpora. The scenario is worst for pattern structures since for every concept the size of the intent is set to the whole set of attributes adding even more complexity. Calculating the whole query space of a termdocument matrix is not advisable, since for a given query only a small part of the whole space is required. In order to avoid a sizeable query space in each step of the retrieval process, progressive actions to filter data are performed. In the following, we describe the retrieval process and each action.
1. Constructing the pattern structure: The process starts with the input of a query q = ft1; t2; :::; tjqjg and ends after the pattern structure containing the virtual querydocument is created. We include in the set of documents only those which contain at least a given number of the terms provided in the query, which can be performed at a negligible cost by firstly storing documents and terms in a relational database. The set of terms only include those provided in the query. The minimum number of terms for a document is left as a parameter of the process.
2. Constructing the ip-concept lattice: This step receives the pattern structure in
order to create an ip-concept lattice. A standard FCA algorithm, namely Ganter’s
algorithm [
Many ip-concepts found in the interval pattern lattice are not useful for document retrieval purposes. For example, the framework creates ip-concepts with documents which do not share terms (e.g. consider the interval h[0; 1][0; 1][0; 1]i created from the documents sharing no terms with orthogonal representations v1 = h[0; 0][1; 1][1; 1]i and v2 = h[1; 1][0; 0][0; 0]i). We denominate these concepts non-informational.
In order to reduce the amount of non-informational concepts, we modified the u
operator in the set of ordered patterns (P; u) such as [l; r] u [0; 0] = [ ] and [l; r] u [ ] =
[ ]; 8l; r 2 R. The interval [ ] has been used before to indicate absence of similarity
[
To test the validity of the proposed approach, we applied it on a popular IR dataset
which is openly available. We refer to this implementation as “ip-CL4IR”. The CISI
dataset4 consists of 1460 documents and 35 queries, each one containing a set of valid
answers. Documents contain text in natural language and queries are given as a set of
terms connected by Boolean operators. In our experiments, we converted documents to
collections of weighted terms and stored them in a relational database. The weighting
4 http://ftp.cs.cornell.edu/pub/smart/cisi/
measure used was term frequency-inverse document frequency (tf.idf ) [
After receiving a query, ip-CL4IR consults the database and extracts all documents
that contain at least 2 terms of the query (as described in Section 3.3, this value is a
parameter of ip-CL4IR). The ip-concept lattice is computed using a minimal
dimensionality of min dim = 2, to keep consistency w.r.t. the restriction given for the creation of
the pattern structure. The query concept is searched in the lattice and its superconcepts
are retrieved and ranked using the Euclidean distance between the boundaries of their
interval patterns. Cosine distance (instead of Euclidean distance) was also calculated
showing better results. Table 4 shows the results for 11-point precision of fixed recall
and 6 measures of precision for the top 5,10 and 20 ranked documents retrieved. Results
on an implementation based on concept lattice-based ranking (CLR) [
Table 4 reports the results in 8 measures for ip-CL4IR, a reported CL4IR system
called concept lattice-based ranking (CLR) [
Values in Table 4 show a better performance of ip-CL4IR on 4 of the 8 measures while EM is better in the remaining 4, namely precision and recall in the first 5 and 10 ranked documents. This indicates that EM is actually better to recognize documents very close to the query, but for documents with less elements in common with the query, EM is not very precise. This can be better appreciated in Figure 3 where the interpolated precision values of ip-CL4IR quickly overcome those of EM which is only better in 1 of the 11 recall points. This fact is also supported by the significant difference in the values of IAP and MAP between ip-CL4IR and EM. For the 35 queries in the dataset, our approach took 42.23 seconds (1.2 seconds per query) to execute while for CLR took 1550.333 (44.29 seconds per query) showing an impressive enhancement in the computational time required to retrieve documents, a key issue in document retrieval. Both these times include lattice construction. Using better measures which consider the correlation among terms, or including external knowledge sources like term taxonomies may improve greatly the quality of the answers provided by our approach. These issues are currently planned as future work. These experiments were performed in an Intel Xeon machine running at 2.27 GHz with 62 GB of RAM memory.
There are many perspectives for our approach, however the most important is the
full exploitation of the ip-lattice structure to improve the quality in the answers. While
our principal goal in this article is to describe a general process to directly support
numeric term-document datasets in a concept lattice-based information retrieval system,
we argue that different IR tasks (some already supported on CL4IR systems) can be also
supported on ip-CL4IR for example, document clustering [
In this article we introduce a CL4IR approach which is able to deal directly with numerical datasets through the use of the pattern structure framework (ip-CL4IR). We provide a method and a process to construct an interval pattern concept lattice (ip-concept lattice) which can be used as a document index. We present the idea of an ip-concept lattice as a query space which can be navigated in order to find relevant documents. We also provide means to rank these documents using vector-based distances. The feasibility of our approach is validated through its application on a popular IR dataset for which we present precision and recall values contrasted to those reported in the literature showing a better performance in the overall list of ranked documents and an impressive enhancement in the time needed to answer a single query.
The perspectives for our approach are numerous, ranging from the improvement of its answers, its application on different real-world datasets, but most importantly, the full exploitation of the lattice structure to support different IR tasks.