基于近邻稳定性的离群点检测算法

黄馨玉　陈晓东

摘要：本文提出了基于近邻稳定性的离群点检测算法。实验证明本文提出的算法具有较高的精确度。

[关键词]离群点邻域质心不稳定因子

离群点是指那些明显偏离其它数据、不满足数据的一般模式或行为，与存在的其它数据不一致的数据。物理学中质心与稳定性间存在联系，离质心越近的点，稳定性越强，反之稳定性越弱。JihyunHa等人受这一性质的启发提出了使用不稳定因子的健壮离群点检测算法（INS算法）。该算法容易将处于稀疏区域与稠密区域的交界处的正常点误判为离群点。为解决该问题本文提出了基于近邻稳定性的离群点检测算法（NSINS算法）。

1基于近邻稳定性的离群点检测算法

1.1算法思想

本文提出了基于近邻稳定性的离群点检测算法。该算法的主要思想是：数据集中任意一"点p的k个最近邻组成p的k个邻域，其中第i个邻域包含了p和距离p最近的前i个点。每个邻域计算两个质心。一个质心与p相关，即邻域中包括点p时的质心;另一个质心与p无关，即邻域中不包括点p时的质心。最后会得到两类质心，每类都有k个。比较这两类质心的位置变化，最终确定p的不稳定程度。定义与p无关的质心考虑到了近邻的稳定性对p不稳定因子的影响。

1.2相关定义

定义1邻域（neighborhood）。点p的邻域表示距离点p最近的k个点的集合，用6：（p）表示，即：

其中d（p，q）表示p，q之间的距离，Pr是p的第k个最近邻。当P点计入6r（p）中时，6.（p）的基数是k+1;当p點不计入6r（p）中时，6，（p）的基数是k。

定义2相关邻域质心（relatedcentreofmass）。点p的相关邻域质心表示p的邻域包括点p时的质心，用rm，（p）表示：

其中（...q.）是点q在d维空间中的坐标。

定义3无关邻域质心（unrelatedcentreofmass）。点p的无关邻域质心表示p的邻域不含p时的质心，用urmx（p）表示：

其中点q代表第k个邻域中除p以外的任意一点，xq=（x**"，xx）是点q在d维空间中的坐标

定义4相关质心距离（distance of unrelated center mass）。相关质心距离表示两个相邻的相关质心之间的距离。用rm_d（p）表示：

定义5无关质心距离（distanceofunrelatedcentermass）。无关质心距离表示两个相邻的无关质心之间的距离。用urm_d：（p）表示：

定义6不稳定因子（instabilityfactor）不稳定因子定义为相关质心距离之和与无关质心距离之和的比，用INSF表示：

INSF（P）值为1，说明p与邻域内各点均匀分布;值大于1，说明p的加入使得邻域质心的变化加剧，从而说明p的不稳性较强;值小于1，说明p的加入使得邻域质心的变化减缓，从而说明p的稳定性较强。比值越大，p离群可能性越高。

2实例分析

数据集采用INS算法中的葡萄酒质量数据集。该数据集包括1599个红葡萄酒样本数据和4898个白葡萄酒样本数据。品质差的葡萄酒和品质高的葡萄酒数据量很少，是离群点检测的目标。红葡萄酒数据集中K取值50时，INS准确率88.9%，NSINS准确率94.4%;K取值100时，INS准确率88.9%，NSINS准确率100%。白葡萄酒数据集中K取值50时，INS准确率65%，NSINS准确率85%;K取值100时，INS准确率70%，NSINS准确率80%。

3结束语

本文提出的算法改进了使用不稳定因子的健壮离群点检测算法，考虑到了近邻的稳定性对被检测点的影响，该算法综合两类质心的变化情况来决定不稳定因子大小。在数据集分布不规则的情况下优势明显。

参考文献

[1]Xia Huo-Song. Data warehouse anddata mining technolo [M]. Beijing： Science Press， 2004： 229-231.

[2]Jihyun Ha， Seulgi Seok， Jong-SeokLee. Robust outlier detection us ingthe instability factor [J]. Knowledge-Based Systems. 2014（63）： 15-23.