如何用均值聚類算網路異常入侵

Ⅰ 基於網路的入侵檢測數據集研究

摘要：標記數據集是訓練和評估基於異常的網路入侵檢測系統所必需的。本文對基於網路的入侵檢測數據集進行了重點的文獻綜述，並對基於包和流的底層網路數據進行了詳細的描述。本文確定了15種不同的屬性來評估單個數據集對特定評估場景的適用性。這些屬性涵蓋了廣泛的標准，並被分為五類，例如用於提供結構化搜索的數據量或記錄環境。在此基礎上，對現有數據集進行了全面的綜述。本綜述還強調了每個數據集的特性。此外，本工作還簡要介紹了基於網路的數據的其他來源，如流量生成器和數據存儲庫。最後，我們討論了我們的觀察結果，並為使用和創建基於網路的數據集提供了一些建議。

一、引言

信息技術安全是一個重要的問題，入侵和內部威脅檢測的研究已經投入了大量的精力。在處理與安全相關的數據[1]-[4]、檢測僵屍網路[5]-[8]、埠掃描[9]-[12]、蠻力攻擊[13]-[16]等方面已經發表了許多貢獻。所有這些工作的共同點是，它們都需要具有代表性的基於網路的數據集。此外，基準數據集是評價和比較不同網路入侵檢測系統(NIDS)質量的良好基礎。給定一個帶標簽的數據集，其中每個數據點都被分配給類normal或attack，可以使用檢測到的攻擊數量或虛警數量作為評估標准。

不幸的是，沒有太多具有代表性的數據集。Sommer和Paxson[17](2010)認為，缺乏具有代表性的公共可用數據集是基於異常的入侵檢測面臨的最大挑戰之一。Malowidzki等人(2015)和Haider等人(2017)也發表了類似的聲明。然而，社區正在解決這個問題，因為在過去幾年中已經發布了幾個入侵檢測數據集。其中，澳大利亞網路安全中心發布了UNSW-NB15[20]數據集，科堡大學發布了CIDDS-001[21]數據集，新布倫瑞克大學發布了CICIDS 2017[22]數據集。未來還會有更多數據集發布。然而，現有數據集沒有全面的索引，很難跟蹤最新的發展。

本文對現有的基於網路的入侵檢測數據集進行了文獻綜述。首先，對底層數據進行更詳細的研究。基於網路的數據以基於包或基於流的格式出現。基於流的數據只包含關於網路連接的元信息，而基於包的數據也包含有效負載。然後，對文獻中常用的評價網路數據集質量的不同數據集屬性進行了分析和分組。本調查的主要貢獻是對基於網路的數據集進行了詳盡的文獻綜述，並分析了哪些數據集滿足哪些數據集屬性。本文重點研究了數據集內的攻擊場景，並強調了數據集之間的關系。此外，除了典型的數據集之外，我們還簡要介紹了流量生成器和數據存儲庫作為網路流量的進一步來源，並提供了一些觀察和建議。作為主要的好處，本調查建立了一組數據集屬性，作為比較可用數據集和確定合適數據集的基礎，給出了特定的評估場景。此外，我們創建了一個網站1，其中引用了所有提到的數據集和數據存儲庫，我們打算更新這個網站。

本文的其餘部分組織如下。下一節將討論相關工作。第三部分詳細分析了基於包和流的網路數據。第四部分討論了文獻中常用來評價入侵檢測數據集質量的典型數據集屬性。第五節概述了現有的數據集，並根據第四節確定的屬性檢查每個數據集。第六節簡要介紹了基於網路的數據的進一步來源。在本文件以摘要結束之前，第七節討論了意見和建議。

二、相關工作

本節回顧基於網路的入侵檢測數據集的相關工作。需要注意的是，本文沒有考慮基於主機的入侵檢測數據集，比如ADFA[23]。讀者可以在Glass-Vanderlan等人的[24]中找到關於基於主機的入侵檢測數據的詳細信息。

Malowidzki等人[18]將缺失的數據集作為入侵檢測的一個重要問題進行了討論，對好的數據集提出了要求，並列出了可用的數據集。Koch等人的[25]提供了入侵檢測數據集的另一個概述，分析了13個數據源，並根據8個數據集屬性對它們進行了評估。Nehinbe[26]為IDS和入侵防禦系統(IPS)提供了關鍵的數據集評估。作者研究了來自不同來源的七個數據集(如DARPA數據集和DEFCON數據集)，強調了它們的局限性，並提出了創建更真實數據集的方法。由於在過去的四年中發布了許多數據集，我們延續了2011年到2015年[18]，[25]，[26]的工作，但提供了比我們的前輩更最新和更詳細的概述。

