异常检测：基于聚类模型(原理篇)

• 系统运维中的异常检测Anomaly Detection概述
• 异常检测：基于分类模型
• 异常检测：基于聚类模型-原理篇
• 异常检测：基于聚类模型-实践篇
• 异常检测：基于OneClass模型 ( 待续 )
• 异常检测：基于数据重构 ( 待续 )
• 异常检测：基于深度学习 ( 待续 )
• 异常检测：基于集成学习 ( 待续 )

异常检测与无监督学习。 大部分情况下异常极少发生，常混在在大量的正常数据中，数据量少和不同类别的数据不均衡，导致模型难以从这些特点的数据中有效地学习异常的特征，常用的机器学习算法不能直接应用于异常检测。所以异常检测大量使用无监督学习算法。

无监督学习聚类算法。 无监督学习方法种类繁多，它根据样本自身的特点，将样本聚成多个簇一些聚类算法还可提取离群点作为 Noisy ：

• 基于距离的算法。样本点的特征张成的一个高维空间，数据分布在该空间中，距离较近的点为聚成一个簇，例如 K-Means ，层次聚类， Gaussian Mixture 等。
• 基于密度的算法。根据数据的密度，稠密的点聚成一个簇，远离稠密区域的离群点为噪音，例如 DBSCAN ， density peak ， MeanShift 等。
• 其他聚类算法。例如基于相似度传播的 Affinity propagation ，根据之间的相似度进行传播，相似的点聚成一个簇。基于矩阵分解的谱聚类 (spectral clustering) 。

下面是无监督学习聚类算法在不同数据上的聚类效果：

以上算法大多数可用于异常检测，我们从上面分类中各挑选一种介绍，下面分别介绍K-Means和DBSCAN来介绍异常检测的原理。

基于 K-Means 算法的异常检测。 K-Means 是最简单、最容易理解的聚类算法，它通过迭代地反复执行下面 2 个步骤，就可以将数据聚成 K 个簇：

• 选择簇中心。由样本的特征形成一个高维空间，例如数据是 2 个特征，那么就形成 2 维的平面，样本分布在这个空间中。计算出 K 个簇的中心位置，也就是特征的平均值的位置，该位置就是该簇的中心。
• 样本的簇分配。计算每个点于簇中心的距离，距离那个簇中心近，该点就分配给该簇，最终形成 K 个簇。下面是 K-Means 的动画示意图：

我们可以将远离簇中心的点作为离群点，来进行异常检测。

基于 DBSCAN 的异常检测。 DBSCAN 是一种基于密度的聚类，它可以寻找数据中的高密度区域，将高密度区域的数据连成一个簇。该算法有 2 个重要的参数分别为 Eps 和 min_samples, Eps 表示半径， min_samples 表示以该半径画出的圆中样本点的最小数目。该算法以一个样本点为圆心，以 Eps 为半径画一个圆，如果圆中样本点的数目大于或等于 min_samples ，则表示该点周围的点比较密集，那么该点是一个核心点 (core point), 核心点与周围的点形成簇。如果一个样本点不是核心点，自己也远离其他核心点，不能“融入 ” 其他核心点所在的簇，该点就是噪音。我们将该噪音当做离群点，便可以进行异常检测。

如何使用聚类进行异常检测。 有多种方法，例如：

• 在异常检测中，对最后形成的聚类结果，计算每个样本点到聚类中心的距离，对该距离进行排序，将原理聚类中心的样本作为离群点。
• 对每个点计算轮廓系数，对轮廓系数进行排序，将轮廓系数较小者作为离群点。

轮廓系数原本是衡量聚类好坏的评价指标，值在 [1,-1] 之间，值越大聚类结果也越好。先计算每个点的轮廓系数，然后将所有点的轮廓系数求平均就是该聚类结果的轮廓系数：

先计算 a 和 b ， a 表示一个样本距离簇内其他点的平均值，对于 b ，计算该点和其他簇中点距离平均值，然后最最小的一个。在异常检测中，我们计算每个点的轮廓系数即可。

总结。 KMeans 算法简单容易理解，被广泛使用，但也存在一些问题，例如簇的数目如何确定，簇中心的初始化对结果的影响较大，生成的各个簇中元素数目类似 , 特别是在使用 K-Means 时需要先指定簇的数量。不过这些问题都有其他方法在某种程度上解决这些问题。 DBSCAN 是一个基于密度的聚类，不需要选择簇的数量 K ，并且可以直接筛选出噪音作为离群点，作为异常检测算法较为便利。

聚类算法非常多，一些聚类算法如 2007 年发表于Science的相似度传播算法 (Affinity propagation) ， 2014 年发表于 Science 的 density peaks ，混合高斯模型，在无监督数据处理方面算法简洁精妙，值得学习，将来有空再来介绍这些赫赫有名的方法。