Hoa Huu

Nouria Nguyen

Jérôme Harbi

Darmont

An Efficient Fuzzy Clustering-Based Approach for Intrusion Detection

Keywords: classification, fuzzy clustering, intrusion detection, cyber attack

The need to increase accuracy in detecting sophisticated cyber attacks poses a great challenge not only to the research community but also to corporations. So far, many approaches have been proposed to cope with this threat. Among them, data mining has brought on remarkable contributions to the intrusion detection problem. However, the generalization ability of data mining-based methods remains limited, and hence detecting sophisticated attacks remains a tough task. In this thread, we present a novel method based on both clustering and classification for developing an efficient intrusion detection system (IDS). The key idea is to take useful information exploited from fuzzy clustering into account for the process of building an IDS. To this aim, we first present cornerstones to construct additional cluster features for a training set. Then, we come up with an algorithm to generate an IDS based on such cluster features and the original input features. Finally, we experimentally prove that our method outperforms several well-known methods.

Introduction

In recent years, with the dramatically increasing use of network-based services and the vast spectrum of information technology security breaches, more and more organizational information systems are subject to attack by intruders. Among many approaches proposed in the literature to deal with this threat, data mining brings on a noticeable success to the development of high performance intrusion detection systems (IDSs). The preeminence of such an approach lies in its good generalization abilities to correctly classify (or detect) both known and unknown attacks. However, as an inherent essence, the effectiveness of data mining-based IDSs depends heavily upon the quality of IDS datasets. In practice, IDS datasets are often extracted from raw traces in a chaotic system environment, and hence could hold implicit deficiencies, e.g., the existence of noise in class labels due to mistakes in measurement, and the lack of base features. Moreover, due to the sophisticated characteristics of attacks and the diversification of normal events, different data regions could behave differently, i.e., true class labels could seriously be interlaced.

Such factors pose a great difficulty for inducers to identify appropriate decision boundaries from the input space of IDS datasets. In other words, when the input space is not robust enough to discriminate class labels, making further treatments from alternative knowledge sources as new supplemental features is highly desirable. To this aim, one common approach is to transform the input space into a higher dimensional space from which data are more separable. New additional features can be found by either manual ways based on prior knowledge or automatic analysis methods (e.g., principle component analysis). However, in a high dimensional input space, finding new relevant features is a tough task that often requires human analyses, but derived features are sometimes not as good as expected. As a result, in practice, one often applies standard dimensional-transformation methods (e.g., polynomial, radial basic function) to application domains where class discrimination is ambiguous and additional features are hard to be identified. Yet, such methods are greatly affected by input parameters and data distribution, thus not always outputting a high performance classifier. In this vision, it is desirable to find additional features in a less complex way so that general-purpose algorithms such as Decision Trees (DT) or Support Vector Machines (SVM) can learn the data more efficiently.

Such a context motivates us to propose a novel approach that treats fuzzy cluster information as additional features. These features are selectively incorporated into the input space for building an efficient IDS. we experimentally show that our solution approach is considerably superior to several well-known methods.

The remainder of this paper is organized as follows. Section 2 presents the problem formulation of our approach, whereas section 3 describes our solution for generating an IDS. Section 4 shows the experimental results we achieved. Section 5 finally gives a conclusion of the method we propose.

Problem formulation

Clustering aims to organize data into groups (clusters) according to their similarities measured by some concepts. Unlike crisp clustering that crisply assigns each data point to a separate cluster, fuzzy clustering allows each data point to belong to various clusters with different membership degrees (or weights). Fuzzy clusters are expressed by their centers (or centroids) that are simultaneously found in the partitioning process of a fuzzy clustering algorithm. The number of clusters (k) is often inputted as a parameter to a fuzzy clustering algorithm. The nk membership matrix W={w ij  [0,1]} of n data points is found in the fuzzy clustering process. For example, Figure 1 describes the instance space of a training set partitioned into four fuzzy clusters, where membership weights that data point x 1 belongs to clusters '1', '2', '3', and '4' are 0.3, 0.14, 0.16, and 0.4, respectively.

Let us first denote S={X,Y} the original training set of n data points X={x 1 ,…,x n }, where each point x i is an m-dimensional vector (x i1 ,…,x im ) and assigned to a label

y i Y belonging one of the c classes ={ 1 , …, c }. Let B={b i | b i =max(w ij ), j=1…k}
hold the maximum membership weight of each point x i , and Z={z i | z i =argmax j (w ij ), j=1…k } contains the cluster (symbolic) number assigned to each point x i .

For conciseness in describing the approach, we term two column matrices Z and B as two "basic cluster features". In addition, we name the j th column of the membership matrix (W) as P j , and term the columns P 1 , ..., P k as "extended cluster features". We also term the training set added with cluster features {X, Z, B, P 1 , …, P k , Y} as a "manipulated training set". These notations and terminologies are depicted in Figure1. The problem formulation follows: "Given a training set S={X,Y} and an inducer I, the goal is to find a high performance classifier induced by I over the m initial features of S and the supplemental cluster features {Z, B, P 1 , P 2 , …, P k } resulting from a parameterized-by-k fuzzy clustering based on X".

Undoubtedly, fuzzy clustering has a great potential in expressing the latently natural relationships between data points. Here, a question is whether information about fuzzy clusters benefits certain inducing types. Basically, there exist some types of inducers to which fuzzy cluster features are helpful. For example, in the SVM context, the decision boundary often falls into a low density region, but the true boundary might not pass through this region, thus resulting in a poor classifier. However, when supplemented with relevant cluster features, data points in high dimensional spaces can become more uniform and discriminatory, hence avoiding an improper separation across this region. In fact, the crucial factor to the success of SVM lies in a kernel trick that maps the initial input space to a much higher dimensional feature space, where the transformed data are expected to be more separable from a linear hyper-plane function. In order words, while other inducers somewhat find dimensionality a curse, blessing of dimensionality can enable SVM to be more effective. Under such a sense, incorporating relevant cluster features into the input space discernibly benefits SVM inducers.

Another consideration relates to the univariate Decision Tree (DT) setting. Due to its greedy characteristic, the DT inducer examines only one ahead partitioning step for growing child trees, rather than considering deeper partitioning steps that can achieve a better tree. This characteristic can lead to an improper tree-growing termination (e.g., the XOR problem), and thus generate a poor classifier. In this vision, cluster features help the DT inducer to determine splits more properly for tree growing.

Fuzzy Cluster Feature-based Classification

Cluster Feature Generation and Selection

Basically, cluster features can be generated by any fuzzy clustering algorithm. However, for concreteness, we express cluster features with the fuzzy c-means clustering [START_REF] Hoppner | Cluster Analysis[END_REF], which typically solves the minimization problem to the objective function of Formula 1. In a common form, the objective function (Formula 1) reaches to a minimum over W (membership matrix) and V (centroids), by Formulas 2 and 3.

2 11 ( , , ) ( , ) kn obj ij i j ji f X W V w d x v    
, subject to the constrain

1 1 k ij j w    (1) 11 ( ) ( ) nn j ij i ij ii v w x w                 ( 2
)
11 11 22 1 11 ( , ) ( , ) k ij q i j i q w d x v d x v                      ( 3
)
where  is a fuzzy constant and d(x i ,v j ) is the distance from x i (X ) to v j (V)