雖然許多數據集論文(如CIDDS-002[27]、ISCX[28]或UGR ' 16[29])只對一些入侵檢測數據集做了一個簡要的概述，但Sharafaldin等人對[30]提供了更詳盡的綜述。他們的主要貢獻是一個生成入侵檢測數據集的新框架。Sharafaldin等人還分析了11個可用的入侵檢測數據集，並根據11個數據集屬性對其進行了評估。與早期的數據集論文相比，我們的工作重點是對現有的基於網路的數據集提供一個中立的概述，而不是提供一個額外的數據集。

最近的其他論文也涉及到基於網路的數據集，但主要關注的焦點有所不同。Bhuyan等人對網路異常檢測進行了全面的綜述。作者描述了現有的9個數據集，並分析了現有異常檢測方法所使用的數據集。類似地，Nisioti等人的[32]關注於用於入侵檢測的無監督方法，並簡要參考了現有的12個基於網路的數據集。Yavanoglu和Aydos[33]分析比較了最常用的入侵檢測數據集。然而，他們的審查只包含七個數據集，包括其他數據集，如HTTP CSIC 2010[34]。總而言之，這些作品往往有不同的研究目標，而且只是接觸對於基於網路的數據集，則略有不同。

三、數據

通常，網路流量以基於包或基於流的格式捕獲。在包級捕獲網路流量通常是通過鏡像網路設備上的埠來完成的。基於包的數據包含完整的有效載荷信息。基於流的數據更加聚合，通常只包含來自網路連接的元數據。Wheelus等人通過一個說明性的比較強調了這一區別:「捕獲包檢查和NetFlow之間的一個很好的區別示例是徒步穿越森林，而不是乘坐熱氣球飛越森林」[35]。在這項工作中，引入了第三類(其他數據)。另一個類別沒有標准格式，並且因每個數據集而異。

A基於分組的數據

基於包的數據通常以pcap格式捕獲，並包含有效負載。可用的元數據取決於使用的網路和傳輸協議。有許多不同的協議，其中最重要的是TCP、UDP、ICMP和IP。圖1顯示出了不同的報頭。TCP是一種可靠的傳輸協議，它包含諸如序列號、確認號、TCP標志或校驗和值之類的元數據。UDP是一種無連接的傳輸協議，它的頭比TCP小，TCP只包含四個欄位，即源埠、目標埠、長度和校驗和。與TCP和UDP相比，ICMP是一個包含狀態消息的支持協議，因此更小。通常，在報頭旁邊還有一個可用的IP報頭傳輸協議的。IP報頭提供源和目標IP地址等信息，如圖1所示。

b .流為基礎數據

基於流的網路數據是一種更簡潔的格式，主要包含關於網路連接的元信息。基於流的數據將所有在時間窗口內共享某些屬性的包聚合到一個流中，通常不包含任何有效負載。默認的五元組定義，即，源IP地址、源埠、目標IP地址、目標埠和傳輸協議[37]，是一種廣泛使用的基於流的數據屬性匹配標准。流可以以單向或雙向格式出現。單向格式將主機A到主機B之間共享上述屬性的所有包聚合到一個流中。從主機B到主機A的所有數據包聚合為另一個單向流。相反，一個雙向流總結了主機a和主機B之間的所有數據包，不管它們的方向如何。

典型的基於流的格式有NetFlow[38]、IPFIX[37]、sFlow[39]和OpenFlow[40]。表I概述了基於流的網路流量中的典型屬性。根據特定的流格式和流導出器，可以提取額外的屬性，如每秒位元組數、每個包的位元組數、第一個包的TCP標志，甚至有效負載的計算熵。

此外，可以使用nfmp2或YAF3之類的工具將基於包的數據轉換為基於流的數據(但不是相反)。讀者如果對流導出器之間的差異感興趣，可以在[41]中找到更多細節，並分析不同的流導出器如何影響僵屍網路分類。

c .其他數據

這個類別包括所有既不是純基於包也不是基於流的數據集。這類的一個例子可能是基於流的數據集，這些數據集已經用來自基於包的數據或基於主機的日誌文件的附加信息進行了豐富。KDD CUP 1999[42]數據集就是這一類別的一個著名代表。每個數據點都有基於網路的屬性，比如傳輸的源位元組數或TCP標志的數量，但是也有基於主機的屬性，比如失敗登錄的數量。因此，這個類別的每個數據集都有自己的一組屬性。由於每個數據集都必須單獨分析，所以我們不對可用屬性做任何一般性的說明。

四、數據集屬性

為了能夠比較不同的入侵檢測數據集，並幫助研究人員為其特定的評估場景找到合適的數據集，有必要將公共屬性定義為評估基礎。因此，我們研究了文獻中用於評估入侵檢測數據集的典型數據集屬性。一般概念FAIR[43]定義了學術數據應該遵循的四個原則實現，即可查找性、可訪問性、互操作性和可重用性。在與這個一般概念相一致的同時，本工作使用更詳細的數據集屬性來提供基於網路的入侵檢測數據集的重點比較。通常，不同的數據集強調不同的數據集屬性。例如，UGR ' 16數據集[29]強調較長的記錄時間來捕捉周期效應，而ISCX數據集[28]強調精確的標記。由於我們的目標是研究基於網路的入侵檢測數據集的更一般的屬性，所以我們試圖統一和概括文獻中使用的屬性，而不是採用所有的屬性。例如，一些方法評估特定類型攻擊的存在，比如DoS(拒絕服務)或瀏覽器注入。某些攻擊類型的存在可能是評估這些特定攻擊類型的檢測方法的相關屬性，但是對於其他方法沒有意義。因此，我們使用一般的屬性攻擊來描述惡意網路流量的存在(見表三)。第五節提供了關於數據集中不同攻擊類型的更多細節，並討論了其他特定的屬性。

我們不像Haider et al.[19]或Sharafaldin et al.[30]那樣開發評估評分，因為我們不想判斷不同數據集屬性的重要性。我們認為，某些屬性的重要性取決於具體的評估場景，不應該在調查中普遍判斷。相反，應該讓讀者能夠找到適合他們需要的數據集。因此，我們將下面討論的數據集屬性分為五類，以支持系統搜索。圖2總結了所有數據集屬性及其值范圍。

A.一般資料

以下四個屬性反映了關於數據集的一般信息，即創建年份、可用性、正常網路流量和惡意網路流量的存在。

1)創建年份:由於網路流量受概念漂移影響，每天都會出現新的攻擊場景，因此入侵檢測數據集的年齡起著重要作用。此屬性描述創建年份。與數據集發布的年份相比，捕獲數據集的底層網路流量的年份與數據集的最新程度更相關。

2)公共可用性:入侵檢測數據集應公開可用，作為比較不同入侵檢測方法的依據。此外，數據集的質量只能由第三方檢查，如果它們是公開可用的。表III包含此屬性的三個不同特徵:yes, o.r. (on request)和no。On request是指在向作者或負責人發送消息後授予訪問許可權。

3)正常用戶行為:此屬性指示數據集中正常用戶行為的可用性，並接受yes或no值。值yes表示數據集中存在正常的用戶行為，但它不聲明是否存在攻擊。一般來說，入侵檢測系統的質量主要取決於其攻擊檢測率和誤報率。此外，正常用戶行為的存在對於評估IDS是必不可少的。然而，缺少正常的用戶行為並不會使數據集不可用，而是表明它必須與其他數據集或真實世界的網路流量合並。這樣的合並步驟通常稱為覆蓋或鹽化[44]、[45]。

4)攻擊流量:IDS數據集應包含各種攻擊場景。此屬性指示數據集中是否存在惡意網路通信，如果數據集中至少包含一次攻擊，則該屬性的值為yes。表四提供了關於特定攻擊類型的附加信息。

B.數據的性質

此類別的屬性描述數據集的格式和元信息的存在。

1)元數據:第三方很難對基於包和基於流的網路流量進行內容相關的解釋。因此，數據集應該與元數據一起提供關於網路結構、IP地址、攻擊場景等的附加信息。此屬性指示附加元數據的存在。

2)格式:網路入侵檢測數據集以不同的格式出現。我們大致將它們分為三種格式(參見第三節)。(1)基於分組的網路流量(例如pcap)包含帶負載的網路流量。(2)基於流的網路流量(如NetFlow)只包含關於網路連接的元信息。(3)其他類型的數據集可能包含基於流的跟蹤，帶有來自基於包的數據甚至來自基於主機的日誌文件的附加屬性。

3)匿名性:由於隱私原因，入侵檢測數據集往往不會公開，或者只能以匿名的形式提供。此屬性指示數據是否匿名以及哪些屬性受到影響。表III中的none值表示沒有執行匿名化。值yes (IPs)表示IP地址要麼被匿名化，要麼從數據集中刪除。同樣，值yes (payload)表示有效負載信息被匿名化，要麼從基於分組的網路流量中刪除。

C.數據量

此類別中的屬性根據容量和持續時間描述數據集。

1) Count:屬性Count將數據集的大小描述為包含的包/流/點的數量或物理大小(GB)。

2)持續時間:數據集應涵蓋較長時間內的網路流量，以捕捉周期性影響(如白天與夜晚或工作日與周末)[29]。屬性持續時間提供每個數據集的記錄時間。

D.記錄環境

此類別中的屬性描述捕獲數據集的網路環境和條件。

1)流量類型:描述網路流量的三種可能來源:真實的、模擬的或合成的。Real是指在有效的網路環境中捕獲真實的網路流量。模擬的意思是在測試床或模擬網路環境中捕獲真實的網路流量。綜合意味著網路流量是綜合創建的(例如，通過一個流量生成器)，而不是由一個真實的(或虛擬的)網路設備捕獲的。

2)網路類型:中小企業的網路環境與互聯網服務提供商(ISP)有著本質的區別。因此，不同的環境需要不同的安全系統，評估數據集應該適應特定的環境。此屬性描述創建相應數據集的基礎網路環境。

3)完整網路:該屬性採用Sharafaldin等人的[30]，表示數據集是否包含來自具有多個主機、路由器等網路環境的完整網路流量。如果數據集只包含來自單個主機(例如蜜罐)的網路流量，或者只包含來自網路流量的一些協議(例如獨佔SSH流量)，則將值設置為no。

E.評價

以下特性與使用基於網路的數據集評估入侵檢測方法有關。更精確地說，這些屬性表示預定義子集的可用性、數據集的平衡和標簽的存在。

