主要内容包括：

  • Feature Bagging
  • 孤立森林

1、引言

在实际场景中，很多数据集都是多维度的。随着维度的增加，数据空间的大小（体积）会以指数级别增长，使数据变得稀疏，这便是维度诅咒的难题。维度诅咒不止给异常检测带来了挑战，对距离的计算，聚类都带来了难题。例如基于邻近度的方法是在所有维度使用距离函数来定义局部性，但是，在高维空间中，所有点对的距离几乎都是相等的（距离集中），这使得一些基于距离的方法失效。在高维场景下，一个常用的方法是子空间方法。
集成是子空间思想中常用的方法之一，可以有效提高数据挖掘算法精度。集成方法将多个算法或多个基检测器的输出结合起来。其基本思想是一些算法在某些子集上表现很好，一些算法在其他子集上表现很好，然后集成起来使得输出更加鲁棒。集成方法与基于子空间方法有着天然的相似性，子空间与不同的点集相关，而集成方法使用基检测器来探索不同维度的子集，将这些基学习器集合起来。
下面来介绍两种常见的集成方法：

2、Feature Bagging

Feature Bagging，基本思想与bagging相似，只是对象是feature。feature bagging属于集成方法的一种。集成方法的设计有以下两个主要步骤：

1.选择基检测器

这些基本检测器可以彼此完全不同，或不同的参数设置，或使用不同采样的子数据集。Feature bagging常用lof算法为基算法。下图是feature bagging的通用算法：
image-20210104144520790.png

2.分数标准化和组合方法

不同检测器可能会在不同的尺度上产生分数。例如，平均k近邻检测器会输出原始距离分数，而LOF算法会输出归一化值。另外，尽管一般情况是输出较大的异常值分数，但有些检测器会输出较小的异常值分数。因此，需要将来自各种检测器的分数转换成可以有意义的组合的归一化值。分数标准化之后，还要选择一个组合函数将不同基本检测器的得分进行组合，最常见的选择包括平均和最大化组合函数。
下图是两个feature bagging两个不同的组合分数方法：
image-20210105140222697-1609839336763.png
（广度优先)

image-20210105140242611.png
（累积求和）

基探测器的设计及其组合方法都取决于特定集成方法的特定目标。很多时候，我们无法得知数据的原始分布，只能通过部分数据去学习。除此以外，算法本身也可能存在一定问题使得其无法学习到数据完整的信息。这些问题造成的误差通常分为偏差和方差两种。
方差：是指算法输出结果与算法输出期望之间的误差，描述模型的离散程度，数据波动性。
偏差：是指预测值与真实值之间的差距。即使在离群点检测问题中没有可用的基本真值
image.png

3. 方差与偏差的选择：

image.png

选择相对较好的模型的顺序：方差小，偏差小 > 方差小，偏差大 > 方差大，偏差小 > 方差大，偏差大。 方差小，偏差大 之所以在实际中排位相对靠前，是因为它比较稳定。很多时候实际中无法获得非常全面的数据集，那么，如果一个模型在可获得的样本上有较小的方差，说明它对不同数据集的敏感度不高，可以期望它对新数据集的预测效果比较稳定。
原知乎地址：https://zhuanlan.zhihu.com/p/44872686

3、Isolation Forests

