共计 4356 个字符，预计需要花费 11 分钟才能阅读完成。
阿里妹导读： 互联网黑产盛行，其作弊手段层出不穷，导致广告效果降低，APP 推广成本暴增。精准识别作弊是互联网公司和广告主的殷切期望。今天我们将从时间序列、统计、距离、线性方法、分布、树、图、行为序列、有监督机器学习和深度学习模型等多个角度探讨异常检测。
作者 | 黎伟斌、胡熠、王皓
背景
异常点检测 (Outlier detection)，又称为离群点检测，是找出与预期对象的行为差异较大的对象的一个检测过程。这些被检测出的对象被称为异常点或者离群点。异常点检测在生产生活中有着广泛应用，比如信用卡反欺诈、工业损毁检测、广告点击反作弊等。
异常点（outlier）是一个数据对象，它明显不同于其他的数据对象。如下图 1 所示，N1、N2 区域内的点是正常数据。而离 N1、N2 较远的 O1、O2、O3 区域内的点是异常点。
异常检测的一大难点是缺少 ground truth。常见的方法是先用无监督方法挖掘异常样本，再用有监督模型融合多个特征挖掘更多作弊。
近期使用多种算法挖掘异常点，下面从不同视角介绍异常检测算法的原理及其适用场景，考虑到业务特殊性，本文不涉及特征细节。
1. 时间序列
1.1 移动平均（Moving Average，MA）
移动平均是一种分析时间序列的常用工具，它可过滤高频噪声和检测异常点。根据计算方法的不同，常用的移动平均算法包括简单移动平均、加权移动平均、指数移动平均。假设移动平均的时间窗口为 T，有一个时间序列：
1.1.1 简单移动平均（Simple Moving Average,SMA）
从上面的公式容易看出可以用历史的值的均值作为当前值的预测值，在序列取值随时间波动较小的场景中，上述移动均值与该时刻的真实值的差值超过一定阈值则判定该时间的值异常。
适用于：
a. 对噪声数据进行平滑处理，即用移动均值替代当前时刻取值以过滤噪声；
b. 预测未来的取值。
1.1.2 加权移动平均（Weighted Moving Average, WMA）
由于简单移动平均对窗口内所有的数据点都给予相同的权重，对近期的最新数据不够敏感，预测值存在滞后性。按着这个思路延伸，自然的想法就是在计算移动平均时，给近期的数据更高的权重，而给窗口内较远的数据更低的权重，以更快的捕捉近期的变化。由此便得到了加权移动平均和指数移动平均。
加权移动平均比简单移动平均对近期的变化更加敏感，加权移动平均的滞后性小于简单移动平均。但由于仅采用线性权重衰减，加权移动平均仍然存在一定的滞后性。
1.1.3 指数移动平均（Exponential Moving Average, EMA）
指数移动平均（Exponential Moving Average, EMA）和加权移动平均类似，但不同之处是各数值的加权按指数递减，而非线性递减。此外，在指数衰减中，无论往前看多远的数据，该期数据的系数都不会衰减到 0，而仅仅是向 0 逼近。因此，指数移动平均实际上是一个无穷级数，即无论多久远的数据都会在计算当期的指数移动平均数值时，起到一定的作用，只不过离当前太远的数据的权重非常低。在实际应用中，可以按如下方法得到 t 时刻的指数移动平均：
1.2 同比和环比
同比和环比计算公式如图 2 所示。适合数据呈周期性规律的场景中。如：1. 监控 APP 的 DAU 的环比和同比，以及时发现 DAU 上涨或者下跌；2. 监控实时广告点击、消耗的环比和同比，以及时发现变化。当上述比值超过一定阈值（阈值参考第 10 部分）则判定出现异常。
1.3 时序指标异常检测 (STL+GESD)
STL 是一种单维度时间指标异常检测算法。大致思路是：
(1) 先将指标做 STL 时序分解，得到 seasonal，trend，residual 成分，如图 3 所示；
(2) 用 GESD (generalized extreme studentized deviate) 算法对 trend+residual 成分进行异常检测；
(3) 为增强对异常点的鲁棒性，将 GESD 算法中的 mean,std 等统计量用 median, MAD(median absolute deviation) 替换；
(4) 异常分输出：abnorm_score = (value – median)/MAD, value 为当前值，median 为序列的中位数。负分表示异常下跌，正分表示异常上升。
2. 统计
3. 距离
3.1、基于角度的异常点检测
4. 线性方法（矩阵分解和 PCA 降维）
基于矩阵分解的异常点检测方法的主要思想是利用主成分分析（PCA）去寻找那些违反了数据之间相关性的异常点。为了找到这些异常点，基于主成分分析的算法会把数据从原始空间投影到主成分空间，然后再从主成分空间投影回原始空间。对于大多数的数据而言，如果只使用第一主成分来进行投影和重构，重构之后的误差是较小的；但是对于异常点而言，重构之后的误差相对较大。这是因为第一主成分反映了正常点的方差，最后一个主成分反映了异常点的方差。
其中是使用 top- j 的主成分重构之后的数据集，是一个维的矩阵。如图 6 所示：
5. 分布
即对比基准流量和待检测流量的某个特征的分布。
5.1 相对熵（KL 散度）
5.2 卡方检验
6. 树（孤立森林）
孤立森林（Isolation Forest）假设我们用一个随机超平面来切割数据空间, 每切一次便可以生成两个子空间。接着继续用一个随机超平面来切割每个子空间，循环下去，直到每个子空间里面只有一个数据点为止。那些密度很高的簇是需要被切很多次才能让子空间中只有一个数据点，但是那些密度很低的点的子空间则很快就被切割成只有一个数据点。如图 7 所示，黑色的点是异常点，被切几次就停到一个子空间；白色点为正常点，白色点聚焦在一个簇中。孤立森林检测到的异常边界为图 7 中红色线条，它能正确地检测到所有黑色异常点。
如图 8 所示，用 iForest 切割 4 个数据，b 和 c 的高度为 3，a 的高度为 2，d 的高度为 1，d 最先被孤立，它最有可能异常。
7. 图
7.1 最大联通图
在无向图 G 中，若从顶点 A 到顶点 B 有路径相连，则称 A 和 B 是连通的；在图 G 中存在若干子图，其中每个子图中所有顶点之间都是连通的，但不同子图间不存在顶点连通，那么称图 G 的这些子图为最大连通子图。
如图 9 所示，device 是设备 id，mbr 是会员 id，节点之间有边表示设备上有对应的会员登录过，容易看出 device_1、device_2、device_3、device_4 是同人，可以根据场景用于判断作弊，常用于挖掘团伙作弊。
最大联通图的前提条件是每条边必须置信。适用场景：找所有连通关系。当数据中存在不太置信的边时，需要先剔除脏数据，否则会影响最大联通图的效果。
7.2 标签传播聚类
标签传播图聚类算法是根据图的拓扑结构，进行子图的划分，使得子图内部节点的连接较多，子图之间的连接较少。标签传播算法的基本思路是节点的标签依赖其邻居节点的标签信息，影响程度由节点相似度决定，通过传播迭代更新达到稳定。图 10 中的节点经标签传播聚类后将得 2 个子图，其中节点 1、2、3、4 属于一个子图，节点 5、6、7、8 属于一个子图。
标签传播聚类的子图间可以有少量连接。适用场景：节点之间“高内聚低耦合”。图 10 用最大联通图得 1 个子图，用标签传播聚类得 2 个子图。
8. 行为序列（马尔科夫链）
如图 11 所示，用户在搜索引擎上有 5 个行为状态：页面请求（P），搜索（S），自然搜索结果（W），广告点击（O），翻页（N）。状态之间有转移概率，由若干行为状态组成的一条链可以看做一条马尔科夫链。
统计正常行为序列中任意两个相邻的状态，然后计算每个状态转移到其他任意状态的概率，得状态转移矩阵。针对每一个待检测用户行为序列，易得该序列的概率值，概率值越大，越像正常用户行为。
9. 有监督模型
上述方法都是无监督方法，实现和理解相对简单。但是由于部分方法每次使用较少的特征，为了全方位拦截作弊，需要维护较多策略；另外上述部分方法组合多特征的效果取决于人工经验。而有监督模型能自动组合较多特征，具备更强的泛化能力。
9.1 机器学习模型 GBDT
样本：使用前面的无监督方法挖掘的作弊样本作为训练样本。如果作弊样本仍然较少，用 SMOTE 或者 GAN 生成作弊样本。然后训练 GBDT 模型，用转化数据评估模型的效果。
9.2 深度学习模型 Wide&Deep
Wide&Deep 通过分别提取 wide 特征和 deep 特征，再将其融合在一起训练，模型结构如图 12 所示。wide 是指高维特征和特征组合的 LR。LR 高效、容易规模化（scalable）、可解释性强。出现的特征组合如果被不断加强，对模型的判断起到记忆作用。但是相反的泛化性弱。
deep 则是利用神经网络自由组合映射特征，泛化性强。deep 部分本质上挖掘一些样本特征的更通用的特点然后用于判断，但是有过度泛化的风险。
算法通过两种特征的组合去平衡记忆（memorization）和泛化（generalization）。
为了进一步增加模型的泛化能力，可以使用前面的无监督方法挖掘的作弊样本作为训练样本，训练 Wide&Deep 模型识别作弊。
10. 其他问题
10.1 常用选择阈值的思路
上述各种方法都需要计算异常阈值，可以用下述思路先选阈值，再用转化数据验证该阈值的合理性。
a. 无监督方法：使用分位点定阈值、找历史数据的分布曲线的拐点；
b. 有监督模型：看验证集的准召曲线
10.2 非高斯分布转高斯分布
有些特征不符合高斯分布，那么可以通过一些函数变换使其符合高斯分布，以便于使用上述统计方法。常用的变换函数：，其中 c 为非负常数；，c 为 0 - 1 之间的一个分数。
参考文献：
[1] Charu C, Aggarwal, et al. Outlier Analysis Second Edition, Springer.2016
[2] Varun Chandola, Arindam Banerjee, et al. Anomaly Detection: A survey,ACM Computing Surveys. 2009
[3] Kalyan Veeramachaneni, Ignacio Arnaldo, et al. AI2: Training abig data machine to defend, In Proc. HPSC and IDS. 2016
[4] Liu, Fei Tony, Kai Ming Ting, and Zhi-Hua Zhou, et al. Isolationforest, ICDM. 2008
[5] Cheng H T, Koc L, Harmsen J, et al. Wide & Deep Learning forRecommender Systems, ACM Computing Surveys. 2016
[6] SMOTE: Synthetic Minority Over-sampling Technique, JAIR. 2002
本文作者：新零售技术
阅读原文
本文来自云栖社区合作伙伴“阿里技术”，如需转载请联系原作者。
