亿展宏图 第六篇|相似度构图的高效聚类方案
作者|尹航&梁伟明
编辑|林颖
供稿|eBay支付风控团队
本文共4797字，预计阅读时间10分钟
更多干货请关注“eBay技术荟”公众号
导读
“亿展宏图”是eBay 支付风控团队推出的系列文章，分享了eBay风控团队工作在图算法方面的一些理解和研究。在上期的亿展宏图 第五篇|基于异构图的深度学习算法里，我们介绍了基于异构图这一种网络结构，介绍异构图神经网络算法和一种我们开发的xFraud异构图算法模型。本期亿展宏图，我们将展示如何在海量数据的大图上构建基于相似度的边，并通过高性能的聚类算法进行聚类，并定位恶意注册团伙。
业务背景
随着在线购物的规模不断扩大，交易欺诈风险也随之增加。和传统的欺诈相比，如今的网络交易欺诈表现出专业化、产业化、隐蔽化和场景化的特点。而且，很多欺诈交易相互之间合作紧密，表现出了协同作案的“团队精神”。针对上述问题，单单只考虑相互独立的统计类因素已经不足以有效地打击此类欺诈，所以我们引入了图关系结构。
传统的图结构一般是基于交易建立的，在选择关联关系的时候会面临一些问题，如“强关联”关系（如银行卡号码）稀疏；同时“弱关联”关系虽然相对稠密，但是噪音又比较大（如收获地址是同一个转运仓）。那么，有没有一种介于两者之间的，既有比较高置信度的衡量“相似度”的能力又相对稠密的关系呢？这就需要用户行为出场了。
1
利用用户行为构建关联关系
1.1 为什么要选择用户行为
在某些已知的欺诈交易中，我们发现这些交易存在相同的活动轨迹，比如机器注册，机器下单等。而且他们都有动机明确、停留时间短和活动页面少的特点。这些活动轨迹和特点都可以从用户行为中分析出来，因此选择用户行为去构建关联关系可以更好地帮助我们发现欺诈交易。
1.2 如何量化用户行为序列
我们首先按照分布选取了大约40个页面作为行为数据的候选集。另外，不同页面的停留时间、商品类别和金额也是能很好量化不同行为的指标。再经过不同的实验，最终我们的网络输入由浏览页面序列以及相应页面停留时间序列组成。模型（如下示意图所示）采用了双向的长短期记忆（Long Short-Term Memory, LSTM）,其预测的目标为浏览的下一个页面。
(点击可查看大图)
根据上面的任务，我们得到序列的Embedding在盗刷退款（chargeback）角度的效果展示。如下图所示，利用T-SNE/PCA将序列Embedding放到三维空间，其中红色表示盗刷退款的订单。由下图可以看出对于不同的人群，用户行为基本都有一定的聚集性，所以后面我们将这种行为的相似引入到图中。
(点击可查看大图)
1.3 如何构建行为关联
根据上面的计算，获取了用户/订单的行为序列Embedding进行聚类，根据一定的阈值，属于同一类的订单之间就构成了一条“行为相似”的关联边。
2
HDBSCAN算法
这么大规模的交易在这样高的维度下，即使是传统最简单的KNN（K-Nearest Neighbors）也要聚类好几天，那该采用什么方法才能快速有效地进行聚类呢？这里就要隆重介绍一下我们自研的基于FAISS-gpu的HDBSCAN算法。
HDBSCAN的全称是Hierarchical Density-Based Spatial Clustering of Applications with Noise，标题虽看起来长且复杂，但它包含了这个算法的主要特性：层级的（Hierarchical）、密度的（Density-based）、空间的（Spatial，主要指适用于欧式距离或cosine距离）、适应噪音的（With noise）。
为了更好地理解HDBCSAN的优势，我们用如下图所示经典样本集举个例子，此样本集一共包含四个类别。此样本集有如下几个特点：首先是点的分布密度不均，特别是边缘附近；其次，下方的两个类别呈现交缠现象。
针对上述样本集，我们分别用经典的Kmeans算法和HDBSCAN算法进行聚类处理。
对于Kmeans，首先我们需要指定centroids number。其次，如下图所示，在指定相同ncentroids的情况下（前两个图所示），由于初始种子的随机，导致两个结果并不相同，即结果不稳定。
(点击可查看大图)
对HDBSCAN算法来说，在不用输入额外参数（准确的说还是需要一些系统参数的，但通常默认即可）的情况下，就可以得到很好的聚类结果。从下图可以看到，除了两个紫色点被标记为噪音外，其他类别均得到了很好的自适应划分。总而言之，HDBSCAN算法不用指定额外参数，而且聚类结果更稳定，说明该算法比Kmeans有更大的优势。
3
算法实现的优化
由于HDBSCAN效果很好，所以在scikit-learn库中也提供了HDBSCAN的实现，但问题是scikit-learn的实现对于工业级超大规模（千万级甚至更多）的数据来说，实在是太慢了。我们测试过仅仅是440K的数据，原版的实现就需要运行两天左右！因此需要我们去优化实现，以更短的时间得到结果。
由于我们着重介绍工程实现优化，本篇文章对于算法部分只做最简单的描述，感兴趣的同学可以参考原版文档查看更多细节，原版算法在scikit-learn上有非常详细的描述[1]。接下来我们主要从工程优化的角度出发，介绍原版算法的每一步优化策略。
3.1 空间转换
Transform the space
这一步核心工作是计算距离矩阵，并进行空间转换，从而突出噪音点。
为了更好的理解，我们将所有数据分布看作是大海中的小岛，而最终的目的就是找到那些孤岛。一个直观的想法是：孤岛附近的邻居小岛会很少，即使有两三个小岛抱团或互相靠近，他们仍然是孤岛。所以我们用每个岛与其最近的N个岛的最大距离，作为这个岛是否孤立的特征，称其为core distance。在原始距离矩阵上，如下图所示，两个点之间的距离如果小于其中任意一个点的core distance，就用core distance替代。这样孤岛就会被显著的标注出来，相当于对空间进行了变换。
空间变换[2]
计算全距离矩阵这一步实际上是最耗时的操作。如果不做优化的话，全距离矩阵的时间复杂度是O(|V|2*|dim|)， 在|V|=107, |dim|=102的情况下，总时间复杂度将达到1016！再乘以常数项，在大部分情况下就需要天级别的耗时了。接下来计算可达距离矩阵，其复杂度也是O(|V|2）。所以这一步的优化极为重要。
我们在仔细研究并通过实践后发现，第一步中的全距离矩阵在后续步骤中主要用于：①计算可达距离；②构建最小生成树。
这也就意味着对于每个点来说，并不需要所有的边，如果我们只提供最近的N条边，在大部分情况下也可以满足算法的要求。由于N是一个常数（实际中设为30即可获得非常近似的结果）。这样一来算法的复杂度就大为降低。另外，我们实际上也并不需要精确的KNN，我们需要的是对每个点来说它附近最近的若干条边，这些边会帮助我们扩展到其他边并构建最小生成树，进而构成聚类。如下图所示，左图是原算法依赖全连接矩阵，边的复杂度非常高。右图是我们优化后的算法示意图，边的复杂度缩小了一个数量级。
在这样的优化思想下，我们自然想到了Facebook AI Similarity Search(FAISS)。FAISS提供强大的基于高维向量的近似查找算法。更重要的是FAISS提供GPU版本的实现，性能更是突破天际！
更更更重要的是，FAISS提供了一系列的近似查找库，虽牺牲一定的准确性，但换来的是天际之外的成倍的效率提升。比如，利用Voronoi算法，先对空间进行划分，再计算n最近邻。在一系列的优化叠加下，对于12M的数据，80维的向量，计算K=30最近邻，在1个P100GPU的情况下只需要计算14分钟。效率得到了极大的提升。
3.2 构建最小生成树
Build the minimun spanning tree
这一步的核心思想是“剪枝”。为啥要这么做呢，实际上是为了下一步做层次树的计算。树实际上是一种特殊的有向无环图，也是联通图。上述提到的“剪枝”、“无环图”、“联通图”这些关键词自然会联想到最小生成树。最小生成树建立完，如下图所示，我们就能隐约看到层次化聚类树的影子了。
最小生成树[2]
最小生成树的经典算法是Kruskal和Prim算法。实现也并不难，但是在超大规模的数据上，工程实现的细节与最终的时间消耗有着成倍的差距。因此我们也分别实现了这两种最小生成树的算法，并根据实际数据分布做了工程实现上的优化，极力的压缩计算耗时。
比如在Kruskal算法中，需要对边按照距离排序。如下图所示，如果用python原生的sort函数对3.6亿个浮点数进行排序需要200秒左右，但是用cupy的GPU版本排序，耗时不到1秒！
再比如，算法中的排序实际上是带数据结构的排序，即按照边距离对边的属性一起移动。利用numpy的矩阵操作，可以更高效的实现。
3.3 构建聚类层次结构
Build the cluster hierarchy
这一步需要把最小生成树，转换成层次化的聚类层级树。算法的细节是：首先对边进行从小到大排序，依次合并每条边两端的两个点所属的子树（注意是合并点所属的子树，而不是直接合并两个点）。按照这个步骤，会逐步从下往上形成如下图所示的层次树。
层次树[2]
在这一步的实现必须用到并查集(Disjoint Set)。并查集的时间复杂度是|V|log|V|的，为了最大程度地压缩开销，我们也对这一数据结构进行优化，在合并两个集合的时候，需要做如下两个优化：
1）确保浅的子树挂到深的子树上；
2）在追溯root的过程中，修改路径上所有点的父节点为最终root。
(点击可查看大图)
3.4 压缩聚类树的层次结构
Condense the cluster tree
在实际数据（千万级）中，层次树深度可以达到百万级，这样的层次树是极度不平衡的。因此需要对整棵树压缩，即去除那些噪音节点。简单来说，压缩不平衡树的过程是从上往下递归的检查每一个子节点。如果当前节点的左右子树不平衡，比如左子树特别大，右子树特别小，就把当前节点替换成整棵左子树，右子树归并到当前节点的“噪音点集”中。如下图所示是样本集压缩后的树状结构。
压缩后的树状结构[2]
3.5 从压缩树中提取稳定聚类簇
Extract the clusters
最后从下向上递归的遍历子树，依据原算法计算每一个节点的“稳定性”，并根据“稳定性”，将一整棵树拆分成很多棵子树，每一棵子树都是一个最终的类簇。
提取稳定聚类簇[2]
压缩聚类树层次结构和提取稳定聚类簇这两步的实现都需要深度优先递归整棵树，但是在工业级的数据中，树的深度往往可以达到50w层，那么递归的实现必然会涉及到栈越界的问题。即使调整了栈空间，效率也会比较低下。这里我们在工程上用数组模拟了函数栈的调用，实现了树的深度遍历算法。
我们将优化后的算法实现和原版的进行对比（如下表前两行，pHDBSCAN算法是我们的实现版本）。经过以上一系列的优化和实现之后，性能有了大幅度提升。
另外，在数据大小为12M、维度80和GPU有两个的情况下，计算时间可以冲进一小时以内，比一个GPU的计算时间有显著提升。
特别值得注意的是上表最后两行的数据对比，在总时间复杂度差不多的情况下，即12M 80维 vs 8M 200维，后者所需的时间消耗远小于前者，说明特征维度对最终计算时间的影响较小，影响最终时间消耗的主要是数据量。
4
反欺诈应用
根据上面的介绍，我们已经有了每个用户/每笔订单的行为序列Embedding。利用内部基于GPU的HDBSCAN，我们就可以将大量的序列进行聚类, 成团概率大于50%，根据业务需要进行了一些筛选，作为行为相似度边。至此，我们在原有的强关联关系（如银行卡，IP地址等），加入了行为相似度边，使得图变得稠密，使得下游学习任务能够学到更多不同角度的信息。
在基于图的学习中，首先构建以订单为节点的，以行为相似度、支付令牌、IP、邮寄地址等作为关系的图，我们利用订单、卖家、买家等相关的200多个特征，以及是否发生过退款作为标签，使用GCN算法对标签做预测，这里对GCN算法不做过多赘述，在我们的应用中，可以简单理解为是结合了节点本身和邻居信息的浅层神经网络。从结果来看，加入行为边后对于未参与训练的数据的预测效果优于只使用传统强关联关系的图。
5
总结
本期文章，我们针对反欺诈的实际应用，在海量数据的大图上，我们加入了基于用户行为作为关联关系，并采用我们自研的基于FAISS-gpu的HDBSCA算法进行聚类，此聚类方法大大提高了性能和效率。如此我们将基于行为相似度构建的图，应用在反欺诈的识别场景中。针对以上相关技术有感兴趣的朋友，欢迎大家与我们沟通。下一期“亿展宏图”，我们将带大家从静态图算法延伸到动态图算法模型，敬请期待！
参考资料：
[1]https://hdbscan.readthedocs.io/en/latest/index.html
[2]https://hdbscan.readthedocs.io/en/latest/how_hdbscan_works.html
[3]https://en.wikipedia.org/wiki/Ackermann_function#Inverse
[4]https://en.wikipedia.org/wiki/Disjoint-set_data_structure
往期推荐
亿展宏图 第一篇|两张图入门图算法
亿展宏图 第二篇|图算法在eBay支付风控领域的应用
亿展宏图 第三篇|如何高性能训练图神经网络
亿展宏图 第四篇|当图算法遇到大数据
亿展宏图 第五篇|基于异构图的深度学习算法
点击阅读原文，一键投递
eBay大量优质职位虚席以待
我们的身边，还缺一个你