1)預定義的分割:有時，即使在相同的數據集上對不同的IDS進行評估，也很難對它們的質量進行比較。在這種情況下，必須明確是否使用相同的子集進行訓練和評估。如果數據集附帶用於訓練和評估的預定義子集，則此屬性提供信息。

2)均衡:基於異常的入侵檢測通常採用機器學習和數據挖掘方法。在這些方法的訓練階段(例如，決策樹分類器)，數據集應該與其類標簽相平衡。因此，數據集應該包含來自每個類(normal和attack)的相同數量的數據點。然而，真實世界的網路流量是不平衡的，它包含了比攻擊流量更多的正常用戶行為。此屬性指示數據集是否與其類標簽相平衡。在使用數據挖掘演算法之前，應該通過適當的預處理來平衡不平衡的數據集。他和Garcia[46]提供了從不平衡數據中學習的良好概述。

3)帶標簽:帶標簽的數據集是訓練監督方法、評估監督和非監督入侵檢測方法所必需的。此屬性表示是否標記了數據集。如果至少有兩個類normal和attack，則將此屬性設置為yes。此屬性中可能的值為:yes, yes with BG。(yes with background)、yes (IDS)、indirect和no。是的，有背景意味著有第三類背景。屬於類背景的包、流或數據點可以是正常的，也可以是攻擊。Yes (IDS)是指使用某種入侵檢測系統來創建數據集的標簽。數據集的一些標簽可能是錯誤的，因為IDS可能不完美。間接意味著數據集沒有顯式標簽，但是可以通過其他日誌文件自己創建標簽。

五、數據集

我們認為，在搜索足夠的基於網路的數據集時，標記的數據集屬性和格式是最決定性的屬性。入侵檢測方法(監督的或非監督的)決定是否需要標簽以及需要哪種類型的數據(包、流或其他)。因此，表II提供了關於這兩個屬性的所有研究的基於網路的數據集的分類。表三給出了關於第四節數據集屬性的基於網路的入侵檢測數據集的更詳細概述。在搜索基於網路的數據集時，特定攻擊場景的存在是一個重要方面。因此，表III顯示了攻擊流量的存在，而表IV提供了數據集中特定攻擊的詳細信息。關於數據集的論文描述了不同抽象級別的攻擊。例如，Vasudevan等人在他們的數據集中(SSENET- 2011)將攻擊流量描述為:「Nmap、Nessus、Angry IP scanner、Port scanner、Metaploit、Backtrack OS、LOIC等是參與者用來發起攻擊的一些攻擊工具。」相比之下，Ring等人在他們的CIDDS-002數據集[27]中指定了執行埠掃描的數量和不同類型。因此，攻擊描述的抽象級別可能在表四中有所不同。對所有攻擊類型的詳細描述超出了本文的范圍。相反，我們推薦感興趣的讀者閱讀Anwar等人的開放存取論文「從入侵檢測到入侵響應系統:基礎、需求和未來方向」。此外，一些數據集是其他數據集的修改或組合。圖3顯示了幾個已知數據集之間的相互關系。

基於網路的數據集，按字母順序排列

AWID [49]。AWID是一個公共可用的數據集4，主要針對802.11網路。它的創建者使用了一個小型網路環境(11個客戶機)，並以基於包的格式捕獲了WLAN流量。在一個小時內，捕獲了3700萬個數據包。從每個數據包中提取156個屬性。惡意網路流量是通過對802.11網路執行16次特定攻擊而產生的。AWID被標記為一個訓練子集和一個測試子集。

Booters[50]。Booters是罪犯提供的分布式拒絕服務(DDoS)攻擊。Santanna et. al[50]發布了一個數據集，其中包括九種不同的啟動程序攻擊的跟蹤，這些攻擊針對網路環境中的一個空路由IP地址執行。結果數據集以基於分組的格式記錄，包含超過250GB的網路流量。單獨的包沒有標記，但是不同的Booters攻擊被分成不同的文件。數據集是公開可用的，但是出於隱私原因，booters的名稱是匿名的。

僵屍網路[5]。僵屍網路數據集是現有數據集的組合，可以公開使用。僵屍網路的創建者使用了[44]的疊加方法來組合ISOT[57]、ISCX 2012[28]和CTU-13[3]數據集的(部分)。結果數據集包含各種僵屍網路和正常用戶行為。僵屍網路數據集被劃分為5.3 GB訓練子集和8.5 GB測試子集，都是基於包的格式。

CIC DoS[51]。CIC DoS是加拿大網路安全研究所的一組數據，可以公開使用。作者的意圖是創建一個帶有應用層DoS攻擊的入侵檢測數據集。因此，作者在應用層上執行了8種不同的DoS攻擊。將生成的跟蹤結果與ISCX 2012[28]數據集的無攻擊流量相結合生成正常的用戶行為。生成的數據集是基於分組的格式，包含24小時的網路流量。

CICIDS 2017 [22]。CICIDS 2017是在模擬環境中歷時5天創建的，包含基於分組和雙向流格式的網路流量。對於每個流，作者提取了80多個屬性，並提供了關於IP地址和攻擊的附加元數據。正常的用戶行為是通過腳本執行的。數據集包含了多種攻擊類型，比如SSH蠻力、heartbleed、僵屍網路、DoS、DDoS、web和滲透攻擊。CICIDS 2017是公開可用的。

cidds - 001 [21]。CIDDS-001數據集是在2017年模擬的小型商業環境中捕獲的，包含為期四周的基於單向流的網路流量，並附帶詳細的技術報告和附加信息。該數據集的特點是包含了一個在互聯網上受到攻擊的外部伺服器。與蜜罐不同，來自模擬環境的客戶機也經常使用此伺服器。正常和惡意的用戶行為是通過在GitHub9上公開可用的python腳本執行的。這些腳本允許不斷生成新的數據集，並可用於其他研究。CIDDS-001數據集是公開可用的，包含SSH蠻力、DoS和埠掃描攻擊，以及從野外捕獲的一些攻擊。

cidds - 002 [27]。CIDDS-002是基於CIDDS-001腳本創建的埠掃描數據集。該數據集包含兩個星期的基於單向流的網路流量，位於模擬的小型業務環境中。CIDDS-002包含正常的用戶行為以及廣泛的不同埠掃描攻擊。技術報告提供了關於外部IP地址匿名化的數據集的附加元信息。數據集是公開可用的。

Ⅱ 異常檢測方法 二

  離群點是一個數據對象，它顯著不同於其他數據對象，好像它是被不同的機制產生的一樣。有時也稱非離群點為「正常數據」，離群點為「異常數據」。
  離群點不同於雜訊數據。雜訊是被觀測變數的隨機誤差或方差。一般而言，雜訊在數據分析（包括離群點分析）中不是令人感興趣的。如在信用卡欺詐檢測，顧客的購買行為可以用一個隨機變數建模。一位顧客可能會產生某些看上去像「隨機誤差」或「方差」的雜訊交易，如買一份較豐盛的午餐，或比通常多要了一杯咖啡。這種交易不應該視為離群點，否則信用卡公司將因驗證太多的交易而付出沉重代價。因此，與許多其他數據分析和數據挖掘任務一樣，應該在離群點檢測前就刪除雜訊。
  離群點檢測是有趣的，因為懷疑產生它們的機制不同於產生其他數據的機制。因此，在離群點檢測時，重要的是搞清楚為什麼檢測到的離群點被某種其他機制產生。通常，在其餘數據上做各種假設，並且證明檢測到的離群點顯著違反了這些假設。

