數據清洗下的改進半監(jiān)督聚類入侵檢測算法研究

周志平，陳曉潔

（龍巖學院信息工程學院，福建龍巖364000）

數據清洗下的改進半監(jiān)督聚類入侵檢測算法研究

周志平，陳曉潔

（龍巖學院信息工程學院，福建龍巖364000）

針對半監(jiān)督聚類算法易受噪點的影響，提出一種基于數據清洗的改進半監(jiān)督聚類算法DCSC。將噪點從數據集中提取出來另行分析。從數據清洗處理后的數據集中抽取若干正常與異常樣本分別計算作為初始樣本輔助K-Means算法進行聚類。實驗結果表明,與現有相關算法相比，該算法具有檢測未知攻擊的能力，且具有更高的攻擊檢測率以及更低的誤報率。

數據清洗；半監(jiān)督聚類；入侵檢測

計算機網絡已融入到人類社會的方方面面，隨著網絡的快速發(fā)展，網絡攻擊技術和手段也日趨復雜多樣，網絡安全問題日漸突出。入侵檢測是指通過分析網絡或者系統(tǒng)中的數據，發(fā)現是否存在異常并生產報警信息的過程。入侵檢測作為一種有效的網絡安全防御技術，引起國內外學者的廣泛關注。傳統(tǒng)的入侵檢測系統(tǒng)（intrusion detection system,IDS）采用模式匹配的方法，從網絡或者系統(tǒng)的數據中提取特征并與攻擊特征庫中的攻擊特征進行匹配來識別入侵行為。隨著網絡技術的發(fā)展，基于專家提供的攻擊特征庫構建越來越困難，使得這種方法存在大量的錯報或虛報的情況，并且對于未定義的新型攻擊特征無法檢測。將數據挖掘技術引入入侵檢測中[1]，可以大大改善入侵檢測系統(tǒng)建模過程中人為以及不定因素的影響。

在入侵檢測系統(tǒng)中常用的數據挖掘算法有時序算法、決策樹算法、神經網絡算法、聚類分析算法等?；诰垲惙治龅娜肭謾z測是一種無監(jiān)督的異常檢測技術，該方法對無標簽的數據集進行操作，將相似的數據樣本劃分到一個類中，相異的數據樣本劃分到不同的類中。理想狀況下，通過聚類算法，將正常數據與異常數據劃分到不同的類中。為了提高聚類算法的檢測率，降低誤報率，可將半監(jiān)督學習的思想引入到入侵檢測中。半監(jiān)督學習是近幾年來在機器學習領域發(fā)展的一種新方法，它綜合利用有標簽和無標簽樣本進行學習。將半監(jiān)督聚類分析引入入侵檢測，利用少量的標有正常與異常標簽的數據樣本對數據集進行約束，輔助聚類算法，減少錯報虛報，提高算法的效率。由于數據來源不一，可能存在不同模式的描述，甚至存在矛盾。因此，在數據集成的過程中對數據進行清洗，以消除相似，重復或是異常的數據是非常必要的[2]。本文提出基于數據清洗的半監(jiān)督聚類算法（data cleaning based semi-supervised clustering algorithm, DCSC），將數據集進行降噪處理，可以改善噪點對于聚類過程的影響，并分別抽取若干正常與異常樣本進行初始化，引導后續(xù)的聚類過程。

1 相關工作

1.1 K-means算法

K-means算法是一種最常用的基于劃分的聚類方法，將目標數據劃分為K個類，樣本與樣本之間的距離采用歐氏距離計算。該算法是基于目標函數的聚類算法，其目標函數為，其中μl為第l個類的質心。該算法的優(yōu)點是簡單，能夠高效的處理大型數據，缺點是對初始值K以及隨機數敏感，對噪點和孤立點非常敏感，易陷入局部最優(yōu)解。

算法描述：

輸入：聚類數目k。

輸出：誤差平方和（sum of squared errors,SSE）；聚類中各類樣本數目。

算法步驟：

