網(wǎng)絡(luò)異常檢測(cè)的無監(jiān)督聚類方法

1、Unsupervised clustering approach for networkanomaly detection文獻(xiàn)閱讀筆記論文：網(wǎng)絡(luò)異常檢測(cè)的無監(jiān)督聚類方法本文描述了無監(jiān)督聚類方法在檢測(cè)未知的網(wǎng)絡(luò)入侵或攻擊方面的應(yīng)用。給出了五種聚類 算法和它們?cè)趯?shí)際情況中的具體表現(xiàn)。五種聚類算法分別是：k-Means算法，改進(jìn)的k-Means 算法,k-Medoids算法,EM聚類法和基于距離的孤立點(diǎn)檢測(cè)法。k-Meansk-Means是機(jī)器學(xué)習(xí)中最簡(jiǎn)單的一種聚類算法，算法需要事先定好類別的個(gè)數(shù)K，第一 步是選擇K個(gè)實(shí)例集合作為聚合質(zhì)心，通常每個(gè)集合選擇一個(gè)實(shí)例即可，盡可能遠(yuǎn)的能使 每個(gè)類別分開。

2、具體算法如下：Select the total number of clusters (k)選擇聚合類別的個(gè)數(shù) KChoose random k points and set as centroid隨機(jī)選擇K個(gè)點(diǎn)和集合作為聚心Calculate the distance from each instance to all centroids using Euclidean method 使用歐 幾里德方法計(jì)算每個(gè)實(shí)例到聚心的距離Assign each instance to the closest centroid將每個(gè)實(shí)例分配到距離最近的聚心的集合Recalculate the positi

3、ons of the centroids 重新計(jì)算各個(gè)聚心的位置Repeat step 3-5 until the centroids do not change 重復(fù) 3-5 步，直到聚心不再改變k-Medoidsk-Medoids算法和k-Means類似，但是本算法能將實(shí)例到聚心的距離最小化.一個(gè) medoid定義為用來代表一個(gè)類集的模板數(shù)據(jù)點(diǎn)。k-Means算法對(duì)噪聲和離群值比較健壯。具 體算法如下：Input a data set D consists of n objects 輸入有個(gè) n 對(duì)象的數(shù)據(jù)集 DInput the number of clusters K 輸入聚合類別的個(gè)

4、數(shù) KSelect k objects randomly as the initial cluster centres or cluster medoids 隨機(jī)選擇 K 個(gè) 對(duì)象作為初始化聚心或medoidAssign each object to the cluster with the nearest medoid 將每個(gè)對(duì)象分配到距離最近的 medoid的集合Calculate the total distance between the object and its cluster medoid 計(jì)算對(duì)象到它的 medoid的總距離Swap the medoid with non-m

5、edoid object 交換 medoid 和非 medoidRecalculate the positions of the k medoids 重新計(jì)算 K 個(gè) medoids 的位置Repeat 4-7 until the medoids become fixed 重復(fù) 4-7 步，直到 medoids 不再改變EM ClusteringExpectation Maximization (EM) clustering最大期望聚類法是變種的k-Means算法，廣泛 使用在非監(jiān)督聚類的數(shù)據(jù)點(diǎn)密度估計(jì)上。EM計(jì)算使數(shù)據(jù)的似然值最大的參數(shù)，假定數(shù)據(jù)由 K個(gè)正態(tài)分布生成.，算法同時(shí)得到正態(tài)分布的

6、方法和協(xié)方差。算法需要輸入數(shù)據(jù)集、聚合 的類別個(gè)數(shù)、最大誤差公差、最大迭代次數(shù)。EM可分為兩個(gè)重要過程E過程(E-step)和M過程(M-step).E-step目的是計(jì)算每個(gè)實(shí)例的似然值的期望，然后用它們的概率估計(jì)重新標(biāo)記每個(gè) 實(shí)例。M-step的目的是重新估計(jì)參數(shù)值，輸出參數(shù)值作為下一個(gè)E-step的輸入。兩個(gè)過程反復(fù)迭代計(jì)算，直到結(jié)果收斂。Outlier Detection Algorithms孤立點(diǎn)檢測(cè)(Outlier detection)是為了找到數(shù)據(jù)中不合預(yù)期的行為的數(shù)據(jù)模式。大多 數(shù)的聚類算法雖然不是為所有的點(diǎn)分配類別，但在在計(jì)算中其實(shí)都把噪聲對(duì)象考慮了進(jìn)去。 Outlier d

7、etection算法首先實(shí)現(xiàn)一個(gè)聚類算法然后檢索噪聲集。因此算法的效果取決于聚類 算法的好壞。算法有兩種實(shí)現(xiàn)方式：基于距離的孤立點(diǎn)檢測(cè)和基于密度的孤立點(diǎn)檢測(cè)?；诰嚯x的孤立點(diǎn)檢測(cè)，假設(shè)正常的數(shù)據(jù)對(duì)象有一個(gè)密集的分布區(qū)，孤立點(diǎn)距離那些區(qū) 域很遠(yuǎn)。論文只給出了基于距離的孤立點(diǎn)檢測(cè)算法。通過nested loop (NL)算法來計(jì)算每一 對(duì)兒對(duì)象的距離，而那些遠(yuǎn)離大多數(shù)對(duì)象的則被標(biāo)記為孤立點(diǎn)?；诿芏鹊墓铝Ⅻc(diǎn)檢測(cè)，假設(shè)正常的數(shù)據(jù)對(duì)象的密度與其相鄰分布區(qū)密度相似，孤立點(diǎn) 則大相徑庭。算法通過計(jì)算孤立值來比較這種密度差異。Experimental Setup 實(shí)驗(yàn)過程Intrusion Dataset

