Mustapha Bourahla
email: mbourahla@hotmail.com

Exact Reasoning over Imprecise Ontologies

Keywords: Vagueness, Ontology, OWL, Description Logics, Automatic Reasoning

A real world of objects (individuals) is represented by a set of assertions written with respect to defined syntax and semantics of description logic (formal language). These assertions should be consistent with the ontology axioms described as terminology of knowledge. The axioms and the assertions represent ontology about a particular domain. A real world is a possible world if all the assertions and the axioms over its set of individuals, are consistent. It is possible then to query the possible world by specific assertions (as instance checking) to determine if they are consistent with it or not. However, ontology can contain vague concepts which means the knowledge about them is imprecise and then query answering will not possible due to the open world assumption if the necessary information is incomplete (it is currently absent). A concept description can be very exact (crisp concept) or exact (fuzzy concept) if its knowledge is complete, otherwise it is inexact (vague concept) if its knowledge is incomplete. In this paper we propose a vagueness theory based on the definition of truth gaps as ontology assertions to express the vague concepts in Ontology Web Language (OWL2) (which is based on the description logic SROIQ(D)) and an extension of the Tableau algorithm for reasoning over imprecise ontologies.

Introduction

Formalisms for dealing with vagueness have started to play an important role in research related to the Web and the Semantic Web [START_REF] Lukasiewicz | Managing uncertainty and vagueness in description logics for the semantic web[END_REF][START_REF] Straccia | Foundations of Fuzzy Logic and Semantic Web Languages[END_REF]. Ontologies are the definition of domain concepts (extensions) and the relations between them. Formal ontologies are expressed in well-defined formal languages (for example, OWL2) [START_REF] Hitzler | OWL 2 Web Ontology Language: Primer[END_REF][START_REF] Krötzsch | OWL 2 profiles: An introduction to lightweight ontology languages[END_REF] that are based on expressive description logics (for example, SROIQ(D)) [START_REF] Baader | What's new in description logics[END_REF][START_REF] Turhan | Introductions to description logics -a guided tour[END_REF][START_REF] Horrocks | The even more irresistible SROIQ[END_REF]. We say ontology is vague if it has at least a vague definition of a concept. A concept (an extension) is vague if it defines a meaning gap with which we cannot decide the membership of certain objects (vague intension).

We state the problem with the following example. Assume an ontology defining a concept called Expensive in a domain about cars. The meaning of the concept is vague. This vagueness is pervasive in natural language, but until now is avoided in ontologies definitions. For the concept Expensive, we can define three sub-extensions, definitely expensive extension (there are some car prices that we regard as definitely expensive), definitely cheap extension (others we regard as definitely cheap cars) and a vagueness extension, average car prices are neither expensive nor cheap. The source of this indecision is the imprecise definition of concepts that is caused by lack of rigorous knowledge.

Related Works: Almost all concepts we are using in natural language are vague (imprecise). Therefore common sense reasoning based on natural language must be based on vague concepts and not on classical logic. The rising popularity of description logics and their use, and the need to deal with vagueness, especially in the Semantic Web, is increasingly attracting the attention of many researchers and practitioners towards description logics able to cope with vagueness. There are many works in literature for dealing with vagueness and most of them express it as a concept property as those based on fuzzy logics.

The notion of a fuzzy set proposed by Lotfi Zadeh [START_REF] Zadeh | Knowledge representation in fuzzy logic[END_REF] is the first very successful approach to vagueness. Fuzzy description logics (FDLs) are the logics underlying modes of reasoning which are approximate rather than exact, assertions are true to some degree [START_REF] Straccia | Foundations of Fuzzy Logic and Semantic Web Languages[END_REF][START_REF] Bobillo | Joining gödel and zadeh fuzzy logics in fuzzy description logics[END_REF][START_REF] Lukasiewicz | Description logic programs under probabilistic uncertainty and fuzzy vagueness[END_REF][START_REF] Stefan | Consistency reasoning in lattice-based fuzzy description logics[END_REF]. In this case, any concept instance will have a degree of membership that is determined by a defined fuzzy function. The vagueness under fuzzy theory is treated by extended fuzzy description logics that are supported by fuzzy semantics and fuzzy reasoning. The fuzzy description logics are applied in many domains. The fuzzy knowledge base is interpreted as a collection of constraints on assertions. Thus, the inference is viewed as a process of propagation of these constraints.

Assertions in fuzzy description logics, rather being satisfied (true) or unsatisfied (false) in an interpretation, are associated with a degree of truth using semantic operators, where the membership of an individual to the union and intersection of concepts is uniquely determined by its membership to constituent concepts. This is a very nice property and allows very simple operations on fuzzy concepts. In addition to the standard problems of deciding the satisfiability of fuzzy ontologies and logical consequences of fuzzy assertions from fuzzy ontologies, two other important reasoning problems are the best truth value bound problem and the best satisfiability bound problem.

In our work, the concepts are treated as having a fixed meaning (not a balanced meaning), shared by all users of the ontology; we propose instead that the meaning of a vague concept evolves during the ontology evolution, from more vague meaning to less vague meaning until it reaches if possible, a situation where it becomes non-vague concept. This meaning instability is the base of our vagueness theory that is used for reasoning over vague ontologies. Both theories represent two different approaches to vagueness. Fuzzy theory addresses gradualness of knowledge, expressed by the fuzzy membership, whereas truth gap theory addresses granularity of knowledge, expressed by the indiscernibility relation. The result of reasoning over vague ontology using truth gap theory is the posterior description that represents a revision of the prior description on the light of the evidence provided by acquired information. This property can be used to draw conclusions from prior knowledge and its revision if new evidence is available.

The other closest work to ours is the work in [START_REF] Pareti | Learning vague concepts for the semantic web[END_REF] which presents a framework for adjusting numerical restrictions defining vague concepts. An inconsistency problem can happen when aligning the original ontology to another source of ontological information or when ontology evolves by adding learned axioms. This adjustment is used to repair the original ontology for avoiding the inconsistency problem by modifying restrictions parameters called adaptors specified as concept annotations. The idea of this work is close to ours in the sense that we reduce the truth gaps when adding new assertions as learned knowledge to the ontology to guide the reasoning process which will play the same role as adjusting the vague concept restrictions. However, this work differs from our approach by the repair (modification) process applied on the original ontology to avoid introduced inconsistency. In our approach, we define the vague concepts as super concepts over restriction definitions. So, we don't have the problem of inconsistency to repair the ontology.

This paper is organized as follows. We begin in Section 2, by presenting Ontology Web Language (OWL2) and its correspondent description logic (SROIQ(D)). In Section 3, a vagueness theory is proposed to show how to express vague concepts and to describe the characteristics of vague ontologies. Section 4 presents the extended version of Tableau algorithm, to reason over imprecise ontologies. At the end, we conclude this paper by conclusions and perspectives.

Description Logics and Ontology Web Language

Ontologies are definitions of concepts and the relationships between them. They can be represented formally using formal languages. These formal description languages are based on well-defined Description Logics (DLs) [START_REF] Baader | What's new in description logics[END_REF], a family of knowledge representation formalisms. OWL2 DL is a variant of SROIQ(D) [START_REF] Horrocks | The even more irresistible SROIQ[END_REF], which consists of an alphabet composed of three sets of names. The set C of atomic concepts corresponding to classes interpreted as sets of objects, the set R of atomic roles corresponding to relationships interpreted as binary relations on objects and the set I of individuals (objects). It consists also of a set of constructors used to build complex concepts and complex roles from the atomic ones. The roles (object or concrete) are called properties; if their range values are individuals (relation between individuals) then they are called object (abstract) properties. If their range values are concrete data (relation between individual and a concrete data) then they are called data (concrete) properties. The set of SROIQ(D) complex concepts can be expressed using the following grammar:

C ::= | ⊥ | A | {a} | ¬C | C D | C D | ∃o.Self | ∀o.Self | (1) ∃o.C | ∀o.C | ∃c.P | ∀c.P | ≥ n s.C | ≤ n s.C
Where is the universal concept, ⊥ is the empty concept, A is an atomic concept, a an individual, C and D are concepts, o an object role, c a concrete role, s a simple role w.r.t. R, and n a non-negative integer. P is a predicate over a concrete domain that can have the form

P ::= DataT ype [∼ value] | P P | P P, ∼∈ {<, ≤, >, ≥} (2)
The data type can be any recognized data type as integer, real, etc. This syntax allows expressing concepts and roles with a complex structure. However, in order to represent real world domains, one needs the ability to assert properties of concepts and relationships between them. The assertion of properties is done in DLs by means of an ontology (or knowledge base). A SROIQ(D) ontology is a pair Thus, the assertional box A of a knowledge base, provides a description of a world. It introduces individuals by specifying their names, the concepts to which they belong, and their relations with other individuals. The semantics of the language uses either the closed world assumption or the open world assumption. With the closed world assumption, we consider that the world is limited to what is stated. It is this assumption that is normally adopted in databases. In description logics, it is rather the assumption of the open world which prevails. This open world assumption has an impact in the way of making inferences in description logics. The inference is more complex with the assumption of the open world; it is often called to consider several alternative situations for the proof. Another important aspect of description logic is that it does not presuppose the uniqueness of names (the standard names). That is, two different names do not necessarily mean that there is case to two separate entities in the described world. To be sure that two different entities a and b are represented, should be added the assertion a = b to the assertional box A.

O = T , A ,

Vagueness Theory for Imprecise Ontologies

We define a concept C as vague if it has a deficiency of meaning. Thus, the source of vagueness is the capability of meaning (it has borderline cases). For example, the concept Expensive is extensionally vague and it remains intentionally vague in a world of expensive and non-expensive cars. This means that there are truthvalue gaps where a vague concept is extensionally (intensionally) definitely true (tt), definitely false (ff ) and true or false (t f ). Let us consider the following ontology. Where price and speed are two concrete roles with the universal concept as their domains and their ranges Rge are defined by two integer intervals. In this knowledge base (ontology), we assume the price of a definitely expensive car (ExpensiveCar) is greater than or equal to fifty units and it is less than or equal to one hundred units, and a definitely no-expensive car (N onExpensiveCar) has a price between zero and thirty units. The concept Expensive and its complement are subsuming two complex concept expressions (ExpensiveCar and N onExpensiveCar). Each concept expression contains a sub-expression that is defined as quantified (universal or existential) restriction on a concrete role (for example, the concrete role is price and the restricted sub-expressions are ∃price. (int [≥ 50]) for the concept ExpensiveCar and ∃price. (int [≤ 30]) for the concept N onExpensiveCar). By the same way, we define the vague concept Sports and the concept ExpensiveSportsCar as a conjunction of the concepts Car, Expensive and Sports.

