【教学课件】第10章异常侦测.ppt

《【教学课件】第10章异常侦测.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第10章异常侦测.ppt（32页珍藏版）》请在三一办公上搜索。

1、,第 10 章異常偵測,2008 台灣培生教育出版(Pearson Education Taiwan),異常偵測,異常偵測的目的，是要在很多物件中找到不同的物件，通常異常的物件為離群值（outliers），因為在資料的分散圖中離群值會遠離其他的資料點 異常偵測（anomaly detection）也稱為偏差偵測（deviation detection），因為異常物件的屬性值會與預期的或基本的屬性值有顯著的偏差；或也稱為例外探勘（exception mining），因為異常在一些觀念中代表的是例外。,異常的應用範例,詐欺偵測（fraud detection）：竊取信用卡者的購買行為可能會與信用卡

2、持有人不同，信用卡公司觀察購買行為模式或注意基本行為的變化，可偵測到竊賊。類似的方法也可用於其他類型的詐欺入侵偵測（intrusion detection）：電腦系統和電腦網路是常見的攻擊行為。部分攻擊是顯而易見的，但如癱瘓電腦和網路的運作並秘密地收集資訊之類的攻擊則是很難偵測的。多數這類的攻擊只要監看系統與網路的異常狀況，即可偵測到生態系統的混亂（ecosystem disturbances）：在真實的世界中，有很多異常事件會對人類造成很大的影響，例如颶風、洪水、乾旱、熱浪與火災。這個目的是要去預測這些事件的可能性以及發生的原因,國民健康（public health）：在許多國家，醫院和醫療

3、診所會對國家級組織報告各種統計資料，以便做進一步的分析。例如，若一個城市中的所有小孩已接種某種疫苗（例如麻疹疫苗），則散佈於不同醫院的少數個案就會是一個異常事件，這也代表這個城市有接種疫苗上的問題醫學（medicine）：針對特定的病患，異常的症狀或測試結果代表潛在的健康問題。然而，一個特定測試結果是否為異常，仍要依照病患的其他特徵，如年齡和性別來進行判斷。此外，結果的分類可能為異常的 若病患是健康的，則不需要額外的測試；而若這個條件是未被診斷或是未處理的，則會對病患有害,異常發生的原因,資料來自不同類別：一個物件可能與其他物件不同，其原因可能是它有不同的類型或類別自然的變動：許多資料集合可以

4、由統計分佈來塑模，例如常態（高斯）分佈，當物件與分佈之中心點的距離增加時，會快速降低資料物件的機率資料測量與收集的錯誤：在資料收集或測量程序中的錯誤是另一種異常來源,異常偵測的方法,以模型為基礎之技術：許多異常偵測技術首先會建立資料的模型，而異常資料通常無法適合這個模型 以鄰近值為基礎之技術：通常必須根據鄰近值來定義物件之間的鄰近值，有一些異常偵測方法是根據這些鄰近值以密度為基礎之技術：如果物件間的鄰近值已知，則物件間的密度可以很容易算出來,類別標記的使用,監督式異常偵測：監督式異常偵測的技術需要訓練集合中存在有異常與正常的物件（要注意的是有一個以上之正常或異常的類別）非監督式異常偵測：在許多

5、實際的情況中，並無類別標記。所以要指定一個分數給每個實例（instance），以反應出這個實例是異常的程度半監督式異常偵測：有時訓練資料包含被標示為正常的資料，且沒有關於異常物件的資訊,處理異常時的重要議題,使用屬性數量來定義異常：根據單一屬性來判斷一個物件是否為異常之問題，和物件屬性值是否有異常之問題一樣全域與區域觀點：一個物件對所有物件可能是獨特的，但對它的區域鄰居之物件卻是很一般的哪個點是異常的程度：在一些技術中以二元方法評估物件是否為異常：物件是異常或不是異常在一個時間中發現一個異常與一次發現很多異常,評估方式：若類別標記可用來發現異常與正常資料，則異常偵測方法的有效性可使用5.7節中

6、的分類效能評估方法來評估效率：各種異常偵測方法的計算成本有顯著的不同。以分類為基礎之方法會要求有效的來源以建立類別模型，但通常成本不高,異常偵測的方法,異常偵測方法包含：統計的、以鄰近值為基礎、以密度為基礎和以群集為基礎等分類,統計的方法,統計的方法是以模型為基礎之方法；針對資料來建立模型，並以物件有多適合這個模型來評估物件大多數用在離群值偵測的統計方法是以所建立的機率分佈模型為基礎，並考慮物件有在這個模型中的可能性一個離群值的機率定義：一個離群值是一個物件，其機率在資料的機率分佈模型中是很低的,辨識一個資料集合中特定之分佈 所使用的屬性數量 混合分佈,偵測離群值的重要議題,在單變量常態分佈中

7、偵測離群值,高斯（常態）分佈是一個最常在統計學中使用的分佈，我們將使用它來描述一個簡單的方法來做統計離群值之偵測,在多變量常態分佈中的離群值,對多變量高斯觀察值而言，我們想要採取的方法會與單變量高斯分佈相似，尤其是如果想要將具有較低機率的資料分類為異常時。此外，我們想要用簡單的檢定的來判斷像是從分佈中心至資料點距離的問題然而因為不同變數（屬性）之間的相關性，多變量常態分佈的中心並不是呈對稱的,異常偵測之混合模型方法,在分群法中，混合模型方法假設資料是來自於混合的機率分佈，且會發現每個群集具有一個分佈。同樣地，針對異常偵測，資料可被塑模為一個具有兩個分佈的混合模型，一個是為正常的資料，而另一個是

