c++可视化界面设计,搜索引擎优化自然排名的区别,全国十大网站建设公司排名,wordpress编辑写文章失败阿里妹导读#xff1a;互联网黑产盛行#xff0c;其作弊手段层出不穷#xff0c;导致广告效果降低#xff0c;APP推广成本暴增。精准识别作弊是互联网公司和广告主的殷切期望。今天我们将从时间序列、统计、距离、线性方法、分布、树、图、行为序列、有监督机器学习和深度学… 阿里妹导读互联网黑产盛行其作弊手段层出不穷导致广告效果降低APP推广成本暴增。精准识别作弊是互联网公司和广告主的殷切期望。今天我们将从时间序列、统计、距离、线性方法、分布、树、图、行为序列、有监督机器学习和深度学习模型等多个角度探讨异常检测。 背景
异常点检测(Outlier detection)又称为离群点检测是找出与预期对象的行为差异较大的对象的一个检测过程。这些被检测出的对象被称为异常点或者离群点。异常点检测在生产生活中有着广泛应用比如信用卡反欺诈、工业损毁检测、广告点击反作弊等。
异常点outlier是一个数据对象它明显不同于其他的数据对象。如下图1所示N1、N2区域内的点是正常数据。而离N1、N2较远的O1、O2、O3区域内的点是异常点。 图1.异常点示例
异常检测的一大难点是缺少ground truth。常见的方法是先用无监督方法挖掘异常样本再用有监督模型融合多个特征挖掘更多作弊。
近期使用多种算法挖掘异常点下面从不同视角介绍异常检测算法的原理及其适用场景考虑到业务特殊性本文不涉及特征细节。
1.时间序列
1.1 移动平均Moving AverageMA
移动平均是一种分析时间序列的常用工具它可过滤高频噪声和检测异常点。根据计算方法的不同常用的移动平均算法包括简单移动平均、加权移动平均、指数移动平均。假设移动平均的时间窗口为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时刻的指数移动平均 其中表示权重的衰减程度取值在0和1之间。越大过去的观测值衰减得越快。
1.2 同比和环比 图2.同比和环比
同比和环比计算公式如图2所示。适合数据呈周期性规律的场景中。如1.监控APP的DAU的环比和同比以及时发现DAU上涨或者下跌2.监控实时广告点击、消耗的环比和同比以及时发现变化。当上述比值超过一定阈值阈值参考第10部分则判定出现异常。
1.3 时序指标异常检测(STLGESD)
STL是一种单维度时间指标异常检测算法。大致思路是
(1)先将指标做STL时序分解得到seasonaltrendresidual成分如图3所示 (2)用GESD (generalized extreme studentized deviate)算法对trendresidual成分进行异常检测 (3)为增强对异常点的鲁棒性将GESD算法中的mean,std等统计量用median, MAD(median absolute deviation)替换 (4)异常分输出abnorm_score (value - median)/MAD, value为当前值median为序列的中位数。负分表示异常下跌正分表示异常上升。 图3.STL分解示例
2.统计
2.1 单特征且符合高斯分布
如果变量x服从高斯分布则其概率密度函数为 我们可以使用已有的样本数据来预测总体中的计算方法如下 2.2 多个不相关特征且均符合高斯分布
假设n维的数据集合形如
且每一个变量均符合高斯分布那么可以计算每个维度的均值和方差
具体来说对于可以计算 如果有一个新的数据可以计算概率如下 2.3 多个特征相关且符合多元高斯分布 2.4 马氏距离(Mahalanobis distance)
对于一个多维列向量的数据集合D假设是均值向量那么对于数据集D中的任意对象从到的马氏距离是 其中是协方差矩阵。可以对数值进行排序如果数值过大那么就可以认为点是离群点。
2.5 箱线图
箱线图算法不需要数据服从特定分布比如数据分布不符合高斯分布时可以使用该方法。该方法需要先计算第一四分位数Q125%和第三四分位数Q375%。令IQRQ3-Q1然后算出异常值边界点Q3λIQR和Q1- λIQR通常λ取1.5类似于正态分布中的如下图4所示 图4.箱线图算法示意图
3.距离
3.1、基于角度的异常点检测 图5.点集和角度
如上图5所示现在有三个点XYZ和两个向量如果对任意不同的点YZ角度变化都较小则点X是异常点。通过余弦夹角公式易得角度 D是点集则对于任意不同的点点X的所有角度的方差为 异常点的上述方差较小。该算法的时间复杂度是适合数据量N较小的场景。
3.2 基于KNN的异常点检测
D是点集则对于任意点计算其K近邻的距离之和Dist(K,X)。Dist(K,X)越大的点越异常。时间复杂度是其中N是数据量的大小。
4.线性方法矩阵分解和PCA降维
基于矩阵分解的异常点检测方法的主要思想是利用主成分分析PCA去寻找那些违反了数据之间相关性的异常点。为了找到这些异常点基于主成分分析的算法会把数据从原始空间投影到主成分空间然后再从主成分空间投影回原始空间。对于大多数的数据而言如果只使用第一主成分来进行投影和重构重构之后的误差是较小的但是对于异常点而言重构之后的误差相对较大。这是因为第一主成分反映了正常点的方差最后一个主成分反映了异常点的方差。
假设X是一个p维的数据集合有N个样本它的协方差矩阵是。那么协方差矩阵就可以分解为
其中P是一个维正交矩阵它的每一列都是的特征向量。D是一个维对角矩阵包含了特征值。在图形上一个特征向量可以看成2维平面上的一条线或者高维空间里面的一个平面。特征向量所对应的特征值反映了这批数据在这个方向上的拉伸程度。通常情况下将特征值矩阵D中的特征值从大到小的排序特征向量矩阵P的每一列也进行相应的调整。
数据集X在主成分空间的投影可以写成YXP注意可以只在部分的维度上做投影使用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.树孤立森林 图7.iForest检测结果
孤立森林Isolation Forest假设我们用一个随机超平面来切割数据空间, 每切一次便可以生成两个子空间。接着继续用一个随机超平面来切割每个子空间循环下去直到每个子空间里面只有一个数据点为止。那些密度很高的簇是需要被切很多次才能让子空间中只有一个数据点但是那些密度很低的点的子空间则很快就被切割成只有一个数据点。如图7所示黑色的点是异常点被切几次就停到一个子空间白色点为正常点白色点聚焦在一个簇中。孤立森林检测到的异常边界为图7中红色线条它能正确地检测到所有黑色异常点。
如图8所示用iForest切割4个数据b和c的高度为3a的高度为2d的高度为1d最先被孤立它最有可能异常。 图8.iForest切割过程
7.图
7.1 最大联通图
在无向图G中若从顶点A到顶点B有路径相连则称A和B是连通的在图G中存在若干子图其中每个子图中所有顶点之间都是连通的但不同子图间不存在顶点连通那么称图G的这些子图为最大连通子图。
如图9所示device是设备idmbr是会员id节点之间有边表示设备上有对应的会员登录过容易看出device_1、device_2、device_3、device_4是同人可以根据场景用于判断作弊常用于挖掘团伙作弊。 图9.最大联通图结果
最大联通图的前提条件是每条边必须置信。适用场景找所有连通关系。当数据中存在不太置信的边时需要先剔除脏数据否则会影响最大联通图的效果。
7.2 标签传播聚类
标签传播图聚类算法是根据图的拓扑结构进行子图的划分使得子图内部节点的连接较多子图之间的连接较少。标签传播算法的基本思路是节点的标签依赖其邻居节点的标签信息影响程度由节点相似度决定通过传播迭代更新达到稳定。图10中的节点经标签传播聚类后将得2个子图其中节点1、2、3、4属于一个子图节点5、6、7、8属于一个子图。 图10.标签传播聚类算法的图结构
标签传播聚类的子图间可以有少量连接。适用场景节点之间“高内聚低耦合”。图10用最大联通图得1个子图用标签传播聚类得2个子图。
8.行为序列马尔科夫链
如图11所示用户在搜索引擎上有5个行为状态页面请求P搜索S自然搜索结果W广告点击O翻页N。状态之间有转移概率由若干行为状态组成的一条链可以看做一条马尔科夫链。 图11.用户行为状态图
统计正常行为序列中任意两个相邻的状态然后计算每个状态转移到其他任意状态的概率得状态转移矩阵。针对每一个待检测用户行为序列易得该序列的概率值概率值越大越像正常用户行为。
9.有监督模型
上述方法都是无监督方法实现和理解相对简单。但是由于部分方法每次使用较少的特征为了全方位拦截作弊需要维护较多策略另外上述部分方法组合多特征的效果取决于人工经验。而有监督模型能自动组合较多特征具备更强的泛化能力。
9.1 机器学习模型GBDT
样本使用前面的无监督方法挖掘的作弊样本作为训练样本。如果作弊样本仍然较少用SMOTE或者GAN生成作弊样本。然后训练GBDT模型用转化数据评估模型的效果。
9.2 深度学习模型WideDeep
WideDeep通过分别提取wide特征和deep特征再将其融合在一起训练模型结构如图12所示。wide是指高维特征和特征组合的LR。LR高效、容易规模化scalable、可解释性强。出现的特征组合如果被不断加强对模型的判断起到记忆作用。但是相反的泛化性弱。
deep则是利用神经网络自由组合映射特征泛化性强。deep部分本质上挖掘一些样本特征的更通用的特点然后用于判断但是有过度泛化的风险。
算法通过两种特征的组合去平衡记忆memorization和泛化 generalization。
为了进一步增加模型的泛化能力可以使用前面的无监督方法挖掘的作弊样本作为训练样本训练WideDeep模型识别作弊。 图12.WideDeep模型
10.其他问题
10.1 常用选择阈值的思路
上述各种方法都需要计算异常阈值可以用下述思路先选阈值再用转化数据验证该阈值的合理性。
a.无监督方法使用分位点定阈值、找历史数据的分布曲线的拐点
b.有监督模型看验证集的准召曲线
10.2 非高斯分布转高斯分布
有些特征不符合高斯分布那么可以通过一些函数变换使其符合高斯分布以便于使用上述统计方法。常用的变换函数其中c为非负常数c为0-1之间的一个分数。
原文链接 本文为云栖社区原创内容未经允许不得转载。