離群點可以分成三類：全局離群點、情境（或條件）離群點和集體離群點。

在給定的數據集中，一個數據對象是全局離群點，如果它顯著的偏離數據集中的其他對象。全局離群點是最簡單的一類離群點，大部分的離群點檢測方法都旨在找出全局離群點。

在給定的數據集中，一個數據對象是情境離群點，如果關於對象的特定情境，它顯著的偏離其他對象。情境離群點又稱為條件離群點，因為它們條件的依賴於選定的情境。一般地，在情境離群點檢測中，所考慮數據對象的屬性劃分成兩組：
情境屬性 ：數據對象的情境屬性定義對象的情境。一般為靜態屬性變數，如信用卡欺詐檢測中，不同年齡、不同地區的人消費情況是不同的，先按照靜態屬性將人群大致分類，再檢測每一類的離群點，會得到更好的結果。
行為屬性 ：定義對象的特徵，並用來評估對象關於它所處的情境是否為離群點。在上述例子中，行為屬性可以是消費金額，消費頻率等
情境離群點分析為用戶提供了靈活性，因為用戶可以在不同情境下考察離群點，這在許多應用中都是非常期望的。

給定一個數據集，數據對象的一個子集形成集體離群點，如果這些對象作為整體顯著的偏離整個數據集。如一家供應鏈公司，每天處理數以千計的訂單和出貨。如果一個訂單的出貨延誤，則可能不是離群點，因為統計表明延誤時常發生。然而，如果有一天有100個訂單延誤，則必須注意。這100個訂單整體來看，形成一個離群點，盡管如果單個考慮，它們每個或許都不是離群點。你可能需要更詳細地整個考察這些訂單，搞清楚出貨問題。
與全局和情境離群點檢測不同，在集體離群點檢測中，不僅必須考慮個體對象的行為，而且還要考慮對象組群的行為。因此，為了檢測集體離群點，需要關於對象之間聯系的背景知識，如對象之間的距離或相似性測量方法。

離群點檢測的統計學方法對數據的正常性做假定。假定數據集中的正常對象由一個隨機過程（生成模型）產生。因此，正常對象出現在該隨機模型的高概率區域中，而低概率區域中的對象是離群點。
離群點檢測的統計學方法的一般思想是：學習一個擬合給定數據集的生成模型，然後識別該模型低概率區域中的對象，把它們作為離群點。有許多不同方法來學習生成模型，一般而言，根據如何指定和如何學習模型，離群點檢測的統計學方法可以劃分成兩個主要類型： 參數方法和非參數方法。
參數方法: 假定正常的數據對象被一個以為參數的參數分布產生。該參數分布的概率密度函數給出對象被該分布產生的概率。該值越小，越可能是離群點。
非參數方法: 並不假定先驗統計模型，而是試圖從輸入數據確定模型。非參數方法的例子包括直方圖和核密度估計。

  假定數據集由一個正態分布產生，然後，可以由輸入數據學習正態分布的參數，並把低概率的點識別為離群點。
  在正態分布的假定下，區域包含99.7%的數據，包含95.4%的數據，包含68.3%的數據。視具體情況而定，將其區域外的數據視為離群點。
  這種直截了當的統計學離群點檢測方法也可以用於可視化。例如盒圖方法使用五數概況繪制一元輸入數據：最小的非離群點值（Min）、第一個四分位數（Q1）、中位數（Q2）、第三個四分位數（Q3）和最大的非離群點值（Max）。
  四分位數極差（IQR）定義為Q3-Q1。比Q1小1.5倍的IQR或者比Q3大1.5倍的IQR的任何對象都視為離群點，因為Q1-1.5 IQR和Q3+1.5 IQR之間的區域包含了99.3%的對象。

（1）使用馬哈拉諾比斯距離檢測多元離群點。
對於一個多元數據集，設為均值向量。對於數據集中的對象，從到的馬哈拉諾比斯（Mahalanobis）距離為其中S是協方差矩陣。是一元數據，可以對它進行離群點檢測。如果被確定為離群點，則也被視為離群點。
（2）使用統計量的多元離群點檢測。
在正態分布的假設下，統計量可以用來捕獲多元離群點。對於對象，統計量是
其中，是在第維上的值，是所有對象在第維上的均值，而是維度。如果對象的統計量很大，則該對象是離群點。
（3）使用混合參數分布
在許多情況下，數據是由正態分布產生的假定很有效。然而，當實際數據很復雜時，這種假定過於簡單。在這種情況下，假定數據是被混合參數分布產生的。
混合參數分布中用期望最大化（EM）演算法來估計參數。具體情況比較復雜，可以參考韓家煒的《數據挖掘：概念與技術》一書。

在離群點檢測的非參數方法中，「正常數據」的模型從輸入數據學習，而不是假定一個先驗。通常，非參數方法對數據做較少假定，因而在更多情況下都可以使用。

使用直方圖檢測離群點
包括如下兩步：
步驟1： 構造直方圖。盡管非參數方法並不假定任何先驗統計模型，但是通常確實要求用戶提供參數，以便由數據學習。如指定直方圖的類型（等寬或等深的）和其他參數（如直方圖中的箱數或每個箱的大小）。與參數方法不同，這些參數並不指定數據分布的類型（如高斯分布）。
步驟2： 檢測離群點。為了確定一個對象是否是離群點，可以對照直方圖檢驗它。在最簡單的方法中，如果該對象落入直方圖的一個箱中，則該對象被看做是正常的，否則被認為是離群點。

對於更復雜的方法，可以使用直方圖賦予每個對象一個離群點得分。一般可以令對象的離群點得分為該對象落入的箱的容積的倒數。得分越高，表明是離群點的概率越大。

使用直方圖作為離群點檢測的非參數模型的一個缺點是，很難選擇一個合適的箱尺寸。一方面，如箱尺寸太小，則由很多正常對象都會落入空的或稀疏箱，因而被誤識別為離群點。這將導致很高的假正例率或低精度。相反，如果箱尺寸太大，則離群點對象可能滲入某些頻繁的箱中，這將導致很高的假負例率或召回率。為了解決這些問題，使用核密度估計來估計數據的概率密度分布。具體參考韓家煒的《數據挖掘：概念與技術》。

  給定特徵空間中的對象集，可以使用距離度量來量化對象間的相似性。基於鄰近性的方法假定：離群點對象與它最近鄰的鄰近性顯著偏離數據集中其他對象與它們近鄰之間的鄰近性。
  有兩種類型的基於鄰近性的離群點檢測方法：基於距離的和基於密度的方法。基於距離的離群點檢測方法考慮對象給定半徑的鄰域。一個對象被認為是離群點，如果它的鄰域內沒有足夠多的其他點。基於密度的離群點檢測方法考察對象和它近鄰的密度。這里，一個對象被識別為離群點，如果它的密度相對於它的近鄰低得多。

對於待分析的數據對象集D，用戶可以指定一個距離閾值r來定義對象的合理鄰域。對於每個對象o，可以考察o的r-鄰域中的其他對象的個數。如果D中大多數對象都遠離o，即都不在o的r-鄰域中，則o可以被視為一個離群點。
令是距離閾值，是分數閾值。對象是一個離群點，如果
其中是距離度量。
如何計算-離群點？一是嵌套循環方法，時間復雜度為。當數據集很大時，該方法的開銷很大。為了改進性能，可以用基於網格的方法來實現。具體見韓家煒《數據挖掘》一書。

