Network traffic classification method and system based on improved K-means algorithm

Patent metadata

Field	Value
Publication number	US-11570069-B2
Application number	US-202217846908-A
Country	US
Kind code	B2
Filing date	Jun 22, 2022
Priority date	Jun 22, 2020
Publication date	Jan 31, 2023
Grant date	Jan 31, 2023

Abstract

Disclosed are a network traffic classification method and system based on an improved K-means algorithm. The method comprises: judging whether a total number NIC of network traffic data points in an initial clustering center set reaches an expected number k of network traffic clusters, if the k is not reached, calculating candidate metric values of network traffic data points in a high-density network traffic data point set, selecting a network traffic data point having the maximum candidate metric value, adding same into an initial clustering center set, removing the network traffic data point from the high-density network traffic data point set, then repeating the step until the total number NIC of network traffic data points in the initial clustering center set reaches the k, and ending the step. The method and system can ensure high network traffic classification accuracy.

First claim

The invention claimed is:

1. A network traffic classification method based on an improved K-means algorithm, comprising the following steps of:
defining a number of network traffic data points as N;
defining a Euclidean distance between a network traffic data point which is n th closest to an i th network traffic data point and the i th network traffic data point as an n th distance of the i th network traffic data point, wherein i=1, 2, 3, . . . , N;
defining a distribution density of all network traffic data points from the closest to the n th closest to the i th network traffic data point in a multi-dimensional hypersphere with the i th network traffic data point as a spherical center and the n th distance of the i th network traffic data point as a radius r as an n th density D in of the i th network traffic data point, wherein one and only one network traffic data point which is closest to the i th network traffic data point and one and only one network traffic data point which is n th closest to the i th network traffic data point are provided respectively, and all network traffic data points comprise the network traffic data point closest to the i th network traffic data point and the network traffic data point n th closest to the i th network traffic data point;
inputting a network traffic data point set to be clustered and an expected number k of network traffic clusters;
determining a specific value of n in the n th distance of the i th network traffic data point;
calculating an average value avg of n th densities of all network traffic data points;
adding the network traffic data points in all network traffic data points with the n th density greater than the average value avg of the n th densities into a high-density network traffic data point set, wherein the high-density is greater than the average value avg of the n th densities; and
selecting network traffic data points having the maximum n th density in the high-density network traffic data point set, adding the network traffic data points having the maximum n th density into an initial cluster center set, and removing the network traffic data points from the high-density network traffic data point set until a total number NIC of network traffic data points in the initial cluster center set reaches the expected number k of network traffic clusters;
clustering the initial cluster center set;
establishing a mapping relation between a network traffic cluster obtained by the clustering and a network application type; and
classifying the network traffic data point based on the mapping relation.

2. The network traffic classification method based on the improved K-means algorithm according to claim 1 , wherein a calculation formula of the n th density D in of the i th network traffic data point is that

D

i
⁢
n

=

n
-
0.5

r
+
1

.

3. The network traffic classification method based on the improved K-means algorithm according to claim 1 , wherein a calculation formula of n in the n th distance of the i th network traffic data point is that

n
=

N

k
×
8

.

4. The network traffic classification method based on the improved K-means algorithm according to claim 2 , wherein a calculation formula of the average value avg of the n th densities of all network traffic data points is that

a
⁢
v
⁢
g

=

1
N

⁢

∑

i
=
1

N

D

i
⁢
n

.

5. The network traffic classification method based on the improved K-means algorithm according to claim 1 , wherein a candidate metric value of a j th network traffic data point in the high-density network traffic data point set is recorded as cd j , and a calculation formula thereof is that cd j =min(<A j , ic 1 >, <A j , ic 2 >, . . . , <A j , ic NIC >),
wherein, A j is the j th network traffic data point in the high-density network traffic data point set, j=1, 2, 3, . . . , NHD, and NHD is a total number of network traffic data points in the high-density network traffic data point set, ic 1 , ic 2 , . . . , ic NIC are respectively first, second, . . . , NIC th network traffic data points in the initial cluster center set, <A j , ic 1 > is a Euclidean distance between the j th network traffic data point in the high-density network traffic data point set and the first network traffic data point in the initial cluster center set, and so on,
<A j , ic NIC > is a Euclidean distance between the j th network traffic data point in the high-density network traffic data point set and the NIC th network traffic data point in the initial cluster center set.

6. A network traffic classification system based on an improved K-means algorithm, comprising a processor and a storage medium, wherein:
the storage medium is configured for storage instructions; and
the processor is configured for operating according to the instructions to perform a network traffic classification method based on an improved K-means algorithm, the method comprising the following steps of:
defining a number of network traffic data points as N;

defining a Euclidean distance between a network traffic data point which is n th closest to an i th network traffic data point and the i th network traffic data point as an n th distance of the i th network traffic data point, wherein i=1, 2, 3, . . . , N;
defining a distribution density of all network traffic data points from the closest to the n th closest to the i th network traffic data point in a multi-dimensional hypersphere with the i th network traffic data point as a spherical center and the n th distance of the i th network traffic data point as a radius r as an n th density D in of the i th network traffic data point, wherein one and only one network traffic data point which is closest to the i th network traffic data point and one and only one network traffic data point which is n th closest to the i th network traffic data point are provided respectively, and all network traffic data points comprise the network traffic data point closest to the i th network traffic data point and the network traffic data point n th closest to the i th network traffic data point;

Assignees

• Univ Nanjing Posts & Telecommunications
• Nanjing Univ Of Posts And Telecommunicatins

Inventors

• Zhang Dengyin
• Cai Yue
• Xiao Yi
• Zhao Shasha

Classifications

• G06K9/6223

  Physics · mapped topic

• H04L43/0888

  Throughput · CPC title

• H04L43/0882

  Utilisation of link capacity · CPC title

• H04L43/062 Primary

  related to network traffic · CPC title

• H04L43/0811

  by checking connectivity · CPC title