ACE算法：快速、低内存的无监督异常检测

主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1439（局部敏感）计数估计器（ACE）的阵列：边缘异常检测摘要陈罗莱斯大学休斯敦，德克萨斯cl67@rice.edu德克萨斯州休斯敦市anshumali@rice.edu简要描述了一些现代挑战的无监督异常检测是大规模数据处理应用程序中经常用到的重要子程序之一。即使是一个被充分研究的主题，用于无监督异常检测的现有技术也需要存储大量的数据，这从存储器、延迟和隐私角度来看是禁止的，特别是对于具有超低存储器预算和有限计算能力的小型移动设备。在本文中，我们提出了ACE（（局部敏感）计数估计器的Ar射线）算法，可以比大多数最先进的无监督异常检测算法快60倍。此外，ACE具有吸引人的隐私属性。我们的实验表明，ACE算法具有显着较小的内存占用（<4 MB在我们的实验），可以利用任何现代处理器的3级缓存。 在ACE算法的核心，有一个新的统计估计，这是来自局部敏感哈希（LSH）的抽样视图。这种观点与广泛流行的用于近邻搜索的LSH的观点显著不同并且有效我们显示了ACE算法在3个基准数据集上超过11个流行基线的优越性，其中包括KDD-Cup 99数据，该数据是最大的公共基准，包含超过50万个具有地面真实异常标签的条目。1引言异常（或离群值）检测的问题是识别数据中不符合预期行为的实例（或模式）的任务[9]。这些不符合的示例通常被称为异常或离群值，有时可互换。异常检测可以是有监督的[28]或无监督的[20]。受监督的异常检测在被标记为异常或非异常的数据集上利用机器学习算法，诸如分类。然而，有监督的异常检测算法存在三个主要问题：1）在大多数应用中，关于异常的标签信息不可用; 2）异常是罕见的，并且因此存在巨大的类别不平衡，以及3）有监督的算法需要重新训练以用于具有新标签信息的漂移数据分布。漂移数据分布在大数据系统中非常因此，我们感兴趣的是无监督的异常检测，它不需要任何标签信息，并且可以自动处理数据分布随时间的变化。我们本文在知识共享署名4.0国际（CC BY 4.0）许可下发布。作者保留在其个人和公司网站上以适当的归属方式传播作品的权利WWW 2018，2018年4月23日© 2018 IW3C2（国际万维网会议委员会），在知识共享CC BY 4.0许可下发布。ACM ISBN 978-1-4503-5639-8/18/04。异常检测，我们将在这项工作中解决挑战1：高速漂移数据：许多应用需要快速响应和实时推断动态和漂移的大量传感器数据。大多数异常检测应用，例如通过web网络服务器，需要在几秒钟内处理前所未有的数据量数据分布是不断变化的，它往往是突发的[25，29]。实时检测异常事件，如DDoS（分布式拒绝服务）攻击、网络故障等。在监控网络性能方面非常有益挑战2：超低内存预算：在许多高速流应用中，例如高能物理（HEP）和网络服务器，任何需要存储和处理大部分数据的算法都是禁止的。超低存储器算法的另一个关键推动需求是移动电话或智能传感器上的异常检测需要大量资源的算法对于低资源平台是禁止的。挑战3：边缘（移动设备）上的异常检测：便携式设备或移动设备上的异常检测通常需要处理高速漂移数据、低存储器以及另外的超低功率。现代智能手机通常仅具有相对较小的存储器容量（1.2千兆字节）和有限的计算能力。电池寿命是一个重要的问题，将数据传输到云进行分析具有隐私风险，并且由于其能源需求而不可持续随着包括WiMAX和LTE在内的4G（或5G）技术的加速采用，蜂窝设备将成为许多用户宽带互联网接入的主要方式根据思科的报告，全球移动数据流量在2016年底达到每月7.2艾字节[14]。因此，由移动设备监视或生成的业务数据是极其高速和巨大的，并且依赖于需要咨询数据的显著部分的异常检测方法是无望的。不幸的是，大多数无监督异常检测技术是基于近邻的并且需要查询，并且因此需要禁止存储历史数据。挑战4：隐私：随着物联网的普及，消费者必须要求更好的安全和隐私保护，以免他们受到企业监控和数据泄露的影响。因此，存储用于发现异常行为的数据的显著部分是禁止的。隐私保护异常检测本身就是一个具有挑战性的问题[7]。上述挑战的重要性和影响使高速数据挖掘成为十大大数据挑战之一[46]，这也将是当前工作的重点主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1440（D）D[-]H无监督异常检测的流行方法：文献中有许多用于无监督异常检测的方法。我们在实验中对其中11种常用的方法进行了回顾和比较无监督异常检测可以大致分为两类：1）基于近邻（NN）和2）基于聚合统计（或分数）。基于NN的方法通常基于q自身的行为与q的近邻的行为之间的差异来定义点q的离群值分数。第一类是最常见的类别。另一方面，基于聚合统计的方法基于数据的全局函数Sq相对于q的预期行为来定义点q的离群值分数。其中一个值得注意的方法是ABOD（基于角度的离群值检测）[32]。ABOD计算由数据集中入射到感兴趣点q上的不同点对形成的角度的方差。预计异常值的方差较小[32]。存在现有异常检测算法的若干实现。其中一个值得注意的是ELKI包[1]，由于高度优化的实现，它是目前最有效和最流行的离群值检测包之一。这两类异常检测算法都需要存储完整的数据集，以根据数据计算近邻或所需的统计数据瓶颈计算成本是在数据上的至少一次传递以计算近邻或统计。因此，这些方法具有较差的计算和存储器要求。此外，数据分布的变化需要存储和处理更大的观测集采样和快速近邻：为了解决计算要求，自然会求助于快速替代方案[8]。有很多技术可以利用有效的近邻能力来加速NN。然而，它们仍然需要将数据存储在存储器中。即使在计算加速的情况下，这些方法对于超高速数据挖掘仍然是缓慢的，因为在大数据上的精确近邻搜索是昂贵的。依靠随机抽样和数据预测来有效地估计总统计量并不是什么新鲜事[9]。例如，最近，[32]表明使用智能随机采样和散列算法，我们可以加快异常检测，并减少内存需求。而不是存储所有的数据点，我们只需要一些随机样本和它们的量化投影。他们提出了FastVOA，它使用修改后的ABOD统计数据，可以在接近恒定的时间内进行估计，并且与ABOD一样适用于异常检测。然而，这些近似方法仍然需要存储大量的数据样本，这使得算法缓慢并且从隐私角度来看是禁止的FastVOA涉及各种中位数计算和其他昂贵的统计数据。我们的实验表明，基于采样的FastVOA方法是显着慢于快速NN为基础的替代品。在数据流中的滑动窗口上存在第三类异常检测算法[44]。在这些算法中的异常的概念被限制到一个给定的固定大小的窗口随着时间的推移。毫不奇怪，如果增加滑动窗口的大小考虑到大量的数据，我们再次观察而不限于有限的滑动窗口。我们的贡献：我们提出了一个家庭的统计数据，提供了一个“ 这些特殊的统计，由于其形式，可以有效地计算在超低的内存，他们不需要存储甚至一个单一的数据样本。此外，数据的任何更新都可以在运行中合并，使我们的建议非常适合高速数据应用。此外，所提出的算法具有很强的隐私特性，使其成为IoT（物联网）设置的理想选择。我们建议的家庭的统计数据来自碰撞概率的局部敏感哈希（LSH）功能。我们表明，这些类的统计有很强的鉴别属性，识别离群值，最重要的是，它可以准确地估计使用阵列的计数估计（ACE），一种新颖的和微小的LSH为基础的数据结构。设计这些估计器需要使用LSH的采样视图，而不是广泛流行的近邻搜索视图。据我们所知，这是第一次使用LSH计数作为离群值的无偏估计。我们证明，经验和理论上，建议的LSH计数估计是显着更准确的随机抽样方法。我们的ACE算法只需要计算几个局部敏感的哈希数据和一个小的计数数组查找来估计拟议的统计急剧。我们的方法甚至不需要一个单一的距离计算。本文所提出的估计量的理论和类本身可能具有独立的意义。我们在三个公共离群值检测基准上展示了严格的实验证据，包括最大的公开可用的基准数据集KDD-cup 99 HTTP数据集，其具有超过50万个标记实例。从经验上讲，我们的算法只需要大约4 MB的内存和几乎恒定的计算量，对于所有三个基准数据集。因此，我们可以利用快速的L3缓存（3级缓存），这可以比处理主内存快得多。我们提供了我们的算法与11种不同的方法，其中包括一些最快和最流行的异常检测算法的比较。我们的实验表明，在最大的基准测试KDD-cup 99 HTTP数据集上，我们比性能最好的竞争对手快至少60倍 考虑到我们算法的计算简单性和超低内存打印，这种破坏性的加速并不令人惊讶。2背景：位置敏感散列局部敏感哈希（LSH）[22]是一种用于高效近似最近邻搜索的流行技术。 LSH是函数族，使得从该散列族均匀采样的函数具有在散列映射下相似点具有具有相同散列值的高概率的属性。 更确切地说，考虑将RD映射到离散集合0、R1的散列函数族。定义2.1. 局部敏感哈希（LSH）家族A相同的内存和延迟问题。本文的重点是无监督离群点检测，其中异常的概念是家庭Hdx，y∈R称为（S0，cS0，u1，u2）-敏感的，如果对任意两点且从H中一致选取的h满足：• 若Sim（x，y）≥S0则PrH（h（x）=h（y））≥u1主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1441（）（）∼ ()（D）（D）（）下一页θ.DDθ≥（）下一页D（）下一页（）下一页（）下一页D {| ∈ []}nK S（q，D）DD（D）D（）下一页（）下一页∈D独立SRP位，通过采样k次，并使用生成的K位数作为新的S（q，D）=Σπ• 若Sim（x，y）≤cS0则PrH（h（x）=h（y））≤u2当两个数据向量的散列值相等时发生冲突，这意味着h x=hy。LSH是计算机科学理论和实践中研究得非常好的主题。数据库文献在文献中有许多众所周知的LSH家族。详情请参阅[17]最受欢迎的内部点异常值随机投影[11]。符号随机投影（SRP）是余弦近似的LSH边境点0 5 10 15投影数Klarity测量，它源于随机舍入（SRP）的概念[11，18，30]。 给定向量X，SRP利用随机w向量，其中每个分量从i.i.d. 正常，即，wi N 0，1，并且仅存储投影的符号。正式地，SRP族由下式给出：图1：Sq的鉴别能力：从图中可以看出，与非异常值相比，异常值的Sqhw（x）= siдn（wT x）.（一）在开创性的工作[18]中表明，SRP下的碰撞满足以下方程：Prw（hw（x）=hw（y））=1−π，（2）相反，我们专注于评分函数S的类别。. 可以使用可以容易地适合快速处理器高速缓存的微小（存储器效率）数据结构来有效地估计。此外，我们还希望动态更新数据结构特别地，从到j的数据中的任何改变不需要改变，并且估计得到动态调整。其中θ=cos−1XTy| |y| || |y| |.xTy是余弦相似度。| |y| || |y| |我们证明了如下形式的一类得分函数具有上述性质：二二二二如果我们生成Kwindepen-.哈希函数H，则新的冲突概率为Pr（H（x）=H（y））=（1−π）（三）xi∈D其中p是任何LSH族的冲突概率，并且K1是整数。本文的分析自然延伸到任何LSH计划。简单的概率乘法定律 我们将在工作中大量使用这一观察结果。在过去的十年中，在减少摊销计算和存储器需求方面已经有了显著的进步对于这项工作，我们将集中在流行的签署随机投影（SRP）的LSH，因为它的简单性。此外，快速SRP的进步导致了一些非常轻量级的哈希变体。在SRP的情况下，冲突概率p（q，x，i）由下式给出用于计算数据向量的若干LSH签名 对于基于随机投影的LSH，其中有符号随机投影是一种特殊情况，我们可以计算数据向量的m个LSH散列。p（q，xi）=1−1cos−1qTxiq对于尺寸d，在时间上为Odlogd+m，相对于Odm有显著的改进。 由于Fast-Johnson-Lindenstrauss变换的理论[3，15]，这种加速是可能的。 在正交方面，使用基于置换的LSH （例如minwise hashing）获得了O d + m的更好加速，使用了致密化的思想[37-40]。散列时间的这些大幅减少有助于使基于LSH的算法更具吸引力和实用性。3我们的建议用=xii1，n表示数据集，其中n是中的数据点的数量。根据定义，异常值显著与平均数据点分开因此，任何合理其也将是纸的其余部分的p（q，xi）的值3.1它能区分离群值吗？为了证明等式4中评分函数的区分能力，我们进行了类似于[32]中执行的模拟实验。我们首先生成一个带有离群点的简单数据集图1（左）显示了数据的快照有两组数据点。异常值和一般数据点。此外，对于一般数据点，我们在边界点和内部点之间进行区分，如图所示。在图1（右）中，我们绘制了我们提出的统计数据的值对于不同的数据点集合，由等式4给出的IS（q，D）xi相对于所有其他xj∈ D的统计将偏离sig-的功能。我们可以从图中看到1的值对于离群点来说接近于零。特别是，它是标志性的与正常数据点相比，异常值显著即使xi与的所有其他元素的平均距离也是相当好的统计数据[33]。然而，如前所述，计算这些统计数据需要存储完整的数据。一般来说，计算每个单个SXi需要对数据集进行一次完整的遍历。此外，我们的实验表明，基于随机抽样和随机投影的替代估计仍然会导致显着的计算开销。与内部点甚至边界点的相同统计值相比更低这种行为是预期的。注意，我们的统计是所有数据点X1上的LSH映射的冲突概率的总和。根据LSH的理论，碰撞概率pq，xi指示q和xi之间的相似性水平。如果q是异常值，则预期p q，xi显著较低。我们将在实验部分进一步证明这些统计数据的有用性内内部点离群边界点边境异常值地p（q，xi）K，⑷K主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1442（）下一页[]（）∈ D联系我们（D）∈D（）L（D）≤−.×个（D）（）下一页.ˆ--∈DS（xi，D）=L（）下一页Lˆj=算法1（局部敏感）计数估计器阵列（ACE）算法1：输入：数据集D，哈希数K，哈希表数L，α2：散列初始化：生成L_H_j。每个使用K个独立的SRP。3：对于i=l至L，做4：Aj=新短2K0（短阵列）5：μ=0，n=06：结束数据点...计数数组7：在线添加阶段8：对于x我做9：μincre =010：对于j=l至L，do图2：我们使用数据点的LSH散列将相应的计数器增加到不同的（独立的）散列数组中。我们不保存任何东西，我们只为每个桶增加1的值，然后忘记数据。11：Aj[Hj（xi）]++12：μincre =μincre+13：结束。+12Aj[Hj（x）]+1ΣHj（x）=[hj 1（x）; hj 2（x）;…;hjK（x）]，每个为K位K位是联系我们14：μ=n115：n++;16：结束nμ+μ增加通过级联各个比特来生成这里hij，i1，2，…K以及j1，2，…是SRP的KL独立评估。整个算法在以下两个阶段工作1) 计数相位：我们构造L个短阵列，Aj，j ={1，2，... L}，17：查询（检测）阶段：给定查询q18：S q， =019：对于j=l至L，do20：S（q，D）=S（q，D）+1Aj[Hj（xi）]大小为2K，每个初始化为零。给定任何观察到的元素x，我们递增数组Aj中相应计数器Hj x的计数，对于所有j s。因此，每个计数器都保存对该特定索引的命中数的总计数（参见图2）。对于任何给定的x，更新数据结构的总成本是KLSRP21：结束22：如果Sq，μ a，则23：报告q24：如果结束计算之后是L增量。平均动态更新对于每个xi∈ D，我们的估计得分为1 .一、Lj=13.2ACE算法我们计算数据集x∈ D中所有元素的得分的平均行为μ。为了便于解释，我们首先描述我们提出的ACE算法的程序。我们后来表明，这一程序是一个有效的统计估计我们提出的离群得分1Nμ=ni=1S（xi，D）.S q， 由等式4定义。在算法1中总结了ACE的总体过程 我们的ACE算法使用Kk个独立的SRP散列函数，每个散列函数由等式1给出。K和L是预先指定的超参数注意，这类似于用于近邻搜索的传统K，L参数化LSH算法。然而，我们不执行任何检索，这需要沉重的哈希表偏离该平均值将指示异常值。事实证明当我们读取（或观察）新数据时，我们可以动态地更新平均值μ，如算法中所示详情见第3.4.1节。2) 实时（查询）阶段：给定我们想要计算分数的查询q，我们报告所有计数器的平均值Aj[Hj（q）]j∈{1，2，…. ，L}，i. e. ，S（q，D）=1L1Aj[Hj（q）]。We（D）具有用于每个散列索引的候选的桶对于近邻，我们还需要计算这些候选项到找出最好的相反，我们的算法不需要一个单一的距离计算。我们的方法只需要在每个索引处检查一个简单计数器的值我们只需要计数器数组与单个LSH近邻查询相比，该过程在内存和速度方面都非常高效。我们使用给出一位输出的带符号随机投影（SRP）hsim（等式1）。使用这些1位输出，然后生成L个不同的元散列函数，由下式给出如果估计得分Sq，则将q报告为异常，小于μα，其中α是某个预先选择的超参数。整体查询的成本是KL个SRP计算和L个查找，然后是简单的平均计算。3.3随机抽样理论的分析及其优越性我们首先定义几个符号需要分析。给定查询点q。 为了方便起见，我们将用pi表示q的SRP与xi的SRP的冲突概率。由于篇幅所限，这些证明被省略了。+1个内部点边境点异常值+1个+1个+1+1+1个LAj [Hj（xi）]。1...1...450...1...10......3467主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1443我∈iq我∈∈iqjq∈∈iqjq∈D我.（D）（D）我我Hj（q）是S（q，C）=np（q，xi）K.这然而，对于真实数据集，对于任何随机选择的对xi，xi，j，q在同一个桶中应注意piL−1pi我 J协方差Cov（Ixi∈Bq，Ixj∈Bq）几乎总是负数。直觉：LSH作为采样器LSH被广泛接受为黑色将贡献负项−pKpK。因此，如果我们选择K大最近邻搜索框算法我们采取另一种适应方法-我Jm是最近出现的LSH的有效采样视图[10，12，bucket中元素的期望数量很小。因此，我们可以预期方差显著13、41、42]。如第2节中所论述，对于给定查询q和K位SRP，小于。.npK（1−pK）Σ。我们在实验中观察到哈希函数Hj，任何元素xi递增的概率i=1i L数组Aj中的位置Hj（q）（查询的位置）的计数精确地为p（q，xi）K。使用这个观察，我们将表明从D到t的元素的数目的计数。他的桶queryi=1LSH作为统计估计的有效数据结构的新用途K=15是一个很好的推荐常数值。如上所述，方差取决于数据分布。如果我们有所有精确的重复，那么所有的协方差都是正的。本身可能具有独立的利益我们定义指示变量Ixi∈Bq为估计S（q，D）的替代方式是使用随机取样. 其思想是对大小为S D的子集进行均匀.1、 如果x在q我Q，否则。L，并将随机抽样估计器RSE（q，D）报告为：Ix∈B =0（五）n .K在这里，我xB查询是用于数据元素xi和xi∈S从随机抽样的理论来看，这个估计量也是无偏的Pr（Ixi∈Bq =1）=p（q，xi）K=pK（六）并且具有以下方差：理论3.2.注意，IX B和IXB相关。如果xi和xi是“换言之，高相似性指示正相关。 由于相关性，E[RSE（q，D）]=X.我pK=S（q，D）我们可能有两种情况：≥pKpK，（正相关）.nK. Σn（七）i=1ΣKΣ≤pK pK，（负相关）。我J这里，E是期望值。RSE q和Sq都是无偏的。对于相同的样本数，方差较小的估计量是优越的。使用上面的符号，我们可以表明，对于给定的查询我们可以从主要术语中得到一些启示。npK.Σn−在算法1中计算的q，S（q，D）是ΣΣΣi=1i LS（q，D），方差由下式给出1pK和1 .npK（1−pK）。一般而言，对于任何i和large理论3.1.i L i=1i.如果n足够多，我们总是有n-1≥1（1−pK）。因此，对于大E[S（q，D]=xi∈D pK=S（q，D）够了RSE（q，D）=L[（11）V ar（RSE（q，D））=E[Ixi∈BqIxj ∈Bq]我主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1444p.Li=1pi（−pi）相依相关将ACE估计器的数据集设置为更准确（方差更小）com-ΣΣ我我LLK1. .nK Kn>主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1445我们所有实验中使用的固定值RSE（q，D）S（q，D）.nΣV ar（S（q，D））=L pi（1−pi）1 .一、V ar（RSE（q，D））>pK（1−pK）主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1446i≠jLi=1我我L我 JLi≠jxi∈Bqxj ∈Bq我 J⇒两者均为1）。时间复杂度O（（n-m））i=1.主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1447KK ΣLi=1i i.Σ+E[Ixi∈BqIxj∈Bq]−pipj对于可以执行1的实际数据，最好使用参数 .nK1KS（q，D）的方差是相关的。关于数据分布。Var（S（q，D））. 通过对不同的材料进行精确的数学比较在方差1中有两个项 .npK（1−pK）和这两个估计量的差异是相当具有挑战性的，由于数据-1 .一、i≠j。E[Ixi∈BqIxj∈Bq] −pKpK.. 求和中的项是经验比较：如前所述，我们预期Ixi∈Bq和Ixj∈Bq之间的协方差E [I xi∈Bq I xj∈Bq]−pKpK =E[ Ixi∈Bq Ixj∈Bq]（8）与随机抽样估计量相比来验证我们的论点主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1448经验上，我们比较这些估计的三个基准主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1449我J–=Cov（Ixi∈Bq，Ixj∈Bq）（10）主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1450异常检测数据集。这些数据集与实验部分（详见第5.1节）。对于所有三主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1451在方差的第二项中存在n（n-1）个协方差项数据集，我们随机选择了50个查询，并估计它们的S（q，D）1 .. E[II]− pK pK. . 来看看为什么几乎所有的使用两个竞争估计器。我们使用K=15，这是主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1452将为负数，设m为桶中的元素数的查询。所以只有对xi和xj在桶（O（m2）对）的查询Hj（q）将对求和（乘积）贡献1−pKpK≥0主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1453我们绘制估计值的均方误差，使用实际值和估计值对三个实际异常检测主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1454数据集，如图3所示。我们随机改变样品的数量主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1455我J指标为12 ）抽样估计量和的数组数。主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1456Ace随机抽样Ace随机抽样均方误差均方误差ˆ（）下一页（）下一页（D）（）下一页（D）（D）不超过×× ×× ××DD（）下一页（D）|D|.D（）下一页JJ我2.5#随机抽样的抽样集大小#随机抽样2#随机抽样221.5 1.51.51110.50.50.50 5 1015ACE的查找表数量（L）00 5 1015ACE的查找阵列数（L）00 5 10 15ACE的查找阵列数（L）图3：ACE估计量与随机抽样估计量在三个数据集上的比较X轴分别表示ACE估计器和随机抽样估计器的阵列数量从计算的角度来看，ACE估计不仅更准确，而且比随机抽样估计更便宜。从图中可以清楚地看出，在所有三个真实数据集上，如从我们的分析中所预期的，我们的ACE估计量Sq在相同的L水平上始终优于随机抽样估计量RSE q。注意，这些估计量是无偏的，因此均方误差值也是理论方差。这些实验表明，我们的ACE估计的方差是优于估计Sq，随机抽样。除了提供更清晰的估计，在下一节中，我们表明，我们的ACE算法只需要O d log d + KL计算，计算分数。这里，d是数据集的维度。 对于相同数量的样本L，随机采样估计器需要OLd计算。 假设K = 15是一个固定常数。对于高维数据集，我们将有d>K。因此，我们的估计是不仅更准确，但也更便宜的随机抽样估计从计算的角度来看。3.4实现细节、运行时间、缓存利用率和内存运行时间：从算法1中不难看出，对于查询q，我们需要计算数据的KL哈希，然后简单地加上大小L。最昂贵的步骤是KL散列的计算，对于d维数据，可以使用快速随机投影的进步在O d log d+ KL计算中完成（第2节）。 如果相反，我们使用minwise哈希作为LSH则可以在仅仅O（d+KL）中使用快速minwise来完成如果我们使用短计数器，则L个计数器阵列所需的内存总量为每个2K字节数组所需的总空间为L2K 2字节。对于K= 15和L=50，ACE算法所需的总空间约为3。2MB。此外，我们需要计算KL=750个哈希，这需要存储750个随机种子（整数），我们可以从中动态生成哈希750个整数与3个整数相比所需的空间可以忽略不计。2MB。 在最坏的情况下，即使我们决定存储完整的随机投影，我们也只需要750 d 8字节（约6 d千字节）。L3缓存利用率：对于我们所有的实验，ACE算法的总内存需求是所有数据集的4MB。我们的查询数据结构，数组，可以很容易地适应任何现代处理器的L3缓存，其中内存访问可以是2- 10倍的速度比主内存（DRAM）访问的任何地方。检测异常需要评分，其仅需要来自阵列的读取计数。 由于所有这些独特的有利属性，我们的算法是数量级的速度比最快的无监督异常检测软件包。3.4.1动态更新。ACE算法的吸引人的特征之一是数据可以动态更新。如果我们决定添加任何数据x，则直接递增计数器。但是，我们将丢失所有的数据信息。我们只存储了一组count数组，因此不清楚我们如何更新全局计数的平均值μ更新μ是算法1的重要部分注意，更新后的平均值μJ应该是所有散列。然而，minwise散列仅限于二进制数据集。J=+x中所有数据的估计得分。结果表明我们可以精确地计算出μJ的新值注意，经由朴素计算来计算原始得分Sq需要O次计算。对于高维高维数据的异常点需要存储所有的从现有的计数数组。为了简化，让我们把旧的意思μ通过将其乘以数据集n =的大小来求和。记录总数是数据集可能是禁止的。在我们所有的实验中，我们对所有三个数据集使用K = 15和L= 50（见第6节）。因此，有了这些小的常数值，我们的nμ=X.我1LLj=1Aj [Hj（xi）]。与其他算法相比，评分时间可以忽略不计，其他算法需要在整个数据集上通过一次。在实验中，我们看到，即使使用如此微小的计算，我们的方法也提供了具有竞争力的准确性，同时比11种最先进的方法快了几个数量级。注意，如果新的x到达数组Aj中的位置Hjx，则对于任何j。位置Hj的计数将递增1。 这也将导致映射到数组中的Hj（x）的所有元素的得分增加精确地L1。由于我们已经知道A[H（x）]的计数值，因此总和的总增量将是内存：由于我们有2K计数器，因此不太可能计数器将获得太多命中。 为了节省两倍的内存，我们可以使用短整数（16位）代替整数计数器。Aj [Hj（xi）]。此外，新数据X将添加额外的Aj [Hj（Xi）]+1，用于itLs〇wn_count。因此，我们可以精确地计算总和的增量对于数据X的加法，新的平均值μJ可以是Ace随机抽样均方误差∈D主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1457（）下一页计算为J1.一、n+1.L2Aj[Hj（x）]+1Σj=1L表1：三个数据集的统计4讨论：隐私保护异常检测隐私正在成为数据挖掘和机器学习中的一个热门方向 隐私保护异常检测在大数据和IoT（物联网）社区中引起了广泛的兴趣[45]。在许多设置中，我们确实希望检测数据中的异常然而，还期望属性信息保持私有和安全。结果表明，我们提出的ACE算法具有理想的隐私保护异常检测性能。ACE不需要存储任何数据属性，并且完全算法仅在从散列数据生成的聚合计数上起作用。如果散列不是可逆的，则算法是安全的。 我们可以利用安全计算的进步来设计隐藏哈希机制的协议[19]。使用ACE获得差异隐私[5，31]是非常有吸引力和整洁的。 由于ACE算法依赖于随机投影来计算散列，而不是原始数据，因此我们可以通过仅添加高斯噪声而不是重尾拉普拉斯噪声来使ACE算法差分私有。[24]示出了一种以隐私保护方式释放用户信息以用于近邻搜索的方式。证明了在随机投影后加入高斯噪声N0，σ 2可以保持差分隐私。差异私有对象的任何函数也是差异私有的。因此，为了计算SRP（有符号随机投影）的私有变体，我们使用差分私有随机投影的符号（通过将高斯噪声添加到通常投影来生成），如[24]中所建议的。最后的算法非常简单。数据永远不会透露给任何人。 在源本身处，使用数据的差分私有随机投影的符号而不是通常的SRP。所有其他过程保持不变。 现在，因为我们只使用高斯噪声而不是拉普拉斯算子来干扰我们的算法，所以我们可以预期效用损失（或输出变化）最小。注意，使用存储实际数据或甚至样本的其他最先进的异常检测算法，隐私明显更难 使这样的算法私有化需要用重尾拉普拉斯噪声扰动系统，这可能会严重损害算法的结果。5实验评价5.1数据集我们选择三个真实世界的基准数据集进行异常检测：1）StatlogShuttle，2）Object Images（ALOI）和3）KDD-Cup 99HTTP。这些数据集被标记，因此可以用于量化异常检测措施的有效性。这三个数据集还涵盖了无监督异常检测的广泛应用。我们使用的第一个数据集是shuttle数据集1。此数据集来自-在NASA航天飞机中使用9个属性记录散热器位置表2：为这些基准数据集推荐的比较算法及其参数值。方法班车图像对象KDD-CUP 99AceK=15，L= 50K=15，L= 50K=15，L= 50LOFK=5K=5K=10KNNK=5K=5K=10kNNWK=5K=5K=10回路kr=kc=5λ= 0。2kr=kc=5λ= 0。2kr=kc=10λ= 0。2LDOFK=5K=5K=10奥丁K=5K=5K=10KDEOSK=5B= 5，s= 0。2高斯核K=5B= 5，s= 0。2高斯核K=10B= 5，s= 0。2高斯核COFK=5K=5K=10LDFh= l，c= 0。1高斯核h= l，c= 0。1高斯核h= l，c= 0。1高斯核INFLOk= 5，m= 0。5k= 5，m= 0。5k= 10，m= 0。5FastVOAk=5，|S2|=2，|= 320|=320k=5，|S2|=2，|= 320|=320k=10，|S2|=2，|= 320|=320数据集，约20%的数据被视为异常。整个数据集包含34，987个实例和879个异常。第二个数据集是对象图像（ALOI）数据集2。阿洛伊数据集来自“它包含了在不同光线条件和视角下拍摄的1000个小物体的大约110张图像 从原始图像中，使用HSB颜色直方图提取27维特征向量[35]。选择一些对象作为异常，并且对数据进行下采样，使得所得到的数据集包含50，000个实例，包括1508个异常。第三个数据集是KDD-Cup 99 HTTP 。 3 . 第 三 章。KDD-Cup99HTTP数据集[28]是无监督异常检测评估的最大基准。 它包含在计算机网络环境中的IP级别上的模拟正常和攻击流量，以测试入侵检测系统。总共有36个维度。该数据集包含596，853个实例，具有1055个标记的异常。这些数据集的统计数据如表所示1.一、5.2基线我们使用11种不同的最先进的方法与ACE进行比较。 这些方法涵盖了非监督异常检测技术的整个频谱，这些技术具有多年来开发的各种变化。 我们的基线覆盖了基于简单到复杂策略的最新评分机制，包括近邻、核密度估计、图连通性等。相互竞争的方法有：ACE（拟定），它被设计用于监督异常检测。在原2http://aloi.science.uva.nl/1https：//archive.ics.uci.edu/ml/datasets/Statlog+（Shuttle）3http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html=μnμ+.（十二）数据集实例异常值尺寸Statlog Shuttle34，9878799对象图像（ALOI）五万150827KDD-Cup99五九六八五三105536主题：Web of Things，Mobile and UbiquitousComputingWWW 2018，2018年4月23日至27日，法国里昂1458表3：比较结果报告的日期设置方法正确错过F1 得分F1-Rank Time（s）使用ACE加速ACE6763 273 606 0.071 50.81s1xLOF 4356 381 498 0.145 3 14.12s 17.4xkNN 4897 493 386 0.170 2 12.35s 15.2xkNNW 5264 610 269 0.199 1 13.54s 16.7x环6145 201 678 0.057 8 14.51s 17.9xStatlog Shuttle图像对象KDD-CUP 99LDOF 6433 330 549 0.090 4 16.42s 20.3xODIN 9775 375 504 0.071 6 12.21s 15.1xKDEOS 12630 314 565 0.046 12 11.73s 14.5xCOF 9133 280 599 0.056 11 13.45s 16.6xLDF 9809 375 504 0.070 7 19.93s 24.6xI