基于自然最近邻的离群检测方法研究.docx
14页
基于自然最近邻的离群检测方法研究 李士果 卢建云 邓剑勋摘 要：在实际应用中，近邻技术具有简单、快速、高效的特点，受到研究人员的青睐近来自然最近邻被提出并应用到离群检测和聚类中，鉴于自然最近邻消除了参数k设置的特点，本文将自然最近邻的概念应用到逆k最近邻、互k最近邻、共享k最近邻中，提出了自然逆最近邻、自然互最近邻和自然共享最近邻并将提出的3种算法在离群点检测中进行了实验对比分析实验结果表明自然逆最近邻和自然互最近邻能够有效发现局部和全局离群点关键词：近邻技术;离群点检测;自然最近邻;数据挖掘：2095-2163（2019）04-0040-06 ：TP391 文献标志码：A0 引 言近邻技术是数据挖掘和机器学习的重要技术之一，被广泛地应用到分类、聚类、异常检测、协同过滤、图像处理等研究领域在实际应用中，近邻技术具有简单、快速、高效的特点，一直以来受到研究人员的重视目前存在的近邻技术有k最近邻、互k最近邻、逆k最近邻、共享最近邻、自然最近邻这些近邻技术各有特点，自提出以来都得到了广泛的应用近来自然最近邻被应用到离群检测和聚类中，并取得了比较好的效果鉴于自然最近邻能够消除参数k设置，本文将自然最近邻这一特点应用到其它近邻中，提出了自然逆最近邻、自然互最近邻、自然共享最近邻的概念，并给出了相应的算法描述。
在离群检测应用中，对提出的自然逆最近邻、自然互最近邻、自然共享最近邻算法进行了实验对比分析，实验结果表明自然逆最近邻和自然互最近邻能够有效发现局部和全局离群点本文的主要贡献如下：（1）结合自然最近邻消除参数k设置的特点，提出了无参的自然逆最近邻、自然互最近邻、自然共享最近邻的概念，并给出了相应的算法描述;（2）在离群检测应用中，对提出的算法进行了实验对比分析，实验结果表明自然逆最近邻和自然互最近邻能够有效地检测局部和全局离群点1 相关研究最近邻概念直观、简单，认为一个对象与离其最近的对象具有相同的特点，最初被应用于基于示例的学习方法中从概率的角度出发，可以通过多个对象投票的方式来确定被分类模式的标签，则引入了k最近邻的概念k最近邻有非常广泛的用途，例如模式分类、机器学习、数据挖掘等领域[1]在模式分类中，k最近邻作为分类器对待识别模式进行分类，考虑每个近邻的贡献不同，出现了基于权重的kNN[2]分类方法在图像分割中，kNN与贝叶斯网络结合，出现了贝叶斯kNN图像分割算法[3]，还有kNN作为启发的区域迭代的图像分割算法[4]在数据挖掘中，k最近邻与距离结合衡量数据集中对象的密度，被用来进行离群点检测。
对于聚类应用，k个最近邻能够形成子图，通过相似度度量函数，不断合并相似的子图，直到满足需要得到的子图数目，从而实现聚类互k最近邻比k最近邻要严格，加入了一个限制条件，即要求2个对象p和q出现在对方的k最近邻域，则p和q为互k最近邻通常，构建的互k最近邻图更加紧密，常被应用到去噪、分类中[5]共享k最近邻进一步考虑了对象p和q邻域共有的近邻数目，采用量化的方法来度量两个对象的相似程度，常被应用到离群检测、聚类中[6]逆k最近邻与k最近邻具有相反的概念，是考虑一个对象对其周围对象的影响，被应用于决策支持、资源定位与营销等研究领域[7]目前，对逆k最近邻的研究主要集中在如何高效地进行搜索[8]最近提出的自然最近邻概念具有自适应的特点，不需要显示地指定参数k的值，而是通过迭代计算得到给定数据集的自适应k值自然最近邻被应用到高维数据结构学习、离群检测、分类、聚类等场景[9]自然最近邻在形成的过程中，带有密度信息和离群信息，能够被应用到局部密度估计和离群检测[10]2 近邻技术本节中，给出了互k最近邻、逆k最近邻、共享k最近邻和自然最近邻的定义，并对各种近邻的特点进行了分析2.1 互k最近邻在k最近邻的基础上，增加一个限制条件，即2个对象要互为k最近邻，这就是互k最近邻的思想。
2个对象互为k最近邻，恰恰反应了2个对象之间的紧密程度相对于k最近邻反映的是单边关系，而互k最近邻描述的是一种双边关系2.2 逆k最近邻求解k最近邻时，一个对象总是返回k个最近邻，每个对象拥有最近邻的数目是不变的在实际应用中，对于密度度量，处于稀疏空间的对象并不总是有k个最近邻逆k最近邻是与k最近邻具有相反含义的一种最近邻概念k最近邻反应的是查询对象离某个被查询对象最近，而逆k最近邻描述的是被查询对象对数据集中其它查询对象的影响，被查询对象能够影响的对象数目可能有一个、多个或者是没有2.3 共享k最近邻互k最近邻描述了2个对象之间的相近或紧密程度这种度量关系比较简单，只有紧密、不紧密，或者相近、不相近这样的二元关系共享k最近邻突破了这种二元关系，采用一种可以量化的度量方法，即衡量2个对象共有最近邻的数目，这种量化度量方式很好地表达了相对程度2.4 自然最近邻在k近邻技术中，参数k是需要设置的，对于不同的应用场景，参数k的设置也不尽相同，往往通过经验分析得到合适的参数值为了减轻参数k对最近邻计算结果的影响，邹咸林等人提出了自然最近邻概念[9]求解自然最近邻时，不需要指定参数k或者邻域半径ε，其是一种无尺度的最近邻概念。
求解自然最近邻的核心思想是设置计算的终止条件，整个计算过程是对给定数据集的一个自适应过程，当迭代计算收敛时，得到数据集中每个对象的自然最近邻自然最近邻数目是一种量化的度量方法，能夠反映数据集疏密分布情况求解自然最近邻的方式可以有多种，表现为迭代计算的终止条件不同3 自然最近邻在其它近邻中的应用本节中，给出了自然逆最近邻、自然互最近邻和自然共享最近邻的定义和算法描述自然最近邻概念的要点是“数据集中最离群的数据对象都至少有一条路径到达”，这个特点使得每个对象具有不固定尺度的近邻数目，也减轻了参数k对最终近邻数目的影响3.1 自然最近邻定义在定义7中，自然共享最近邻不是指2个对象p和q共有的近邻对象，而是指p和q的一种关系，如果p和q共有的近邻数目大于等于m，则p和q是一种自然共享最近邻的关系下面给出定义5到定义7的算法实现描述3.2 自然最近邻算法描述算法1 自然逆最近邻算法（NRNN）输入：数据集D包含n个对象输出：D中每个对象的自然逆最近邻数目算法描述如下：初始化变量r=1，向量nrnn（i）=0，0
在实际应用中，对于包含一些相对离群对象的数据集，算法的收敛性变的很差因此，在算法的具体实现中，加入了另外一个终止条件，即在迭代过程中数据集中没有逆最近邻的数据对象的数目连续两次没有变化，则算法停止该终止条件对算法的本质并没有影响，因为算法的目的是统计数据集中对象的逆最近邻数目，逆最近邻数目反映了数据对象的密度分布信息算法提前终止说明数据集中的一些对象处于相对稀疏的区域，这对数据集整体的密度分布并没有影响在下面2个算法的具体实现中，也加入了类似的终止条件算法2 自然互最近邻算法（NMNN）输入：数据集D包含n个对象输出：D中每个对象的自然互最近邻数目算法描述如下：初始化变量r=1，向量nmnn（i）=0，0
第10行是算法的终止条件，即数据集中的每个对象都至少有一个互最近邻算法3 自然共享最近邻算法（NSNN）输入：数据集D包含n个对象输出：D中每个对象的自然共享最近邻数目初始化变量r=m，向量nsnn（i）=0，0
实验数据集的具体信息见表14.2 评价指标采用精确率（Precision）、召回率（Recall）和F-Measure对3种算法的实验结果进行评价，3种评价指标的解释如下：精确率=（表示模型预测为所有正样本数量中真正为正样本的比例）;召回率=（表示模型准确预测为正样本的数量占所有正样本数量的比例）;F-Measure =（a2+1）（精确率*召回率）a2（精确率+召回率）当a=1时，F1 = 2*（精确率*召回率）/（精确率+召回率）4.3 实验和结果通过2个实验对3种自然最近邻算法NRNN、NMNN和NSNN进行对比分析第一个实验分析3种自然最近邻数目在DS1和DS2数据集上的统计分布情况，如图1和图2所示统计3种自然最近邻数目分布的目的，是通过分布反映数据集中对象所在区域的疏密情况通常情况下，拥有很多自然最近邻的对象处于数据集中比较密集的区域，具有很少自然最近邻的对象位于数据集中相对稀疏的区域，这与利用密度进行离群检测的方法吻合，通常离群点是位于数据集中相对稀疏的区域图1显示了NRNN、NMNN和NSNN在DS1数据集上的统计分布由此可以看出，当r值为5时，NRNN算法收敛，此时DS1中不是每个数据对象都至少有一个自然逆最近邻。
算法收敛是因为在连续2次迭代的过程中，没有自然逆最近邻的对象数目没有变化同理，在r值为6时，NMNN算法收敛NSNN算法设置的共享最近邻数目阈值为9，当r值为14时，DS1中每个对象都至少有一个自然共享最近邻图2显示了NRNN、NMNN和NSNN 3种算法在DS2数据集上的统计分布可以看出，NRNN算法在r=6时收敛，收敛时，数据集中仍有几个对象没有自然逆最近邻当r取值为9时，NMNN算法收敛，此时数据集中的所有对象都至少有一个自然互最近邻对于NSNN算法，共享最近邻数目阈值设置为9，当r值为15时，NSNN算法收敛，此时，数据集中仍有几个对象没有自然共享最近邻离群点通常处于数据集中稀疏的区域，根据自然最近邻数目在数据集上的分布，通过设置阈值找到拥有相对少的自然最近邻数目的对象，从而实现离群检测实验对比结果见表2和表3从表2可以看。