基於距離的離群點檢測從全局考慮數據集。由於以下兩個原因，這種離群點被看成「全局離群點」：
l 例如，一個-離群點至少遠離（用參數r定量）數據集中的對象。換言之，這種離群點遠離數據的大多數。
l 為了檢測基於距離的離群點，需要兩個距離參數，它們用於每個離群點對象。
現實世界的許多數據集都呈現更復雜的結構，那裡對象可能關於其局部鄰域，而不是關於整個數據分布而被視為離群點。如下圖，基於距離的離群點檢測方法不能捕獲像o1和o2這樣的局部離群點。
那麼，如何確切地定義如圖所示的局部離群點？這里關鍵的思想是，需要把對象周圍的密度與對象鄰域周圍的密度進行比較。基於密度的離群點檢測方法的基本假定是：非離群點對象周圍的密度與其鄰域周圍的密度類似，而離群點對象周圍的密度顯著不同於其鄰域周圍的密度。

基於聚類的方法通過考察對象與簇之間的關系檢測離群點。直觀地，離群點是一個對象，它屬於小的偏遠簇，或不屬於任何簇。
這導致三種基於聚類的離群點檢測的一般方法。考慮一個對象。
l 該對象屬於某個簇嗎？如果不，則它被識別為離群點。
l 該對象與最近的簇之間的距離很遠嗎？如果是，則它是離群點。
l 該對象是小簇或稀疏簇的一部分嗎?如果是，則該簇中的所有對象都是離群點。

下面對每一種方法考察一個例子。

例1 把離群點檢測為不屬於任何簇的對象。如圖1所示，使用基於密度的聚類方法，如DBSCAN,注意到黑色點都屬於簇，白色點a不屬於任何簇，因而被認為是離群點。

圖1 對象a是離群點，因為 它不屬於任何簇

圖2 離群點（a,b,c）都（關於簇中心）遠離距它們最近的簇

例2 使用到最近簇的距離的基於聚類的離群點檢測。如圖2所示，使用k-均值聚類方法，可以把圖2中的數據點劃分成3個簇，如圖中不同符號所示，每個簇中心用「+」標記。對於每個對象o，都可以根據該對象與最近簇中心的距離，賦予該對象一個離群點得分。假設到o的最近中心為c,則o與c之間的距離為dist(o,c)，c與指派到c的對象之間的平均距離為L,比率度量與平均值的差異程度。在圖2中，點a,b和c都相對遠離它們的對應中心，因而被懷疑是離群點。

例3 檢測小簇中的離群點

迄今為止我們看到的每種方法都只檢測個體離群點，因為它們一次把一個對象與數據集中的簇進行比較。然而，在大型數據中，一些離群點可能是類似的，並且形成一個小簇。例如，在入侵檢測中，使用相同手段攻擊系統的黑客可能形成一個簇。迄今為止所討論的方法可能被這種離群點所欺騙。
為了解決這一問題，第三種基於聚類的離群點檢測方法識別小簇或稀疏簇，並宣告這些簇中的對象也是離群點。這種方法的一個例子是FindCBLOF演算法，其方法如下。

（1） 找出數據集中的簇，並把它們按大小降序排列。該演算法假定大部分數據點都不是離群點，它使用一個參數來區別大簇和小簇。任何至少包含數據集中百分之（如，=90%）數據點的簇都被視為大簇，而其餘的簇被看成小簇。
（2） 對於每個數據點賦予基於簇的局部離群點因子（CBLOF），對於屬於大簇的點，它的CBLOF是簇的大小和該點與簇的相似性的乘積。對於屬於小簇的點，它的CBLOF用小簇的大小和該點與最近的大簇的相似性的乘積計算。
CBLOF用統計學方法定義點和簇之間的相似性，代表點屬於簇的概率。該值越大，點與簇越相似。CBLOF值可以檢測遠離任何簇的離群點。
基於聚類的離群點檢測方法具有如下優點。首先，它們可以檢測離群點，而不要求數據是有標號的，即它們以無監督方式檢測。它們對許多類型的數據都有效。簇可以看成是數據的概括，一旦得到簇，基於聚類的方法只需要把對象與簇進行比較，以確定該對象是否是離群點，這一過程通常很快，因為與對象總數相比，簇的個數通常很小。
基於聚類的方法的缺點是：它的有效性高度依賴於所使用的聚類方法。這些方法對於離群點檢測而言可能不是最優的。對於大型數據集，聚類方法通常開銷很大，這可能成為一個瓶頸。

如果訓練數據具有類標號，則離群點檢測可以看做分類問題。基於分類的離群點檢測方法的一般思想是，訓練一個可以區分「正常」數據和離群點的分類模型。
基於分類的離群點檢測方法通常使用一類模型（單分類模型SVDD），即構造一個僅描述正常類的分類器，不屬於正常類的任何樣本都被視為離群點。
基於分類的方法和基於聚類的方法可以聯合使用，以半監督的方式檢測離群點。
例通過半監督學習檢測離群點

如上圖所示，其中對象被標記為「正常」或「離群點」，或者沒有標號。使用基於聚類的方法，發現一個大簇C和一個小簇C1。因為C中的某些對象攜帶了標號「正常」，因此可以把該簇的所有對象（包括沒有標號的對象）都看做正常對象。在離群點檢測中，使用這個簇的一類模型來識別離群點。類似的，因為簇C1中的某些對象攜帶標號「離群點」，因此宣布C1中的所有對象都是離群點。未落入C模型中的任何對象（如a）也被視為離群點。

與一般的離群點檢測相比，識別情境離群點需要分析對應的情境信息。情境離群點檢測方法可以根據情境是否可以清楚地識別而分成兩類。

這類方法適用於情境可以被清楚識別的情況，其基本思想是把情境離群點檢測問題轉換成典型的離群點檢測問題。具體地說，對於給定的數據對象，用兩步來評估該對象是否是離群點。第一步，使用對象的情境屬性識別對象的情境。第二步，使用一種傳統的離群點檢測方法，估計該對象的離群點得分。

在某些應用中，清楚地把數據劃分成情境是不方便的或不可行的。這時，可以關於情境對正常行為建模。使用一個訓練數據集，這種方法訓練一個模型，關於情境屬性的值，預測期望的行為屬性值。然後，為了確定一個數據對象是否是情境離群點，可以在該對象的情境屬性上使用該模型。如果該對象的行為屬性值顯著地偏離該模型的預測值，則該對象被宣布為情境離群點。
通過使用連接情境和行為的預測模型，這些方法避免直接識別具體情境。許多分類和預測技術都可以用來構建這種模型，如回歸、馬爾科夫模型和有窮狀態自動機等等。

與情境離群點檢測一樣，集體離群點檢測方法也可以劃分為兩類。第一類方法把問題歸結為傳統的離群點檢測。其策略是識別結構單元，把每個結構單元（例如，子序列、時間序列片段、局部區域或子圖）看做是一個數據對象，並提取特徵。這樣，集體離群點檢測問題就轉換成在使用提取的特徵構造的「結構化對象」集上的離群點檢測。一個結構單元代表原數據集中的一組對象，如果該結構單元顯著地偏離提取的特徵空間中的期望趨勢，則它是一個集體離群點。
為集體離群點檢測預先定義結構單元可能是困難的，或者是不可能的。因此，第二類方法直接對結構單元的期望行為建模。例如，為了在時間序列中檢測離群點，一種方法是從序列中學習馬爾科夫模型。因此，一個子序列被宣布為集體離群點，如果它顯著地偏離該模型。

一般地，高維數據的離群點檢測方法應該應對以下挑戰：

