应用：多算法识别撞库刷券等异常用户

在运营业务中，绝大多数公司会面临恶意注册，恶意刷接口，恶意刷券等流量问题，此类问题的常规解决方案都是拍定单位时间内的ip访问上限次数、qps上限次数等等，会存在误伤、频繁修改阀值等问题。

问题剖析：
此类问题的关键在识别出与正常数据集群差异较大的离群点。所以，存在两个难点：

• 1.难以找到一个很清晰的边界，界定什么是正常用户，什么是异常用户
• 2.维数灾难及交叉指标计算之间的高频计算性能瓶颈

算法概述：

• 1.图形位置分布
• 2.统计方法检测
• 3.距离位置检测
• 4.密度位置检测
• 5.无监督模型识别

算法详述：
1.图形位置分布
当我们不需要长期监控异常用户，只需要少数几次识别异常用户，且精度要求不高的时候，我们可以采取简单方便的图形识别方式，例如：箱式图。

箱式图判断中，一般我们只需要锁定25%(Q1)分位点的用户特征值，75%(Q3)分位点的用户特征值，Q3与Q1之间的位差即为IQR，一般认定Q3+1.5个IQR外的点即为异常点，对应的用户即为异常用户。这种方法也叫做“盖帽法”，不必人为设定上限阀值，随着用户的数据变化而变化上界，避免了高频修改的问题，只是精度欠缺且绝大多数情况下识别出的异常用户较少。

方法比较简单，也不多加解释了。

2.统计方法检测
方法也比较简单，上线开发简单。一直是分两步：

• 先假设全量数据服从一定的分布，比如常见的正太分布，泊松分布等
• 在计算每个点属于这个分布的概率，也就是大家常用的以平均值和方差定密度函数的问题

因为这边，我们前期无法知道数据服从什么样的分布，所以，我们这边可以用切比雪夫不等式来代替确定的分布形式。除此之外，也就是同时用了马氏距离来衡量了每个具体的点在整体数据集中的位置。

核心代码就是下面这个协方差矩阵及矩阵相乘：

#两个维度之间协方差矩阵
S=np.cov(X)  
#协方差矩阵的逆矩阵
SI = np.linalg.inv(S)    
#第一次计算全量用户的维度重心
XTmean = XT.mean(axis=0)
d1=[]
n  = XT.shape[0]
for i in range(n):
    delta = XT[i] - XTmean
    d = np.sqrt(np.dot(np.dot(delta,SI),delta.T))
    d1.append(d)

这个方法的最核心的优点就是对全量数据进行了分块，可以理解为将1拆分成了必定有问题的1/m用户，可能有问题的1/n用户，必定没问题的1/w用户（1/m+1/n+1/w=1），这也奠定了后续更好的方法的基础。
但是问题也是很明显的，对于1/m，1/n的大小确定无法非常的精准，多了则影响正常用户，少了则无法准确拦截，还是一个划分的算法，并不能给出每个人的好坏程度。

3.距离位置检测
距离探测的方法有一个非常强的假设，正常的用户都比较集中，有较多的邻居，而异常用户都特立独行。
在常见的业务问题中都是满足的，比如对爬虫ip的识别，撞库的识别，这些一看那些高频访问的就不是正常用户，但是对于特别稀疏的业务场景，比如企业融资，高深度的敏感页面访问，均不是很适用，它们的频次较低无法构成一个邻居的概念。

这边非常常用的有2种，一个是连续特征间的欧式距离（标准化下的欧式距离（马氏距离）），另一个是名义变量下的余弦相似度。

这边只讨论第一种情况，连续特征下如何衡量数据是否为异常数据。前面我们也说到了，切比雪夫不等式的方法能够有效的划分出三个类别正常用户，异常用户，未知用户。所以，相应的，我们只需要在未知用户的集群里面去寻找与正常用户更不相似的，或者和异常用户更相似的用户就可以了。

对于单变量衡量：

对于多变量衡量：

核心计算相似度的方式就是以上两个公式，会有一些细节处理的问题及注意点，大家可自行研究。

4.密度位置检测
这边先等下谈原理，较为冗长，先说结论，其实，在能够使用距离位置检测的情况下，优先使用距离位置检测的方法。密度方法的前提几乎与位置方法的前提一致，但是在计算量级上而言，存在较大的差异差别。

上述的图片是Fei Tony Liu, Kai Ming Ting, Zhi-Hua Zhou的一篇论文里面对比的常见的iForest,ORCA,LOF(也就是密度位置检测),RF方法的准确率和耗时情况，也清晰的可以看出，同为距离衡量的ORCA的耗时较大，但是LOF的耗时更高，甚至部分情况下都无法计算出结果。

下面让我们看下理论先，密度位置检测的方法之一，LOF：
概念定义：

1. d(p,o)：两点p和o之间的距离；
2. k-distance：第k距离
   　　　　对于点p的第k距离dk(p)定义如下：
   　　　　dk(p)=d(p,o)，并且满足：
   　　　　　　a) 在集合中至少有不包括p在内的k个点o,∈C{x≠p}， 满足d(p,o,)≤d(p,o) ；
   　　　　　　b) 在集合中最多有不包括p在内的k−1个点o,∈C{x≠p}，满足d(p,o,)<d(p,o) ；

上面两个条件总结起来就是1.距离范围内至少满足一定数量的点数，2.最多允许有一个距离最大的非p点
形象的看，距离就是p的第k距离，也就是距离p第k远的点的距离，不包括p，如下图箭头的路径长度。

3. k-distance neighborhood of p：第k距离邻域
   　　　　点p的第k距离邻域Nk(p)，就是p的第k距离即以内的所有点，包括第k距离。
   　　　　因此p的第k邻域点的个数记为 |Nk(p)|，且|Nk(p)|≥k

