简介
异常检测系统
eBay的DSS(Data Services and Solutions)部门开发并维护了一套名为MMD（Moving Metrics Detection）的系统，用于各项业务指标的搜集与监控。业务指标包含了流量（浏览、点击、搜索等），订单（下单率、拍卖单数、成交单数等），支付（gmv等），风控等各个领域。大部分指标以日级粒度落表，少部分以小时级粒度落表。异常检测模型对每个指标进行检测，当指标发生突增或突降时，即发出报警（以邮件订阅或StoryBoard方式）。
（点击可查看大图）
异常检测模型由MMD团队自研，它采用了STL（Seasonal and Trend decomposition using Loess）[1]的思路并做了更细致的处理：将过去一段时间的指标拆解成趋势项、周期项和残差项。在分解之前，时间序列会进行一次傅立叶变换（有关傅立叶变换可以参考文章[2])，将原始的时间序列进行一定程度的平滑。趋势项代表了整体指标的走势情况，它将多个邻近点汇总成一个点（取中位数），再使用滑动窗口得到走势；周期项对于日级别指标而言，通常取七天为一周期。以周期为窗口进行滑动聚合，获得周期内每天的取值。如下图所示：
（点击可查看大图）
当有了趋势项和周期项，则可据此对时间序列进行预估，得到未来时间点下的数据。同时，也可以对过去一段时间数据进行拟合。用每日实际值减去拟合值，即为波动的残差项。我们认为残差项是平稳序列，符合正态分布。检测平稳序列下的异常值有很多方法，这里我们使用MAD[3]算法。对于最新的一个点，使用预估值与实际值算得残差项，当该残差项超过MAD给出的正常范围时，就认为该点为异常。
★
关联分析Correlation
1
简介
当用户发现指标异常时，首先关心的是引发异常的原因是什么。为了更好地帮助用户进行问题分析，同时提升平台的洞察能力，我们在异常检测的基础上，设计了关联分析的产品。关联分析(Correlation)并不是归因：存在因果关系的两个指标大部分有一定的关联性，但反之未必。单从因果推断的角度讲，倘若有完整的指标上下游关系链，则可以借此进行归因分析。但遗憾的是，我们的指标来自于各个不同业务领域（如流量、广告、风控、支付等），很难给出它们彼此间的拓扑关系。因此，我们退而求其次，致力于找寻与发生异常的指标相关的指标，将它们提供给业务及分析人员，辅助他们进行归因诊断。虽然这个相关关系不能完全准确地反映真实的因果关系，但是仍然可以为诊断提供一些很好的线索和启示。
由于我们的指标都以时间序列的方式来表达，通常以天为单位，而一段时间序列天然可以看成是向量。因此，我们使用向量的相似度来表达它们的相关程度。向量的相似度计算方式有很多，这里我们采用余弦距离，从而屏蔽掉量纲影响，使得两个指标只要在线型上相似，就会有较高的相关度。如下图所示（基于业务数据保密的原因，对坐标轴进行了隐去处理）。
（点击可查看大图）
2
问题与挑战
对每一个异常指标，在全库中通过余弦距离来检索其相似指标，显然是颇具挑战性的。挑战之一在于搜索空间十分庞大，我们目前全库中的指标大约有2000多个，但每个指标有不同的维度（即dimension，如国家，类目，设备类型等等），不同维度下取值的排列组合使得指标的量级猛然增大。作为第一版产品，我们仅使用面向分析师的核心指标作为产品启动数据，这些指标大约有700-800个，按照维度组合展开则大约有70000-80000个左右。对每个异常指标都在这样的空间中去搜索相似向量，将会是十分耗时的。而未来我们将会对更多指标进行相关性分析，因此需要考虑内存空间的可支持性及计算性能。
第二个挑战来源于向量相似度的计算方式，我们取过去90天的时间序列，对应一段90维的空间向量，若使用逐点计算的方式，则在原来计算次数之上还要乘以90，即90*1000*80000（按每日约1000个左右异常指标计），考虑到未来更多指标的加入，性能上显然是难以接受的。因此我们需要通过一些方案解决这两个挑战。
3
相似指标的召回
对于搜索空间巨大的问题，我们采用spark分布式计算来解决；对于向量相似度计算的问题，则采用高维向量索引的解决方案。接下来我们详细来谈谈：
一、先来看下向量相似度计算：实际上，向量相似度计算的方案在业界已十分成熟。在广告及推荐领域，许多商品、文本、用户等都采用向量方式来表达，因此线上召回需要有高效的相似向量检索方式。高维向量索引是对快速检索相似向量的解决方案的通称，常见方法包括：Hashing、向量乘积（Product Quantization，即PQ）、基于KD-树的方案、基于图的方案。这里我们采用了向量乘积，它是高维向量的一种压缩算法，能满足大部分的研究，以及实时性要求不是特别高的场景。PQ对应有非常成熟的解决方案--FaceBook开源的Faiss软件库，它支持了在任意大小向量上搜索算法，也支持评估和参数调节。
它的原理大致如下图所示：假设有50k个1024维的向量，每个向量都被划分为M（通常取8）段，每一段使用K-means算法进行聚类，聚成K个中心点（图中为256个），每一段的向量都使用其聚类中心表示，这样就压缩了向量的表达空间。K通常取256，使用8bits可以表达，这样每一段就变为8位向量空间，最终向量从``50k * 1024 * 32 bit``的空间，压缩成了``50k * M * 8bit``的空间。
（点击可查看大图）
当计算query与空间中某个向量x的距离时，可以计算该query所在聚类中心与x所在聚类中心的距离，该距离可预计算，因此在线查询的效率很高；另外，也可以计算query本身与x所在聚类中心的距离，需要线上计算，查询效率相对低，但更准确。
从性能上看，若要查找最相近的k个邻居，PQ仍然是不够的，因为仍需要遍历M*K次。IVFPQ在PQ基础上对这个问题进行了很好的解决。它的思路是，先对N个向量进行K个聚类，每个聚类中心索引其类内向量。查找时，先对聚类中心进行遍历，找到最近的聚类中心，再进行类内的PQ查询。
二、基于Faiss所提供的高性能检索方案，我们可以较为容易地解决向量相似度计算问题。对于潜在搜索空间巨大的问题，我们则采用spark的分布式解决方案，如下图所示：
（点击可查看大图）
我们先将搜索向量空间均匀地分成若干份，分发到spark上的不同计算节点上；接着将query（在这里，我们的query指发生异常的指标所对应的向量）拷贝分发到spark上的每个计算节点上。在每个节点上，我们使用Faiss来召回相似向量，再经过排序（基于相似程度）和截断，将头部向量汇总返回，汇总后的相似向量再经过二次排序（基于业务逻辑）和截断，计算出每个异常指标的关联指标，汇总后同时写入HDFS和线上库，用于查询。
通过分布式的计算方式，可以将搜索空间进行拆分，从而减轻了每个计算节点的工作量，使之具有较高的可扩展性和较好的计算性能。
除了相似指标，我们同时提供了相反指标的召回，如下图所示。因为有些指标天然相反（如展现与点击率），相反指标可以捕获这种关系。
（点击可查看大图）
4
面向业务的推荐
一般来说，Correlation应该是一个严格的数学上的计算，但如果不考虑业务场景，就会有很多荒谬的结果，如[4]、[5]中所展示的一样。我们也可以看下面一个例子，当所有时间序列仅仅采用余弦相似度进行排序，而不考虑其他因素时，会有大量相同指标（仅仅是维度不同）以及业务上看起来毫不相关的指标出现在搜索结果里：
（点击可查看大图）
由于搜索结果条目数限制（条目数的限制来源于两点：
1、从产品角度考虑，条目数过多无法给用户快速提供有效信息；
2、受限于线上工程的检索性能），在有限的条目里出现大量冗余信息，显然不利于有效信息的提供。
因此，在使用Faiss召回相似时间序列后，我们加入了一个排序模块。
排序逻辑包含以下若干逻辑：
对指标进行压缩，同一个指标仅仅是维度不同，只保留最重要的几个，重要性判断逻辑如下：某指标的子维度（如site:ebay.com与site:ebay.com;device:ios是父子关系）仅部分异常，则保留该指标子维度中有异常的指标，并按照相似度排序截断；若子维度全部有异常或全部无异常，则仅保留该父维度的指标。
对某些维度进行适当过滤，如最重要的site，country等维度，当存在大量结果时，仅保留与原始异常指标具有相同site或country的（如果召回结果中不包含site，country维度，则不过滤）；
使用调整的Jaccard相似度来计算相关指标的相似度，即：使用加权后的维度的交集除以加权后的维度的并集（这里并不是维度越相似越好，想一下如果原始异常的维度是device:android,相关异常是device:ios甚至是非device维度，反倒会提供更多信息，因此除了国家、site等重要维度，其他维度不会给予过高权重）。
熟悉推荐系统的读者，可能会看出，我们的相关向量搜索过程与推荐系统非常相似，都包含了召回和排序过程。事实上，我们正是使用推荐系统的思路来不断改进和完善correlation系统的：
（点击可查看大图）
自下而上地，我们通过多路召回手段找出与原始异常指标相关的指标，接着使用业务或模型的方式来对召回的指标进行整体排序，继而从业务角度对排序后的指标进行取舍，最终将结果返回给用户。可以看出，我们前面所介绍的系统中，召回手段仅仅是通过时间序列相似来比较和过滤，那么是否还有其他的召回手段可以从不同角度来找出相关指标呢？接下来，我们来介绍下另一个相似指标召回手段：Graph embedding。
★
Graph Embedding
“
背景介绍
MMD平台上的指标（metrics），一般使用spark sql产出，因此我们可以获取原始的metrics来源：
（点击可查看大图）
从这样的语句中，我们可以解析出源表和目标指标，从而构建起从源到目标的指向关系。基于大量的指向关系可以构建出一个完整的图。下图使用neo4j来展示MMD上部分指标的图关系。我们使用了某天的报异常的数据。其中，蓝色节点代表源表，红色节点代表当天有异常的指标，橙色节点代表正常指标。
（点击可查看大图）
“
Graph Embedding的构建
我们可以充分利用图关系，来构建指标间的相关关系。比如使用规则的方式，对于同源的两个指标，认为具有一定的相关性，或者是有多个源的指标，相同源的交集越多，就越相似。但是，规则很难穷尽所有情况，且计算方式相对粗糙：如图中的三个源a、b、c和是三个指标metricsA、metricsB和metricsC，metricsA和metricsC虽然并不同源，但以metricsB为媒介，两者可能具备一定的远亲关系，使用规则的方式则很难捕获这类情况。为了能够充分利用指标的图关系，我们采用了图嵌入(Graph Embedding)的方式来探索指标的相关性。
（点击可查看大图）
有关Graph Embedding的相关介绍有很多，感兴趣的读者可以自行查阅，此处仅作一个简要说明：在图中通过随机游走可以抽取出大量短序列（3-10个左右），通过对每个抽样序列中单节点的预测（源空间通过隐层，映射到目标空间，期望是目标空间每个节点与源空间尽可能保持一致），来构建一个神经网络，当对目标空间的节点们的预测达到一定的精准度时，训练完成。这时，隐层向量就代表了图嵌入向量。
（点击可查看大图）
Graph Embedding有非常好的特质：训练好后，每个向量对应图中一个节点，当图中两个节点较为相近时，它们的向量距离也会非常近。基于这样的特质，对于发生异常的指标，我们就可以召回其相似指标了（相对于上文的correlation所述的线型相似，Graph Embedding所说的相似，指的其实是图拓扑关系上的血缘相似）。
“
两种方式的比较
通过Graph Emebedding对图节点进行向量化之后，其后的召回也是使用Faiss召回，排序方式则与Correlation类似，具体细节不再赘述。我们可以通过一个例子来观察Correlation和Graph Embedding两种方案的不同之处：
（点击可查看大图）
上面表格记录了2022年11月某天，ipad会话的跳出率发生了异常，这个异常出现在意大利这个site，且发生在首页。我们看一下Correlation召回的结果，记录如下：
（点击可查看大图）
从上面结果中可以看到，跳出率异常不仅仅发生在iPad的首页上，同样发生在iPhone上，以及除首页之外的其他页面上，因此可以推断该异常并非是由于某些页面更新引发的，极有可能来自于iOS系统流量上的异常。接下来，我们看看Graph Embedding提供给我们怎样的视角：
（点击可查看大图）
Graph Embedding更多地告诉我们，该异常并不仅仅发生于意大利，同时也在其他国家同时也发生了异常。这两种不同的召回方案，向我们呈现的是不同方面的信息，使得用户能够更加精确地把握异常的波及范围。
案例
Graph Embedding中所述的例子，对于原因的分析是基于召回结果的猜测，但并没有Ground Truth的数据来验证。这里，我们给出一个被验证过的案例，以更形象地说明关联分析的价值。
（点击可查看大图）
在2022.6.17日，GMB（买家产生的GMV，可近似认为是GMV）相关指标发生了一个极大的上升，该指标异常发生的site是美国，另一个dimension是iPad这个设备。我们来看看correlation在当天给出了怎样的结果，这些结果又给我们怎样的启示。
（点击可查看大图）
Correlation结果中，有几个比较重要的指标，如core abp，它代表当日商品的单均价格。这个指标的显著异常，说明了GMB的异常并非是总体商品量突增（否则单价不会出现同样大的异常），很可能来源于少量商品的高价出售。另一个correlation结果auction gmb share则告诉我们，这个异常显著定位在拍卖中，结合分析，我们大概得出结论：当天有一件或几件拍卖品拍出了天价。那么，当日究竟发生了什么？
我们追溯当日新闻，就会发现，ebay平台上当天发生了一项著名拍卖：巴菲特的天价慈善午餐，这就是导致GMB异常的真正原因。可以说，Correlation的结果已经非常接近事实真相了。
Localization
下钻定位
对于归因的探究，我们并不仅仅局限于Correlation。事实上，我们还有另一个方向的研究：下钻定位（Localization）。从业务角度探究，Localization应该置于Correlation之前：下钻定位是指当某个指标发生异常时，究竟是哪个或哪些维度引发的异常。打个比方：一个人腹部疼痛，医生首先关心疼痛是出现在肝脏、脾脏还是胃部（Localization），其次才会关注引发疼痛的外在原因，是饮酒过量，还是感冒发烧（Correlation）。如上面那个GMB的案例中，下钻后会发现GMB的异常最终定位到ebay.com这个site（说明是在美国发生的异常），以及iOS平台。其次再来关注是由哪些原因（高价拍卖）引发的异常。
下钻定位该如何实现呢？
上面的GMB突增的例子比较简单，通常情况下，一个指标会有五个以上维度，维度彼此间排列组合形成笛卡尔积。同时，当异常发生时，并非仅仅只有一个子维度组合会发生异常，可能很多维度组合下都有或多或少的异常。那么找到根因（root cause）就需要一些技巧了。下面样例表展示了一个指标不同维度组合下预测值、实际值的波动情况：
（点击可查看大图）
直觉上看，我们使用每个子维度下实际值与预测值的差异，除以总指标实际值与预测值的差异，得到的delta占比，就能代表该维度组合下的波动程度对总体波动程度的影响。这样做似乎非常符合逻辑，但现实并非如此。
一方面，这种算法仅适用于可加指标，如GMV，PV等，而对于ratio类指标--如点击率、单均价等则不适用；另一方面，这样的计算存在一个问题：有些维度天然占有较高比例，那么所有的变化几乎都会归因于这个占比极高的维度，使得真正的root cause难以被发现；另外还有dimension彼此交叠的情况，使得root cause更难被发现。举一个例子，假设我们仅有两个维度：国家与用户群（注册时长小于180天的用户/注册时长介于180-1年的用户/...）。假设某个国家为新开拓市场，因此所有的用户都是新用户。
（点击可查看大图）
如上图所示，假设某天因为当地的app更新，导致流量异常，就会发现该国家与新用户群的delta贡献占比都是100%，那么难道两者都是root cause么？显然并非如此。虽然这个例子是为了便于理解而虚构的，但现实场景中这种问题所在皆是，且更为复杂。因此需要一个正确的方式来挖掘root cause。
为了合理正确地下钻定位，我们查阅了多篇资料，最终选择微软的研究《Adtributor: Revenue Debugging in Advertising Systems》[6]来设计我们的Localization。具体算法不再详述，感兴趣的朋友可以阅读原文。其最核心的思路是设计了一个叫惊奇度（surprise）的指标：该指标比较子维度下两个值（预测值和实际值）的分布和总指标两个值分布间的差异，即KL散度，稍作调整改为对称型指标js散度。子维度与总指标的js散度越大，则认为该子维度的贡献越大。该论文同时提供了ratio类指标js散度的计算方法。该算法最核心的python代码如下：
（点击可查看大图）
我们用这段代码看一下前面虚构的例子，就发现国家和用户群的惊奇度分别如下：
（点击可查看大图）
新国家市场的惊奇度要高于用户群，说明国家这个维度才是真正的root cause。我们对原始算法稍作修改，一方面对原始论文仅能计算一层维度的限制进行扩展，使得用户可以不断下钻找到影响最大的维度组合；另一方面对分数进行合理的变形和归一化，使得用户更易理解。
这是我们线上使用该模型的产品：
（点击可查看大图）
Summary
总结
在业务监控中，异常原因诊断具有很高的实际应用价值。Localization可以帮助用户快速定位引发异常的具体维度；而无论Correlation或是Graph Embedding都能够揭示引发异常的可能的业务原因，有助于用户快速反应，减少大量人工分析的时间，并消弭异常引发的损失。
我们未来的工作主要着眼于两个方向：
\ | /
★
一、更多数据的获取：一方面，我们寻找更多能揭示指标之间拓扑关系的数据（如构建Graph Embedding所依赖的的sql语句）；另一方面我们会探寻更多的Ground Truth（如巴菲特的午餐这个案例），它有助于测评我们的算法的准召程度，以及更好地优化我们的算法；
\ | /
★
二、算法的迭代：一方面我们会继续迭代当前的算法，另一方面，我们会探求新领域，如因果推断领域的算法，与当前已有算法互为印证，从而不断提升结果的准确程度。
1
END
1
[1]STL decomposition, https://otexts.com/fpp2/stl.html
[2] [CV] 通俗理解『卷积』——从傅里叶变换到滤波器。https://zhuanlan.zhihu.com/p/28478034
[3] Median absolute deviation, 维基百科。 https://en.wikipedia.org/wiki/Median_absolute_deviation
[4] Spurious Correlation and Its Significance to Physiology. https://www.jstor.org/stable/2277144?seq=1
[5] A Study of Spurious Correlation. https://www.jstor.org/stable/2276802?seq=1
[6]Adtributor: Revenue Debugging
in Advertising Systems。https://www.usenix.org/system/files/conference/nsdi14/nsdi14-paper-bhagwan.pdf
