異常檢測學習日志5——高維異常

前言：本博文為DateWhale組隊學習日志記錄，學習周期為半個月，學習内容為異常檢測。

1、引言

在實際場景中，很多資料集都是多元度的。随着次元的增加，資料空間的大小（體積）會以指數級别增長，使資料變得稀疏，這便是次元詛咒的難題。次元詛咒不止給異常檢測帶來了挑戰，對距離的計算，聚類都帶來了難題。例如基于鄰近度的方法是在所有次元使用距離函數來定義局部性，但是，在高維空間中，所有點對的距離幾乎都是相等的（距離集中），這使得一些基于距離的方法失效。在高維場景下，一個常用的方法是子空間方法。

內建是子空間思想中常用的方法之一，可以有效提高資料挖掘算法精度。內建方法将多個算法或多個基檢測器的輸出結合起來。其基本思想是一些算法在某些子集上表現很好，一些算法在其他子集上表現很好，然後內建起來使得輸出更加魯棒。內建方法與基于子空間方法有着天然的相似性，子空間與不同的點集相關，而內建方法使用基檢測器來探索不同次元的子集，将這些基學習器集合起來。

下面來介紹兩種常見的內建方法：

2、Feature Bagging

Feature Bagging，基本思想與bagging相似，隻是對象是feature。feature bagging屬于內建方法的一種。內建方法的設計有以下兩個主要步驟：

1.選擇基檢測器。這些基本檢測器可以彼此完全不同，或不同的參數設定，或使用不同采樣的子資料集。Feature bagging常用lof算法為基算法。下圖是feature bagging的通用算法：

2.分數标準化群組合方法：不同檢測器可能會在不同的尺度上産生分數。例如，平均k近鄰檢測器會輸出原始距離分數，而LOF算法會輸出歸一化值。另外，盡管一般情況是輸出較大的異常值分數，但有些檢測器會輸出較小的異常值分數。是以，需要将來自各種檢測器的分數轉換成可以有意義的組合的歸一化值。分數标準化之後，還要選擇一個組合函數将不同基本檢測器的得分進行組合，最常見的選擇包括平均和最大化組合函數。

下圖是兩個feature bagging兩個不同的組合分數方法：

（廣度優先）

（累計求和）

基探測器的設計及其組合方法都取決于特定內建方法的特定目标。很多時候，我們無法得知資料的原始分布，隻能通過部分資料去學習。除此以外，算法本身也可能存在一定問題使得其無法學習到資料完整的資訊。這些問題造成的誤差通常分為偏差和方差兩種。

方差：是指算法輸出結果與算法輸出期望之間的誤差，描述模型的離散程度，資料波動性。

偏差：是指預測值與真實值之間的差距。即使在離群點檢測問題中沒有可用的基本真值

3、Isolation Forests

孤立森林（Isolation Forest）算法是周志華教授等人于2008年提出的異常檢測算法，是機器學習中少見的專門針對異常檢測設計的算法之一，方法因為該算法時間效率高，能有效處理高維資料和海量資料，無須标注樣本，在工業界應用廣泛。

孤立森林屬于非參數和無監督的算法，既不需要定義數學模型也不需要訓練資料有标簽。孤立森林查找孤立點的政策非常高效。假設我們用一個随機超平面來切割資料空間，切一次可以生成兩個子空間。然後我們繼續用随機超平面來切割每個子空間并循環，直到每個子空間隻有一個資料點為止。直覺上來講，那些具有高密度的簇需要被切很多次才會将其分離，而那些低密度的點很快就被單獨配置設定到一個子空間了。孤立森林認為這些很快被孤立的點就是異常點。

用四個樣本做簡單直覺的了解，d是最早被孤立出來的，是以d最有可能是異常。

怎麼來切這個資料空間是孤立森林的核心思想。因為切割是随機的，為了結果的可靠性，要用內建（ensemble）的方法來得到一個收斂值，即反複從頭開始切，平均每次切的結果。孤立森林由t棵孤立的數組成，每棵樹都是一個随機二叉樹，也就是說對于樹中的每個節點，要麼有兩個孩子節點，要麼一個孩子節點都沒有。樹的構造方法和随機森林(random forests)中樹的構造方法有些類似。流程如下：

（1) 從訓練資料中随機選擇一個樣本子集，放入樹的根節點；

（2) 随機指定一個屬性，随機産生一個切割點V，即屬性A的最⼤值和最小值之間的某個數；

（3) 根據屬性A對每個樣本分類，把A小于V的樣本放在目前節點的左孩子中，大于等于V的樣本放在右

孩子中，這樣就形成了2個子空間；

（4) 在孩子節點中遞歸步驟2和3，不斷地構造左孩子和右孩子，直到孩子節點中隻有一個資料，或樹的

高度達到了限定高度。

獲得t棵樹之後，孤立森林的訓練就結束，就可以用生成的孤立森林來評估測試資料。

孤立森林檢測異常的假設是：異常點一般都是非常稀有的，在樹中會很快被劃分到葉子節點，是以可以用葉子節點到根節點的路徑長度來判斷一條記錄是否是異常的。和随機森林類似，孤立森林也是采用構造好的所有樹的平均結果形成最終結果的。在訓練時，每棵樹的訓練樣本是随機抽樣的。從孤立森林的樹的構造過程看，它不需要知道樣本的标簽，而是通過門檻值來判斷樣本是否異常。因為異常點的路徑比較短，正常點的路徑比較長，孤立森林根據路徑長度來估計每個樣本點的異常程度。

路徑長度計算方法：

孤立森林也是一種基于子空間的方法，不同的分支對應于資料的不同局部子空間區域，較小的路徑對應于孤立子空間的低維

4、總結

1.feature bagging可以降低方差

2.孤立森林的優勢在于：

• 計算成本相比基于距離或基于密度的算法更小。
• 具有線性的時間複雜度。
• 在處理大資料集上有優勢。

孤立森林不适用于超高維資料，因為鼓勵森林每次都是随機選取次元，如果次元過高，則會存在過多噪音。