Fuzzy c-means clustering tries to find the best fit for a fixed value of k, the number of clusters. However, as an essential problem of clustering, determining an appropriate parameter k is a tough task. The most common way to find the reasonable number of clusters is to run the clustering with various values of k  {2,…, k max } and then use a validity measure (e.g., partition coefficient ) to evaluate cluster fitness.

In our approach, however, we need data to be grouped in a way that reveals helpful information for inducers, not for clustering itself, even though the number of clusters might be wrong. In other words, using validity measures to determine the best number of clusters is not reliable enough to derive good cluster features for classifiers. In such a vision, instead of endeavoring to find the best k with validity measures, we use the over-production method to generate several candidate classifiers for different values of k and then evaluate their performance to determine the best one. Evaluating the performance of candidate classifiers can be based either on a validation set or Cross Validation (CV) method [START_REF] Andrew | Preventing Overfitting of Cross-Validation Data[END_REF]. Thus, a proper value of k is simultaneously found in the process of finding a maximum performance classifier from candidate classifiers.

In addition, the use of cluster features should be examined individually for a concrete inducing type. Intuitively, two basic cluster features (Z, B) are benefic enough for DT inducer, instead of including k extended cluster features (P 1 ,…,P k ). By contrast, in the SVM context, it is applicable to employ either only the basic cluster features (Z, B) or all the cluster features (Z, B, P 1 ,…,P k ) for building a classifier. Another solution that can be applied for any inducing type is to employ feature selection techniques (e.g., filter, wrapper) to pick out high merit features from both m initial input features and all (k+2) cluster features. The objective is to apply feature selection techniques on (m+k+2) features to bring about a smaller but more qualitative feature subset than those only on m initial features. Here, note is that feature selection is simultaneously carried out in the process of building candidate classifiers. In a nutshell, formally, there are three possibilities to incorporate cluster features into the initial features

(A 1 , …, A m ), i.e., (A 1 , …, A m , Z, B), (A 1 , …, A m , Z, B, P 1 , …, P k ), or Feature Selection(A 1 , …, A m , Z, B, P 1 , …, P k ).

Algorithm for generating a fuzzy cluster feature-based classifier

Our algorithm for generating a classifier from both initial and cluster features, called CFC, is depicted from Figure 2. Related notations are indicated in Table 1.

V k A k  m matrix of k centroids obtained from clustering X into k clusters. V k* A k*  m matrix of k* centroids, corresponding to C k* . W k An n  k membership matrix of n data points x i  X, corresponding to V k . k B
A column matrix containing the maximum membership weight of each x i  X.

* k C , * k V 1: N orm alize( ) XX   //Normalize continuous features 2: For each k  K do 3: { , } FuzzyC lustering ( , ) kk W V X k   4: { | m ax ( ), 1 ... , 1 ... } k i i ij B b b w i n j k     5: { | arg m ax ( ), 1 ... , 1 ... } k i i j ij Z z z w i n j k    

6:

Case //D is a manipulated training set 7:

T = 1: ()

k k k D X Z B W    

//Initial features & all cluster features 9:

T = 3:

( , ) k k k F X Z B W Y      //Apply a feature selection () k k k D X Z B W     [F]
//Project data by the derived subset 10:

End Case 11: The key idea is that, for each clustering with different number of clusters (kK), the algorithm builds and valuates a candidate classifier from the training set manipulated with a given feature selection type, by q-Fold Cross Validation [START_REF] Andrew | Preventing Overfitting of Cross-Validation Data[END_REF]. The resulting classifier is the one exhibiting maximum performance.

In the training phase, the algorithm first normalizes continuous features (e.g., by a variance-based spread measure) to avoid the dispersion in different ranges (Line 1). Here, it is noticed that the normalized data (X) is merely for clustering purpose, whereas classifiers are built by using the original data (X). In addition, instead of executing clustering with parameter k ranging from 2 to a given kmax value, the algorithm uses a predefined set K={k} to mainly focus on important values of k, which can be recognized by experiment or prior knowledge (Line 2). As mentioned in Section 3.1, there are three cases to incorporate cluster features into the initial features. Hence, for general purpose, the algorithm introduces an input parameter T for specifying the way to employ features for building classifiers (Lines 6-10). Subsequently, the algorithm builds and evaluates one candidate classifier for each clustering (Lines 11, 12). Here, note is that evaluating candidate classifiers is based on the averaged performance of q-fold stratified cross validation from the manipulated training set. Finally, the algorithm determines one best classifier from |K| candidate classifiers, together with a corresponding centroid set (Lines 14, 15).

In the operation phase, for an unlabeled testing instance x, the algorithm first normalizes x in the same way as those applied to the training set. Then, cluster features of x are calculated based on the centroid set

Experiments

Dataset

Our experiments are conducted on the intrusion detection dataset KDD99 [START_REF][END_REF]. This dataset was derived from the DARPA dataset, a format of TCPdump files captured from the simulation of normal and attack activities in the network environment of an air-force base, created by MIT's Lincoln Laboratory. The KDD99 dataset comprises 494,021 training instances and 311,029 testing instances. Due to data volume, the research community mostly uses small subsets of the dataset for evaluating IDS methods. Each instance in the dataset represents a network connection, i.e., a sequence of network packets starting and ending at some well defined times, between which data flows to and from a source IP address to a target IP address under some well defined protocol. Such a connection instance is described by a 41-dimensional feature vector and labeled with respect to five classes: Normal, Probe, DoS (denial of service), R2L (remote to local), and U2R (user to root).

To facilitate experiments without losing generality, we only use a smaller set of the KDD99 dataset for the purpose of evaluating and comparing our method to others. In particular, the training and testing sets used in our experiments are made up of 33,016 instances and 169,687 instances that are selectively extracted from the KDD99 training and testing sets, respectively. The principle for forming such reduced sets is to get all instances in each small group (attack type), but only a limited amount of instances in each large group, from both the KDD99 training and testing sets. More explicitly, for forming the reduced training, we randomly select five percent of each large group Neptune, smurf, and normal, while gathering all instances in the remaining groups from the KDD99 training set. For sampling the reduced testing set, we randomly select 50 percent of each large group Neptune, smurf, and normal, whereas collecting all instances in the remaining groups from the KDD99 testing set. Class distribution of these two reduced sets is shown in Table 2.

Experiment Setup

In our experiments, the predefined set K is set to {2, 3, …, 50}. The convergence criterion (termination tolerance) of fuzzy c-means clustering is set to 10 -6 , whereas the fuzzy degree (exponent  in Formulas 1-3) is set to 3. On the other hand, continuous futures are normalized by max_min value ranges [START_REF] Hoppner | Cluster Analysis[END_REF]. To handle different feature types as well as express different merit contributions of features in the Euclidian space, we calculate distances between data points by the metric proposed in Formula 4.

22 ( , ) ( , )

m i j q q iq jq q d x v G d x v   (4)
where G q is information gain of feature q [5], and

    1, , {sym bolic} ( ) , {unknow n} | |, , {continuous} ( , ) || , , {ordinals}; {ordinals} 1 0
