1. 主要内容包括：

Feature Bagging
孤立森林

2. 学习背景：

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

3. 解决方式

集成是子空间思想中常用的方法之一，可以有效提高数据挖掘算法精度。集成方法将多个算法或多个基检测器的输出结合起来。
集成学习的基本思想是利用不同算法在不同子集的表现，将其集成起来使得输出更加鲁棒。

3.1 feature bagging

Bagging方法通常考虑的是同质弱学习器，相互独立地并行学习这些弱学习器，并按照某种确定性的平均过程将它们组合起来。
Feature Bagging，基本思想与bagging相似，只是对象是feature。feature bagging属于集成方法的一种。集成方法的设计有以下两个主要步骤：

3.1.1 选择基检测器

feature bagging常用lof算法为基算法，下图是feature bagging的通用算法：

3.1.2 分数标准化和组合方法

把来自各种检测器的分数转换成可以有意义的组合的归一化值。分数标准化之后，还要选择一个组合函数将不同基本检测器的得分进行组合，最常见的选择包括平均和最大化组合函数。

下图是两个feature bagging两个不同的组合分数方法：

广度优先
累积求和

3.2 孤立森林算法（Isolation Forests）

特点

时间效率高
有效处理高维数据和海量数据，无须标注样本，在工业应用广泛。

算法思想
孤立森林属于非参数和无监督的算法，通过用一个随机超平面来切割数据空间来查找异常点，切一次可以生成两个子空间。然后继续用随机超平面来切割每个子空间并循环，直到每个子空间只有一个数据点为止。直观上来讲，很快被孤立的点就是异常点。

构造方法

从训练数据中随机选择一个样本子集，放入树的根节点
随机指定一个属性，随机产生一个切割点V，即属性A的最大值和最小值之间的某个数
根据属性A对每个样本进行分类，把A小于V的样本放在当前节点的左子树中，否否则放于右子树中。依次生成随机二叉树
重复前一步骤，直到子树中只有一个数据，停止生成。

孤立森林检测异常的假设
异常点一般都是非常稀有的，在树中会很快被划分到叶子节点，因此可以用叶子节点到根节点的路径长度来判断一条记录是否是异常的。在训练时，每棵树的训练样本是随机抽样的。从孤立森林的树的构造过程看，它不需要知道样本的标签，而是通过阈值来判断样本是否异常。因为异常点的路径比较短，正常点的路径比较长，孤立森林根据路径长度来估计每个样本点的异常程度。

路径长度计算方法

4. 总结

feature bagging可以降低方差
孤立森林的优势在于：计算成本相比基于距离或基于密度的算法更小；具有线性的时间复杂度；在处理大数据集上有优势；孤立森林不适用于超高维数据，因为鼓励森林每次都是随机选取维度，如果维度过高，则会存在过多噪音。

5.思考题

为什么feature bagging可以降低方差？
因为变量之间具备相关性，不是完全独立的。
feature bagging存在哪些缺陷，有什么可以优化的idea?
要训练多个弱学习器，计算开销大。优化：在随机采样训练若学习器前，对样本训练集进行KNN聚类，筛选明显存在异常值的样本集，再进行弱学习器的训练。

6. 实验

feature bagging

import pyod.utils.data as data
from pyod.models.feature_bagging import FeatureBagging
import matplotlib.pyplot as plt
import numpy as np

x,y= data.generate_data(n_train=100,n_features=2,contamination=0.1,train_only=True,behaviour='new')
xn=[]
xa=[]
for i in range(100):
    if(y[i]==0):
        xn.append(x[i])
    else:
        xa.append(x[i])
xn=np.array(xn)
xa = np.array(xa)
plt.figure()
plt.scatter(xn[:,0],xn[:,1])
plt.scatter(xa[:,0],xa[:,1], color = 'red')
plt.show()

clf = FeatureBagging()
clf.fit(x)
y_pred = clf.labels_

nr_pred = []  #预测正常正确
ar_pred = []  #预测异常正确
ne_pred = []  #预测正常错误
ae_pred = []  #预测异常错误
for i in range(100):
    if(y_pred[i]==0 and y[i]==0):
        nr_pred.append(x[i])
    if(y_pred[i]==1 and y[i]==1):
        ar_pred.append(x[i])
    if(y_pred[i]==0 and y[i]==1):
        ne_pred.append(x[i])
    if y_pred[i]==1 and y[i]==0:
        ae_pred.append(x[i])

ne_pred=np.array(ne_pred).reshape(-1,2)
nr_pred = np.array(nr_pred).reshape(-1,2)
ae_pred = np.array(ae_pred).reshape(-1,2)
ar_pred = np.array(ar_pred).reshape(-1,2)
plt.figure()
plt.scatter(nr_pred[:,0],nr_pred[:,1],marker='.',c='blue')
plt.scatter(ar_pred[:,0],ar_pred[:,1], marker='.',c = 'red')
plt.scatter(ne_pred[:,0],ne_pred[:,1],marker='*',c='blue')
plt.scatter(ae_pred[:,0],ae_pred[:,1], marker='*',c = 'red')
plt.show()

检测结果如上图所示：
图一中蓝色是正常数据点，红色是异常数据点。
图二中点是预测正确的点，星号是预测错误的点。

孤立森林实验

import pyod.utils.data as data
from pyod.models.iforest import IForest
import matplotlib.pyplot as plt
import numpy as np
'''生成同样example'''
x,y= data.generate_data(n_train=100,n_features=2,contamination=0.1,train_only=True,behaviour='new')
xn=[]
xa=[]
for i in range(100):
    if(y[i]==0):
        xn.append(x[i])
    else:
        xa.append(x[i])
xn=np.array(xn)
xa = np.array(xa)
plt.figure()
plt.scatter(xn[:,0],xn[:,1])
plt.scatter(xa[:,0],xa[:,1], color = 'red')
plt.show()
clf = IForest()
clf.fit(x)
y_pred = clf.labels_
nr_pred = []  #预测正常正确
ar_pred = []  #预测异常正确
ne_pred = []  #预测正常错误
ae_pred = []  #预测异常错误
for i in range(100):
    if(y_pred[i]==0 and y[i]==0):
        nr_pred.append(x[i])
    if(y_pred[i]==1 and y[i]==1):
        ar_pred.append(x[i])
    if(y_pred[i]==0 and y[i]==1):
        ne_pred.append(x[i])
    if y_pred[i]==1 and y[i]==0:
        ae_pred.append(x[i])
ne_pred=np.array(ne_pred).reshape(-1,2)
nr_pred = np.array(nr_pred).reshape(-1,2)
ae_pred = np.array(ae_pred).reshape(-1,2)
ar_pred = np.array(ar_pred).reshape(-1,2)
plt.figure()
plt.scatter(nr_pred[:,0],nr_pred[:,1],marker='.',c='blue')
plt.scatter(ar_pred[:,0],ar_pred[:,1], marker='.',c = 'red')
plt.scatter(ne_pred[:,0],ne_pred[:,1],marker='*',c='blue')
plt.scatter(ae_pred[:,0],ae_pred[:,1], marker='*',c = 'red')
plt.show()