乐趣区

关于人工智能:异常检测探索数据深层次背后的奥秘下篇

异样检测:摸索数据深层次背地的神秘《下篇》

异样检测——高维数据异样检测:孤立森林

在理论场景中,很多数据集都是多维度的。随着维度的减少,数据空间的大小(体积)会以指数级别增长,使数据变得稠密,这便是维度咒骂的难题。维度咒骂不止给异样检测带来了挑战,对间隔的计算,聚类都带来了难题。例如基于邻近度的办法是在所有维度应用间隔函数来定义局部性,然而,在高维空间中,所有点对的间隔简直都是相等的(间隔集中),这使得一些基于间隔的办法生效。在高维场景下,一个罕用的办法是子空间办法。

集成是子空间思维中罕用的办法之一,能够无效进步数据挖掘算法精度。集成办法将多个算法或多个基检测器的输入联合起来。其根本思维是一些算法在某些子集上体现很好,一些算法在其余子集上体现很好,而后集成起来使得输入更加鲁棒。集成办法与基于子空间办法有着人造的相似性,子空间与不同的点集相干,而集成办法应用基检测器来摸索不同维度的子集,将这些基学习器集合起来。

上面来介绍两种常见的集成办法:

1.Feature Bagging

Feature Bagging,根本思维与 bagging 类似,只是对象是 feature。feature bagging 属于集成办法的一种。集成办法的设计有以下两个次要步骤:

1. 抉择基检测器。这些根本检测器能够彼此齐全不同,或不同的参数设置,或应用不同采样的子数据集。Feature bagging 罕用 lof 算法为基算法。下图是 feature bagging 的通用算法:

2. 分数标准化和组合办法:不同检测器可能会在不同的尺度上产生分数。例如,均匀 k 近邻检测器会输入原始间隔分数,而 LOF 算法会输入归一化值。另外,只管个别状况是输入较大的异样值分数,但有些检测器会输入较小的异样值分数。因而,须要将来自各种检测器的分数转换成能够有意义的组合的归一化值。分数标准化之后,还要抉择一个组合函数将不同根本检测器的得分进行组合,最常见的抉择包含均匀和最大化组合函数。

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

​ (广度优先)

​(累积求和)

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

方差:是指算法输入后果与算法输入冀望之间的误差,形容模型的离散水平,数据波动性。

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

2、Isolation Forests

孤立森林(Isolation Forest)算法是周志华传授等人于 2008 年提出的异样检测算法,是机器学习中少见的专门针对异样检测设计的算法之一,办法因为该算法工夫效率高,能无效解决高维数据和海量数据,毋庸标注样本,在工业界利用宽泛。

孤立森林属于非参数和无监督的算法,既不须要定义数学模型也不须要训练数据有标签。孤立森林查找孤立点的策略十分高效。假如咱们用一个随机超平面来切割数据空间,切一次能够生成两个子空间。而后咱们持续用随机超平面来切割每个子空间并循环,直到每个子空间只有一个数据点为止。直观上来讲,那些具备高密度的簇须要被切很屡次才会将其拆散,而那些低密度的点很快就被独自调配到一个子空间了。孤立森林认为这些很快被孤立的点就是异样点。

用四个样本做简略直观的了解,d 是最早被孤立进去的,所以 d 最有可能是异样。

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

1) 从训练数据中随机抉择一个样本子集,放入树的根节点;

2) 随机指定一个属性,随机产生一个切割点 V,即属性 A 的最大值和最小值之间的某个数;

3) 依据属性 A 对每个样本分类,把 A 小于 V 的样本放在以后节点的左孩子中,大于等于 V 的样本放在右孩子中,这样就造成了 2 个子空间;

4) 在孩子节点中递归步骤 2 和 3,一直地结构左孩子和右孩子,直到孩子节点中只有一个数据,或树的高度达到了限定高度。

取得 t 棵树之后,孤立森林的训练就完结,就能够用生成的孤立森林来评估测试数据。

