Datawhale组队学习【数据挖掘-异常检测-TASK5】

Datawhale组队学习【数据挖掘-异常检测-TASK5】


前言

异常检测TASK5主要内容:
学习高位数据的异常检测方法

  • 了解集成方法的思想
  • 理解feature bagging原理
  • 掌握孤立森林算法

内容来自datawhale组队学习讲义:
https://gitee.com/dreamzll/team-learning-data-mining/blob/master/AnomalyDetection/%E4%BA%94%E3%80%81%E9%9B%86%E6%88%90%E6%96%B9%E6%B3%95.md


1、引言

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

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

下面来介绍两种常见的集成方法:

2、Feature Bagging

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

1.选择基检测器。这些基本检测器可以彼此完全不同,或不同的参数设置,或使用不同采样的子数据集。Feature bagging常用lof算法为基算法。下图是feature bagging的通用算法:
Datawhale组队学习【数据挖掘-异常检测-TASK5】

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

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

Datawhale组队学习【数据挖掘-异常检测-TASK5】

​ (广度优先)

Datawhale组队学习【数据挖掘-异常检测-TASK5】

​ (累积求和)

基探测器的设计及其组合方法都取决于特定集成方法的特定目标。很多时候,我们无法得知数据的原始分布,只能通过部分数据去学习。除此以外,算法本身也可能存在一定问题使得其无法学习到数据完整的信息。这些问题造成的误差通常分为偏差和方差两种。

方差:是指算法输出结果与算法输出期望之间的误差,描述模型的离散程度,数据波动性。

偏差:是指预测值与真实值之间的差距。即使在离群点检测问题中没有可用的基本真值

3、Isolation Forests

孤立森林(Isolation Forest)算法是周志华教授等人于2008年提出的异常检测算法,是机器学习中少见的专门针对异常检测设计的算法之一,方法因为该算法时间效率高,能有效处理高维数据和海量数据,无须标注样本,在工业界应用广泛。
Datawhale组队学习【数据挖掘-异常检测-TASK5】
定义:假设T是孤立树的一个节点,它要么是没有子节点的叶子节点,要么是只有两个子节点(Tl,Tr)的内部节点。每一步分割,都包含特征q和分割值p,将q<p的数据分到Tl,将q≥p的数据分到Tr。给定n个样本数据X={x1,⋯,xn},特征的维度为d。为了构建一棵孤立树,需要随机选择一个特征qq及其分割值p,递归地分割数据集X,直到满足以下任意一个条件:(1)树达到了限制的高度;(2)节点上只有一个样本;(3)节点上的样本所有特征都相同。

异常检测的任务是给出一个反应异常程度的排序,常用的排序方法是根据样本点的路径长度或异常得分来排序,异常点就是排在最前面的那些点。

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

用四个样本做简单直观的理解,d是最早被孤立出来的,所以d最有可能是异常。

Datawhale组队学习【数据挖掘-异常检测-TASK5】

怎么来切这个数据空间是孤立森林的核心思想。因为切割是随机的,为了结果的可靠性,要用集成(ensemble)的方法来得到一个收敛值,即反复从头开始切,平均每次切的结果。孤立森林由t棵孤立的数组成,每棵树都是一个随机二叉树,也就是说对于树中的每个节点,要么有两个孩子节点,要么一个孩子节点都没有。树的构造方法和随机森林(random forests)中树的构造方法有些类似。流程如下:

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

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

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

路径长度计算方法:

Datawhale组队学习【数据挖掘-异常检测-TASK5】

孤立森林也是一种基于子空间的方法,不同的分支对应于数据的不同局部子空间区域,较小的路径对应于孤立子空间的低维

4、代码实践

feature_bagging

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import pyod as py
from pyod.utils.data import generate_data
from pyod.models.feature_bagging import FeatureBagging
from pyod.models.lof import LOF
from pyod.utils.example import visualize
from pyod.utils.data import evaluate_print
import seaborn as sns

