. The potentials of formal concept analysis (FCA) for information retrieval (IR) have been highlighted by a number of research studies since its inception. The growth of the web has favoured the emergence of new search applications. In this paper, we will focus on the unique features of FCA for searching in distributed information and for reducing the size of the set information. The development of a FCA-based applications for distributed information returns a major gain and the obtained results are promising. This study has several perspectives for real and fuzzy data.
Along with the growth of the world wide web, information retrieval systems gain
importance since they are often the only way to find the few documents actually
relevant to a specific question in the vast quantities of text available. Moreover, with
the advent of the Web along with the unprecedented amount of information available
in electronic format and its distributed structure, Formal Concept Analysis (FCA) is
more useful and practical than ever, because this technology addresses important
limitations of the systems that currently support users in their quest for information.
Over the last few years, the range of functionality has been expanded to include new
tasks such as data reduction and collaborative (or cooperative) information retrieval.
In fact, due to the huge quantity of available information and its distributed structure,
it is necessary to abstract it and eliminate the redundancy data. In this context, a
method for data reduction based on the formal concept analysis is proposed in
[
Among the mathematical theories found recently with important applications in
computer science, lattice theory has a specific place for data organization, information
engineering, data mining and for reasoning. It may be considered as the mathematical
tool that unifies data and knowledge or information retrieval
[
)RUPDO &RQWH[W
'HILQLWLRQ : A formal context is a triple k = <O,P,R>, where O is a finite set of
elements called objects, P a finite set of elements called properties and R is a binary
relation defined between O and P. The notations (g,m), or R(g,m)=1, mean that
“formal object g verifies property m in relation R" [
Let O= {Leech, Bream, Frog, Dog} and P={a, b, c, d}. The following context may be defined by the table 1.
a b c d 1 Leech 1 1 0 1 2 Bream 1 1 0 1 3 Frog 1 1 1 1 4 Dog 1 0 1 1
Table 1 : An example of a formal context.
*DORLV &RQQHFWLRQ 'HILQLWLRQ Let A Í O and B Í P two finite sets, R a relation on O x P. For both sets A and B, operators I(A) and K (B) are defined as :
I (A) = {m | "g, g Î A Æ (g,m) Î R}
K (B) = {g | "m, m Î B Æ (g,m) Î R}
Operator I defines the properties shared by all elements of A. Operator K defines
objects sharing the same properties included in set B. Operators I and K define a
Galois Connection between sets O and P [
(TXLYDOHQFH EHWZHHQ DQ REMHFW DQG D VXEVHW RI RWKHU REMHFWV
'HILQLWLRQ Let x Î O be an object, AÍ O be a finite set and R a relation on O ´ P.
We define FORVXUH [ = g(f(x)) and FORVXUH $ g(f(A)) [
A B C O1 1 1 1 O2 1 0 1 O3 1 0 0 O4 0 1 1
O5 0 0 1
Table 2 : Example of a relation R O5 is equivalent to {O1,O2,O4}, the reason is that the concept containing O5 is CP={O1,O2,O4,O5}´{C} ; and inversely the concept containing {O1,O2,O4} is also CP.
&XUUHQW 6HDUFK
Using FCA can complement the existing search systems to address some of their
main limitations. Basically, FCA exploits the similarity between documents in order
to offer an automatically support structure (i.e., the document lattice) in which to
place the information retrieval process. The document lattice can be used to improve
basic individual search strategies [
&RQFHSWXDO 5HGXFWLRQ 0HWKRG
The fundamental question for data reduction is the following : How can we reduce
data without losing any knowledge ? The advantage of reduced data is that it can be
used directly as a prototype for making decision, for supervised learning or reasoning
[
Algorithm reduction (RD, R)
Initialize RD=R For each object x in the domain of the remaining context RD, we do the following steps : 1)we find the set of its properties P (i.e. subset
attributes satisfied by x). 2) we find the set of objects S, except x, sharing all the properties P. 3)if S is not empty, we check if object x is included in the set of objects sharing the same properties as S. In the positive case, object x is removed from context RD.
End of the loop of End.
This method takes place on two steps. The first step consists in applying the relational join operator on the set of the tables. The second step is the execution of the conceptual reduction algorithm on the result table. The major problem is that the
Ibtissem Nafkha, Samir Elloumi, Ali Jaoua treatment of an important size databases needs a considerable storage space and makes the reduction process sultry. Our idea is to propose an algorithm which makes simultaneously the join and the reduction of the tables set in only one reduced table. Then, we will present our system in the next section.
In this section we will present some search that may be improved through a FCA for distributed information.
&RRSHUDWLYH FRQFHSWXDO ,QIRUPDWLRQ 5HWULHYDO 6\VWHP
To improve upon regular Information Retrieval System (IRS), cooperative
conceptual information retrieval system (C2IRS) was proposed [
First of all, we apply the 0HUJLQJ $OJRULWKP on the $QVZHU $UUD\. Then, we apply the 0HUJLQJ $OJRULWKP on the modified $QVZHU DUUD\ in order to obtain the final answer. We detail those algorithms with an illustrative example. &RRSHUDWLYH ,QIRUPDWLRQ 5HWULHYDO 6\VWHP Different information retrieval systems (IRS) cooperate to give a most complete answer to a query. Each IRS has a local database on which we apply the Galois connection (GC) to retrieve the documents
Using Concept Formal Analysis for Cooperative Information Retrieval
125
satisfying the query. In the query, we express that we want to find documents which
are indexed by some indexing terms Qr. To resolve a query (Qr), each CIRS executes
the 5HWULHYH $OJRULWKP proposed in [
a) database 1 b) database 2 c) database 3 t1 W= W> t1 W= W? t1 W> W? I J Answer @BACED;FHG Table 3 : THE ARRAY. W= W> W= W? W> W?
A C G A B G
Based on this array, we construct the final answer by the application of the
)LQDOB$QVZHUB)RUPXODWLRQ algorithm proposed in [
We apply the 5HWULHYH $OJRULWKP already presented on the set of databases. The Galois connection applied on the set of query terms, existing in the first database, Tl={t2,t3}, gives the set of documents {A,C}. Then, we put the first concept found ({t2,t3},{ A, C}) in the first cell of the $QVZHU array.
By the same way, we continue to find concept from each contexts . We obtain four concepts from the several databases that we place in the following $QVZHU array. )LQDO $QVZHU IRUPXODWLRQ In this section, we present the second part of our system which is the final answer formulation. The formulation of the final answer consists in the application of two proposed algorithms on the $QVZHU array. This algorithm combines the concepts of the AQVZHU array according to some conditions. The final answer is built somehow iteratively. Initially, the final answer is an the empty set. We read the set of concepts element by element. For each element, if the domain of a concept is equal or greater than the terms of the query, then we add its range (set of document references) to the final answer. If this condition is not satisfied, we build intersection between its range and ranges of other concepts in the answer array (i.e. a subset of documents), and we compute the union of the domains (to find a subset of terms). We continue to build these intersections until we find at least all the terms of the query. ([DPSOH For our example, we remind that our query is {t2,t3,t5}. Initially, the final answer is an empty set. We read the first concept of $QVZHU array. Their terms are different to the query. So, we merge their terms with terms of the second concept and we compute the intersection between their ranges. The union of terms is the set {t2, t3, t5} which is equal to the query. But the result of the intersection between documents is an empty set. So, we continue with the next concept. We merge the terms of the first and the last concept. The result is the set {t2,t3,t5} which is equal to the query. The intersection between their documents gives the set of documents {A}. We add this set to the final answer. By repeating this process with to the next concept, we find the union of terms {t2,t5,t3} which is equal to the query. So, we add the result of the intersection of documents that is the set {G} to the final answer. The final answer is now the set {A,G}. The final answer obtained is the set of documents {A,G} that will be deliver to the user.
The retrieval process using this system is based on a formal concept analysis. For each database, we search the local concept. We use a cooperative approach to formulate the final answer basing on extracted concepts from several databases. The major problem is that when we search for pertinent information, we generally get a huge number of references. Moreover, the treatment of an important size databases needs a considerable storage space and makes the research process sultry. So, we need to minimize the size of each database. In the next section, we present the cooperative conceptual information retrieval system based on data reduction.
&RRSHUDWLYH &RQFHSWXDO ,QIRUPDWLRQ 5HWULHYDO 6\VWHP EDVHG RQ 'DWD 5HGXFWLRQ
To improve upon cooperative conceptual information retrieval system, we propose
a system for cooperative conceptual information retrieval basing on data reduction.
As it is shown in figure 3, our proposed system is composed of two parts :
1. Part 1 is detailed in the next subsection. In this phase, our proposed system
uses a conceptual approach, proposed in [
Basing on the set of reduced databases (RDB) and the equivalent objects set,
Using Concept Formal Analysis for Cooperative Information Retrieval
127
we cooperate to give a most complete answer to a query by using the
cooperating process, proposed in [
DB1
DBN RDB1
&RQFHSWXDO GDWD UHGXFWLRQ In [
Let the following databases presented by the formal contexts in figure. For the database 1, the document D is equivalent to {B,C,A}, the reason is that the concept containing D is C1={A,B,C,D}´{t3}; and inversely the concept containing {A,B,C} is also C1 that may be obtained by using the Galois connection. This means that document D can be removed without modifying the initial knowledge database. By the same way, we can remove B and J from the database 2. Moreover, we remove the document A from the database 3. The reduced databases are showed in the following table.
A B C t 1 0 1 1
W 0
W 1
G K L t 1 0 1 1
W 0 0
W 0 1
B C G t 1 1 1 0
W 1
W 0
Based on the reduced databases and the set of equivalent documents, the
cooperative conceptual search process is executed to respond to the query. We detail
the steps of this system in the next subsection.
&RRSHUDWLYH &RQFHSWXDO ,QIRUPDWLRQ 5HWULHYDO In this section, we present the
second part of our system which is a cooperative conceptual information retrieval
which is proposed in [
&RQFHSWXDO LQIRUPDWLRQ UHWULHYDO V\VWHP EDVHG RQ FRRSHUDWLYH FRQFHSWXDO GDWD UHGXFWLRQ
In this section, we present an approach for information retrieval [
DB1
DBN
The advantage of this approach is that it is much faster than other methods. Indeed, the treatment of databases which have an important size needs a considerable storage space and makes the research process sultry. So, we need to minimize the size of the databases set. Based on the reduced database, the conceptual research process is executed. In the query, we express that we want to find documents which are indexed by some indexing terms. We apply the Galois connection only on the query terms
Ibtissem Nafkha, Samir Elloumi, Ali Jaoua
existing in the reduced documentary database to formulate the answer that will be
delivered to the user.
&RRSHUDWLYH FRQFHSWXDO GDWD UHGXFWLRQ In this section, we present the principle of
our method for the cooperative conceptual data reduction and show how we apply in
order to generate the reduced table and the set of equivalent objects. The algorithm
proposed in [
We execute the principle of the cooperative conceptual data reduction on the same example to prove that it give the same result as the conceptual reduction data. ([DPSOH Let the following databases presented in figure 2. We apply now our proposition. The table RT and the graph G are empty. For the first object {A}´{t2,t3,t5} generates a new node , that has as domain {A} and as range is {t2,t3,t5}, that is added to the graph.
W= W> W?
The treatment of the second document {B}´{t1,t3,t5} generates a new node , that is (B, {t1,t3,t5}), in the graph. The treatment with the node gives the intersection {t3,t5}. We add a new node that its domain is {A,B} and its range is the set {t3,t5}. 1
A Using Concept Formal Analysis for Cooperative Information Retrieval 131
For the object {C}´{t1,t2,t3}, a new node is added to the graph. The treatment with the node gives the intersection {t2,t3}. We add a new node that its domain is {A,C} and its range is {t2,t3}. The treatment with the node generate a new node that is its domain is {B,C} and its range is the intersection found {t1,t3}.
W W= W>
W= W> 3
A B 2
B
For the object {D}´{t3}, a new node is added to the graph. The treatment with the node and gives an intersection {t3} that is its range, it’s a modified node. We add to domain the set {A,B,C}. We verify the propriety of the proposition presented. Indeed, we remark that the domain of the node is different from the union of the domains of their children and ({A,B,C,D} <> {A,C}È{A,B}È{B,C}) and its range is equal to the intersection of the ranges of their children ({t3}= {t2,t3}Ç {t3,t5}Ç {t1,t3}). So, the object D (D ={A,B,C,D} \ {A,C} È {A,B} È {B,C}) will be eliminate from the node and from RT. The document D is equivalent to {A,B,C}. The graph becomes : 4
C 5
A C A 3 A B 2
B
B C 6 A B A B C
By the same way, we continue the treatment for the others objects. Finally, we obtain the following graph.
A B C B C G L
A 8 A B L
1 t1 t3 t5
Finally, we obtain the reduced database RT that is presented in the following table.
The document D is equivalent to the set of documents {B,C,G}, the document J is equivalent to the set {B,G} and the document K is equivalent to the set {B,C,L}. Basing on the reduced database and the set of equivalent objects, we execute the conceptual research process that is detailed in the next section. &RQFHSWXDO LQIRUPDWLRQ UHWULHYDO The information retrieval system (IRS) is based on the reduced database to give a most complete answer to a query. We apply the Galois connection (GC) on the reduced database to retrieve the documents satisfying the query. In the query, we express that we want to find documents which are indexed by some indexing terms Qr. To resolve a query (Qr), we apply the Galois connection on the query terms Tl. Thus, the result of IRS is a concept which range is the searching terms Tl and its domain is the retrieved documents. ([DPSOH Let us treat the databases presented in the table 9. For a query of the form:"Which documents are indexed by the terms t2, t3 and t5", the query is formed by three terms t2, t3 and t5. We will find the concept from reduced database by applying Galois connection. The concept found is {t2, t3,t5}´{G}. The final answer obtained is the document G that will be delivered to the user. We have in the set of equivalent object the information that the document G is equivalent to the document A. So, the final answer will be {A,G}. We remark that we obtain the same result as the cooperative information retrieval based on the data reduction, presented in the last section, that treats three databases containing in total 9 rows. Moreover, our proposed system is applied on the four rows reduced database that is more easy. In the next section, we present the complexity of all presented systems for information retrieval.
&RPSOH[LW\ $QDO\VLV
v equal in : &¶ (n,m) = &¶} (n,m) + &¶}" (Q¶ P¶).
7LPH FRPSOH[LW\ It is easy to find the complexity &¶ (Q P) for this system which is
The complexity of phase 1 is O(n*m). The phase 2 realize (2(Q¶ P¶ Q¶ operations
[
The complexity analysis of a treatment is ensured by calculating : i) the time complexity, which is the number of operations of the treatment, and ii)the space complexity, which is the number of memories cases used by the treatment.
We compute the complexity analysis of cooperative conceptual information retrieval system, conceptual information retrieval system based on data reduction and conceptual information retrieval system based on cooperative data reduction.
Phase 1: the search of concepts from different databases.
Phase 2: the formulation of the final answer from the found concepts. &RRSHUDWLYH &RQFHSWXDO ,QIRUPDWLRQ 5HWULHYDO 6\VWHP
We present the complexity of the cooperative conceptual information retrieval
system (C2IRS) proposed in [
&RRSHUDWLYH FRQFHSWXDO LQIRUPDWLRQ UHWULHYDO LQIRUPDWLRQ EDVHG RQ 'DWD UHGXFWLRQ
We suppose that the database has Q sites and P properties and the reduced database has Q¶ sites and P¶ properties. We remind first all steps of this system: - Phase 1: conceptual data reduction applied on several databases. - Phase 2: cooperative conceptual information retrieval applied on the reduced databases. So, &¶ (n,m) = nm + 2n’m’ + n’.
Since the size of the reduced database is lesser than that of the initial database (n’<<n). So, the complexity of our proposed system is lesser than that of the C2IRS . &¶ (n,m) = nm + 2n’m’+n’ << & (n,m) = 2nm + n. 6SDFH &RPSOH[LW\ Our retrieval system handles a reduced database. So, we can reserve only (k*n’*m’) memory cells. So, the space complexity of our system is C’S=kn’m’.
We note that our algorithm uses a less number of memory cells that the C2IRS : C’S<<CS. This can be explained by the integration of the conceptual data reduction in our proposed system.
&RQFHSWXDO LQIRUPDWLRQ UHWULHYDO EDVHG RQ &RRSHUDWLYH GDWD UHGXFWLRQ 7LPH FRPSOH[LW\ If we have K tables, each one has Q lines and P properties, we realize N iterations where N = nn. In each iteration, we cover the concepts graph G and we do then ||G|| operations where ||G|| represents the graph cardinality. So, we do ||G|| update operations on the graph (adding or modification operation). So , C’T » O(N* ||G||2).
Then, our algorithm have a complexity less then that of the conceptual data reduction considering the cardinality of the graph is too small compared to the number of properties (||G||<< M) 6SDFH &RPSOH[LW\ Our algorithm treat in each iteration one line. So, we can reserve only M memory cases. For the treatment of each line, the algorithm uses a graph that is constructed in incremental manner. This graph necessities 8*||G|| memory cells since for each graph node, we reserve 8 memory cells. So, the space complexity of our algorithm is C’S=M+(8*||G||).
We note that our algorithm uses a less number of memory cells that the conceptual data reduction : C’S<<CS. This can be to explain by the fact why the conceptual data reduction treats a matrix of N lines and M columns on the other hand our algorithm treats only one line.
&RQFOXVLRQ
In this paper, we have presented three conceptual information retrieval systems. The cooperative conceptual information retrieval system combines the results of several information retrieval systems. Each one has its local formal context representing a database on which we apply a conceptual search to obtain a first set of concepts. From this set of concepts, we formulate the final answer by applying a proposed algorithm merging and combining concepts with a suitable way. The volume of the available information is increasing exponentially. So, generally we get a huge number of reference. It is necessary to abstract it and eliminate the redundancy data. However, our main idea is to integrate the data reduction in the search process. The information retrieval is based on the data reduction. From a set of formal contexts presenting a databases set, we apply the relational join operator in order to fusion the