构建基于密度峰值聚类算法的反作弊系统

叶 楠，寇丽杰

（福州理工学院，福建 福州 350506）

0 引言

随着互联网技术的发展普及，日益增加的广告投放需求与流量需求，不停推动着广告平台自身对流量扩增的需求，在存量时代的零和博弈现状下，数以百万计的应用激烈争夺有限的流量市场，自然而然会引来大量的黑产，去谋取其中的一些利益[1]。广告黑产的定义，即通过制造大量虚假的曝光和点击下载的传播，来达到更多的曝光、更多的点击、更多的下载、更多的转化。黑产演进已经从技术实现简单的协议刷量、群控刷量发展到了技术复杂度越高的真人众包刷量[2]。

本文分析了主要的流量反作弊的痛点和技术难点，构建基于对抗性训练的广告流量反作弊学习框架，结合对密度峰值聚类算法的多重改良，提出了一种解决行为序列分类问题的Transformer self attention模型，旨在将多模态结合提升模型效果，通过流量反作弊中的对抗性训练设计实现黑产演变攻击的对抗方案[3]。

1 流量反作弊的对抗性学习框架

洞察出正常流量与恶意流量的区别，关键点就在于恶意流量是很难完全伪造出正常流量的，它会在某些行为或者说数据的特征上呈现出与正常流量的一些区别[4]。利用这个思路，本文创新性地提出了一个流量反作弊的对抗性学习框架，如图1所示[5]。整个学习框架分为四层，第一层为数据安全层，即数据的管理层，相当于把所有的数据收集起来，然后做一系列的清洗之后作为第二层画像层的输入，在画像层构建出关于设备和环境等不同Item的一些画像。最后通过把这些构建出来的画像提供到对抗学习模型上面，给需要的一些模型进行学习，最终发布到应用层面上，提供强有力的反作弊服务能力[6]。

图1 流量反作弊对抗性学习框架

2 改进密度峰值聚类算法模型

2.1 密度峰值聚类算法

密度峰值聚类算法是一种很简要易用的聚类算法，能够识别各种不同形状的类簇，该算法有两步很重要的步骤，一个是密度的计算，另一个是最小距离的计算，密度的计算就主要是指计算每一个点，与其所有其他点的最小距离之和[7]。当得到每一个点的最小距离和密度后，可以由局部密码和距离( ， )构造出对确定聚类中心具有决定性作用的决策图，这个决策图横坐标是每一个点的密度，然后纵坐标是点的一个最小的距离[8]。局部密度 和距离 的计算公式如下。

从公式中可以看到，密度越大、距离越远的点，越有可能被定义成一个聚类的中心，因为该算法的假设是类簇的中心由一些局部密度比较低的点围绕，并且这些点距离其他有高局部密度的点的距离都比较大。从另一个层面来说，聚类中心与聚类中心之间会有一定的距离，同时也可以发现那些密度很小，但是距离很远的点，很有可能就是所要找到的一些离群点。

2.2 算法改良优化思路

经过深入分析并结合具体应用，采用该密度峰值聚类算法会有以下问题：时间复杂度高、强高斯假设和无法准确检测离群点[9]。

（1）时间复杂度高。算法中三个计算步骤时间复杂度为 ，当数据规模较大时，算法基本不能输出结果。

（2）强高斯假设。密度的计算是基于球体半径作为阈值来计算的，所以依然以高斯假设为前提。无法理想地聚集任意形状的簇，密度的计算以高斯假设为前提，所以簇依然与高斯分布相关。

（3）无法准确检测出离群点。根据密度与距离判断离群点缺乏鲁棒性，离群点之间也会相互影响，无法根据离群点的最小距离判断其离群的程度。

如何解决时间复杂度问题？通过合并多个重复计算、进行数据点距离计算、密度函数等优化，可以将多个计算步骤时间复杂度由 下降至 ，如表1所示，达到百万级数据集轻松计算，时间缩小100倍。

表1 解决时间复杂度的算法优化

如何理想地聚集任意形状的簇？通过去掉高斯假设，如果密度的计算是基于k个最近邻居点，则其分布可以是任意形状。如何使离群点检测更具鲁棒性？在关于离群点检测这个方法上增加一个新的指标LOF（Local Outlier Factor），如式（3）所示，主要用于衡量每个点的密度与它最近邻居点的密度之比的平均。

在LOF计算指标公式中，j为k个最近邻居点；和 分别为i点和j点的密度。

通过如上改善，本文所提出的改良DPeak后的算法IM-DPeak（Improve DPeak）解决了几个重要的问题：第一个是把时间复杂度，从 下降至 ；第二个是引入了k最近邻居的计算，成功去掉了一个高斯假设；第三个是通过计算k最近邻居点的密度之比的平均作为衡量新指标，可以使得离群点的检测更具鲁棒性。从实际的场景和数据也可以发现，如果根据最小的距离无法检测出一些很准确的离群点，而通过新的指标，却能发现一些相应的离群点，并且我们把这些离群点剔除之后，使本文的分类算法在设计上得到了一定的提高。

