1、引言

在实际场景中，很多数据集都是多维度的。随着维度的增加，数据空间的大小（体积）会以指数级别增长，使数据变得稀疏，这便是维度诅咒的难题。维度诅咒不止给异常检测带来了挑战，对距离的计算，聚类都带来了难题。例如基于邻近度的方法是在所有维度使用距离函数来定义局部性，但是，在高维空间中，所有点对的距离几乎都是相等的（距离集中），这使得一些基于距离的方法失效。在高维场景下，一个常用的方法是子空间方法。

集成是子空间思想中常用的方法之一，可以有效提高数据挖掘算法精度。集成方法将多个算法或多个基检测器的输出结合起来。其基本思想是一些算法在某些子集上表现很好，一些算法在其他子集上表现很好，然后集成起来使得输出更加鲁棒。集成方法与基于子空间方法有着天然的相似性，子空间与不同的点集相关，而集成方法使用基检测器来探索不同维度的子集，将这些基学习器集合起来。下面来介绍两种常见的集成方法：

2、Feature Bagging

Feature Bagging，基本思想与bagging相似，只是对象是feature。feature bagging属于集成方法的一种。集成方法的设计有以下两个主要步骤：
Bagging算法 （英语：Bootstrap aggregating，引导聚集算法），又称装袋算法，是机器学习领域的一种团体学习算法。最初由Leo Breiman于1996年提出。Bagging算法可与其他分类、回归算法结合，提高其准确率、稳定性的同时，通过降低结果的方差，避免过拟合的发生。

随机采样(bootsrap)就是从我们的训练集里面采集固定个数的样本，但是每采集一个样本后，都将样本放回。也就是说，之前采集到的样本在放回后有可能继续被采集到。对于我们的Bagging算法，一般会随机采集和训练集样本数m一样个数的样本。这样得到的采样集和训练集样本的个数相同，但是样本内容不同。如果我们对有m个样本训练集做T次的随机采样，，则由于随机性，T个采样集各不相同。 　　　　注意到这和GBDT的子采样是不同的。GBDT的子采样是无放回采样，而Bagging的子采样是放回采样。 　　　　对于一个样本，它在某一次含m个样本的训练集的随机采样中，每次被采集到的概率是五、高维数据的异常检测 - 图1。不被采集到的概率为五、高维数据的异常检测 - 图2。如果五、高维数据的异常检测 - 图3次采样都没有被采集中的概率是五、高维数据的异常检测 - 图4。当五、高维数据的异常检测 - 图5时，五、高维数据的异常检测 - 图6也就是说，在bagging的每轮随机采样中，训练集中大约有36.8%的数据没有被采样集采集中。 　　　　对于这部分大约36.8%的没有被采样到的数据，我们常常称之为袋外数据(Out Of Bag, 简称OOB)。这些数据没有参与训练集模型的拟合，因此可以用来检测模型的泛化能力。 　　　　bagging对于弱学习器没有限制，这和Adaboost一样。但是最常用的一般也是决策树和神经网络。 　　　　bagging的集合策略也比较简单，对于分类问题，通常使用简单投票法，得到最多票数的类别或者类别之一为最终的模型输出。对于回归问题，通常使用简单平均法，对T个弱学习器得到的回归结果进行算术平均得到最终的模型输出。 　　　　由于Bagging算法每次都进行采样来训练模型，因此泛化能力很强，对于降低模型的方差很有作用。当然对于训练集的拟合程度就会差一些，也就是模型的偏倚会大一些。 来源https://www.cnblogs.com/pinard/p/6156009.html

