Ismaïl Biskri
email: ismail.biskri@uqtr.ca

Flexibility in Classification Process

Keywords: Classification, Flexibility, Applicative Systems

A whole classification process is the result of a discovery process that requires constant back and forth between theoretical description of the solution, software implementation, testing and refinement of the theoretical description in the light of the results of experimentation. This process is iterative. It should be, always, under the control of the user according to his subjectivity, his knowledge and the purpose of his analysis. In the last years, several platforms for digging data where classification is the main functionality have emerged. Some of these platforms allow a rapid prototyping and support a re-use of existing "computational modules" from existing "computational tool cases". However, they lack flexibility and sound formal foundations. We propose, in this paper, a formal model with strong logical foundations, based on typed applicative systems. In this model, "computational modules" are considered as operators followed by their operands. A specific processing chain becomes a specific arrangement of a set of modules according to the needs of the user. The model ensures a firm compositionality of this arrangement.

Introduction

Language processing, text processing, social Medias processing, knowledge extraction, applications in education, etc. are a broad field of research including information retrieval, indexation, classification, and information's analysis. As Web is a big source of information, this field can have many implications on several sectors of society. Compared to the quick expansion of data quantity, the evolution of their analysis is too slow and insufficient.

Classification is a major component of many processing chains for language processing, text processing, social Medias processing, knowledge extraction, applications in education, etc. Classification organizes documents, files, data, etc. in such a way that similar documents, files, data, etc. are grouped together. From a computational point of view, classification relies on statistical comparison of contentbased descriptors identified by the user according to his needs and goals.

The whole classification process may be divided in three steps. The first one is the features extraction. Extracted features are used as content -based descriptors. The user decides the nature of these descriptors. He may decide to replace them by other descriptors. Indeed, the main difficulty is not extracting the features, over the years, many libraries have been developed and shared to facilitate the features extraction; but it is choosing the right features.

The second step is the classification process itself. Different classifiers such as neural network based classifier can be used to perform this step. One of the limitations of these classifiers is that they are opaque and it's not always easy to evaluate the contribution of a specific descriptor and a specific classifier in the classification result.

The third step is the interpretation by the user of the classification results. A user can use different tools to make an enlightened reading of the results. The choice of the tool strongly depends on the purpose of the analysis, or even the knowledge and subjectivity of the user.

Features extraction, classifiers and interpretation tools have an impact on the classification process. Different combinations of features, classifiers and interpretation tools should continue to be explored in order to improve the computer assisted classification process or in some cases better customize the classification process to specific application areas.

In the literature about classification, data-mining, text-mining, and Big-Data, many projects aim to allow the creation of complex processing chains. ALADIN [START_REF] Seffah | ALADIN : Un atelier orienté objet pour l'analyse et la lecture de Textes assistée par ordinaleur[END_REF], D2K/T2K [START_REF] Downie | A revolutionary approach to humanities computing: tools development and the D2K datamining framework[END_REF], RapidMiner [START_REF] Mierswa | YALE: Rapid Prototyping for Complex Data Mining Tasks[END_REF], Knime [START_REF] Warr | Integration, analysis and collaboration[END_REF] and WEKA [START_REF] Witten | Data Mining: Practical Machine Learning Tools and Techniques[END_REF] use processing chains for language and data engineering, Gate [START_REF] Cunningham | GATE: A Framework and Graphical Development Environment for Robust NLP Tools and Applications[END_REF] use it for linguistic analysis. The processing chains are widely used, but the solutions previously mentioned suffer from limitations. They are strongly bonded to their specific platforms and programming languages. To take the best advantage of them, the user needs to have knowledge about the developed software and sometimes about programming language. The user is not, always expert, in programming language. A big challenge in these fields is the multitude of disciplines needed to go further. So, experts of different domains need to work together.

In our paper, we propose a formal model based on typed applicative systems, in which the validation of the construction of a processing chain is performed by a logical calculation on types. Typed application systems are widely used in the field of automatic processing of natural language with the current of categorial grammars [1; 2; 3] and applicative grammars [START_REF] Shaumyan | Two Paradigms of Linguistics: The Semiotic Versus Non.Semiotic Paradigm[END_REF]. They allowed the construction of parsers for many languages like French, Arabic, English, Dutch, Korean, etc. They also allowed logical representations for linguistic or cognitive operators.

Before presenting the formal model itself, we will first introduce, in the next section, typed applicative systems and combinatory logic.

Combinatory Logic and Typed Applicative Systems

