第5期 冯骥，等：基于自然邻居邻域图的无参数离群检测算法 ·999· 应用推进了人们的生活中，大数据研究也成为了 等基于算法空间复杂度的考虑提出了Bitk “十三五”期间的重点发展项目。 means算法；王习特等提出了BOD(BDSP-based 离群检测也是大数据战略中举足轻重的核心 outlier detection)分布式离群点检测算法解决了传 技术，在大数据技术发展日新月异之际，包括离 统的集中式算法处理效率受限的问题；陆海青等四 群检测在内，数据挖掘中聚类、分类等技术也随 提出的图像分割算法需根据图像噪声的强度适当 之不断地进步与发展。离群检测的目的在于检测 地选取邻域窗口大小，并根据邻域窗口中各像素 出数据集中那些被怀疑由异常机制产生的奇异数 的灰度差异，利用指数函数进一步控制邻域像素 据，广泛应用于欺诈检测四、异常检测、图像检 的影响权重，实现像素灰度的自适应加权，从而 测)、医学分析、信号异常检测等，并取得了众 提高像素灰度计算的准确性；赵冠哲等)提出的 多令人满意的结果。 异常检测方法针对移动数据中历史位置和好友圈 然而迄今为止，对离群的定义没有一个统一 信息进行高效的检测，并在检测方法中探讨了针 的认识，因离群定义的不同，离群检测算法的检 对不同情况时邻域参数的选择策略；张美琴等 测结果也会有所不同。本文将同时考虑全局离群 提出了一种基于加权聚类集成的标签传播算法 点和局部离群点，提出了基于加权自然邻居邻域 该算法利用逆邻居的思想完成了计算基聚类集， 图的离群检测算法(weighted natural neighborhood 进而利用基聚类集的加权相似性矩阵得到社区划 graph outlier detection algorithm,WNaNG)。该算法 分结果。 利用加权自然邻居邻域图计算局部自然邻居离群 上述算法在各自的应用领域中均取得了令人 度，找出离群度最高的n个离群点，而无需人为地 满意的效果，进一步推动了相关技术的发展，却 预设邻域参数k。在此基础上，本算法可以利用 也同时凸显出了另一个亟待解决的问题一邻域参 离群度的离散图辅助挖掘出合理的离群点，或利 数对算法效率的影响。大多数基于距离和基于密 用长尾理论直接根据离群度的分布找到合理的离 度的离群检测算法的核心都架构于k最近邻居思 群点区间，进而去除参数n,在无需邻域参数k的 想，因此邻域参数的选择也就是k值的设置。 基础上将算法完善为完全无参数的离群检测算法。 k值较大会导致短路，使得算法在离群点检测中 1传统离群检测算法 错误地将部分局部离群点归到正常点的范围中， 而k值较小则会导致数据簇的不完整，将边缘点 为了解决局部离群点的问题，基于密度的离 与稀疏点错误地归为局部离群点。更为困难的 群检测算法被陆续提出（例如LOF算法）。与距 是，选择一个恰当具有非普适性的k值，在一个数 离度量不同的是，基于密度的离群检测算法通过 据集中合适的k值通常在其他数据集中都会成为 定义各种不同的局部离群度来检测局部离群点。 一个不恰当的选择。解决邻域参数的选取问题出 局部离群度往往能够准确地反映出数据点与其周 现了两种思考的方向：探寻具有普适性的邻域参 围点密度特性上的差异，进而可以通过局部离群 数选择方法，或降低邻域参数的敏感性。 度的大小直观地找到离群点。这种方法在面对局 Ha等利用不稳定因子提出了一种新的对 部离群点时，往往能够取得更好的检测效果。 参数不敏感的离群检测算法INS(instability 近年来，随着数据挖掘研究领域的不断深入， factor))。NS改善了KNN算法中离群检测算法对 针对不同的应用领域，研究人员提出了大量的改 参数敏感的问题，使得离群检测的准确率能够在 进算法。Kim等1利用k-d树和近似k-最近邻居 较大的范围内不会随着参数的改变而产生很大的 方法提出了一种高效的离群检测算法；Campello 变化，且可以检测出数据集中的全局和局部离群 等)则提出了一种基于层次密度的数据挖掘算 点。但是NS算法对参数的不敏感性牺牲了一部 法，该算法提高了传统的基于密度的聚类效果， 分离群检测的准确率，即NS的离群检测结果趋 并通过计算得到层次化的聚类结果进行聚类、离 于稳定时检测准确率往往低于邻域参数选择合理 群检测和数据可视化等多项任务。苟和平等利 时的其他算法。而且NS算法很难同时检测出局 DBSCAN(density-based spatial clustering of ap- 部离群点和全局离群点，检测局部离群点时需要 plications with noise)算法对样本进行去噪和裁剪 调整不稳定因子的设定。 提出了KNN(k-nearest neighbor)算法的改进算法； 通过以上分析可以得知，现有的离群检测算 周芳芳等以体数据的标量值与梯度模直方图的 法各自有各自的优势。但是，无论是基于距离的 密度分布为基础对传统算法进行了改进：周国兵 还是基于密度的算法都存在一个参数k值的设置应用推进了人们的生活中，大数据研究也成为了 “十三五”期间的重点发展项目。 离群检测也是大数据战略中举足轻重的核心 技术，在大数据技术发展日新月异之际，包括离 群检测在内，数据挖掘中聚类、分类等技术也随 之不断地进步与发展。离群检测的目的在于检测 出数据集中那些被怀疑由异常机制产生的奇异数 据，广泛应用于欺诈检测[1] 、异常检测[2] 、图像检 测 [3] 、医学分析[4] 、信号异常检测[5] 等，并取得了众 多令人满意的结果。 然而迄今为止，对离群的定义没有一个统一 的认识，因离群定义的不同，离群检测算法的检 测结果也会有所不同。本文将同时考虑全局离群 点和局部离群点，提出了基于加权自然邻居邻域 图的离群检测算法 (weighted natural neighborhood graph outlier detection algorithm，WNaNG)。该算法 利用加权自然邻居邻域图计算局部自然邻居离群 度，找出离群度最高的 n 个离群点，而无需人为地 预设邻域参数 k。在此基础上，本算法可以利用 离群度的离散图辅助挖掘出合理的离群点，或利 用长尾理论直接根据离群度的分布找到合理的离 群点区间，进而去除参数 n，在无需邻域参数 k 的 基础上将算法完善为完全无参数的离群检测算法。 1 传统离群检测算法 为了解决局部离群点的问题，基于密度的离 群检测算法被陆续提出 (例如 LOF 算法)。与距 离度量不同的是，基于密度的离群检测算法通过 定义各种不同的局部离群度来检测局部离群点。 局部离群度往往能够准确地反映出数据点与其周 围点密度特性上的差异，进而可以通过局部离群 度的大小直观地找到离群点。这种方法在面对局 部离群点时，往往能够取得更好的检测效果。 近年来，随着数据挖掘研究领域的不断深入， 针对不同的应用领域，研究人员提出了大量的改 进算法。Kim 等 [6] 利用 k-d 树和近似 k-最近邻居 方法提出了一种高效的离群检测算法；Campello 等 [7] 则提出了一种基于层次密度的数据挖掘算 法，该算法提高了传统的基于密度的聚类效果， 并通过计算得到层次化的聚类结果进行聚类、离 群检测和数据可视化等多项任务。苟和平等[8] 利 用 DBSCAN(density-based spatial clustering of ap￾plications with noise) 算法对样本进行去噪和裁剪 提出了 KNN(k-nearest neighbor) 算法的改进算法； 周芳芳等[9] 以体数据的标量值与梯度模直方图的 密度分布为基础对传统算法进行了改进；周国兵 等 [10] 基于算法空间复杂度的考虑提出了 Bit k￾means 算法；王习特等[11]提出了 BOD(BDSP-based outlier detection) 分布式离群点检测算法解决了传 统的集中式算法处理效率受限的问题；陆海青等[12] 提出的图像分割算法需根据图像噪声的强度适当 地选取邻域窗口大小，并根据邻域窗口中各像素 的灰度差异，利用指数函数进一步控制邻域像素 的影响权重，实现像素灰度的自适应加权，从而 提高像素灰度计算的准确性；赵冠哲等[13] 提出的 异常检测方法针对移动数据中历史位置和好友圈 信息进行高效的检测，并在检测方法中探讨了针 对不同情况时邻域参数的选择策略；张美琴等[14] 提出了一种基于加权聚类集成的标签传播算法， 该算法利用逆邻居的思想完成了计算基聚类集， 进而利用基聚类集的加权相似性矩阵得到社区划 分结果。 上述算法在各自的应用领域中均取得了令人 满意的效果，进一步推动了相关技术的发展，却 也同时凸显出了另一个亟待解决的问题——邻域参 数对算法效率的影响。大多数基于距离和基于密 度的离群检测算法的核心都架构于 k-最近邻居思 想，因此邻域参数的选择也就是 k 值的设置。 k 值较大会导致短路，使得算法在离群点检测中 错误地将部分局部离群点归到正常点的范围中， 而 k 值较小则会导致数据簇的不完整，将边缘点 与稀疏点错误地归为局部离群点。更为困难的 是，选择一个恰当具有非普适性的 k 值，在一个数 据集中合适的 k 值通常在其他数据集中都会成为 一个不恰当的选择。解决邻域参数的选取问题出 现了两种思考的方向：探寻具有普适性的邻域参 数选择方法，或降低邻域参数的敏感性。 Ha 等 [15] 利用不稳定因子提出了一种新的对 参数不敏感的离群检测算 法 INS(instability factor)。INS 改善了 KNN 算法中离群检测算法对 参数敏感的问题，使得离群检测的准确率能够在 较大的范围内不会随着参数的改变而产生很大的 变化，且可以检测出数据集中的全局和局部离群 点。但是 INS 算法对参数的不敏感性牺牲了一部 分离群检测的准确率，即 INS 的离群检测结果趋 于稳定时检测准确率往往低于邻域参数选择合理 时的其他算法。而且 INS 算法很难同时检测出局 部离群点和全局离群点，检测局部离群点时需要 调整不稳定因子的设定。 通过以上分析可以得知，现有的离群检测算 法各自有各自的优势。但是，无论是基于距离的 还是基于密度的算法都存在一个参数 k 值的设置 第 5 期 冯骥，等：基于自然邻居邻域图的无参数离群检测算法 ·999·