1.选择基检测器。这些基本检测器可以彼此完全不同，或不同的参数设置，或使用不同采样的子数据集。Feature bagging常用lof算法为基算法。下图是feature bagging的通用算法：
五、高维数据的异常检测 - 图7

  • 给定：五、高维数据的异常检测 - 图8，标签五、高维数据的异常检测 - 图9 ，五、高维数据的异常检测 - 图10为离群值，五、高维数据的异常检测 - 图11 为正常值。五、高维数据的异常检测 - 图12对应向量五、高维数据的异常检测 - 图13的维数（特征数）
  • 标准化数据集五、高维数据的异常检测 - 图14
  • 对于五、高维数据的异常检测 - 图15
    1. 在五、高维数据的异常检测 - 图16和五、高维数据的异常检测 - 图17中，均匀随机选取特征子集大小五、高维数据的异常检测 - 图18。
    2. 创建一个特征子集五、高维数据的异常检测 - 图19，不进行放回的前提下，随机选取五、高维数据的异常检测 - 图20个特征
    3. 利用特征子集五、高维数据的异常检测 - 图21，应用离群检测算法五、高维数据的异常检测 - 图22
    4. 离群点检测算法五、高维数据的异常检测 - 图23的输出为异常分数向量五、高维数据的异常检测 - 图24
  • 将整合异常得分向量五、高维数据的异常检测 - 图25，并输出最终异常得分向量 五、高维数据的异常检测 - 图26五、高维数据的异常检测 - 图27
    2.分数标准化和组合方法**：不同检测器可能会在不同的尺度上产生分数。例如，平均k近邻检测器会输出原始距离分数，而LOF算法会输出归一化值。另外，尽管一般情况是输出较大的异常值分数，但有些检测器会输出较小的异常值分数。因此，需要将来自各种检测器的分数转换成可以有意义的组合的归一化值。分数标准化之后，还要选择一个组合函数将不同基本检测器的得分进行组合，最常见的选择包括平均和最大化组合函数。

下图是两个feature bagging两个不同的组合分数方法：
image.png
广度优先
image.png
累计求和
**
基探测器的设计及其组合方法都取决于特定集成方法的特定目标。很多时候，我们无法得知数据的原始
分布，只能通过部分数据去学习。除此以外，算法本身也可能存在一定问题使得其无法学习到数据完整
的信息。这些问题造成的误差通常分为偏差和方差两种。

方差：是指算法输出结果与算法输出期望之间的误差，描述模型的离散程度，数据波动性。 偏差：是指预测值与真实值之间的差距。即使在离群点检测问题中没有可用的基本真值

3、Isolation Forests

孤立森林（Isolation Forest）算法是周志华教授等人于2008年提出的异常检测算法，是机器学习中少见的专门针对异常检测设计的算法之一，方法因为该算法时间效率高，能有效处理高维数据和海量数据，无须标注样本，在工业界应用广泛。

孤立森林属于非参数和无监督的算法，既不需要定义数学模型也不需要训练数据有标签。孤立森林查找孤立点的策略非常高效。假设我们用一个随机超平面来切割数据空间，切一次可以生成两个子空间。然后我们继续用随机超平面来切割每个子空间并循环，直到每个子空间只有一个数据点为止。直观上来讲，那些具有高密度的簇需要被切很多次才会将其分离，而那些低密度的点很快就被单独分配到一个子空间了。孤立森林认为这些很快被孤立的点就是异常点。

用四个样本做简单直观的理解，d是最早被孤立出来的，所以d最有可能是异常。
image.png
怎么来切这个数据空间是孤立森林的核心思想。因为切割是随机的，为了结果的可靠性，要用集成（ensemble）的方法来得到一个收敛值，即反复从头开始切，平均每次切的结果。孤立森林由t棵孤立的数组成，每棵树都是一个随机二叉树，也就是说对于树中的每个节点，要么有两个孩子节点，要么一个孩子节点都没有。树的构造方法和随机森林(random forests)中树的构造方法有些类似。流程如下：

  1. 从训练数据中随机选择一个样本子集，放入树的根节点；
  2. 随机指定一个属性，随机产生一个切割点V，即属性A的最大值和最小值之间的某个数；
  3. 根据属性A对每个样本分类，把A小于V的样本放在当前节点的左孩子中，大于等于V的样本放在右孩子中，这样就形成了2个子空间；
  4. 在孩子节点中递归步骤2和3，不断地构造左孩子和右孩子，直到子节点中只有一个数据，或树的高度达到了限定高度。