我们在定义一些衡量指标，那么LOF就算是完成了：
1、可达距离（reach-distance）
点o到点p的第k可达距离定义为：
reach-distancek(p,o)=max{k−distance(o),d(p,o)}

2、局部可达密度（local reachablility density）
点p处的局部可达密度为：

其中，|Nk(p)|为p的第k领域点的个数，∑o∈Nk(p)reach-distk(p,o)计算的是p的k领域内的点到p的可达距离，也就是1中涉及的计算方式。

3、局部离群因子（local outlier factor）
点p的局部离群因子为：
LOF（p） = （∑o∈Nk(p)lrdk(o)/lrdk(p)）/|Nk(p)|
其中，lrdk(o)/lrdk(p)比值衡量了p点与附近的点之间的密切差异情况，LOF值=1时，代表p与p附近的点密度一致；LOF值<1时，代表p点的密度大于p附近点的密度；LOF值>1时，代表p点的密度小于p附近点的密度，也是非常符合我们的前提假设的，异常点总是比较稀疏，正常点总是比较稠密的。

到此位置LOF的数学理论就完成了，让我们回顾一下它的思想。它其实就是找数据集合中的每一个点及其邻居的点，计算它和它的邻居的密度，当它的密度大于等于它邻居的密度的时候，则认为它是稠密中心，是正常用户数据；否则异常。
但是要计算每个点及对应的邻居的LOF值，计算成本也是非常的高的，最初我们也指出了这一点。

核心代码：

def k_distance(k, instance, instances, distance_function=distance_euclidean):
    distances = {}
    for instance2 in instances:
        distance_value = distance_function(instance, instance2)
        if distance_value in distances:
            distances[distance_value].append(instance2)
        else:
            distances[distance_value] = [instance2]
    distances = sorted(distances.items())
    neighbours = []
    k_sero = 0
    k_dist = None
    for dist in distances:
        k_sero += len(dist[1])
        neighbours.extend(dist[1])
        k_dist = dist[0]
        if k_sero >= k:
            break
    return k_dist, neighbours

5.无监督模型识别
其实这边说完全的无监督，我觉得不是很准确，我觉得叫“半监督”可能更好一些。
这边方法很多，我只介绍两种：
1.Iforest
2.RNN

先让我们看下Iforest：
算法的关键在于:对于一个有若干维的数据集合，对于其中的任一维度，如果该维度是连续属性的话，在若干次随机二分类后，边界稀疏点最容易优先达到子叶节点,如下图：

算法实现详细的过程为：
假设数据集有N条数据，构建一颗iTree时，从N条数据中均匀抽样(一般是无放回抽样)出m(通常为256)个样本出来，作为这颗树的训练样本。在样本中，随机选一个特征，并在这个特征的所有值范围内(最小值与最大值之间)随机选一个值，对样本进行二叉划分，将样本中小于该值的划分到节点的左边，大于等于该值的划分到节点的右边,重复以上划分步骤，直到达到划分层数上限log(m)或者节点内只有一个样本，一棵树Itree的结果往往是不可信的，所以我们可以训练100-255棵树，最后整合所以树的结果取平均的深度作为输出深度，也叫做Isolation Forest。

有了算法逻辑，再看衡量指标：

其中，h(x)为x对应的节点深度，c(n)为样本可信度，s(x,n)~[0,1]，正常数据来讲s(x,n)小于0.8，s(x,n)越靠近1，数据异常的可能性越大。（这边需要注意，在sklearn中的Isolation是取得相反的逻辑，score越小数据异常的可能性越大。）

这边也贴上核心代码：

 def fit(self, X, y=None, sample_weight=None):
        X = check_array(X, accept_sparse=['csc'], ensure_2d=False)
        if issparse(X):
            # Pre-sort indices to avoid that each individual tree of the
            # ensemble sorts the indices.
            X.sort_indices()

        rnd = check_random_state(self.random_state)
        y = rnd.uniform(size=X.shape[0])

        # ensure that max_sample is in [1, n_samples]:
        n_samples = X.shape[0]
        if not (self.max_samples <= n_samples):
            warn("max_samples is larger than the total number of samples"
                 " n_samples. Corrected as max_samples=n_samples")
            self.max_samples = n_samples
        if not (0 < self.max_samples):
            raise ValueError("max_samples has to be positive")

        super(IsolationForest, self).fit(X, y, sample_weight=sample_weight)
        return self

    def _cost(self, n):
        if n <= 1:
            return 1.
        else:
            harmonic_number = np.log(n) + 0.5772156649
            return 2. * harmonic_number - 2. * (n - 1.) / n

2.RNN
通常我们会以5层的卷积神经网络作为训练网络。我在这边处理之前将切比雪夫不等式划分出来的正常用户作为0-output，异常用户作为1-output，然后尽可能的降低损失函数的误差即可。

第一层是常规层，将不同的input做线性组合：

第二层、第四层是做数据非线性变化：
这边选用的是tanh函数

第三层是做梯度分层下的非线性变化，抹平相似特征间的ouput：

其中，k为3，N为想要分的梯度的个数，a3为一个阶梯跳跃到另一个阶梯的转换效率，形如：

第五层，也就是最后一层通过sigmoid进行0-1之间的压缩。

这边的损失函数用的是常见的mse：

当通过测试数据训练完成后，再将未知数据进行模型训练，观察得到结果的大小，越靠近1，越有可能为异常用户。

以上就是5种常见的只基于数据下的异常用户的识别，更偏方法技术一点，但是无论是算法实现还是业务应用中，同样需要注意输入特征的问题。由于大家运用方向不同，就不细节赘述。

详细实现demo可以私信我要，最后谢谢大家阅读了。