Combinatory logic was introduced by Moses Schönfinkel in 1924, and extended by Curry and Feys [6;[START_REF] Hindley | Lambda.calculus and Combinators, an Introduction[END_REF]. This logic uses abstract operators called combinators in order to eliminate the need of the variables and, thus, to avoid variable telescoping.

Combinators act as functions over argument within a typed operator-operand structure. Their action is expressed by a unique rule called β-reduction rule; which defines the equivalence between the logical expression without combinator and the one with combinator. Elementary combinators can be associated to others to create complex combinators. In our paper, we use only the four elementary combinators B, C, S, W, whose notations and β-reductions are shown in the table below.

Combinator Role β-Reduction B Composition B x y z → x (y z) C Permutation C x z y → x y z S Distributive composition S x y u → x u (y u) W Duplication W x y → x y y
The composition combinator B combines two operators x and y together and constructs the complex operator B x y that acts on an operand z, z being the operand of y and the result of the application of y to z being the operand of x.

The permutation combinator C uses an operator x in order to build the complex operator C x that acts on the same two operands as x but in reverse order.

The composition combinator S distributes an operand u to two operators x and y. The duplication combinator W takes an operator x that acts on the same operand y twice and constructs the complex operator Wx that acts on this operand only once.

We can combine elementary combinators together to construct more complex combinators. For example, we could have an expression such as "B S C x y z u v". Its global action is determined by the successive application of its elementary combinators (first B secondly S and finally C).

B S C x y z u v S (C x) y z u v (C x) z (y z) u v C x z (y z) u v x (y z) z u v
The resulting expression, without combinators, is called a normal form. This form, according to Church-Rosser theorem, is unique.

Two other forms of complex combinators exist : the power and the distance of a combinator. Let χ be a combinator.

The power of a combinator, noted by χ n , represents the number n of times its action must be applied. It is defined recursively by χ¹ = χ and χ n = B χ χ n-1 . For example, the action of the expression C² x y z would be:

C 2 x y z B C C x y z C (C x) y z (C x) z y C x z y x y z
The distance of a combinator, noted by χ n , represent the number n of steps its action is postponed. It is defined by χ 0 = χ and χ n = B n χ. For example, the action of the expression C 2 x y z u v will be:

W 2 x y z u v B 2 W x y z u v B B B W x y z u v B (B W) x y z u v (B W) (x y) z u v B W (x y) z u v W ((x y) z) u v ((x y) z) u u v x y z u u v
Applicative systems assign to each operator and to each operand an applicative type to express how they work. The set of applicative types is recursively defined as follows:

1. Basic types are types.

2. If x and y are types, Fxy is a type. Fxy is the applicative type of an operator whose operand is of type x and the result of its application to its operand is of type y.

An operator function having two x typed operand and returning a y typed result will be of type FxFxy. This can also be read as: an operator taking an x type operand and giving back an operator taking an x type operand and returning an y type result.

Formal Model

In our model, we aim at explicitly defining the set of operations contained in programs. In the applicative modeling, these operations are translated into functional terms represented by typed modules. This translation allows a more formal definition of an operation in terms of its internal structure and relation with other operations. Also, this translation allows for a better specification of the processing chain design. Typed modules are organized in series and as such they form processing chains. A typed module acts then like a mathematical function that takes several arguments, process them and return an output. Here, we are not interested in the internal programming of the modules but only in their representation as functions and how they are organized to create processing chains.

A processing chain must be syntactically correct. Its semantic interpretation depends, mainly, on the user's point of view regarding the expected analysis.

Our model tends to answer two questions:  Given a set of typed modules, what are the allowable arrangements that lead to coherent processing chains?

 Given a coherent processing chain, how can we automate as much as possible its assessment?

Fig. 1. Module schematisation

To do that, we must, first, assign to each module an applicative type. For example the type Fxy is assigned the module M1 in (Fig. 1) since its input is of type x and its output is of type y. We note the module M1 of type Fxy as follow: [M1 : Fxy].

As a general notation, [M1 : Fx 1 ...Fx n y] is a module M1 with n inputs of different types, input in place "i" is of type x i , and an output of type y, [M2 : (Fx) n y] is a module M2 with n inputs of type x and an output of type y.

A processing chain is the representation of the order of application of several modules on their inputs. To be valid, the type of an input must be the same as the output linked to it (Fig. 2). It also can be seen as a module itself as it has inputs and output (Fig. 3). --------------------------[Y : y] COMPOSITION RULE --------------------------------B [B M2 M1 : Fxz]

Fig. 2. Valid chain of two modules in series

[M1 : Fxy] + [M2 : Fyz] -
DISTRIBUTIVE COMPOSITION RULE [M1 : Fxy] + [M2 : FxFyz] ----------------------------------S [S M2 M1 : Fxy] PERMUTATION RULE [M1 : FxFyz] ----------------------C [C M1 : FyFxz]

DUPLICATION RULE [M1 : FxFxy] ---------------------W [W M1 : Fxy]

The above rules are only the core set of the model. Extended rules are provided so they can be applied to any number of inputs. ---------------------------------------------------------------------------C -------------------W

COMPOSITION RULE

[M1 : Fx 1 ...Fx n y] + [M2 : Fyz] ------------------------------------B n [B n M2 M1 : Fx 1 ...Fx n z] PERMUTATION RULE [M1 : Fx 1 ...Fx n y] -
n [W n M1 : Fxy]
The composition rule is used when two modules are in series (as in Fig. 2). If M1 has n inputs, the power of the B combinator is n. For these rules, the inputs number of M2 can be more than one. The duplication rule transforms a module with n identical inputs to a module with only one input. It can be applied only if the chain give the same value to each of its inputs (Fig. 4). The permutation rule allows to change the order of inputs. It takes the input at position m and moves it to the position p, with p<m. It's used to reorganize input to make the other rules applicable. In this section, we will show how the rules given in the previous section are applied and illustrate the reduction of a processing chain with an example. Let us consider the linear connection of two modules (Fig. 2). The module [M1 : FxFxy] applies on two identical inputs of type x and yield an output of type y. The module [M2 : Fyz] applies on this output to yield an output of type z. This chain is expressed by the expression: The permutation rule allows reorganising the inputs of a module to apply another rule. Let M be a module with four inputs of types x, y, z and x and an output of type t : [M : FxFyFzFxt]. Let X be the value given to the first and fourth inputs (Fig. 5-a). If the fourth was in second position, we could apply the duplication rule to M. So, we want to move the fourth input to second position. The permutation rule returns the complex module [C 1 (C 2 M) : FxFxFyFzt] (Fig. 5-b). on this new module, the duplication rule can be applied to get a complex module [W (C 1 (C 2 M)) : FxFyFzt] (fig 5 -c). Let us now give the analysis of a somewhat complex processing chain (Fig. 6). This chain is a combination of five modules.

B (C (C 2 (B 2 (S (B M5 M2) M3) M1))) M4 Z X Y C (C 2 (B 2 (S (B M5 M2) M3) M1)) (M4 Z) X Y C 2 (B 2 (S (B M5 M2) M3) M1) X (M4 Z) Y B 2 (S (B M5 M2) M3) M1 X Y (M4 Z) S (B M5 M2) M3 (M1 X Y) (M4 Z) B M5 M2 (M1 X Y) (M3 (M1 X Y)) (M4 Z) M5 (M2 (M1 X Y)) (M3 (M1 X Y)) (M4 Z)
This normal form expresses the order of application of modules on their inputs (X, Y and Z).

Even if this work is currently at the theoretical stage, a first prototype of the model was implemented. The rules are implemented in a F# library and a testing software in C# language.

The prototype has been tested on 40 different processing chains containing 15 syntactically incorrect chains and 25 correct chains. The results are shown in table 1. We are, currently, working on the implementation of modules with effective functionalities in the domain of classification.

Conclusion

The need for flexible, adaptable, consistent and easy-to-use tools and platforms is essential. But, many challenges are yet to be solved. The user stays in center of its experience and he can change his mind. The flexibility of the tools is really important when it happens. Without it, user needs to, constantly, go back and forth between theoretical description of the solution, software implementation, testing and refinement of the theoretical description in light of experimentation results. The model that we propose allows rapid prototyping and support a maximal re-use and composition of existing modules. It also ensures a firm compositionality of the different modules in the different processing chains. Moreover, our approach provides a general framework in which users would be able to build multiple language and text analysis processes according to their own objectives.

Fig. 3 .

 3 Fig. 3. Processing chain as a new module

n [C p- 1 (

 1 C p (…(C m-2 M1))) : Fx 1 ...Fx p-1 Fx m Fx p ...Fx m-1 Fx m+1 ...Fx n y] DUPLICATION RULE [M1 : (Fx) n y] -

Fig. 4 .

 4 Fig. 4. Module getting a single value in its three inputs

  [M1 : FxFxy] + [M2 : Fyz]. The composition rule can be applied and returns the complex module [B 2 M2 M1 : FxFxy]. If the type of M1 output and M2 output where not the same, we could not have applied the composition rule. So, the application of the rules is a proof of syntactic correctness of the chain. The module [B 2 M2 M1 : FxFxy] can be reduced a second time with the duplication rule. It is reduced to the complex module [W (B 2 M2 M1) : Fxy].

Fig. 5 .

 5 Fig. 5. inputs reorganisation



  M1 of type FxFyz  M2 of type Fzx  M3 of type Fzx  M4 of type Fzy  M5 of type FxFxFyt To reduce this chain, we will start with the last module and process from left to right. So we start with [M5 : FxFxFyt]. His first input takes the output of [M2 : Fzx]. The composition rule gives a new complex module [B M5 M2 : FzFxFyt] (Fig. 7). This new module and [M3 : Fzx] can be reduced with the distributive composition rule to get the module [S (B M5 M2) M3 : FzFyt]. (Fig. 8). The first input of this module can be reduced with the composition rule to get a new module [B 2 (S (B M5 M2) M3) M1 : FxFyFyt]. (Fig. 9) To reduce this module with [M4 : Fzy] we want to use the composition rule. But to apply it, M4 output must be the first input of our module. We use the permutation rule to reorganise the inputs and got a new module [C (C 2 (B 2 (S (B M5 M2) M3) M1)) : FyFxFyt] (Fig. 10). Finally, we can apply the combination rule that returns the module [B (C (C 2 (B 2 (S (B M5 M2) M3) M1))) M4 : FzFxFyt]. As we have only one module, and no other rule can be applied, the processing chain is reduced.

Fig. 6 .Fig. 7 .Fig. 8 .step 2 Fig. 9 .Fig. 10 .Fig. 11 -

 678291011 Fig.6. A complex processing chain

Table 1 .

 1 Results of reduction

		REDUCED	NOT REDUCED
	VALID CHAIN	25	0
	INVALID CHAIN	0	15


Mohammed Mahseur
email: mahseur.mohammed@gmail.com

Abdelmadjid Boukra
email: aboukra@usthb.dzyassine.meraihi@yahoo.fr

Yassine Meraihi

Improved Quantum Chaotic Animal Migration Optimization algorithm for QoS multicast routing problem

Keywords: Animal Migration Optimization, Quantum Representation, Chaotic Maps, Quality of Service (QoS), Multicast routing

In recent years, we are witnessing the spread of many and various modern real-time applications implemented on computer networks such as video conferencing, distance education, online games, and video streaming. These applications require the high quality of different network resources such as bandwidth, delay, jitter, and packet loss rate. In this paper, we propose an improved quantum chaotic animal migration optimization algorithm to solve the multicast routing problem(Multi-Constrained Least Cost MCLC). We used a quantum representation of the solutions that allow the use of the original AMO version without discretization, as well as improving AMO by introducing chaotic map to determine the random numbers. These two contributions improve the diversification and intensification of the algorithm. The simulation results show that our proposed algorithm has a good scalability and efficiency compared with other existing algorithms in the literature.

Introduction

The evolution of computer networks has been accompanied by the emergence of a new range of real-time multimedia network applications that exchange and share data, images, videos, sound files, etc. These applications require multicast transmissions with strict QoS guarantees as essential capabilities, where the same data streams are delivered from the source node to a selected group of nodes simultaneously. The most important requirements of QoS parameters are cost, delay, delay jitter, bandwidth, and packet loss rate. Therefore, it is essential to use the different network resources in a rational way. The QoS multicast routing problem (MCLC) is a nonlinear combinatorial optimization problem for transmission in the areas of networks. It is proved to be NP-Hard [START_REF] Wang | Quality-of-service routing for supporting multimedia applications. Selected Areas in Communications[END_REF] and has recently attracted an increasing attention from researchers. Its main objective consists in finding the optimal multicast routing tree by minimizing the cost under multiple constraints such as delay, delay-jitter, bandwidth, and packet loss rate. It was approached by various algorithms based on meta-heuristics such as Genetic Algorithm (GA), Tabu Search (TS), Particle Swarm Optimization (PSO), Bat Algorithm (BA), and Optimization Based on Biogeography (BBO).

Hwang et al. [START_REF] Hwang | Multicast routing based on genetic algorithms[END_REF] proposed a GA-based algorithm for multicast routing problem without constraints, the optimization of the multicast tree is achieved through a serial path selection, by crossover and mutation operation. Results showed that the proposed algorithm is able to find a better solution than the RSR algorithm. Haghighat et al. [START_REF] Haghighat | GA-based heuristic algorithms for QoS based multicast routing[END_REF] proposed a novel QoS-based multicast routing algorithm based on the GA to find a multicast tree with least cost satisfying the constraints of delay and bandwidth. Simulation results showed that the proposed algorithm outperformed other algorithms.

Youssef H et al. [START_REF] Youssef | QoS-driven multicast tree generation using tabu search[END_REF] present a TS algorithm to build the near optimal solution, their algorithm starts with an initial feasible solution and builds a tree of the sink for each destination with the shortest path of Dijkstra algorithm, in each iteration the algorithm refines the tree at a lower cost. Experimental results showed that TS is able to find better solutions that other reported multicast algorithms. Ghaboosi and Haghighat [START_REF] Ghaboosi | A path relinking approach for delay-constrained least-cost multicast routing problem[END_REF] used the PRA, which is a progressive method. They construct solutions by the combination of elements of a couple of solutions chosen randomly (an initial solution and a guide one) using systematic and deterministic rules.

Liu et al. [START_REF] Liu | QoS multicast routing based on particle swarm optimization[END_REF] proposed a PSO algorithm to solve the QoS multicast routing problem by means of serial path selection to obtain a feasible multicast tree by exchanging paths in the vector. Experimental results indicated that the proposed algorithm can converge to the optimal or near the optimal solution with lower computational cost. It also appeared that PSO outperformed GA on QoS the tested multicast routing problem. Qu et al. [START_REF] Qu | Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems[END_REF] developed a PSO algorithm based on the jump (JPSO), such that each particle moves either based on its position, either based on a chosen attractor, once the particle reaches his new position, it performs a local search to improve its position.

Mahseur and Boukra [START_REF] Mahseur | Using bio-inspired approaches to improve the quality of service in a multicast routing[END_REF] proposed two approaches to solve the MCLC Problem, the first one is based on BBO and the second on BA, the results of their experimentation are encouraging in comparison with other existing algorithms. Meraihi et al. [START_REF] Meraihi | An Improved Chaotic Binary Bat Algorithm for QoS Multicast Routing[END_REF] proposed an improved chaotic binary bat algorithm to solve the QoS multicast routing problem. Simulation results reveal the efficiency of the proposed algorithm compared with some other existing algorithms in the literature.

In this paper, we have applied a new meta-heuristic called Animal Migration Optimization (AMO) to resolve the problem of MCLC. To improve diversification and intensification, we have used the quantum representation of solutions and integrated the chaotic maps in some characteristic equations of AMO.

The rest of the paper is organized as follows. section 2 presents the mathematical multicast routing problem formulation followed by Section 3 which describes the AMO algorithm. In Section 4, we propose the improved quantum chaotic animal migration optimization algorithm. In section 5 we study three scenarios, we investigate the performance of our algorithm in first one, the convergence and scalability in the second one, and the robustness and speed in the last one. Finally section 6 summarizes the findings.

Multicast Routing Problem formulation

Throughout this work, the communication network is modeled as a directed weighted graph G = (V, E) where V denotes the set of nodes, and E denotes the set of the edges representing wireless links between nodes. |V | = n is the number of nodes and |E| = l is the number of links in the network. Each link e = (i, j) ∈ E that connects node i with node j is associated with link cost C(e) : E → R + , link delay D(e) : E → R + ,link delay jitter J(e) : E → R + , link bandwidth B(e) : E → R + , and link packet loss rate P L(e) : E → R + , where R + is the set of all nonnegative real numbers. We assume that s ∈ V represents the source node and M ⊆ {V -{s}} represents a set of multicast destination nodes such that s and M construct a multicast tree T (s, M ).

The multicast tree has the following parameters [START_REF] Sun | QoS multicast routing using a quantumbehaved particle swarm optimization algorithm[END_REF], [START_REF] Abdel-Kader | An improved discrete PSO with GA operators for efficient QoS-multicast routing[END_REF]: The total cost of the multicast tree T (s, M ), denoted by Cost(T (s, M )), is defined as the sum of the costs of all links in that tree. It can be given by:

Cost(T (s, M )) = e∈T (s,M ) C(e) (1)
The total delay of the path P T (s, m), denoted by Delay(P T (s, m)), is simply the sum of the delays of all links along the path:

Delay(P T (s, m)) = e∈P T (s,m) D(e) (2)
Where P T (s, m) denotes the routing path of the multicast tree T (s, M ) that connects the source node s with the destination node m ∈ M (clearly

P T (s, m) is a subset of T (s, M )).
The delay jitter of the path P T (s, m) , denoted by Jitter(P T (s, m)), is defined as the sum of the delays-jitter of all links along the path and can be given by:

Jitter(P T (s, m)) = e∈P T (s,m) J(e) (3)
The bandwidth of the path P T (s, m), denoted by B(P T (s, m)), is defined as the minimum required bandwidth at any link along P T (s, m):

B(P T (s, m)) = min e∈P T (s,m) (B(e)) (4)
The Packet loss rate of the path from source node s to destination node m, denoted by P L(P T (s, m)) is given by:

P L(P T (s, m)) = 1 - e∈P T (s,m) (1 -P L(e)) (5)
The MCLC problem can be formulated as follows:

M inimize Cost(T (s, M )) (6)
Subject to:

Delay(P T (s, m)) ≤ D max (7)
Jitter(P T (s, m)) ≤ J max (8) M in(B(P T (s, m))) ≥ B min (9)
P L(P T (s, m)) ≤ P L max [START_REF] Sun | QoS multicast routing using a quantumbehaved particle swarm optimization algorithm[END_REF] 3 Animal Migration Optimization AMO Animal Migration Optimization Algorithm (AMO), developed by Li et al. in 2014 [START_REF] Li | Animal migration optimization: an optimization algorithm inspired by animal migration behavior[END_REF], is a novel interesting nature-inspired metaheuristic optimization algorithm used to solve various optimization problems. This optimization algorithm is inspired by the migration behavior of animals in groups to ensure their survival. These animals can be found in several families such as mammals, birds, fish, reptiles, amphibians, insects, and crustaceans. These families are leaving their current habitats and migrating to other geographically distant habitats that can provide better living conditions. There are several reasons for migration such as food shortage, drought, reproduction, and seasonal change. For simplicity, AMO uses the following two idealized rules [START_REF] Li | Animal migration optimization: an optimization algorithm inspired by animal migration behavior[END_REF]:

1. The leading animal with high position quality will be kept for the next generation; 2. The number of animals in the group is fixed, and the animal leaving the group will be replaced by a new individual with a probability P a.

AMO algorithm works based on two processes. In the first process, the algorithm simulates how the groups of animals move from the current position to the new position. In the second process, the algorithm simulates how some animals leave the group and some join the group during the migration. Each individual i changes its current position during the iteration G + 1 by changing the components of its vector X i according to one of the neighbors according to the following formula:

X i,G+1 = X i,G + δ.(X neighborhood,G -X i,G ) (11)
Where δ is a parameter defined according to the problem treated, and the neighboring individual is randomly selected from the neighbors. Remember that the topology and the size of the population are fixed. An animal is asked to leave the group with probability Pa and replaced by another obtained by the following formula:

X i,G+1 = X r1,G + rand.(X best,G -X i,G ) + rand.(X r2,G -X i,G ) (12)
4 IQCAMO for QoS multicast routing

Improved Quantum Chaotic AMO algorithm

In order to improve the effectiveness and the robustness of the AMO algorithm, we have proposed two modification methods. The first modification method introduces the quantum representation of the solutions to allow the use of the original AMO version without discretization.

The second modification method adopts the chaotic map to overcome the problem of choosing the right value of the two random numbers used in equation 12.

There are several chaotic maps like logistic map, circle map, tent map, piecewise map, iterative map, Chebyshev map, sine map, sinusoidal map etc. Logistic map is the most representative chaotic map with simple operations and well dynamic randomness [START_REF] Kanso | Logistic chaotic maps for binary numbers generations[END_REF]. So this chaotic behavior map is adopted in this paper to generate the two random numbers at each iteration. The random number generated by a logistic map is given by:

CM t+1 = aCM t (1 -CM t ), t = 0, 1, 2 . . . (13)
Where CM t is the chaotic map value at the t-th iteration, it is in [0, 1]. Here a is a control parameter and 0 < a < 4. The chaotic system is very sensitive to the initial values, to make the logistic map in a complete chaos, we adopt the parameter a = 4 and CM t does not belong to {0, 0.25, 0.5, 0.75, 1} otherwise the logistic equation does not show chaotic behavior [START_REF] Dos Santos Coelho | Differential evolution optimization combined with chaotic sequences for image contrast enhancement[END_REF]. In our experiments, we take CM 0 = 0.7 . Algorithm 1 describes the pseudo-code of the IQCAMO algorithm for multicast routing problem.

Representation of the solution

The solution representation of the i-th Qbit individual is defined by a real vector Q t i = (q t i1 , q t i2 , . . . , q t im ), j = 1, 2 . . . , m, where m represents the length of the vector which is equal to the total number of links in the network. The Qbit vector Qi is defined as follows:

  α t i1 α t i2 . . . α t im β t i1 β t i2 . . . β t im   ( 14
)
The binary representation of the solution which is a multicast tree is a binary vector X t i = (x t i1 , x t i2 , . . . , x t im ), j = 1, 2 . . . , m, where x t ij = 0 or 1, which indicates whether the corresponding link i is selected or not to construct the multicast tree. The binary vector X t i is defined as follows:

x ij =    1; if rand(0, 1) > |α t ij | 2 (i is selected to construct the multicast tree). 0; otherwise . ( 15
)

Initial population

Before the generation of the initial population, we delete all link with bandwidths less than the bandwidth constraint B min . The initial population is produced by the Depth First Search (DFS) method, we take the source node and connect it randomly to one of its successors and compare it with the set of destination nodes M , if it is a destination so it is a valid path, otherwise we redo the same approach until obtaining a solution in natural form. If the path is saturated (blocked road), we restart the operation from the source node. Each connection of a node, a check is made to avoid the construction of loops.

Simulation results

The performances of the proposed approach are studied and compared with the implemented algorithms: GA [START_REF] Hwang | Multicast routing based on genetic algorithms[END_REF] and JPSO [START_REF] Qu | Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems[END_REF]. The three algorithms were implemented using Visual C++ on a PC Intel Core 2 Duo 2.0 GHz. The nodes are randomly distributed in a rectangle of 4000km x 2400km, links are generated according to the topology model Waxman [START_REF] Waxman | Routing of multipoint connections. Selected Areas in Communications[END_REF]. In this model, the existence of a link between two nodes u and v depends on a probability p(u, v) given by the following formula: P (u, v) = B exp(-l(u, v)/AL) Where: l(u, v) represents the Euclidean distance between two nodes u and v. L is the maximum distance between any two points in the network. B is a parameter that controls the number of links in the network. A is a parameter that controls the number of short links in the network. A and B are set to 0.8 and 0.7 respectively like in [START_REF] Qu | Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems[END_REF]. The cost, delay, packet loss rate and bandwidth of the links are taken randomly in the interval [START_REF] Wang | Quality-of-service routing for supporting multimedia applications. Selected Areas in Communications[END_REF]100], [1ms, 30], [0.0001, 0.01] and [2Mbps, 10] respectively. The thresholds constraints ∆, ξ, and δ are set to 120ms, 60ms and 0.05 respectively. The bandwidth required by the flow to send β is randomly generated in the interval [2Mbps, 10] [START_REF] Waxman | Routing of multipoint connections. Selected Areas in Communications[END_REF]. The source and destination nodes are selected randomly from the network. We perform tree scenarios:

1. In the first scenario,and in order to evaluate the performance of each algorithm, we evaluate the cost of the multicast tree while varying the number of nodes in the network with 10% of destinations; 2. In the second scenario, we observe the cost of the best solution for each algorithm according to the number of iterations and the size of network to study the convergence and scalability of algorithms;

3. In the third scenario, we have varied the number of destination nodes to evaluate for each algorithm the cost of the optimal solution and the convergence time in order to study the robustness and speed of algorithms.

Results of the first scenario

In the first scenario, we varied the size of the network from 20 to 120 nodes. Each time, the source node and the destinations (10% of the nodes) are chosen randomly. The results are represented in Figure 1.

Figure 1 shows the multicast tree cost of GA, JPSO, and IQCAMO, according to the network size. First, we observe that the multicast tree cost increases with the increase of the network size. Second, we observe that the multicast tree cost generated by IQCAMO is less than the other multicast tree costs.

Results of the second scenario

In the second scenario, we have study three kinds of networks: small network(50 nodes), medium network (200 nodes), and large network (500 nodes) with 10% destinations, then we evaluated the optimal solution of each algorithm during the iterations. The results are represented in Figures: 2, 3, and4.

Figure 2 shows solutions obtained by the three algorithms in a small network, we observe that the solutions proposed by JPSO are the best.

We observe in Figure 3 and Figure 4 that our algorithm has the best speed of convergence; this is provided by the use of quantum principles.

Results of the third scenario

