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

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

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

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

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

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

7、etection算法首先實現一個聚類算法然后檢索噪聲集。因此算法的效果取決于聚類 算法的好壞。算法有兩種實現方式：基于距離的孤立點檢測和基于密度的孤立點檢測。基于距離的孤立點檢測，假設正常的數據對象有一個密集的分布區，孤立點距離那些區 域很遠。論文只給出了基于距離的孤立點檢測算法。通過nested loop (NL)算法來計算每一 對兒對象的距離，而那些遠離大多數對象的則被標記為孤立點。基于密度的孤立點檢測，假設正常的數據對象的密度與其相鄰分布區密度相似，孤立點 則大相徑庭。算法通過計算孤立值來比較這種密度差異。Experimental Setup 實驗過程Intrusion Dataset

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

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

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

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

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

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

14、ns算法, k-Medoids算法，EM聚類法和基于距離的孤立點檢測法。使用一個未標記的數據集作為輸 入。結果見下表：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%與上一個錯誤檢測模塊相比，異常檢測模塊在檢測新異常的表現上顯然更好一些。這 些聚類算法能夠在沒有先驗知識的情況下檢測入侵。實驗中outlier detection算法達到了最 好的準確率80.15%,第二好的是EM clustering算法78.06%, k-Medoids達到76.71%,改進的 k-Means達到65.40%，k-Means達到57.81%。遺憾的是誤報率也都超過20%。因此，我們 未來的工作將集中在如何減少誤報同時還提高準確率。各個算法的執行時間如下圖:把入侵數據集分類為四個類型的入侵后，再用outlier detection