周志平，陳曉潔

（龍巖學(xué)院信息工程學(xué)院，福建龍巖364000）

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

周志平，陳曉潔

（龍巖學(xué)院信息工程學(xué)院，福建龍巖364000）

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

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

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

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

1 相關(guān)工作

1.1 K-means算法

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

算法描述：

輸入：聚類數(shù)目k。

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

算法步驟：

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

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

Step 3更新簇的平均值；

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

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

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

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

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

2.1 數(shù)據(jù)清洗方法

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

2.2 算法描述

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

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

輸出：聚類樣本數(shù)；SSE；聚類中各類樣本數(shù)目。

算法步驟：

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

Step 4采用K-means算法對數(shù)據(jù)集進行聚類，并分析算法結(jié)果。

3 實驗結(jié)果分析

3.1 實驗平臺與數(shù)據(jù)集

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

表1 數(shù)據(jù)清洗前各類樣本數(shù)目Table 1 Number of samples before data cleaning

表2 數(shù)據(jù)清洗后各類樣本數(shù)目Table 2 Number of samples after data cleaning

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

表3 corrected數(shù)據(jù)集Table 3 Corrected data set

3.2 性能評價指標

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

3.3 聚類結(jié)果

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

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

表4 kdd cup數(shù)據(jù)集聚類結(jié)果比較Table 4 Comparison of clustering results of kdd cup data set

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

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

表5 corretced數(shù)據(jù)集聚類結(jié)果比較Table 5 Comparison of clustering results of corrected data set

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

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

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

4 小結(jié)

基于數(shù)據(jù)清洗的改進半監(jiān)督聚類算法，通過將數(shù)據(jù)集進行降噪處理既可以降低噪點對半監(jiān)督聚類算法效率的影響，又可以由噪點中分析出未知攻擊，這對于入侵檢測系統(tǒng)應(yīng)對攻擊手法不斷更新，病毒特征不斷改變具有重要的意義。實驗結(jié)果表明本文提出的改進算法具有較高的效率以及良好的數(shù)據(jù)集適應(yī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]馮登國，張敏，李昊.大數(shù)據(jù)安全與隱私保護[J].計算機學(xué)報，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

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

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