基于谱聚类的离群检测

冯超　罗杰

关键词：谱聚类；候选离群因子；离群点检测；kNN

中图法分类号：TP311 文献标识码：A

1引言

目前，数据挖掘技术大多集中于挖掘数据集中数据对象的常规数据模式，然而并不是所有的数据对象都符合这种常规模式。数据集中一些新颖、不符合常规的少部分异常模式通常被视为噪声或异常而被抛弃，然而在很多应用中，这些小众的数据模式可能蕴涵重要的隐藏信息，如入侵行为、欺诈行为、医学上疾病前期的征兆等。这些稀有的异常模式通常被称为离群点，目前关于离群点并没有一个广泛认可的定义，按照Hawkins的观点：“离群点是偏离其他观察点非常大的观察点，以至于怀疑它是由不同的机制所产生的”。离群点挖掘的目的是在大量复杂的数据集中发现这些小部分的异常模式。

近年来，基于数据挖掘概念的离群点检测技术已经取得一定的研究成果，大致可分为基于分布的离群点检测方法、基于密度的离群点检测方法、基于距离的离群点检测方法和基于深度的离群点检测方法。谱聚类是近年来新出现的一种极具竞争力的聚类算法，它建立在谱图理论基础上，实质是将原始数据点映射到它的谱特征空间上，然后用K-means，C -means等方法对谱特征空间聚类实现原始数据集的聚类。与传统的K-means，EM聚类算法相比，谱聚类的优势在于聚类可以在任何形状的样本空间上进行并且能够收敛于全局最优解，因此逐渐受到广大数据挖掘研究者的重视。由于谱聚类算法只与数据的点数有关，而与维数无关，因此可以避免由高维特征向量造成的奇异性问题。另外，谱聚类可用于大规模数据集。离群点代表的是一种不同于主体结构特征的结构，鉴于谱聚类算法的诸多优势，将谱聚类方法引入离群数据挖掘中显得尤为重要，这将有利于从结构特征分析数据对象，并发现离群点与主体结构特征的相异之处，最终实现离群数据的挖掘。

本文在研究了离群数据挖掘和谱聚类相关理论的基础上，提出一种新型的基于谱聚类算法的离群点检测方法。仿真验证了该方法不仅在低维数据上有很好的效果，并且对高维及高维空间上的离群点检测具有更好的效果，这为目前基于距离和密度的离群点检测方法在高維数据空间上存在维数灾难等问题提供了重要的参考价值。

3仿真结果

以人工合成数据集为例，数据总数为140，其中索引号为0，80，81，82，106，116，124的数据点为离群点，索引号为0，106，116的数据点为局部离群点，索引号为80，81，82的点组成了离群簇，索引号为124的点为全局离群点。我们对所有数据点的kNN谱聚类求出的特征值和特征向量进行了分析，图1表示所有点谱聚类后第二小特征值与该点的kNN谱聚类后第二小特征值组的平均值的偏离程度。

图1中横线表示偏离阈值的分割线，横线以上部分是偏离值大于0.05的数据点，总数为24，横线以下部分是偏离值小于0.05的数据点，总数为116。之所以选择阈值为0.05，从统计学角度考虑，离群点一般是在数据集中出现概率小于某一阈值的数据点，在整个数据集中只占一小部分，为了得到包含所有离群点的最小候选离群点集，一般将偏离值选择为大于该值的数据点个数占整个数据集规模的15%～20%。从图1中可以看到，偏离程度大于0.05的数据点中包含所有的离群点。因此，我们受到启发：对于数据集中每个数据点的k个邻近点组成的数据集通过谱聚类算法求出的第二小特征值，以及该点每个k邻近点的kNN组经过谱聚类后得到的第二小特征值组的平均值，这2个值的差值越大的那些点意味着离群。

4结束语

通过谱聚类算法求解的特征值和特征向量，包含关于离群点和正常数据点谱的丰富信息。为了弥补传统方法的不足和充分利用特征空间的信息，本文提出了一种基于谱聚类的离群点检测的新思路。该算法的优点在于对大规模和高维数据集上的离群点检测具有很高的参考价值。

作者简介：

冯超（1986—），本科，工程师，研究方向：网络安全、个人信息保护。

罗杰（1985—），硕士，工程师，研究方向：网络安全、数据安全。