1 引言
在實(shí)際場景中，很多數(shù)據(jù)集都是多維度的。隨著維度的增加，數(shù)據(jù)空間的大小（體積）會以指數(shù)級別增長，使數(shù)據(jù)變得稀疏，這便是維度詛咒的難題。維度詛咒不止給異常檢測帶來了挑戰(zhàn)，對距離的計(jì)算，聚類都帶來了難題。例如基于鄰近度的方法是在所有維度使用距離函數(shù)來定義局部性，但是，在高維空間中，所有點(diǎn)對的距離幾乎都是相等的（距離集中），這使得一些基于距離的方法失效。在高維場景下，一個常用的方法是子空間方法。
集成是子空間思想中常用的方法之一，可以有效提高數(shù)據(jù)挖掘算法精度。集成方法將多個算法或多個基檢測器的輸出結(jié)合起來。其基本思想是一些算法在某些子集上表現(xiàn)很好，一些算法在其他子集上表現(xiàn)很好，然后集成起來使得輸出更加魯棒。集成方法與基于子空間方法有著天然的相似性，子空間與不同的點(diǎn)集相關(guān)，而集成方法使用基檢測器來探索不同維度的子集，將這些基學(xué)習(xí)器集合起來。
下面來介紹兩種常見的集成方法：
2.Featrue Bagging
Feature Bagging, 基本思想與bagging相似 ， 只是對feature。 feature bagging屬于集成方法的一種，集成方法的設(shè)計(jì)有以下兩個主要步驟：
1.選擇基檢測器。 這些基本檢測器可以彼此完全不同。或不同的參數(shù)設(shè)置，或采用不同的子數(shù)據(jù)集。Feature bagging常用的lof算法為基算法。
下圖是feature bagging的通用算法：
2.分?jǐn)?shù)標(biāo)準(zhǔn)化和組合方式：不同檢測器可能會在不同的尺度上產(chǎn)生分?jǐn)?shù)。例如，平均k近鄰檢測器會輸出原始距離分?jǐn)?shù)，而LOF算法會輸出歸一化值。另外，盡管一般情況是輸出較大的異常值分?jǐn)?shù)，但有些檢測器會輸出較小的異常值分?jǐn)?shù)。因此，需要將來自各種檢測器的分?jǐn)?shù)轉(zhuǎn)換成可以有意義的組合的歸一化值。分?jǐn)?shù)標(biāo)準(zhǔn)化之后，還要選擇一個組合函數(shù)將不同基本檢測器的得分進(jìn)行組合，最常見的選擇包括平均和最大化組合函數(shù)。
下圖是兩個feature bagging兩個不同的組合分?jǐn)?shù)方法：
基探測器的設(shè)計(jì)及其組合方法都取決于特定集成方法的特定目標(biāo)。很多時候，我們無法得知數(shù)據(jù)的原始分布，只能通過部分?jǐn)?shù)據(jù)去學(xué)習(xí)。除此以外，算法本身也可能存在一定問題使得其無法學(xué)習(xí)到數(shù)據(jù)完整的信息。這些問題造成的誤差通常分為偏差和方差兩種。
方差：是指算法輸出結(jié)果與算法輸出期望之間的誤差，描述模型的離散程度，數(shù)據(jù)波動性。
偏差：是指預(yù)測值與真實(shí)值之間的差距。即使在離群點(diǎn)檢測問題中沒有可用的基本真值
3.Isolation Forests
孤立森林（Isolation Forest）算法是周志華教授等人于2008年提出的異常檢測算法，是機(jī)器學(xué)習(xí)中少見的專門針對異常檢測設(shè)計(jì)的算法之一，方法因?yàn)樵撍惴〞r間效率高，能有效處理高維數(shù)據(jù)和海量數(shù)據(jù)，無須標(biāo)注樣本，在工業(yè)界應(yīng)用廣泛。
孤立森林屬于非參數(shù)和無監(jiān)督的算法，既不需要定義數(shù)學(xué)模型也不需要訓(xùn)練數(shù)據(jù)有標(biāo)簽。孤立森林查找孤立點(diǎn)的策略非常高效。假設(shè)我們用一個隨機(jī)超平面來切割數(shù)據(jù)空間，切一次可以生成兩個子空間。然后我們繼續(xù)用隨機(jī)超平面來切割每個子空間并循環(huán)，直到每個子空間只有一個數(shù)據(jù)點(diǎn)為止。直觀上來講，那些具有高密度的簇需要被切很多次才會將其分離，而那些低密度的點(diǎn)很快就被單獨(dú)分配到一個子空間了。孤立森林認(rèn)為這些很快被孤立的點(diǎn)就是異常點(diǎn)。
用四個樣本做簡單直觀的理解，d是最早被孤立出來的，所以d最有可能是異常。
怎么來切這個數(shù)據(jù)空間是孤立森林的核心思想。因?yàn)榍懈钍请S機(jī)的，為了結(jié)果的可靠性，要用集成（ensemble）的方法來得到一個收斂值，即反復(fù)從頭開始切，平均每次切的結(jié)果。孤立森林由t棵孤立的數(shù)組成，每棵樹都是一個隨機(jī)二叉樹，也就是說對于樹中的每個節(jié)點(diǎn)，要么有兩個孩子節(jié)點(diǎn)，要么一個孩子節(jié)點(diǎn)都沒有。樹的構(gòu)造方法和隨機(jī)森林(random forests)中樹的構(gòu)造方法有些類似。流程如下：
獲得t棵樹之后，孤立森林的訓(xùn)練就結(jié)束，就可以用生成的孤立森林來評估測試數(shù)據(jù)。
孤立森林檢測異常的假設(shè)是：異常點(diǎn)一般都是非常稀有的，在樹中會很快被劃分到葉子節(jié)點(diǎn)，因此可以用葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑長度來判斷一條記錄是否是異常的。和隨機(jī)森林類似，孤立森林也是采用構(gòu)造好的所有樹的平均結(jié)果形成最終結(jié)果的。在訓(xùn)練時，每棵樹的訓(xùn)練樣本是隨機(jī)抽樣的。從孤立森林的樹的構(gòu)造過程看，它不需要知道樣本的標(biāo)簽，而是通過閾值來判斷樣本是否異常。因?yàn)楫惓｜c(diǎn)的路徑比較短，正常點(diǎn)的路徑比較長，孤立森林根據(jù)路徑長度來估計(jì)每個樣本點(diǎn)的異常程度。
路徑長度計(jì)算方法：
孤立森林也是一種基于子空間的方法，不同的分支對應(yīng)于數(shù)據(jù)的不同局部子空間區(qū)域，較小的路徑對應(yīng)于孤立子空間的低維
4.總結(jié)
1.feature bagging可以降低方差
2.孤立森林的優(yōu)勢在于：
計(jì)算成本相比基于距離或基于密度的算法更小。
具有線性的時間復(fù)雜度。
在處理大數(shù)據(jù)集上有優(yōu)勢。
孤立森林不適用于超高維數(shù)據(jù)，因?yàn)楣膭钌置看味际请S機(jī)選取維度，如果維度過高，則會存在過多噪音。