O = T =                                    Dom(price) ≡ , Rge(price) ≡ (int[≥ 0]) (int[≤ 100]), Dom(speed) ≡ , Rge(speed) ≡ (int[≥ 100]) (int[≤ 300]),
                                   , A =    Car(a)
We have taken advantage of the open world assumption in description logics to define vague concepts. This ontology satisfies the assertions Expensive(b) and ¬Expensive(a) but the assertions Expensive(d) and (¬Expensive)(d) are both not satisfied. With this knowledge base (ontology), we will assign tt to Expensive(b), ff to Expensive(a), and t f to Expensive(d). This means, there is a deficiency of meaning (truth value gaps) between Expensive and ¬Expensive. Consequently, the concept Expensive is considered vague and the same thing for the vague concept Sports. The assertion ExpensiveSportsCar(c) is considered as acquired information to state that c is an expensive sports car in spite of the fact that the terminology does not imply this assertion from information of the object c. We will see how this acquired (learned) information will be used to decide on other instances.

Thus, the satisfaction of a membership assertion to a vague concept depends on the concrete property value and the truth gaps. The vagueness definition of a concept will create one or more truth gaps. These are convex intervals (or ordered sequences) of values from a concrete domain with which the satisfaction of a membership assertion to the vague concept cannot be decided. There are two borderline values for each interval (or sequence). They are the lower (l) and the upper (u) bounds of a truth gap. Thus, we associate with each vague concept C a set of truth gap assertions according to a concrete role r (or to different concrete roles) used by its description.

These truth gaps assertions can be formulated using the description logic SROIQ(D) as a result of ontology description pre-processing. This will augment the ontology O = T , A by the membership and property assertions to be O = T , A ∪ {C(tt), (¬C)(ff ), r(x i , l i ), r(y i , u i )} if C is checked to be a vague concept according to a concrete role r, tt and ff are considered as two additional dummy individuals. The individuals x i , y i are either tt or ff with the conditions x i = y i ∧ x i+1 = y i , l i and u i are numerical values from the range of the concrete role r with l i < u i < l i+1 for 1 ≤ i < n, where n is the number of the truth gaps. This description should verify the following vagueness consistency. Lemma 1. (vagueness consistency). The truth gaps set defined of any vague concept C associated with a role r (or a set of roles) should verify the condition of acceptability (vagueness consistency), this means ∀i = 1, • • • , n -1 :

x i = y i ∧ y i = x i+1 ∧ l i < u i < l i+1 < u i+1
. This vagueness consistency condition can be formulated using the assertions on the dummy individuals tt and ff as

({C(tt), r(tt, d 1 ), r(tt, d 2 ), (¬C)(ff ), r(ff, d)} ⊆ A ⇒ d ∈ [d 1 , d 2 ]) ∧ ({(¬C)(ff ), r(ff, d 1 ), r(ff, d 2 ), C(tt), r(tt, d)} ⊆ A ⇒ d ∈ [d 1 , d 2 ]) (4)
A non-vague (crisp) concept C will have an empty set of truth gaps according to any concrete role r.

The intuition for this vagueness theory is as follows. An ontology is considered the knowledge base of an intelligent agent; if the ontology (knowledge base) O contains a vague concept C with respect to a concrete role r and one of its truth gaps has the smallest interval [l, u], where the assertions r(tt, u), r(ff, l) are in O. The agent cannot decide if an individual (object) a with r-property value within the interval [l, u] if it belongs to C or to its complement (we say that the knowledge base is incomplete). We assume that at a moment, assertions like C(a), r(a, d) are added to the ontology O, where l < d < u. This new information will change the ontology agent beliefs by reducing the truth gap interval to be [l, d]. We call that the individual a is similar to the dummy individual tt because they belong to the same concept C. Then, the individual tt will inherit the property of a. Now, if we add the assertions (¬C)(b), r(b, d ) with u > d > d, this will produce a vagueness inconsistency according to this vagueness theory because the agent has already changed its beliefs so that every property assertion of an individual with respect to the concrete role r where its range is greater than d should be member of the concept C. This vagueness theory is used to adjust the truth intervals (or the truth gaps) described in the original ontology by acquired new information.

Semantics for Vagueness Theory

The formal semantics of DLs is given in terms of interpretations. A SROIQ(D) interpretation is a pair I = (∆ I , (.) I ) where ∆ I is a non-empty set called the domain of I, and (.) I is the interpretation function which assigns for every A ∈ C a subset (A) I ⊆ ∆ I , for every o ∈ R a relation (o) I ⊆ ∆ I × ∆ I , called object role, for every c ∈ R a relation (c) I ⊆ ∆ I × D, called concrete role (D is a data type as integer and string) and for every a ∈ I, an element (a) I ∈ ∆ I . We say the interpretation I is a model of a SROIQ(D) ontology O = T , A , if it satisfies all the assertions in T and A. In addition, it is a model of any satisfied assertion by the ontology O. If C r is a vague concept with respect to the concrete role r and x i , y i ∈ {tt, ff }, then the interpretation function is extended to complex concepts and roles according to their syntactic structure.

( ) I = ∆ I (⊥) I = ∅ ({a}) I = (a) I (r) I = (r) I ∪ {(x i , l i ), (y i , u i ) ∧ x i = y i = x i+1 ∧ l i < u i , i = 1, • • • , n} (C r ) I = (C) I ∪ {tt} (¬C r ) I = (¬C) I ∪ {ff } (C r D r ) I = (C r ) I ∩ (D r ) I (C r D r ) I = (C r ) I ∪ (D r ) I (∃o.Self ) I = {a ∈ ∆ I |∃(a, b) ∈ (o) I ∧ a = b} (∀o.Self ) I = {a ∈ ∆ I |∀(a, b) ∈ (o) I ⇒ a = b} (∃o.C r ) I = {a ∈ ∆ I |∃(a, b) ∈ (o) I ∧ b ∈ (C r ) I } (∀o.C r ) I = {a ∈ ∆ I |∀(a, b) ∈ (o) I ⇒ b ∈ (C r ) I } (∃c.P ) I = {a ∈ ∆ I |∃(a, d) ∈ (c) I ∧ P (d)} (∀c.P ) I = {a ∈ ∆ I |∀(a, d) ∈ (c) I ⇒ P (d)} (≥ n s.C r ) I = {a ∈ ∆ I | |{b|(a, b) ∈ (s) I ∧ b ∈ (C r ) I }| ≥ n} (≤ n s.C r ) I = {a ∈ ∆ I | |{b|(a, b) ∈ (s) I ∧ b ∈ (C r ) I }| ≤ n}
Where n is the number of truth gaps for the vague concept C, P (d) means the value d verifies the predicate P and |S| is the cardinality of the set S. The predefined concepts like the universal concept , the empty concept ⊥, the atomic concepts A and the nominative concepts {a 1 , a 2 , • • • , a n } are defined as crisp concepts and then they will not be considered as vague concepts.

Example 1. The new ontology after generation of truth gap assertions on the original ontology O = T , A described in (3), is O new = T new , A new where, T new = T and using the syntax of SROIQ(D), A new = A ∪ {Expensive(tt), (¬Expensive)(ff ), Sports(tt), (¬Sports)(ff ), price(ff, 0), price(ff, 30), price(tt, 50), price(tt, 100), speed(tt, 200), speed(tt, 300), speed(ff, 100)}, speed(ff, 150)}. The new interpretations with these introduced assertions are as follows. The interpretation for the concrete role price is (price) I = {(a, 25), (b, 55), (c, 40), (d, 45), (ff, 0), (ff, 30), (tt, 50), (tt, 100)} and for the concrete role speed, the interpretation is (speed) I = {(a, 220), (b, 250), (c, 160), (d, 180), (ff, 100), (ff, 150), (tt, 200), (tt, 300)}. The interpretation of the vague concept Expensive price is {b, c, tt}.

This new ontology containing concept truth gaps is considered vague and then it is incomplete for reasoning. An ontology is complete if we can assign only the definite truth values (tt and ff ) to assertions. A vague (incomplete) ontology is an ontology that has at least one vague concept and then it is possible to assign the value t f to certain assertions. In addition, a vague ontology should be acceptable (Lemma 1), which means all the truth gap sets should be acceptable. We define a partial order between ontologies that is noted by O, ≤ , where O is a non-empty set of ontologies describing a domain. If O 1 and O 2 are two ontologies from O we write O 1 ≤ O 2 , if O 1 is less complete than O 2 (we say also that O 2 extends O 1 ). The relation ≤ (we call it also the extension relation) is based on comparison of truth gaps and it is transitive and antisymmetric. By this partial order definition, there is a canonical normal ontology O n that is the least complete ontology, which can be extended by other complete ontologies.

The set O has a base ontology that corresponds to description of which all other descriptions are extensions. This base ontology is composed of the terminological assertions and eventually some membership assertions. A condition that can be imposed on domain ontology is its completeability. It states that any intermediate ontology can be extended to a complete ontology. We suppose that ontology O has a vague concept C, with an acceptable set of truth gaps defined by the assertions set {C(tt), (¬C)(ff ), r(x 1 , l 1 ), r(y 1 , u 1 ), r(x 2 , l 2 ), r(y 2 , u 2 ), • • • , r(x n , l n ), r(y n , u n )}, then we define the ontology extension (⊕) by the assertions {C(a), r(a, d)} as follows.

T , A [C(tt), (¬C)(ff ), • • • , r(x i , l i ), r(y i , u i ), • • •] ⊕ T , {C(a), r(a, d)} = T , A ∪ {C(a), r(a, d)} ∪ r(x i , d) if x i = tt ∧ l i < d < u i r(y i , d) if y i = tt ∧ l i < d < u i T , A [C(tt), (¬C)(ff ), • • • , r(x i , l i ), r(y i , u i ), • • •] ⊕ T , {(¬C)(a), r(a, d)} = T , A ∪ {(¬C(a)), r(a, d)} ∪ (x i , d) if x i = ff ∧ l i < d < u i r(y i , d) if y i = ff ∧ l i < d < u i
This extension guarantees the ontology stability if the acquired informations are satisfied by the ontology description to be extended. Lemma 2. (stability property of O, ≤ ). Let α be an assertion, we say O, ≤ is stable if

