=Paper=
{{Paper
|id=Vol-2622/paper15
|storemode=property
|title=Network Traffic Classification based on Class Weight based K-NN Classifier (CWK-NN)
|pdfUrl=https://ceur-ws.org/Vol-2622/paper15.pdf
|volume=Vol-2622
|authors=Mohammad Hijazi,Jawad Khalife,Hussein Al-ghor,Jesus Diaz Verdejo
|dblpUrl=https://dblp.org/rec/conf/bdcsintell/HijaziKAD19
}}
==Network Traffic Classification based on Class Weight based K-NN Classifier (CWK-NN)==
https://ceur-ws.org/Vol-2622/paper15.pdf
Network Traffic Classification based on
Class Weight based K-NN Classifier (CWK-NN)
Jesus Diaz Verdejo School of
Mohamad Hijazi School of Arts and Jawad Khalife
IT and Telecom. Eng. University
Sciences Lebanese International School of Arts and Sciences
of Granada
University Nabatieh, Lebanon Lebanese International University
Granada, Spain
MohamadOsamaHijazi@Gmail.com Beirut, Lebanon
jedv@ugr.es
jkhalife.khalife@liu.edu.lb
Hussein Al-ghor Faculty
of Technology Lebanese
University Saida,
Lebanon
Hussein.ghor@ul.edu.lb
Abstract— Network traffic identification is the first and Numerous methods were proposed for traffic classification as
most important step in network management and in [1] in the last decade. These methods have different
security. Numerous methods introduced by researchers.
One solution depends on processing both packet header characteristics at many levels, including the analyzed input,
and payload, which is costly from both time and the applied techniques, and the classified target objects.
processing aspects. Another solution depends on the flow
Deciding upon which classification features to use is a
of statistical information such as packet header length,
flow duration. Blind classifiers are not accurate yet very strategic choice for any traffic classifier. Ideally, Deep packet
fast and do not violate privacy. Machine learning fills the inspection as in [2] and [3], or DPI, evaluates the data part
gap between accuracy and time by using the blind
classifier method and comparing the results with grand and the header of a packet that is transmitted through an
truth then adapting and increasing the accuracy. K-NN is inspection point. DPI goes beyond examining IP packet
used widely for its effectiveness and simplicity. However,
headers, therefore, it raises many privacy concerns and is not
a major drawback
of K-NN is its dependency on the training set, being a applicable when the traffic is encrypted or tunneled.
lazy classification algorithm with no classification model However, DPI techniques are considered in the literature as
to build. In this work, we aim first at assessing the KNN
algorithm in traffic classification. Then we introduce a the most accurate techniques and are used therefore as
new deficiency, related to the training samples reference classifiers to build the Ground Truth or reference
distribution in the n-dimensional space we measure and
results.
propose an enhancement for K-NN adapting to the new
problem and outperforming native K-NN classifier. We On the other hand, blind classifiers do not inspect the payload
weight the classes, not the instance, based on the and have the potential ability to deal with these obstacles, at
intersections of
class clusters in the dataset. Finally, we propose a the expense of an acceptable sacrifice in accuracy. However,
new Class Weight based K-NN Classifier (CWK- less accurate, the so-called blind methods are preferred in
NN), an enhanced K-NN algorithm that can easily most environments because they guarantee the
adapt to the newly explored training set deficiency.
users’ privacy, have the potential to classify encrypted
Keywords— K-NN, weighted K-NN, traffic classification, communications and usually require less computational
computer network, traffic identification, training dataset power.
Most of these techniques are based on traffic attributes at the
I. INTRODUCTION
network and transport layers, such as packet sizes and inter-
The ability to identify network applications is centric to many
arrival times. Due to the problem dimensionality, Machine
network management and security tasks, including quality of
Learning (ML) techniques can be used in the classification
service assignment, traffic engineering, content-dependent
context. ML classification is considered an instance of
pricing, resource allocation, traffic shaping, and others. With
supervised learning, i.e., learning where a training set of
the proliferation of applications, many of them using different
kinds of obfuscation, traditional port-based classification has
long become obsolete.
Copyright © 2019 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
105
correctly identified observations is available. An algorithm II. RELATED WORK
that implements classification, especially in a concrete
A large number of traffic classification approaches exist in the
implementation, is known as a classifier. In machine learning,
literature, some are based on deep packet inspection, which
the observations are often known as instances, the
discloses the packet payload and raises privacy concerns,
explanatory variables are termed features (grouped into a
while others rely on discriminative traffic attributes at the
feature vector), and the possible categories to be predicted are
network and transport layers, such as packet sizes and inter-
classes. The term "classifier" sometimes also refers to the
arrival times. This emergent research needs to arise since
mathematical function, implemented by a classification
IANA Port-based classification in [9] has become obsolete for
algorithm that maps input data (traffic attributes in the traffic
more than one decade. Machine learning techniques have been
classification case) to a category (Application type like
widely used in the literature, especially the K Nearest
HTTP, NTP, DNS…etc.).
Neighbor due to its simplicity, zero-time for training, and
There is a relevant research activity in network traffic
adequacy for general classification contexts.
classification, employing different Machine learning
approaches. Among them, K-NN was used in several papers
In [10] authors reduced the flow attributes used in
[4-7] due to its simplicity and zero-training time, as will be
classification by introducing a relationship between flows in
shown in the next sections.
order to derive an expanding vector of flow which represents
Cover and Hart first proposed K-NN (K Nearest Neighbor)
the attributes of the classes. Their algorithm outperforms naïve
algorithm in 1968. The algorithm itself is simple and
base classifier with 3.2% of decrease in error rate and achieved
effective, which is a typical lazy or instance-based learning
99% of accuracy.
algorithm. It is not essential for the classifier to use the
training set to train and the training time complexity is 0.
With K-NN, the function is only approximated locally and all Known DPI methods were enhanced in [11] by introducing a
computation is deferred until classification. The principle of methodology that automatically learns signatures for
application. Their method enhances known DPI by identifying
K nearest neighbor classification algorithm (K-
neighborhood) is that if the K samples in the eigenvalue space new applications that old dpi cannot identify, has higher
most closed to the sample to be identified almost belong to accuracy, handles variation in applications and adapts to
the same class, we determine this sample also belongs to such changing network traffic without user intervention.
a class. The key difference between classification and
regression tree in [8] is that in classification, the task is Many papers in the literature used K-NN for traffic
predicting a discrete class label while in regression, the task classification and attempted to enhance the native algorithm
consists of predicting a continuous quantity. by addressing key challenges. For example, to select the most
In section two, we included the most significant papers appropriate K value for K-NN, authors in [7] used Dynamic
available in the literature. In section three, we explained the K-NN, distance weighted K-NN, clustering the results, and
known knn problems which is assessing knn in classifying the building a model. Dynamic K-NN is responsible for selecting
datasets in each application. In section four we introduced the the most appropriate K value for each dataset. In the training
new problem and we proposed and applied a solution. In phase, K value is selected as well as calculating the weight of
section 5 we will describe briefly the Experimental design each sample, then having clusters in order to build a model. In
(for the lack of space). And provide the results of this work. the test phase, they calculate the distance between the center
In section 6 there is a conclusion. of each cluster and the test point X to be classified. After
finding the nearest cluster, the weighted distance between X
and the rest of the cluster samples is calculated. After
determining the class of X they add it to the training dataset
106
after calculating its weight. As a result, they preserved the B. Dataset Challenges
same accuracy but were able to decrease the time to classify 1) Outlier Instances
An outlier is a data point that differs significantly
an instance by 50%.
from other observations. An outlier may be due to
variability in the measurement or it may indicate the
III. K-NN CHALLENGES experimental error; the latter are sometimes excluded
from the data set. Outliers, when found in the training
A. Algorithm Challenges
dataset, can decrease the classification accuracy of K-
1) Adjusting the K value
NN voting.
The K value has a major impact in determining the nature of Finding such exception has received much attention
the instance to be classified, selecting a small value of K in the data mining field. For example, one of the
means that noise will have a higher influence on the result and solutions used in [15] is to partition the dataset into
a large value make it computationally expensive as explained several clusters and then in each cluster, to calculates
in [12]. .The only way to validate a K-NN model is by the the Kth nearest neighborhood for the object to find
error on test data. As The authors in [13] applied the manual outliers.
way of K value Selection. They also applied other solutions Another Solution is weighting each Instance which
related to the dataset modelling. They outperformed old K-NN is quantifying each Instance contribution in the
with performance increase ranging from 0.01 to 0.02 of Classification process. And adding that number to the
average misclassification cost. voting process.
2) Distance Method Selection Authors in [16] used fuzzy K-NN to enhance
accuracy f score and g mean of pulsar selection
The distance function plays a major role in K-NN
algorithm. They a special weighting algorithm in the
classification accuracy. Researches constantly enhance
training phase, where they compute the relationship
distance functions and add a new attribute to increase
between the features and the class membership. Nearest
accuracy. To determine the proximity of two objects in the
neighbors are given high membership value to the class
feature space, any distance type method can be applied.
they are near from. However, the samples that are far
(Euclidean, Manhattan, Minkowski, etc.) yet researcher must
from a class will be given a small membership value to
test different distance types for each dataset application . In
this class. The proposed algorithm outperforms other
[14] author introduced a new parameter for the original
machine learning algorithms in accuracy metric values
distance method enhanced K-NN by focusing on enhancing
starting from 0.01 to 0.04, G means metric from 0.03 to
the distance measurement method. In [14] the authors
0.06, and decreased the FPR value by 0.04 .
introduced a new variable to the distance rule that made it
dynamic. This variable represents the radius of a sphere
2) Class Imbalance Problem
centered on the new object and excluding all samples that have A drawback of the basic "majority voting"
a distinct label, the distance between an unknown point X (to classification occurs when the class distribution is
be classified) and samples that have the same skewed. That is, examples of a more frequent class tend
“nature” is less than 1 while the distance between X and to dominate the prediction of the new example because
the different elements is 1. They tested the new algorithm on they tend to be common among the k nearest neighbors
five different Datasets and values of K ranging from 1 to 50, due to their large number.
with Manhattan, Euclidean distance methods used, they One way to overcome this problem is to weight the
achieved lowering error rates up to 6%. classification, taking into account the distance from the
test point to each of its k nearest neighbors. The class
107
(or value, in regression problems) of each of to derive the classification decision through majority
the k nearest points is multiplied by a weight voting. When each class has many samples, KNN voting
proportional to the inverse of the distance from that described earlier will make the assumption about the
point to the test point. eventual class of the unknown point.
As such, in a less or near-ideal training-set situation,
Another Intersecting application of weighting is
an unknown point may fall then within the zone in the n-
Introduced by authors in [4] used the sigmoid function to
dimensional space where only members of the same
weight training Instances based on Instances distribution in
class surround it, in this case, KNN voting will be more
the dataset.
reliable since the unknown point shall undoubtedly
belong to the same class of its surrounding neighbors.
WKS algorithm boost the weight of instances surrounded Following the same reasoning, the closer the samples are
by “friendly neighbors” and the decreases the weight if the to the class centroid (i.e. higher density near the
instance is surrounded mostly with different class members. centroid), the more reliable KNN decision shall be.
They were able to decrease the error rate that ranged from To illustrate this concept, Figure 1 shows, the
0.007 to 0.025 for 10 different datasets. We find that their distribution of labeled training points. The set of labels
work was the most significant to our algorithm so we belonging to each class (Classes 1, 2 and 3), are
implemented their algorithm in the experimental setup we clustered into circles for n=2 or spheres for n=3. The
built and compared the results between the native, WKS, and point labeled with X is the unknown point. Class cluster
CWK-NN. radius is defined by the standard deviation of the
training samples distances from the centroid, and the
distance between two clusters is the distance between
IV. PROPOSED ALGORITHM (CLASS WEIGHT K-NN)
their centroids. For example, D12 denotes the distance
As mentioned previously, the dataset may have
between centroid C1 of class 1 and C2 of class 2
various deficiencies, most commonly, outliers (samples
with errors) and, imbalance in the dataset classes (some
classes are predominant over the others). To address
these deficiencies, weighing samples (outliers problem),
or clustered samples (imbalance problem) are among the
most common solutions found in the literature.
To explore and understand further KNN training set
deficiencies, let us consider the ideal training set for
KNN, as derived from the way KNN classifies best any
unknown sample.
In a very ideal training-set situation, space is made
of one representative sample for each class so that any
unknown point will fall in the n-dimensional (n is the Fig. 1. real training set samples' distribution
number of features or attributes)
“exactly” (i.e. coincides) in the location where
only one of the class samples exist.
In real training-sets, however, the location of the
unknown point and existing sample can rarely coincide.
They might rather be close enough for KNN to be able
108
Consider the reliability of the KNN classification
decision when classifying the instances that belong to
collide classes. The reliability of KNN decisions is very
weak. yet for the classes not intersecting the reliability
is supposed to increase evidently for training sets having
the distribution similar to class one and class 3. Since
the reliability of KNN decisions for points, falling inside
the clusters will be higher than those falling outside any
Fig. 2. ideal distribution for a KNN-based classifier
of the existing clusters or at the intersections. Except for
the differences in the neighbors’ distances
Fig 2. Shows a near-ideal distribution where the
considerations, the reliability of the classification
clusters are disjoint and do not intersect at all,
decision shall be quite the same for points falling
mimicking the near ideal situation. In this case, a test
outside any of the existing clusters or at the intersections
point falling into only one of the class clusters will lead
in both cases.
to a highly deterministic KNN voting decision since all
Therefore, when the circles representing class
nearest neighbors to X will have the same label, class 2
clusters are more distant and dense as in Fig2, KNN
in this case.
classification is supposed to become more reliable, at
In the case where unknown points fall out of the
least for the unknown points falling within class
radius of any of the existing clusters, KNN voting
clusters. On the contrary, having too close cluster
decision still applies however with less reliability. In
centroids with lower density (i.e. more spread
other words, the points falling in the intersections or
distribution) will result in additional intersections
between zones are those for which KNN decision will
between clusters, which will decrease the reliability of
be controversial (i.e. not all of the nearest neighbors
KNN classification for the unknown points falling on
have the same class label), which will decrease the
the intersecting zones between classes (e.g. C2 and C3
overall reliability of KNN classification decisions when
in Fig 1.).
compared to the ideal training-set distribution in Fig 2.
In other words, when class clusters have no or fewer
intersections, the training dataset shall become closer to
the “near-ideal distribution” in Fig 2. . Thus
leading for better classification results.
Despite the fact that imbalanced sets are likely to
have class clusters intersections, having one
characteristic (i.e. class imbalance or class intersections)
does not necessarily imply the other:
A dataset can be imbalanced but classes do
not intersect
Fig. 3. Real dataset classes distribution
A dataset can be balanced but classes do
To highlight more on this aspect and for simplicity, intersect
in Fig3. we introduce a dataset having only four classes.
The latter case, depicted in Fig 1. is the most
Each instance has only two attributes. Please notice that
relevant to our approach where we measure the new
the classes are balanced yet two classes is intersecting.
KNN training set deficiency related to
relative points’ distribution within the n-
dimensional space rather than
109
their relative numbers. To the best of our knowledge, Training phase:
“Class clusters intersections” is not For each class we add two instances the first instance is
explored yet as a deficiency for KNN training The centroid, and second instance represents the avarge
sets, nor was it regarded in separate from the distribution of the class in the n dimensions (where n is the
imbalanced class problem. number of attributes).
Up to this level, we have theoretically explained The centroid is the instance core instance having the
and discussed what we think to be ideal for KNN average value of all attributes. The radius is the distance
training set distribution and speculated about its impact between centroid and the instance having the variance of
on KNN classification. However, most of the presented value for all attributes. Thus it’s the allowed
assumptions have to be proven through normal margin for class distribution in the n dimensional
experimentation. space. All the instances outside the threshold is considered as
For this reasons, we attempt next to measure and outliers and they are not significant comparing to the majority
quantify the value of “class clusters of the class instances. Distances between centroids are
intersections” inside KNN training sets. Then, accordingly calculated. To formalize how CWKNN operates
we attempt to derive a new KNN classifier in order to in the training phase refers to simply formalize how class
experimentally demonstrate the importance and impact weights are calculated. The main idea of setting the class
of considering of class intersections or training points weights is that classes who do not intersect have less error
distribution in the training set on KNN classification. margin. We boost the weight of all of Instances having the
same class. However, classes with intersections should
A. Weighting Classes with CWKNN have decreased weights.
A Class Weight based KNN Classifier or CWKNN is
Let M be the total number of classes in the dataset
simply a KNN classifier that takes into consideration the
For each class i, find the distance between the class
samples distribution or class intersections described earlier.
centroid and all other centroids.
As mentioned, intersections should be expressed in terms of
newly defined class weights. The WCKNN algorithm is a
two-phase process that includes the training and the testing Equation 1
described as follows:
𝑊 = 1 + 𝑒 −𝑖
1- Calculate centroids of each class.
2- Calculate the variance instance of each class.
3- Calculate the distance between centroids.
Equation 2
if the distance is larger than the sum of two
radiuses the classes does not intersect and the 𝑀
weight of the two classes remain the same. Else = ∑ 𝑎
if the distance between centroids is smaller than =1
the sum of radiuses there is an intersection and
the weights of the classes must be decreased.
4- Assign the weight calculated for all instances .
110
accomplishment of some additional objectives related to
1 building the experimental setup.
𝜖 [0 , ]
𝑀
1 In this experiment we used a server that has 16 GB of ram ,
𝐴 𝜖 [ 𝑀 , 1]
2 Intel(R) Xeon(R) 2.66 GHz processors with 4 cores each.
𝑊 𝜖 [ 1, (1 + 𝑒 −1 )] With Ubuntu 18.01 OS to capture network traffic and
converting the flows into a dataset. We captured network
Wi: Weight of class i in what concerns class
flows by using tcp dump. then we used nDPI to detect the real
intersections.
nature of the flow traffic and to set the flow attributes.
aij is a discrete value indicating if there is an intersection
was collected the flow , over an extended period of time
between classes i and j.
spanning around 3 days and totaling around 1.2 GB of real
Ai is a value measuring the level of intersections between traffic. we have excluded the encrypted traffic.
class i and the rest of classes. The 3 days span of collecting the data was due to our desire
to collect, a large dataset for testing and classification and
then we were obliged to use a part of the data collected 51752
As shown in equation 1, if Ai, denoting the number of class labeled flow for the lack of resources. The part was selected
i’s intersections with other classes, increases
randomly. Knn classification algorithm stores all training
then Wi should decrease. dataset in the in the RAM.
1
Ai has a minimal value of (since each class intersects with
𝑀 After obtaining the dataset we have used weka open
itself at least)--when the class is disjoint from all other source software to add wks and our algorithm.
classes-- and a maximum value for Ai=1 when theoretically To validate the obtained Result we have used many other
datasets from the weka library. We will only include the
it intersects with all other classes. results from three dataset for the lack of time.
This mechanism ensures that the interval of Wi is.
Intersecting classes are not thus explicitly punished, but Number Number
Number of
Dataset of of
clases
rather, they are not rewarded higher weights. attributes instances
Network flow 7 59 51752
Test phase: each training sample belonging to class i is
Indian diabetes 2 8 768
assigned the weight of the class. The weighted voting of K
Balance scale 3 4 628
neighbors is combined, and the weight of each neighbor is the
Fig. 4. Datasets general information.
function of the class to which the neighbor
As mentioned, there is no optimal conditions applicable
the training phase. for all dataset so we have ran several experiments to adjust the
As per equation 1, the class weight decreases exponentially optimal k value and distance method per dataset. Then we
applied wks and CWK-NN enhancement.
when the value of the number of intersections increases
The dataset was randomized we used 0 as a random seed.
towards M. The contributions of the classification for the Then we split the dataset by 2/3 ratio for training and the
remaining for testing.
training sample belonging to a good class is regulated thus by
the weight value when the numbers of intersections get
True positive rate
considerably higher. Dataset
K-NN WKS CWK-NN
Network flow 98.548% 98.367% 98.721%
V. DATASET AND RESULTS Indian diabetes 61.67% 64.05% 69.02%
One of the objectives of this work, as previously stated, is to Balance scale 77.74% 78.18% 78.93%
assess and to enhance KNN in network traffic Fig. 5. comparison between the native knn, wks, and the proposed
algorithm in the best k value and distance method per dataset.
classification. The completion of these
objectives requires the
111
[2] J. Khalife J. Verdejo, and A. Hajjar On the Performance of OpenDPI
in Identifying P2P Truncated traffic [Book]. - [s.l.] : JOURNAL OF
NETWORKS, 2013. - Vols. VOL. 8, NO. 1.
VI. CONCLUSION [3] digitalguardian digitalguardian [Online] // digitalguardian. -
digitalguardian, 2019. - https: //digitalguardian.com/blog/what-deep-
In this work, we have explored and measured a new packet-inspection-how-it-works-use-cases-dpi-and-more.
[4] Min Zhang Min Qi ，*, Kang Sun , YuJun Niu , Longxiang Shi New
deficiency, related to KNN training samples distribution in the
Classification Algorithm WKS Based on Weight [Conference] // 2017
n-dimensional space and classes’ intersections. IEEE 19th International Conference on e-Health Networking,
Applications and Services (Healthcom). - Dalian, China : IEEE, 2017.
We weighted classes accordingly in the training set. Then, [5] Hou Kaihu Zhan, Hui ,Zhou Zhou A Weighted KNN Algorithm Based
on Entropy [Journal]. - Kunming, china : IEEE, 2018.
we suggested class weighting scheme, then we derived a [6] Shweta Taneja Charu Gupta, Kratika Goyal , Dharna Gureja Enhanced
K-Nearest Neighbor Algorithm Using Information Gain and Clustering
newly proposed Class Weight based KNN Classifier [Conference] // 2014 Fourth International Conference on Advanced
Computing & Communication Technologies. - [s.l.] : IEEE, 2014.
(CWKNN), an enhanced KNN algorithm that can account for
[7] Kumar Nath Syed,M.Rahman,Akram Salah An Enhancement of k -
sample distributions or classes intersections in KNN training Nearest Neighbor Classification Using Genetic Algorithm [Journal]. -
2018.
sets. [8] machinelearningmastery machinelearningmastery [Online] //
machinelearningmastery. - machinelearningmastery, 2018. - https:
Furthermore, we have assessed KNN algorithm in traffic //machinelearningmastery.com/classification-versus-regression-in-
machine-learning/.
classification contexts through an experimental test-bed that [9] IANA IANA Port Numbers. [Online] // IANA . - IANA, 2013. - 01
we build for this purpose. 2013. - http: //www.iana.org/assignments/ port-numbers.
[10] Lei Dinga Jun Liua, Tao Qina, Haifei Lib Internet Traffic Classification
Our tests on real captured and Internet-based datasets showed Based on Expanding Vector of Flow [Journal]. - China : IEEE.
[11] Alok Tongaonkar⇑ Ruben Torres, Marios Iliofotou, Ram Keralapura,
up top 7% enhancements in the classification results, Antonio Nucci Towards self adaptive network traffic classification
[Journal]. - [s.l.] : IEEE, 2014.
compared to the native and samples’ weighted KNN
[12] pseudo_teetotaler stack overflow [Online] // stack overflow. - 2019. -
approaches. https: //stackoverflow.com/questions/33884325/ideal-k-value-in-
KNN-for-classification.
Moreover, and as per our testbed, we showed that K=3 and [13] Zhang Shichao Cost-Sensitive KNN Classification [Journal]. - [s.l.] :
IEEE, 2019.
Euclidean distance type can lead to more than 98% of overall [14] Jigang Wang Predrag Neskovic,Leon N. Cooper Improving nearest
neighbor rule with a simple adaptive Distance measure [Conference] //
Tp in computer traffic classification context. International Conference on Natural Computation. - [s.l.] : ICNC 2006:
Advances in Natural Computation, 2006.
[15] P. Yang B. Huang KNN Based Outlier Detection Algorithm in Large
VII. REFRENCES Dataset [Conference] // 2008 International Workshop on Education
Technology and Training & 2008 International Workshop on
Geoscience and Remote Sensing. - Shanghai : Research Gate, 2008.
[1] J. Khalife J. Verdejo, and A. Hajjar A multilevel taxonomy and [16] TM Mohamed Pulsar Selection Using Fuzzy knn Classifier
requirements for an optimal traffic-classification model [Journal]. - [Conference] // Future Computing and Informatics Journal (2018). -
[s.l.] : Int. Journal of Network Management , 2014. - 2 : Vol. 24. [s.l.] : IEEE, 2018.
112