8、入侵?jǐn)?shù)據(jù)集試驗(yàn)使用的是NSL-KDD入侵?jǐn)?shù)據(jù)。訓(xùn)練和測(cè)試數(shù)據(jù)都出現(xiàn)的入侵?jǐn)?shù)據(jù)：back, buffer_overflow, ftp_write, guess_passwd, imap,ipsweep, land, loadmodule, multihop, neptune, nmap, phf, pod, portsweep, rootkit, satan, smurf,spy,teardrop,warezclient,warezmaster。只在測(cè)試數(shù)據(jù)中出現(xiàn)的入侵?jǐn)?shù)據(jù)：apache2,httptunnel,mailbomb,mscan,named,perl,processtable,ps,

9、saint,sendmail,snmpgetattac k,snmpguess,sqlattack,udpstorm,worm,xlock,xsnoop,xterm。訓(xùn)練數(shù)據(jù)集包含有25191個(gè)實(shí)例，測(cè)試數(shù)據(jù)集包含有11950個(gè)實(shí)例。四十種不同入侵分為四類：DoS (Denial of Service), R2L (Remote to Local Attack),U2R(User to Root Attack) and Probing Attack,Performance Metric 評(píng)價(jià)指標(biāo)我們使用準(zhǔn)確率和誤報(bào)率作為評(píng)價(jià)指標(biāo):Actual Result 真實(shí)值IntrusionNormal

10、Predicted Result預(yù)測(cè)值IntrusionTrue Positive (TP)False Positive (FP)NormalFalse Negative (FN)True Negative (TN)用如下公式計(jì)算準(zhǔn)確率和錯(cuò)誤率：Accuracy rate = TP+FN(1), False Positive = (2)JTP+TN+FP+FN TP+FP 7Misuse Detection Module 錯(cuò)誤檢測(cè)模塊錯(cuò)誤檢測(cè)模塊包括五個(gè)階段：特征提取 feature extraction降維 dimensionality reduction分類算法 classificatio

11、n algorithms模型應(yīng)用apply model性能測(cè)試和分析 performance measurement & analysis。Anomaly Detection Module 異常檢測(cè)模塊Fig. 2. Anomaly Detection System Design給定一個(gè)訓(xùn)練數(shù)據(jù)集，平均和標(biāo)準(zhǔn)偏差特征向量計(jì)算方法如下:1 Navg_vectorj = instancestd_vectorj= N avg_vectorj)2i=i然后訓(xùn)練集中每個(gè)實(shí)例（特征向量）做如下轉(zhuǎn)換：.rvectorf/lstd_vectorjnew_instancej-Experimental Resul

12、ts and Discussion 實(shí)驗(yàn)結(jié)果及分析6.1Misuse Detection Module 錯(cuò)誤檢測(cè)模塊在第一個(gè)實(shí)驗(yàn)中，我們只使用訓(xùn)練數(shù)據(jù)包含大約22個(gè)不同的類型的已知入侵。結(jié)果見表 所示：AlgorithmAccuracyFalse PositiveNaive BayesS9.59%10,60%Nearest Neighbour99.44%0.60%Rule Induction99.58%0.40%Decision Tree99.56%0.40%表中可見四個(gè)算法中有三個(gè)實(shí)現(xiàn)了高于99%的準(zhǔn)確率和低于1%的誤報(bào)率。效果顯著。在第二個(gè)實(shí)驗(yàn)中，我們使用一個(gè)錯(cuò)誤檢測(cè)模塊的測(cè)試數(shù)據(jù)集評(píng)價(jià)的

13、入侵檢測(cè)模塊的性 能。測(cè)試數(shù)據(jù)含有22種已知的入侵和18種未知的入侵。結(jié)果見表所示：AlgorithmAecu racyFalse PositiveNaive Bayes55.77%34.80%Nearest Neighbour624%20.90%Rule Induction63.69%Decision Tree63.97%17.90%表中可見由于有大量的未知入侵?jǐn)?shù)據(jù)，錯(cuò)誤檢測(cè)模塊效果不是很好。最準(zhǔn)確率僅為 63.97%,最低的誤報(bào)率是17.90%。6.2 Anomaly Detection Module 異常檢測(cè)模塊我們實(shí)現(xiàn)了五種非監(jiān)督聚類算法，分別是： k-Means算法，改進(jìn)的k-Mea

14、ns算法, k-Medoids算法，EM聚類法和基于距離的孤立點(diǎn)檢測(cè)法。使用一個(gè)未標(biāo)記的數(shù)據(jù)集作為輸 入。結(jié)果見下表：AlgorithmAccuracyFalse Positivek-Means57.81%22.95%improved k-Mcans65.40%21.52%k-Mcdoids76.71%2L83%EM clustering78.06%20.74%Distance-based outlier detection80.15%21.14%與上一個(gè)錯(cuò)誤檢測(cè)模塊相比，異常檢測(cè)模塊在檢測(cè)新異常的表現(xiàn)上顯然更好一些。這 些聚類算法能夠在沒有先驗(yàn)知識(shí)的情況下檢測(cè)入侵。實(shí)驗(yàn)中outlier detection算法達(dá)到了最 好的準(zhǔn)確率80.15%,第二好的是EM clustering算法78.06%, k-Medoids達(dá)到76.71%,改進(jìn)的 k-Means達(dá)到65.40%，k-Means達(dá)到57.81%。遺憾的是誤報(bào)率也都超過20%。因此，我們 未來的工作將集中在如何減少誤報(bào)同時(shí)還提高準(zhǔn)確率。各個(gè)算法的執(zhí)行時(shí)間如下圖:把入侵?jǐn)?shù)據(jù)集分類為四個(gè)類型的入侵后，再用outlier detection