l 離群點的解釋：不僅應該能夠識別檢測離群點，而且能夠提供離群點的解釋。離群點的解釋可能是，例如，揭示離群點的特定子空間，或者關於對象的「離群點性」的評估。這種解釋可以幫助用戶理解離群點的含義和意義。
l 數據的稀疏性：這些方法應該能處理高維空間的稀疏性。隨著維度的增加，對象之間的距離嚴重地被雜訊所左右。因此，高維空間中的數據通常是稀疏的。
l 數據子空間：它們應該以合適的方式對離群點建模，例如，自適應現實離群點的子空間和捕獲數據的局部變化。在所有的子空間上使用固定的距離閾值來檢測離群點捕食一種好想法，因為兩個對象之間的距離隨著維度增加而單調增加。
l 關於維度的可伸縮性：隨著維度的增加，子空間的數量指數增加。包含所有可能的子空間的窮舉組合探索不是可伸縮的選擇。
高維數據的離群點檢測方法可以劃分成三種主要方法，包括擴充的傳統離群點檢測、發現子空間中的離群點和對高維離群點建模。

一種高維數據離群點檢測方法是擴充的傳統離群點檢測方法。它使用傳統的基於鄰近性的離群點模型。然而，為了克服高維空間中鄰近性度量惡化問題，它使用其他度量，或構造子空間並在其中檢測離群點。

HilOut演算法就是這種方法的一個例子。HitOut找出基於距離的離群點，但在離群點檢測中使用距離的秩，而不是絕對距離。具體地說，對於每個對象o，HitOut找出o的k個最近鄰，記作nn1(o),nn2(o)……nnk(o),其中k是一個依賴於應用的參數。參數o的權重定義為

所有對象按權重遞減序定秩。權重最高的top-p個對象作為離群點輸出，其中p是另一個用戶指定的參數。

HilOut演算法計算每個對象的k-最近鄰開銷很大，當維度很高並且數據很大時不能伸縮。
另一種方法則是通過維歸約，把高維離群點檢測問題歸結為較低維上的離群點檢測。其基本思想是，把高維空間歸約到低維空間，那裡標準的距離度量仍然能夠區分離群點。如果能夠找到這樣的較低維空間，則可以用傳統的離群點檢測方法。
為了降低維度，可以對離群點檢測使用或擴充一般的特徵特徵選擇和提取方法。例如，可以用主成分分析（PCA）來提取一個低維空間。

高維數據中離群點檢測的另一種方法是搜索各種子空間中的離群點。其唯一的優點是，如果發現一個對象是很低維度的子空間的離群點，則該子空間提供了重要信息，解釋該對象為什麼和在何種程度上是離群點。
如何檢測子空間中的離群點，一種方法是基於網格的子空間離群點檢測。具體做法見韓家煒《數據挖掘》。

另一種方法是試圖直接為高維離群點建立一個新模型。這種方法通常避免鄰近性度量，而是採用新的啟發式方法來檢測離群點。具體做法見韓家煒《數據挖掘》。

Ⅲ 入侵檢測系統的檢測方法

在異常入侵檢測系統中常常採用以下幾種檢測方法： 基於貝葉斯推理檢測法：是通過在任何給定的時刻，測量變數值，推理判斷系統是否發生入侵事件。 基於特徵選擇檢測法：指從一組度量中挑選出能檢測入侵的度量，用它來對入侵行為進行預測或分類。 基於貝葉斯網路檢測法：用圖形方式表示隨機變數之間的關系。通過指定的與鄰接節點相關一個小的概率集來計算隨機變數的聯接概率分布。按給定全部節點組合，所有根節點的先驗概率和非根節點概率構成這個集。貝葉斯網路是一個有向圖，弧表示父、子結點之間的依賴關系。當隨機變數的值變為已知時，就允許將它吸收為證據，為其他的剩餘隨機變數條件值判斷提供計算框架。
基於模式預測的檢測法：事件序列不是隨機發生的而是遵循某種可辨別的模式是基於模式預測的異常檢測法的假設條件，其特點是事件序列及相互聯系被考慮到了，只關心少數相關安全事件是該檢測法的最大優點。 基於統計的異常檢測法：是根據用戶對象的活動為每個用戶都建立一個特徵輪廓表，通過對當前特徵與以前已經建立的特徵進行比較，來判斷當前行為的異常性。用戶特徵輪廓表要根據審計記錄情況不斷更新，其保護去多衡量指標，這些指標值要根據經驗值或一段時間內的統計而得到。 基於機器學習檢測法：是根據離散數據臨時序列學習獲得網路、系統和個體的行為特徵，並提出了一個實例學習法IBL，IBL是基於相似度，該方法通過新的序列相似度計算將原始數據（如離散事件流和無序的記錄）轉化成可度量的空間。然後，應用IBL學習技術和一種新的基於序列的分類方法，發現異常類型事件，從而檢測入侵行為。其中，成員分類的概率由閾值的選取來決定。
數據挖掘檢測法：數據挖掘的目的是要從海量的數據中提取出有用的數據信息。網路中會有大量的審計記錄存在，審計記錄大多都是以文件形式存放的。如果靠手工方法來發現記錄中的異常現象是遠遠不夠的，所以將數據挖掘技術應用於入侵檢測中，可以從審計數據中提取有用的知識，然後用這些知識區檢測異常入侵和已知的入侵。採用的方法有KDD演算法，其優點是善於處理大量數據的能力與數據關聯分析的能力，但是實時性較差。
基於應用模式的異常檢測法：該方法是根據服務請求類型、服務請求長度、服務請求包大小分布計算網路服務的異常值。通過實時計算的異常值和所訓練的閾值比較，從而發現異常行為。
基於文本分類的異常檢測法：該方法是將系統產生的進程調用集合轉換為「文檔」。利用K鄰聚類文本分類演算法，計算文檔的相似性。 誤用入侵檢測系統中常用的檢測方法有： 模式匹配法：是常常被用於入侵檢測技術中。它是通過把收集到的信息與網路入侵和系統誤用模式資料庫中的已知信息進行比較，從而對違背安全策略的行為進行發現。模式匹配法可以顯著地減少系統負擔，有較高的檢測率和准確率。 專家系統法：這個方法的思想是把安全專家的知識表示成規則知識庫，再用推理演算法檢測入侵。主要是針對有特徵的入侵行為。 基於狀態轉移分析的檢測法：該方法的基本思想是將攻擊看成一個連續的、分步驟的並且各個步驟之間有一定的關聯的過程。在網路中發生入侵時及時阻斷入侵行為，防止可能還會進一步發生的類似攻擊行為。在狀態轉移分析方法中，一個滲透過程可以看作是由攻擊者做出的一系列的行為而導致系統從某個初始狀態變為最終某個被危害的狀態。

Ⅳ 聚類演算法

1. 概述

K-means聚類演算法也稱k均值聚類演算法，是集簡單和經典於一身的基於距離的聚類演算法。它採用距離作為相似性的評價指標，即認為兩個對象的距離越近，其相似度就越大。該演算法認為類簇是由距離靠近的對象組成的，因此把得到 緊湊且獨立的簇作為最終目標。

2. 演算法核心思想

K-means聚類演算法是一種迭代求解的聚類分析演算法，其步驟是隨機選取K個對象作為初始的聚類中心，然後計算每個對象與各個種子聚類中心之間的距離，把每個對象分配給距離它最近的聚類中心。聚類中心以及分配給它們的對象就代表一個聚類。每分配一個樣本，聚類的聚類中心會根據聚類中現有的對象被重新計算。這個過程將不斷重復直到滿足某個終止條件。終止條件可以是沒有（或最小數目）對象被重新分配給不同的聚類，沒有（或最小數目）聚類中心再發生變化，誤差平方和局部最小。

