主要內(nèi)容包括：
- Feature Bagging
孤立森林
練習
1倒慧、引言
在實際場景中摆出，很多數(shù)據(jù)集都是多維度的掖举。隨著維度的增加快骗，數(shù)據(jù)空間的大小（體積）會以指數(shù)級別增長塔次，使數(shù)據(jù)變得稀疏滨巴，這便是維度詛咒的難題。維度詛咒不止給異常檢測帶來了挑戰(zhàn)俺叭，對距離的計算，聚類都帶來了難題泰偿。例如基于鄰近度的方法是在所有維度使用距離函數(shù)來定義局部性熄守，但是，在高維空間中耗跛，所有點對的距離幾乎都是相等的（距離集中）裕照，這使得一些基于距離的方法失效。在高維場景下调塌，一個常用的方法是子空間方法晋南。
集成是子空間思想中常用的方法之一，可以有效提高數(shù)據(jù)挖掘算法精度羔砾。集成方法將多個算法或多個基檢測器的輸出結(jié)合起來负间。其基本思想是一些算法在某些子集上表現(xiàn)很好，一些算法在其他子集上表現(xiàn)很好姜凄，然后集成起來使得輸出更加魯棒政溃。集成方法與基于子空間方法有著天然的相似性，子空間與不同的點集相關态秧，而集成方法使用基檢測器來探索不同維度的子集董虱，將這些基學習器集合起來。
下面來介紹兩種常見的集成方法：
2申鱼、Feature Bagging
Feature Bagging愤诱，基本思想與bagging相似，只是對象是feature捐友。feature bagging屬于集成方法的一種淫半。集成方法的設計有以下兩個主要步驟：
1.選擇基檢測器。這些基本檢測器可以彼此完全不同匣砖，或不同的參數(shù)設置撮慨，或使用不同采樣的子數(shù)據(jù)集竿痰。Feature bagging常用lof算法為基算法。下圖是feature bagging的通用算法：
2.分數(shù)標準化和組合方法：不同檢測器可能會在不同的尺度上產(chǎn)生分數(shù)砌溺。例如影涉，平均k近鄰檢測器會輸出原始距離分數(shù)，而LOF算法會輸出歸一化值规伐。另外蟹倾，盡管一般情況是輸出較大的異常值分數(shù)，但有些檢測器會輸出較小的異常值分數(shù)猖闪。因此鲜棠，需要將來自各種檢測器的分數(shù)轉(zhuǎn)換成可以有意義的組合的歸一化值。分數(shù)標準化之后培慌，還要選擇一個組合函數(shù)將不同基本檢測器的得分進行組合豁陆，最常見的選擇包括平均和最大化組合函數(shù)。
下圖是兩個feature bagging兩個不同的組合分數(shù)方法：
? (廣度優(yōu)先)
? （累積求和）
?
基探測器的設計及其組合方法都取決于特定集成方法的特定目標吵护。很多時候盒音，我們無法得知數(shù)據(jù)的原始分布，只能通過部分數(shù)據(jù)去學習馅而。除此以外祥诽，算法本身也可能存在一定問題使得其無法學習到數(shù)據(jù)完整的信息雄坪。這些問題造成的誤差通常分為偏差和方差兩種维哈。
方差：是指算法輸出結(jié)果與算法輸出期望之間的誤差登澜，描述模型的離散程度帖渠，數(shù)據(jù)波動性。
偏差：是指預測值與真實值之間的差距份招。即使在離群點檢測問題中沒有可用的基本真值
3锁摔、Isolation Forests
孤立森林（Isolation Forest）算法是周志華教授等人于2008年提出的異常檢測算法谐腰，是機器學習中少見的專門針對異常檢測設計的算法之一，方法因為該算法時間效率高励背，能有效處理高維數(shù)據(jù)和海量數(shù)據(jù)砸西，無須標注樣本芹枷，在工業(yè)界應用廣泛。
孤立森林屬于非參數(shù)和無監(jiān)督的算法饱溢，既不需要定義數(shù)學模型也不需要訓練數(shù)據(jù)有標簽绩郎。孤立森林查找孤立點的策略非常高效绿聘。假設我們用一個隨機超平面來切割數(shù)據(jù)空間熄攘，切一次可以生成兩個子空間挪圾。然后我們繼續(xù)用隨機超平面來切割每個子空間并循環(huán)哲思，直到每個子空間只有一個數(shù)據(jù)點為止吩案。直觀上來講徘郭，那些具有高密度的簇需要被切很多次才會將其分離，而那些低密度的點很快就被單獨分配到一個子空間了胧后。孤立森林認為這些很快被孤立的點就是異常點壳快。
用四個樣本做簡單直觀的理解，d是最早被孤立出來的瘤旨，所以d最有可能是異常裆站。
怎么來切這個數(shù)據(jù)空間是孤立森林的核心思想宏胯。因為切割是隨機的肩袍，為了結(jié)果的可靠性婚惫，要用集成（ensemble）的方法來得到一個收斂值先舷，即反復從頭開始切，平均每次切的結(jié)果牲芋。孤立森林由t棵孤立的數(shù)組成缸浦，每棵樹都是一個隨機二叉樹裂逐，也就是說對于樹中的每個節(jié)點卜高，要么有兩個孩子節(jié)點南片，要么一個孩子節(jié)點都沒有铃绒。樹的構(gòu)造方法和隨機森林(random forests)中樹的構(gòu)造方法有些類似。流程如下：
從訓練數(shù)據(jù)中隨機選擇一個樣本子集矮燎，放入樹的根節(jié)點；
隨機指定一個屬性澜沟，隨機產(chǎn)生一個切割點V峡谊，即屬性A的最大值和最小值之間的某個數(shù)；
根據(jù)屬性A對每個樣本分類濒析，把A小于V的樣本放在當前節(jié)點的左孩子中号杏，大于等于V的樣本放在右孩子中斯棒，這樣就形成了2個子空間荣暮；
在孩子節(jié)點中遞歸步驟2和3，不斷地構(gòu)造左孩子和右孩子护赊，直到孩子節(jié)點中只有一個數(shù)據(jù)百揭，或樹的高度達到了限定高度蜓席。
獲得t棵樹之后厨内，孤立森林的訓練就結(jié)束渺贤，就可以用生成的孤立森林來評估測試數(shù)據(jù)志鞍。
孤立森林檢測異常的假設是：異常點一般都是非常稀有的固棚，在樹中會很快被劃分到葉子節(jié)點仙蚜，因此可以用葉子節(jié)點到根節(jié)點的路徑長度來判斷一條記錄是否是異常的委粉。和隨機森林類似贾节，孤立森林也是采用構(gòu)造好的所有樹的平均結(jié)果形成最終結(jié)果的衷畦。在訓練時霎匈，每棵樹的訓練樣本是隨機抽樣的铛嘱。從孤立森林的樹的構(gòu)造過程看，它不需要知道樣本的標簽球匕，而是通過閾值來判斷樣本是否異常亮曹。因為異常點的路徑比較短照卦，正常點的路徑比較長役耕，孤立森林根據(jù)路徑長度來估計每個樣本點的異常程度聪廉。
路徑長度計算方法：
孤立森林也是一種基于子空間的方法板熊，不同的分支對應于數(shù)據(jù)的不同局部子空間區(qū)域，較小的路徑對應于孤立子空間的低維
4津辩、總結(jié)
1.feature bagging可以降低方差
2.孤立森林的優(yōu)勢在于：
- 計算成本相比基于距離或基于密度的算法更小情萤。
- 具有線性的時間復雜度摹恨。
- 在處理大數(shù)據(jù)集上有優(yōu)勢。
孤立森林不適用于超高維數(shù)據(jù)睁宰，因為鼓勵森林每次都是隨機選取維度寝凌，如果維度過高较木，則會存在過多噪音伐债。
5、練習
1.使用PyOD庫生成toy example并調(diào)用feature bagging
contamination = 0.1 # percentage of outliers
n_train = 200 # number of training points
n_test = 100 # number of testing points
# Generate sample data
X_train, y_train, X_test, y_test = \
generate_data(n_train=n_train,
n_test=n_test,
n_features=2,
contamination=contamination,
random_state=42)
# train Feature Bagging detector
clf_name = 'FeatureBagging'
clf = FeatureBagging(check_estimator=False)
clf.fit(X_train)
# get the prediction labels and outlier scores of the training data
y_train_pred = clf.labels_ # binary labels (0: inliers, 1: outliers)
y_train_scores = clf.decision_scores_ # raw outlier scores
# get the prediction on the test data
y_test_pred = clf.predict(X_test) # outlier labels (0 or 1)
y_test_scores = clf.decision_function(X_test) # outlier scores
# evaluate and print the results
print("\nOn Training Data:")
evaluate_print(clf_name, y_train, y_train_scores)
print("\nOn Test Data:")
evaluate_print(clf_name, y_test, y_test_scores)
#On Training Data:
#FeatureBagging ROC:1.0, precision @ rank n:1.0
#On Test Data:
#FeatureBagging ROC:1.0, precision @ rank n:1.0
# visualize the results
visualize(clf_name, X_train, y_train, X_test, y_test, y_train_pred,
y_test_pred, show_figure=True, save_figure=False)
2.使用PyOD庫生成toy example并調(diào)用Isolation Forests
from __future__ import division
from __future__ import print_function
import os
import sys
from pyod.models.iforest import IForest
from pyod.utils.data import generate_data
from pyod.utils.data import evaluate_print
from pyod.utils.example import visualize
contamination = 0.1 # percentage of outliers
n_train = 200 # number of training points
n_test = 100 # number of testing points
# Generate sample data
X_train, y_train, X_test, y_test = \
generate_data(n_train=n_train,
n_test=n_test,
n_features=2,
contamination=contamination,
random_state=42)
# train IForest detector
clf_name = 'IForest'
clf = IForest()
clf.fit(X_train)
# get the prediction labels and outlier scores of the training data
y_train_pred = clf.labels_ # binary labels (0: inliers, 1: outliers)
y_train_scores = clf.decision_scores_ # raw outlier scores
# get the prediction on the test data
y_test_pred = clf.predict(X_test) # outlier labels (0 or 1)
y_test_scores = clf.decision_function(X_test) # outlier scores
# evaluate and print the results
print("\nOn Training Data:")
evaluate_print(clf_name, y_train, y_train_scores)
print("\nOn Test Data:")
evaluate_print(clf_name, y_test, y_test_scores)
#On Training Data:
#IForest ROC:0.9961, precision @ rank n:0.9
#On Test Data:
#IForest ROC:1.0, precision @ rank n:1.0
# visualize the results
visualize(clf_name, X_train, y_train, X_test, y_test, y_train_pred,
y_test_pred, show_figure=True, save_figure=False)
3.(思考題：feature bagging為什么可以降低方差？)
針對上述集成模型魄衅，當各個子模型相同時，
此時不會降低variance。
對應公式：設有n個隨機變量毅访，兩兩變量之間的相關性為??盘榨，則方差為
Bagging對樣本重采樣草巡，對每一重采樣得到的子樣本集訓練一個模型型酥，最后取平均查乒。由于子樣本集有相似性玛迄，同時也使用同種模型棚亩，則各個子模型有相似的bias和variance，由上面結(jié)論可知讥蟆，此時的bias與單模型近似相同，所以bagging不能顯著降低bias修然。（因此在選擇模型時，需要選擇bias小的模型）子模型介于相同與獨立兩個極端情況之間愕宋，所以對應variance會處于var(x) 與 var(x)/n之間结榄，即通過降低上述公式中的第二項降低整體方差。
而根據(jù)模型期望泛化誤差公式雄妥，由于方差的降低，也能帶來最終模型的期望泛化誤差的降低依溯，從而降低過擬合老厌。
作者：小蛋子
鏈接：http://www.reibang.com/p/cffec6353289
來源：簡書
著作權(quán)歸作者所有枝秤。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)淀弹，非商業(yè)轉(zhuǎn)載請注明出處薇溃。
4.(思考題：feature bagging存在哪些缺陷，有什么可以優(yōu)化的idea缭乘？)
雖然Bagging有相當多的優(yōu)點沐序，但是它的缺點也是相當明顯的。在社會科學實驗中提到，”就是參與實驗者彼此之間必須互相獨立“策幼，但是邑时，學習器是根據(jù)分布大致相同的數(shù)據(jù)學習的，自助法可能未必保證學習器之間的相對獨立特姐。同時晶丘，數(shù)據(jù)量少時提升效果不明顯，效率差唐含。
另外铣口，我們采用取平均值或者投票法來得到最后的結(jié)果觉壶，這樣我們就無法針對學習器印象薄弱的”模糊地帶“加強區(qū)分。這就意味著已艰，我們最好能為不同的學習器設置好不同的權(quán)重。同時，集成學習算法更應該是串行的而不是并行的。
6誊稚、參考文獻
[1]Goldstein, M. and Dengel, A., 2012. Histogram-based outlier score (hbos):A fast unsupervised anomaly detection algorithm . InKI-2012: Poster and Demo Track, pp.59-63.
[2]https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/icdm08b.pdf
[3]《Outlier Analysis》——Charu C. Aggarwal
關于Datawhale：
Datawhale是一個專注于數(shù)據(jù)科學與AI領域的開源組織疾瓮，匯集了眾多領域院校和知名企業(yè)的優(yōu)秀學習者，聚合了一群有開源精神和探索精神的團隊成員。Datawhale以“for the learner，和學習者一起成長”為愿景岩瘦，鼓勵真實地展現(xiàn)自我劈伴、開放包容、互信互助、敢于試錯和勇于擔當迷帜。同時Datawhale 用開源的理念去探索開源內(nèi)容锋玲、開源學習和開源方案，賦能人才培養(yǎng)媚污，助力人才成長京髓，建立起人與人备图，人與知識饿肺，人與企業(yè)和人與未來的聯(lián)結(jié)。
