With the advent of the Web along with the unprecedented amount of information coming from sources of heterogeneous data, 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. In this paper, we will focus on the unique features of FCA for searching in distributed heterogeneous information. The development of FCA-based applications for distributed heterogeneous information returns a major gain.
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.
2
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 [
Definition 1. 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" [
Example 1. Let O = {a1, a2, a3, a4, a5, a6} be a set of person of different grade and P = {b1, b2, b3, b4, b5, b6, b7} be a set of the properties. This context describes the professional qualifications verified by the persons set according to the binary relation R. The f (A) = {m | ∀g, g ∈ A Æ
objects sharing the same properties included in set B. Operators f and h define a
Galois Connection between sets O and P [
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 [
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 [
[
Semantic Similarity. Definition 5. Let k=<O,P,R> a formal context, O is object set,
between two objects a and b is considered the commons properties. Let a and b two
elements of O, Pa the verifying properties by the object a and Pb the verifying
properties by the object b. The commons properties between two objects a and b
forms the set Pa∩Pb. The similarity between two objects is calculated with the
following formula [
Similarity (a, b) =
Pa ∩ Pb Pa ∪ Pb (1) (2)
tween 5 objects {O1, O2, O3, O4, O5} and three properties {A, C, D} and between four objects {O6, O7, O8, O9} and four properties {A, B, C, E}.
Similarity (a, b) = cos( a , b ) = O1 O2 O3 O4 O5
different from each other. So, we determine two sets Sim_objet and
Sim_objet (a) = { b ; Similarity (a,b) >= αsim }
Dis_objet (a) = { b ; Similarity (a,b) < αsim } 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. 3
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 [
cal 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.
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). Algorithm Research Inputs: Query: Qr
Local database: LD Output: Response Vector: RV Begin End
M := the keywords of LD.
Ml := M ∩ Qr RV contains the concept obtained by Galois connection application on M1.
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.
tain 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.
Algorithm Merge_IH
Inputs : Query: Qr
Response Vector RV: a concepts set C1 .. CN Threshold similarity: S
Output : Final answer: FA Begin
FA := ∅•// initialize the final answer For each concept Ci of RV do
If extent of concept Ci = Qr then
Add the intent of Ci to FA Else
While exist a concept Cj (j > i) do - Initialize P by the extent of Ci - Initialize D by the intent of Ci
While (P <> Qr and exist a concept Cj) do - Add the extent of Cj to P - Search the similar documents, with the threshold S, between the intent of the concept Cj and the elements of D:
D := Similar (D, intent_ Cj,S) - Pass to the next concept End do If (P = Qr ) then
Add D to FA : FA :=FA ∪ D
End if
End do
End if
End for
End.
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.
Function Similar Inputs:
Objects sets: A1, A2.
Similarity Threshold: S Output: Objects set: A3 Begin
A3 := Ø
For each object di of A1 do For each object dj of A2 do - Calculate the similarity between two objects di and dj : α :=
P d i ∩ P d i ∪
P d j
P d j - If α>=S, add objects di and dj and the similarity α to 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 M2, M3 and M4 having a similarity Threshold 0.33", the query is formed by three keywords M2, M3 and M4. The treatment of this query is carried out in two steps. - Step 1 : Cooperative Research
database. The Galois connection application on the query keywords sets existing in the first database presented in table 3 and the query (M1 = {M2,M3}) gives the documents set {D1}. The found concept is then ({M2,M3}, {D1}).
for the keywords M2 and M4, the common found keywords between the local database keywords and those of the query, we give the documents {D6, D9}. So, the result for this local database is formed by the concept ({M2,M4}, {D6,D9}).
1 2 3 M2 M3 D1 M2 M4 D6 D9 M3 M4 D10 D13
- Step 2: Final Answer Formulation
the answers merger.
Similar objects detection : The Response vector contains three concepts that we examine one by one. The first concept contains the document D1. We calculate then the degree of similarity between this document and every document existing in the two other concepts that are D6, D9, D10 and D13. The same treatment is carried out on the document D6. We calculate the similarity degree between D6 and D10 then between D6 and D13. The same treatment is done on the document D9. The degrees of calculated similarities are the following ones:
Similarity(D1, D6) = 1/3 =0.33; Similarity (D1, D9)= 1/4 = 0.25; Similarity (D1,D10) = 1/3 = 0.33; Similarity (D1,D13) = 1/3 = 0.33; Similarity (D6,D10) = 1/3 = 0.33; Similarity (D6,D13) = 1/3= 0.33;
Similarity (D9,D10) = 1 / 4 =0.25; Similarity (D9,D13) = 1/4 = 0.25;
is 0.33. Initially, the final answer is an empty set. We treat the first concept of the
words with those of the second concept and we search the similar documents. The result of this research is the documents set {D1,D6}, considering that the documents
0.25 that is less than the similarity threshold. So, we ignore D9 and we add the found documents to the final answer. At this step, the final answer is the set {D1,D6}.
first and the third concepts of the Response vector. The merge result is the set {M2,M3,M4} that is equal to the query. We remark that the documents D10 and D13 are similar to D1 and to D6 with the degree superior to 0.33. So, we add those documents to final answer that becomes {D1,D6,D10,D13}.
the last concepts. The result is the set {M2,M3,M4}. The similar documents are {D6,D10,D13} that we add to the final answer. The final answer is now the set {D1,D6,D10,D13} 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.
complexities.
- Phase 1: the concepts research from the different local databases. - Phase 2: the similar objects detection and the merge of k found concepts.
CT = CPhase 1(n,m,k) + CPhase 2(n,m,k)
tions. So, the temporal complexity is: CT = k×n×m+k×(n+1)+(n×k) = (k×n×m)+(k2k)/2+n×k ≈ O(k×n×m+k2) operations. The temporal complexity of the system HIC2RS is then in order of O(k×n×m+k2) operations.
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: CS = (n× m× k+ k+n2). 6
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.
1 0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0
age 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%.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Query Fig. 4. The answer time take by the systems CIRS and HIC2RS for the MED test collection.
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). 1 0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0 450 400 350 300 250 200 150 100 50 0 HIC2RS CIRS CIRS HIC2RS 0,1667 0,2 0,25 0,3333 0,4 0,5 0,6 0,6667 0,8333 1
Recall
450 400 350 300 250 200 150 100 50 0 CIRS HIC2RS 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29
Query Fig. 5. The answer time take by the systems CIRS and HIC2RS for the CRAN test collection.
ous 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.
ing. In the 1st International Conference on Formal Concept Analysis, Darmstadt, Germany, (2003).