3. 演算法實現步驟

1、首先確定一個k值，即我們希望將數據集經過聚類得到k個集合。

2、從數據集中隨機選擇k個數據點作為質心。

3、對數據集中每一個點，計算其與每一個質心的距離（如歐式距離），離哪個質心近，就劃分到那個質心所屬的集合。

4、把所有數據歸好集合後，一共有k個集合。然後重新計算每個集合的質心。

5、如果新計算出來的質心和原來的質心之間的距離小於某一個設置的閾值（表示重新計算的質心的位置變化不大，趨於穩定，或者說收斂），我們可以認為聚類已經達到期望的結果，演算法終止。

6、如果新質心和原質心距離變化很大，需要迭代3~5步驟。

4. 演算法步驟圖解

上圖a表達了初始的數據集，假設k=2。在圖b中，我們隨機選擇了兩個k類所對應的類別質心，即圖中的紅色質心和藍色質心，然後分別求樣本中所有點到這兩個質心的距離，並標記每個樣本的類別為和該樣本距離最小的質心的類別，如圖c所示，經過計算樣本和紅色質心和藍色質心的距離，我們得到了所有樣本點的第一輪迭代後的類別。此時我們對我們當前標記為紅色和藍色的點分別求其新的質心，如圖d所示，新的紅色質心和藍色質心的位置已經發生了變動。圖e和圖f重復了我們在圖c和圖d的過程，即將所有點的類別標記為距離最近的質心的類別並求新的質心。最終我們得到的兩個類別如圖f。

K-means術語：

簇：所有數據的點集合，簇中的對象是相似的。

質心：簇中所有點的中心（計算所有點的中心而來）

5. K-means演算法優缺點

優點：

1、原理比較簡單，實現也是很容易，收斂速度快。

2、當結果簇是密集的，而簇與簇之間區別明顯時, 它的效果較好。

3、主要需要調參的參數僅僅是簇數k。

缺點：

1、K值需要預先給定，很多情況下K值的估計是非常困難的。

2、K-Means演算法對初始選取的質心點是敏感的，不同的隨機種子點得到的聚類結果完全不同 ，對結果影響很大。

3、對噪音和異常點比較的敏感。用來檢測異常值。

4、採用迭代方法，可能只能得到局部的最優解，而無法得到全局的最優解。

Ⅳ 聚類演算法--KMeans

    與分類、序列標注等任務不同，聚類是在事先並不知道任何樣本標簽的情況下，通過數據之間的內在關系把樣本劃分為若干類別，使得同類別樣本之間的相似度高，不同類別之間的樣本相似度低(即增大類內聚，減少類間距)。    

    聚類屬於非監督學習，K均值聚類是最基礎常用的聚類演算法。它的基本思想是，通過迭代尋找K個簇(Cluster)的一種劃分方案，使得聚類結果對應的損失函數最小。其中，損失函數可以定義為各個樣本距離所屬簇中心點的誤差平方和。

其中 代表第i個樣本， 是 所屬的簇，  代表簇對應的中心點，M是樣本總數。

相關概念：

    K值： 要得到的簇的個數。

    質心： 每個簇的均值向量。即向量各維取平均即可。

    距離量度： 常用歐幾里得距離和餘弦相似度(先標准化)。

    KMeans的主要思想是：在給定K值和K個初始類簇中心點的情況下，把每個點(亦即數據記錄)分到離其最近的類簇中心點所代表的類簇中，所有點分配完畢之後，根據一個類簇內的所有點重新計算該類簇的中心點(取平均值)，然後再迭代的進行分配點和更新類簇中心點的步驟，直至類簇中心點的變化很小，或者達到指定的迭代次數。

    KMeans的核心目標是將給定的數據集劃分成K個簇(K是超餐)，並給出每個樣本數據對應的中心點。具體步驟非常簡單：

    （1）首先確定一個K值，即我們希望將數據集經過聚類得到k個集合。

    （2）從數據集中隨機選擇K個數據點作為質心。

    （3）對數據集中每一個點，計算其與每一個質心的距離(如歐式距離)，離哪個質心近，就劃分到哪個質心所屬的集合。

    （4）把所有數據歸好集合後，一共有K個集合。然後重新計算每個集合的質心。

    （5）如果新計算出來的質心和原來的質心之間的距離小於某一個設置的閾值(表示重新計算的質心的位置變化不大，趨於穩定，或者說收斂)，我們可以認為聚類已經達到期望的結果，演算法終止。

    （6）如果新質心和原質心距離變化很大，需要迭代3-5步驟。

KMeans最核心的部分是先固定中心點，調整每個樣本所屬的類別來減少J；再固定每個樣本的類別，調整中心點繼續減小J。兩個過程交替循環，J單調遞減直到極小值，中心點和樣本劃分的類別同時收斂。

KMeans的優點 ：

 高效可伸縮，計算復雜度為O(NKt)接近於線性(N是數據量，K是聚類總數，t是迭代輪數)。

 收斂速度快，原理相對通俗易懂，可解釋性強。

當結果簇是密集的，而簇與簇之間區別是明顯時，他的效果較好。主要需要調參的參數僅僅是簇數K。

缺點 ：

 受初始值和異常點影響，聚類結果可能不是全局最優而是局部最優。K-Means演算法對初始選取的質心點是敏感的，不同的隨機種子點得到的聚類結果完全不同，對結果影響很大。

 K是超參數，一般需要按經驗選擇。

 對噪音和異常點比較的敏感，用來檢測異常值。

 只能發現球狀的簇。在K-Means中，我們用單個點對cluster進行建模，這實際上假設各個cluster的數據是呈高維球型分布的，但是在生活中出現這種情況的概率並不算高。例如，每一個cluster是一個一個的長條狀的，K-Means的則根本識別不出來這種類別( 這種情況可以用GMM )。實際上，K-Means是在做凸優化，因此處理不了非凸的分布。

根據以上特點，我們可以從下面幾個角度對演算法做調優。

（1）數據預處理：歸一化和異常點過濾

    KMeans本質是一種基於歐式距離度量的數據劃分方法，均值和方差大的維度將對數據的聚類結果產生決定性影響 。所以在聚類前對數據( 具體的說是每一個維度的特徵 )做歸一化和單位統一至關重要。此外，異常值會對均值計算產生較大影響，導致 中心偏移 ，這些雜訊點最好能提前過濾。

（2）合理選擇K值

    K值的選擇一般基於實驗和多次實驗結果。例如採用 手肘法 ，嘗試不同K值並將對應的損失函數畫成折線。手肘法認為圖上的 拐點就是K的最佳值 (k=3)。

為了將尋找最佳K值的過程自動化，研究人員提出了Gap Statistic方法。不需要人們用肉眼判斷，只需要找到最大的Gap Statistic對應的K即可。

       損失函數記為  ，當分為K類時，Gap Statistic定義為：  。 是 的期望 ，一般由蒙特卡洛模擬產生。我們在樣本所在的區域內按照均勻分布隨機地產生和原始樣本數一樣多的隨機樣本，並對這個隨機樣本做KMeans，得到一個 ，重復多次就可以計算出 的近似值。

       的物理含義是隨機樣本的損失與實際樣本的損失之差。Gap越大說明聚類的效果越好 。一種極端情況是，隨著K的變化 幾乎維持一條直線保持不變。說明這些樣本間沒有明顯的類別關系，數據分布幾乎和均勻分布一致，近似隨機。此時做聚類沒有意義。