∀O 1 , O 2 ∈ O, O 1 ≤ O 2 : O 1 |= α ⇒ O 2 |= α and O 2 |= α ⇒ O 1 |= α
The complete ontology may not be available to remove completely the vagueness, thus it is necessary to work with the most extended ontology. This means, the truth-valuation is based upon the most extended ontology. Ontology can be extended to complete ontology by learned assertions as a process of ontology evolution when using an intelligent agent or inferred assertions. The learned assertions can be imported from other domain ontologies, RDF databases or simply added by the user. In the following, we propose an extension of reasoning that can take into account the proposed vagueness theory.

Reasoning over Imprecise Ontologies

An interpretation I is a model of an ontology O = T , A denoted by I |= O if I satisfies all the axioms in T and all the assertions in A. The reasoning is for checking concept and role instances and for query answering over a satisfiable ontology [START_REF] Lutz | A tableau algorithm for DLs with concrete domains and GCIs[END_REF][START_REF] Pérez-Urbina | Efficient query answering for owl 2[END_REF]. Ontology satisfiability is to verify whether ontology O admits at least one model where consistency properties should be verified. Concept instance checking is to verify whether an individual a is an instance of a concept C in every model of O, i.e., whether O |= C(a). Role instance checking is to verify whether a pair (a, b) of individuals is an instance of a role r in every model of O, i.e., whether O |= r(a, b).

The satisfaction properties will be extended to deal with the vagueness in ontologies. A vague (imprecise) ontology is satisfiable if it generates acceptable truth gaps for all its concepts (note that an empty set of truth gaps is acceptable). For example, if we modify the concept ExpensiveCar in the vague ontology of the previous example to be Car ∃price. (int [≥ 55]) ¬Expensive, this will change the set of truth gaps assertions associated with the vague concept Expensive to be {Expensive(tt), (¬Expensive)(ff ), price(tt, 50), price(tt, 100), price(ff, 0), price(ff, 55)}. This set of truth gaps is not acceptable because it is a false set of assertions according to the vagueness consistency stated in (4). Nevertheless, the vague ontology is satisfiable by using the traditional reasoning techniques. However, if we add the assertions {Car(d), price(d, 52)} to the assertional box, the vague ontology becomes inconsistent because d is now at the same time expensive car and no-expensive car, although the ontology was initially satisfiable. In the following, we will extend the reasoning Tableau algorithm to cope with the problem of vague ontologies using this proposed vagueness theory.

The principle of this reasoning algorithm is the expansion of a finite configuration T = {A 1 , • • • , A n } of assertions that is represented as a set of subsets, each subset is composed of assertions on individuals, using well defined rules until no rule can be applied on at least one subset (satisfaction) or contradictions (clashes) are observed within all subsets (unsatisfaction). We will have a clash in a subset A i when a contradiction happens in it. There are three types of contradictions: ⊥(a) ∈ A i , C(a) ∈ A i ∧ (¬C)(a) ∈ A i , or unacceptable truth gaps assertions. If no expansion rule can be applied in A i we say that A i is open. The terminological box should be normalized to apply the expansion rules. It is necessary to begin the inference with formulas that are independent from any terminology. This means elimination of the definitions (equivalence axioms) and subsumptions (inclusion axioms) in the terminological box. If it contains no cycle in the definitions (which will be the case most of the time), it will happen

T 2 =            A 2 0 = A 1 0 = , A 2 1 = A 1 1 ∪
price(tt, 55), price(tt, 40), price(ff, 25), price(ff, 45), speed(tt, 220), speed(ff, 120), speed(tt, 160) ,

A 2 2 = A 1 2 ∪
price(tt, 55), price(tt, 40), price(ff, 25), speed(tt, 220), speed(ff, 120), speed(tt, 160), speed(ff, 180)

          
It is clear that the subset A 2 1 of assertions contains unacceptable truth gaps assertions (the following implication {Expensive(tt), price(tt, 40), price(tt, 50), (¬Expensive)(ff ), price(ff, 45)} ∈ A 2 1 ⇒ 45 ∈ [40, 50] is false). The same thing for the subset A 2 2 , where the implication {Sports(tt), speed(tt, 160), speed(tt, 200), (¬Sports)(ff ), speed(ff, 180)} ∈ A 2 2 ⇒ 180 ∈ [160, 200] is also false. Thus a clash is observed in the two subsets which makes d a member of ExpensiveSportsCar. The principle of this approach is as follows. Without this vagueness theory, d which has the price of 45 (greater than 30 and less than 50) and the speed of 180 (greater than 150 and less than 200) cannot be decided by the classical reasoners, as Expensive, Sports, ¬Expensive and ¬Sports because the definitions of Expensive and Sports are vague. However, the ontology contains an assertion indicating that the price 40 of c is an expensive price (Expensive(c)) and its speed 160 makes it a sports car; this information can help the reasoner to decide that the car d of price 45 and of speed 180 is also an expensive sports car.

Conclusion

In this paper, we have presented a vagueness theory to deal with the problem of ontologies containing vague concepts. The vague property (characteristic) of a concept is based in general, on certain concept data properties that may generate truth gaps. With the traditional reasoning methods, it is not possible to decide the membership of an individual (object) to a vague concept (class) if its data property is in the truth gap. Ontologies could have extension (evolution), where assertions may be added, intentionally or as result of inferences. This ontology evolution can reduce the truth gaps and then logically it will be possible to infer on previously undecided assertions. This proposed vagueness theory is used to extend the current reasoning method to take into account this vagueness notion. Implementation of this approach is one of our perspectives.

  where T is called a terminological box and A is called an assertional box. The terminological box consists of a finite set of axioms on concepts and roles. There are inclusion axioms on concepts, object and concrete roles to define a hierarchy (taxonomy) on the names of concepts and roles, (we write C D to denote inclusion axioms on concepts, where C and D are concepts, C ≡ D as an abbreviation for C D ∧ D C and r 1 r 2 for role inclusion, where r 1 and r 2 are object (concrete) roles, the same equivalence abbreviation can be applied on roles). The assertional box consists of a finite set of assertions on individuals. There are membership assertions for concepts (C(a) means the object (individual) a is member of C), membership assertions for roles (o(a, b) means the objects a and b are related by the object property o and c(a, d) means the object a has the data property (concrete role) c with a value equals d).

  , Car(b), Car(c), Car(d), ExpensiveSportsCar(c), price(a, 25), price(b, 55), price(c, 40), price(d, 45), speed(a, 220), speed(b, 250), speed(c, 160), speed(d, 180)

simply by replacing all the terms in the formula by their definitions in the terminology. Obviously, if a term of formula has no definition in terminology, it remains unchanged. We repeat this process until the resulting formula contains no term which has a definition in the terminology.

For reasoning over vague ontologies using the proposed vagueness theory, we have added the following two expansion rules that should be applied after every expansion by a classical Tableau rule (the reader can be referred to [START_REF] Horrocks | The even more irresistible SROIQ[END_REF][START_REF] Horrocks | A tableau decision procedure for SHOIQ[END_REF][START_REF] Lutz | A tableau algorithm for DLs with concrete domains and GCIs[END_REF] for the classical Tableau rules). We will get a clash (contradiction) if any new set of truth gaps assertions is not acceptable (Lemma 1 and Equation 4). The configuration length depends on ontology description and property being checked. Using the DL syntax of SROIQ(D), these two rules can be formulated as

These two rules will augment the assertions subset A i by the property assertion r(tt, d) if A i contains the assertion C(a)∧r(a, d)∧C(tt) (the rule V -Rule + (DL)) or by the property assertion r(ff, d) if A i contains the assertion (¬C)(a)∧r(a, d)∧ (¬C)(ff ) (the rule V -Rule -(DL)). We explain this algorithm extension on a simple example of an instance checking using the ontology described in [START_REF] Hitzler | OWL 2 Web Ontology Language: Primer[END_REF]. We want to check the membership of the individual d (instance checking) to the class ExpensiveSportsCar (O |= ExpensiveSportsCar(d)). This means that we want to prove that (¬ExpensiveSportsCar)(d) is inconsistent with the ontology description. After elimination of terminological axioms and normalization as preliminary steps before applying Tableau Rules, we have:

Using the classical expansion rule of the disjunction, we obtain the configuration:

We observe a clash in the subset A 1 0 (it contains Car(d) and (¬Car)(d)). By applying the rules V -Rule + (DL) and V -Rule -(DL), we get:


Imen Brahmi
email: imen.brahmi@gmail.com

Hanen Brahmi

Sadok Ben Yahia
email: sadok.benyahia@fst.rnu.tn

A Multi-agents Intrusion Detection System Using Ontology and Clustering Techniques

Keywords: Intrusion Detection System, Multi-agents, Clustering, Ontology. Recently, few approaches, within the intrusion detection field, are dedicated

Nowadays, the increase in technology has brought more sophisticated intrusions. Consequently, Intrusion Detection Systems (IDS) are quickly becoming a popular requirement in building a network security infrastructure. Most existing IDS are generally centralized and suffer from a number of drawbacks, e.g., high rates of false positives, low efficiency, etc, especially when they face distributed attacks. This paper introduces a novel hybrid multi-agents IDS based on the intelligent combination of a clustering technique and an ontology model, called OCMAS-IDS. The latter integrates the desirable features provided by the multi-agents methodology with the benefits of semantic relations as well as the high accuracy of the data mining technique. Carried out experiments showed the efficiency of our distributed IDS, that sharply outperforms other systems over real traffic and a set of simulated attacks.

Introduction

As far the cost of information processing and Internet accessibility is dropping, more and more organizations are becoming vulnerable to a wide variety of cyber threats. Therefore, network security is becoming a major challenge. Consequently, software tools, that can automatically detect a variety of intrusions, are of a compelling need. An Intrusion Detection Systems (IDS) has been of use to detect and defend intrusions more proactively in short period.

