- Open Access
- Authors : Ashwini Pathak , Sakshi Pathak
- Paper ID : IJERTV9IS050303
- Volume & Issue : Volume 09, Issue 05 (May 2020)
- Published (First Online): 18-05-2020
- ISSN (Online) : 2278-0181
- Publisher Name : IJERT
- License: This work is licensed under a Creative Commons Attribution 4.0 International License
Study on Decision Tree and KNN Algorithm for Intrusion Detection System
MPS in Analytics Northeastern University Boston, USA
Information Technology SGSITS
Indore 452001, India
Abstract With the increase in use of network technology and internet in todays world, cyber attacks and corruption of network protocols have become an inevitable part of the system. In order to tackle this, an efficient Intrusion Detection System (IDS) is required. IDS is a system that detects malicious activity by monitoring a system or a network. This paper focuses on implementing machine learning techniques – Decision Tree and KNN on IDS and evaluates the performance of both the techniques based on their accuracy. The performance is calculated after applying the Univariate feature selection technique with ANOVA(Analysis of Variance) and algorithms are executed on the NSL-KDD dataset. The performance of algorithms is calculated by metrics like accuracy, recall, precision and F-score. The two algorithms are compared on the basis of these performance metrics.
Keyword ANOVA, Decision Tree, IDS, KNN, NSL-KDD Dataset
The main objective of IDS is to protect the network from malicious events. Considering the variety of cyber attacks, the traditional firewall will not be able to protect the network. Therefore, IDS is important to prevent novel attacks that make the system more vulnerable.
The IDS are of two types based on employed detection method:[1-2]. First is Signature based- as the name suggests, it identifies signatures or specific patterns that can be recognized as a malicious information. It works best for only those type of attacks that are known and has no false alarm. Second is anomaly based which implements machine learning techniques and compares current real time traffic to its previously recorded malicious free real time traffic. It is effective in recognizing unknown attacks but it gives rise to higher false negatives. Therefore, it is most widely used.
The IDS are of three types based on where the attack is taking place:[1-2]
Host based IDS- It functions on a device. It checks for any malicious activity by comparing a file in its present state with its past state and informs the owner or administrator in case any change is found.
Network based IDS- It is placed in the network from where it analyzes all devices. It compares the current traffic on subnet to the known attacks. If any anomaly is detected, it informs it to the administrator.
Hybrid based IDS- When both HIDS and NIDS come into play it is called Hybrid based IDS.
There have been several research work on implementing machine learning algorithm on KDD CUP 99 dataset and NSLKDD dataset. Some work on feature selection for intrusion detection system are done in [3-4]. Reference  termed feature selection as an important factor for better accuracy. They found that seven features were not important in the determination of attacks. Reference  compared NaÃ¯ve Bayes and Decision tree algorithm and they found out that decision tree performs better when compared to NaÃ¯ve Bayes. A method of TCM-KNN is proposed for network anomaly detection in  on KDD Cup 99 dataset. KNN algorithm is studied in  while a study on Random forest and SVM is done in . Aegean Wi-Fi Intrusion Dataset (AWID) with different machine learning techniques implementation is proposed in  with information gain and chi square metrics.
The previous research papers show various machine learning algorithms evaluated on KDD CUP 99, NSL KDD dataset. Various feature selection technique have been applied in research papers. This paper will study Decision tree and KNN and will apply Univariate feature selection with ANOVA. We will compare the algorithms by calculating their performance metrics.
Dataset that provide the best understanding of various intrusion attacks are KDD dataset. The popular KDDCUP99 dataset was one of the dataset which was available for network IDS but it had a major problem. The problem is the redundancy of data. By analysis, it is found that 78% of data in train dataset is duplicated and 75% of test dataset is duplicated. The newer KDD CUP 99 is NSL KDD. It has selective records from the KDD CUP 99 and does not have redundant data. It has reasonable number of records in both test and train data set which makes it easier to analyze and eliminate the need of choosing some records from it . NSL KDD dataset description is given in Table 1.
Table 1. Dataset Description
duration of connection(in seconds)
type of protocol
Number of bytes transferred from source to destination
Number of bytes transferred from destination to source
If connection is to same host land=1, else 0
Number of wrong fragments
Number of urgent packets
Number of hot indicators
Number of failed logins
If logged in logged_in=1, else 0
Number of compromised conditions
If root shell is obtained root_shell=1, else 0
If su root accesses, su_attempted=1, else 0
Number of accessed roots
Number of file creations
Number of shell prompt
Number of operations on access files
Number of outbound commands
If login is hot is_host_login=1, else 0
If login is guest is_guest_login=1, else 0
Number of connections to the same host in last 2 seconds
Number of connections to the same service in last 2 seconds
Percentage of connection with syn error
Percentage of connection with syn error
Percentage of connection with rej error
Percentage of connection with rej error
Percentage of connection of same service
Percentage of connection of different service
Percentage of connection of different hosts
Number of connections of same destination host
Number of connections of same destination host and service
Percentage of connections having same destination host and service
Percentage of connections having different service on current host
Percentage of connections of current host having same src port
Percentage of connection of same service and different hosts
Percentage of connections of current host having S0 error
Percentage of connections of current host of a service having S0 error
Percentage of connections of current host that have rst error
Percentage of connections of current host of service that have rst error
Type of attack
Table 2. presents the attacks types classified in 4 types of attacks namely: Dos, U2R, R2L, Probe.
Table 2. Distribution of attacks
Neptune, back, land, pod, smurf, teardrop, mailbomb, apache2, processtable, udpstorm, worm
buffer_overflow, loadmodule, perl, rootkit, ps, sqlattack, xterm
ftp_write, guess_passwd, imap, multihop, phf, spy, warezclient, warezmaster, sendmail, named, snmpgetattack, snmpguess, xlock, xsnoop, httptunnel
ipsweep, nmap, portsweep, satan, mscan, saint
There are 4 basic type of class:
DoS(Denial of Service)- It is one of the most harmful attacks. These type of attacks restrict the user from using certain services. The attacker tries to overload the system or keep the resources busy in the network and does not allow the user to access services.
U2R- In this kind of attack, the attacker tries to gain access to the system as a root user. The attacker tries to gain access to all data of the system and have full control on the server.
R2L- In this attack, the attacker tries to gain access to a system by sending some message to the server and gaining access to system from a remote machine. The attacker makes some changes to the server to get access to resources. One of the examples being guessing passwords.
Probe attacks- This attack aims to analysing the network, gather information. This attack is generally performed to be able to attack through some other methods later.
Fig 1. shows the number of instances of each attack type in the train dataset while Fig 2. presents data from test dataset. The analysis shows that DoS class has maximum instances in both datasets.
Fig. 1. Number of instances of each type of attack in train dataset
DoS U2R R2L Probe
Fig. 2. Number of instances of each type of attack in test dataset
Data Pre-processing is done to convert raw data into another format for preparing data for analysing the data further.
Handling missing data
One Hot Encoding: Since any feature with object/string type values will not be valuable to analyse the data, we have to convert categorical data to quantitative variables by using One Hot Encoding. The features having object datatype are: protocol_type, service, flag. We convert these columns to category data type and then apply label encoding to convert it into numerical values. These column values are then converted to binary vectors for further analysis. After performing One Hot Encoding the training and testing dataset is divided into 4 parts depending on the type of attack: DoS, U2R, R2L or Probe attack.
Data Normalization: It is performed in order to scale the data so that any feature which is comparatively high in values might not be given more weightage. While it is necessary for KNN, it is not useful for Decision Tree algorithm.
It is one of the most important processes in data preprocessing in machine learning. It keeps only the relevant attributes and removes all the redundant features. Any attribute that does not contribute towards predicting the target value are not important and are removed.
The feature selection technique comprises of 4 steps: First step is the feature selection that selects the required features for a particular problem. Second step is the function assessment that evaluates the set of features selected. Third step is the stopping criteria that identifies if the features will help in stopping the search. Fourth step is the validation procedure that assesses the features and identifies the quality of features. They are divided in two groups: Filter and Wrapper. Filter finds the similarity between attributes and the class. Wrapper evaluates the concerned attributes . The Univariate Feature selection with ANOVA F-test is performed to find the appropriate features for a label by determining the relationship between features and label. The univariate approach chooses the attributes which are related largely with target variable. The class SelectPercentile selects the features which are best associated with the target variable. The metrics chosen is f_classif for finding the best features.
Classifiers are given training data, it constructs a model. Then it is supplied testing data and the accuracy of model is calculated. The classifiers used in this paper are :
Decision Tree algorithm is one of the well known classification method. Decision tree is a tree like graph. It assigns classification based on the rules applied from the root to the leaf of the tree. The internal nodes are test, branch corresponds to the result of test and leaf nodes assigns a classification. The data having least impurity is chosen. This impurity is measured by entropy. Higher the entropy means high impurity.
Decision Tree algorithm:
Choose any attribute from the data.
Calculate the significance of attribute while splitting the data.
Split the data on value of best attribute.
Again go to step 1
Gini impurity: This measure is used for classification of trees. It is a variation of entropy calculated for decision tree. If an item is classified according to the distribution of labels, gini impurity is the likelihood of incorrect classification of that item. Gini impurity is a measure of how often a randomly chosen element from the set would be incorrectly labeled if it was randomly labeled according to the distribution of labels in the subset . The Gini index is defined as :
The criteria for defining ai is defined as :
Advantages of Decision tree are that it does not require parameter setting. Also, it evaluates all possible outcomes and makes the best possible decision. Disadvantages of Decision tree are that small change in dataset will lead to bigger changes in the decision tree. 
KNN(K-nearest neighbour): It is a method for classifying similar cases. Also called the lazy learner because it does not have any learning phase. It produces results only when they are requested.
Algorithm for KNN-
Choose a value of k
Calculate the Euclidean distance of all cases from unknown case.
The Euclidan distance (also called the least distance) between sample x and y is : 
where xi is the ith element of the instance x, yi is the ith element of the instance y and n is the total number of features in the data set.
Choose k number of observations near to the unknown case.
The unknown data will belong to the majority cases in k nearest neighbour
Advantages of KNN are that it is one of the simplest algorithms as it has to compute the value of k and the Euclidean distance only. It is faster than majority of other algorithms because of its lazy learning feature. Also, it is very efficient for multiclass problem. Disadvantages of KNN are that the algorithm may not generalize well as it does not go through the learning phase. It is slower for a large dataset as it will have to calculate sort all the distances from the unknown item. KNN algorithm also requires feature scaling for best result.[18-19]
RESULTS AND DISCUSSIONS
After training the model, the algorithms: Decision Tree and KNN is tested on a testing dataset. It is represented by a confusion matrix. The confusion matrix presents the value of True positives, true negatives, false positives and false negatives.
True Negative(TN): It is the number of correct prediction that an instance does not belong to a particular class.
False Positive(FP): It is the number of incorrect prediction that an instance belongs to same class when it belongs to some other class.
False Negative(FN): It is the number of incorrect prediction that an instance belongs to some other class when it belongs to the same class.
True Positive(TP): It is the number of correct prediction that an instance belongs to same class.
The following performance metrics are calculated: Accuracy = (TP+TN) / (TP+TN+FN+FP)
Recall = TP/ (TP+FN)
Precision = TP/ (TP+FP)
F-Score = 2*(precision*recall) / (precision + recall)
Table 3 shows the result of the implementation of both the algorithms and displays the value of Accuracy, Precision, Recall and F-score for each kind of attack.
Table 3. Experimental Result
Fig. 3 compares the accuracy of both the algorithms for all types of attacks. Fig. 4 compares the average value of accuracy, precision, recall and f-score for both algorithms.
Fig. 3. Comparison of accuracy acquired by the two algorithms: Decision tree and KNN
Fig. 4. Comparison of average accuracy, precision, recall and f-score of the two algorithms: Decision tree and KNN
The observations made from the performance are:
The average accuracy of Decision tree algorithm is better than KNN.
The accuracy for correctly identifying DoS, U2R is slightly better for KNN while the accuracy for correctly identifying R2L and Probe attacks is better for Decision tree.
The KNN algorithm reaches high precision.
The precision rate for DoS, U2R is higher for KNN while it is higher in case of R2L and Probe attacks for Decision tree algorithm.
The recall value and F score is higher for Decision tree algorithm.
Decision tree has a fairly low time demand as compared to KNN.
We have met the objective of this paper of studying two algorithms: Decision tree and KNN applied on the NSLKDD dataset. We performed data pre-processing on the NSL KDD dataset by handling missing values, applying one hot encoding and normalizing data. We have successfully applied ANOVA f-test on the dataset and selected the best features for each type of attack. We have acquired the performance of both algorithms on classification of 4 attacks: DoS, U2R, R2L and Probe. We have found that the Decision tree algorithm gives a better result with an accuracy of 99.15%. Also, we found that the time taken to build the Decision tree algorithm was far less than the KNN algorithm. Therefore, the results show that Decision tree algorithm gives an overall better result as compared to KNN.
Ashoor A S, Gore S. Importance of Intrusion Detection System (IDS). IJSER, 2011, 2(1).
Saxena A K, Sinha S, Shukla P. General study of intrusion detection system and survey of agent based intrusion detection system. ICCCA, 2017, pp. 471-421.
Olusola A A, Oladele A S, Abosede D O. Analysis of KDD 99 Intrusion Detection Dataset for Selection of Relevance Features. Proceedings of the World Congress on Engineering and Computer Science WCECS, San Francisco, USA, 2010, Vol. 1.
Sung A H,Mukkamala S. Identifying Important Features for Intrusion Detection Using Support Vector Machines and Neural Networks. Proceedings of the 2003 Symposium on Applications and the Internet, 2003.
Amor N B, Benferhat S, Elouedi Z. Naive Bayes vs decision trees in intrusion detection systems, Proceedings of the ACM Symposium on Applied Computing, 2004, 1: pp. 420-424.
Li Y, Fang B, Guo L, Chen Y. Network Anomaly Detection Based on TCM-KNN Algorithm. Proceedings of the 2nd ACM Symposium on Information, Computer and Communications Security, 2007, 7, pp. 13-19
Liao Y, Vemuri R V. Use of K-Nearest Neighbor classifier for intrusion detection. Computers & Security, 2002, 21(10): 439-448.
Patgiri R, Varshney U, Akutota T, Kunde R. An Investigation on Intrusion Detection System Using Machine Learning, 2019
Thanthrige U S K P M, Samarabandu J, Wang X. Machine learning techniques for intrusion detection on public dataset . IEEE Canadian Conference on Electrical and Computer Engineering (CCECE), 2016, pp. 1-4.
Tavallaee M, Bagheri E, Lu W, Ghorbani A A. A Detailed Analysis of the KDD CUP 99 Data Set. Proceedings of the 2009 IEEE Symposium on Computational Intelligence in Security and Defense Applications CISDA, 2009.
Jha J, Ragha L. Intrusion Detection System using Support Vector Machine. International Journal of Applied Information Systems (IJAIS), 2013
Tribak H, Delgado B, Rojas P, Valenzuela O, Pomares H, Rojas I. Statistical analysis of different artificial intelligent techniues applied to Intrusion Detection System. Proceedings of 2012 International Conference on Multimedia Computing and Systems, ICMCS, 2012, pp. 434-440.
Rai K, Devi M, Devi, Guleria A. Decision Tree Based Algorithm for Intrusion Detection. IJANA, 2016, 07:2828-2834
Kumar A, Nidhi A, Michael R. Implementing an Intrusion Detection System using a Decision Tree, 2014.
Rokach L, Maimon O. Top-down induction of decision trees classifiers – a survey. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2005, 35(4), pp. 476-487.
Sahu S K, Sarangi S, Jena S K. A detail analysis on intrusion detection datasets. IEEE International Advance Computing Conference (IACC), 2014, pp. 1348-1353.
Brao B, Swathi K. Fast kNN Classifiers for Network Intrusion Detection System. Indian Journal of Science and Technology, 2017, 10, pp. 1-10.
Ajayi, A, Idowu S A. Comparative study of selected data mining algorithms used for intrusion detection, 2013, 7.
Kim J, Kim B S, Savarese S. Comparing Image Classification Methods: K-Nearest-Neighbor and Support-Vector-Machines. Applied Mathematics in Electrical and Computer Engineering, 2019, 6, pp. 133-138.