異常檢測(cè)——高維數(shù)據(jù)異常檢測(cè)
主要內(nèi)容包括：
Feature Bagging
孤立森林
[TOC]
1、引言
在實(shí)際場(chǎng)景中，很多數(shù)據(jù)集都是多維度的庆猫。隨著維度的增加抠璃，數(shù)據(jù)空間的大序讯椤（體積）會(huì)以指數(shù)級(jí)別增長(zhǎng)妹萨，使數(shù)據(jù)變得稀疏孵睬，這便是維度詛咒的難題石窑。維度詛咒不止給異常檢測(cè)帶來(lái)了挑戰(zhàn)牌芋，對(duì)距離的計(jì)算，聚類都帶來(lái)了難題松逊。例如基于鄰近度的方法是在所有維度使用距離函數(shù)來(lái)定義局部性躺屁，但是，在高維空間中经宏，所有點(diǎn)對(duì)的距離幾乎都是相等的（距離集中）犀暑，這使得一些基于距離的方法失效。在高維場(chǎng)景下烁兰，一個(gè)常用的方法是子空間方法耐亏。
集成是子空間思想中常用的方法之一，可以有效提高數(shù)據(jù)挖掘算法精度沪斟。集成方法將多個(gè)算法或多個(gè)基檢測(cè)器的輸出結(jié)合起來(lái)广辰。其基本思想是一些算法在某些子集上表現(xiàn)很好，一些算法在其他子集上表現(xiàn)很好，然后集成起來(lái)使得輸出更加魯棒择吊。集成方法與基于子空間方法有著天然的相似性李根，子空間與不同的點(diǎn)集相關(guān)，而集成方法使用基檢測(cè)器來(lái)探索不同維度的子集几睛，將這些基學(xué)習(xí)器集合起來(lái)房轿。
下面來(lái)介紹兩種常見(jiàn)的集成方法：
2、Feature Bagging
Feature Bagging枉长，基本思想與bagging相似冀续，只是對(duì)象是feature琼讽。feature bagging屬于集成方法的一種必峰。集成方法的設(shè)計(jì)有以下兩個(gè)主要步驟：
1.選擇基檢測(cè)器。這些基本檢測(cè)器可以彼此完全不同钻蹬，或不同的參數(shù)設(shè)置吼蚁，或使用不同采樣的子數(shù)據(jù)集。Feature bagging常用lof算法為基算法问欠。下圖是feature bagging的通用算法：
2.分?jǐn)?shù)標(biāo)準(zhǔn)化和組合方法：不同檢測(cè)器可能會(huì)在不同的尺度上產(chǎn)生分?jǐn)?shù)肝匆。例如，平均k近鄰檢測(cè)器會(huì)輸出原始距離分?jǐn)?shù)顺献，而LOF算法會(huì)輸出歸一化值旗国。另外，盡管一般情況是輸出較大的異常值分?jǐn)?shù)注整，但有些檢測(cè)器會(huì)輸出較小的異常值分?jǐn)?shù)能曾。因此，需要將來(lái)自各種檢測(cè)器的分?jǐn)?shù)轉(zhuǎn)換成可以有意義的組合的歸一化值肿轨。分?jǐn)?shù)標(biāo)準(zhǔn)化之后寿冕，還要選擇一個(gè)組合函數(shù)將不同基本檢測(cè)器的得分進(jìn)行組合，最常見(jiàn)的選擇包括平均和最大化組合函數(shù)椒袍。
下圖是兩個(gè)feature bagging兩個(gè)不同的組合分?jǐn)?shù)方法：
(廣度優(yōu)先)
（累積求和）
?
基探測(cè)器的設(shè)計(jì)及其組合方法都取決于特定集成方法的特定目標(biāo)驼唱。很多時(shí)候，我們無(wú)法得知數(shù)據(jù)的原始分布驹暑，只能通過(guò)部分?jǐn)?shù)據(jù)去學(xué)習(xí)玫恳。除此以外，算法本身也可能存在一定問(wèn)題使得其無(wú)法學(xué)習(xí)到數(shù)據(jù)完整的信息优俘。這些問(wèn)題造成的誤差通常分為偏差和方差兩種京办。
方差：是指算法輸出結(jié)果與算法輸出期望之間的誤差，描述模型的離散程度兼吓，數(shù)據(jù)波動(dòng)性臂港。
偏差：是指預(yù)測(cè)值與真實(shí)值之間的差距。即使在離群點(diǎn)檢測(cè)問(wèn)題中沒(méi)有可用的基本真值。
方差與偏差的選擇：
選擇相對(duì)較好的模型的順序：方差小审孽，偏差小 > 方差小县袱，偏差大 > 方差大，偏差小 > 方差大佑力，偏差大式散。 方差小，偏差大 之所以在實(shí)際中排位相對(duì)靠前打颤，是因?yàn)樗容^穩(wěn)定暴拄。很多時(shí)候?qū)嶋H中無(wú)法獲得非常全面的數(shù)據(jù)集，那么编饺，如果一個(gè)模型在可獲得的樣本上有較小的方差乖篷，說(shuō)明它對(duì)不同數(shù)據(jù)集的敏感度不高，可以期望它對(duì)新數(shù)據(jù)集的預(yù)測(cè)效果比較穩(wěn)定透且。
原知乎地址：https://zhuanlan.zhihu.com/p/44872686
3撕蔼、Isolation Forests
孤立森林（Isolation Forest）算法是周志華教授等人于2008年提出的異常檢測(cè)算法，是機(jī)器學(xué)習(xí)中少見(jiàn)的專門針對(duì)異常檢測(cè)設(shè)計(jì)的算法之一秽誊，方法因?yàn)樵撍惴〞r(shí)間效率高鲸沮，能有效處理高維數(shù)據(jù)和海量數(shù)據(jù)，無(wú)須標(biāo)注樣本锅论，在工業(yè)界應(yīng)用廣泛讼溺。
孤立森林屬于非參數(shù)和無(wú)監(jiān)督的算法，既不需要定義數(shù)學(xué)模型也不需要訓(xùn)練數(shù)據(jù)有標(biāo)簽最易。孤立森林查找孤立點(diǎn)的策略非常高效怒坯。假設(shè)我們用一個(gè)隨機(jī)超平面來(lái)切割數(shù)據(jù)空間，切一次可以生成兩個(gè)子空間耘纱。然后我們繼續(xù)用隨機(jī)超平面來(lái)切割每個(gè)子空間并循環(huán)敬肚，直到每個(gè)子空間只有一個(gè)數(shù)據(jù)點(diǎn)為止。直觀上來(lái)講束析，那些具有高密度的簇需要被切很多次才會(huì)將其分離艳馒，而那些低密度的點(diǎn)很快就被單獨(dú)分配到一個(gè)子空間了。孤立森林認(rèn)為這些很快被孤立的點(diǎn)就是異常點(diǎn)员寇。
用四個(gè)樣本做簡(jiǎn)單直觀的理解弄慰，d是最早被孤立出來(lái)的，所以d最有可能是異常蝶锋。
怎么來(lái)切這個(gè)數(shù)據(jù)空間是孤立森林的核心思想陆爽。因?yàn)榍懈钍请S機(jī)的，為了結(jié)果的可靠性扳缕，要用集成（ensemble）的方法來(lái)得到一個(gè)收斂值慌闭，即反復(fù)從頭開(kāi)始切别威，平均每次切的結(jié)果。孤立森林由t棵孤立的數(shù)組成驴剔，每棵樹(shù)都是一個(gè)隨機(jī)二叉樹(shù)省古，也就是說(shuō)對(duì)于樹(shù)中的每個(gè)節(jié)點(diǎn)，要么有兩個(gè)孩子節(jié)點(diǎn)丧失，要么一個(gè)孩子節(jié)點(diǎn)都沒(méi)有豺妓。樹(shù)的構(gòu)造方法和隨機(jī)森林(random forests)中樹(shù)的構(gòu)造方法有些類似。流程如下：
從訓(xùn)練數(shù)據(jù)中隨機(jī)選擇一個(gè)樣本子集布讹，放入樹(shù)的根節(jié)點(diǎn)琳拭；
隨機(jī)指定一個(gè)屬性，隨機(jī)產(chǎn)生一個(gè)切割點(diǎn)V描验，即屬性A的最大值和最小值之間的某個(gè)數(shù)白嘁；
根據(jù)屬性A對(duì)每個(gè)樣本分類，把A小于V的樣本放在當(dāng)前節(jié)點(diǎn)的左孩子中挠乳，大于等于V的樣本放在右孩子中权薯，這樣就形成了2個(gè)子空間；
在孩子節(jié)點(diǎn)中遞歸步驟2和3睡扬，不斷地構(gòu)造左孩子和右孩子，直到孩子節(jié)點(diǎn)中只有一個(gè)數(shù)據(jù)黍析，或樹(shù)的高度達(dá)到了限定高度卖怜。
獲得t棵樹(shù)之后，孤立森林的訓(xùn)練就結(jié)束阐枣，就可以用生成的孤立森林來(lái)評(píng)估測(cè)試數(shù)據(jù)马靠。
孤立森林檢測(cè)異常的假設(shè)是：異常點(diǎn)一般都是非常稀有的，在樹(shù)中會(huì)很快被劃分到葉子節(jié)點(diǎn)蔼两，因此可以用葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑長(zhǎng)度來(lái)判斷一條記錄是否是異常的甩鳄。和隨機(jī)森林類似，孤立森林也是采用構(gòu)造好的所有樹(shù)的平均結(jié)果形成最終結(jié)果的额划。在訓(xùn)練時(shí)妙啃，每棵樹(shù)的訓(xùn)練樣本是隨機(jī)抽樣的。從孤立森林的樹(shù)的構(gòu)造過(guò)程看俊戳，它不需要知道樣本的標(biāo)簽揖赴，而是通過(guò)閾值來(lái)判斷樣本是否異常。因?yàn)楫惓｜c(diǎn)的路徑比較短抑胎，正常點(diǎn)的路徑比較長(zhǎng)燥滑，孤立森林根據(jù)路徑長(zhǎng)度來(lái)估計(jì)每個(gè)樣本點(diǎn)的異常程度。
路徑長(zhǎng)度計(jì)算方法：
孤立森林也是一種基于子空間的方法阿逃，不同的分支對(duì)應(yīng)于數(shù)據(jù)的不同局部子空間區(qū)域铭拧，較小的路徑對(duì)應(yīng)于孤立子空間的低維
4赃蛛、總結(jié)
1.feature bagging可以降低方差
2.孤立森林的優(yōu)勢(shì)在于：
- 計(jì)算成本相比基于距離或基于密度的算法更小。
- 具有線性的時(shí)間復(fù)雜度搀菩。
- 在處理大數(shù)據(jù)集上有優(yōu)勢(shì)焊虏。
孤立森林不適用于超高維數(shù)據(jù)，因?yàn)楣膭?lì)森林每次都是隨機(jī)選取維度秕磷，如果維度過(guò)高诵闭，則會(huì)存在過(guò)多噪音。
