基于特征选择和子空间搜索的离群点检测算法

摘 要： 为解决高维空间下基于密度的离群点检测的低精度和高计算量的问题，提出基于特征选择和子空间搜索的离群点检测算法。该算法先通过特征选择选择数据的主要属性，然后对这些属性进行子空间搜索，从而有效的降低维数和避免全局搜索。最后通过一个数据集的实验来说明该算法的有效性。

关键词： 高维空间；离群点检测；特征选择；子空间搜索

中图分类号：TP301.6 文献标识码：A 文章编号：1671－7597（2012）0210130－02

0 引言

离群点检测已经广泛应用在网络入侵、金融分析、公共卫生和安全等上。目前主要有四种方法用于离群点检测：基于统计的方法，基于聚类的方法，基于距离的方法以及基于密度的方法。

Peter J.Rousseeuw et al.[1]总结了几种基于统计的离群点检测方法，它们可用于单变量、低维和高维数据集检测。然而，在实际数据集中，并不知道数据分布模型，因此，这种检测方法效率很低。为解决这一问题，相应的聚类方法应用而生。它将不属于任何一个类的数据点视为离群点。本文在求核密度前会对数据先聚类。

基于距离和密度的检测方法则是应用最广的。它们首先分别被Knorr et al.[2]和Breunig et al.[3]提出。然而，因为数据集可能会包含有一些噪音、不相关或冗余的属性，在全维空间下求距离已经变得没有意义[4]，甚至会影响精度。为了提高针对高维和分布式数据检测的性能和精度，Nguyen et al.[5]提出了HighDOD的子空间检测方法，它具有良好的精度。但是，因为它是在全维属性下计算，所以时间花费巨大，同时也可能会影响精度。本文使用迹比准则先对全维属性进行特征选择，然后对其采用类似的方法进行离群点检测。

1 FSS算法

1.1 相关概念和定义

定义1：z-score规范化：对数据集进行预处理，即属性A的值v规范化为v'。

其中， 和 分别为A的均值和标准差。

定义2：特征子集（ ）得分：用于特征选择的评价准则。

其中， 为转换矩阵 为数据矩阵， 为 拉普拉斯矩阵，具体设置参看文献[6]。

定义3：OC(p,S)：点p在子空间S下的离群系数（Outlier Coefficient）。

其中， 是S的维数， 是p在S下的k-最近邻数据点的集合， 是S下点p和q的欧拉距离。

1.2 FSS算法具体实现

FSS算法的主要思想是：先用迹比准则选择主要的特征属性，然后对特征属性做i-dimensional（i=1,2,…,subspacemaxsize）的搜索离群点，而对剩余的属性仅做1-dimensional子空间的搜索。对每一个子空间S的搜索，都保留前n个OC（p,S）最大的数据在OutlierSet中，直到搜索结束。最后OutlierSet中的数据点便是检测到的离群点。主要有两个函数：特征选择函数FeatureSelection和子空间搜索函数SubspaceSearching，具体如下：

1.3 时间复杂度分析

FeatureSelection()的时间复杂度为 ，iter为 收敛的迭代次数，n为训练集样本个数，d为维数；SubspaceSearching()的时间复杂度为 ，j=subspacemaxsize, n为要检测的离群点个数。

2 实验分析

本试验中的数据集WDBC来自UCI[7]，将本文算法与经典算法top-KNN

其中 为可疑的离群点数，本实验取m=15， 、n为m个实例中真离群点的个数， 均为数据集中离群点的个数， 为前m个实例中第i个离群点的所在的序号。实验结果如图：

从实验结果来看，FSS在三个参数都有较好的表现，不足之处的原因可能来自特征选择和子空间搜索维数的不足。

3 总结

本文提出了一种基于特征选择和子空间搜索的FSS算法，该算法针对高维数据集来说有较好的表现，它降低了数据的维数又避免了全维空间搜索，在时间性能上有一定优势。不过，因为特征选择需要用户输入参数，在一定程度上影响了检测的精度，这也是今后要努力的方向。

参考文献：

[1]Peter J. Rousseeuw, Mia Hubert, Robust statistic for outlier detection. 2011 John Wiley & Sons, Inc. WIREs Data Mining Knowl Discov 2011:73-79.

[2]Knorr, E.M., Ng, R.T.,Tucakov and V.,Distance-based outliers: Algorithms and applications, In: VLDB Journal 8, 2000:237-253.

[3]Breunig, M.M., Kriegel, H.P., Ng, R.T., Sander and J, Lof: Identifying density-based local outliers, In: ACM SIGMOD on Management of Data, 2000:386-395.

[4]Aggarwal, C.C., Yu, P.S: An Effective and Efficient Algorithm for High-Dimensional Outlier Detection. VLDB J, 2005, 14(2):211-221.

[5]Hoang Vu Nguyen, Vivekanand Gopalkrishnan and Ira Assent, A Unbiased Distance-Based Out lier Detection Approach for High-Dimensional Data, In: DASFAA 2011, LNCS 6587,2011:138-152.

[6]Feiping Nie, Shiming Xiang, Yangqing Jia, Changshui Zhang, Shuicheng Yan, Trace Tatio Criterion for Feature Selection. In: Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, 2008.

[7]archive.ics.uci.edu/ml/.

作者简介：

仲训标（1988-），男，汉族，江西省南康人，硕士研究生，在读，研究方向：数据挖掘；黄晓霞（1968-），女，汉族，上海人，博士研究生，专业教师，工作单位：上海海事大学，研究方向：嵌入式系统，物流信息化技术，智能信息处理，供应链信息处理等。