In the third test, we study the cost of multicast routing and the convergence time by varying the number of destination nodes. The results are represented in Figure 5 and Figure 6.

Figure 5 shows the multicast tree cost of GA, JPSO, and IQCAMO while varying the number of destination nodes. We observe that IQCAMO gives the best routing cost. This is due to the use of the quantum representation and the chaotic maps which are more efficient in exploring large search space. Figure 6 shows that the convergence time increases while increasing the number of destination nodes and we observe that IQCAMO gives the best convergence time. Thus, the proposed approach is more robust and fast. This is due to the use of the quantum mechanism and the chaotic maps which are more efficient in exploring large search space.

Friedman test

In order to study the difference between the three algorithms in terms of multicast tree cost, we use the Friedman test. The results are given in table 1. We observe that the significance level is less than 5%, so the null hypothesis H 0 is rejected which implies that the Friedman test is significant. Furthermore, IQCAMO is classed as the best algorithm in terms of multicast tree cost.

Conclusion

In this paper, we have applied a new meta-heuristic called AMO on multicast routing problem which is an NP-hard problem. we used a quantum representation of the solutions that allowed us to use the original AMO version without discretization, as well as improving AMO by introducing chaotic Maps into the calculation of some equations. these two contributions improve the diversification and intensification of the algorithm. we performed an optimization on the graph representing the network and another on the initial population which accelerated the exploration of the search space. To evaluate the performance of our solution we tested three comparative scenarios with two other algorithms: in the first scenario, we compared the multicast tree cost with varying the network size and using 10% as destinations. We notice that IQCAMO produces the minimum cost, In the second scenario, we study the convergence of the three algorithms; we observe that IQCAMO is the best. In the last scenario, we evaluate the cost and the convergence time while varying the size of the set of destination nodes. We found that our approach has an ability to deliver the best results. The experimental results lead to conclude that our algorithm increases the overall research capacity. As future work, we intend to investigate the multi-objective aspect of the problem. Indeed, to have a better resolution of the problem, other objectives must be considered, like delay, bandwidth, jitter etc.

Fig. 1 .

 1 Fig. 1. The cost of the multicast tree while varying the number of nodes in the network.

Fig. 2 .

 2 Fig. 2. Convergence of algorithms in a small network .

Fig. 3 .

 3 Fig. 3. Convergence of algorithms in a medium network .

Fig. 4 .

 4 Fig. 4. Convergence of algorithms in large network.

Fig. 5 .

 5 Fig. 5. The cost of the multicast tree while varying the number of destination nodes.

Fig. 6 .

 6 Fig. 6. The convergence time while varying the number of destination nodes.

Table 1 .

 1 Friedman test.

	Friedman test
	Algo	Mean Rank
	GA	2.70
	JPSO	2.01
	IQCAMO	1.30
	Test statistics
	N	64
	Chi-Square 73.495
	df	2
	Asymp.sig	.000

for i = 1 to N P do 7: δ = Li/Lmax 8:

for j = 1 to |E| do 9:

Qi,j,G+1 = Qi,j,G + δ.(Q neighborhood of i,j,G -Qi,j,G) 10:

if Qi,j,G+1 < 0 then 11:

Qi,j,G+1 = 0 12:

end if 13:

if Qi,j,G+1 > Π/2 then 14:

Qi,j,G+1 = Π/2 15:

end if 16:

end for 17: end for 18:

for i = 1 to N P do 19:

Repair infeasible solutions 20:

Evaluate Fitness(Qi,G+1) 21:

if F itness(Qi,G+1) < F itness(Qi,G) then 22:

Qi = Qi,G+1 23:

end if 24: end for 25:

for i = 1 to N P do 26:

Calculate P ai 27:

if rand < P ai then 28:

for j = 1 to |E| do 29:

Qi,j,G+1 = Qr1,j,G + CM 1(G + 1).(Q best,j,G -Qi,jG) + CM 2(G + 1).(Qr2,j,G -Qi,j,G) 30:

if Qi,j,G+1 < 0 then 31:

Qi,j,G+1 = 0 32: end if 33:

if Qi,j,G+1 > Π/2 then 34:

Qi,j,G+1


Tayeb Kenaza

Abdelkarim Machou

Abdelghani Dekkiche

Implementing a Semantic Approach for Events Correlation in SIEM Systems

Keywords: SEIM, Monitoring, Intrusion detection, Alert correlation, Description logic, Rules based reasoning, Ontology, OWL

Efficient reasoning in intrusion detection need to manipulate different information provided by several analyzers in order to build a reliable overview of the underlying monitored system trough a central security information and event management system (SIEM). SIEM provides many functions to take benefit of collected data, such as Normalization, Aggregation, Alerting, Archiving, Forensic analysis, Dashboards, etc. The most relevant function is Correlation, when we can get a precise and quick picture about threats and attacks in real time. Since information provided by SIEM is in general structured and can be given in XML, we propose in this paper to use an ontological representation based on Description Logics (DLs) which is a powerful tool for knowledge representation and reasoning. Indeed, Ontology provides a comprehensive environment to represent any kind of information in intrusion detection. Moreover, basing on DLs and rules, Ontology is able to ensure a decidable reasoning. Basing on the proposed ontology, an alert correlation prototype is implemented and two attack scenarios are carried out to show the usefulness of the semantic approach.

Introduction

Information systems security requires the deployment of a rigorous security policy with several security mechanisms and tools. We generally start with prevention systems such as authentication where the goal is to prove the identity of users, access control where the goal is to define rights of users on data, and firewalls where the role is to control the access to the information system towards the outside world.

However, these mechanisms are not sufficient to fully protect systems against malicious attacks. Indeed, computer systems often exhibit vulnerabilities, which allow attackers to bypass preventive mechanisms. In addition, many security tools focus on the protection against external attacks, while attacks can be also internal. For example, client side attacks are a very common nowadays. Therefore, intrusion detection is necessary as a second layer of security after deploying prevention systems. Unfortunately, Intrusion Detection is still imperfect for two reasons. First, intrusion detection systems (IDSs) generate a very large number of low-level alerts, where most of them are false positive; i.e, alerts generated in the absence of attacks. And second, IDSs suffer from false negative which is the absence of alerts in the presence of attacks.

In order to overcome these problems, a promising approach is the so-called cooperative intrusion detection [START_REF] Zhou | A survey of coordinated attacks and collaborative intrusion detection[END_REF][START_REF] Elshoush | Alert correlation in collaborative intelligent intrusion detection systems a survey[END_REF], which allows various intrusion detection tools to cooperate. In addition to IDS, other analyzers can be considered such as network and vulnerability scanners in order to correlate alerts by considering contextual information. This can be done by including for example topology and cartography. In fact, nowadays all security tools have to cooperate using a central security information and event management system (SIEM). A SIEM provide many functions to take benefit of the collected data, such as Normalization, Aggregation, Alerting, Archiving, Forensic analysis, Dashboards, etc. The most relevant function is Correlation, when we can get a precise and quick picture about the threats and attacks in real time. However, most of proprietary SIEM use its own data representation and its own correlation techniques which are not always favorable to share knowledge and to do custom reasoning.

In such situation, the use of common and extensible formalism to describe information in intrusion detection is a major concern. This information is generally structured and encoded in XML. For example, this is the case of alerts in IDMEF (for Intrusion Detection Message Exchange Format) and TAXII (Trusted Automated eXchange of Indicator Information) as well as the vulnerabilities in OVAL (Open Vulnerability and Assessment Language) and STIX (Structured Threat Information eXpression). However, information encoded here in XML is limited to a syntactic representation basing in different taxonomies. Consequently, in the absence of a semantic approach correlating this information is a fastidious task. Indeed, it is more interesting to move from taxonomies to ontology specification languages [START_REF] Staab | Handbook on ontologies[END_REF][START_REF] Motik | Owl 2 web ontology language: Structural specification and functional-style syntax[END_REF], which are able to simultaneously serve as recognition, reporting and correlation languages.

Several existing knowledge representation models can be used in SIEM such as [START_REF] Morin | A logic-based model to support alert correlation in intrusion detection[END_REF][START_REF] Abdoli | Ontology-based distributed intrusion detection system[END_REF][START_REF] Azevedo | An autonomic ontology-based multiagent system for intrusion detection in computing environments[END_REF][START_REF] More | A knowledge-based approach to intrusion detection modeling[END_REF]. In this paper, our contribution can be seen as an enhancement of existing representations by regrouping a large amount of information into a single ontology. This will offer a comprehensive and extensible knowledge representation which can be used in many event correlation systems.

On an other hand, given that tools used in SIEM are not totally reliable, usually conflicts appear between them [START_REF] Tombini | A serial combination of anomaly and misuse idses applied to http traffic[END_REF][START_REF] Yahi | Conflicts handling in cooperative intrusion detection: a description logic approach[END_REF]. For example, one can easily see that IDSs are not fully reliable since they generate many false positives and false negatives. Therefore, it is very important to resolve these conflicts in order to exploit the cooperation. Hence, our second contribution is an ontological reasoning approach to correlate alerts in order to reduce the amount of alerts, especially false positives.

The rest of this paper is organized as follows. In Section 2 we briefly recall intrusion detection and some works of knowledge representation proposed in the context of intrusion detection, and then we present the proposed ontology. Section 3 presents an architecture of an alert correlation system based on DLs reasoning. In section 4 experiments are conducted and results are discussed. In section 5, some related works are briefly discussed. Section 6 concludes this paper.

Related works

The automatic correlation of information from different security systems has been a vivid topic of research for over a decade [START_REF] Zhou | A survey of coordinated attacks and collaborative intrusion detection[END_REF][START_REF] Elshoush | Alert correlation in collaborative intelligent intrusion detection systems a survey[END_REF]. Numerous approaches have been developed for correlating alerts and other log entries to strength the power of intrusion detection systems. Here, we briefly discuss only related works regarding the use of ontology in computer security. Ontology can be used in many field in SIEM, such as to analyze user behavior and system activities, or to identify known attack patterns, or also to analysis abnormal behavior and activity of both systems and users. Notice that semantic approaches have many advantages over existing approaches, mainly two aspects: the formal and extensible knowledge representation capability and the decidable reasoning.

