用于异常检测的序列特征解释
【读书顺序】
摘要+介绍 为了解决什么问题提出什么思想
(A)提出SFE进行异常解释。 即给出一系列按照重要性排序的特征直到分析师能够确定它是否异常。
(B)第一种对异常解释的定量评估方法。即通过达到某种置信水平，最小化需要呈现的顺序特征个数来评估异常解释方法。 MFP(x，a，E)，最小特征前缀 x异常数据点 E重要性顺序索引 a分析师实验+结论 实验结果怎么样
- 算法细节
0 摘要
在许多应用中，异常检测系统向人类分析师提供最异常的数据实例，然后人类分析师必须确定该实例是否是真正感兴趣的(例如。 安全设置中的威胁)。不幸的是，大多数异常探测器没有解释为什么一个实例被认为是异常的，让分析师没有从哪里开始调查的指导。 为了解决这一问题，我们研究了异常检测器序列特征解释(SFEs)的计算和评估问题。 异常的SFE是一系列特征， 他们是每次（按顺序）提交给分析员，直到突出显示的特征中所包含的信息足以使分析员对异常作出有信心的判断。 由于分析人员的工作量与他们在调查中关系的信息量有关，因此解释的质量与必须揭示的功能数有关以获得信任（由于分析师的努力与他们在调查中考虑的信息量有关，解释的质量与必须揭示的特征数量有关，才能达到目的证据）。 我们的主要贡献之一是提出了一个新的框架，以大规模定量评价SFEs，其中质量衡量是基于分析师的努力。为了做到这一点，我们从真实的数据集中构造异常检测基准，并与人工专家一起进行模拟以供评估。 我们的第二个贡献是评估框架内和传统异常检测基准的几种新的解释方法，为这些方法提供了一些见解。1 介绍
异常检测是在数据集中识别异常的问题，其中异常是由与生成“正常”点的过程不同的过程生成的点。 统计异常检测器通过在数据中寻找统计异常值来解决这个问题。 然而，在大多数应用程序中，统计异常值并不总是与语义上的异常一致。 例如，在计算机安全应用程序中，由于复制和打印活动的数量异常之多，用户可能被认为在统计上是异常的，但在现实中，它有一个良性的解释，因此不是一个真正的异常。 由于统计和语义之间的这种差距，分析师通常会调查统计异常值，以决定哪些异常值很可能是真正的异常并值得采取下一步行动。
给定一个异常点，分析师面临分析与该点相关的数据的问题，以便对它是否是异常进行判断。 即使是数据点的描述要通过几十个特征，这可能是具有挑战性的，特别是当特征交互对判断至关重要时。 在实践中，情况往往更糟，比如成千上万的特征。 在这种情况下，即使异常探测器将一个真正的异常传递给分析师，由于信息过载，分析师也不会识别出造成这种异常的关键属性。 这意味着，实际上，整个系统的漏失异常率是异常探测器和分析师的漏失率的组合。 因此，提高检测率的一个途径是减少分析员正确识别异常所需的努力，其预期的副作用是降低分析员的漏检率。在本文中，我们考虑减少分析师的检测努力，为他们提供解释为什么点被探测器判断为异常。 基于这样的解释，分析师可以通过把调查重点放在与解释有关的信息上来尽量减少努力。
我们的第一个贡献是引入一种直观和简单的解释形式，我们称之为顺序特征解释(SFEs)。 给定一个由探测器判断为离群点的点， 这一点的SFE是一个有序的特征序列，其中顺序表示相对于导致高离群点分数的重要性。 一个SFE是通过增量重建呈现给分析师的一次一个特征，直到分析师获得足够的信息来决定该点是否是异常(例如。 在安全方面，威胁或非威胁)。 分析人员的调查工作大致与必须披露的特征数量有关。 因此，计算SFE的目的是尽量减少必须按顺序揭示的特征的个数，以便分析师自信地识别真正的异常。
我们的第二个贡献是制定一种定量评估方法来评估SFE，允许比较不同的SFE算法。 该方法的关键思想是利用监督学习和地面真相构建每个异常检测基准的模拟分析器。 然后，模拟分析师可以用来评估SFE的质量相对于必须显示的特征数量， 尽我们所能以达到指定的置信度水平。这是第一种对任何类型的异常解释方法的定量评估方法。
3 异常检测公式
【一句话】异常通常与其他点的生成过程不一致占极少部分。如何更好的让分析师确定是否是真的异常数据。
我们考虑定义在一组N个数据点{x1，…，xN}上的异常检测问题，其中每个点xi是一个n维实值向量。 集合包含一个法线点的混合物 ND异常点，通常正常点占数据的绝大多数。 在大多数异常检测应用中，异常点是由一个不同的过程产生的 从正常点，特别是一个过程，是重要的检测为特定的应用程序。 例如，数据点可以描述cor的所有用户的使用行为 计算机网络和异常可能对应内部威胁。
由于N通常很大，通过所有点手动搜索异常通常是不实际的。 统计异常探测器通过寻找统计异常点来寻找异常来解决这个问题 异常值。 然而，问题是，并非所有异常值都对应于异常，在实践中，分析师必须检查异常值，以决定哪些异常值可能是异常。 我们说当分析师发现他或她有异常点时，他或她能够确定有足够的证据表明该点确实是异常。 这个应用程序的成功蟑螂取决于异常探测器识别异常作为异常值的精度，也取决于分析人员正确检测异常的能力。 如果没有进一步的帮助，分析师可能需要 在分析过程中考虑与异常点的所有n个特征相关的信息。 在许多情况下，彻底考虑这些信息是不可能的，增加了不被发现的机会 异常，这可能是昂贵的许多领域。
4 SFE
为了减少分析师检测异常的努力，我们建议向分析师提供顺序特征解释(SFEs)，试图有效地解释为什么一个点是c被认为是一个离群者。 点的长度k的SFE是特征指数
的有序列表，其中
。其意图是，顺序中较早出现的特征被认为对一个点的高离群点分数更重要(例如。 
是最重要的)。 我们将使用符号
来表示E的第一个 i 特征索引的集合。 对于任意一组特征索引S和一个数据点x，我们设
表示x在S指定的子空间上的投影。
给定点x的SFE E，该点通过首先只呈现特征xE1递增地呈现给分析师。 如果分析人员只能根据这些信息做出判断 我们已经完成了这一点。 否则，下一个功能将添加到给分析师的信息中，即分析师现在看到xE2。 逐步向s中添加特征的过程 提交的信息的ET继续，直到分析师能够作出决定。 由于时间的限制，这一过程也可能提前结束；然而，我们没有在本文中研究这种情况。
对于正常点，SFE的增量表示可能无助于分析师更有效地免除这些点。 相反，对于异常情况，可以合理地预期分析师将 能够通过考虑比没有SFE少得多的信息量来检测异常，这应该减少错过检测的机会。 我们假设分析员的工作量 是所考虑的特征数的单调递增函数。 这促使我们通过必须向分析人员揭示的特征数量来衡量一个目标的SFE的质量，以便进行正确的检测。 更正式地说，给定一个异常点x，一个分析师a和一个x的SFE E，表示MFP(x，a，E)，最小特征前缀，是必须揭露给a进行正确判断的最小特征个数，按E指定的顺序，a将x视为异常。
虽然MFP提供了SFE质量的定量度量，但它的定义需要接触分析师。 这使得SFE计算方法在MFP方面的比较复杂化。 第6节讨论了这一问题，并介绍了采用多指标估计数进行广泛评价的方法。
5 解释方法
我们现在考虑计算异常探测器SFE的方法。 先前计算异常探测器解释的工作要么计算不依赖于所使用的特定异常探测器的解释(例如。 [5])或使用特定异常探测器的方法(例如。 [6])。 我们希望避免采用前一种方法，因为直觉上的解释应该试图说明为什么使用的特定检测器发现一个点是一个离群点。 考虑到后一种方法，我们寻求更一般的方法，可以更广泛地应用于不同的检测器。 因此，在这里，我们考虑了广泛研究的一类密度探测器的解释方法（我们的方法实际上可以用于更一般的“基于密度的检测器”类，只要分数可以计算给定任一特征子集。 为了简单起见，我们将重点放在基于密度的 本文中的检测器，其中密度函数用于计算分数）。
基于密度的检测器通过估计概率密度函数f(X)(例如。 GMM)超过 整套N点，并将f作为正常点上的密度。这是合理的，通常假设异常与正常相比是非常罕见的。然后根据f(X)的升序值对点进行排序，使根据f最小的正常对象按顺序最高。我们的方法不假定知道f的形式，但确实需要一个接口到f，允许计算联合边际值。 也就是说，对于特征索引S和点x的任何子集，我们要求我们可以计算
。 对于f的许多选择，如GMM，这些联合边缘有简单的封闭形式。 如果没有封闭形式，那么精确或近似于可以使用参考技术(例如MCMC)。
值得注意的是，通过考虑依赖于正在使用的异常检测器的SFE方法，MFP的性能将取决于异常检测器和SFE的质量。 例如，考虑一种情况，即异常检测器将异常点x判断为异常点，其原因与为什么x是异常语义无关。对于x的SFE不太可能帮助分析人员更有效地确定x是一个异常，因为语义关键特征可能出现在排序中较晚。 虽然这是一种可能性，但它超出了SFE方法的控制范围。 因此，在设计SFE方法时，我们将假定f所作的离群点判断对于应用程序在语义上是有意义的。 我们现在介绍两种主要的SFE方法 我们称之为marginal方法和dropout方法。
5.1 Marginal方法
在这里，我们考虑将分析师建模为一个贝叶斯分类器，它假设法线点是根据f生成的，并且异常在特征的支持下具有均匀的分布u的特征空间，在没有先验知识的异常分布这是一个合理的假设。 给定一个点x，一个SFE E和一些揭示的特征个数 i，这样的分析人员将通过比较似然比来决定x是否为异常
到达某种阈值。由于u被假定是均匀的，这相当于将联合边缘
与阈值进行比较。从直觉上看，这意味着如果我们的目标是使分析师迅速决定x是一个异常，我们应该选择一个E，产生的小值，特别是对于小i。
这导致了我们的第一个SFE方法，称为顺序边际(SeqMarg)。 SeqMarg方法在SFE E=
中一次添加一个特性，在每个步骤中添加最小化的特性 **联合边缘密度**与先前选择的特征。 更正式地说，SeqM根据以下公式计算
是S的补集。为了计算长度k的解释，SeqM需要O(kn)联合边际计算。请注意，由于SeqM固有的贪婪性， 
不一定是最小化 f 的最优 i 特征集。相反，如果目标是优化 i 的特定值，我们需要考虑大小 i 的所有
特征子集。 然而，我们的问题公式没有为我们提供 i 的目标值，因此SeqM提供了一种更易于处理的方法，重点是以贪婪的方式尽可能快地最小化 f 。
除了SeqMarg之外，我们还考虑了一种计算上更便宜的替代方案，称为独立边际(IndMarg)，它只需要c 单个边缘f
的计算。这种方法只是通过按的增加顺序对特征进行排序来选择x的解释E。这只需要O(N)边际计算来计算任何长度的解释。IndMarg提供了一个计算上更便宜的替代SeqMarg，但未能捕获联合特征交互。 例如，SeqMarg将以优化联合值的方式选择
，当与以前的特性
结合时。相反，IndMarg忽略了与先前选择的特性的交互。因此，IndMarg是理解计算解释时考虑联合特征交互的重要性的基线。
5.2 Dropout方法
接下来的两种方法都受到Robnik Sikonja和Kononenko[1]关于计算监督分类器的特征相关性解释的工作的启发。 在他们的工作中，特征的相关性分数是将该特征提供给分类器时的分类分数与省略该特征时的分类分数之间的差异。 （”dropout”）。 异常检测的类似方法是根据包含特征时密度值的变化以及不包含特征或被排除在外时的密度值的变化对特征进行评分。这产生了第一种dropout方法，成为独立dropout(IndDO),给定一个点x，则为每个特征分配一个分数
，在这里我们滥用符号，用
表示从x中删除
。 从直觉上讲，得分较高的要素是使该点在移除后显得最正常的要素。 然后通过按分数的降序对特征进行排序来获得SFE E。
我们也可以定义一个dropout的序列版本，通过遵循相同的配方，我们考虑了IndMarg和SeqMarg。SeqDO定义如下：
此方法需要与SeqMarg相同数量的边际计算。 该算法可以看作是SeqMarg的对偶，因为它根据特征点在移除后的正常程度来衡量特征集的贡献，而SeqMarg仅在包含那些特征的情况下衡量点看起来如何异常。
6 评估解释的框架 待补充
//TODO
评估解释面临的两个挑战：
- 相比于有监督学习，异常探测领域已建立的基准数据集较少，特别是基于真实世界数据的基准。
- 给定基准数据集，目前尚不清楚如何定量评估解释，因为基准既没有基本真理解释Ground Truth，也没有分析人员。
提出框架，相关解决办法：
- 借鉴最近基于实际数据构建大量异常检测基准的工作。
- 我们通过使用监督学习来构建可用于定量评估的模拟分析师来解决第二个问题。
6.1 异常检测基准
最近的工作[8]描述了从监督学习基准（分类或回归）系统地创建异常检测基准的方法。 因为大量的重新 世界监督学习基准，这允许相应的大量和多样化的异常检测基准。 此外，这些基准可以建立在可控和 可测量的性质，如异常频率和正常点和异常点的“聚集性”。 我们简要概述了主要思想。 给定一个有监督的分类数据集，称为母亲 设置，该方法选择一个或多个类来表示异常类，不同的选择导致异常类的不同属性。 其他班级代表的工会 憎恨正常的阶级。 然后，通过按指定比例对正常点和异常点进行采样，创建单个异常检测基准。
表1概述了Emmott等人的基准。 在我们的实验中使用。 例如，UCI数据集穿梭机被用作母集，以创建1600个不同的异常检测benc 哈马克。
6.2 模拟分析师
我们考虑将分析师建模为从数据点给定特征子集的正常类的条件分布。 更正式地，我们将分析师建模为函数A(x，S)=P(正常|x S)，它返回的概率点x是正常的，只考虑集合S指定的特征。我们描述了我们如何在下面的实验中获得这个函数。 鉴于这一职能，a 点x和x的SFEE，我们可以生成一个分析师确定性曲线，在揭示I特征之后绘制分析师的确定性，即A(x，EI)与I。 图1显示了一个例子 第一曲线从我们的实验使用我们的模拟分析师在一个基准计算从UCI阿巴隆数据集。 每条曲线都对应着一个不同的异常在数据集中使用解释 使用SeqMarg计算。 我们看到，不同的异常导致不同的速率，分析员变得确定异常，即确定点是不正常的。
回想一下，我们提出的质量度量MFP(x，a，E)测量了根据SFEE必须显示给分析师a的特征数，以便a检测异常x。 评估这次会议要求我们定义分析员检测x的条件。 我们将分析人员与检测阈值联系起来，τ∈[0，0.5]，并说如果A(x，E)发生检测，就会对此进行建模
回想一下，我们提出的质量度量MFP(x，a，E)测量了根据SFEE必须显示给分析师a的特征数，以便a检测异常x。 评估这次会议要求我们定义分析员检测x的条件。 我们将分析人员与检测阈值联系起来，τ∈[0，0.5]，并说如果A(x，E)发生检测，就会对此进行建模 i)≤τ，即正态性的概率变得足够小.. 我们将用一个（τ）表示这个分析师。 给定a（τ），然后我们可以通过记录壮举的数量来计算任何异常点的MFP 分析师确定性曲线首先低于τ所需的Res。
当然，选择τ的值没有先验基础。 因此，在我们的实验中，我们考虑了一个离散的 τP（τ）值的分布，它模拟了一系列合理的阈值。 考虑到这一分布，我们报告了预期的MFP-MFP的期望值(x，a（τ），E)-作为定量计量。异常x的SFEE。 在我们的实验中，我们定义P（τ）在0.1、0.2和0.3的值上是一致的，并指出我们的结果在各种合理的选择中是一致的。分配。
它仍然是指定我们如何获得分析函数A(x，S)。 由于我们的异常检测基准都是由一个母分类数据集导出的，所以我们可以构造一个t以上的训练集 异常和正常等级的软管点。 考虑到这一训练集，获得分析师的一种方法是学习生成模型，或联合分布P(正态分布，x)，这可以是用于通过边缘化s中不包括的特征来计算A(x，S)。然而，与判别模型相比，这种生成模型在实践中往往要不太准确。 然而，学习判别模型P(正态|x)不直接支持按我们的要求计算x的任意子集的概率。 虽然为此目的提出了启发式方法(例如。 Robnik-Sik Onja和Kononenko[1]我们发现它们在广泛应用时是不可靠的。 因此，在这项工作中，我们采取了野蛮的方法。我们只是预先学习一个单独的判别模型，每个可能的特征子集到一个最大的大小k。 （我们只是为每个po预先学习一个单独的判别模型最大尺寸k的可扩展特征子集）。然后，评估A(x，S)只需要评估与子集S相关联的模型。
当特征数量或数据点数量很大时，可能不可能预先学习所有可能的子集。 在这种情况下，有一种选择是在实时学习和缓存模型在评估期间需要（每个模型只学习一次）。 我们使用这种方法对我们实验中报道的KDD-Cup结果进行了研究..
当特征数量或数据点数量很大时，可能不可能预先学习所有可能的子集。 在这种情况下，有一种选择是在实时学习和缓存模型 在评估期间需要（每个模型只学习一次）。 我们用这种方法对实验中报告的KDD-Cup结果进行了研究
7 实验
我们现在提出我们的实证评估异常检测基准从Emmott等人。 和常用的KDDCup异常检测基准.
7.5 评估
我们现在显示了UCIKD DCup入侵检测Bechmark[11]的结果。 该数据集中的点有41个特性，我们考虑包含涉及http服务的实例的数据子集。 由此得出的基准包含大约620K点，约4K。表示网络入侵的异常点。 我们再次使用EGMM作为异常探测器。 对所有特征子集进行模拟分析是不可行的，因此我们遵循自适应APProach描述了第6节，其中只学习和缓存了评估过程中所需的模型子集。 总的来说，这导致了大约7.5K RFF模型的培训。 在这里 域，EGMM模型是相当有效的，并将所有异常排序非常接近排名列表的顶部。 因此，我们评估了这个领域的所有异常。
图4显示了我们的方法实现的平均MFP。 显然，边际方法明显优于这里的辍学方法。 特别是，Seq Marg和Ind Marg都实现了平均MFP接近1，这是最小的可能。 这表明EGMM和边际解释的结合在这一领域是非常有效的。 尤其是模拟分析员 只需要平均显示一个单一的特征，以便正确地检测异常。
我们再次假设，辍学方法的性能要弱得多，这是由于它们为早期决策提供了“微弱信号”。 这个问题只在麻木程度较大的情况下才被放大 特征的ERS，就像KDDCup数据一样。
8 主要观察
以上实验的主要观察结果可归纳如下..
- 所有引入的SFE方法都显著优于随机生成的SFE。
- 边缘marginal方法一般不比dropout方法更差，有时也明显优于dropout方法。
- 当使用EGMM异常检测器时，我们观察到顺序方法和独立方法的性能之间几乎没有差别。
- 当使用oracle异常检测器时，SeqMarg的性能IndMarg，这表明在一般情况下，顺序方法可以优于独立方法。
- 总之，根据我们的结果，在我们研究的方法中, SeqMarg是计算SFE的推荐方法。
9 总结
本文介绍了序列特征解释(SFEs)用于异常检测的概念。 主要的动机是减少分析员正确工作所需的工作量 昆虫异常。 我们描述了几种计算SFE的方法，并引入了一个新的框架，允许对解释方法进行大规模定量评估。 我们的实验表明总的来说，计算SFE的顺序边际方法是本文介绍的首选方法。
END
若有收获，就点个赞吧
0 人点赞