获得t棵树之后，孤立森林的训练就结束，就可以用生成的孤立森林来评估测试数据。

孤立森林检测异常的假设是：异常点一般都是非常稀有的，在树中会很快被划分到叶子节点，因此可以
用叶子节点到根节点的路径长度来判断一条记录是否是异常的。和随机森林类似，孤立森林也是采用构
造好的所有树的平均结果形成最终结果的。在训练时，每棵树的训练样本是随机抽样的。从孤立森林的
树的构造过程看，它不需要知道样本的标签，而是通过阈值来判断样本是否异常。因为异常点的路径比
较短，正常点的路径比较长，孤立森林根据路径长度来估计每个样本点的异常程度。
路径长度计算方法：
image.png
孤立森林也是一种基于子空间的方法，不同的分支对应于数据的不同局部子空间区域，较小的路径对应
于孤立子空间的低维

4、总结

1.feature bagging可以降低方差
2.孤立森林的优势在于：

  • 计算成本相比基于距离或基于密度的算法更小。
  • 具有线性的时间复杂度。
  • 在处理大数据集上有优势。

孤立森林不适用于超高维数据，因为鼓励森林每次都是随机选取维度，如果维度过高，则会存在过多噪
音。

5、练习

1.使用PyOD库生成toy example并调用feature bagging

  1. from pyod.models.feature_bagging import FeatureBagging
  2. from pyod.utils.data import generate_data
  3. from pyod.utils.data import evaluate_print
  4. from pyod.utils.example import visualize
  6. if __name__ == "__main__":
  7.     contamination = 0.05  # percentage of outliers
  8.     n_train = 4000  # number of training points
  9.     n_test = 1000  # number of testing points
  11.     # Generate sample data
  12.     X_train, y_train, X_test, y_test = \
  13.         generate_data(n_train=n_train,
  14.                       n_test=n_test,
  15.                       n_features=2,
  16.                       contamination=contamination,
  17.                       random_state=42)
  19.     # train LOF detector
  20.     clf_name = 'FeatureBagging'
  21.     clf = FeatureBagging()
  22.     clf.fit(X_train)
  24.     # get the prediction labels and outlier scores of the training data
  25.     y_train_pred = clf.labels_  # binary labels (0: inliers, 1: outliers)
  26.     y_train_scores = clf.decision_scores_  # raw outlier scores
  28.     # get the prediction on the test data
  29.     y_test_pred = clf.predict(X_test)  # outlier labels (0 or 1)
  30.     y_test_scores = clf.decision_function(X_test)  # outlier scores
  32.     # evaluate and print the results
  33.     print("\nOn Training Data:")
  34.     evaluate_print(clf_name, y_train, y_train_scores)
  35.     print("\nOn Test Data:")
  36.     evaluate_print(clf_name, y_test, y_test_scores)
  38.     # visualize the results
  39.     visualize(clf_name, X_train, y_train, X_test, y_test, y_train_pred,
  40.               y_test_pred, show_figure=True, save_figure=False)

On Training Data: FeatureBagging ROC:0.5717, precision @ rank n:0.19

On Test Data: FeatureBagging ROC:0.482, precision @ rank n:0.1 拟合效果很一般。

image.png
按照队长的参数进行调优之后，传送门https://www.yuque.com/u8039732/dfqrpz/xrr38o
算了，也差不多。。。。