Even that IDSs have become a standard component in security infrastructures, they still have a number of signicant drawbacks [START_REF] Pinzón | idMAS-SQL: Intrusion Detection Based on MAS to Detect and Block SQL Injection Through Data Mining[END_REF]. Indeed, they suffer from problems of reliability, relevance, disparity and/or incompleteness in the presentation and manipulation of knowledge as well as the complexity of attacks. This fact hampers the detection ability of IDS, since it causes the generation excessive of false alarms and decreases the detection of real intrusions. In addition, most of the IDSs use centralized architectures. Unfortunately this strategy has several drawbacks [START_REF] Brahmi | Towards a Multiagent-Based Distributed Intrusion Detection System Using Data Mining Approaches[END_REF]. Indeed, the central processing node can lead to a single point of failure. Clearly, whenever the central processing node is attacked, then the whole IDS has been damaged. Besides, the transfer of all the information at a central processing unit implies a great need on network resources and leads to much network load on the system. Consequently, the centralized IDS suffers from scalability problems [START_REF] Brahmi | Towards a Multiagent-Based Distributed Intrusion Detection System Using Data Mining Approaches[END_REF]. Moreover, the communication and cooperation between a centralized IDS components are badly missing. To palliate these problems, the integration of a multi-agents technology within the IDS seemed to be an appropriate solution. In fact, the use of multi-agents system for intrusion detection offers a new alternative to the IDS with several advantages listed in literature, e.g., independently and continuous running, minimal overhead, scalability, etc., [START_REF] Brahmi | Towards a Multiagent-Based Distributed Intrusion Detection System Using Data Mining Approaches[END_REF]. Therefore, multi-agent technology makes the resilience of the system strong and thus ensures its safety [START_REF] Brahmkstri | Ontology Based Multi-Agent Intrusion Detection System for Web Service Attacks Using Self Learning[END_REF] Alongside, the concept of ontology has emerged as a powerful method for domain knowledge representation and sharing. It can improve the intrusion detection features giving the ability to share a common conceptual understanding threats and design the signature rules [START_REF] Abdoli | Ontology-based Distributed Intrusion Detection System[END_REF][START_REF] Djotio | MONI: Mobile Agents Ontology based for Network Intrusions Management[END_REF][START_REF] Isaza | Towards Ontology-Based Intelligent Model for Intrusion Detection and Prevention[END_REF][START_REF] Mandujano | An Ontology-Based Multiagent Approach to Outbound Intrusion Detection[END_REF][START_REF] Undercoffer | Modeling Computer Attacks: An Ontology for Intrusion Detection[END_REF]. In fact, the use of the ontologies and OWL (Ontology Web Language) within the intrusion detection context has different advantages: (i) Grasping the semantic knowledge about the intrusion detection subject; (ii) Expressing the IDS much more by building better rules of signatures using the SWRL (Semantic Web Rule Language) [START_REF] Horrocks | SWRL: A Semantic Web Rule Language Combining OWL and RuleML[END_REF]; and (iii) Making intelligent reasoning [START_REF] Brahmkstri | Ontology Based Multi-Agent Intrusion Detection System for Web Service Attacks Using Self Learning[END_REF][START_REF] Isaza | Towards Ontology-Based Intelligent Model for Intrusion Detection and Prevention[END_REF]. In this respect, it is possible to design a multi-agents architecture based on a knowledge basis represented as an ontology. The use of such architecture reveals conducive to the development of IDSs [START_REF] Brahmkstri | Ontology Based Multi-Agent Intrusion Detection System for Web Service Attacks Using Self Learning[END_REF].

In this paper, we investigate another way of tackling the aforementioned problems. Thus, we introduce a new distributed IDS, called OCMAS-IDS (Ontology and Clustering based Multi-AgentS Intrusion Detection System). OCMAS-IDS is based on the integration of the multi-agents technology, the ontology and the clustering technique. In this respect, our proposed system uses a set of agents that can be applied to a number of tasks, namely: data capturing, detecting the known and unknown attack categories and ultimately alerting the administrator. Through extensive carried out experiments on a real-life network traffic and a set of simulated attacks, we show the effectiveness of our proposal in terms of (i) the scalability and (ii) the detection ability of our system.

The remaining of the paper is organized as follows. Section 2 sheds light on the related work. We introduce our new distributed intrusion detection system based on the multi-agents technology in Section 3. We then relate the encouraging results of the carried out experiments in Section 4. Finally, Section 5 concludes and points out avenues of future work. fitting in the distributed IDS trend using ontological structure attempt to enhance the IDS accuracy and performing intelligent reasoning.

Worth of mention that the first research of applying ontology within intrusion detection context was done by Undercoffer et al. [START_REF] Undercoffer | Modeling Computer Attacks: An Ontology for Intrusion Detection[END_REF] in 2003. In this respect, the authors developed an ontology focused on the target (centric) and supply it within the format of the logical description language DARPA DARPA Agent Markup Language + Ontology Inference Layer (DAML + OIL). This ontology allows modeling the domain of computer attacks and facilitates the process of reasoning to detect and overcomes the malicious intrusions.

Mandujano [START_REF] Mandujano | An Ontology-Based Multiagent Approach to Outbound Intrusion Detection[END_REF] proposed a detection tool composed of a multi-agents architecture and an ontology focused on attacker, called FROID (First Resource for Outbound Intrusion Detection). FROID attempts to protect a set of nodes in a network using the ontology OID (Outbound Intrusion Detection). The proposed system is characterized by its intention to detect known attacks based on signatures. Thus, the main drawback of FORID system is that in case of an emerging attack, it will ignore it since this new attack has not yet been listed in the base of signatures.

In addition, Abdoli and Kahani [START_REF] Abdoli | Ontology-based Distributed Intrusion Detection System[END_REF] proposed a system, called ODIDS. The system includes two types of agents: IDSagent and MasterAgent. Based on the techniques of the semantic web, they have built an ontology for extracting semantic relationships between intrusions. The main moan that can be addressed to the ODIDS system stands in the fact that the MasterAgent is a central point of failure. Hence, if an intruder can prevent it from working (e.g., blocking or slowing the host where it is running), the entire system will be damaged. Another criticism of the ODIDS system is time wasting, since the system needs more time to make a connection between the MasterAgent and the IDSagents on the network and to send and receive messages between them.

Azevedoln et al. [START_REF] Azevedoln | An Autonomic Ontology-Based Multiagent System for Intrusion Detection in Computing Environments[END_REF] proposed an autonomic model, called AutoCore, which includes a set of intelligent agents as well as a domain ontology CoreSec, in order to perform intrusion detection independently. The system makes use of CoreSec as an ontology knowledge base with high-level concepts for information [START_REF] Azevedoln | An Autonomic Ontology-Based Multiagent System for Intrusion Detection in Computing Environments[END_REF]. The agents are then responsible for enabling the analysis of network traffic and the detection of malicious activities. However, the approach does not consider the secure state which is important to judge false positive alerts and successful possibility of attacks [START_REF] Li | An Ontology-Based Intrusion Alerts Correlation System[END_REF].

In [START_REF] Djotio | MONI: Mobile Agents Ontology based for Network Intrusions Management[END_REF], Djotio et al. proposed a MONI system based on an ontology model, called NIM-COM. The MONI system includes a multi-agents IDS to achieve a distribution of the detection activities. In addition, MONI is endowed with a Case Based Reasoning (CBR) mechanism to learn new attacks. Even though CBR is considered as a powerful reasoning paradigm and easy to set up, it suffers from re-engineering problems [START_REF] Pinzón | idMAS-SQL: Intrusion Detection Based on MAS to Detect and Block SQL Injection Through Data Mining[END_REF]. This lack of flexibility of the knowledge representation is with no doubt an inherent CBR limitation.

With the same preoccupation, Isaza et al. [START_REF] Isaza | Towards Ontology-Based Intelligent Model for Intrusion Detection and Prevention[END_REF] developed a multi-agents architecture for the detection and prevention of intrusions, called OntoIDPSMA. The representation of known attacks has been designed using a semantic model based on ontology specifying signatures and reaction rules. The authors integrated an Artificial Neural Network (ANN) technique and the clustering algorithm K-means for the identification of new attacks. However, the most significant disadvantage of ANN relies on the fact that its ability to identify an intrusion is completely dependent on the accurate training of the system, data and the methods that are used. Moreover, the configuration of an ANN is delicate and can significantly affect the results [START_REF] Sodiya | Neural Network based Intrusion Detection Systems[END_REF]. In addition, the performance of K-means and its effectiveness as a method for detecting new attacks depends on the random selection of the number of initial groups. Therefore, a "bad choice" of this number will decrease the detection of actual intrusions and increase the generation of false alarms [START_REF] Brahmi | Towards a Multiagent-Based Distributed Intrusion Detection System Using Data Mining Approaches[END_REF].

Due to its usability and importance, detecting the distributed intrusions still be a thriving and a compelling issue. In this respect, the main thrust of this paper is to propose a hybrid distributed IDS, called OCMAS-IDS, which integrates : (i) a multi-agents technology; (ii) an ontology; and (iii) an unsupervised clustering technique. The main idea behind our approach is to address limitations of centralized IDSs by taking advantage of the multi-agents paradigm as well as the ontological representation.

The OCMAS-IDS system

Agents and multi-agents systems are one of the paradigms that best fit the intrusion detection in distributed networks [START_REF] Brahmi | Towards a Multiagent-Based Distributed Intrusion Detection System Using Data Mining Approaches[END_REF]. In fact, the multi-agents technology distributes the resources and tasks and hence each agent has its own independent functionality, so it makes the system perform work faster [START_REF] Brahmkstri | Ontology Based Multi-Agent Intrusion Detection System for Web Service Attacks Using Self Learning[END_REF].

The distributed structure of OCMAS-IDS is composed of different cooperative, communicant and collaborative agents for collecting and analyzing massive amounts of network traffic, called respectively: SnifferAgent, MisuseAgent, AnomalyAgent and ReporterAgent. Figure 1 sketches at a glance the overall architecture of OCMAS-IDS. Worth of mention that the combination of the detection known attacks as well as the unknown ones can lead to improve the performance of the IDS and enhances its detection ability [START_REF] Kim | A Novel Hybrid Intrusion Detection Method Integrating Anomaly Detection With Misuse Detection[END_REF]. Consequently, OCMAS-IDS efficiently merges the detection of both types of attacks. It incorporates a MisuseAgent specialized on known attacks detection, as well as an AnomalyAgent competent on unknown attacks detection. The processing steps of OCMAS-IDS can be summarized as follows:

1. The SnifferAgent captures packets from the network. Indeed, a distributed IDS must undertake to analyze a huge volumes of events collected from different sources around the network. Consequently, the SnifferAgent permits to filter the packets already captured. Besides, it converts them to XML, using the XStream library3 . Finally, the pre-processed packets will be sent to others agents to be analysed; 2. The MisuseAgent receives the packets converted to XML from the Snif-ferAgent. It transforms these packets to OWL format in order to be compatible with the SWRL rules stored in the ontology. Now, it is ready to analyze the OWL packets to detect those that correspond to known attacks. Indeed, the MisuseAgent searches for attack signatures4 in these packets, by consulting the ontology ASO (Attack Signatures Ontology). Consequently, if there is a similarity between the OWL packets and the SWRL rules that define the attack's signatures, then the agent raises an alert to the ReporterAgent; 3. The filtered network packets are fed into an AnomalyAgent, which uses the clustering algorithm AD-Clust to detect the unknown attacks. Likewise, the agent sends an alert to the ReporterAgent, if an attack is identified; 4. Finally, the ReporterAgent generates reports and logs. OCMAS-IDS detects the known attacks through the intelligent agent Mis-useAgent, which uses an ontology to enrich data intrusions and attack signatures by semantic relationships. In what follows, we present the proposed ontology used within our system OCMAS-IDS.

The Attack Signatures Ontology (ASO)

Since last few decades, Raskin et al. [START_REF] Raskin | Ontology in Information Security: A Useful Theoretical Foundation and Methodological Tool[END_REF] opened a new field, that focuses on using Ontology within information security and its advantages. In fact, ontologies present an extremely promising new paradigm in computer security domain. They can be used as basic components to perform automatic and continuous analysis based on high-level policy defined to detect threats and attacks [START_REF] Isaza | Towards Ontology-Based Intelligent Model for Intrusion Detection and Prevention[END_REF]. Moreover, they enable the IDS with improved capacity to reason over and analyze instances of data representing an intrusion [START_REF] Djotio | MONI: Mobile Agents Ontology based for Network Intrusions Management[END_REF][START_REF] Undercoffer | Modeling Computer Attacks: An Ontology for Intrusion Detection[END_REF]. Furthermore, the interoperability property of the ontologies is essential to adapt to the problems of the systems distribution, since the cooperation between various information systems is supported [START_REF] Azevedoln | An Autonomic Ontology-Based Multiagent System for Intrusion Detection in Computing Environments[END_REF][START_REF] Djotio | MONI: Mobile Agents Ontology based for Network Intrusions Management[END_REF]. Within the OCMAS-IDS system, an ontology, called ASO (Attack Signatures based Ontology), is implemented, in order to optimize the knowledge representation and to incorporate more intelligence in the information analysis. Moreover, OCMAS-IDS integrates into its internal structure the interoperability between agents since they use the same model of ontology. The ASO ontology is characterized by network components, intrusion elements, classification defining traffic signatures and rules classes and instances. Figure 2 depicts a fragment of the ontology ASO, which implements the intrusion detection knowledge. The ASO ontology allows the representation of the signatures basis for known attacks, used with the agent MisuseAgent. The power and usefulness of ontology, applied to the signature basis issue, provide a simple representation of the attacks expressed by the semantic relationships between intrusion data. We can also infer additional knowledge about intrusion due to the ability of the ontology to infer new behavior by reasoning about data. Therefore, this fact improves the process of decision support for an IDS [START_REF] Abdoli | Ontology-based Distributed Intrusion Detection System[END_REF][START_REF] Brahmkstri | Ontology Based Multi-Agent Intrusion Detection System for Web Service Attacks Using Self Learning[END_REF][START_REF] Undercoffer | Modeling Computer Attacks: An Ontology for Intrusion Detection[END_REF].

The signature basis incorporates rules provided by the ASO ontology, that allows a semantic mean for reasoning and inferences. In fact, the rules are extracted using the SWRL language (Semantic Web Rule Language). The latter extend the ontology and enriches its semantics by the deductive reasoning capabilities [START_REF] Horrocks | SWRL: A Semantic Web Rule Language Combining OWL and RuleML[END_REF]. It allows to handle instances with variables (?x, ?y, ?z). Thus, the SWRL rules are developed according to the scheme: Antecedent → Consequent, where both antecedent and consequent are conjunctions of atoms written a 1 ∧ ...∧ a n . Variables are indicated using the standard convention of prefixing them with a question mark (e.i., "?x"). The following example shows a rule represented with SWRL.

Example 1. NetworkHost(?z) ∧ IntrusionState(?p) ∧ GeneratedBY(?p,?z) ∧ SQLInjection(?p) ∧ Directd To(?p,?z) → SystemSQLInjectionState(?p,?z) Using this syntax, a rule asserting that the composition of the network host(z) and an intrusion state(p) properties implies the attack "SQL Injection" property.

When constructing our ontology, we designed and implemented multiple rules to define various attacks and signatures. The defined rules allow properties inferences and reasoning process. The attack properties, e.g., WebAttack, SQLInjection, DoS, dDoS, and so on, are defined as ontology' attributes identifying the type of an intrusion.

Even thought, the known attacks are detected, it remains nevertheless the problem of the new attacks detection. In this respect, additionally to the Mis-useAgent, based on the ontology, OCMAS-IDS uses an AnomalyAgent based on the clustering analysis. The algorithm is described in the following subsection.

The clustering algorithm AD-Clust

Needless to remind that the application of the data mining techniques within the intrusion detection context can effectively improve the detection accuracy, the detection speed, and enhance the system's own security [START_REF] Azad | Data Mining in Intrusion Detection: A Comparative Study of Methods, Types and Data Sets[END_REF]. Thus, as an intelligent analysis task, the AnomalyAgent provides the crossroads of multi-agents systems with the clustering technique, in particular the AD-Clust algorithm. The idea behind this technique is that the amount of normal connection data is usually overwhelmingly larger than that of intrusions [START_REF] Brahmi | AD-Clust: Dtection des anomalies base sur le Clustering[END_REF]. Whenever this assumption holds, the anomalies and attacks can be detected based on cluster sizes, i.e, large clusters correspond to normal data, and the rest of the data points, which are outliers, correspond to attacks [START_REF] Syarif | Unsupervised Clustering Approach for Network Anomaly Detection[END_REF].

AD-Clust, (Anomaly Detection-based Clustering), is an unsupervised clustering algorithm introduced by Brahmi et al. in [START_REF] Brahmi | Towards a Multiagent-Based Distributed Intrusion Detection System Using Data Mining Approaches[END_REF][START_REF] Brahmi | AD-Clust: Dtection des anomalies base sur le Clustering[END_REF], to improve the quality of the K-means algorithm applied within the intrusion detection context. Indeed, the latter suffers from a greater time complexity, which becomes an extremely important factor within intrusion detection due to the very large packets sizes [START_REF] Ranjan | A New Clustering Approach For Anomaly Intrusion Detection[END_REF]. Moreover, the number of clusters dependency and the degeneracy constitute the drawbacks that hamper the use of K-means for anomaly detection [START_REF] Ranjan | A New Clustering Approach For Anomaly Intrusion Detection[END_REF]. In this respect, the AD-Clust algorithm combines two prominent categories of clustering, namely: distance-based [START_REF] Syarif | Unsupervised Clustering Approach for Network Anomaly Detection[END_REF] as well as density-based [START_REF] Duan | Density-Based Clustering and Anomaly Detection[END_REF]. It exploits the advantages of the one to palliate the limitations of the other and vice versa.

The processing steps of our algorithm AD-Clust can be summarized as follows [START_REF] Brahmi | Towards a Multiagent-Based Distributed Intrusion Detection System Using Data Mining Approaches[END_REF]:

1. Extraction of the density-based clusters that are considered as candidate initial cluster centers. The density-based clustering is used as a preprocessing step for the AD-Clust algorithm; 2. Compute the Euclidean distance between the candidate cluster center and the instance that will be assigned to the closest cluster. For an instance x i and a cluster center z i , the Euclidean distance is defined as:

distance(x i , z i ) = n i=1 (x i -z i ) 2 (1)
3. The size of a neighborhood of instances is specified by an input parameter.

We use the k parameter to distinguish it from the k parameter used by the K-means algorithm. Hence, k specifies the minimal number of instances in a neighborhood and controls the granularity of the final clusters of the clustering-based density. If k is set to a large value, then a few large clusters are found. To reduce the number of candidate clusters k to the expected number k, we can iteratively merge the two most similar clusters. Otherwise, if k is set too small, then many small clusters will be generated. The clusters will be split, new clusters will be created to replace the empty ones and the instances will be re-assigned to existing centers. This iteration will continue until there is no empty cluster. Consequently, the outliers of clusters will be removed to form new clusters, in which instances are more similar to each other. In this way, the value of initial cluster centers k will be determined automatically by splitting or merging clusters; 4. Within the detecting phase, the AD-Clust algorithm performs the detection of intrusions. Thus, for each novel instance I the algorithm proceeds as follows:

(a) Compute the Euclidean distance and find the cluster that presents the shortest distance with respect to I. (b) Classify I by the category of the closest cluster. Clearly, if the distance between I and the cluster of "normal" instances is the shortest one, then I will be a normal instance. Otherwise, I is an intrusion.

Experimental results

In order to assess the overall performance of OCMAS-IDS in a realistic scenario, a prototype of the proposed architecture was implemented using Sun's Java Development Kit 1.4.1, the well known platform JADE5 3.7, the Eclipse and the JPCAP6 0.7. The ontology ASO is designed using Protégé7 . Through the carried out experiments, we have to stress on evaluating the performance of our system in terms of (i ) the scalability-related criteria such as network bandwidth, detection delay and system response time; and (ii ) the detection ability. During the evaluations, we compare the results of the OCMAS-IDS system vs. that of the centralized IDS Snort [START_REF] Roesch | Snort -Lightweight Intrusion Detection System for Networks[END_REF] and the multi-agents based ontology one MONI8 [START_REF] Djotio | MONI: Mobile Agents Ontology based for Network Intrusions Management[END_REF]. All experiments were carried out on equivalent machines equipped with a 3GHz Pentium IV and 8GB of main memory. We used machines that were connected via a switch, thus forming a switched network. Moreover, we simulated attacks using the well known tool Metasploit9 version 3.5.1. The simulated eight different attack types are:

-attack1: DoS Smurf; -attack2: Backdoor Back Office; -attack3: SPYWARE-PUT Hijacker; -attack4: Nmap TCP Scan; -attack5: Finger User; -attack6: RPC Linux Statd Overflow; -attack7: DNS Zone Transfer; and -attack8: HTTP IIS Unicode.

The scalability evaluation

In order to test the scalability of OCMAS-IDS, we study the relationship between the bandwidth consumption and a number of attack types. Moreover, the variation of the detection delay according to the number of packets is evaluated. Additionally, we assess how the response time varies with respect to eight attack types. As depicted in Figure 3 (a), the maximum bandwidth consumed by OCMAS-IDS and MONI is lower compared to that of Snort. For example, the maximum bandwidth consumed by OCMAS-IDS is 0.06 Mbits/sec, which is very low as well. The reduction of the network bandwidth consumption is owe to the use of the multi-agents system. Thus, the OCMAS-IDS system is not greedy in bandwidth consumption, which is definitely a desirable feature for any distributed system [START_REF] Brahmi | Towards a Multiagent-Based Distributed Intrusion Detection System Using Data Mining Approaches[END_REF].

Besides, Figure 3(b) plots the detection delay against the number of packets, using the OCMAS-IDS, MONI and Snort systems. According to this figure, we can answer the question: why the realization of the multi-agents IDS is advantageous? Clearly, the results show that the detection delay of both systems linearly increases with the number of packets. Moreover, the gap between both curves related to the detection delay of OCMAS-IDS and MONI is small, since both systems are based on multi-agents technology. In addition, Figure 3(b) highlights that our proposed system OCMAS-IDS is faster than the system Snort. This can be explained by the fact that agents operate directly on the host whenever an action has to be taken, their response is faster than systems where actions were taken by the central controller, i.e., Snort.

Figure 3 (c) illustrates the response time required by OCMAS-IDS with respect to the attack types. On the one hand, we remark that the detection of all attack types, on average, result in lower response time compared to that of Snort, due to its centralized detection engine. In addition, this figure proved how fast our system respond. For example, the response time of OCMAS-IDS was 35 seconds for attack5, which is absolutely negligible.

On the other hand, within MONI, the ontology model is developed under JADE. Differently, the ontology ASO of our system OCMAS-IDS is designed under Protégé and queried with SWRL. The response time of OCMAS-IDS is better than that of MONI. The main reason is that in the case of OCMAS-IDS, the inferred model is computed only once before the matching starts and used throughout all the queries. Thus, the figure indicates that OCMAS-IDS outperforms MONI and permits the exploitation of the semantics of ASO.

To sum up, it is clear from the obtained results that the performance of the OCMAS-IDS will not deteriorate too much with the increase in the number of attacks, which is justified by its low bandwidth consumption, reduced detection delay and quick response time. Likewise, in case of more machines are connected to the network, the OCMAS-IDS system still withstand the load and swiftly deliver the results.

The detection ability

In order to evaluate the detection ability of an IDS, two interesting metrics are usually of use [START_REF] Brahmi | Towards a Multiagent-Based Distributed Intrusion Detection System Using Data Mining Approaches[END_REF]: the Detection Rate (DR) and the False Positive Rate (FPR). Indeed, the DR is the number of correctly detected intrusions. On the contrary, the FPR is the total number of normal instances that were "incorrectly" considered as attacks. In this respect, the value of the DR is expected to be as large as possible, while the value of the FPR is expected to be as small as possible. With respect to Figure 4 (a), we can remark that the FPR of OCMAS-IDS and MONI is significantly lower compared to that of Snort. This fact is due to the adaptive mechanisms used by the agents, enabling both systems, i.e., OCMAS-IDS and MONI, to better suit the environment. Consequently, the false alarms can be reduced correspondingly. For example, for attack3 the FPR of Snort can reach values as high as 0.019% compared to 0.007% of MONI and 0.005% of OCMAS-IDS.

Moreover, Figure 4 (b) shows that the DR of OCMAS-IDS is higher than that of MONI. Moreover, among the three investigated IDS, Snort has the lowest DR. For instance, for attack3, whenever OCMAS-IDS and MONI have the DR 97.9% and 94.9%, respectively, Snort has 74.1% DR. This is due to his centralized architecture.

Knowing that a main challenge of existing IDSs is to decrease the false alarm rates [START_REF] Brahmi | Towards a Multiagent-Based Distributed Intrusion Detection System Using Data Mining Approaches[END_REF], the main benefit of our system is to lower the false alarm rate, while maintaining a good detection rate.

Conclusion

In this paper, we focused on a distributed architecture and multi-agents analysis of intrusions detection system to tackle the mentioned above challenges, i.e., the high detection delay, the high bandwidth consumption as well as the low detection ability. Thus, we introduced a multi-agents intrusions detection system called OCM AS-IDS based on an efficient ontology model, called ASO, as well as a clustering algorithm called AD-Clust. The carried out experimental results showed the effectiveness of the OCMAS-IDS system and highlighted that our system outperforms the pioneering systems fitting in the same trend.

Future issues for the present work mainly concern: (i) the alert correlation techniques by using the multi-agents system and ontology [START_REF] Li | An Ontology-Based Intrusion Alerts Correlation System[END_REF].

Fig. 1 .

 1 Fig. 1. The architecture of OCMAS-IDS at a glance.

Fig. 2 .

 2 Fig. 2. The Attack Signatures based Ontology ASO.

Fig. 3 .

 3 Fig. 3. The bandwidth consumption, the analysis delay and the response time of OCMAS-IDS vs. Snort and MONI.

Fig. 4 .

 4 Fig. 4. The FPR and the DR of OCMAS-IDS vs. Snort and MONI.

Available at: http://xstream.codehaus.org/.

An attack signature is a known attack method that exploits the system vulnerabilities and causes security problem[START_REF] Brahmi | Towards a Multiagent-Based Distributed Intrusion Detection System Using Data Mining Approaches[END_REF].

Available at: http://jade.tilab.com

Available at: http://netresearch.ics.uci.edu/kfujii/jpcap/doc/

Available at: http://protege.stanford.edu/download/download.html

We thank Mrs. Djotio et al.[START_REF] Djotio | MONI: Mobile Agents Ontology based for Network Intrusions Management[END_REF] for providing us with the implementation of MONI system.

Available at: http://www.metasploit.com/


Said Gadri
email: kadri.said28@yahoo.fr

Abdelouahab Moussaoui
email: moussaoui.abdel@gmail.com

Arabic Texts Categorization: Features Selection Based on the Extraction of Words' Roots

Keywords: root extraction, information retrieval, bigrams technique, Arabic morphological rules, feature selection

One of methods used to reduce the size of terms vocabulary in Arabic text categorization is to replace the different variants (forms) of words by their common root. The search of root in Arabic or Arabic word root extraction is more difficult than other languages since Arabic language has a very different and difficult structure, that is because it is a very rich language with complex morphology. Many algorithms are proposed in this field. Some of them are based on morphological rules and grammatical patterns, thus they are quite difficult and require deep linguistic knowledge. Others are statistical, so they are less difficult and based only on some calculations. In this paper we propose a new statistical algorithm which permits to extract roots of Arabic words using the technique of ngrams of characters without using any morphological rule or grammatical patterns.

Introduction

Arabic is one of the oldest and the most used language in the world, it is spoken by over 300 million people in Arabic world, and used by more than 1.7 billion Muslims over the world because it is the language of the Holy Quran, here we can distinguish two types of Arabic; a more classical language, as found in the Holy Quran or poetry, a standardized modern language, and regional dialects [START_REF] Fatma | Rule-based Approach for Arabic Root Extraction: New Rules to Directly Extract Roots of Arabic Words[END_REF]. We note also that Arabic language is a semitic language [START_REF] Ghazzawi | The Arabic Language in the Class Room. 2nd EDN[END_REF][START_REF] Ethnologue | [END_REF] based on 28 cursives letters written from right to left .

The word in Arabic is formed of the root part and some affixes (antefixes, prefixes, infixes, suffixes) that form the word ؼأنرًَٕٛٓا( Saaltmwnyha). The Arabic root extraction is a very difficult task which is not the case for other languages as English or French, because Arabic is a very rich language with a very difficult structure and complex morphology. Arabian linguists show that all nouns and verbs of Arabic language are derived from a set of roots containing about 11347 roots; more than 75 % of them are trilateral roots [START_REF] Al-Kamar | Computer and arabic language computerizing[END_REF].

There are many applications based on the roots of words in Arabic processing such as: text"s classification, text summarizing, information retrieval, data and text mining. [START_REF] Ghwanmeh | ah: Enhanced algorithm for extracting the root of Arabic words[END_REF][START_REF] Yousef | Evaluation of different query expansion techniques and using different similarity measures in Arabic documents[END_REF].

The Arabic words " roots can be classified according to the vowels letters ( ٘ ، ٔ ، أ a, w, y) into two types [START_REF] Wightwick | Arabic Verbs and Essentials of Grammar, 2E (Verbs and Essentials of Grammar Series)[END_REF], strong roots that do not contain any vowel ( ، ذطج ، شْة فرح go,

come out, open), vocalic roots that contain at least one vowel ٔعس( ، أٖٔ shelter, promise). Arabic roots can be further classified according to the number of their characters into four types: Trilateral roots which form most words in Arabic language [START_REF] Al-Kamar | Computer and arabic language computerizing[END_REF] (e.g., ذطج ، كرة ، عهى know, write, come out), Quadrilateral roots (e.g., طًأٌ ، زحطج roll, assure), Quinquelateral roots (e.g., ، اَطهك ، الرظس اَكؽط، broken, economize, start) and Hexalateral roots ّط( الشع اؼرحؽٍ ، اؼرعًم use, enjoy, tremble).