Using ontology in computer security is relatively new. The first research work was done by Jeffrey Undercoffer et al. [START_REF] Undercoffer | A target-centric ontology for intrusion detection[END_REF]. They produced an ontology that specify a model of computer attack. Their ontology is based on attack strategies which is categorized according to targeted system components, tools of attacks, consequences of attacks, and location of attackers. They present their model as a target-centric ontology. Since the work of Jeffrey many other ontologies was proposed. In [START_REF] Ju | Ovm: an ontology for vulnerability management[END_REF], Wang et al. propose an Ontology for Vulnerability Management (OVM) which contains several concepts about vulnerabilities, affected products, consequences and countermeasures, etc. Authors have used their own implementation of their ontology without referring to any languages. In [START_REF] Azevedo | An autonomic ontology-based multiagent system for intrusion detection in computing environments[END_REF], Azevedo et al. propose a domain-ontology with more generic and abstract concepts in the field of computer security, serving as the basis for the construction of other specific security-domain-ontologies called CoreSec. In [START_REF] Gao | Ontology-based model of network and computer attacks for security assessment[END_REF], Jian-bo et al. provide an ontology-based attack model which is used to assess the information system security from attack angle. The proposed ontology consists of five dimensions, which include attack impact, attack vector, attack target, vulnerability and defense.

More recently, many semantic description methods for the security policy has been proposed. In [START_REF] Tang | Semantic description and verification of security policy based on ontology[END_REF], an ontology-based method is presented to solve the problem of the semantic description and verification of a security policy. Onto-ACM (ontology-based access control model), is a semantic analysis model proposed by Chang Choi et al. [START_REF] Choi | Ontology-based access control model for security policy reasoning in cloud computing[END_REF] to address the difference in the permitted access control between service providers and users. More over, in [START_REF] Wang | Using ontologies to perform threat analysis and develop defensive strategies for mobile security[END_REF] ontologies are used to perform threat analysis and develop defensive strategies for mobile security. Autors has proposed on ontology-based approach that can identify an attack profile in accordance with structural signature of mobile viruses, and also overcome the uncertainty regarding the probability of an attack being successful, thanks to semantic reasoning.

Ontological based specification and reasoning for Alert Correlation

Knowledge Representation in Intrusion Detection

In front of an intrusion detection environment characterized by a very low detection rate, a high rate of false alerts, and a poor granularity of the information provided by alerts, a huge effort has been made by the intrusion detection community for the standardization of threats and attacks representation.

The resulted data formalisms (e.g. IDMEF, TAXII, STIX, etc.) has provided a workspace for open communication between security tools and has been largely used in many alert correlation systems [START_REF] Elshoush | Alert correlation in collaborative intelligent intrusion detection systems a survey[END_REF][START_REF] Ali Mirheidari | Alert correlation algorithms: A survey and taxonomy[END_REF].

Despite their different approaches, alert correlation systems have to share knowledge about attacks and the context in which they occur. However, many security tools do not care about how they represent their knowledge and how they use it. We think that having a coherent and formal model to represent knowledge is important for any correlation system. M2D2 is among the most important work in this area, it is a relational model that regroup essential information used in correlation, such as alerts, events, nodes, softwares, etc. In 2009, this model was revised by adding new concepts and by regrouping concepts into classes, this new model is called M4D4 [START_REF] Morin | A logic-based model to support alert correlation in intrusion detection[END_REF]. In a recent work [START_REF] Sadighian | Semantic-based context-aware alert fusion for distributed intrusion detection systems[END_REF] proposed by Sadighian et al, authors have designed a set of comprehensive and extensible ontologies, and have implemented fusion and detection algorithms based on OWL-DL and SQWRL in order to allow reducing false positives.

The Proposed Ontology

Strassner defines the ontology as follows : "An ontology is a formal, explicit specification of a shared, machine-readable vocabulary and meanings, in the form of various entities and relationships between them, to describe knowledge about the contents of one or more related subject domains throughout the life cycle of its existence [START_REF] Strassner | Knowledge engineering using ontologies[END_REF]. This meaning of ontology is used mostly in the context of knowledge sharing.

IDMEF and M4D4 are among the most important work in terms of knowledge representation in the domain of intrusion detection. However, IDMEF does not contain enough information because it describes just alerts, and M4D4 is proposed in the context of network intrusion detection including contextual information (cartography and topology) and the description of vulnerabilities.

In this section, we propose an ontological conceptualization that combines the representation of IDMEF, M4D4, TAXII and other information sources such as OVAL, STIX and NVD.Generally, we can divide knowledge in intrusion detection into 5 groups [START_REF] Morin | A logic-based model to support alert correlation in intrusion detection[END_REF] : Analyzers, Events and alerts, Attacks and Vulnerabilities, Contextual information, and Users and Attackers. Figure 1 shows the main concepts and relations of the proposed ontology, baptized "ONTO-SIEM".

Ontology based Event Correlation System

The use ONTO-SIEM is very suitable for event correlation within a SIEM, when many tools have to cooperate and to exchange information. Indeed, we developed a prototype of alert correlation system to show the importance and usefulness of this ontology. The architecture of our system consists of two essential modules : the conversion module that puts reported alerts into the ontology, as well as contextual information (topology and cartography), and the correlation module that allows reasoning about the constructed ontology. Figure 2 summarizes the architecture of the correlation system.