2.使用PyOD库生成toy example并调用Isolation Forests

  1. from pyod.models.iforest import IForest
  2. from pyod.utils.data import generate_data
  3. from pyod.utils.data import evaluate_print
  6. contamination = 0.05  # 异常值的比例
  7. n_train = 80000  # 训练集样本容量
  8. n_test = 20000  # 测试样本容量
  10. # 生成样本数据集
  11. X_train, y_train, X_test, y_test =  generate_data(n_train=n_train, n_test=n_test,
  12.                                                    n_features=20,  contamination=contamination,
  13.                                                    random_state=42)
  14. # 模型训练
  15. model_name = 'IForest'
  16. model = IForest()  
  17. model.fit(X_train)
  19. y_train_pred = model.labels_  # 训练集训练后生成的标签，0为正常值，1为异常值
  20. y_train_scores = model.decision_scores_   # 训练数据的异常值得分
  21. params = model.get_params()  # 模型参数的估计量
  23. # 对测试集进行预测
  24. y_test_pred = model.predict(X_test)  # 生成测试集的预测标签
  25. y_test_scores = model.decision_function(X_test)  # 使用合适的探测器预测X的原始异常分数。
  27. # 打印评估结果
  28. print("\nParams: ", params)
  29. print("\nOn Training Data:")
  30. evaluate_print(model_name, y_train, y_train_scores)
  31. print("\nOn Test Data:")
  32. evaluate_print(model_name, y_test, y_test_scores)

image.png
8万条数据，14.6s就跑完了，很快

  1. model = IForest(n_estimators = 400,behaviour='new',bootstrap=True)
  3. model.fit(X_train)
  5. y_train_pred = model.labels_  
  6. y_train_scores = model.decision_scores_   
  7. params = model.get_params()  
  9. # 对测试集进行预测
  10. y_test_pred = model.predict(X_test)  # 生成测试集的预测标签
  11. y_test_scores = model.decision_function(X_test)  # 使用合适的探测器预测X的原始异常分数。
  13. # 打印评估结果
  14. print("\nParams: ", params)
  15. print("\nOn Training Data:")
  16. evaluate_print(model_name, y_train, y_train_scores)
  17. print("\nOn Test Data:")
  18. evaluate_print(model_name, y_test, y_test_scores)

image.png
修改了一下训练的参数，增加了每次训练的样本数量，和修改成替换采样。最后的结果应该是有个非常不错的提升，但是因为之前训练的得分都是1，所以这里看起来好像没有什么提升呢。

3.(思考题：feature bagging为什么可以降低方差？)

bagging：多次采样获取训练子集 五、高维数据的异常检测 - 图35 ,并通过平均来降低只有单个 五、高维数据的异常检测 - 图36 的方差。但值得注意的是， 五、高维数据的异常检测 - 图37 之间有相关性（correlation），因为是sampling with replacement。如果有无限个不重复采样（sampling without replacement），那么事实上我们通过平均就得到期望。但即使每个采样出的子集都会造成一定程度的bias，通过取均值的方差降低还是可以弥补这个损失。有相同思路还有subagging，以及对特征进行采样的feature bagging，比较著名的应用就是随机森林。一般来说，我们假设这种抽样更好的模拟了真实分布，因此比单用一个训练集达到了更低的方差。但退一步说，将多个因随机而不同的分类器输出结果集成后增强了不同决策面上的表达，如果把集成后的结果看作是一个整体，那么整体的bias降低了，对于数据的表达更强了。

方差的公式五、高维数据的异常检测 - 图38

4.(思考题：feature bagging存在哪些缺陷，有什么可以优化的idea？)
①缺陷：由于Bagging需要进行多次重抽样和计算，需要消耗大量的空间和时间。
②优化：在数据准备阶段，先进行预处理，尝试减少和标签相关性比较低的特征。

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是一个专注于数据科学与AI领域的开源组织，汇集了众多领域院校和知名企业的优秀学 习者，聚合了一群有开源精神和探索精神的团队成员。Datawhale以“for the learner，和学习者 一起成长”为愿景，鼓励真实地展现自我、开放包容、互信互助、敢于试错和勇于担当。同时 Datawhale 用开源的理念去探索开源内容、开源学习和开源方案，赋能人才培养，助力人才成 长，建立起人与人，人与知识，人与企业和人与未来的联结。衷心感谢DataWhale