x_train,y_train,x_test,y_test=generate_data(
        n_train=500,n_test=70, n_features=15,
        train_only=False,behaviour='old',offset=10)
#对数据进行拆分

outlier_fraction = 0.1
random_state = np.random.RandomState(42)
x_outliers, x_inliers = py.utils.data.get_outliers_inliers(x_train,y_train)
#使用LOF
classifiers = {
    'Feature bagging (feature_bagging)':FeatureBagging(
        LOF(n_neighbors=60), n_estimators=10,contamination=outlier_fraction,
        random_state=random_state,check_estimator=False
    )
}
for i, (clf_name, clf) in enumerate(classifiers.items()):

    clf.fit(x_train)
    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
    clf_name = 'feature_bagging'
    print("\nOn Training Data:")
    evaluate_print(clf_name, y_train, y_train_scores)
    # print(precision_score(y_train,y_train_pred))
    print("\nOn Test Data:")
    evaluate_print(clf_name, y_test, y_test_scores)
    # print(precision_score(y_test,y_test_pred))

————————————————
版权声明:本文为CSDN博主「weiphm」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/weiphm/article/details/113094690

孤立森林

import numpy as np
import matplotlib.pyplot as plt
from sklearn.ensemble import IsolationForest

rng = np.random.RandomState(42)

# Generate train data
X = 0.3 * rng.randn(100, 2)
X_train = np.r_[X + 1, X - 3, X - 5, X + 6]
# Generate some regular novel observations
X = 0.3 * rng.randn(20, 2)
X_test = np.r_[X + 1, X - 3, X - 5, X + 6]
# Generate some abnormal novel observations
X_outliers = rng.uniform(low=-8, high=8, size=(20, 2))

# fit the model
clf = IsolationForest(max_samples=100*2, random_state=rng)
clf.fit(X_train)
y_pred_train = clf.predict(X_train)
y_pred_test = clf.predict(X_test)
y_pred_outliers = clf.predict(X_outliers)

# plot the line, the samples, and the nearest vectors to the plane
xx, yy = np.meshgrid(np.linspace(-8, 8, 50), np.linspace(-8, 8, 50))
Z = clf.decision_function(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)

plt.title("IsolationForest")
plt.contourf(xx, yy, Z, cmap=plt.cm.Blues_r)

b1 = plt.scatter(X_train[:, 0], X_train[:, 1], c='white')
b2 = plt.scatter(X_test[:, 0], X_test[:, 1], c='green')
c = plt.scatter(X_outliers[:, 0], X_outliers[:, 1], c='red')
plt.axis('tight')
plt.xlim((-8, 8))
plt.ylim((-8, 8))
plt.legend([b1, b2, c],
           ["training observations",
            "new regular observations", "new abnormal observations"],
           loc="upper left")
plt.show()

Datawhale组队学习【数据挖掘-异常检测-TASK5】

5、总结

1.feature bagging可以降低方差

2.孤立森林的优势在于:

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

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

6、练习

1.思考题:feature bagging为什么可以降低方差?

偏差通常是由于我们对学习算法做了错误的假设导致的,而方差通常是由于模型的复杂度相对于训练样本数过高导致的。

Bagging:是降低方差,它是Bootstrap Aggregating 的简称,意思是再抽样,然后在每个样本训练出来的模型取平均。这样的话方差是原来单个模型的1/n。
Boosting:是降低偏差,它是在训练好一个弱分类器后,计算弱分类器的错误或者残差,作为下一个分类器的输入,这个过程就是在不断减小损失函数,即降低偏差

对于feature bagging,是对每一个模型取平均值,其输出的期望更接近总体的期望。

2.思考题:feature bagging存在哪些缺陷,有什么可以优化的idea?
由于需要对每个基学习器进行调参,需要很多运算资源,消耗较大。
可以在feature baggiing 之前,先使用其他算法检测出含有异常值的样本

上一篇:Oracle常用函数


下一篇:python——k邻近算法