In order to use an ontology within an application, it must be specified in a formal representation. Indeed, a variety of languages exists that are used to represent conceptual models, with varying expressiveness, ease of use and computational complexity. We used OWL, which is a recommendation of The World Wide Web Consortium (W3C), widely used in web semantic. OWL is based on Description Logics. Description Logics are known for their expressiveness and their clearly defined semantics that allow a decidable reasoning. In this work, we build our ontology using the API Jena (http://jena.apache.org/), and the reasoning is provided by Pellet (http://clarkparsia.com/pellet/) which is a full OWL-DL reasoner.

Populating the Ontology

To populate our ontology we need to use several tools. Information about hosts and the network topology are given using Nmap (http://nmap.org/). This tool can provide many information such as running hosts and their operating systems, servers listening in these hosts with their corresponding version, and many further information. Information about the vulnerabilities of systems and applications are given using Nessus (http://www.tenable.com/products/nessus/). Information about attacks are given in real time by IDS/IPS, in our system we used Snort (http://www.snort.org/) with a set of VRT and community rules. Notice that it is also possible to insert directly information into ONTO-SIEM by security operators, namely add information about equipments, systems and applications.

Reasoning with the Ontology

Reasoning is important in ontology because it allows to ensure the quality of ontology. Indeed, through the use of a reasoner, it is possible to test whether concepts are non-contradictory, and also to derive implicit relations.

Filtering Events : In Table 1 and 2, we present some rules that can be used to filtering pertinent and not pertinent events. Most of theses rules are reused from the Pasagrada framework [START_REF] Sadighian | Semantic-based context-aware alert fusion for distributed intrusion detection systems[END_REF]. Notice that if an event is not classified as pertinent this does not means it is not pertinent. To decide so, the event must satisfy at least one rule from Table 2. Alert(?a) ∧ N ode(?h) ∧ Sof tware(?sof ) ∧ V ulnerability(?v1) ∧ V ulnerability(?v1) ∧ Classif ication(?cl) ∧ P rocess(?p) ∧ Conf iguration(?conf ) ∧ hasT arget(?a, ?h) ∧ hasClass(?a, ?cl) ∧ Hosts(?h, ?p) ∧ Execute(?p, ?sof ) ∧ T ake -part -of (?sof, ?conf ) ∧ Af f ects(?v1, ?conf ) ∧ Ref ers -to(?cl, ?v2) ∧ equivalentto(?v1, v2?) → sqwrl : select(?a)

Rule 1 selects events generated by analyzers that can actually monitors the target. For example, an IDS can only detect events that occur in the network to which it is connected. This can be explicitly provided by the relation monitors or infered, for example for NIDS, as follows.

monitors ≡ hosted -in ∧ connected ∧ netN odes (1)
Rules 2 and 4 select events based on the vulnerability of the OS and the Application, respectively. Some tools such as vulnerability scanners can confirm if an OS or an application is vulnerable or not to a given vulnerability. Obviously, this concern only known vulnerabilities, not zero-day vulnerabilities. Rules 4 and 6 are similar to rules 3 and 4, they just consider the equivalence between vulnerabilities reported by several organisms with different names. These tow rules deal with the case when different analyzers (IDS and scanners) refer to the same vulnerability with different names or references. Alert(?a) ∧ N ode(?h) ∧ Analyser(?an) ∧ hasT arget(?a, ?h) ∧ T rigers(?an, ?a) ∧ N otM onitors(?an, ?h) → sqwrl : select(?a) Rule-7 (based vulnerability)

Alert(?a) ∧ N ode(?h) ∧ V ulnerability(?v) ∧ Classif ication(?cl) ∧ hasClass(?a, ?cl) ∧ hasT arget(?a, ?h) ∧ IsN otV ulnerable(?h, ?v) → sqwrl : select(?a)

Rule 6 is the inverse of rule 1, it selects events reported by tools that does not actually monitor the target of the attack. Rules 7 selects events reported for target that is not actually vulnerable to the referred vulnerability. This concern both OS and Software vulnerabilities. The question now is haw to get such information, because traditionally scanners only report affected hosts not protected onces. For instance we admit that such information is explicitly given by the relation IsN otV ulnerable.

Aggregating Events : Here we consider only pertinent event for which we try to group events together in order to generate meta-event. A meta-event represent a summarizing of a single malicious activity that causes multiple elementary events. We distinguish tow types, Host based meta-event and Network-based meta-event. In this latter we can distinguish three sub-classes [START_REF] Sadighian | Semantic-based context-aware alert fusion for distributed intrusion detection systems[END_REF], within certain time interval.

1. One-to-One (Rule-8). This can be an attack attempted by a single attacker against a single target, for example a SQL injection. 2. One-to-Many (Rule-9). This can be an attack attempted several time by a single attacker against many targets, for example a network or vulnerabilities scan. 3. May-to-One (Rule-10). This can be an attack attempted by several attackers against a single target, for example a DDoS. M essage(?meg) ∧ N ode(?h1) ∧ N ode(?h2) ∧ hasSource(?meg, ?h1) ∧ hasT arget(?meg, ?h2)∧generated-at(?meg, ?t)∧biggerT han(?t, ?t1)∧ lessT han(?t, ?t2) → sqwrl : select(?meg) Rule-9 (many to one) M essage(?meg) ∧ N ode(?h1) ∧ N ode(?h2) ∧ hasT arget(?meg, ?h1) ∧ generated -at(?meg, ?t) ∧ biggerT han(?t, ?t1) ∧ lessT han(?t, ?t2) → sqwrl : select(?meg) s qwrl : count(?meg) Rule-10 (one to many) M essage(?meg) ∧ N ode(?h1) ∧ N ode(?h2) ∧ hasSource(?meg, ?h1) ∧ generated -at(?meg, ?t) ∧ biggerT han(?t, ?t1) ∧ lessT han(?t, ?t2) → sqwrl : select(?meg) s qwrl : count(?meg)

For host-base meta-event, we consider several event' features to decide to group or not events. These features are Node (N), User (U), Process (P), Service (S), and File (F) [START_REF] Sadighian | Semantic-based context-aware alert fusion for distributed intrusion detection systems[END_REF]. Based on these features and in case of a complete availability of data, we can distinguish two main subclasses.

1. NUP (Rule-11), when many events have the same node, the same user and the same process. 2. NUF (Rule-12), when many events have the same node, the same user and the same file. M essage(?msg) ∧ N ode(?h) ∧ U ser(?u) ∧ F ile(?f ) ∧ Analyser(?an) ∧ hasT arget(?msg, ?h) ∧ Launches(?u, ?f ) ∧ Hosts(?u, ?f ) ∧ M oniters(?an, ?f ) ∧ T rigers(?an, ?msg) ∧ generated -at(?msg, ?t) ∧ biggerT han(?t, ?t1) ∧ lessT han(?t, ?t2) → sqwrl : select(?msg) ∧ sqwrl : count(?msg)

Experimental results

ONTO-SIEM is implemented using Protégé which is a powerful editor supporting OWL-Dl, SWRL and other many reasoners such as HermiT, Pollet, etc. Protégé is powerful thanks to many plugins that can be add to it.

To evaluate the proposed rules we have used UNB-ISCX-2012 [START_REF] Shiravi | Toward developing a systematic approach to generate benchmark datasets for intrusion detection[END_REF] which is an open Intrusion Detection Evaluation dataset. UNB-ISCX-2012 is an interesting benchmark because it provides a real labeled traffic which contains both attacks and normal activities. Moreover, this benchmark provides a complete capture of the traffic with a set of divers and multi-steps attack scenarios. Table 5 gives a summary about the benchmark and its attack scenarios. We tested our approach using 2 scenarios, namely "Infiltrating from inside" and "HTTP DDoS". The first scenario consists to obtain access to a host inside the local network, and then the compromised host is used as a pivot to attack computers which are not accessible via the Internet. The second scenario consists of performing a stealthy, low bandwidth denial of service attack without the need to flood the network (for more details about the testbed architecture and the attack scenarios see [START_REF] Shiravi | Toward developing a systematic approach to generate benchmark datasets for intrusion detection[END_REF]).

Populating ONTO-SIEM

The UNB-ISCX-2012 benchmark provides only the raw traffic collected during 7 days, and an xml file containing labeled attacks with their execution periods, but no thing about topology and the cartography of the testbed, as well as the Vulnerabilities. So, we did a had work to manually extract that information from the benchmark. For instance, in Table 6 we show some of used OSs and Softwares. Vulnerabilities are also manually insert into ONTO-SIEM. The raw traffic are analyzed using Prelude-Snort, and then reported alert are translated from xml to ONTO-SIEM. Prelude is an open SIEM which can easly be connected with many analyzers. Prelude' output are in xml, so it will be very simple to translate them to ONTO-SIEM.

Discussing results

Concerning the first scenario, snort has reported alerts which are translated into ONTO-SIEM using Prelude (https://www.prelude-siem.org/). Correlation process has given results shown in Table 7. The first filtering level has reduced the amount of alerts by 30% (3307 alerts are removed) which are alerts that refer to no existing hosts, while the second filtering level has reduced about 17% (1340 alerts are removed) of the amount of the remainder alerts. Therefore, after this preliminary filtering stage, more than 43% of alerts are reduced. Only 57% of the initial alerts will be concerned by further correlation processing using the ontology. The same discussion is given for the second scenario. Table 8 shows correlation process results. The first filtering level has reduced the amount of alerts by 27.95% (1561 alerts are removed) which are alerts that refer to no existing hosts, while the second filtering level has reduced about 10% (410 alerts are removed) of the remainder alerts. Therefore, after this preliminary filtering stage, more than 36% of alerts are reduced. Only 64% of the initial alerts will be concerned by further correlation processing using the ontology.

CONCLUSION AND FUTURE WORK

We proposed in this paper a domain ontology for a cooperative intrusion detection based on several data sources such as IDMEF, TAXII, STIX, M4D4, OVAL, NVD, etc. This ontology is implemented with OWL which is recommended by W3C since 2004 for the representation of ontologies in the Web Semantic. OWL is based on Description Logics which are a decidable fragment of the first order logic and are well suitable to represent structured information.

We have illustrated the usefulness of this ontology through an application in the context of alert correlation. This application allows automatic translation of alerts generated by IDSs to OWL, as well as contextual information generated by network and vulnerability scanners. Furthermore, a set of rules proposed to be inferred over the constructed ontology, these rules aim mainly to remove not pertinent alerts. This is very important to reduce the amount of alerts by analyzing in priority pertinent alerts. Other actions can be performed in the perspective to complete this work. Indeed, the proposed ontology need to be completed by more concepts and relation to allow a more comprehensive correlation rules, and also by using other reasoning mechanisms provided by OWL-Dl such as the verification of consistency and the satisfiability of concepts.

Fig. 1 .

 1 Fig. 1. Main concepts and relations of ONTO-SIEM

Fig. 2 .

 2 Fig. 2. ONTO-SIEM based alert correlation system architecture.

Table 1 .

 1 Filtering Pertinent Events

	Rule-1 (based	Alert(?a) ∧ N ode(?h) ∧ Analyser(?an) ∧ hasT arget(?a, ?h) ∧
	analyser)		monitors(?an, ?h) ∧ T rigers(?an, ?a) → sqwrl : select(?a)
	Rule-2 (based	Alert(?a) ∧ N ode(?h) ∧ OS(?o) ∧ V ulnerability(?v) ∧
	OS)		Classif ication(?cl) ∧ hasT arget(?a, ?h) ∧ hasClass(?a, ?cl) ∧
			Hosts(?h, ?o) ∧ isvulnerable(?o, ?v) ∧ Ref ers -to(?cl, ?v) → sqwrl :
			select(?a)
	Rule-3 (based	Alert(?a) ∧ N ode(?h) ∧ OS(?o) ∧ V ulnerability(?v1) ∧
	OS	with	V ulnerability(?v2) ∧ Classif ication(?cl) ∧ hasT arget(?a, ?h) ∧
	vulnerability	hasClass(?a, ?cl) ∧ Hosts(?h, ?o) ∧ isvulnerable(?o, ?v1) ∧ Ref ers -
	Equivalence)	to(?cl, ?v2) ∧ equivalent -to(?v1, v2?) → sqwrl : select(?a)
	Rule-4 (based	Alert(?a) ∧ N ode(?h) ∧ Sof tware(?sof ) ∧ V ulnerability(?v) ∧
	application)	Classif ication(?cl) ∧ P rocess(?p) ∧ Conf iguration(?conf ) ∧
			hasT arget(?a, ?h)	∧	hasClass(?a, ?cl)	∧	Hosts(?h, ?p)	∧
			Execute(?p, ?sof ) ∧ T ake -part -of (?sof, ?conf ) ∧
			Af f ects(?v, ?conf ) ∧ Ref ers -to(?cl, ?v) → sqwrl : select(?a)
	Rule-5 (Ap-
	plication with
	vulnerability
	Equivalence)

Table 2 .

 2 Filtring Not Pertinent Events

	Rule-6 (based
	analyzer)

Table 3 .

 3 Network based Events Aggregating

	Rule-8 (one to
	one)

Table 4 .

 4 Host based Events Aggregating

	Rule-11	M essage(?msg) ∧ N ode(?h) ∧ U ser(?u) ∧ P rocess(?p) ∧
	(Node-user-	Analyser(?an) ∧ hasT arget(?msg, ?h) ∧ Launches(?u, ?p) ∧
	process)	Hosts(?u, ?p) ∧ M oniters(?an, ?p) ∧ T rigers(?an, ?msg) ∧ generated -
		at(?msg, ?t) ∧ biggerT han(?t, ?t1) ∧ lessT han(?t, ?t2) → sqwrl :
		select(?msg) ∧ sqwrl : count(?msg)
	Rule-12
	(Node-user-
	file)

Table 5 .

 5 UNB-ISCX benchmark Description

	Day	Scenario Description	Size (GB)
	Friday	Normal activity	16.1
	Saturday Normal activity	4.22
	Sunday	Infiltrating from the inside + normal activity 3,95
	Monday	HTTP DDoS + normal activity	6,85
	Tuesday	DDoS using an IRC Botnet	23,4
	Wednesday Normal activity	17.6
	Thursday Brute Force SSH + normal activity	12.3

Table 6 .

 6 UNB-ISCX benchmark' OS and Softwares

	OS	Softwares
	4 Windows xp SP1, Windows xp SP2,	Acrobat Adobe Reader 8.1, Apache 2.2.9,
	Windows 7, Windows Server 2003, Ubuntu	9, Postfix, Dovecot, IIS 6, MSSQL
	10.04.	Server, OpenSSH 5.3, Vsftp 2.2.2.

Table 7 .

 7 Filtering alerts of scenario 1

	Rules	Not pertinent alerts
	Rule 1	3307/11016	(30.02% of alerts are removed)
	Rule 2 to 5 1340/7709	(17.40% of alerts are removed)

Table 8 .

 8 Filtering alerts of scenario 2

	Rules	Not pertinent alerts
	Rule 1	1561/5584	(27.95% of alerts are removed)
	Rule 2 to 5 410/4023	(10.20% of alerts are removed)


Brahim Sahmadi
email: sahmadi.brahim@univ-medea.dzrekia_rah@yahoo.fr

Dalila Boughaci
email: dboughaci@usthb.dz

Rekia Rahmani

Noura Sissani

A Modified Firefly Algorithm with Support Vector Machine for Medical Data Classification

Keywords: Medical data classification, machine learning, feature selection, binary Firefly algorithm, support vector machine (SVM), cross-validation

Clinical information systems store a large amount of data in medical databases. In the use of medical dataset for diagnosis, the patient's information is selectively collected and interpreted based on previous knowledge for detecting the existence of disorders. Feature selection is important and necessary data pre-processing step in medical data classification process. In this work, we propose a wrapper method for feature subset selection based on a binary version of the Firefly Algorithm combined with the SVM classifier, which tries to reduce the initial size of medical data and to select a set of relevant features for enhance the classification accuracy of SVM. The proposed method is evaluated on some medical dataset and compared with some well-known classifiers. The computational experiments show that the proposed method with optimized SVM parameters provides competitive results and finds high quality solutions.

Introduction

Clinical information systems store a large amount of information in medical databases. So, the manual classification of this information is becoming more and more difficult. Therefore, there is an increasing interest in developing automated evaluation methods to follow up the diseases. Classification is one of the techniques of data mining which involves extracting a general rule or classification procedure from a set of learning examples. Medical data classification refers to learning classification models from medical datasets and aims to improve the quality of health care [START_REF] Almuhaideb | Impact of preprocessing on medical data classification[END_REF].

As medical datasets are generally characterized as having high dimensionality, and many of the feature attributes in a typical medical dataset are collected for reasons other than data classification. Some of the features are redundant while others are irrelevant adding more noise to the dataset, although in medical diagnosis, it is desirable to select the clinical tests that have the least cost and risk and that are significantly important in determining the class of the disease [START_REF] Almuhaideb | Hybrid metaheuristics for medical data classification[END_REF].

Feature selection is important and necessary data pre-processing steps to increase the quality of the feature space. It aims to select a small subset of important (relevant) features from the original full feature set. It can potentially improve the performance of a learning algorithm significantly in terms of the accuracy; increase the learning speed, and simplifying the interpretation of the learnt models [START_REF] Liu | Toward integrating feature selection algorithms for classification and clustering[END_REF][START_REF] Huerta | A hybrid GA/SVM approach for gene selection and classification of microarray data[END_REF]. Feature selection is used in different tasks of learning or data mining, in the fields of image processing, pattern recognition, data analysis in bioinformatics, categorization of texts, etc.

The methods used to evaluate a feature subset in the selection algorithms can be classified into three main approaches: filter methods, wrapper methods and embedded methods. Filter methods perform the evaluation independently of any classification algorithm; they are based on data and attributes [START_REF] Liu | Toward integrating feature selection algorithms for classification and clustering[END_REF]. Wrapper methods use the learning algorithm as an evaluation function. It therefore defines the relevance of the attributes through a prediction of the performance of the final system. Embedded methods combine the exploration process with a learning algorithm. The difference with wrapper methods is that the classifier not only serves to evaluate a candidate sub-set, but also to guide the selection mechanism.

Wrapper approaches conducts a search in the space of candidate subsets of features, and the quality of a candidate subset is evaluated by the performance of the classification algorithm trained on this subset [START_REF] Duval | Advances in metaheuristics for gene selection and classification of microarray data[END_REF]. Several wrapper methods have been proposed for feature selection, among them, the stochastic local search methods and the population based optimization metaheuristic methods, like the Genetic Algorithms (GA), the Memetic Algorithm (MA), Particle Swarm Optimization (PSO), and the Harmony Search Algorithm (HAS) [START_REF] Aboudi | Review on Wrapper Feature Selection Approaches[END_REF].

In this work, we apply a wrapper method based on a binary version of Firefly Algorithm to the feature selection problem in medical data classification, in order to extract an ideally minimal subset of features with strong discriminative power. The proposed approach uses the SVM classifier for evaluating a feature subset.

This paper is organized as follows: first, we briefly outline the main idea of support vector machine methods (SVM) and the Binary Firefly Algorithm in Section 2. In Section 3, we describe the proposed approach for feature selection and classification of medical data. The experimental results are presented and discussed in Section 4. Finally, we conclude this study and discuss possible future work in Section 5.

Background

Support Vector Machines

Support Vector Machines (SVM) are a class of supervised learning algorithms introduced by Vladimir Vapnik [START_REF] Vapnik | The Natural of Statistical Learning theory[END_REF]. The main principle of SVM is the construction of a function f called decision function that for an input vector x matches a value y, y = f (x), where x is the example to classify and y is the class which corresponds to the example input. SVM are originally defined for binary classification problems, and their extension to nonlinear problems is offered introducing the kernel functions. SVM are widely used in statistical learning and has proved effective in many application areas such as image processing, speech processing, bioinformatics, natural language processing, and even data sets of very large dimensions [START_REF] Kecman | Learning and soft computing: support vector machines[END_REF]. SVM classifiers are based on two key ideas: the notion of maximum margin and the concept of kernel function. The first key idea is the concept of maximum margin. We seek the hyperplane that separates the positive examples of negative examples, ensuring that the distance between the separation boundary and the nearest samples (margin) is maximal, they are called support vector. And as it seeks to maximize the margin, we will talk about wide margin separators [START_REF] Burgers | A tutorial on support vector machines for pattern recognition[END_REF].

The second key idea in SVM is the concept of kernel function. This is transforming the data space entries in a space of larger dimension called feature space in which it is likely that there is a dividing line, in order to deal with cases where the data are not linearly separable. Some examples of kernel functions are: -Linear kernel: ( )

-Polynomial kernel: ( ) ( ) , γ > 0.
-RBF kernel: ( )

| |
, γ > 0.

-Sigmoid kernel: ( ) ( )

Where , r and d are kernel parameters. In this study, we utilized the LIBSVM toolset and chose Radial Basis Function (RBF) as the kernel function, and its C and γ parameters are optimized using an iterative search method. Previous studies show that these two parameters play an important role on the success of SVMs [START_REF] Nekkaa | A memetic algorithm with support vector machine for feature selection and classification[END_REF].

Binary Firefly Algorithm

The Firefly algorithm is a recent bio-inspired metaheuristic developed by Xin She Yang in 2008 and it has become an important tool for solving the hardest optimization problems in almost all areas of optimization [START_REF] Yang | Nature-Inspired Metaheuristic Algorithms[END_REF]. The algorithm is based on the principle of attraction between fireflies and simulates the behavior of a swarm of fireflies in nature, which gives it many similarities with other meta-heuristics based on the collective intelligence, such as the PSO (Particle Swarm Optimization) algorithm or the bee colony optimization algorithm. He uses the following three idealized rules:

-All fireflies are unisex, meaning that one firefly is attracted by another, regardless of sex.

-The attractiveness and brightness are proportional, so that for two flashing fireflies, the less bright will move towards the brighter. Attractiveness and brightness decrease with increasing distance. If there is not one firefly brighter than the other, they will place themselves randomly. -The brightness of a firefly is determined by the point of view of the objective function to optimize. For a maximization problem, the luminosity is simply proportional to the value of the objective function.

Since the attractiveness is proportional to the luminosity of the adjacent fireflies, then the variation in the attractiveness β with the distance r is defined by:

β = β 0 e -γr2
(1)

Where β 0 is the attractiveness at r = 0 and γ is the absorption coefficient. The distance r ij between 2 fireflies is determined by the formula [START_REF] Liu | Toward integrating feature selection algorithms for classification and clustering[END_REF].

‖ ‖ √∑( ) (2)
Where is the kth component of the spatial coordinate of the ith firefly and d is the number of dimensions.

The movement of a firefly to another firefly more attractive is calculated by:

( ) ( ) (3)
Where and are the current position of the fireflies and , and is the ith firefly position of the next generation. The second term is due to attraction. The third term introduces randomization, with being the randomization parameter.

The basic steps of the firefly algorithm can be formulated as the pseudo code shown in the Algorithm 1.

The original firefly algorithm is designed for optimization problems with continuous variables. Recently, several binary firefly algorithms were developed to solve discrete problems, such as scheduling, timetabling and combination. Compared with the original firefly algorithm, binary firefly algorithm obeyed similar fundamental principles while redefined distance, attractiveness, or movement of the firefly. In this study, we use a binary firefly algorithm for feature selection with new definitions of distance and movement of a firefly, similar to the approach used in [START_REF] Zhang | Identification of DNA-binding proteins using multi-features fusion and binary firefly optimization algorithm[END_REF].

The Proposed Method for Feature Selection and Classification

The feature selection task is a typical combination problem in essence, with the objective of selecting an optimal combination of features from a given feature space.

Theoretically, for an n-dimensional feature space, there will be possible solutions (NP-hard problem). The use of metaheuristics methods as random selection algorithms, capable of effectively exploring large search spaces, which is usually required in case of feature selection. In this work, a binary firefly algorithm (BFA-SVM) is proposed; where the feature space is explored by a population of fireflies and the SVM classifier is used for evaluating a feature subset. The normalized Hamming distance was used to calculate attractiveness between a pair of fireflies and in order to increase the diversity of fireflies a dynamic mutation operator was introduced. The flowchart of BFA-SVM method is shown in Fig. 1.

Fireflies Representation and Initialization

To represent the subset of selected features, we chose a binary representation of a solution in the multidimensional search space. Every firefly in the binary firefly algorithm represents a subset of the feature space (i.e. a possible solution for feature selection problem) as an N-dimensional binary array: bit values 1 and 0 represent a selected and unselected feature, respectively. The Initial population of fireflies is generated randomly; the bit positions for each firefly are randomly assigned as 1 or 0.

Objective Function

The objective function of the BFA-SVM algorithm when searching for the optimal features subset is to maximize the accuracy rate in classifying the testing dataset. This is equivalent to an optimization problem seeking for a maximum solution. The classification rate ACC is calculated using cross-validation with 10-Folds [START_REF] Han | Data mining concepts and techniques[END_REF]. This measure is calculated by the formula (4):

( ) (4

The attractiveness of fireflies

For two fireflies and , the distance is defined based on the similarity ratio of the two fireflies using the normalized Hamming distance of the two position vectors as follow:

(∑ ) (5)
Where denotes the XOR operation and is the positions dimension. The attractiveness β between a pair of fireflies is calculated using the formula (1).

The movement of fireflies

The original firefly algorithm is designed for optimization problems with continuous variables. For the binarization of continuous metaheuristics, there are two main groups of binarization techniques. The first group of techniques allows working with the continuous metaheuristics without operator modifications and includes steps of binarization of the continuous solution after the original continuous iteration. The second group of techniques is called continuous-binary operator transformation; it redefines the algebra of the search space, thereby reformulating the operators [START_REF] Crawford | Putting Continuous Metaheuristics to Work in Binary Search Spaces[END_REF]. In this work, we use a modification in the movement of a firefly by the reformulation of the formula [START_REF] Liu | Toward integrating feature selection algorithms for classification and clustering[END_REF]. When a firefly moves to another firefly more attractive, every bit in its representation vector will make a decision to change its value or not. Changing a bit in firefly is done in two steps: the β-step (attraction) as indicated in the formula [START_REF] Yang | Nature-Inspired Metaheuristic Algorithms[END_REF], which is regulated by the attractiveness β, and the α-step (mutation) were using the formula [START_REF] Eibe | The WEKA Workbench[END_REF], which is controlled by a parameter α.

{ (6) { (7)
β is the probability of a hetero-bit in the moving firefly changes to the corresponding bit in the brighter firefly (0→1 or 1→0). The parameter α regulates the random moving behavior (mutation) of a bit , and it is calculated in each iteration of the BFA-SVM algorithm by the following formula :

The mutation probability α is high in initial iterations, which makes BFA-SVM focus on exploration. As the number of iteration increases, the mutation probability will decrease, and BFA-SVM will accelerate its converging pace gradually.

Experiments

The proposed BFA-SVM algorithm was implemented on a PC with an Intel Core 2 Duo CPU 2.93 GHz, 4 GB of memory and the Windows 7 operating system. The programs are coded in Java language and we have used the LIBSVM package [START_REF] Chang | LIBSVM: a library for support vector machines[END_REF] as a library for the SVMs.

Dataset

To evaluate the performance of the proposed method, we have used 11 medical datasets obtained from the UCI Machine Learning Repository [START_REF] Lichman | UCI Machine Learning Repository[END_REF]. Table 1 describes the main characteristics of these datasets. The prediction process with the SVMs requires that the dataset must be normalized. The main advantages of such operation are to avoid attributes in greater numeric ranges dominating those in smaller numeric ranges, and to avoid numerical difficulties during the computation step. The range of each feature value is linearly scaled to the range [-1, +1] using the WEKA tools [START_REF] Eibe | The WEKA Workbench[END_REF].

Parameter Settings

The parameter values of the proposed algorithm are fixed by an experimental study. After a series of experiments, the different parameters are fixed empirically. The values of each parameter for the proposed method are given in Table 2.

Numerical Results

Due to the non-deterministic nature of the proposed method, several executions (20) were considered for each dataset. The minimum value, the maximum value, and the average of the accuracy rate of the classification for each dataset are reported. The best results are in bold font. Table 3 gives a comparison between the results (mean of accuracy rate) obtained by the use of SVM classifier with default parameters for RBF kernel function, the use of SVM with optimized parameters given with a grid-search method, and the results obtained with by BFA-SVM with optimized parameters. The best results are obtained with BFA-SVM algorithm for all datasets, confirming that the feature selection and optimization of SVM parameters improves significantly the classification accuracy. In order to evaluate the effectiveness of the proposed algorithm BFA-SVM, a comparison of the experimental results obtained by the method with the results of the works cited in [START_REF] Nekkaa | A memetic algorithm with support vector machine for feature selection and classification[END_REF][START_REF] Nekkaa | Hybrid Harmony Search Combined with Stochastic Local Search for Feature Selection[END_REF] is presented in the Table 4, where gives the average (Mean), the best (Max), the worst (Min) values of the classification accuracy, and the standard deviation (Sd) obtained by different methods. In [START_REF] Nekkaa | Hybrid Harmony Search Combined with Stochastic Local Search for Feature Selection[END_REF], a hybrid search method based on both harmony search algorithm and stochastic local search, combined with a support vector machine (HAS+SVM) is given for feature selection in data classification. And the authors of [START_REF] Nekkaa | A memetic algorithm with support vector machine for feature selection and classification[END_REF] propose a genetic algorithm (GA) and memetic algorithm (MA) with SVM classifier for feature selection and classification.

As shown in Table 4, BFA-SVM algorithm succeeds in finding the best results for almost the checked datasets compared to HAS+SVM, MA+SVM and GA+SVM methods in term of classification accuracy point of view (in 8 datasets among 11, the BFA-SVM algorithm gives the best classification rate average and for the max value of the classification accuracy is reached in 10 datasets among 11). The small standard deviations of the classification accuracies presented show the consistency of the proposed algorithm. This proves the ability of the proposed algorithm as a good classifier in medical data diagnosis.

Conclusion

Health care systems generates vast amount of information and it is accumulated in medical databases, and the manual classification of this data becoming more and more difficult. Therefore, there is an increasing interest in developing automated methods for medical data analysis. In this work we proposed a wrapper method for feature selection and classification of medical dataset based on a Binary firefly algorithm combined with the SVM classifier. The results obtained from tests carried out on several public medical dataset indicate that the proposed BFA-SVM method is competitive with other meta-heuristics (Genetic algorithm, Memetic algorithm and Harmony search algorithm) for the feature selection, and experiments have shown us that the method greatly improves the learning quality and ensures the stability of the generated prediction model. It also reduces the size of the representation space by eliminating noise and redundancy. As a continuation of this work, it would be desirable to work on the reduction of the computation time by proposing a parallel implementation of the proposed method. It is also possible to use the binary firefly algorithm with other classification algorithms such as neural networks and Naïve Bayes.

Fig. 1 .

 1 Fig.1. The flowchart of the proposed binary firefly algorithm for feature selection

  Where Total correct is the number of examples correctly classified by the SVM classifier, and L is the total number of examples. The classification rate indicates whether the candidate subset permits good class discrimination.

	end if;
	end for j;
	end for i;
	6.2. Rank the fireflies and find the current best;
	6.3. Set t ← t+1;
	end while;
	7. Return the global best firefly (i.e. the best solution);

) Algorithm 1. Pseudo code of the Firefly algorithm Inputs : n (number of fireflies), max_iter (maximum number of iterations), α (randomness parameter), γ (absorption coefficient). 1. Define objective function f(x), x = (x 1 , ..., x d ) T ; // d is positions dimension 2. Initialize parameters n, max_iter, α and γ; 3. Initialize a population of fireflies x i (i = 1, 2, ..., n); 4. Calculate the light intensity I i (fitness) for each x i by f(x i ); 5. Set t ← 0; 6. while (t <max_iter) do 6.1. for i = 1 to n // all n fireflies for j = 1 to n // all n fireflies If (I j > I i ) -Move firefly i towards j in all d dimensions; -Attractiveness varies with distance r ij via ; -Evaluate new solutions and update light intensity;

Table 1 .

 1 The dataset description

	(8)

Table 3 .

 3 Comparison between SVM default , SVM and BFA-SVM Optimized

	Dataset	SVM default Mean (%)	SVM Optimized Mean (%)	BFA-SVM Optimized Mean (%)
	Arrhythmia	55.93	71.99	75.84
	Breast cancer	97.01	97.12	97.66
	Colon cancer	80.89	87.34	91.94
	Dermatology	97.95	97.99	99.36
	Diabetes	77.14	77.39	79.23
	Heart-c	82.67	83.12	85.07
	Heart-stat	82.44	83.94	86.56
	Hepatitis	85.06	86.06	92.46
	Liver-disorders	58.41	73.59	75.70
	Lung cancer	73.91	77.50	99.53
	Lymphography	83.04	84.56	89.66

Table 4 .

 4

	Comparison between BFA-SVM Optimized, HAS+SVM, MA+SVM and GA+SVM	BFA-SVM Optimized HSA+SVM MA+SVM GA+SVM	Dataset Mean Max Min Sd (%) (%) (%) (%) Mean (%) Max (%) Min (%) Sd (%) Mean (%) Max (%) Min (%) Sd (%) Mean (%) Max (%) Min (%) Sd (%)	Arrhythmia 75.84 76.77 74.78 0.57 69.15 71.24 66.59 1.28 -----------------	Breast cancer 97.66 97.80 97.51 0.05 97.44 97.65 97.22 0.10 97.44 97.80 97.49 0.20 97.20 97.36 96.63 0.14	Colon cancer 91.94 91.94 91.94 0.00 89.94 90.32 88.71 0.69 ----------------	Dermatology 99.36 100.00 98.91 0.41 100.00 100.00 100.00 0.00 99.86 100.00 98.90 0.02 98.69 98.90 98.63 0.08	Diabetes 79.23 79.56 78.78 0.17 77.79 78.13 77.47 0.17 77.71 78.26 77.34 0.21 77.53 77.99 76.82 0.27	Heart-c 85.07 85.81 84.16 0.48 59.80 61.05 58.41 0.49 57.88 63.38 56.44 1.11 59.30 60.73 58.08 0.63	Heart-stat 86.56 87.04 86.30 0.27 84.64 85.56 83.70 0.57 84.56 86.30 83.70 0.57 84.11 85.18 83.70 0.35	Hepatitis 92.46 93.55 90.97 0.71 99.94 100.00 99.35 0.19 99.66 100.00 98.06 0.45 88.83 90.00 86.45 0.89	Liver-disorders 75.70 76.23 75.36 0.22 72.60 73.33 71.30 0.42 71.75 73.04 70.43 0.58 63.49 64.35 62.60 0.55	Lung cancer 99.53 100.00 96.88 1.14 98.75 100.00 93.75 2.26 99.96 100.00 99.86 0.18 88.22 90.62 87.50 0.62	Lymphography 89.66 91.22 88.51 0.93 49.00 55.41 43.92 3.09 48.73 54.70 46.62 1.82 50.83 52.02 49.32 0.66	81.73 82.97 80.04 0.84 81.95 83.72 80.98 0.57 78.69 79.68 77.75 0.47 Average 88.46 89.08 87.65 0.45	-The

Acknowledgments:

The authors would like to thank the developers of the Library for Support Vector Machines (LIBSVM) and the developers of Waikato Environment for Knowledge Analysis (WEKA) for the provision of the open source code.