孤立森林（Isolation Forest）算法是周志华教授等人于2008年提出的异常检测算法，是机器学习中少见的专门针对异常检测设计的算法之一，方法因为该算法时间效率高，能有效处理高维数据和海量数据，无须标注样本，在工业界应用广泛。
孤立森林属于非参数和无监督的算法，既不需要定义数学模型也不需要训练数据有标签。孤立森林查找孤立点的策略非常高效。假设我们用一个随机超平面来切割数据空间，切一次可以生成两个子空间。然后我们继续用随机超平面来切割每个子空间并循环，直到每个子空间只有一个数据点为止。直观上来讲，那些具有高密度的簇需要被切很多次才会将其分离，而那些低密度的点很快就被单独分配到一个子空间了。孤立森林认为这些很快被孤立的点就是异常点。
用四个样本做简单直观的理解，d是最早被孤立出来的，所以d最有可能是异常。
v2-bb94bcf07ced88315d0a5de47677200e_720w.png
怎么来切这个数据空间是孤立森林的核心思想。因为切割是随机的，为了结果的可靠性，要用集成（ensemble）的方法来得到一个收敛值，即反复从头开始切，平均每次切的结果。孤立森林由t棵孤立的数组成，每棵树都是一个随机二叉树，也就是说对于树中的每个节点，要么有两个孩子节点，要么一个孩子节点都没有。树的构造方法和随机森林(random forests)中树的构造方法有些类似。流程如下：
1) 从训练数据中随机选择一个样本子集，放入树的根节点；
2) 随机指定一个属性，随机产生一个切割点V，即属性A的最大值和最小值之间的某个数；
3) 根据属性A对每个样本分类，把A小于V的样本放在当前节点的左孩子中，大于等于V的样本放在右孩子中，这样就形成了2个子空间；
4) 在孩子节点中递归步骤2和3，不断地构造左孩子和右孩子，直到孩子节点中只有一个数据，或树的高度达到了限定高度。
获得t棵树之后，孤立森林的训练就结束，就可以用生成的孤立森林来评估测试数据。
孤立森林检测异常的假设是：异常点一般都是非常稀有的，在树中会很快被划分到叶子节点，因此可以用叶子节点到根节点的路径长度来判断一条记录是否是异常的。和随机森林类似，孤立森林也是采用构造好的所有树的平均结果形成最终结果的。在训练时，每棵树的训练样本是随机抽样的。从孤立森林的树的构造过程看，它不需要知道样本的标签，而是通过阈值来判断样本是否异常。因为异常点的路径比较短，正常点的路径比较长，孤立森林根据路径长度来估计每个样本点的异常程度。
路径长度计算方法：
image-20210103183909407.png
孤立森林也是一种基于子空间的方法，不同的分支对应于数据的不同局部子空间区域，较小的路径对应于孤立子空间的低维

4、总结

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

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

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

5、练习

1.思考题：feature bagging为什么可以降低方差？
答：bagging是对许多强（甚至过强）的分类器求平均。对于每个单独的分类器来说，其bias都是低的，平均之后的bias也低。但是每个单独的分类器都可能强到overfitting，即variance高。求平均的操作可以显著降低variance，故而feature bagging可以降低方差。
2.思考题：feature bagging存在哪些缺陷，有什么可以优化的idea？
答：要训练多个弱学习器，计算开销大。优化：在随机采样训练若学习器前，对样本训练集进行KNN聚类，筛选明显存在异常值的样本集，再进行弱学习器的训练。