Step 1隨機選擇k個樣本作為初始簇質心并進行標準化處理；

Step 2根據簇中對象的平均值，將每個對象賦給最類似的簇；

Step 3更新簇的平均值；

Step 4重復Step 2，Step 3直到重新分配不再變化。

1.2 基于距離的半監(jiān)督聚類算法

半監(jiān)督聚類算法[3]是指在數據集中選取若干seed樣本作為帶有標簽的數據樣本，以輔助聚類過程，使得聚類結果的精確度更高。文獻[4]提出了兩種基于距離的半監(jiān)督聚類算法：Seeded K-Means和Constrained K-Means。兩者的差別在于前者的樣本標簽僅用于初始化，而不參與后續(xù)的聚類過程；后者的標簽樣本在聚類步驟中維持不變，只有非標簽樣本進行聚類。該算法的初始化如下：

2 基于數據清洗的半監(jiān)督聚類算法

由于在半監(jiān)督聚類算法中，seed樣本可能混入噪點，而噪點數據對于IDS來說很有可能是未知攻擊，并且聚類算法對噪點以及孤立點相當敏感，從而造成IDS性能的不穩(wěn)定以及檢測率的降低。為了降低噪點對半監(jiān)督聚類算法的影響，檢測出未知攻擊，提高IDS的檢測率，本文提出對數據樣本預降噪的方法。采用密度聚類算法進行數據清洗，抽取出噪點由管理員進行進一步分析，將剩余的樣本進行聚類，以保持半監(jiān)督聚類算法的穩(wěn)定性。

2.1 數據清洗方法

DBSCAN（density-based spatial clustering of applicationswith noise）是一個比較具有代表性的基于密度的聚類方法，它將簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在有噪點的空間數據集發(fā)現任意形狀的聚類，常用于基于孤立點的聚類分析方法。該算法將不滿足密度分布的點視為噪點數據，將其抽取出來以降低噪點數據對聚類的影響。提出數據清洗的方法旨在于抽取出DBSCAN排除的噪點數據，而不關心DBSCAN的聚類結果。

2.2 算法描述

將數據樣本由DBSCAN進行數據清洗后，從剩余數據樣本中抽取若干正常與異常樣本，作為半監(jiān)督聚類的seed樣本，分別計算質心用于后續(xù)的聚類算法初始化。算法描述如下：

輸入：聚類數目k；抽取正常樣本的比率NorRatio；抽取異常樣本比率AttRatio；seed總數目numSeeds；正常seed數目numNormalSeeds；KDD99樣本D={d1,d2,…,dn}；有標簽的正常樣本；有標簽的異常樣本

輸出：聚類樣本數；SSE；聚類中各類樣本數目。

算法步驟：

Step 1初始化，采用DBScan密度聚類算法對數據集進行分析，抽取出噪點另行分析并從數據集中將其刪除；

Step 4采用K-means算法對數據集進行聚類，并分析算法結果。

3 實驗結果分析

3.1 實驗平臺與數據集

實驗使用的是數據挖掘軟件平臺weka-3-5，數據集使用的是KDD CUP 99[5]。由于數據集過于龐大，本實驗是在10%的子集（kddcup.data_10_percent.gz）中隨機抽取1/25。具體數據如下表1及表2所示。

表1 數據清洗前各類樣本數目Table 1 Number of samples before data cleaning

表2 數據清洗后各類樣本數目Table 2 Number of samples after data cleaning

為驗證算法的穩(wěn)定度，本實驗引入KDD CUP 99數據集中經過糾正標簽的數據集corrected.gz并抽取1/30進行測試，具體數目如表3所示。

表3 corrected數據集Table 3 Corrected data set

3.2 性能評價指標

為了評價聚類算法在入侵檢測中的性能，我們引入聚類及入侵檢測相關統(tǒng)計量：誤差平方和（SSE，sum of squared errors）表示各聚類中樣本的相似度，Centroidi為第i個聚類的質心，該值越低表示聚類的效果越好；檢測率（DR，detection rate），該值越高表示入侵檢測算法的效果越好；誤報率（FPR，false positive rate），該值越低表示入侵檢測算法的效果越好。

