分布式方法中基于最近邻算法的无监督距离离群点检测

Jayshree S.Gosavi¹，维诺德²

印度普那瓦格霍里Savitribai Phule Pune大学计算机工程系研究生
助理教授，计算机工程系，ICOER, Savitribai Phule浦那大学，Wagholi，浦那，印度

摘要

离群值检测是从给定数据集中发现离群模式的过程。离群值检测成为各个知识领域的重要课题。数据量每年都翻一番，因此需要尽早检测出大型数据集中的异常值。在高维数据中，由于维数的诅咒，离群点检测面临着各种挑战。通过在无监督离群值检测上下文中再次检查反向最近邻的概念，高维可以产生不同的影响。在高维中，观察到反向邻居计数点的分布变得倾斜。本文的工作旨在开发和比较一些无监督离群点检测方法，并提出一种改进方法。本文详细介绍了局部离群因子(LOF)、局部距离离群因子(LDOF)、影响离群因子(influence Outliers)等离群值检测算法的发展和分析，并结合这些算法的概念，实现了一种新的分布式方法，在速度、复杂度和精度等方面均有较好的改进。

关键字

离群值检测，高维数据，反向近邻，无监督离群值检测方法。

介绍

数据中的异常值检测定义为在不符合正常行为的数据或不符合预期行为的数据中发现模式，这样的数据被称为异常值、异常值、异常值。Anomaly和Outlier意思相似。分析人员对异常值非常感兴趣，因为它们可能代表各个领域的关键和可操作的信息，例如入侵检测、欺诈检测以及医疗和健康诊断。异常值是数据实例中不同于其他数据集的观察值。出现异常值的原因有很多，比如数据质量差，设备故障，前信用卡欺诈。

与数据实例关联的数据标签显示该实例属于正常数据还是异常数据。基于数据实例标签的可用性，异常检测技术分为以下三种模式:1)监督异常检测，在监督模式下训练的技术考虑训练数据集中正常类和异常类的标记实例的可用性。2)半监督异常检测，在监督模式下训练的技术考虑到正常的标记实例的可用性，不需要标记异常类。3)无监督异常检测，在无监督模式下运行的技术不需要训练数据。

基于最近邻的离群点检测方法有很多种，这些方法都考虑到离群点出现在离它们最近的邻居很远的地方。这种方法基于距离或相似度度量来搜索邻居，具有欧几里得距离。许多基于邻居的方法包括将一个点的离群值定义为到它的第k个最近邻居的距离(k-NN方法)，一些方法根据它的相对密度来确定一个点的分数，因为给定数据点到第k个最近邻居的距离可以被视为它周围的逆密度的估计值。

2相关工作

作者[2]为给定的数据实例分配一个称为局部离群因子(LOF)的异常分数。对于任何给定的数据实例，LOF分数等于该实例的k个最近邻居的平均局部密度与数据实例本身的局部密度之比。为了找到一个数据实例的局部密度，作者首先找到以包含k个最近邻居的数据实例为中心的最小超球的半径。然后用k除以这个超球体的体积来计算局部密度。对于一个稠密区域中的正常实例，其局部密度与相邻实例相似，如果其局部密度低于最近的相邻实例，则该实例为异常实例。因此异常实例将获得更高的LOF分数。在[3]中，作者提出了一种基于局部距离的离群因子(LDOF)的离群值检测方法，用于检测分散数据集中的离群值。以此来测量有多少物体偏离了它们分散的邻域。使用对象与其邻居之间的相对距离。一个对象的违例程度越高，大多数对象是离群值。 In [4] proposed on a symmetric neighborhood relationship measure considers both neighbors and reverse neighbors of an object when estimating its density distribution .To avoid problem, when outliers are in the location where the density distributions in the neighborhood are significantly different.

在[5]中，作者提出了一种基于反向最近邻的数据流离群点检测算法SODRNN。处理滑动窗口模型，检测异常异常点查询在当前窗口中按顺序执行。仅在当前窗口的一次扫描中更新插入或删除，从而提高效率。