6、利用pyod代码实现

  1. import numpy as np
  2. from scipy import stats
  3. import matplotlib.pyplot as plt
  4. import matplotlib.font_manager
  5. from pyod.models.feature_bagging import FeatureBagging  # 导入feature bagging模块
  6. from pyod.models.iforest import IForest
  7. # 导入isolation forest模块
  8. from pyod.models.lof import LOF
  10. from pyod.utils.data import generate_data, get_outliers_inliers
  12. # generate random data with two features
  13. X_train, Y_train = generate_data(n_train=200, train_only=True, n_features=2)
  15. # by default the outlier fraction is 0.1 in generate data function
  16. outlier_fraction = 0.1
  18. # store outliers and inliers in different numpy arrays
  19. x_outliers, x_inliers = get_outliers_inliers(X_train, Y_train)
  21. n_inliers = len(x_inliers)
  22. n_outliers = len(x_outliers)
  24. # separate the two features and use it to plot the data
  25. F1 = X_train[:, [0]].reshape(-1, 1)
  26. F2 = X_train[:, [1]].reshape(-1, 1)
  28. # create a meshgrid
  29. xx, yy = np.meshgrid(np.linspace(-10, 10, 200), np.linspace(-10, 10, 200))
  31. # scatter plot
  32. plt.scatter(F1, F2)
  33. plt.xlabel('F1')
  34. plt.ylabel('F2')
  35. plt.show()
  37. random_state = np.random.RandomState(42)
  38. # Define seven outlier detection tools to be compared
  39. classifiers = {
  40.     'Feature Bagging': FeatureBagging(LOF(n_neighbors=35), contamination=outlier_fraction, check_estimator=False,
  41.                                       random_state=random_state),
  42.     'Isolation Forest': IForest(contamination=outlier_fraction, random_state=random_state),
  43. }
  44. # 设置包括feature bagging和isolation forests的分类器
  46. # set the figure size
  47. plt.figure(figsize=(10, 10))
  48. # 分别用feature bagging和isolation forests进行异常值检测
  49. for i, (clf_name, clf) in enumerate(classifiers.items()):
  50.     # fit the dataset to the model
  51.     clf.fit(X_train)
  53.     # predict raw anomaly score
  54.     scores_pred = clf.decision_function(X_train) * -1
  56.     # prediction of a datapoint category outlier or inlier
  57.     y_pred = clf.predict(X_train)
  59.     # no of errors in prediction
  60.     n_errors = (y_pred != Y_train).sum()
  61.     print('No of Errors : ', clf_name, n_errors)
  63.     # rest of the code is to create the visualization
  65.     # threshold value to consider a datapoint inlier or outlier
  66.     threshold = stats.scoreatpercentile(scores_pred, 100 * outlier_fraction)
  68.     # decision function calculates the raw anomaly score for every point
  69.     Z = clf.decision_function(np.c_[xx.ravel(), yy.ravel()]) * -1
  70.     Z = Z.reshape(xx.shape)
  72.     subplot = plt.subplot(1, 2, i + 1)
  74.     # fill blue colormap from minimum anomaly score to threshold value
  75.     subplot.contourf(xx, yy, Z, levels=np.linspace(Z.min(), threshold, 10), cmap=plt.cm.Blues_r)
  77.     # draw red contour line where anomaly score is equal to threshold
  78.     a = subplot.contour(xx, yy, Z, levels=[threshold], linewidths=2, colors='red')
  80.     # fill orange contour lines where range of anomaly score is from threshold to maximum anomaly score
  81.     subplot.contourf(xx, yy, Z, levels=[threshold, Z.max()], colors='orange')
  83.     # scatter plot of inliers with white dots
  84.     b = subplot.scatter(X_train[:-n_outliers, 0], X_train[:-n_outliers, 1], c='white', s=20, edgecolor='k')
  85.     # scatter plot of outliers with black dots
  86.     c = subplot.scatter(X_train[-n_outliers:, 0], X_train[-n_outliers:, 1], c='black', s=20, edgecolor='k')
  87.     subplot.axis('tight')
  89.     subplot.legend(
  90.         [a.collections[0], b, c],
  91.         ['learned decision function', 'true inliers', 'true outliers'],
  92.         prop=matplotlib.font_manager.FontProperties(size=10),
  93.         loc='lower right')
  95.     subplot.set_title(clf_name)
  96.     subplot.set_xlim((-10, 10))
  97.     subplot.set_ylim((-10, 10))
  98. plt.show()

image.png
image.png
由此可见，feature bagging的结果优于isolation forests

参考资料

[1] https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/icdm08b.pdf
[2]《Outlier Analysis》——Charu C. Aggarwal
关于Datawhale：
Datawhale是一个专注于数据科学与AI领域的开源组织，汇集了众多领域院校和知名企业的优秀学习者，聚合了一群有开源精神和探索精神的团队成员。Datawhale以“for the learner，和学习者一起成长”为愿景，鼓励真实地展现自我、开放包容、互信互助、敢于试错和勇于担当。同时Datawhale 用开源的理念去探索开源内容、开源学习和开源方案，赋能人才培养，助力人才成长，建立起人与人，人与知识，人与企业和人与未来的联结。