In order to protect valuable computer systems, network data needs to be analyzed and classified so that possible network intrusions can be detected. Machine learning techniques have been used to classify network data. For supervised machine learning methods, they can achieve high accuracy at classifying network data as normal or malicious, but they require the availability of fully labeled data. Semi-supervised machine learning methods, however, can use a small number of labeled examples and train a large number of examples without label. In this research, we explore the use of semi-supervised Random Forest in classifying network data and intrusion detection. It was used to classify the Third International Knowledge Discovery and Data Mining Tools Competition dataset (KDD 1999) and the result were compared with the results of using the supervised methods of Random Forest. The results were also compared with those using ladder network, an approach which combines unsupervised neural networks, in classifying KDD 1999.
In the last decade, the development of computer technology and the invention of the internet have brought many benefits to society. Some of these benefits include faster communication, better convenience and more productivity. Today, more than three billion people have access to the Internet, equating to 42 percent of the global population in 2014. Thus, network security has become very important. Intrusion Detection System (IDS) is a device or software application that monitors a network or system for malicious activity or policy violation. Current IDSs are either signature based or anomaly based. The signature based IDS detects the attacks which have been documented. Thus new types of attacks cannot be detected by the signature based detection. The anomaly based detection focuses on finding unknown or unusual activity patterns in the observed data. It can detect new attacks but it also needs a domain expert to distinguish normal or abnormal activity patterns.
In this research, machine learning methods has been
used to detect attacks. Some of the machine learning
classifiers have been developed under supervised learning.
Supervised learning is to use labeled data to train the
classifier and then test the classifier in the test set. The
disadvantage of supervised learning is that it needs a large
amount of labeled data, which is not practical since it’s
labor intensive. Different from supervised learning, the
unsupervised learning is to use unlabeled data to train the
classifier and to infer a function described hidden structure.
However unsupervised learning is very sensitive to noise
data and the results can be influenced a lot. Hasan and his
team developed the Support Vector Machine (SVM) and
Random Forest supervised learning methods[
Semi-supervised learning falls between supervised
learning and unsupervised learning. Different from
supervised learning, semi-supervised learning uses a small
amount of labeled data and a large amount of unlabeled
data to train and test the classifiers. Researchers have found
that unlabeled data, when used in conjunction with a small
amount of labeled data, can produce considerable
improvement in learning accuracy. There are two kinds of
semi-supervised learning, transductive and inductive
learning. Transductive learning is to use labeled data to
train the classifier and use the unlabeled data to test the
classifier. The inductive learning is to use both labeled and
unlabeled data to train the classifier. Zehra Cataltepe et al
had a research on semi-supervised decision trees for
network intrusion detection based on KDD99 dataset [
This research implemented semi-supervised Random
Forest for network intrusion detection. KDD99 dataset was
used for training the classifier. The experiments used the
same number of classes, and the same number of samples
in each class as in Mtahir et al ’s research [
The paper is organized as follows. Section 2 discusses
the background of Random Forest based on Dr. Leo
Breiman’s research [
Random Forest is an ensemble of classification or
regression trees. The Random Forest classifier works by
partitioning the training set of the data into k subsets and
constructing a decision tree out of each subset. All of the
subsets are randomly selected. Each decision tree is made
by randomly selecting m variables out of all the variables
and finding the best split on the selected variables. This is
done at each node and continued until a node cannot be
split further, leading to the leaf nodes. Each tree votes on a
classification after running the test set on each of them. The
final classification of the forest is determined by the
majority of the decision trees [
The algorithm of Random Forest proposed by Dr. Leo
Breiman described as below [
Given a set of classifiers t1(x), t2(x),…, tk(x), and with the training set drawn at random from the distribution of the random vector Y, X, we can get the margin function as !" #, % = '( )* +) # = % −!'. /0 1'( )* +) # = 2 where I is the indicator function. The margin measures the average number of votes at X, Y for the right class exceeds the average votes for any other class. The larger the margin, the more accuracy in testing. The generalization error is given by
34 ∗ = 3#,1 !" #, % < 0 where the subscripts X, Y indicate that the probability is over the X, Y space.
In random forests, tk(X) = t(X, Qk). When the forest has a large number of trees, it follows the Strong Law of Large Numbers and the tree structure that:
3#,1(39 + #, Θ = % − !'. /0 139 + #, Θ = 2 < 0 (3) where Q is random vector for splitting selection and Qk is independent identically distributed random vector.
For Random Forest F = {t1, t2, …, tN}, when each tree is constructing, it learns a function F: x ®y. The training set is {xi Îx}i = 1…l and the test set {yi Î y}i = 1…l. Each internal node of Random Forest is binary split with a partition criterion.
When testing, given a test case x, Random Forest gives the probability estimation for each class as ; < .
where pi (k|x) is the probability estimation of class k
given by the ith tree [
It is estimated by calculating the ratio that class k gets votes from the leaves in the ith tree ;? < .
AB,C E DFG AB,D
(1) (2) (4) (5) Semi-supervised Random Forest for Intrusion Detection where li,k is the number of leaves in the ith tree that vote for class k. Here the overall decision function of Random Forest is as follows.
H = 'I"!'.; < . | < ∈ L (6)
Xiao Liu et al [
The process of Random Forest constructing, an individual training set for each tree (random input) is generated from the original training set using bootstrap aggregation (for labeled set MA? and unlabeled setMN?). The samples which are not included in the training set is OOB samples and can be used to calculate OOB error. A OOBE is a good feature to do node splitting and semi-supervised training.
Xiao’s algorithm for semi-supervised splitting is as
follows [
Train the tree with only labeled data: +A? = +I'OPQIRR MA? .
Step 5: Calculate the OOBE: RA? = TTUR +A?, MA − MA? using the labeled trained tree and the difference between original labeled data and labeled samples. Step 6: Train the tree with both labeled and unlabeled data: +N? = VR!OQIRR MA?, MN? .
Step 7: Calculate the OOBE: RN? = TTUR +N?, MA − MA? using unlabeled trained tree and the difference between original labeled dataset and labeled samples.
Step 8: Compare the OOBE of the above two different trained tree to select final classifiers.
if RA? > RN? then Step 9: H = H ∪ +N?.
Step 10: else Step 11: H = H ∪ +A?.
Step 12: end if Step 13: end for Step 14: Return F. 3
3.1 KDD 1999 dataset
KDD 1999 is the Third International Knowledge
Discovery and Data Mining Tools Competition, which was
held in conjunction with the Fifth International Conference
on Knowledge Discovery and Data Mining [
This research used Berman’s Random Forest model [
In order to compare with supervised Random Forest
method, the experiments used the samples as 10, 1000,
3000 and 5000 examples per class and classes as 16, 9, 6
and 6 respectively which were same as those in Mtahir et
al ’s research [
To compare the supervised machine learning and
semisupervised machine learning, we used Mutahir Nadeem et
al [
Table 5 and Table 6 are the result comparison for
semisupervised Random Forest and semi-supervised Ladder
Network of Mutahir et al [
To be consistent, the result used the samples as 10, 1000, 3000 and 5000 examples per class. The training data set includes both labeled and unlabeled examples. The ratio of labeled data is 50%.
Compared with the result of semi-supervised Random Forest, the Ladder Network took more time to execute. For large amount of data, semi-supervised RF and Ladder Network has similar accuracy. But for the medium amount of data, the Ladder Network has lower accuracy than that of Random Forest.
In summary, the Semi-supervised Random Forest performed better than the Semi-supervised Ladder Network. Even though it took more time to train in semi-supervised Random Forest than that in supervised Random Forest, it has advantage because it only needs small amount of labeled data. This is practical because in the real world, it is hard to label large amount of data. Also, training the classifier using unlabeled data can make the margin more accurate and smooth.
Our future work includes improving the training algorithm of semi-supervised Random Forest and making it faster. Also we will develop semi-supervised Support Semi-supervised Random Forest for Intrusion Detection Vector Machine (SVM) and Deep Belief Network (DBN) on KDD 99 and compare their results.
The 28th Modern Artificial Intelligence and Cognitive Science
Conference, Fort Wayne, Indiana, USA This work is partially supported by NSF under the grant CNS-1460864. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of NSF.
Heidelberg.