8、離群值資料,分群法與異常偵測兩者的主要目的，是要去估計分佈的參數以最大化資料的總概似值（機率）。在分群法中，EM演算法用來估計每個機率分佈的參數，然而，這裡出現的異常偵測技術是一個較簡單的方法。最初，所有的物件會被放到一個正常物件之集合中，而異常物件集是空的，然後一個反覆的步驟會將物件從正常集合轉移換到異常集合，只要有轉移就會增加資料的總概似值,因為正常物件的數量相較於異常物件的數量來的多，當一個物件移到異常集合後，正常物件的分佈並不會改變很多，在這個情況下，每個正常物件對正常物件之總概似值之貢獻將會保持不變,統計方法的優點與缺點,統計方法在處理離群值上已有一個穩定且標準的技術，例如估計分佈的

9、參數。當有足夠的資料知識與檢定類型時，應用這些檢定會變得很有效率，對個別屬性來說，有各種統計離群值之檢定方法對於多變量資料而言的選擇則較少，且這些檢定在多維度資料中可執行結果較差,以鄰近值為基礎之離群值偵測,用來測量物件是否遠離大多數點的一個最簡單的方法，是使用至k個最近鄰居（k-nearest neighbor）的距離 至k個最近鄰居之距離：物件的離群分數是由物件的k個最近鄰居來給定,以鄰近值為基礎之離群值偵測的優點與缺點,以鄰近值為基礎之方法基本上需要O(m2)的時間，對於大量資料集而言，此方法的成本很高此方法對於參數的選擇是敏感的，且無法處理具有很多不同密度區域之資料集合,以密度為基礎之

10、離群值偵測,以密度為基礎之觀點來看，離群值是在低密度區域中的物件以密度為基礎之離群值：物件的離群分數為物件周圍密度之倒數以密度為基礎之離群值偵測會與以鄰近值為基礎之離群值偵測非常相關，因為密度通常被定義為鄰近值。一個常用來定義密度的方法為到k個最近鄰居之平均距離的倒數。若這個距離很小，則密度會很高，反之亦然,以密度為基礎之離群值偵測的優點與缺點,以相對密度為基礎之離群值偵測提供一個數值評估方法，以評估哪個物件為離群值的程度，雖然資料有不同密度區域，此方法仍可以運作得很好參數的選擇也是困難的，雖然標準LOF演算法說明這個問題可以藉由尋找各種k值，然後取最大的離群分數。然而，這仍需要選擇這些值的上

11、限與下限,以分群為基礎之技術,群集分析是找到有很強關聯之物件群集，而異常偵測是找到與其他物件沒有很強關聯之物件用來偵測離群值的一個方法是將遠離其他群集的小群集刪除。這個方法可用在任何分群技術中，但需要最小群集大小之門檻值，以及小群集和其他群集之間距離的門檻值通常刪除所有小於最小值之群集以簡化這個方法的步驟，這個方法會對所選擇之群集數量非常敏感,以分群為基礎之技術,一個更系統化的方法首先會對所有物件分群，然後評估物件屬於任何群集的程度。針對以雛型為基礎之分群法，物件到它的群中心之距離可用來評估一個物件屬於一個群集的程度一般來說，以目標函數為基礎的分群法技術而言，我們可以使用目標函數來評估一個物件

12、屬於群集的程度。若一個物件的移除會造成目標函數有基本的改善，則我們會將這個物件歸類為離群值以分群法為基礎之離群值：若物件沒有很強烈地屬於任何群集，則此物件是群集的離群值,評估哪一個物件屬於群集,針對以雛型為基礎之群集，有一些方法可以評估哪一個物件屬於群集。一個方法是測量物件至群集雛型之距離，並採用這個距離當成物件的離群分數 若群集有不同的密度，則我們會建構離群分數，以測量一個物件至群集雛型，以及至群集中其他物件的相對距離另一個可能性是群集可以正確地用高斯分佈來塑模上，並使用馬氏距離來衡量,以分群法為基礎之範例：點與最近中心點的距離,以分群法為基礎之範例：點與最近中心點之相對距離,離群值對初始分

13、群法的影響,物件被分群，離群值被移除，然後物件再一次分群。雖然這個方法並不保證可以產生最佳結果，但這個方法卻是很容易使用更複雜的方法是有一個特別的群集，其中的物件現在並不適合任何群集，這個群集代表可能的離群值。當分群方法執行時，群集會改變。不強烈屬於任何群集之物件會被加入可能的離群值集合中，而現在已在此集合的物件則會被檢驗。若物件現在屬於一個群集，則會從可能的離群值集合中移除。在分群結束後，仍在這個集合中的物件會被歸類為離群值,使用的群集數量,使用分群法偵測離群值會有一個問題，即分群技術如K-means並不能自動地決定群集數量，因為將物件視為離群值與否是根據群集數量要處理其他的問題並不容易。一個策略是去重複地分析不同數量的群集，另一個方法是去找到很多小的群集，因為（1）小群集較會較有凝聚力，且（2）當有很多小群集，若物件為離群值，則它可能會是真正的離群值缺點是離群值群集來自於小群集，因此很難被偵測出來,分群法偵測離群值的優點與缺點,如K-means之類的分群技術，具有線性或接近線性時間與空間複雜度，因此以這樣的演算法為基礎之離群值偵測技術會很有效率群集的定義通常會與離群值的定義互補，因此要同時找到群集和離群值通常是很有可能的就負面來看，離群值集合的產生及其分數會取決於群集的數量與資料中離群值的出現,