孤立森林检测异样的假如是:异样点个别都是十分罕见的,在树中会很快被划分到叶子节点,因而能够用叶子节点到根节点的门路长度来判断一条记录是否是异样的。和随机森林相似,孤立森林也是采纳结构好的所有树的均匀后果造成最终后果的。在训练时,每棵树的训练样本是随机抽样的。从孤立森林的树的结构过程看,它不须要晓得样本的标签,而是通过阈值来判断样本是否异样。因为异样点的门路比拟短,失常点的门路比拟长,孤立森林依据门路长度来预计每个样本点的异样水平。

门路长度计算方法:

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

  • 小结

1.feature bagging 能够升高方差

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

  • 计算成本相比基于间隔或基于密度的算法更小。
  • 具备线性的工夫复杂度。
  • 在解决大数据集上有劣势。

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

  • 参考资料

[1] https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/icdm08b…

[2]《Outlier Analysis》——Charu C. Aggarwal

3. 数据集

  1. Outlier Detection DataSets (ODDS):http://odds.cs.stonybrook.edu/#table1
  2. KDD99(网络入侵):http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html

4. 工具

4.1 scikit-learn

ensemble.IsolationForestneighbors.LocalOutlierFactor 在此处思考的数据集上体现良好。的svm.OneClassSVM 被称为是对异样值敏感并因而对异样值检测不执行得十分好。话虽如此,在高维中进行离群检测,或者不对根底数据的散布进行任何假如都是十分具备挑战性的。svm.OneClassSVM依然能够与离群值检测一起应用,但须要对其超参数 nu 进行微调 以解决离群值并避免过拟合。最初,covariance.EllipticEnvelope假如数据为高斯并学习一个椭圆。无关不同估计量的更多详细信息,请参阅“比拟异样检测算法以对玩具数据集进行异样检测的示例”及其以下局部。

4.2 PyOD

PyOD 是一个全面且可扩大的 Python 工具箱, 用于 检测 多元数据中的异样 对象。这个令人兴奋而又充斥挑战的畛域通常称为 异样值检测 或异样检测。

从传统的 LOF(SIGMOD 2000)到最新的 COPOD(ICDM 2020),PyOD 包含 30 多种检测算法。自 2017 年以来,PyOD [AZNL19]已胜利用于泛滥学术研究和商业产品 [AGSW19,ALCJ + 19,AWDL + 19,AZNHL19]。机器学习社区也通过各种专门的帖子 / 教程对它进行了宽泛认可,包含 Analytics Vidhya,Towards Data Science,KDnuggets,Computer Vision News 和 awesome-machine-learning.。

代码示例

以下内容来自 PyOD 官网介绍

  1. 导入模型

    from pyod.models.knn import KNN   # kNN detector
  2. 应用 pyod.utils.data.generate_data()生成数据

    contamination = 0.1  # percentage of outliers
    n_train = 200  # number of training points
    n_test = 100  # number of testing points
    
    X_train, y_train, X_test, y_test = generate_data(n_train=n_train, n_test=n_test, contamination=contamination)
  3. fit and predict

    # train kNN detector
    clf_name = 'KNN'
    clf = KNN()
    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
  4. 应用 ROC 和 Precision @ Rank n 评估预测

    from pyod.utils.data import evaluate_print
    # 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)
  5. 察看训练集以及测试集的输入

    On Training Data:
    KNN ROC:1.0, precision @ rank n:1.0
    
    On Test Data:
    KNN ROC:0.9989, precision @ rank n:0.9
  6. 可视化

    visualize(clf_name, X_train, y_train, X_test, y_test, y_train_pred,
              y_test_pred, show_figure=True, save_figure=False)

具体代码请看官网阐明:https://pyod.readthedocs.io/en/latest/pyod.html

更多优质内容请关注公号:汀丶人工智能;会提供一些相干的资源和优质文章,收费获取浏览。

退出移动版