There are two classes of methods used to extract the roots of Arabic words, the first class is based on morphological rules, so its methods simulate the same process of an expert linguist during his analysis of a given Arabic word [START_REF] Fatma | Rule-based Approach for Arabic Root Extraction: New Rules to Directly Extract Roots of Arabic Words[END_REF], [START_REF] Al-Omari | Building and Benchmarking New Heavy/Light Arabic Stemmer[END_REF][START_REF] Shereen | Stemming Arabic text[END_REF][START_REF] Momani | A novel algorithm to extract tri-literal Arabic roots[END_REF][START_REF] Al Shalabi | Pattern-based stemmer for finding Arabic roots[END_REF], which make the process of extracting root difficult and complex because of the diversity of morphological formulas and the multiplicity of words forms for the same root when changing the original characters position in the word (e.g., يعانى ، عٕانى ، عهٕو ، عانى ، عهى know, scientist, sciences, worlds, landmarks) [START_REF] Hajjar | A system for evaluation of Arabic root extraction methods[END_REF][START_REF] Al-Nashashibi | An improved root extraction technique for Arabic words[END_REF]. The second class is formed of statistical methods which are simple, fast, and do not require any morphological rules but some calculations [START_REF] Al-Shalabi | New Approach for Extracting Arabic Roots[END_REF][START_REF] Rehab | Arabic Text Categorization[END_REF][START_REF] Al-Nashashibi | Stemming Techniques for Arabic Words: A Comparative Study[END_REF][START_REF] Kanaan | New Approach for Extracting Quadrilateral Arabic Roots[END_REF][START_REF] Ghwanmeh | An Algorithm for extracting the Root of Arabic Words[END_REF][START_REF] Mohamad | A: Building an Effective Rule-Based Light Stemmer for Arabic Language to Improve Search Effectiveness[END_REF][START_REF] Al-Shalabi | Stemmer Algorithm for Arabic Words Based on Excessive Letter Locations[END_REF].

In this paper, we propose a new statistical method which permits to extract roots of Arabic words using the approach of n-grams of characters without using any morphological rule. The paper is organized as follows: the first section is a general introduction to the field of study. The second section presents some related works, so we review some papers that treat the problem of extraction of Arabic word"s roots. In the third section we introduce our new algorithm. The fourth section presents the experiments that we have done to test our new method and also presents the obtained results. In the last section we conclude our work by summarizing our realized work and giving some ideas to improve it in the future.

Related Works

Many researchers proposed some algorithms to extract Arabic words roots, some of these algorithms are based on morphological rules. Thus, they are called morphological methods. Others do not use any morphological rule but some statistical calculations, so they are called statistical algorithms.

In the first class of algorithms, we can note the following: [START_REF] Shereen | Stemming Arabic text[END_REF], [START_REF] Shereen | Stemming Arabic Text[END_REF] Khoja"s roots extractor removes the longest suffix and prefix. It then matches the remaining word with verbal and noun patterns, to extract the root. The roots extractor makes use of several linguistic data files such as a list of all diacritics, punctuation characters, definite articles, and stop words [START_REF] Larkey | Arabic information retrieval at UMass in TREC-10[END_REF][START_REF] Larkey | Improving Stemming for Arabic Information Retrieval: Light Stemming and Occurrence Analysis[END_REF][START_REF] Larkey | Light Stemming for Arabic Information Retrieval, Arabic Computational Morphology Text[END_REF][START_REF] Sawalha | Comparative Evaluation of Arabic Language Morphological Analyzers and Stemmers[END_REF]. [START_REF] Al-Nashashibi | An improved root extraction technique for Arabic words[END_REF] Propose a linguistic approach for root extraction as a preprocessing step for Arabic text mining. The proposed approach is composed of a rule-based light stemmer and a pattern-based infix remover. They propose an algorithm to handle weak, eliminated-long vowel, hamzated and geminated words. The accuracy of the extracted roots is determined by comparing them with a predefined list of 5,405 trilateral and quadrilateral roots. The linguistic approach performance was tested on texts" collection consists of eight categories, the author achieved a success ratio about 73.74%. [START_REF] Hawas | Exploit relations between the word letters and their placement in the word for Arabic root extraction[END_REF] Presents a new Arabic root extractor that tries to assign a unique root for each Arabic word without having an Arabic roots list, a word patterns list, or the list of Arabic prefixes and suffixes. The algorithm predict the letters positions that may form the word root one by one, using rules based on the relations between the Arabic word letters and their placement in the word. This algorithm consists of two parts, the first part gives the rules that distinguish between the Arabic definite letter انـ" AL, La" and the original word letters ."انـ" The second part segments each word into three parts and classifies its letters according to their positions. The author tested her proposed algorithm using the Holy Quran words and obtained an accuracy of 93.7% in root extracting process.

In the second class of algorithms we can note the following: [START_REF] Al-Shalabi | New Approach for Extracting Arabic Roots[END_REF] Developed a root extraction algorithm which does not use any dictionary, their algorithm categorizes all Arabic letters according to six integer weights, ranging from 0 to 5, as well as the rank of the letter which is determined by the position this letter holds in a word. The weight and rank are multiplied together, and the three letters with the smallest product constitute the root of the word. We note that [START_REF] Al-Shalabi | New Approach for Extracting Arabic Roots[END_REF] did not explain on what basis did it use such ranking or weighting. [START_REF] Momani | A novel algorithm to extract tri-literal Arabic roots[END_REF] Proposes an algorithm to extract tri-literal Arabic roots, this algorithm consists of two steps; in the first step they eliminate stop words as well prefixes and suffixes. In the next step, they remove the repeated word"s letters until only three letters are remained, and then they arrange these remaining letters according to their order in the original word, which form the root of the original word. The obtained results were very promising and give an accuracy of root"s extraction over than 73%. [START_REF] Hmeidi | A novel approach to the extraction of roots from Arabic words using bigrams[END_REF] Propose a new way to extract the roots of Arabic words using n-grams technique. They used two similarity measures; the "Manhattan distance measurement" and the "Dice"s measurement". They tested their algorithm on the Holy Quran and on a corpus of 242 abstracts from the Proceedings of the Saudi Arabian National Computer Conferences. They concluded from their study that combining the n-grams with the Dice"s measurement gives better results than using the Manhattan distance measurement. [START_REF] Boudlal | A markovian approach for Arabic root extraction[END_REF] propose a new algorithm to find a system that assigns, for every non vowel word a unique root. The proposed system consists of two modules; the first one consists of analyzing the context by segmenting the words of the sentence into its elementary morphological units in order to extract its possible roots. So, each word is segmented into three parts (prefix, stem and suffix). In the second module, they based on the context to extract the correct root among all possible roots of the word. They validate their algorithm using NEMLAR Arabic writing corpus that consists of 500,000 words, and their proposed algorithm gives the correct root in more than 98% of the training set and 94% of the testing set. [START_REF] Yousef | An Improved Arabic Word"s Roots Extraction Method Using N-gram Technique[END_REF] Propose a new algorithm which use the ngrams technique. In this technique, both the word and its assumed root are divided into pairs called bi-grams, then the similarity between the word and the root is calculated using equation (1) [START_REF] Frakes | Stemming Algorithms[END_REF]. This process is repeated for each root in the roots list: To use equation [START_REF] Fatma | Rule-based Approach for Arabic Root Extraction: New Rules to Directly Extract Roots of Arabic Words[END_REF] for extracting the word"s root, we must have: the word (A) and the potential roots (B) to compare with, then the similarity measuring is conducted by computing the value of (S) between the word (A) and each potential roots (B).

3.

The Proposed Algorithm

In our new algorithm, we use also the n-grams technique to extract Arabic words roots, for this purpose, we proceed according to the following steps:

Step 1: we segment the word for which we want to find the root, and all the roots of the list into bigrams (2-grams).

For example if we have the word "يرهبىن" and a list of six (06) roots ( ، ذهب ، خرج ، فتح نهب ، وهب ، ,)وجد we proceed the segmentation step as follows:

W = "ٚصْثٌٕ"  ( شٌ ، شٔ ، شب ، شِ ، ٍٚ ، ٕٚ ، ٚة ، ّٚ ٚص، ٌٔ ، تٍ ، تٕ ، ٍْ ، ْٕ ، ْة ، ) R1 = "فرح"  ( ف د ، ف ح ، ذ ح ) R2 = "ذطج"  ضج( ، ذح ، )ذط R3 = "شْة"  ْة( ، شب ، )شِ R4 = "ٔخس"  خس( ، ٔز ، )ٔج R5 = "ْٔة"  ْة( ، ٔب ، ِٔ) R 6 = "َٓة"  ْة( ، َة ، َّ)
Step 2: we calculate the following parameters:

: The number of unique bigrams in the word w : The number of unique bigrams in the root Ri : The number of common unique bigrams between the word W and the root Ri ̅ : The number of bigrams belonging to the word w and do not belong to the root Ri ( ̅ = )

̅ : The number of bigrams belonging to the root Ri and do not belong to the word w ( ̅ = -) For the previous example we have:

=18, =3, =3, =3, =3, =3, =3, =0, =0, =3, =0, =1, =1, ̅ , ̅ ̅ , ̅ , ̅ , ̅ , ̅ ̅ ̅ ̅ ̅ ̅ .
Step3: we take only the roots having at least one common bigram with the word w ( ≥ 1) as candidate roots among the list of all roots in order to reduce the calculation time.

In our previous example, we can take only the roots: R 3 = ,"شْة" R 5 = " ْٔ ة ", R 6 = "َٓة" with = 3, 1, 1 respectively.

Step4: we calculate the distance D(w, R i ) between the word W and each candidate root R i (R 3 , R 5 , R 6 ) according to the following equation :

̅ ̅ (2)
Where: k is a constant which must take a high value (we put here k=100) Step5: in the last step, we assign the root that has the lowest value of distance D(w, R i ) among the candidate roots to the word W. it is the required root.

For
In our example, the root of the word "ٚصْثٌٕ" is "شْة" Finally, we note that our new algorithm has the following advantages: 1.Does not require the removal of affixes whose distinction from the native letters of the word is quite difficult. 2.Works for any word whatever the length of the root.

3.Valid for strong roots and vocalic roots which generally pose problems in

Arabic during their derivation, because of the complete change of their forms. 4.Does not use any morphological rule nor patterns but simple calculations of distances. 5.Very practical algorithm and easy to implement on machine.

Experimentations and Obtained Results

To validate our proposed algorithm, we used three corpus which can be classified according their sizes into: small corpus, middle corpus, and large corpus.

Each one is constituted of many files as indicated below:

1. The file of derived forms (gross words) which contains morphological forms of words derived from many Arabic roots. 2. The file of roots which contains many Arabic roots, we note that these roots are trilateral, quadrilateral, quinquelateral, and hexalateral. We note also that many of them are vocalic roots which contain at least one vowel. 3. The file of golden roots which contain the correct roots of all words present in our corpus (the file in (1)), this golden list was prepared by an expert linguist and used as reference list, i.e., by comparison between the list of obtained roots (extracted by the system) and the reference list (established by the expert), we can calculate the roots extraction accuracy (success ratio).

