主要內容包括：

• Feature Bagging

• 孤立森林

• 練習

1、引言

在實際場景中，很多數(shù)據(jù)集都是多維度的。隨著維度的增加，數(shù)據(jù)空間的大?。w積）會以指數(shù)級別增長，使數(shù)據(jù)變得稀疏，這便是維度詛咒的難題。維度詛咒不止給異常檢測帶來了挑戰(zhàn)，對距離的計算，聚類都帶來了難題。例如基于鄰近度的方法是在所有維度使用距離函數(shù)來定義局部性，但是，在高維空間中，所有點對的距離幾乎都是相等的（距離集中），這使得一些基于距離的方法失效。在高維場景下，一個常用的方法是子空間方法。

集成是子空間思想中常用的方法之一，可以有效提高數(shù)據(jù)挖掘算法精度。集成方法將多個算法或多個基檢測器的輸出結合起來。其基本思想是一些算法在某些子集上表現(xiàn)很好，一些算法在其他子集上表現(xiàn)很好，然后集成起來使得輸出更加魯棒。集成方法與基于子空間方法有著天然的相似性，子空間與不同的點集相關，而集成方法使用基檢測器來探索不同維度的子集，將這些基學習器集合起來。

下面來介紹兩種常見的集成方法：

2、Feature Bagging

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

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

image.png

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

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

image.png

? (廣度優(yōu)先)

image.png

? （累積求和）

?

基探測器的設計及其組合方法都取決于特定集成方法的特定目標。很多時候，我們無法得知數(shù)據(jù)的原始分布，只能通過部分數(shù)據(jù)去學習。除此以外，算法本身也可能存在一定問題使得其無法學習到數(shù)據(jù)完整的信息。這些問題造成的誤差通常分為偏差和方差兩種。

方差：是指算法輸出結果與算法輸出期望之間的誤差，描述模型的離散程度，數(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最有可能是異常。

image.png

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

1. 從訓練數(shù)據(jù)中隨機選擇一個樣本子集，放入樹的根節(jié)點；

2. 隨機指定一個屬性，隨機產生一個切割點V，即屬性A的最大值和最小值之間的某個數(shù)；

3. 根據(jù)屬性A對每個樣本分類，把A小于V的樣本放在當前節(jié)點的左孩子中，大于等于V的樣本放在右孩子中，這樣就形成了2個子空間；

4. 在孩子節(jié)點中遞歸步驟2和3，不斷地構造左孩子和右孩子，直到孩子節(jié)點中只有一個數(shù)據(jù)，或樹的高度達到了限定高度。

獲得t棵樹之后，孤立森林的訓練就結束，就可以用生成的孤立森林來評估測試數(shù)據(jù)。

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

路徑長度計算方法：

image.png

孤立森林也是一種基于子空間的方法，不同的分支對應于數(shù)據(jù)的不同局部子空間區(qū)域，較小的路徑對應于孤立子空間的低維

4、總結

1.feature bagging可以降低方差

2.孤立森林的優(yōu)勢在于：

• 計算成本相比基于距離或基于密度的算法更小。
• 具有線性的時間復雜度。
• 在處理大數(shù)據(jù)集上有優(yōu)勢。

孤立森林不適用于超高維數(shù)據(jù)，因為鼓勵森林每次都是隨機選取維度，如果維度過高，則會存在過多噪音。

5、練習

1.使用PyOD庫生成toy example并調用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)

image.png

2.使用PyOD庫生成toy example并調用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)

image.png

3.(思考題：feature bagging為什么可以降低方差？)
針對上述集成模型，當各個子模型相同時，

image.png

對應公式：設有n個隨機變量，兩兩變量之間的相關性為??，則方差為

image

Bagging對樣本重采樣，對每一重采樣得到的子樣本集訓練一個模型，最后取平均。由于子樣本集有相似性，同時也使用同種模型，則各個子模型有相似的bias和variance，由上面結論可知，此時的bias與單模型近似相同，所以bagging不能顯著降低bias。（因此在選擇模型時，需要選擇bias小的模型）子模型介于相同與獨立兩個極端情況之間，所以對應variance會處于var(x) 與 var(x)/n之間，即通過降低上述公式中的第二項降低整體方差。

而根據(jù)模型期望泛化誤差公式，由于方差的降低，也能帶來最終模型的期望泛化誤差的降低，從而降低過擬合。

作者：小蛋子
鏈接：http://www.itdecent.cn/p/cffec6353289
來源：簡書
著作權歸作者所有。商業(yè)轉載請聯(lián)系作者獲得授權，非商業(yè)轉載請注明出處。

4.(思考題：feature bagging存在哪些缺陷，有什么可以優(yōu)化的idea？)

雖然Bagging有相當多的優(yōu)點，但是它的缺點也是相當明顯的。在社會科學實驗中提到，”就是參與實驗者彼此之間必須互相獨立“，但是，學習器是根據(jù)分布大致相同的數(shù)據(jù)學習的，自助法可能未必保證學習器之間的相對獨立。同時，數(shù)據(jù)量少時提升效果不明顯，效率差。

另外，我們采用取平均值或者投票法來得到最后的結果，這樣我們就無法針對學習器印象薄弱的”模糊地帶“加強區(qū)分。這就意味著，我們最好能為不同的學習器設置好不同的權重。同時，集成學習算法更應該是串行的而不是并行的。

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 用開源的理念去探索開源內容、開源學習和開源方案，賦能人才培養(yǎng)，助力人才成長，建立起人與人，人與知識，人與企業(yè)和人與未來的聯(lián)結。