在[6]中，提出了一个基于一组相关子空间投影中的对象偏差的离群值排名。它排除了显示异常值和残留对象之间没有明显区别的无关投影，并发现在多个相关子空间中偏离的对象，解决了检测隐藏在数据子空间中的异常值的一般挑战。在[7]中，作者提出了由各种离群值模型提供的离群值分数的统一，并将任意的“离群值因子”转换为范围[0,1]中的值，可解释为描述数据对象成为离群值的概率的值。在[8]中提出了一种新的无参数离群值检测算法来计算有序距离差离群值因子。通过考虑有序距离的差异，为每个实例制定一个新的离群值得分。然后，使用这个值来计算离群值。

3现有的系统

A.局部离群因子(LOF:

在LOF中，将实例的局部密度与其邻域实例的密度进行比较，然后给给定的数据实例赋异常值。任何数据实例都是正常的，而不是异常值，LOF分数等于实例k个最近邻居的平均局部密度与数据实例本身的局部密度之比。为求数据实例的局部密度，求以数据实例为中心的小超球半径。实例的局部密度是通过除以k,i的体积来计算的。k超球面的近邻和体积。在这种情况下，为每个对象分配一个程度作为一个异常值，称为局部异常值因子。取决于它的程度，它决定了对象是如何与周围的邻居隔离。位于密集区域的实例是正常实例，如果它们的局部密度与相邻实例相似，则该实例的局部密度低于其最近的相邻实例，则该实例为离群实例。采用top-n方式，LOF更可靠。因此，它被称为top-n LOF，意味着具有最高LOF值的实例被视为异常值。

B.局部距离离群因子(LDOF):

基于局部距离的离群因子度量分散数据集中对象的离群性。该方法使用对象与其邻居的相对位置来确定对象与其邻居实例的偏差程度。在这个分散的社区被认为。数据实例的偏差度越高，越有可能成为异常值。该算法首先计算每个物体的局部距离，然后对LDOF值最高的n个物体进行排序。LDOF值最高的前n个对象被视为离群值。

C.影响异常值(INFLO):

该算法考虑了离群点位于邻域密度分布显著不同的位置的情况，例如物体从稀疏聚类靠近密度较大的聚类，这可能会给出错误的结果。该算法考虑了对称邻域关系。在考虑影响空间时，在估计其密度分布时也考虑对象的邻居和反向邻居。为数据库中的每个对象分配一个受影响的离群度。输入值越高，表示该对象是离群值。

d .缺点:

1.阈值用于区分异常值与正常对象，阈值越低，异常值检测的假阴性率越高。

2.当数据实例位于两个聚类之间时，随着分母值的增大，k个最近邻域对象之间的距离增大，导致误报率较高。

3.需要提高计算异常值的检测速度。

4.需要提高基于密度的离群点检测的效率。

四、拟议系统

A.拟议系统的描述:

提出的系统将提供大型数据集收集的输入，由于数据是从标准数据集存储库收集的，在将数据传递给系统的下一阶段之前将进行数据预处理。此外，这些预处理过的输入被传递到分区模块，这些数据集被划分到多个节点中，其中一个节点是管理节点，并生成分区统计数据，这些统计数据被可视化。其次，在离群值检测模块中，对预处理后的输入数据集提出了分布式算法来识别离群值。这些结果将在性能评估中为所提出的算法分布式方法进行评估。

1)数据收集和数据预处理:

在数据收集中，本系统的初始输入数据将从标准数据集门户收集，即UCI数据集存储库。根据系统的建议，本系统将使用标准数据集，包括Cover类型、IPS数据集。因此，收集的数据集可以以原始的、未压缩的形式提供;在进行后续步骤之前，需要对这些数据进行预处理。对大型数据集内容进行预处理，可用的技术有数据挖掘，如数据集成、数据转换、数据清洗等，将被使用和清洗，生成所需的数据。

2)数据分区:

在该模块中，如前所述，在系统执行计划中，根据所需数量的客户端发出的数据请求，将预处理后的数据从中央管理节点即服务器上划分为客户端数量。然后，各个客户端将对该分区数据进行处理，以根据应用的算法策略识别异常值。

3)异常值检测:

所提出的异常值识别技术将首先应用于分布式客户端，并在异常值计算的最后阶段将检测到的异常值结果集成到服务器机器上。为此，提出了基于ABOD的KNN算法和基于info的离群值检测策略。

该方法基于基于最近邻的异常检测技术，提出了一种基于最近邻的分布式异常检测方法。该方法假设正常数据实例发生在密集的邻域，而异常值实例发生在远离其近邻的地方。在本文提出的工作中，使用基于最近邻的异常检测技术的概念:(1)使用一个数据实例与其第k个最近邻居的距离来计算离群值。(2)计算每个数据实例的相对密度来计算其离群值。

提出的算法将k次出现定义为具有有限n个点集的数据集，对于数据集中的给定点x，根据给定的相似度或距离度量将k次出现的次数表示为Nk(x)，即x在k个最近邻居的所有其他点中出现的次数，并将频繁出现的点作为枢纽点，将不经常出现的点作为反枢纽点。使用反向最近邻居作为实例，查找与查询对象最近的实例。该方法首先读取高维数据集中的每个属性，然后使用基于角度的离群值检测技术，使用数据集设置距离计算每个属性的距离，并与每个实例的距离进行比较，并分配离群值得分。基于该离群值，使用反向最近邻函数确定特定实例是否是离群值。

4)绩效评估和结果可视化:

在本模块中，上述方法检测到的离群值将根据设定的评价参数进行评价，对其进行性能评价。性能评估还将提供有关已实现的系统性能指标、约束条件和未来范围的方向的详细信息。在结果的适当可视化的帮助下，系统执行将使其评估者更容易理解和探索。

五、实验设置与评价

我们使用高维数据集执行测试，该数据集是UCI机器学习库中的Cover Type数据集，其中包含54个属性数量和581012个实例数量。实验评估是在2.53 GHz的Intel双核CPU和4 GB RAM上进行的，操作系统是windows。该算法完全用Java语言实现，用于处理高维数据中的数据实例。

六。结论

本文提出了基于ABOD的KNN算法和基于无监督学习的基于分布式方法的INFLO方法，旨在实现和比较几种无监督离群点检测方法，并在速度和精度方面进行改进，降低假阳性错误率，降低假阴性率，提高基于密度的离群点检测和与现有算法比较的效率。未来的实现是机器学习技术，如监督和半监督方法。

参考文献

V. Chandola, A. Banerjee和V. Kumar，“异常检测:调查”，ACM计算调查，第41卷，no. 1。3，第15页，2009年。
M. M.布吕尼，h . p。Kriegel, R. T. Ng和J. Sander，“LOF:识别基于密度的局部异常值”，SIGMOD Rec，第29卷，no. 2。2, pp. 93-104, 2000。
K. Zhang, M. Hutter，和H. Jin，“一种新的基于局部距离的分散真实世界数据离群值检测方法”，第13届亚太知识发现和数据挖掘会议(PAKDD)，第813-822页。2009.
金伟，董安桂华，韩杰，王伟，“基于对称邻域关系的异常值排序”，第10届亚太知识发现与数据挖掘会议，第577-593页，2006。
C.李军，L. Xiyin, Z. Tiejun, Z. Zhongping, L. Aiyong，“一种基于反向k近邻的数据流离群点检测算法”，第3届计算智能与设计学术研讨会，pp. 239 - 239, 2010。
Emmanuel miller, Matthias Schiffer, Thomas Seidll，“异常值排名相关子空间投影的统计选择”，IEEE, ICDE会议，pp。434 - 445,2011。
Hans-Peter Kriegel Peer Kr¨ger Erich Schubert Arthur Zimek，“解释和统一异常值分数”，SIAM数据挖掘国际会议(SDM)， Mesa，第13-24页。阿兹,2011年。
Nattorn Buthong, Arthorn Luangsodsai, Krung Sinapiromsaran，“基于有序距离差的离群值检测评分”，国际计算机科学与工程会议(ICSEC)，pp。157 - 162, 2013。
H.-P。Kriegel, M. Schubert，和A. Zimek，“高维数据中基于角度的异常值检测”，Proc 14 ACM SIGKDD知识发现和数据挖掘(KDD) Int Conf, pp. 444-452, 2008。