if x v x v or x v x v if x v d x v xv if x v t t                  
The base inducers (I) tested in our method are the C4.5 decision tree [START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF] and the SVM [START_REF] Platt | Fast Training of Support Vector Machines using Sequential Minimal Optimization[END_REF] with polynomial and radial basic function kernels. The feature selection technique () used in this experiment is Correlation-based Feature Subset Evaluation (CfsSubsetEval) with genetic search [START_REF] Hall | Correlation-based Feature Subset Selection for Machine Learning[END_REF]. CfsSubsetEval evaluates the merit of a feature subset by considering the individual predictive ability of each feature along with the degree of redundancy between them. Those subsets that are highly correlated with the class while having low intercorrelation are preferred.

Candidate classifiers are evaluated by an attack type-based stratified cross validation (q=10 folds). The maximum performance classifier is determined based on overall accuracy (i.e., the ratio of the number of correctly classified instances to the total number of instances in the training set).

Experiment Results

The experimental comparison of our method to other well-known methods is featured in Table 3. All the compared classifiers are built from the same training set and tested on the same testing set as described in Section 4.1. Moreover, Figure 4 depicts True Positive Rates (TPRs) and False Positive Rates (FPRs) of classifiers with respect to each class label, whereas Figure 3 portrays average TPRs and FPRs of classifiers.

TPR of a class  c is the ratio of "the number of correctly classified instances in the class  c " to "the total number of instances in the class  c ". FPR of a class  c is the ratio of "the number of instances that do not belong to the class  c but are classified as  c " to "the total number of instances that do not belong to the class  c ".

To have a wider comparative view, we run our algorithm (CFC) with different settings of two parameters (i.e., I: base inducer; T: the way to employ cluster features for building classifiers). The results of such runs are listed in Rows 10-18 of Table 3.

As shown in Figures 3 and4, our method, in general, considerably outperforms the others with respect to TPRs in all five classes and on average. Particularly, CFC classifiers are significantly better than all the others in detecting hard classes (i.e., R2L and U2R). On the other hand, FPRs of CFC classifiers are generally lower than those of the others. Our method also considerably improves the classification ability of base inducers (SVM and DT) in both viewpoints, i.e., applying or not applying feature selection. More concretely, by using the same feature selection technique, the SVM classifier built from the manipulated training set (i.e., CFC(I=SVM,T=3)) is considerably superior to the SVM classifier built from the original training set (i.e., SVM_FS). Similarly, the performance of CFC(I=DT,T=3) is considerably better than that DT_FS. This tells that applying a feature selection technique on the manipulated training set produces a higher qualitative feature subset (including base features and cluster features) than that on the original training set.

Regarding the SVM context, although we further test PSVM (Polynomial SVM) with exponent degrees ranging from 2 to 6, its performance remains worse than CFC(PSVM(degree=2),T={1,2,3}). On average, CFC(PSVM (degree=2),T={1,2,3}) gives a 91.96% TPR (with a 2.2% FPR), whereas PSVM(degree={2,…,6}) produces an 86.84% TPR (with a 3.44% FPR). We also test RSVM (Radial Basic Function SVM) with widths Gamma ranging from 0.1 to 1.0, but its performance still underperforms CFC(RSVM(Gamma=0.1),T={1,2,3}). More precisely, on average, RSVM(Gamma={0.1,0.2,...,1}) produces an 86.72% TPR (with a 3.62% FPR), whereas CFC(RSVM(Gamma=0.1),T={1,2,3}) gives a 91.15% TPR (with a 2.3% FPR). This tells that cluster features benefit SVM in high dimensionality. .07 -DT refers to the C4.5 decision tree inducer [START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF] with established input parameters:

pruning method = pessimistic pruning, confidence=0.2, and Min(#instances per leaf)=6. -Boosting uses the AdaBoost [START_REF] Freund | Experiments with a New Boosting Algorithm[END_REF] with parameters: base inducer=DT, # classifiers=10.

-Bagging uses the Bagging [START_REF] Breiman | Bagging Predictors[END_REF]

Conclusion and Future Work

We propose in this paper a novel method in applying data mining to the intrusion detection problem. The incorporation of cluster features resulting from a fuzzy clustering into the training process is proven to be efficient for enhancing strength of a base classifier. The tactic to achieve a high performance classifier from a training set supplemented with cluster features is addressed. We experimentally show that, as a whole, our method clearly outperforms all the tested methods. Although the experiments are conducted on the KDD99 IDS dataset, the approach we propose can be generally used improve classification in other application domains. However, to be objective in evaluating any data mining solution, our future work will be to test the proposed method on other real datasets. In particular, our current effort is fulfilling a honeypot system for gathering both real intrusion and normal traffic activities. Such real dataset will then be used to evaluate the method we proposed.

Fig. 1 .

 1 Fig. 1. A manipulated training set, resulting from adding cluster features into the input space.

  representing the cluster (symbolic) number of each x i  X.  A horizontal concatenation operator between two matrices. Training phase Input: S={X, Y}: The original training set I: a base inducer K: a predefined integer set representing possible number of clusters : a feature selection technique that returns a specific feature subset T: a type to employ features for building classifiers Output:

Fig. 2 .

 2 Fig. 2. Algorithm CFC.

  [18][19][20]. Finally, the corresponding features are input to classifier * k C for final prediction (Line 21).

Fig. 4 .

 4 Fig. 4. True Positive Rates (%) of classifiers on each class.

Table 1 .

 1 Notations used in Figure2.

	Notation	Description
	C k	A candidate classifier resulting from a clustering with k fuzzy clusters.
	C k*	The best classifier among |K| candidate classifiers.

Table 2 .

 2 Class distribution of the reduced training and testing sets used in experiments.

	Class Training set Testing set	Class	Training set	Testing set
	DoS	22,867	118,807	U2R	52	70
	Probe	4,107	4,166	Normal	4,864	30,297
	R2L	1,126	16,347	Total	33,016	169,687

  , otherw ise,

				iq	jq	iq	jq	iq	jq
			iq	jq	iq	jq
	q	iq	jq
			iq	jq
					iq	jq

87.05 86.27 86.69 86.18 86.49 87.03 86.94 87.02 87.09 90.89 90.18 91.49 91.70 91.24 92.92 90.37 90.96 92.12

	0 100 90 80 70 60 50 40 30 20 10	3.00	5.82	3.20	4.68	3.25	3.27	5.03	3.32	4.61	2.35	2.90	2.16	2.18	2.35	2.08	2.45	2.38	2.07	TPR FPR
			Fig. 3. Average True Positive and False Positive Rates (%) of classifiers

Table 3 .

 3 True Possitive and False Possitive rates (%) of classifiers.

	Classifier		DoS Probe	R2L	U2R Normal Average
	1. Boosting	TP	95.36 82.48	5.51 35.71	99.22	87.05
		FP	0.44	0.46	0.03	0.01	15.01	3.00
	2. Bagging	TP	94.72 80.03	3.46 42.86	98.74	86.27
		FP	4.64	0.41	0.30	0.02	14.18	5.82
	3. NBTree	TP	94.53 83.32	9.54 51.43	98.08	86.69
		FP	0.84	0.62	0.60	0.24	14.22	3.20
	4. DT	TP	94.72 78.68	2.84 51.43	98.77	86.18
		FP	2.85	0.57	0.03	0.10	14.96	4.68
	5. DT_FS	TP	94.26 85.60	7.11 38.57	99.06	86.49
		FP	0.82	0.93	0.26	0.05	14.70	3.25
	6. PSVM	TP	95.14 84.09	9.43 38.57	97.61	87.03
		FP	0.91	0.52	0.24	0.01	14.56	3.27
	7. PSVM_FS	TP	95.44 73.84	8.86 44.29	97.65	86.94
		FP	3.57	0.22	0.29	0.01	14.00	5.03
	8. RSVM	TP	95.11 83.99	9.51 38.57	97.62	87.02
		FP	0.98	0.53	0.23	0.01	14.55	3.32
	9. RSVM_FS	TP	94.98 81.73	9.92 40.00	98.64	87.09
		FP	3.04	0.55	0.17	0.01	13.75	4.61
	10. CFC(I=DT, T=1)	TP	97.69 88.65 25.93 58.57	99.62	90.89
		FP	0.76	0.53	0.02	0.03	10.12	2.35
	11. CFC(I=DT, T=2)	TP	97.46 88.24 21.47 60.00	99.03	90.18
		FP	1.45	0.75	0.03	0.04	10.46	2.90
	12. CFC(I=DT, T=3)	TP	98.30 90.13 28.01 62.86	99.27	91.49
		FP	0.70	0.65	0.03	0.04	9.24	2.16
	13. CFC(I=PSVM, T=1)	TP	98.42 92.49 28.19 68.57	99.57	91.70
		FP	0.81	0.68	0.03	0.03	8.93	2.18
	14. CFC(I=PSVM, T=2)	TP	98.12 92.20 26.27 75.71	99.20	91.24
		FP	0.87	0.48	0.02	0.04	9.70	2.35
	15. CFC(I=PSVM, T=3)	TP	98.83 94.89 37.62 74.29	99.36	92.92
		FP	1.08	0.71	0.03	0.03	7.31	2.08
	16. CFC(I=RSVM, T=1)	TP	97.42 95.06 21.61 68.57	99.23	90.37
		FP	0.76	0.61	0.04	0.02	10.65	2.45
	17. CFC(I=RSVM, T=2)	TP	98.15 91.72 22.51 72.86	99.62	90.96
		FP	0.83	0.58	0.03	0.03	9.96	2.38
	18. CFC(I=RSVM, T=3)	TP	98.22 94.36 33.81 68.57	99.45	92.12
		FP	0.79	0.70	0.02	0.03	8.39	2


Hoa Huu

Nguyen

Nouria Harbi
email: nouria.harbi@univ-lyon2.fr

Jérôme Darmont
email: jerome.darmont@univ-lyon2.fr

An Efficient Local Region and Clustering-Based Ensemble System for Intrusion Detection

Keywords: H.2.8 [Database Application], H.6.5 [Security and Protection] Data mining, ensemble system, intrusion detection, cyber attack

The dramatic proliferation of sophisticated cyber attacks, in conjunction with the ever growing use of Internet-based services and applications, is nowadays becoming a great concern in any organization. Among many efficient security solutions proposed in the literature to deal with this evolving threat, ensemble approaches, a particular family of data mining, have proven very successful in designing high performance intrusion detection systems (IDSs) resting on the mutual combination of multiple classifiers. However, the strength of ensemble systems depends heavily on the methods to generate and combine individual classifiers. In this thread, we propose a novel design method to generate a robust ensemble-based IDS. In our approach, individual classifiers are built using both the input feature space and additional features exploited from k-means clustering. In addition, the ensemble combination is calculated based on the classification ability of classifiers on different local data regions defined in form of k-means clustering. Experimental results prove that our solution is superior to several well-known methods.

INTRODUCTION

Recent years have seen an increasing awareness of the risk of cyber attacks not only coming from outside but also inside organizations. The vast spectrum of security breaches, resulting from the popularity of Internet-based services and applications, makes organizational information systems more and more subject to potential vulnerabilities by intruders. For years, there has been a considerable increase in both types and complexities of attacks that are difficult to detect by using traditional methods (e.g., signature-based techniques). Such security-related concerns have motivated researchers to propose many solutions in the literature to face with this dramatically growing threat. Among them, data mining, by regarding the task of detecting cyber attacks as a classification problem, has brought on a noticeable success in developing intrusion detection systems (IDSs) that efficiently detect various types of cyber attacks ranging from virus infections to phishing scams. The strong point of this approach lies in its good generalization abilities to correctly classify (or detect) both known and unknown attacks. However, different inducers (learning algorithms), or even the same inducer but with different input parameters, often exhibit different pros and cons. Hence, it is not easy to determine a single perfect classifier for the target classification model. An efficient approach to avoid mistaken risks in choosing a single poor or inappropriate classifier is to employ an ensemble system (or multiple classifier system) resting on the mutual combination of multiple classifiers for the classification problem. Ensemble systems exploit the mutual complementary decision boundaries of individual classifiers to improve performance of the whole. However, the effectiveness of ensemble systems heavily depends on the ways to generate and combine individual classifiers. As a whole, individual classifiers are required to have the diversity of decision boundaries. Classifier diversity can be achieved in several ways ranging from the sampling techniques based on instance space (e.g., bagging [START_REF] Breiman | Bagging predictors[END_REF]) and feature space (e.g., random subspace [START_REF] Ho | The random subspace method for constructing decision forests[END_REF]) to the adjustment of inducer parameters and/or paradigm architectures. In addition, the combination of classifier outputs can be grounded under different techniques (e.g., voting, decision template).

In this thread, we propose a novel design approach to generate a high performance ensemble system. In our approach, individual classifiers are trained using both the input feature space and additional features exploited from k-means clustering. The objective is to enhance both strength and diversity of individual classifiers. Furthermore, the selection and combination of ensemble members are calculated according to their classification abilities over different local data regions defined in form of kmeans clustering on a separate validation set. Such a selection and combination method expresses the particular potentials of classifiers more appropriately, and thus produces a higher performance. To this goal, we first present cornerstones to generate and combine individual classifiers. Then, we describe a concrete algorithm for creating a high performance ensemble system. Eventually, we experimentally show that our solution outperforms several well-known methods.

The rest of this paper is organized as follows. Section 2 surveys some main studies related to our work. We present methods to generate ensemble classifiers in Section 3. Section 4 comes up with a technique to combine ensemble classifiers. Section 5 presents the algorithm we propose for creating an ensemble-based IDS. Section 6 portrays the experimental results of our algorithm. The paper finally gives a conclusion of our approach in section 7.

RELATED WORK

Over the past decade, many ensemble design methods have been proposed for various application domains. This section provides a succinct survey of some noticeable studies in ensemble systems for the intrusion detection application.

Giacinto et al. present a multiple classifier system that uses the KDD99 dataset [START_REF]KDD99 data[END_REF] for intrusion detection [START_REF] Giacinto | Intrusion detection in computer networks by a modular ensemble of one-class classifiers[END_REF]. The system consists of various modules, where each is designed for a specific service group. In other words, the instance space of the training set is decomposed with respect to different service groups defined by prior knowledge. For example, the Mail module-based classifier is trained from those instances related to email services, i.e., SMTP, POP2, POP3, NNTP, and IMAP4. This system uses three different learning algorithms (i.e., Parzen, k-means, and v-SVC) to induce ensemble classifiers.

Zhang and Zulkernine construct an ensemble-based IDS using an adaptive random forest algorithm [START_REF] Zhang | Anomaly based network intrusion detection with unsupervised outlier detection[END_REF]. The system produces a forest of classification trees in which each tree is built from a different bootstrap sample. The proposed method only uses the attribute service type (e.g., HTTP) as the target of classification. In misuse detection, a given instance is passed through the trees and then a majority voting mechanism is applied to label this instance. For anomaly detection, the general idea is that if an instance is classified as the one that is different from its own service type, then this instance is regarded as an anomaly. For example, if an HTTP instance is classified as FTP service type, this instance is determined as an anomaly.

Roli and Giacinto propose a multiple classifier system comprising three different groups of classifiers that correspond to three feature subsets predefined by domain knowledge [START_REF] Giacinto | Intrusion detection in computer networks by multiple classifier systems[END_REF]. Specifically, each group of classifiers is trained from one out of the three predefined feature subsets (i.e., intrinsic, traffic, and content feature subsets). A subsequent work of the same authors describes an ensemble architecture including multiple one-class k-means classifiers [START_REF] Giacinto | Network intrusion detection by combining one-class classifiers[END_REF]. Each classifier is built from an instance subspace related to a specific attack type (e.g., Neptune is one of twenty three attack types and belongs to DoS attack class ).

Several studies have also applied Soft Computing algorithms for building ensemble systems for the intrusion detection problem. For example, Abadeh et al. propose a parallel genetic local search algorithm to generate fuzzy rule sets for each class label in the training set [START_REF] Saniee | A parallel genetic local search algorithm for intrusion detection in computer networks[END_REF]. Each of these rule sets is utilized to build a fuzzy classifier. Then, a decision fusion procedure is in charge of determining a class label for a given instance. Likewise, Zainal et al. describe an ensemble model that uses three different learning algorithms to build three classifiers, i.e., Linear Genetic Programming (LGP), Neural Fuzzy Inference, and Random Forest (RF) [START_REF] Zainal | Ensemble of one-class classifiers for network intrusion detection system[END_REF]. Each classifier is trained on the same training set and assigned to a weight calculated based on classifier performance. Finally, apart from other methods that build classifiers from network packet headers, Perdisci et al. introduce a multiple classifier system for anomaly intrusion detection given network packet payloads [START_REF] Perdisci | McPAD: A multiple classifier system for accurate payload based anomaly detection[END_REF]. This system applies a dimensionality reduction algorithm to retrieve several compact representations of payload in different feature spaces. Then, each representation of payload is used to train a one-class SVM classifier.

By contrast to the surveyed methods, our approach, on one hand, exploits supplemental cluster features resulting from k-means clustering for generating the diversity of classifiers. On the other hand, the selection and combination of classifiers are based on dynamic local validation regions with respect to a given testing instance. Intuitively, such factors all together contribute to the performance improvement of the whole system.

GENERATION OF CLUSTER FEATURES AND INDIVIDUAL CLASSIFIERS 3.1 Generation of Cluster Features

Clustering aims to organize data into groups (clusters) according to their similarities measured by some concepts. In metric spaces, similarity is often defined in term of a distance norm measured between data vectors. The potentiality of clustering is to express the latently natural relationships between data points. Clusters are represented by their centers (or centroids) that are found in the partitioning process of a clustering algorithm. In our approach, the k-means clustering algorithm [START_REF] Lloyd | Least square quantization in PCM[END_REF] is used for constructing additional cluster features. These features are then incorporated into the input space for building individual classifiers.

Let us first denote S={X,Y} the original training set of n data points X={x 1 ,…,x n }, where each point x i is an m-dimensional vector (x i1 ,…,x im ) assigned to a label y i Y belonging one of the c classes ={ 1 , …, c }. Let us also denote V the set of k centroids obtained by portioning X into k clusters, using k-means clustering. Let W={w ij | w ij [0,1], i=1…n, j=1…k} be an cluster membership matrix, where w ij is a membership weight that data point x i belongs to cluster j. The matrix W is calculated by Formula 1.

k ij q i j i q w d x v d x v                    ( ( , )
) 1
where k is the number of clusters, and d(x i ,v j ) is the distance from data point x i X to centroid v j V.

Let U={u i | u i =max(w ij ), i=1…n, j=1…k} hold the maximum membership weight of each data point x i , and Z={z i | z i =argmax j (w ij ), i=1…n, j=1…k} contains the cluster (symbolic) number assigned to each data point x i . For conciseness, we term two column matrices Z and U as "cluster features". We also term the training set added with cluster features {X, Z, U, Y} as a "manipulated training set". These notations and terminologies are depicted in Figure 1. Here, cluster features are exploited by partitioning n training data points into four clusters, where x 1 belongs to cluster '4' with a membership weight equal to 0.4, and so on. The manipulated training set is employed to build an individual classifier.

Training set

X Y x 1 y 1 x 2 y 2 … ... x n y n X Z U Y x 1 '4' 0.40 y 1 x 2 '3' 0.45 y 2 … … … ... x n … …

Generation of Individual Classifiers

Obviously, by changing parameter k (the number of clusters in kmeans clustering), we receive different values of cluster features, and hence different classifiers trained by a given inducer. More precisely, we generate an ensemble system of t classifiers induced from the training set manipulated with values k ranging from 2 to t+1. In other words, each individual classifier is trained using both the input feature space and cluster features exploited from kmeans clustering with k{2,3,…,t+1}.

Although it is applicable for any type of inducers, our approach uses Decision Tree (DT) [START_REF]C4.5: Programs for Machine Learning[END_REF] as a base inducer to build individual classifiers for the ensemble. Because the DT inducer is very sensitive to perturbation of the training set, incorporating cluster features into the input space intensifies the diversity of classifiers.

Basically, cluster features exploited from relevant values of k often benefit DT inducer in determining more appropriate splits, thus outputting more efficient classification trees. For example, let us examine an artificial dataset S partially plotted in Figure 2(a). This dataset comprises 12,000 data points, where the squareshaped region contains 3,000 uniformly-distributed data points (plotted) and the outside region includes 9,000 points (not plotted). A decision tree DT * built from both the initial features (A 1 , A 2 ) and cluster features (Z, U, with k=4) of the dataset S is partially depicted in Figure 2(b). Noticeably, for the squareshaped data region, DT * only contains 9 nodes (4 leaves) but attains a 99.41% accuracy, whereas the tree (not shown) generated from the initial features (A 1 , A 2 ) comprises 51 nodes (26 leaves) but only achieves a 97.24% accuracy (10-fold cross valuation).

ENSEMBLE COMBINATION

In the ensemble context, there are two basic approaches, i.e., combination and selection, to classify unforeseen instances. The first approach fuses (or combines) the output of ensemble members in some fashion (e.g., majority voting) to achieve a final decision, whereas the second approach attempts to dynamically select one best ensemble member with respect to some criteria for classifying a given testing instance. Our method follows the first approach, because the second is known to be sensitive to determining an appropriate classifier for a given testing instance.

Typically, ensemble members are often weighted in some manners to further improve the overall performance of the final model.

k k C O A C  R R R (2)
According to the Bayes theorem, the posterior probability estimate that the test instance x belongs to class  j given by the ensemble E is provided in Formula 3. Note that in case the overall accuracy of all classifiers on region R * equals to zero (i.e., OA(

C k | R * )=0,  C k E)
, the posterior probability given by the ensemble E is calculated from Formula 4. By such a formulation, the final prediction of the test instance x is given in Formula 5.

          * * | , | | | , | k jk k k i CE Ei k k j CE O A C P C x Px O A C P C x                  R R (3)       ,| | ,| k jk ki CE Ei kj CE P C x Px P C x                (4)   Label( ) argm ax | , 1... Ei i x P x i c    (5)
With respect to generating local validation regions, the number of cluster prototypes (q) is basically determined by experiment. Usually, the value of parameter q is much smaller than the total number of instances (n) in the validation set. However, if q is too small, the concept of "local region" is no longer applicable and thus the particular ability of each classifier is not exploited either. When q is too large, it takes more time for determining region R * . Moreover, in this case, region R * may comprise only a few instances, which is sensitive to or insufficient for evaluating the classification ability of classifiers. Normally, a reasonable value of q can be found by some prior knowledge such as subclasses (e.g., attack types) or visualization analyses.

ENSEMBLE-BASED IDS

Global Approach

  ,  S X Y Original Training Set (Labelled) R * Label(x)   2 3 1 , ,..., t E C C C     2 2 , , ( ) ( )
C I        X X X V Y ……………………………..   1 1 , , ( ) ( )
t t C I          X X X V Y
(I: a base inducer, C k : a classifier  : a matrix concatenation operator)

Multiple classifier system R 1 R q … Local regions Split S  2 ( , )    X X V,…, 1 ( , ) t 
 Combine 11   ,     S X Y Training Set   ,     S X Y Validation Set 2 3 1 , ..., t     X X X V V V ( k  X V : a set of k centroids)

Centroid sets

Construct cluster features

Extracted/ Constructed/ Transformed Features Preprocess  

Figure 3. Ensemble-based intrusion detection approach

Our approach for generating an ensemble-based IDS is graphically described in Figure 3. Since the task of intrusion detection is regarded as a classification problem, it is first required to have a well-labeled IDS dataset. In general, data can be gathered from various sources such as network traffic packets, operation system audits, system log files (e.g., system calls, shell commands), and application log files. These heterogeneous data are then preprocessed (e.g., data integration, feature extraction, construction, and/or transformation) to establish a well-formed dataset (Step 1). Subsequently, derived data are labeled using domain expert knowledge and/or other supporting techniques (e.g., semi-classification, data visualization) to form an original IDS training set (Step 2). Next, the original training set is split into two separate sets (i.e., a training set and a validation set) by a stratification sampling based on classes or subclasses (Step 3). Subsequently, a multiple classifier system is built using both initial and cluster features by the method described in Section 3 (Steps 4-6). Then, local regions are created by splitting the validation set into q subsets, using k-means clustering (Step 7).

An incoming event to be classified is first preprocessed and transformed into a testing record (instance) as those used for constructing the original training set (Step 8). This unlabeled testing instance is then compared to the prototypes of local regions, by a distance metric, to determine one nearest region R * (Step 9). Because our approach employs the so-called overproduction method to generate a large amount of classifiers (i.e., t classifiers), the next step is to choose b top-ranked (highest performance) classifiers (b  t), evaluated on region R * , for classifying the testing instance (Step 10). Finally, the testing instance is inputted to b top-ranked classifiers for ensemble combination as described in Section 4 ( Step 11).

For calculating distances between data points, we employ the heterogeneous distance metric weighed by information gain [START_REF] Nguyen | An efficient fuzzy clustering-based approach for intrusion detection[END_REF]. Furthermore, to tackle the wide dispersion in different ranges, continuous features are also normalized by min_max scaling [START_REF] Lloyd | Least square quantization in PCM[END_REF].

Algorithm for Generating an Ensemblebased IDS

Our algorithm for generating an ensemble system of classifiers, called CBE, is depicted by the pseudo-code from Figure 4. Builtin functions are shown in Figure 5, whereas related notations are indicated in Table 1. 345Notation Description

Table 1. Notations used in Figures

k D V A set of k centroids, { | 1 ... } k j v j k  D V
, derived by clustering a given dataset D into k clusters.



A function to calculate cluster features for a given dataset D. This function is described in Figure 5.



A vertical concatenation operator between two matrices. E

A set of t classifiers,

  2 3 1 , ,..., t E C C C  
, where each classifier k C is trained from the training set concatenated with cluster features resulting from clustering the training set into k clusters.

V

A set of t centroid sets, , , and

  2 3 1 , ,..., t V      X X X V V V E R A set of q classifier sets,   1...
E V E R Initialization:     , S plit    S S S //      SS where   ,     S X Y is the training set of n instances,   ,     S X Y
is the validation set of n instances

Step1: Generate a multiple classifier system 1: For k=2 to t+1 do [START_REF] Lloyd | Least square quantization in PCM[END_REF] 3:

2:   -M ean s , k kk    X VX // Partition  X into k clusters
  ,, () ()
k k CI        X X X V Y //
  2 3 1 , ,..., t V      X X X V V V
// Store the generated centroid sets

Step2: Create q local validation regions

7:     12 , ,..., C reateLocalR egions , q q   R R R S
(Fig. 5) where , , 1...

{} i i i iq    R X Y
Step3: Evaluate the performance (overall accuracy) of each classifier on each local validation region

8: For each pair   , k k C E V   X V
and each

( 1... ) i iq  R do 9:     | , , () ()
k k i k i i i O A C C        X R X X V Y (Formula 2)
Step4: Determine b top-ranked classifiers (highest performance classifiers evaluated based on OA(C k | R i )) for each region 10: For each For a given unlabelled test instance x, 13: Determine one region

  * 1 ,..., q  R R R
such that its centroid is closest to x.

14: 5) where * is the set of top-ranked classifiers o n R , ( ) is the centroid set used to build ,( )

      Label( ) C om bine , , k k x C E x x     * X R V (Fig.
k k k E b E E CV          * * R R R X X V V
k ij xv      X DV
, using Formula 1 m ax ( ), 1 ... , 1 ... [START_REF] Lloyd | Least square quantization in PCM[END_REF] Compute ij w , ()

i ij d u w j k i n    arg m ax ( ), 1... , 1... i ij d j z w j k i n    Return   ( , ) 1... | i i d z u i n  End Function Function   C reateLocalR egions , q  S //   = , : Validation set    S X Y   -M eans , k kq    X VX //Partition  X into q clusters
k ij xv       X XV
, using Formula 1 arg m ax ( ), 1 ... , 1 ...

| i i ij j l l w j q i n         L Split  S into q regions   { , } i i i    R X Y according to L, (i=1..q) Return   { , } 1... | i i i iq    R X Y End function Function     Ĉ om bine , k C E x  * R // x is a unlabeled testing instance concatenated with cluster features If   * | k O A C R == 0, k C  E * R then Compute   | , 1... , Ei P x i c   using Formula 4.
Else Compute

  | , 1... , Ei P x i c   using Formula 3.
  ˆLabel( ) argm ax | , 1... Then, it overproduces a system of t classifiers; each built from both the original features and the cluster features resulting from k-means clustering (Lines 1-5). The algorithm also stores the generated centroid sets that are later used to construct cluster features for validation and testing data points (Line 6). Then, it creates q local regions by partitioning the validation set into q clusters (Line 7). Subsequently, it evaluates the performance (overall accuracy) of each classifier on each region (Lines 8, 9). Here, cluster features of local regions are calculated based on the corresponding centroid sets exploited from the training set. Finally, the algorithm chooses b top-ranked (highest performance) classifiers for each local region (Lines 10-12).

In the operation phase, for an unlabeled testing instance x, the algorithm first determines one local region R * whose centroid is closest to x (Line 13). Then, it uses b top-ranked classifiers on this region for ensemble combination to produce a final prediction for the test instance (Line 14). Note that cluster features of the testing instance (x) are calculated based on those centroid sets employed to build b top-ranked classifiers.

EXPERIMENTS

Dataset

Our experiments are conducted on the intrusion detection dataset KDD99 [START_REF]KDD99 data[END_REF]. Although the dataset has been criticized by the IDS community mainly because it is unrepresentative of a real-life network scenario [START_REF] Vigna | An analysis of the 1999 Darpa/Lincoln laboratory evaluation data for network anomaly detection[END_REF], so far it is still the only intrusion detection evaluation benchmark for research purposes. The KDD99 dataset comprises 494,021 training instances and 311,029 testing instances. Due to data volume, the research community mostly uses small subsets of the dataset for evaluating IDS methods. Each instance in the dataset represents a network connection, i.e., a sequence of network packets starting and ending at some well defined times, between which data flows to and from a source IP address to a target IP address. Such a connection instance is described by a 41-dimensional feature vector and labeled with respect to 5 classes: Normal, Probe, DoS (denial of service), R2L (remote to local), and U2R (user to root).

To facilitate experiments without losing generality, we only use a smaller set of the KDD99 dataset for the purpose of evaluating and comparing our method to others. In particular, the training and testing sets used in our experiments are made up of 33,016 instances and 169,687 instances that are selectively extracted from the KDD99 training and testing sets, respectively. The principle for forming such reduced sets is to get all instances in each small group (attack type), but only a limited amount of instances in each large group, from both the KDD99 training and testing sets. More explicitly, for forming the reduced training set, we randomly select five percent of each large group Neptune, smurf, and normal, while gathering all instances in the remaining groups from the KDD99 training set. For sampling the reduced testing set, we randomly select 50 percent of each large group Neptune, smurf, and normal, while collecting all instances in the remaining groups from the KDD99 testing set. Class distribution of these two reduced sets is shown in Table 2. and False Positive Rates (FPRs). The TPR of a class  c is the ratio of "the number of correctly classified instances in the class  c " to "the total number of instances in the class  c ". The FPR of a class  c is the ratio of "the number of instances that do not belong to the class  c but are classified as  c " to "the total number of instances that do not belong to the class  c ". Although reaching a very high TPR, all the tested fifteen classifiers incur a very high FPR on class Normal. This is mainly because there is a large mount of R2L instances misclassified as Normal instances. In fact, R2L instances are very similar to Normal instances in the KDD99 dataset, thus many classification methods proposed in the literature (e.g., KDD99 winners [START_REF] Elkan | Results of the KDD'99 classifier learning[END_REF]) incur a very high FPR on class Normal.

It is also noticed that, as the main drawback of overproductionbased ensemble approaches, our method takes more time in the training phase than the others. This is because it overproduces a large pool of candidate classifiers and then chooses some competent classifiers from the pool for ensemble combination. Nevertheless, the detection (classification) time of our method is comparable to that of the others, because choosing 10 top-ranked classifiers for each local validation region is carried out in the training phase. In addition, since the number of local validation regions is often small (e.g., 50), the time to determine region R * with respect to a testing instance in the detection phase is negligible. The average running time of all tested algorithms (executed on a computer with 2.8GHz CPU, 4GB RAM) is shown in Table 4.

CONCLUSION

We propose in this paper an efficient design approach for generating a robust ensemble system for intrusion detection. The use of cluster features exploited from different clustering processes intensifies both performance and diversity of individual classifiers. In addition, the selection and combination of ensemble members, based on different local validation regions, express the particular classification abilities of classifiers more appropriately, and accordingly further enhance performance of the whole system. The tactic to achieve a robust ensemble-based IDS is concretely formulated via a set of algorithms. Moreover, we experimentally show that our method clearly outperforms all the tested seven methods. In particular, our method is considerably superior to all evaluated methods with respect to R2L, U2R, and Probe classes. Although the experiments are conducted on the KDD99 intrusion detection dataset, the approach we propose can be generally used to improve classification in other application domains. However, to be more objective in evaluating any data mining solution as well as overcome criticized drawbacks of the KDD99 dataset, our future work will be to test the proposed algorithms on other real datasets. In particular, our current effort is fulfilling a honeypot system for the goal of gathering both real intrusion and normal traffic activities. Such a real dataset will then be employed to evaluate the algorithms we proposed.

Figure 1 .

 1 Figure 1. A manipulated training set, resulting from adding cluster features into the input space.

Figure 2 .

 2 (a) The 2D scatter plot of a dataset S; (b) A decision tree DT * generated using both initial and cluster features.

R

  consists of b top-ranked classifiers evaluated on region i R TRAINING PHASE Input: S={X,Y}: an original training set; I: a base inducer; t: total number of classifiers; b: number of top-ranked classifiers (bt); q: number of local regions. Output:

  the top-ranked classifier sets OPERATION PHASE

Figure 4

 4 Figure 4. Algorithm CBE BUILT-IN FUNCTIONS Function

Figure 5 .

 5 Built-in functions called by the CBE algorithmIn the training phase, the algorithm initially splits the original training set into a training set and a validation set. The splitting ratio is basically around 7:3, depending on the size of the original training set.

  a dynamic local region surrounding an unlabeled test instance in terms of k-nearest neighbors in the training set, and then estimate the accuracy of classifiers in this region to determine the best one for classifying the test instance[START_REF] Giacinto | Dynamic classifier selection based on multiple classifier behavior[END_REF]. In our opinion, the estimation of such k-nearest-based local accuracy, although efficient, is somewhat unfit for those application domains where classification is required to be instant or online, such as intrusion detection. This is because, in case the training set is large, calculating the k-nearest neighbors for each incoming test instance in the operation phase is time-consuming and hence hardly applicable in this situation.Hence, we propose a combination method by weighting the performance of ensemble members based on dynamic local regions defined in terms of cluster prototypes (or centroids) in the validation set. The basic idea is to estimate the accuracy of each ensemble member in a cluster (region) whose centroid is closest to the test instance needed to be classified. The keystone is to intensify correct decisions and reduce incorrect decisions of each classifier in local regions surrounding the test instance. One obvious advantage to our combination solution is that, in the operation phase, identifying the local regions in the validation set is considered to be instantaneous. Another applicability is that the method is little sensitive to selecting the number of local regions (clusters). This is because it attempts to weight classifier abilities in different local regions for combination purpose rather than dynamic classifier selection. The ensemble combination method we propose is formally defined as follows.

	(	|	*	)	N r of instances in T otal num ber of instances in correctly classified by *
	Such weighting indicates the influence degree of each ensemble
	member to the final decision. One common way to weight
	classifiers is to estimate their performance on a full validation or
	training set. However, such estimates are insufficient to reflect

particular abilities of individual classifiers, especially in application domains where the distribution of target classes is heavily biased. This is because, for example, a classifier exhibits its high performance on the global region but very poor performance on certain local regions. For solving this problem, some researchers define Let E = {C 2 ,…,C t+1 } be the set of t classifiers, where each C k is induced from the training set added with cluster features resulting from a k-means clustering with k clusters. Suppose that each classifier produces its outputs in form of the estimate of posterior probabilities, where P(C k ,  j | x) represents the support degree produced by classifier C k to class  j for a given test instance x. Let us also assume that the instance space of the validation set is divided into q regions (clusters) {R 1 ,…,R q } by a k-means clustering, and R *  {R 1 ,…,R q } is the region whose centroid is closest to the test instance (x) needed to be classified. Then, the overall accuracy of classifier C k on region R * , which is denoted by OA(C k | R * ), is formulated in Formula 2. *

Table 2 . Class distribution of the reduced datasets

 2 Besides, the number of local validation regions (parameter q) is basically set to 23 (i.e., the total number of normal traffic and attack types or subclasses in the KDD99 intrusion detection dataset). Nevertheless, to have a wider comparative view, we experimentally run the CBE algorithm with some more values of parameter q, i.e., 50, 100, 150, and 200.The experimental comparison of our method (implemented in Matlab) to other seven well-known algorithms is presented in Table3. All the compared ensemble methods (Rows 2-12) employ the same base inducer (i.e., DT) and the same number of base classifiers (i.e, 10). To avoid biases related to sampling and randomization factors , we run our CBE algorithms (Rows 8-12) as well as the other six ensemble algorithms (Rows 2-7) ten times, and then get the average result of runs. The performance of classifiers (algorithms) is evaluated by True Positive Rates (TPRs)

	Class	Training Set	Testing Set
	DoS	22,867	118,807
	Probe	4,107	4,166
	R2L	1,126	16,347
	U2R	52	70
	Normal	4,864	30,297
	Total	33,016	169,687
	6.2 Experimental Results
	In our experiments, the reduced training set of 33,016 instances,
	also termed the original training set, is disjointedly split into a
	training set and a validation set with a fraction of 75% and 25%,
	respectively. Intuitively, such a splitting fraction is reasonable to
	the size of the original training set. In addition, the split is carried
	out by randomly sampling the original training set (without
	replacement) based on each stratification of normal traffic and
	attack types. This is to ensure sufficient representative of each
	subclass in both the training and validation sets. The other input
	parameters of our algorithm (CBE) are established as follows.
	The total number of classifiers (parameter t) is set to 150. The
	reason for choosing such a large number is because, firstly, the
	training phase of Decision Tree (i.e., base inducer for CBE) is not
	time-consuming, compared to that of many other inducers such as
	Support Vector Machines or Artificial Neural Networks.
	Secondly, as an inherent essence of the overproduction-based
	ensemble approach, it is necessary to generate a large amount of
	different classifiers. This not only aims to increase the diversity of
	classifiers but also the possibility of selecting best classifiers for
	the ensemble combination. However, when t is too large, it
	becomes much more time-consuming in the training phase.
	The number of top-ranked classifiers (parameter b) is set to 10.
	This setting is just like many other popular methods (e.g.,
	boosting, bagging) that typically use 10 classifiers for the
	ensemble combination.

Table 3 . TPRs and FPRs (%) of classifiers (algorithms)

 3 CBE gives a 23.67% TPR (with a 0.02% FPR), whereas the classifier having highest performance on this class (i.e., Random Committee) produces an 11.44% TPR (with a 0.46% FPR). Likewise, for "hard" class U2R, on the whole average, our method produces an 84.29% TPR (with a 0% FPR), while the best classifier on this class (i.e., Random Committee) gives a 51.43% TPR (with a 0.04% FPR). With respect to class Probe, the average TPR of five CBE classifiers is 15.68% higher than that of the other seven classifiers. The experiment results also tell that the average performance of five CBE classifiers reaches 90.82% TPR (2.39% FPR), whereas performance of the other seven classifiers fluctuates from 86.20% TPR (6.41% FPR) to 87.45% TPR (2.96% FPR).

	Algorithms		DoS Prob R2L U2R Normal Avg
	1. DT	TP 94.67 76.12 6.01 50.00	97.70 86.20
		FP	5.51 0.41 0.05 0.01	14.24 6.41
	2. Boosting TP 95.48 89.46 6.82 47.14	99.28 87.45
		FP	0.41 0.32 0.01 0.01	14.91 2.96
	3. Bagging TP 94.76 77.04 6.24 37.14	98.36 86.42
		FP	3.02 0.45 0.04 0.00	14.96 4.80
	4. Decorate TP 94.92 75.69 5.42 48.57	97.95 86.35
		FP	4.25 0.47 0.10 0.01	14.37 5.56
	5. RC	TP 94.42 83.81 11.41 51.43	98.43 86.86
		FP	0.59 0.32 0.47 0.04	14.69 3.09
	6. Dagging TP 95.29 79.85 10.08 48.57	97.61 87.10
		FP	0.83 0.34 0.08 0.01	14.84 3.25
	7. RS	TP 95.18 76.34 7.71 18.57	98.85 86.91
		FP	3.87 0.39 0.03 0.00	14.01 5.22
	8. CBE	TP 98.12 95.08 25.03 88.57	99.41 91.23
	(q=23) FP	0.38 0.31 0.02 0.00	10.08 2.08
	9. CBE	TP 98.63 96.62 26.29 81.43	99.49 91.76
	(q=50) FP	0.36 0.19 0.01 0.00	9.66 1.98
	10. CBE	TP 97.59 94.39 22.39 78.57	99.36 90.58
	(q=100) FP	0.78 0.32 0.02 0.00	10.71 2.47
	11. CBE	TP 97.16 95.94 22.51 85.71	99.27 90.31
	(q=150) FP	1.02 0.29 0.02 0.00	10.97 2.68
	12. CBE	TP 97.02 95.17 22.12 87.14	99.65 90.22
	(q=200) FP	1.13 0.35 0.01 0.00	10.94 2.75
	Note:
	-DT refers to Decision Tree [16] with input parameters
	established as follows: Pruning method=pessimistic pruning,
	Confidence=0.25, the minimum number of instances per
	leaf=6, and Counting at leaves is smoothed based on Laplace.
	-Classifiers 2-7 uses the following algorithms:
	Boosting, Bagging [1], Decorate [9], Dagging [18],
	RC (Random Committee), and RS (Random Subspace) [2].
	-Classifiers 8-12 are built from our algorithm parameterized
	with: CBE(I=DT, t=150, b=10, q={23, 50, 100, 150, 200}).
	-Column Avg is the average weighted by the number of
	instances on each class.

As shown in Table

3

, in general, while producing a lower FPR, our method (CBE) outperforms the other seven classifiers with respect to TPR in all five classes. Particularly, CBE is considerably superior to all the others in detecting (classifying) R2L, U2R, and Probe attacks. Regarding R2L (a "hard" class), on the whole average,

Table 4 . Training time and detection time (in second) Algorithms Nr of generated individual classifiers Training time

 4

	Detection
	time