DBSCAN在防刷场景下的应用 – 作者:flyking-安全小百科

前言

聚类算法虽然不如监督学习的结果精准，但是其高效的特征簇提取能够方便业务快速的发现恶意特征，特别是在防刷场景下是一个较为实用的初筛恶意用户的利器，本文以dbscan为例来阐述一下聚类在防刷业务场景下的应用。

业务场景描述

游戏礼券，活动礼包，下载场景，关注场景下是防刷场景的重灾区。恶意黑产来利用这些场景接口频繁刷取礼包，或者水军刷取关注点击量，来实现利益套现，本文阐述的是基于游戏礼包的下发，系统初期上线每次礼包下发总是在很短的时间内就发现一抢而空，而正常用户每每落空，我们的任务就是需要识别出这些黑产用户，将其和正常用户区别开来。

算法简介

DBSCAN是一种基于高密度连通区域的基于密度的聚类方法，该算法将具有足够高密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇。它将簇定义为密度相连的点的最大集合；为了理解基于密度聚类的思想，首先要掌握以下几个定义：

1、给定对象半径r内的邻域称为该对象的r邻域；

2、如果对象的r邻域至少包含最小数目MinPts的对象，则称该对象为核心对象；

3、给定一个对象集合D，如果p在q的r邻域内，并且q是一个核心对象，则我们说对象p从对象q出发是直接密度可达的；

4、如果存在一个对象链p1，p2，p3，…，pn，p1=q，pn=p，对于pi属于D，i属于1~n，p（i+1）是从pi关于r和MinPts直接密度可达的，则对象p是从对象q关于r和MinPts密度可达的；

5、如果存在对象o属于D，使对象p和q都是从o关于r和MinPts密度可达的，那么对于对象p到q是关于r和MinPts密度相连的；密度可达是直接密度可达的传递闭包，这种关系非对称，只有核心对象之间相互密度可达；密度相连是一种对称的关系；

有了以上的概念接下来就是算法描述了：DBSCAN通过检查数据库中每点的r邻域来搜索簇。如果点p的r邻域包含的点多余MinPts个，则创建一个以p为核心对象的新簇。然后，DBSCAN迭代的聚集从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以添加到任何簇时，该过程结束；具体的伪代码描述如下（摘自维基百科）：