[發明專利]改進k-means的未知協議數據幀分類方法

在審

• 申請號: 202011234930.5
• 申請日: 2020-11-08
• 公開（公告）號: CN112348084A
• 公開（公告）日: 2021-02-09
• 發明（設計）人: 劉治國;任長慶
• 申請（專利權）人: 大連大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 大連智高專利事務所(特殊普通合伙) 21235
• 代理人: 李猛

1.一種改進k-means的未知協議數據幀分類方法，其特征在于，包括：

對獲取到的比特流數據幀的長度進行對齊處理；

將數據幀中每個字節作為一個屬性，計算各屬性的信息熵來確定其權重，用于加權歐式距離；

計算各個數據幀的密度，基于高密度數據集中通過最大最小距離準則確定聚類中心；

基于簇內簇間加權歐式距離確定最佳聚類個數k，并輸出最佳k值下的聚類結果。

2.根據權利要求1所述的改進k-means的未知協議數據幀分類方法，其特征在于，對獲取到的比特流數據幀的長度進行對齊處理，具體為：將64B作為對齊處理后數據幀的長度，大于此長度的數據幀部分舍去，不足此長度的數據幀通過0補齊。

3.根據權利要求1所述的改進k-means的未知協議數據幀分類方法，其特征在于，計算各屬性的信息熵來確定其權重，具體為：假設對齊處理后的數據幀集合為X＝{X₁,X₂,…,X_n}，其中X_i＝{x_i1,x_i2,…,x_im}，x_ij(1≤i≤n,1≤j≤m)表示第i條數據幀的第j個屬性，根據屬性值集合構造屬性值矩陣X：

計算第i條數據幀的第j個屬性值的比重M_ij：

M_ij(1≤i≤n,1≤j≤m)表示屬性值比重；

計算第j個屬性的熵值H_j：

H_j表示數據幀第j個屬性的熵值；

根據第j個屬性的熵值計算其權值ω_j，第j個屬性的權值ω_j為：

其中：0≤ω_j≤1，

4.根據權利要求1所述的改進k-means的未知協議數據幀分類方法，其特征在于，基于高密度數據集中通過最大最小距離準則確定聚類中心，具體為：計算數據幀X_p和X_q在m個屬性下的加權歐式距離d_ω(X_p,X_q)：

計算高密度數據集中所有數據幀之間的平均加權歐式距離avgd_ω：

求出平均加權歐式距離avgd_ω后，以任意數據幀X_i為圓點，R＝avgd_ω為半徑構造圓形，統計圓內，包括邊緣數據幀的數目ρ_i作為該數據幀的密度，將各個數據幀的密度按照從大到小的順序排列，取前包括數據幀作為擬聚類中心點集合U，U＝{X₁,X₂,…,X_γ,…X_D}，其中

根據最大最小距離準則，確定聚類中心：

1)在擬聚類中心點集合U中選取密度最大的數據幀X₁作為第一個聚類中心點c₁加入聚類中心點集合C中，C＝{c₁,c₂,…,c_κ,…c_k}，其中1≤κ≤k；

2)在擬聚類中心點集合U中選擇距離X₁加權歐式距離最遠的點X_γ作為第二個聚類中心點c₂并加入聚類中心點集合C中；

3)在確定剩余的k-2個聚類中心點時，分別計算擬聚類中心點集合U中剩余的每個數據幀到已確定的聚類中心點的加權歐式距離，并將距離最小值放入最小值集合，待所有的數據幀計算完成時，將集合中的最大值d_max所對應的數據幀作為下一個聚類中心點，如公式(6)所示：

其中，T表示已經確定的聚類中心點的個數，d_iκ表示擬聚類中心點集合U中剩余任意數據幀i到已確定的第κ個聚類中心點加權歐式距離，表示擬聚類中心點集合U中剩余的各個數據幀分別到已確定的κ個聚類中心點的加權歐式距離最小值集合，d_max表示加權歐式距離最小值集合中的最大值；

4)通過公式(6)確定到已經確定的κ-1個聚類中心點加權歐式距離最大的數據幀X_γ，并將X_γ做為第κ個聚類中心點c_κ存入聚類中心點集合C中，直到確定k個聚類中心點為止。

5.根據權利要求1所述的改進k-means的未知協議數據幀分類方法，其特征在于，基于簇內簇間加權歐式距離確定最佳聚類個數k，具體為：

定義第α種協議類簇的第β個數據幀的簇內數據幀距離b(α,β)為該數據幀到同簇其它數據幀加權歐式距離的平均值，如公式(7)所示：

其中，n_α表示第α個協議類簇中數據幀的個數，表示第α個協議類簇中的第β個數據幀的第j屬性；表示第α個協議類簇中的第z個數據幀的第j屬性，表示同一協議類簇內數據幀β到數據幀z的加權歐式距離；

定義第α種協議類簇的第β個數據幀的簇間數據幀距離v(α,β)為該數據幀到其余種協議類簇中數據幀之間的加權歐式距離平均值的最小值，如公式(8)所示：

其中，n_c表示第c個協議類簇中數據幀的個數，表示第c個協議類簇中的第z個數據幀的第j屬性；表示第α個協議類簇中的第β個數據幀的第j屬性；表示不同的協議類簇間的數據幀z到數據幀β的加權歐式距離；

定義第α種協議類簇的第β個數據幀的聚類有效指標為簇內數據幀距離與簇間數據幀距離的比值H，如公式(9)所示：

聚類結果要求同一協議類簇內數據幀之間距離越小越好，不同協議類簇內數據幀之間距離越大越好，即b(α,β)越小，v(α,β)越大，H(α,β)的值越小時聚類效果越好；

假設有n條未知協議類簇的數據幀集合進行分類時，利用公式(10)計算n條數據幀簇內數據幀距離與簇間數據幀距離的比值H的平均值avgH(k)，當avgH(k)取得最小值時所對應的協議種類數，即為最佳的k值；