3.3 聚類結果

數據集中采用DBSCAN聚類算法進行數據清洗。經過處理，抽取227條噪點樣本，剩余12 124條樣本進行半監(jiān)督聚類分析。其中227條的噪點樣本中，有180條是異常樣本，經過與corrected.gz數據集對比，其中有13條為未知攻擊，降噪效率為85.02%。將剩余的數據集繼續(xù)進行聚類實驗。

表4為在抽取的數據清洗后樣本的聚類的情況。表5為抽取的corrected.gz樣本聚類情況。

表4 kdd cup數據集聚類結果比較Table 4 Comparison of clustering results of kdd cup data set

圖1 kdd cup數據集各算法SSE比較Figure 1 Comparison of each algorithm’s SSE of kdd cup data set

圖2 kdd cup數據集各算法DP比較Figure 2 Comparison of each algorithm’s DP of kdd cup data set

表5 corretced數據集聚類結果比較Table 5 Comparison of clustering results of corrected data set

圖3 corrected數據集各算法FPR值比較Figure3 Comparison ofeach algorithm’sFPRofcorrected data set

圖4 corrected數據集各算法DR值比較Figure 4 Comparison ofeach algorithm’s DR of corrected data set

由實驗結果可知，改進的半監(jiān)督聚類算法在各數據集中都具有較高的效率，由于corrected數據集沒有進行數據清洗，在seed中混入了噪點，因此seeded K Means算法的效率較不穩(wěn)定。

4 小結

基于數據清洗的改進半監(jiān)督聚類算法，通過將數據集進行降噪處理既可以降低噪點對半監(jiān)督聚類算法效率的影響，又可以由噪點中分析出未知攻擊，這對于入侵檢測系統(tǒng)應對攻擊手法不斷更新，病毒特征不斷改變具有重要的意義。實驗結果表明本文提出的改進算法具有較高的效率以及良好的數據集適應度。

[1]LASKOV P，DUSSEL P.Learning intrusion detection：su-pervised or un-supervised[C].Image Analysis and Processing,Proc.of 13th ICIAPConference,2005：50-57.

[2]馮登國，張敏，李昊.大數據安全與隱私保護[J].計算機學報，2014,37(1)：246-258

[3]ZHU X.Semi-supervised learning literature survey[R].University ofWisconsin-Madison Technical Report 1530,Computer Sciences,2005.

[4]BASU S，BANERJEE A.Semi-supervised Clustering by Seeding[C].Proceedings of the 19th International Conference on Machine Learning，2002：19-26.

[5]KDD CUP 99 data[R/OL].(2008-03-28)[2016-04-25]http：//kdd.ics.uci.edu/databases/kddcup99/kddcup99.html.

（責任編輯：葉麗娜）

A Data Cleaning Based on Im proved Sem i-supervised Clustering Algorithm for Intrusion Detection System

ZHOU Zhiping,CHEN Xiaojie
(School of Information engineering，LongYan University，Longyan,Fujian 364000)

A data cleaning based improved semi-supervised clustering algorithm is proposed in this paper in order to overcome the problem for semi-supervised clustering algorithm noise sensitivity.Noise sample in the data setswill be extracted for further analysis.From the data cleaned data sets,we collect sampleswhich are labled normal and abnormal,then calculate them respectively to support the initialization phase of K-Means clustering algorithm.Experimental results show that proposed clustering algorithm has the ability to detect unknown attacks,and has a higher attack detection rate and lower false positive rate.

data cleaning；semi-supervised clustering；intrusion detection

TP393

A

1674－2109(2017)03－0067－05

2016-05-02

龍巖學院青年教師攀登項目（LQ2013008，LQ2014001）。

周志平(1985-)，男，漢族，講師，主要從事計算機網絡、網絡安全的研究。