Press "Enter" to skip to content

SUOD:「大规模异常检测系统」初体验

 

本文经授权转载自知乎

 

原文: https://zhuanlan.zhihu.com/p/112588169

 

作者: 微调

 

异常检测 (又称outlier detection、anomaly detection、离群值检测)是一种重要的数据挖掘或机器学习方法,可以找到与“主体数据分布”不同的异常值,比如从信用卡交易中找出诈骗案例,从正常的网络数据流中找出入侵,在正常案例中找到罕见病患者,有非常广泛的商业应用价值。同时它可以被用于机器学习任务中的预处理,防止因为少量异常点存在而导致的训练或预测失败。

 

虽然我们已经有了一系列完备的工具进行异常检测,但还有很多问题亟待解决。而从实用性监督来说,对于异常检测算法落地影响最大的就是「 在高维度、大数据上算法无法收敛 」。

 

针对这个问题,我们提出了一个全新的加速系统—— SUOD(Scalable Unsupervised Outlier Detection Framework)

 

SUOD的代码在GitHub上并可以通过pip下载安装,SUOD的最初版文章先是被AAAI’20 的workshop接收,扩充完善后的文章KDD 20在审中,可以从arxiv上查看。欢迎大家star、follow、fork,提出宝贵的意见和建议。

 

代码:

 

        https://github.com/yzhao062/SUOD

 

PyPI:

 

       https://pypi.org/project/suod/

 

文档:

 

        https://suod.readthedocs.io/en/latest/

 

KDD提交版本:

 

        https://arxiv.org/abs/2003.05731

 

AAAI Workshop版本:

 

        https://arxiv.org/abs/2002.03222

 

1. 背景简介

 

异常检测因为标签难以获得的原因,往往得依靠无监督学习模型。而无监督学习在异常检测这种数据极端不平衡的分类问题中往往表现的很不稳定。 对于无监督学习中的稳定性差的问题,最常见的解决方案就是用集成学习,即合并、选择多个基学习器而得到有提升的结果。

 

但训练或者用大量无监督模型做预测会面临巨大的开销问题,尤其是在高维度、大数据上,很多时候甚至无法收敛。

 

2. 解决方法

 

为了解决在高维大数据上训练多个无监督异常检测模型无法收敛,或耗时过长的问题。我们提出了Scalable Unsupervised Outlier Detection(SUOD)。SUOD的目标是加速训练的同时不牺牲训练和预测的效果,至少以较小的代价使得不易完成的过程变得可能。

 

所以特别值得指出的是, SUOD的目的是加速,而并非提高精度 。SUOD模型的输入是数据集X,与多个要被训练的模型D。而输出则是训练好的模型D,如果需要预测的话,还有预测结果。

 

 

SUOD主要在 三个层面 对训练与预测进行加速,分别是:系统层面,数据层面,模型层面。

 

3. 系统层面:平衡的并行调度

 

先说 系统层面 。当我们需要训练多个模型时,很自然的就是想把它们并行化,在多个core上进行运行。但当我们的多个模型是异质的(heterogeneous)的话,运算的开销会有很大的差别。举个最简单的例子,决策树可能就比K近邻的运算速度要快的多。假设我要训练100个模型,前50个是决策树,后50个是K近邻。假设我们只有2个集群或者worker,那幺简单的按照数量进行分的话,那幺集群1上的任务会会比集群2上完成的速度快的多。那幺这种调度上的不平衡会使得整个系统的运行效率很低。

 

为了解决异质模型在系统调度上的不平衡,我们先训练了一个回归模型,用来预测每个基学习器可能需要的运算开销。之后我们设定了一个调度方法来确保不同的worker上的任务负载尽量接近。 在这种设计下,每个worker(比如core)上的任务数量可能不同,但总的需要时间会更加接近,因此并行任务可以在几乎同一时刻完成。

 

 

以上图为例,我们有个m模型需要训练,先用训练好的模型开销回归器对它们的开销进行训练。并根据开销的排序来分配每个core的任务数。

 

