The information systems these days manage, import, broadcast, exchange and integrate big volumes of sometimes recorded data, often in different formats (documents, cards, tables). With the internet development, the institutions are often confronted to the manipulation and the analysis of important information volumes. These informations are often coming from heterogeneous data sources and are themselves of heterogeneous nature. Regarding this heterogeneity, the integration or the simple exchange of the data is not an easy task if the different intervening (producers or information consumers) do not agree on the semantic of data. It is therefore very difficult to research the answer to an information need in all bases.
In this direction, we are very interested in defining an approach that is focused particularly on the detection of the similar objects. Furthermore, the important volume that occupies the heterogeneous data creates gaps and technical difficulties such as pertinent information deficiency and the loss time for precise information research. In this context, we propose an analysis and an interpretation approach of the similar objects allowing jointly to realize a more effective research and to extract automatically the information from the dispersed sets of heterogeneous data in the framework of the cooperative work. Our approach is based on the formal concept analysis.
So, this paper is organized as follows. In section 2, we introduce some basic definitions on formal analysis. Then in section 3, we present the related work. Section 4 is devoted to the presentation of proposed system for searching in heterogeneous information. In section 5 and 6, we present the evaluation of our system.
Among the mathematical theories recently found 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 [1,4,7,10,18,20,23]. In this section, we define formal context, formal concept, Galois connection and the lattice of concepts associated to the formal context.
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" [3,12]. 1. An example of a formal context.
Definition 2. Let A ⊆ Ο and B ⊆ P two finite sets, R a relation on O x P. For both sets A and B, operators f(A) and h (B) are defined as [12]:
Operator f defines the properties shared by all elements of A. Operator h defines objects sharing the same properties included in set B. Operators f and h define a Galois Connection between sets O and P [12]. Proposition 1. Operators f and h define a Galois connection between O and P, such that if A1, A2 are subsets of O, and B1, B2 are two subsets of P, then f and h verify the following properties [12]:
Definition 3. A formal concept of the context <O,P,R> is a pair (A,B), where A ⊆ Ο, B ⊆ P, such f (A) = B and h (B) = A. Sets A and B are called respectively the domain (extent) and range (intent) of the formal concept [3,12].
Definition 4. From a formal context <O,P,R>, we can extract all possible concepts. In [12], we prove that the set of all concepts may be organized as a lattice, when we define the following partial order relation << between two concepts, (A1,B1) << (A2,B2) ⇔ (A1 ⊆ A2 ) and (B2 ⊆ B1). The concepts (A1,B1) and (A2,B2) are called nodes in the lattice.
The object similarity can be envisioned according to two view points: -The semantic view point: the objects are similar if they have commons properties, -The system view point: to take into account the object model have vector model. Semantic Similarity. Definition 5. Let k=<O,P,R> a formal context, O is object set, P is properties set and R is the binary relation between O and P. The similarity between two objects a and b is considered the commons properties. Let a and b two elements of O, P a the verifying properties by the object a and P b the verifying properties by the object b. The commons properties between two objects a and b forms the set P a ∩P b . The similarity between two objects is calculated with the following formula [23]:
The similarity is a value in the interval [0,1]. System similarity. In order to measure the similarity between two objects a and b, it necessary to take in consideration the different object models. For this reason, we present only the similarity calculation between two objects in the vector seen model the complexity of the others model. [11,21,22,24,25,26,27] Definition 6. The similarity between two objects a and b in the vectorial model [24,25,26] is measured as the angle cosines between two vectors presenting those objects.
Object Similarity Choice. We mention that the object similarity value whatever the view point system or semantic is a value in the interval [0,1]. This object similarity criterean may crold two values: two objects may seen alike or different from each other. So, we determine two sets Sim_objet and Dis_objet according to similarities and dissimilarities of an object with an object a:
where α sim is the threshold that determines the object notion near or distant. In our work, this threshold is provided by the user. The given value of the research session means that the user accepts the similar answers with this degree. Seen that we use the concepts formal analysis as basic foundation of our research approach, we do not consider the similarity from the system view point but we are very interested in the similarity from the semantic view point.
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 automatic support structure (i.e., the document lattice) in which we place the information retrieval process. The document lattice can be used to improve basic individual search strategies [1,2,4,13]. Moreover, query refinement is one of the most natural applications of concept lattices. Its main objective is to recover from the nulloutput or the information overload problem. The concept lattice may be used to make a transformation between the representation of a query and the representation of each document [5,6,7,8,9]. The query is merged into the document lattice and each document is ranked according to the length of the shortest path linking the query to the document concept. On the other hand, in the set of terms describing the document, there exist hierarchies in the form of thesaurus [4,10,13,14]. The information search using FCA takes as input a query that will be forwarded to a selected search engine [6,7,8]. The first pages retrieved by the search engine in answer to the query are collected and parsed. At this point, a set of index units that describe each returned document is generated; such indices are next used to build the concept lattice corresponding to the retrieved results. The last step consists in showing the lattice to the user and managing the subsequent interaction between the user and the system. In spite of such limitations such as for larger information collection, generally we get a huge number of reference, we are interested in building a FCA-based system for distributed information, which may affect both the efficiency and the effectiveness of the overall system [18,19,20]. These systems suppose that a same document is identified in same manner that presents a strong hypothesis. In order to reduce this constraint, we proposed a similar object detection method. While basing itself on this last one, we have defined a cooperative system of heterogeneous information retrieval HIC2RS that will be described in the next section.
We present in this section the cooperative research for heterogeneous information. While considering the formal concept analysis as mathematical foundation, we propose an heterogeneous information conceptual cooperative retrieval system HIC2RS, as illustrated in figure 1, that is composed of two parts:
1) The first part is the cooperative information retrieval system handling local databases. The search of the answer to a query consists in applying a research conceptual approach on every local database. As a result, we will have concepts set forming the content of a Response vector.
2) The second part is the final answer formulation that operates in two steps : i) Similar objects detection based on the Response vector and on the local databases set, and
ii) The concepts merger based on the similar objects set and operated according to the similarity threshold given by the user in order to offer the final answer.
The first part of the system HIC2RS is formed of information retrieval systems set that cooperate to give the complete answer to a query. Every information retrieval system has access to a local database on which it applies the Galois connection to rediscover the satisfactory documents query. This last one is keywords set. To resolve a query (Qr), every conceptual information retrieval system executes the research algorithm, presented in the following, on its local database (LD). This application gives us concepts set forming the Response vector (RV).
Inputs: Query: Qr Local database: LD Output: Response Vector: RV Begin M := the keywords of LD.
Ml := M ∩ Qr RV contains the concept obtained by Galois connection application on M1. End
In this section, we present the second part of the system HIC2RS that is the final answer formulation. The final answer formulation is carried out in two steps: i) the detection of the similar objects of the Response vector, and ii) the merger of the different answers based on the Response vector and on the similar objects. The final answer formulation consists in the application of the algorithm Merge_IH that we propose on the Response vector basing on the query and on the similarity threshold to have the final answer.
Similarity Objects Detection. The similar objects detection consists in examine the documents that figure in the Response vector and calculating the similarity between them. From the concepts, we create a similar objects set. This set contains the similarity degrees between the different documents. The similarity degree calculation between two documents is based on the formula (1) defined in section 2.5. In fact, seen that our system is based on the terminologies of the concepts formal analysis, it is useless to use the similarity from the system view point that depends on used model to present and search the information such as the vectoriel model. While taking account of the keywords number of every document and the number of common keywords between them, the similarity degree between two documents is calculated.
Answer Merge. Basing on the calculated similarity degrees as well as on the Response vector concepts, we formulate the final answer to the query. The merger is based on algorithm Merge_IH that we propose by the continuation. This merger algorithm combines the Response vector concepts while respecting certain conditions. We construct the final answer in a repeated way. Initially, the final answer is an empty set. We treat the concepts set element by element.
For every element, if the keywords (the extension) of the concept are different of those of query, we add then the documents (his intention) to the final answer. If this condition is not satisfied, we search the similar documents to those of other concepts of the Response vector (the intention) verifying the threshold similarity, and we calculate the union of the extensions (to obtain the under together keywords). We continue to construct these sets of similar documents until we find all the query keywords.
This algorithm has as entry the query, the similarity threshold and the Response vector and as a result the final answer.
Inputs The similar function consists in looking the similar objects with a similar threshold in two objects sets. This research is based on the similar objects set found at the time in the phase of the similar objects detection. We keep only the objects having a similarity degree greater than the similarity Threshold. The function is described in the following and it has as inputs two objects sets A1 and A2 and a similarity threshold α and as output the set A3. End if End for End for Return (A3) End.
We take an illustrative example to show the HIC2RS system functionalities. Let the databases presented in tables 2, 3 and 4. These databases describe documents set indexed by a keywords set. For the query: "Which documents indexed by the keywords M 2 , M 3 and M 4 having a similarity Threshold 0.33", the query is formed by three keywords M 2 , M 3 and M 4 . The treatment of this query is carried out in two steps.
The research principle is explained in figure 2. Every conceptual information retrieval system applies algorithm retrieve on its local database. The Galois connection application on the query keywords sets existing in the first database presented in table 3 and the query (M 1 = {M 2 ,M 3 }) gives the documents set {D 1 }. The found concept is then ({M 2 ,M 3 }, {D 1 }).
For the second local database presented in table 4, the Galois connection application for the keywords M 2 and M 4 , the common found keywords between the local database keywords and those of the query, we give the documents {D 6 , D 9 }. So, the result for this local database is formed by the concept ({M 2 ,M 4 }, {D 6 ,D 9 }).
The third local database presented in table 5 contains the keywords M 3 and M 4 . While applying the Galois connection, we find the documents set {D 10 ,D 13 }. Thus, the concept ({M 3 ,M 4 }, {D 10 ,D 13 }) is the result of this research.
We obtain three concepts from different local databases that we find in the Response vector presented by the table 6.
Table 3. TheResponse vector.
Basing ourselves on this vector, we construct the final answer.
The final answer formulation is realized in two phases: similar objects detection and the answers merger.
Similar objects detection : The Response vector contains three concepts that we examine one by one. The first concept contains the document D 1 . We calculate then the degree of similarity between this document and every document existing in the two other concepts that are D 6 , D 9 , D 10 and D 13 . The same treatment is carried out on the document D 6 . We calculate the similarity degree between D 6 and D 10 then between D 6 and D 13 . The same treatment is done on the document D9. The degrees of calculated similarities are the following ones: Answer Merge : We remind that our query is {M 2 ,M 3 ,M 4 } and the similarity threshold is 0.33. Initially, the final answer is an empty set. We treat the first concept of the Response vector. Its keywords are different from the query. So, we merge those keywords with those of the second concept and we search the similar documents. The result of this research is the documents set {D 1 ,D 6 }, considering that the documents D 1 and D 6 are similar with the degree 0.33, and that the keywords union is the set {M 2 ,M 3 ,M 4 } that is equal to the query. The similarity between D 1 and D 9 is equal to 0.25 that is less than the similarity threshold. So, we ignore D 9 and we add the found documents to the final answer. At this step, the final answer is the set {D 1 ,D 6 }.
Then, we calculate the union of the keywords and the similar documents between the first and the third concepts of the Response vector. The merge result is the set {M 2 ,M 3 ,M 4 } that is equal to the query. We remark that the documents D 10 and D 13 are similar to D 1 and to D 6 with the degree superior to 0.33. So, we add those documents to final answer that becomes {D 1 ,D 6 ,D 10 ,D 13 }.
Thus, we continue with the next concept. We merge the keywords of the second and the last concepts. The result is the set {M 2 ,M 3 ,M 4 }. The similar documents are {D 6 ,D 10 ,D 13 } that we add to the final answer. The final answer is now the set {D 1 ,D 6 ,D 10 ,D 13 } that will be delivered to the user.
Remark 1: If we take for example a similarity threshold equal to 0.8, our system returns an empty answer. This answer explains oneself by the fact that there doesn't exist similar objects for this degree. As opposed to the threshold equal to 0.2, the final answer is then composed by all documents forming the Response vector. This can be explained by the fact that the similarity degrees between the different documents are greater than the given value. Thus, our approach considers that the documents set represent the same knowledge and we evade late the empty answers.
In order to evaluate the system HIC2RS, we calculate the temporal and the spatial complexities.
We suppose that a database has n objects and m properties and we dispose of k local databases.
We recall the steps of our system HIC2RS:
-Phase 1: the concepts research from the different local databases.
-Phase 2: the similar objects detection and the merge of k found concepts.
The temporal complexity C T of the system is then:
The phase 1 needs k×n×m operations and the phase 2 needs k×(k-1)/2+(n×k) operations. So, the temporal complexity is: 2 ) operations. The temporal complexity of the system HIC2RS is then in order of O(k×n×m+k 2 ) operations.
The system HIC2RS uses k matrix of n lines and of m columns, a vector of k elements as well as a square of dimension n. The system reserves thus (k×n×m)+k+(n×n) memory cases. So, the spatial complexity of the system HIC2RS is equal to: C S = (n× m× k+ k+n 2 ).
The system HIC2RS treats heterogeneous information. Indeed, to remedy the problem of the existence of different identifications for similar or identical documents, we proposed a similar objects detection method during the cooperative information retrieval process. The implementation of this system consists first of in fragmenting a test collection and next in releasing the retrieval process while supposing that a same document can have different identifications. This hypothesis is based on unit similar objects detection. The experiment was conduced on CRAN and MED collections.
The CRAN collection (Cranfield collection) includes a textual corpus that has a size upper than 1.6Mo. This collection contains 1400 documents and 4612 different terms and it is tested on 225 queries. The MED collection includes a textual corpus that has a size upper than 1.1Mo. It contains 1033 scientific articles extracted from the medicine database domain and 5831 different terms and it is tested on 30 queries. With experiments done on the MED and CRAN test collections, we noticed that the final quality of retrieval improved in term precision and recall that in term answer times.
The figure 3 illustrates the precision and recall graph of the MED test collection for the system treating homogenous information CIRS and HIC2RS. We note, according to figure 3, that for the MED test collection, the measure of average precision has 11 reminder points for the system treating information homogenous (CIRS) is in the order of 43.9%. While, for the system HIC2RS treating information heterogeneous is on the order of 46.7%. Thus, the similar object detection integration gives an improvement of average precision on the order of 6.4%.
All the same, experimentations done on the CRAN test collection fragmented showed an improvement of average precision of the CRAN test collection on the order of 7.5%. (figure 4). The figure 5 shows that HIC2RS treats different MED test collection queries faster than the conceptual information retrieval system. Of even for the CRAN test collection, the answer time take by HIC2RS is lower than the one take by the system treating information homogenous (to see figures 6).
We presented in this paper a conceptual cooperative retrieval system for heterogeneous information (HIC2RS). Being given a heterogeneous environment constituted by a set of information retrieval systems handling each a local database, our approach allows soliciting these databases in order to have a complete answer to a user query.
In fact, after a query and according to a similarity threshold given by the user, our system releases conceptual research processes on the different local databases and it will have as a result a concepts set. Basing on this concepts set and on the similarity threshold, the system formulates the final answer that it delivers to the user. The similar objects detection method, that we defined, enriched the returned answers of different databases. This method improved average precision of 6.4% for the MED test collection and of 7.5% for the CRAN test collection.