ٚرعهًٌٕ

ٌٔ يٍ يٕ نٍ نٕ نى عٍ عٕ عى عم ذٍ ذٕ ذى ذم ذع ٍٚ ٕٚ ٚى ٚم ٚع ٚد

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 28 عانى نى او ال عى عم عا 1 1 1 1 1 1 6 كاذة كد كا ذة اب اخ كة 1 1 1 1 1 1 6 كراذٛة ٚة ذة ذٙ اب ا٘ اخ ذة ذٙ ذد ذا كة كٙ كد كا كد 1 1 1 1 2 2 1 1 1 1 1 2 12

الرظاز

از طس طا ذس ذا ذض لس لا لض لد از اا اص اخ اق

يرألنئ

نئ أئ أل نئ نم أل ذئ ذم ذأ ذم يئ يم يأ يم يد

1 1 2 1 1 1 1 2 1 1 2 1 12 ٚٓعيَٕٓى ٕٚ ٚى ٚع ّٚ يى يّ يٍ يٕ ظو ظِ ظٌ ظٔ ظو ْى ّْ ٍْ ْٕ ْى ْع ٚى ّٚ ٍٚ ْى َى َّ ٔو ِٔ ٌٔ 2 1 2 1 1 1 3 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 23 ّٙ انًرطت ذٙ ّ خ ذة ذط يٙ ّ و ية يط يد نٙ ّ ل نة نط ند نى ا٘ ّ ا اب اض اخ او ال ّ٘ تٙ بّ ض٘ ّ ض ضب 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 28 ٌّٕ انًطت تٕ بّ ضٌ ضٔ ّ ض ضب يٍ يٕ ّ و ية يط نٍ نٕ ّ ل نة نط نى اٌ أ ّ ا اب اض او ال ٌٔ ٌّ ّٔ تٍ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 28 طائطاخ طئ طا اخ ضخ ضا ئد ئا ئط اخ اا اض ائ طد طا طط 2 1 1 1 1 1 1 2 1 1 1 1 1

  of unique bi-grams in the word (A) B = Number of unique bi-grams in the root (B) C = Number of similar unique pairs between the word (A) and the root (B)

  the previous example we obtain: D(w, R 3 ) = 2*3+15*100+0*100 = 1506 D(w, R 5 ) = 2*1+17*100+2*100 = 1902 D(w, R 6 ) = 2*1+17*100+2*100 = 1902

Fig. 1 .

 1 Fig. 1. Correct and wrong results in number of words.

Fig. 2 .

 2 Fig. 2. Calculation of success rate and error rate.

Table 1 .

 1 Corpus used in experiments.

	Corpus	Size of derived	Size of the roots" file Size of the golden
		words" file		roots" file
	Small corpus	50	25	50
	Middle corpus	270	135	270
	Large corpus	1500	450	1500

Table 2 .

 2 An example of morphological forms (gross words).

	Word	Word	Word	Word	Word
	يأذص	أٔايط	تاحس	اخرًاعاخ	يأذص
	يؤاذصج	يؤذًط	تحٕز	اخرًاعٛاخ	يؤاذصج
	يؤاذصٌٔ	يؤايطج	أتحاز	خًٕع	يؤاذصٌٔ
	يؤاذصاخ	يرأيطٌٔ	تاحثٌٕ	خٕايع	يؤاذصاخ
	يؤاظضج	ٚأذًطٌٔ	تاحثاخ	ٚدًعٌٕ	يؤاظضج
	يأكم	ٚأذًطٌ	اترٓال	ٚدًعٍ	يأكم
	أكالخ	أيطْى	يثرٓم	اخرٓاز	أكالخ

Table 3 .

 3 An example of trilateral, quadrilateral, quinquelateral, hexalateral roots.

	Trilateral roots	Quadrilateral roots Quinquelateral	Hexalateral roots
			roots
	ظضع	أكطو	اَطهك	اؼرعًم
	طُع	أعاٌ	اَكؽط	اؼرحؽٍ
	ذدط خًع	أعطٗ ى ّ حط	احرٕٖ الرظس	اؼرعاٌ اذشٕشٍ
	َفط	ّٗ ضت	اذضطّ	ّ ازْاو
	طاض	حاؼة	ّٖ ذحس	احطَدى
	ؼعم	طًأٌ	ذُاظل	ّ الشعط
	طسع	ظنعل	ذسحطج	اطًأٌّ

Table 4 .

 4 Examples of obtained results when segmenting words into bi-grams.

	Word	N-grams

Table 5 .

 5 Extraction of some Arabic words roots using our new algorithm.

	Word	Nearest roots Nb.Common	Distance values	Extracted	Correct
						bi-grams					root	root
	ٚرعهًٌٕ	، عهى ، عانح ، هى ّ ك	3 ، 1 ، 3 ، 2 ، 1	،	2506	،	3202	،	2806	عهى	عهى
	عانى			كًٍ ، عًم ، عهى ، عانح ، ى ّ كه	1 ، 3 ، 3 ، 2		،	، 306	2902 606 ،	، ،	2704 1002	عهى	عهى
				عًم									504
	كاذة		كرة ، الرظس	1 ، 3					306	،	1402	كرة	كرة
	كراذٛة	ذأذأ ، كرة ، الرظس 1 ، 3 ، 1		1402	،	906	،	2002	كرة	كرة
	الرظاز	، الرظس ، لظس	3 ، 10 ، 1		1502	،	420	،	1106	الرظس	الرظس
				عمس
	ٚمظسٌٔ	، الرظس ، لظس	3 ، 3 ، 1		1602	،	1906	،	1206	لظس	لظس
				عمس
	اؼررسو	ذسو ، ذًس ، الرظس 3 ، 2 ، 3		1206	،	1404	،	1906	ذسو	ذسو
	ؼُؽرسضخٓى ، ذسو ، الرظس	1 ، 1 ، 3 ، 1	،	2706	،	3102	،	3802	زضج	زضج
				ْعو ، زضج								3102
	يرصتصب	شتصب ، كرة	1 ، 4					508	،	1002	شتصب	شتصب
	يرألنئ	، ذأذأ ، كًم ، عًم	1 ، 1 ، 1 ، 3	،	1402	،	1302	،	1302	ألأل	ألأل
				ألأل									1006
	ٕ َٓى	ٚٓعي	ْعو ، كًٍ	1 ، 3					2006	،	2042	ْعو	ْعو
	ّٙ انًرطت	الرظس ، عانح ، كهى	1 ، 1 ، 1 ، 1 ، 1	،	3602	،	3202	،	2902	ّٗ ضت	ّٗ ضت
				ّٗ ضت ، عهى ، كرة ،	،6 ، 1	،	2212	،	2902	،	2902
				طاض ،								2902
	ٌّٕ انًطت	، عهى ، عانح ، كهى	1 ، 1 ، 1 ، 1 ، 3	،	2902	،	3202	،	2902	ّٗ ضت	ّٗ ضت
				طاض ، ّٗ ضت ، كًٍ	،1			2902	،	2806	،	2902
	ائطاخ	ط	طاض	، الرظس	3	،	1					6441	،	2102	طاض	طاض

Table 6 .

 6 Obtained results when extracting the words roots.

	Corpus	Nb.Roots Nb.Words	Cor. Results Wr.Results Suc.Rate Err.Rate
	Small	25	50	49	1	98,00	2,00
	Middle	135	270	253	17	94,07	5,93
	Large	450	1500	1358	142	90,53	9,47

Comparison with other algorithms

To show the effectiveness of our proposed algorithm, we concluded our work by establishing a comparison against other known algorithms. For this purpose, we took a sample words list and tried to extract the root of each word using three very known algorithms which are: khodja stemmer, Nidal et al stemmer, and our proposed stemmer, the obtained results are shown in table 7.

In the other hand, we illustrated the obtained results when applying the three above algorithms on the three corpus used in the experimentation, namely: the small corpus, the middle corpus, and the large corpus, and then we summarized the obtained accuracy for each algorithm in table 8.

Table 7. Extraction of some words roots using the three algorithms.

Word

Discussion

From table 7, we see that khodja stemmer algorithm fails sometimes in getting the correct root of the given word and for many words it produced one of two results: [START_REF] Fatma | Rule-based Approach for Arabic Root Extraction: New Rules to Directly Extract Roots of Arabic Words[END_REF] not stemmed (i.e., حٕاؼٛة , يرألنئ , )ؼُؽرسضخٓى completely a new word and sometimes a wrong word that does not exist in Arabic language (i.e., (

). The same thing can be said for Nidal et al algorithm although it"s gives best results than khodja algorithm, but it fails for many words like : (

, حٕاؼٛة( .)َؽٙ، For the same cases, our algorithm gives always the correct root and the failure in our algorithm is very limited.

From Table 8 and figure 3, we can deduce that our proposed algorithm gives the best results for the three used corpus with a very high accuracy. We note here the value 98 % for the small corpus, 94,07 % for the middle corpus, and 90,53 % for the large corpus

Conclusion and Perspectives

In this paper we have studied how we can reduce the size of terms in Arabic text categorization by replacing many words by their common root. In this purpose, we exposed the most known algorithms and techniques in the field, Including morphological algorithms mainly based on the use of morphological rules and grammatical patterns of Arabic, and statistical algorithms which are the newest in the field, and require only simple calculations of distances. We also proposed a new statistical algorithm based on bigrams technique. This algorithm is fast and easy to implement on machine, does not require the removal of affixes nor the use of any morphological rules and grammatical patterns, capable to find all types of roots, i.e., trilateral, quadrilateral, quinquelateral, and hexalateral roots. There is no difference between strong roots and vocalic roots in our new algorithm. We also established a comparison between our proposed algorithm and two other algorithms which are very known in the field, namely: Khodja algorithm, Nidal et al algorithm. The first one fails sometimes in getting the correct root of the given word and for many words it produced one of two results: (1) not stemmed word (2) completely a new word and sometimes a wrong word that does not exist in Arabic. The same thing can be said for second one, although it gives best results than the first, but it fails for many words. For the same cases, our new algorithm gives always the correct root, the failure is very limited, and the obtained success ratio of root extraction is very promising.

In our future work, we plan to apply our new algorithm on corpus of Arabic words with big sizes, to improve the obtained success rate, and to apply it in extracting the root of words in other languages such as English and French.