4. 数据层面:

 

Johnson-Lindenstrauss (JL) projection

 

我们前文说到了运算开销会随着维度上升而变大,而且往往是quadratic的,因此降维是一个非常合理的想法。但随即的降维,比如简单的random projection,往往缺乏性能保证。而线性降维,比如PCA,最大的问题是得到结果是确定的(determinastic)。换句话说,每次用PCA得到的降维结果都是差不多的,这不利于后续的训练多个模型,尤其是集成学习模型。另一个显着的问题就是PCA本身就可以被作为一种异常检测的方法,那幺降维的过程会丢失掉一部分异常点。

 

我们希望有一种降维方法:1 快速,2 可以保留原始样本间的距离关系,3 有一定的随机性,4 在降维的过程中不会丢失异常信息。

 

刚好有一种数学方法,叫做Johnson-Lindenstrauss (JL) projection可以满足这个需求。JL降维的实际操作非常简单,只要随即出一个投影矩阵(比如完全随即的高斯分布)就行,但却有很好的数学性质来达到我们的需求。即使在实际操作中,我们的数据并不完全符合JL的假设,效果却还是不错的。

 

所以在数据层面, 我们会用JL投影对高维数据进行降维,以此来加速训练与预测。

 

5. 模型层面:

 

用(伪)监督模型来替换无监督模型

 

无监督模型,尤其是非参数的无监督模型,往往预测的开销很大。举个简单的例子,K近邻的预测就比较耗时。不幸的是,大部分无监督的异常检测模型的预测开销都很大。那幺我们该如何加速这个过程呢?

 

一个很自然的想法就是,我们能不能用参数化的监督模型来替换无监督模型呢?因此我们提出了Pseudo supervised approximation(PSA),思路其实跟知识蒸馏有点像,但具体操作还是很不相同的。PSA的操作就是现在已有数据上用无监督异常检测来训练,并得到它们的训练分数,再用监督学习模型来模拟这个决策边界。

 

 

上图的1,3,5,7分别是原始的无监督异常检测模型在测试数据上的决策边界(在二维的生成数据上),而2,4,6,8分别是我们用PSA训练得到的决策边界。从肉眼上看,这直接和原始模型和用于模拟的模型的类别有关,但总体的表现较为接近且有一定的防止过拟合的效果。

 

当然,并不是每个无监督模型都该被模拟。这种模拟只针对于运算开销大的的模型,文章里我们更多的讨论什幺时候不该用(比如线性模型像ABOD)。

 

6. SUOD作为一个整体模型

 

需要特别注意的是, SUOD是一个由三个模块组成的加速系统。实际情况中,我们并不需要使用所有模块, 而应该根据具体情况打开或者关闭特定的组件。如果不需要预测的话,就不需要PSA。如果数据维度不是很高,也不需要随机投影。假设没有并行系统的话,自然也不能使用平衡调度。

 

7. 实验结果

 

我们使用了超过30个异常检测数据集进行测试,并将系统实际在IQVIA(一家大型健康咨询公司)的数据集上进行了验证,效果均不错。相信在不断打磨,提升鲁棒性后可以被更广泛的使用。在文章中我们分别验证了每一个模块独立的有效性,也验证了整个系统的效果 。 高度概括的话,加速效果一般可达到30%以上,且模型的预测能力并未降低,甚至略有上升。

 

8. 总结与未来方向

 

在这个工作里,我们提出了SUOD,一个由三个模块组成的大规模异常检测加速系统,可以被直接用于加速PyOD里面的模型。这个三个加速模块着眼于不同的方向,互补且相辅相成。从未来开发的角度上来看,我们希望进一步验证后接复杂模型效果,以及用监督模型来模拟无监督模型的理论依据。

 

我们认为SUOD模型其实还可以被迁移到其他任务上,比如聚类问题,毕竟整个的构成是很像的。

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注