前言

    聚类算法虽然不如监督学习的结果精准，但是其高效的特征簇提取能够方便业务快速的发现恶意特征，特别是在防刷场景下是一个较为实用的初筛恶意用户的利器，本文以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迭代的聚集从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以添加到任何簇时，该过程结束；具体的伪代码描述如下（摘自维基百科）：

DBSCAN can find non-linearly separable clusters.

算法实现

算法实现的核心逻辑主要包括，领域节点查找，簇群扩展，距离算法：

算法入口

1、遍历所有的节点，如果已经遍历则继续下一个节点

2、以该节点为核心查找邻域节点

3、邻域节点数满足最小节点簇阈值则扩展簇群

邻域节点查找

   1、从上面的代码可以看出所有节点都会加入一棵树KD-TREE

   2、通过预先设置好的最小邻域值来搜索其邻域节点

   3、搜索过程会使用到距离计算公式（可自定义：ChebyshevDistance、CosineDistance、EuclideanDistance、GeographicalDistance、ManhattanDistance）

搜寻代码

簇群扩展

以某一个节点为核心，调用邻域查找，只要邻域节点形成的簇群大于最小节点数即可形成一个簇群

线上处理逻辑

线上实时处理框架，数据实时采集，异步定时形成簇，再依据形成的簇群对线上每个节点进行划分。

线上实时分类代码调用

训练结果

我们可以采取时间作为x轴，uid作为y轴建立一个二维空间数据集合，1.5W数据集进行聚类分析恶意用户99.7%聚合在0.6以下。

原始数据集合

聚合效果图