（3）改進初始值的選擇

    之前我們採用隨機選擇K個中心的做法，可能導致不同的中心點距離很近，就需要更多的迭代次數才能收斂。如果在選擇初始中心點時能 讓不同的中心盡可能遠離 ，效果往往更好。這類演算法中，以K-Means++演算法最具影響力。

（4）採用核函數

    主要思想是通過一個非線性映射，將輸入空間中的數據點映射到高維的特徵空間中，並在新的空間進行聚類。非線性映射增加了數據點線性可分的概率(與SVM中使用核函數思想類似)對於非凸的數據分布可以達到更為准確的聚類結果。

 (1）初始的K個質心怎麼選？

    最常用的方法是隨機選，初始質心的選取對最終聚類結果有影響，因此演算法一定要多執行幾次，哪個結果更合理，就用哪個結果。當然也有一些優化的方法，第一種是選擇彼此距離最遠的點，具體來說就是先選第一個點，然後選離第一個點最遠的當第二個點，然後選第三個點，第三個點到第一、第二兩點的距離之和最小，以此類推。第二種是先根據其他聚類演算法(如層次聚類)得到聚類結果，從結果中每個分類選一個點

（2）關於離群值？

    離群值就是遠離整體的，非常異常、非常特殊的數據點，在聚類之前應該將這些"極大""極小"之類的離群數據都去掉，否則會對於聚類的結果有影響。但是，離散值往往自身就很有分析的價值，可以把離群值單獨作為一類來分析。

（3）單位要一致！

（4）標准化

    數據中X整體都比較小，比如都是1到10之間的數，Y很大，比如都是1000以上的數，那麼在計算距離的時候Y起到的作用就比X大很多，X對於距離的影響幾乎可以忽略，這也有問題。因此，如果K-Means聚類中選擇歐幾里得距離計算距離，數據集又出現了上面所述的情況，就一定要進行數據的標准化(normalization)，即將數據按比例縮放，使之落入一個小的特定區間。

    K-Means是無監督學習的聚類演算法，沒有樣本輸出；而KNN是監督學習的分類演算法，有對應的類別輸出 。KNN基本不需要訓練，對測試集裡面的點，只需要找到在訓練集中最近的K個點，用這最近的K個點的類別來決定測試點的類別。而K-Means則有明顯的訓練過程，找到K個類別的最佳質心，從而決定樣本的簇類別。當然，兩者也有一些相似點，兩個演算法都包含一個過程，即找出和某一個點最近的點。 兩周都利用了最近鄰的思想 。

Ⅵ 聚類演算法的具體方法

k-means 演算法接受輸入量 k ；然後將n個數據對象劃分為 k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個「中心對象」（引力中心）來進行計算的。
k-means 演算法的工作過程說明如下：
首先從n個數據對象任意選擇 k 個對象作為初始聚類中心；而對於所剩下其它對象，則根據它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；
然後再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重復這一過程直到標准測度函數開始收斂為止。
一般都採用均方差作為標准測度函數. k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。 K-MEANS有其缺點：產生類的大小相差不會很大，對於臟數據很敏感。
改進的演算法：k—medoids 方法。這兒選取一個對象叫做mediod來代替上面的中心的作用，這樣的一個medoid就標識了這個類。K-medoids和K-means不一樣的地方在於中心點的選取，在K-means中，我們將中心點取為當前cluster中所有數據點的平均值，在 K-medoids演算法中，我們將從當前cluster 中選取這樣一個點——它到其他所有（當前cluster中的）點的距離之和最小——作為中心點。
步驟：
1，任意選取K個對象作為medoids（O1,O2,…Oi…Ok）。
以下是循環的：
2，將餘下的對象分到各個類中去（根據與medoid最相近的原則）；
3，對於每個類（Oi）中，順序選取一個Or，計算用Or代替Oi後的消耗—E（Or）。選擇E最小的那個Or來代替Oi。這樣K個medoids就改變了，下面就再轉到2。
4，這樣循環直到K個medoids固定下來。
這種演算法對於臟數據和異常數據不敏感，但計算量顯然要比K均值要大，一般只適合小數據量。 上面提到K-medoids演算法不適合於大數據量的計算。Clara演算法，這是一種基於采樣的方法，它能夠處理大量的數據。
Clara演算法的思想就是用實際數據的抽樣來代替整個數據，然後再在這些抽樣的數據上利用K-medoids演算法得到最佳的medoids。Clara演算法從實際數據中抽取多個采樣，在每個采樣上都用K-medoids演算法得到相應的（O1, O2 … Oi … Ok），然後在這當中選取E最小的一個作為最終的結果。 Clara演算法的效率取決於采樣的大小，一般不太可能得到最佳的結果。
在Clara演算法的基礎上，又提出了Clarans的演算法，與Clara演算法不同的是：在Clara演算法尋找最佳的medoids的過程中，采樣都是不變的。而Clarans演算法在每一次循環的過程中所採用的采樣都是不一樣的。
與上面所講的尋找最佳medoids的過程不同的是，必須人為地來限定循環的次數。

Ⅶ 簡述入侵檢測常用的四種方法

入侵檢測系統所採用的技術可分為特徵檢測與異常檢測兩種。

1、特徵檢測

特徵檢測(Signature-baseddetection)又稱Misusedetection，這一檢測假設入侵者活動可以用一種模式來表示，系統的目標是檢測主體活動是否符合這些模式。

它可以將已有的入侵方法檢查出來，但對新的入侵方法無能為力。其難點在於如何設計模式既能夠表達「入侵」現象又不會將正常的活動包含進來。

2、異常檢測

異常檢測(Anomalydetection)的假設是入侵者活動異常於正常主體的活動。根據這一理念建立主體正常活動的「活動簡檔」，將當前主體的活動狀況與「活動簡檔」相比較，當違反其統計規律時，認為該活動可能是「入侵」行為。

異常檢測的難題在於如何建立「活動簡檔」以及如何設計統計演算法，從而不把正常的操作作為「入侵」或忽略真正的「入侵」行為。

(7)如何用均值聚類算網路異常入侵擴展閱讀

入侵分類：

1、基於主機

一般主要使用操作系統的審計、跟蹤日誌作為數據源，某些也會主動與主機系統進行交互以獲得不存在於系統日誌中的信息以檢測入侵。

這種類型的檢測系統不需要額外的硬體．對網路流量不敏感，效率高，能准確定位入侵並及時進行反應，但是佔用主機資源，依賴於主機的可靠性，所能檢測的攻擊類型受限。不能檢測網路攻擊。

2、基於網路

通過被動地監聽網路上傳輸的原始流量，對獲取的網路數據進行處理，從中提取有用的信息，再通過與已知攻擊特徵相匹配或與正常網路行為原型相比較來識別攻擊事件。

此類檢測系統不依賴操作系統作為檢測資源，可應用於不同的操作系統平台；配置簡單，不需要任何特殊的審計和登錄機制；可檢測協議攻擊、特定環境的攻擊等多種攻擊。

但它只能監視經過本網段的活動，無法得到主機系統的實時狀態，精確度較差。大部分入侵檢測工具都是基於網路的入侵檢測系統。

3、分布式

這種入侵檢測系統一般為分布式結構，由多個部件組成，在關鍵主機上採用主機入侵檢測，在網路關鍵節點上採用網路入侵檢測，同時分析來自主機系統的審計日誌和來自網路的數據流，判斷被保護系統是否受到攻擊。