3 黑产演变攻击的对抗方案

方案参考了Few Shot Learning的思想，主要采用Prototypical Network with Attention网络，这张网络的核心思想在于让网络去学习一个转义的空间，然后让输入映射到一个圆形的空间里面，使得不同种类的流量会在圆形空间里面分布在不同的角落，而网络的目标是让它们形成各自的簇，然后在预测时，只要把流预测的样本输入网络，让它映射回圆形空间里面去看，判断它会更接近于哪一个种类的流量。

通过如上Transformer网络已经可以很好地抽取到一些行为的特征，图2为进行多模态结合的流程模型，结合之前一些App的画像Embedding、设备的画像以及IP地址的画像，把这些不同模态的特征融合在一起，作为多模态模型的一个输入，能够为分类器的模型带来很大的提升效果。

图2 多模态结合提升模型效果

4 实验分析

4.1 背景和实验环境描述

为了评估本文优化构建的IM-DPeak算法的聚类效果和离群点检测准确性，对接拥有线上百万级用户的第三方新媒体IP视频云平台中的程序化广告系统进行实验，该平台注册用户在200万以上，在线并发率超过10%，终端涵盖了机顶盒端、手机端、PC端等门户，提供了以视频、图片为主的广告推送服务。实验结果以规则校验下异常流量的过滤能力、聚类中心判定的识别准确度作为参考，同时要求IM-DPeak算法能够聚集任意形状的类簇，具备标准数据集的同等聚类效果。发起单次完整的广告流程中包括了请求、下发、曝光和点击四个基本要素。

4.2 实时和离线反作弊系统策略

实时反作弊系统策略主要依赖直接反馈特征，在快速、高效的基础上，根据独立广告流量进行实时分析。其策略主要包括参数合规性检查、广告流量地址防盗链校验、点击事件真实性决策等。离线广告反作弊系统主要依赖于统计分析和关联分析，根据用户基数和日志量级需要损耗一定的计算性能。规则策略分为以下几类。

（1）基于点击的策略。①进行页面上下游分析、页面行为深度分析、页面加载耗时分析，了解用户在点击事件上的跳转行为是否符合规律和合法路径；②进行用户画像、标签组关联大量分组广告的用户请求分析，判决点击事件真实性；③绘制点击次数跟随时间变化的控制图，描述上下限变化稳定度，发现点击事件转化情况。

（2）基于曝光的策略。①一定时间内累计达到广告曝光次数时，比对设备、IP地址、用户ID、时间间隔等参数；②单维度曝光量突降时应检查慢速比、卡顿比的影响；③当A/B Test数据驱动决策时对曝光率变化情况的融合进行分析。

如上策略结合请求和下发情况，可以更进一步产生基于组合的策略，通过对广告全流程的节点监控，如多维度的历史数据挖掘和系统质量趋势，进行持续跟踪、发现异常、及时报警。

4.3 合成和真实数据集上的聚类对比

实验环境包含x86服务器1台，配置为Windows 10 64位操作系统，Intel XEON金牌6130 2.1 GHz，64 GB内存，软件为PyCharm Python 3.8 64bit版本。

表2为基于广告大数据系统软硬探针和终端SDK采集统计的实例，提供实验所用的4个真实数据集，其中各数据集按照不同奖励形式定义了规则分类，按照整体热度分布提取了一定量级的实例数进行集合分析。

表2 实验中采用的真实数据集

为了分析新媒体IP视频云平台抽样用户的行为规律和检测是否存在刷量离群样本，IM-DPeak算法在4个真实数据集上的聚类结果如图3所示。从图3(a)决策图中可以看出，通过IM-DPeak算法进行不同数据集的聚类后，通过混合不同采样数据集同样可以正确找出聚类中心，根据反作弊系统规则，在这些数据集上的类中仅存在按设定分类的明显密度峰值，同时用三角形标出距离较大、密度较小的离群点。在图3(b)中，IM-DPeak算法在4个真实数据集上可以准确划分聚类结果，且存在部分离群点（使用黑色点标注）及部分需要借助反作弊系统辅助二次审计的疑似离群点（使用放大同色点标注），实验真实数据集的聚类情况说明本文所设计的IM-DPeak算法在不同形状数据集上的处理效果较优，可与不同群体类别的广告用户行为数据进行混合分析。

图3 IM-DPeak算法在4个真实数据集上的聚类效果

5 结束语

密度峰值聚类算法具备很好的分类及离群检测机制，本文将密度峰值聚类算法进行改良后，创新性地应用于面向黑产技术演进发展的流量反作弊系统，提出了一种基于DPeak算法的对抗性学习框架，通过复杂度降级提高算力、构建模型解决少量样本的行为序列分类问题等步骤，形成了完善流程的反作弊系统。同时建立多维度的画像输入机制，让不同模态特征进行融合，持续提升新分类器模型效果。■