背景异常检测（Outlierdetection），也称为离群点检测，是一种检测过程，用于找出行为与预期对象有较大差异的对象。.这些检测到的对象被称为异常值或离群值。异常值检测广泛应用于生产和生活中，如信用卡反欺诈、工业损害检测、广告点击反作弊等。异常值是指与其他数据对象明显不同的数据对象。如下图1所示，N1和N2区域的点是正常数据。O1、O2、O3区域中远离N1、N2的点为异常点。图1.异常值示例异常检测的困难之一是缺乏基本事实。一种常见的方法是先用无监督的方法挖掘异常样本，然后用有监督的模型融合多个特征来挖掘更多的作弊行为。最近，各种算法被用于挖掘异常值。下面从不同的角度介绍异常检测算法的原理及其适用场景。考虑到业务的特殊性，本文不涉及特性的细节。1.时间序列1.1移动平均线（MA）移动平均线是分析时间序列的常用工具，可以过滤高频噪声和检测异常点。根据计算方法的不同，常用的移动平均算法有简单移动平均法、加权移动平均法和指数移动平均法。假设移动平均线的时间窗口为T，则有一个时间序列：1.1.1SimpleMovingAverage(SMA)由上式不难看出，历史值的平均值可以作为预测值当前值的值，在序列值随时间波动较小的场景中，如果该时刻的移动平均值与真实值的差值超过某个阈值，则判定该时刻的值为异常。适用于：平滑噪声数据，即用移动平均代替当前值，滤除噪声；b.预测未来价值。1.1.2加权移动平均(WMA)由于简单移动平均对窗口内的所有数据点赋予相同的权重，因此对最近的最新数据不够敏感，预测值存在滞后性。延伸这个思路，很自然的想法就是在计算移动平均的时候，对最近的数据赋予更高的权重，对距离窗口较远的数据赋予较低的权重，从而更快地捕捉到最近的变化。由此，获得加权移动平均线和指数移动平均线。加权移动平均线比简单移动平均线对近期变化更敏感，加权移动平均线的滞后性小于简单移动平均线。但是由于只使用了线性权重衰减，所以加权移动平均还是有一定的滞后性。1.1.3指数移动平均线（EMA）指数移动平均线（EMA）类似于加权移动平均线，不同的是每个值的权重按指数下降，而不是线性下降。另外，在指数衰减中，无论数据向前看多远，这一时期数据的系数都不会衰减到0，而只会趋近于0。因此，指数移动平均实际上是一个无限级数，即就是不管数据有多远，都会对计算当前的指数移动平均值起到一定的作用，但是离当前太远的数据权重很低。在实际应用中，t时刻的指数移动平均可以得到：其中表示权重的衰减程度，取值在0到1之间，越大，过去的观测值衰减得越快。1.2同比及环比图2.同比及环比同比及环比的计算公式如图2所示，适用于数据具有周期性的场景。例如：1、监控APP的DAU环比和同比，及时发现DAU的上升或下降；2.实时监控广告点击量、消费率、同比率，及时发现变化。当上述比例超过某个阈值（阈值参见第10节）时，则判定存在异常。1.3时序指标异常检测（STL+GESD）STL是一种单维时间指标异常检测算法。总体思路是：（1）首先对STL时间序列中的指标进行分解，得到季节、趋势、残差成分，如图3所示；(2)使用GESD(generalizedextremestudentizeddeviate)算法检测趋势+残差成分的异常；(3)为了增强异常点的鲁棒性，将GESD算法中的mean、std等统计量替换为median、MAD(medianabsolutedeviation)；(4)异常分数输出：abnormal_score=(value-median)/MAD，value为当前值，median为序列的中位数。负分表示异常下降，正分表示异常上升。图3.STL分解示例2.统计2.1单特征和高斯分布如果变量x服从高斯分布：，那么它的概率密度函数为：我们可以利用已有的样本数据来预测总体。方法如下：2.2具有多个不相关特征且n维均符合高斯分布假设的数据集如下：。并且每个变量都符合高斯分布，那么就可以计算每个维度的均值和方差，具体来说，对于，可以计算：如果有一个新的数据，概率可以计算如下：2.3多个特征相关并且符合多元高斯分布假设一个n维数据集，每个变量都符合高斯分布，可以计算出n维均值向量的协方差矩阵：如果有新的数据，可以计算出概率：2.4马氏距离（Mahalanobisdistance）对于A数据集D的多维列向量，假设它是一个均值向量，那么对于数据集D中的任意一个对象，从到的马氏距离为：其中是协方差矩阵。可以对值进行排序，如果值太大，可以认为该点是离群点。2.5Boxplot箱线图算法不要求数据服从特定的分布。例如，当数据分布不符合高斯分布时，可以使用这种方法。该方法需要先计算出第一四分位数Q1（25%）和第三四分位数Q3（75%）。令IQR=Q3-Q1，然后计算离群边界点Q3+λ*IQR和Q1-λ*IQR，通常λ为1.5（与正态分布类似，如下图4所示：图4.Boxplot算法示意图3.Distance3.1,Angle-basedoutlierdetection图5.Pointsetandangle如上图5所示，现在有三个点X,Y,Z,和两个向量，如果有不同的点Y,Z,变化很小，则X点为异常点，通过余弦角公式很容易得到角度：D是一个点集，那么对于任意不同的点，X点所有角度的方差是：上述异常点的方差小该算法的时间复杂度适用于数据量N较小的场景3.2基于KNN的异常值检测D是一个点集，那么对于任意一个点，计算其K个最近邻Dist(K,X)的距离之和，Dist(K,X)越大，表示该点越不正常。时间co复杂性是，其中N是数据量的大小。4.基于矩阵分解检测方法的线性方法（矩阵分解和PCA降维）的主要思想是使用主成分分析（PCA）来寻找违反数据之间相关性的异常值。为了找到这些异常值，基于PCA的算法会将数据从原始空间投影到主成分空间，再从主成分空间投影回原始空间。对于大部分数据，如果只用***主成分进行投影重建，重建后的误差很小；但对于异常点，重构后误差比较大。这是因为***主成分反映了正常点的方差，***主成分反映了异常点的方差。假设X是具有N个样本的p维数据集，其协方差矩阵为。那么协方差矩阵可以分解为：其中P是维正交矩阵，其每一列都是的特征向量。D是包含特征值的维对角矩阵。从图形上看，特征向量可以看作是二维平面上的一条线，也可以看作是高维空间中的一个平面。特征向量对应的特征值反映了这批数据在这个方向上的拉伸程度。通常，特征值矩阵D中的特征值按照从大到小的顺序排列，特征向量矩阵P的每一列都相应调整。数据集X在主成分空间的投影可以写成Y=XP。请注意，只能在某些维度上进行投影。使用top-j进行主成分投影后的矩阵为：。其中有矩阵P的第j列，也就是说是一维矩阵。是矩阵Y的前j列，它是一个一维矩阵。同理将主成分空间映射到原始空间，重构后的数据集为。其中是使用top-j的主成分重构后的数据集，是一个一维矩阵。如图6所示：图6.矩阵变换示意图。定义数据的异常值分为：表示top-j主成分占所有主成分的比例，特征值按从大到小的顺序排列。因此它是增量的，这意味着j越大，考虑的方差就越大，因为它是从1到j的总和。在这个定义下，偏差最大的第一个主成分获得最小的权重，偏差最小的最后一个主成分获得最大的权重1。根据PCA的性质，异常值对最后一个主成分的偏差较大，因此具有更大的离群值。5.分布指的是参考流与待检测流相比，某一特征的分布。5.1相对熵（KL散度）相对熵（KL散度）可以衡量两个随机分布之间的距离。当两个随机分布相同时，它们的相对熵为零。当两个随机分布的差异增加时，它们的相对熵也会增加。所以相对熵可以用来比较两个分布的相似度。设为两个概率分布的值，则对应的相对熵为。5.2卡方检验卡方检验通过检验统计量比较预期结果与实际结果的差异，进而得出实际结果发生的概率。其中O代表观察值，E代表期望值。此检验统计量提供了预期值与观察值之间差异的度量。***根据设定的显着性水平，通过查卡方概率表确定。6.树（IsolationForest）图7.iForest测试结果隔离森林（IsolationForest）假设我们使用随机超平面对数据空间进行切割，每次切割可以生成两个子空间。然后继续用一个随机超平面切割每个子空间，循环直到每个子空间只有一个数据点。那些密度高的聚类需要多次切割，使得子空间中只有一个数据点，但那些密度低的点的子空间很快就被切割成只有一个数据点。如图7所示，黑色的点是异常点，经过多次切割后停在一个子空间；白点是法线点，白点集中在一个簇中。isolationforest检测到的异常边界就是图7中的红线，可以正确检测到所有的黑色异常。如图8，使用iForest切割4条数据，b和c的高度为3，a的高度为2，d的高度为1，d***是孤立的，极有可能是异常.图8.iForest切割过程7.图7.1***连通图在无向图G中，如果从顶点A到顶点B存在一条路径，则称A和B连通；否则称A和B连通。图G中有多个子图，每个子图中的所有顶点都是连通的，但不同子图之间没有顶点连接，则称图G的这些子图为***连通子图。如图9所示，device是设备id，mbr是成员id，节点之间的连线表示设备上对应的成员已经登录，容易看出device_1、device_2、device_3、device_4是同事，可以根据场景判断作弊，经常用来挖团伙作弊。图9.***连通图结果***连通图的先决条件是每条边都必须是可信的。适用场景：查找所有连通关系。当数据中存在不可信边时，需要先去除脏数据，否则会影响最连通图的效果。7.2标签传播聚类标签传播图聚类算法根据图的拓扑结构划分子图，使子图内部节点连接多，子图间连接少。标签传播算法的基本思想是节点的标签依赖于其邻居节点的标签信息，影响程度由节点的相似度决定，通过传播迭代更新实现稳定性.图10中的节点通过标签传播聚类后，会得到两个子图，其中节点1、2、3、4属于一个子图，节点5、6、7、8属于一个子图。图10.标签传播聚类算法的图结构标签传播聚类的子图之间可以有少量的连接。适用场景：节点间“高内聚低耦合”。在图10中，使用***联通图得到一个子图，通过标签传播聚类得到两个子图。8、行为序列（马尔可夫链）如图11所示，用户在搜索引擎上有5种行为状态：页面请求（P）、搜索（S）、自然搜索结果（W）、广告点击（O）、转页（N）。状态之间存在转移概率，由若干行为状态组成的链可以看做马尔可夫链。图11.用户行为状态图统计正常行为序列中任意相邻的两个状态，然后计算每个状态转移到任意其他状态的概率，得到状态转移矩阵。对于每个待检测的用户行为序列，该序列的概率值很容易得到。概率值越大，用户行为越正常。9.监督模型以上方法都是无监督方法，实现和理解都比较简单。但是，由于某些方法每次使用的特征较少，因此需要维护更多的策略，以便全方位拦截作弊；此外，上述某些方法的多个特征组合的效果取决于人的经验。监督模型可以自动组合更多的特征，具有更强的泛化能力。9.1机器学习模型GBDT样本：使用之前无监督方法挖掘出的作弊样本作为训练样本。如果作弊样本还很少，就用SMOTE或者GAN生成作弊样本。然后训练GBDT模型，并用转换后的数据评估模型的效果。9.2深度学习模型Wide&DeepWide&Deep分别提取宽特征和深特征，然后融合在一起进行训练。模型结构如图12所示，Wide是指高维特征和特征组合的LR。LR高效、易于扩展（scalable）、可解释。如果不断强化出现的特征组合，会对模型的判断起到记忆作用。但相反的泛化能力较弱。deep是利用神经网络对映射特征进行自由组合，泛化能力强。深度部分本质上是挖掘一些样本特征的更普遍的特征，然后用它们来进行判断，但是存在过度泛化的风险。该算法通过两个特征的组合来平衡记忆和泛化。为了进一步增加模型的泛化能力，可以将之前无监督方法挖掘出的作弊样本作为训练样本，训练Wide&Deep模型识别作弊。图12.Wide&Deep模型10.其他问题10.1选择阈值的常用思路a．无监督法：利用分位数点确定阈值，寻找历史数据分布曲线的拐点；b.监督模型：看验证集的准召回曲线10.2将非高斯分布转换为高斯分布。可以通过一些函数将其转化为高斯分布，以方便上述统计方法的使用。常用的变换函数：其中c为非负常数；c是0-1之间的分数。参考文献：[1]CharuC,Aggarwal,etal.异常值分析第二版，Springer.2016[2]VarunChandola、ArindamBanerjee等。异常检测：一项调查，ACM计算调查。2009[3]KalyanVeeramachaneni、IgnatiusArnaldo等人。AI2：训练大数据机器进行防御，InProc。HPSC和IDS。2016[4]Liu,FeiTony,KaiMingTing,andZhi-HuaZhou,etal.隔离森林，ICDM。2008年
