第14卷第5期 智能系统学报 Vol.14 No.5 2019年9月 CAAI Transactions on Intelligent Systems Sep.2019 D0:10.11992/tis.201809032 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20181229.1113.002.html 基于自然邻居邻域图的无参数离群检测算法 冯骥，冉瑞生，魏延 (重庆师范大学计算机与信息科学学院，重庆401331) 摘要：数据挖掘领域，基于最近邻居思想的离群检测算法在面对复杂数据时，很难在没有足够先验知识条件 下进行适当的参数选择。为了解决这个问题，本文在自然邻居方法的基础上，提出一种利用加权自然邻居邻域 图进行离群检测的算法。该算法在整个过程不需要人为设置参数，并且能在不同分布特征的数据中准确找到 数据集中的全局离群点和局部离群点。人工数据集和真实数据的离群检测结果均证明，本算法能够取得和有 参数的算法中最优参数相近的效果，算法检测结果远好于对参数敏感算法的大部分情况，且更优于对参数不敏 感的算法，具有更强的普适性和实用性。 关键词：无参数：自适应：最近邻居；加权图；离群检测；离群因子；全局离群点：局部离群点 中图分类号：TP311 文献标志码：A 文章编号：1673-4785(2019)05-0998-09 中文引用格式：冯骥，冉瑞生，魏延.基于自然邻居邻域图的无参数离群检测算法J.智能系统学报，2019,14(5)：998-1006 英文引用格式：FENG Ji,RAN Ruisheng,WEI Yan.A parameter-free outlier detection algorithm based on natural neighborhood graph[J.CAAI transactions on intelligent systems,2019,14(5):998-1006. A parameter-free outlier detection algorithm based on natural neighborhood graph FENG Ji,RAN Ruisheng,WEI Yan (College of Computer and Information Science,Chongqing Normal University,Chongqing 401331,China) Abstract:This study aims to deal with the practical shortages of nearest-neighbor-based data mining techniques,partic- ularly outlier detection.In particular,when data sets have arbitrarily shaped clusters and varying density,determining the appropriate parameters without a priori knowledge becomes difficult.To address this issue,on the basis of the natur- al neighbor method,which can better reflect the relationship between elements in a data set than the k-nearest neighbor method,we present a graph called the weighted natural neighborhood graph for outlier detection.The weighted natural neighborhood graph does not need to set parameters artificially in the entire process and can identify global and local outliers in the data set with different distribution characteristics.The outlier detection results of artificial dataset and real data prove that the algorithm can obtain an effect similar to that of the optimal parameter in the algorithm with paramet- ers.The algorithm detection result is far better than that of most parameter-sensitive algorithms and is much better than that of the parameter-insensitive algorithm,which has stronger universality and more practicality. Keywords:parameter-free;adaptive neighbor,nearest neighbor;weighted graph;outlier detection;outlier factor,global outlier;local outlier 随着大数据技术和数据密集型科学的发展， 数据已经渗透到各个行业和业务功能中，成为了 收稿日期：2018-09-16.网络出版日期：2019-01-04 生产的一个重要因素。越来越多的国家、政府、 基金项目：教育部人文社会科学研究项目(18X灯C880002:重庆 行业、企业等机构已经意识到大数据正在成为组 市教委科技项目(KJQN201800539):重庆市自然科学 基金项日(cstc2013jcjA40049):重庆师范大学基金 织最重要的资产，数据分析能力也已经成为组织 项目(17XLB003). 通信作者：冯骥.E-mail:jifeng@cqnu.edu.cn, 的核心竞争力。目前，国家、政府已经把大数据
DOI: 10.11992/tis.201809032 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20181229.1113.002.html 基于自然邻居邻域图的无参数离群检测算法 冯骥，冉瑞生，魏延 （重庆师范大学 计算机与信息科学学院，重庆 401331） 摘 要：数据挖掘领域，基于最近邻居思想的离群检测算法在面对复杂数据时，很难在没有足够先验知识条件 下进行适当的参数选择。为了解决这个问题，本文在自然邻居方法的基础上，提出一种利用加权自然邻居邻域 图进行离群检测的算法。该算法在整个过程不需要人为设置参数，并且能在不同分布特征的数据中准确找到 数据集中的全局离群点和局部离群点。人工数据集和真实数据的离群检测结果均证明，本算法能够取得和有 参数的算法中最优参数相近的效果，算法检测结果远好于对参数敏感算法的大部分情况，且更优于对参数不敏 感的算法，具有更强的普适性和实用性。 关键词：无参数；自适应；最近邻居；加权图；离群检测；离群因子；全局离群点；局部离群点 中图分类号：TP311 文献标志码：A 文章编号：1673−4785(2019)05−0998−09 中文引用格式：冯骥, 冉瑞生, 魏延. 基于自然邻居邻域图的无参数离群检测算法 [J]. 智能系统学报, 2019, 14(5): 998–1006. 英文引用格式：FENG Ji, RAN Ruisheng, WEI Yan. A parameter-free outlier detection algorithm based on natural neighborhood graph[J]. CAAI transactions on intelligent systems, 2019, 14(5): 998–1006. A parameter-free outlier detection algorithm based on natural neighborhood graph FENG Ji，RAN Ruisheng，WEI Yan (College of Computer and Information Science, Chongqing Normal University, Chongqing 401331, China) Abstract: This study aims to deal with the practical shortages of nearest-neighbor-based data mining techniques, particularly outlier detection. In particular, when data sets have arbitrarily shaped clusters and varying density, determining the appropriate parameters without a priori knowledge becomes difficult. To address this issue, on the basis of the natural neighbor method, which can better reflect the relationship between elements in a data set than the k-nearest neighbor method, we present a graph called the weighted natural neighborhood graph for outlier detection. The weighted natural neighborhood graph does not need to set parameters artificially in the entire process and can identify global and local outliers in the data set with different distribution characteristics. The outlier detection results of artificial dataset and real data prove that the algorithm can obtain an effect similar to that of the optimal parameter in the algorithm with parameters. The algorithm detection result is far better than that of most parameter-sensitive algorithms and is much better than that of the parameter-insensitive algorithm, which has stronger universality and more practicality. Keywords: parameter-free; adaptive neighbor; nearest neighbor; weighted graph; outlier detection; outlier factor; global outlier; local outlier 随着大数据技术和数据密集型科学的发展， 数据已经渗透到各个行业和业务功能中，成为了 生产的一个重要因素。越来越多的国家、政府、 行业、企业等机构已经意识到大数据正在成为组 织最重要的资产，数据分析能力也已经成为组织 的核心竞争力。目前，国家、政府已经把大数据 收稿日期：2018−09−16. 网络出版日期：2019−01−04. 基金项目：教育部人文社会科学研究项目 (18XJC880002)；重庆 市教委科技项目 (KJQN201800539)；重庆市自然科学 基金项目 (cstc2013jcyjA40049)；重庆师范大学基金 项目 (17XLB003). 通信作者：冯骥. E-mail：jifeng@cqnu.edu.cn. 第 14 卷第 5 期 智 能 系 统 学 报 Vol.14 No.5 2019 年 9 月 CAAI Transactions on Intelligent Systems Sep. 2019
第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 applications with noise) 算法对样本进行去噪和裁剪 提出了 KNN(k-nearest neighbor) 算法的改进算法； 周芳芳等[9] 以体数据的标量值与梯度模直方图的 密度分布为基础对传统算法进行了改进；周国兵 等 [10] 基于算法空间复杂度的考虑提出了 Bit kmeans 算法；王习特等[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·
·1000· 智能系统学报 第14卷 问题，那就是如何选择一个合适的邻居个数 outlier factor)。数据点p的自然邻居离群因子 k值。为了解决这一问题，本文选择结合自然邻 f(p)满足： 居的思想提出适用于离群检测的普适性邻域参数 maxw(p,q)minw(p,q) 选择方法。基于自然邻居形成过程无参的特性， f(p)=s gEO dgree(p) 本文提出了一种离群检测算法，该算法能够在已 其中，集合Q={qle=(p,q)∈E},即Q为数据点 知离群点参数n的情况下无需邻域参数k找到数 p的所有自然邻居所构成的数据子集。 据集中的离群点。最后，算法探讨了完全无参数 在完善了加权自然邻居邻域图和自然邻居离 化的离群检测算法，在挖掘出正确的离群点的同 群因子的定义后，本文提出基于加权自然邻居邻 时去除邻域参数k和离群点数量参数n。 域图的离群检测算法，算法流程如图1所示。 2基于自然邻居思想的离群检测算法 算法开始 2.1自然邻居概述 获取目标数据集 自然邻居思想是笔者及课题组成员提出的一 自然邻居搜索 种无尺度的概念，与传统的KNN方法相比，该思 想能够在无需邻域参数k的情况下构建出合理的 输出全局离群点 邻居关系，为后续的数据挖掘方法提供分析基 础。该思想包含以下几个核心概念。 局部离群点挖据 定义1搜索稳定状态(search stable state) 输出局部离群点 (Hx)(xr∈NA(x≠x) →(x,∈KNN,(x》A(x∈KNN,(x) 算法结束 定义2自然邻居(natural neighbor) 图1基于加权自然邻居邻域图的离群检测算法流程图 xeNN(x)台(x∈KNN(x)A(x,eKNN(x) Fig.1 Flowchart of the WNaNG outlier detection algorithm 定义3自然邻居特征值(natural neighbor ei-. 算法1基于加权自然邻居领域图的离群 genvalue) 检测 1兰r,eN{lNx)3x;r∈N)A(x+x) 输入目标数据集X,离群点总数： →(x∈KNN(x》A(x∈KNN,()l 输出加权自然邻居邻域图G,局部离群点 定义4自然邻居邻域图(natural neighbor- 个数n,全局离群点。 hood graph) 1)初始化k=0,并创建数据集X对应的k-d e(v,v)∈E台x∈NNx) 树T: 在定义1~4中，数据集X={x1,x2,,xn}, 2)令=k+1,并利用k-d树T找到数据集中每 KNN,(x)代表点x,的r邻域，即前r个邻居构成的 个点的k最近邻居： 集合，1是自然邻居特征值，NN(x)代表点x,的自 3)分析当前的邻居关系，将互为k最近邻居 然领域。自然邻居概念的定义在提出时就对该概 的两点构成一条边，并记录当前的k作为该边的 念的扩展性进行了展望分析，而本文正是在此基 权值； 本概念基础上，提出并构造加权自然邻居邻域图， 4)重复执行步骤2)~3)，直到数据集X中所有 并以此为基础完成无参数的离群点的检测算法。 点都至少具有一个邻居，或连续r次未增加新的 22基于加权自然邻居邻域图的离群检测算法 边，其中r=Vk-r; 定义5加权自然邻居邻域图(weighted nat- 5)将加权自然邻居邻域图中没有边的点标记 ural neighborhood graph)。加权自然邻居邻域图反 为全局离群点，并计算出剩余的局部离群点个数n: 映了自然稳定状态时数据集中数据点之间的邻居 6)根据当前所有已知边的信息构造加权自然 关系，每一条加权边反映了对应的两个数据点首 邻居邻域图。 次互为邻居关系时的最近邻居搜索状态。加权自 自然邻居搜索算法通过自然邻居搜索过程和 然邻居邻域图权值的形式化描述为 自然邻居邻域图的简单分析，找到了全局离群点， w(x,x）=min(r){rl&eKNN,(x》A(c∈KNN(x)l 同时给出了剩余数据的加权自然邻居邻域图。算 权值的取值范围为[1，]。 法得到的加权自然邻居邻域图将会被用于局部离 定义6自然邻居离群因子(natural neighbor 群点挖掘过程，找到数据集中最终的局部离群点
问题，那就是如何选择一个合适的邻居个 数 k 值。为了解决这一问题，本文选择结合自然邻 居的思想提出适用于离群检测的普适性邻域参数 选择方法。基于自然邻居形成过程无参的特性， 本文提出了一种离群检测算法，该算法能够在已 知离群点参数 n 的情况下无需邻域参数 k 找到数 据集中的离群点。最后，算法探讨了完全无参数 化的离群检测算法，在挖掘出正确的离群点的同 时去除邻域参数 k 和离群点数量参数 n。 2 基于自然邻居思想的离群检测算法 2.1 自然邻居概述 自然邻居思想是笔者及课题组成员提出的一 种无尺度的概念，与传统的 KNN 方法相比，该思 想能够在无需邻域参数 k 的情况下构建出合理的 邻居关系，为后续的数据挖掘方法提供分析基 础 [16]。该思想包含以下几个核心概念。 定义 1 搜索稳定状态 (search stable state) (∀xi)(∃xj)(r ∈ N)∧(xi , xj) → (xi ∈ KNNr(xj))∧(xj ∈ KNNr(xi)) 定义 2 自然邻居 (natural neighbor) xi ∈ NN(xj) ⇔ (xi ∈ KNNλ(xj))∧(xj ∈ KNNλ(xi)) 定义 3 自然邻居特征值 (natural neighbor eigenvalue) λ ∆ = rr∈N{r|(∀xi)(∃xj)(r ∈ N)∧(xi , xj) → (xi ∈ KNNr(xj))∧(xj ∈ KNNr(xi))} 定义 4 自然邻居邻域图 (natural neighborhood graph) e(vi , vj) ∈ E ⇔ xj ∈ NN(xi) 在定义 1~4 中，数据集 X={x 1 , x 2 , ···, x n }， KNNr (xi ) 代表点 xi 的 r 邻域，即前 r 个邻居构成的 集合，λ 是自然邻居特征值，NN(xi ) 代表点 xi 的自 然领域。自然邻居概念的定义在提出时就对该概 念的扩展性进行了展望分析，而本文正是在此基 本概念基础上，提出并构造加权自然邻居邻域图， 并以此为基础完成无参数的离群点的检测算法。 2.2 基于加权自然邻居邻域图的离群检测算法 定义 5 加权自然邻居邻域图 (weighted natural neighborhood graph)。加权自然邻居邻域图反 映了自然稳定状态时数据集中数据点之间的邻居 关系，每一条加权边反映了对应的两个数据点首 次互为邻居关系时的最近邻居搜索状态。加权自 然邻居邻域图权值的形式化描述为 w(xi , xj) = min(r){r|(xi ∈ KNNr(xj))∧(xj ∈ KNNr(xi))} 权值的取值范围为 [1，λ]。 定义 6 自然邻居离群因子 (natural neighbor outlier factor)。数据点 p 的自然邻居离群因子 f (p) 满足： f(p) = max q∈Q w(p,q)min q∈Q w(p,q) dgree(p) 其中，集合 Q ={q|e =(p,q)∈ E}，即 Q 为数据点 p 的所有自然邻居所构成的数据子集。 在完善了加权自然邻居邻域图和自然邻居离 群因子的定义后，本文提出基于加权自然邻居邻 域图的离群检测算法，算法流程如图 1 所示。 算法开始 自然邻居搜索 获取目标数据集 输出全局离群点 局部离群点挖掘 输出局部离群点 算法结束 图 1 基于加权自然邻居邻域图的离群检测算法流程图 Fig. 1 Flowchart of the WNaNG outlier detection algorithm 算法 1 基于加权自然邻居领域图的离群 检测 输入 目标数据集 X，离群点总数 n； 输出 加权自然邻居邻域图 G，局部离群点 个数 nl，全局离群点。 1) 初始化 k=0，并创建数据集 X 对应的 k-d 树 T； 2) 令 k=k+1，并利用 k-d 树 T 找到数据集中每 个点的 k 最近邻居； 3) 分析当前的邻居关系，将互为 k 最近邻居 的两点构成一条边，并记录当前的 k 作为该边的 权值； r = √ k−r 4) 重复执行步骤 2)~3)，直到数据集 X 中所有 点都至少具有一个邻居，或连续 r 次未增加新的 边，其中 ； 5) 将加权自然邻居邻域图中没有边的点标记 为全局离群点，并计算出剩余的局部离群点个数 nl； 6) 根据当前所有已知边的信息构造加权自然 邻居邻域图。 自然邻居搜索算法通过自然邻居搜索过程和 自然邻居邻域图的简单分析，找到了全局离群点， 同时给出了剩余数据的加权自然邻居邻域图。算 法得到的加权自然邻居邻域图将会被用于局部离 群点挖掘过程，找到数据集中最终的局部离群点。 ·1000· 智 能 系 统 学 报 第 14 卷
第5期 冯骥，等：基于自然邻居邻域图的无参数离群检测算法 ·1001· 算法2局部离群点挖掘算法 3 输入加权自然邻居邻域图G=(V,E),局部 离群点个数n: 输出局部离群点。 1)对邻域图进行遍历，找到每个点的所有加 7 权边； 2)根据定义6计算所有点的自然离群因子f 50 100 150180 离群点的下标 3)对所有点的自然离群因子进行降序排序， 图3数据集中各个数据点对应的自然邻居离群因子 前m,个点即为局部离群点。 Fig.3 Natural neighbor outlier factor of each data point 局部离群点挖掘算法首先计算加权自然邻居 另外，若希望离群检测摆脱人为的参数设置 邻域图中点的自然邻居离群因子，其次依照离群 和图像化辅助决策，在此选择对自然邻居离群因 因子的大小得到局部离群点。 子进行降序排序，离群度的分布形态与长尾分布 2.3自然邻居离群因子离散图分析 具有极高的相似度，因此可以尝试利用长尾分布 在上述算法的局部离群点挖掘算法中，剩余 的相关理论进行自然邻居离群因子的阈值确定， 离群点依然需要人为设置，如算法中则是用离群 实现无需人为干涉、无需邻域参数k和离群点数 点数量参数n减去已经找到的全局离群点个数。 量参数n的自适应离群检测算法。 为了进一步完成无参数的离群点检测算法，本文 2.4算法复杂度分析 尝试通过对自然邻居离群因子的离散图进行分 本算法的总体时间复杂度为O(NIg N)。其中 析，去除离群点数量参数n,使得本文提出的离群 自然邻居搜索算法的时间复杂度为OW1gN),局 检测算法具有更强的自适应性。因此，本文有针 部离群点挖掘算法的时间复杂度为OW。 对性地构造了一个具有多个局部离群点的人工数 首先，自然邻居搜索算法在自然邻居查找和 据集，并针对其局部离群点的情况和自然邻居离 自然稳定状态的获取阶段时间复杂度为OWg)。 其次，全局集群点和离群簇的挖掘均可以在邻居 群因子的值进行分析。 搜索的过程中完成，且并不会在数量级级别增加 在图2中可以看到，数据点1、2、3、4和162、 算法的时间复杂度。因此当前阶段的时间复杂度 163、164、165为局部离群点。从图3中可以看出，图2 为O(NIg N)。 中提到的离群点所对应的局部离群因子均远远高 在算法的第二阶段，局部离群点挖掘算法的 于普通数据点的局部离群因子，因此如果以自然 时间复杂度要低于上一阶段。首先，自然邻居邻 邻居离群因子离散图作为辅助决策，可以直观地 域图中的任意点最多具有1条边，最少具有一条 通过其数据分布确定自然邻居离群因子的阈值， 边。因此，自然邻居离群因子阶段的时间复杂度 并以此阈值作为局部离群点的判定标准，达到去 为OW),其中1为一个较小的整数，因此该阶段 除离群点数量参数n的目的。这种结合图形化展 实际复杂度为OW)。之后的聚类分析具体操作 示的离群点检测方法使得离群点的度量和检测能 时只需要对上一阶段中的数据簇结果进行简单的 够进行更为直观地展示。 修改，而该修改操作的时间复杂度为O(W)。 3实验结果 163 3.1人工数据集实验 162 164 人工数据集的实验分为两部分。1)着重于展 示本算法自适应性的优势，即与其他算法选择多 165 个参数时能够获得的最好检测结果相比，本算法 能够获得与之相似甚至于更好的结果，且无需选 择邻域参数。在这一部分中，同一数据集中多个 图2自然邻居邻域图和局部离群点示意 算法均选取相同的离群点数量n。2)分讨论算法 Fig.2 Natural neighbor graph and local outliers 在无需离群点数量参数n的情况下利用自然邻居
算法 2 局部离群点挖掘算法 输入 加权自然邻居邻域图 G=(V, E)，局部 离群点个数 nl； 输出 局部离群点。 1) 对邻域图进行遍历，找到每个点的所有加 权边； 2) 根据定义 6 计算所有点的自然离群因子 f； 3) 对所有点的自然离群因子进行降序排序， 前 nl 个点即为局部离群点。 局部离群点挖掘算法首先计算加权自然邻居 邻域图中点的自然邻居离群因子，其次依照离群 因子的大小得到局部离群点。 2.3 自然邻居离群因子离散图分析 在上述算法的局部离群点挖掘算法中，剩余 离群点依然需要人为设置，如算法中则是用离群 点数量参数 n 减去已经找到的全局离群点个数。 为了进一步完成无参数的离群点检测算法，本文 尝试通过对自然邻居离群因子的离散图进行分 析，去除离群点数量参数 n，使得本文提出的离群 检测算法具有更强的自适应性。因此，本文有针 对性地构造了一个具有多个局部离群点的人工数 据集，并针对其局部离群点的情况和自然邻居离 群因子的值进行分析。 在图 2 中可以看到，数据点 1、2、3、4 和 162、 163、164、165 为局部离群点。从图 3 中可以看出，图 2 中提到的离群点所对应的局部离群因子均远远高 于普通数据点的局部离群因子，因此如果以自然 邻居离群因子离散图作为辅助决策，可以直观地 通过其数据分布确定自然邻居离群因子的阈值， 并以此阈值作为局部离群点的判定标准，达到去 除离群点数量参数 n 的目的。这种结合图形化展 示的离群点检测方法使得离群点的度量和检测能 够进行更为直观地展示。 4 1 2 3 163 162 164 165 图 2 自然邻居邻域图和局部离群点示意 Fig. 2 Natural neighbor graph and local outliers 0 50 100 150 180 离群点的下标 2 7 12 17 22 自然离群因子 f 图 3 数据集中各个数据点对应的自然邻居离群因子 Fig. 3 Natural neighbor outlier factor of each data point 另外，若希望离群检测摆脱人为的参数设置 和图像化辅助决策，在此选择对自然邻居离群因 子进行降序排序，离群度的分布形态与长尾分布 具有极高的相似度，因此可以尝试利用长尾分布 的相关理论进行自然邻居离群因子的阈值确定， 实现无需人为干涉、无需邻域参数 k 和离群点数 量参数 n 的自适应离群检测算法。 2.4 算法复杂度分析 O(N lgN) O(N lgN) O(N) 本算法的总体时间复杂度为 。其中 自然邻居搜索算法的时间复杂度为 ，局 部离群点挖掘算法的时间复杂度为 。 O(N lgN) O(N lgN) 首先，自然邻居搜索算法在自然邻居查找和 自然稳定状态的获取阶段时间复杂度为 。 其次，全局集群点和离群簇的挖掘均可以在邻居 搜索的过程中完成，且并不会在数量级级别增加 算法的时间复杂度。因此当前阶段的时间复杂度 为 。 O(λN) O(N) O(N) 在算法的第二阶段，局部离群点挖掘算法的 时间复杂度要低于上一阶段。首先，自然邻居邻 域图中的任意点最多具有 λ 条边，最少具有一条 边。因此，自然邻居离群因子阶段的时间复杂度 为 ，其中 λ 为一个较小的整数，因此该阶段 实际复杂度为 。之后的聚类分析具体操作 时只需要对上一阶段中的数据簇结果进行简单的 修改，而该修改操作的时间复杂度为 。 3 实验结果 3.1 人工数据集实验 人工数据集的实验分为两部分。1) 着重于展 示本算法自适应性的优势，即与其他算法选择多 个参数时能够获得的最好检测结果相比，本算法 能够获得与之相似甚至于更好的结果，且无需选 择邻域参数。在这一部分中，同一数据集中多个 算法均选取相同的离群点数量 n。2) 分讨论算法 在无需离群点数量参数 n 的情况下利用自然邻居 第 5 期 冯骥，等：基于自然邻居邻域图的无参数离群检测算法 ·1001·
·1002· 智能系统学报 第14卷 离群因子查找局部离群点的算法结果。 的所有子图中，WNaNG算法的准确率是确定的， 首先进行基于邻域参数k的实验展示。本实 即对固定的数据集，WNaNG算法只有一个确定 验用到的人工数据集如图4所示。 的离群检测结果。为了算法对比效果的展示，WNaNG 图4中的6个数据集均包含了多个肉眼可见 算法的准确率采用直线进行标示。 的离群点，其中既有局部离群点，又有全局离群 点，且这6个数据集具有不同的数据分布特性，因 鲫 而能更准确地反映出邻域参数对算法的影响，以 及本算法的自适应性在面对数据集的多样性时的 实际表现。 (a)数据集1 (b)数据集2 本文将基于加权自然邻居邻域图的数据挖掘 算法与4种离群检测算法相对比，检验本算法与 当前离群检测算法之间的性能差异，被选取的对 比算法为KNN、LOF、NFLO和NS。 (c)数据集3 (d)数据集4 图5用曲线图展示了5种不同的离群检测算 法在6个数据集中的检测精确率。为了更好地反 映准确率随着邻域参数取值的变化而上下波动的 详细情况，这里将x轴设定为邻域参数k的不同 取值，y轴则是各个算法在选取每一个k值时对 (e)数据集5 ()数据集6 应的离群检测准确率。本算法克服了传统的邻域 图4包含离群点的6个人工数据集 选择问题，即无需在算法中设置参数k,则在图5 Fig.4 Six synthetic data sets of the outliers 1.0 1.0 。 0.8 0.8 部0.6 6 --LOF -INFLO 0.4 -05 INFLO KNN 02 -INS 02 WNaNG WNaNG 40 80 101 40 80 101 k值 k值 (a)数据集1检测结果 (b)数据集2检测结果 1.0 1.0 0.8 0.8 0.6 =0.4 --LOF 。-NFLO 是04 LOF INFLO 0.2 KNN KNN -INS 0.2 --INS WNaNG WNaNG 40 80 101 40 80101 k值 k值 (©)数据集3检测结果 (d)数据集4检测结果 1.0 1.0 0.8 0.8 0.6 腰0.6 0.4 -LOF 4 。-NFLO 02 --KNN INS 0.2 -WNaNG WNaNG 101 40 80 101 k值 k值 (e)数据集5检测结果 ()数据集6检测结果 图55种离群检测算法在取不同k值时离群检测准确率对比 Fig.5 Outlier detection accuracies of five detection methods over a range of k values
离群因子查找局部离群点的算法结果。 首先进行基于邻域参数 k 的实验展示。本实 验用到的人工数据集如图 4 所示。 图 4 中的 6 个数据集均包含了多个肉眼可见 的离群点，其中既有局部离群点，又有全局离群 点，且这 6 个数据集具有不同的数据分布特性，因 而能更准确地反映出邻域参数对算法的影响，以 及本算法的自适应性在面对数据集的多样性时的 实际表现。 本文将基于加权自然邻居邻域图的数据挖掘 算法与 4 种离群检测算法相对比，检验本算法与 当前离群检测算法之间的性能差异，被选取的对 比算法为 KNN、LOF、INFLO 和 INS。 图 5 用曲线图展示了 5 种不同的离群检测算 法在 6 个数据集中的检测精确率。为了更好地反 映准确率随着邻域参数取值的变化而上下波动的 详细情况，这里将 x 轴设定为邻域参数 k 的不同 取值，y 轴则是各个算法在选取每一个 k 值时对 应的离群检测准确率。本算法克服了传统的邻域 选择问题，即无需在算法中设置参数 k，则在图 5 的所有子图中，WNaNG 算法的准确率是确定的， 即对固定的数据集，WNaNG 算法只有一个确定 的离群检测结果。为了算法对比效果的展示，WNaNG 算法的准确率采用直线进行标示。 (a) 数据集 1 (b) 数据集 2 (c) 数据集 3 (d) 数据集 4 (e) 数据集 5 (f) 数据集 6 图 4 包含离群点的 6 个人工数据集 Fig. 4 Six synthetic data sets of the outliers 40 80 101 k 值 0.4 0.8 0.6 0.2 1.0 0.4 0.8 0.6 0.2 1.0 准确率 LOF INFLO KNN INS WNaNG (a) 数据集 1 检测结果 0 LOF INFLO KNN INS WNaNG 40 80 101 k 值 (b) 数据集 2 检测结果 0 LOF INFLO KNN INS WNaNG 40 80 101 k 值 准确率 0.4 0.8 0.6 0.2 1.0 准确率 0.4 0.8 0.6 0.2 1.0 准确率 0.4 0.8 0.6 0.2 1.0 准确率 0.4 0.8 0.6 0.2 1.0 准确率 (c) 数据集 3 检测结果 0 LOF INFLO KNN INS WNaNG 40 80 101 k 值 (d) 数据集 4 检测结果 0 40 80 101 k 值 (e) 数据集 5 检测结果 0 LOF INFLO KNN INS WNaNG 40 80 101 k 值 (f) 数据集 6 检测结果 0 LOF INFLO KNN INS WNaNG 图 5 5 种离群检测算法在取不同 k 值时离群检测准确率对比 Fig. 5 Outlier detection accuracies of five detection methods over a range of k values ·1002· 智 能 系 统 学 报 第 14 卷
第5期 冯骥，等：基于自然邻居邻域图的无参数离群检测算法 ·1003· 纵观所有子图，WNaNG算法的普适性高于 15 其余算法，能够在6个数据集中均取得令人满意 1.0 出 10 的结果。若对每一个算法在各个数据集中均选择 0.5 J 一个最优的参数k与本算法相比较，在数据集1 中其余5种算法的最优算法略高于本算法，而在 0 0.5 10 0 200400600 数据点的下标 其余几个数据集中，其最优值基本仅能与本算法 (a)WNaNGI (b)离群因子离散图1 取得相似的检测效果，大部分的邻域参数值所对 1.0 45 应的检测效果均与本算法有一定的差距。 0.5 30 从算法对邻域参数的适应性上看，本算法完 15 全摆脱了邻域参数的影响，并取得了令人满意的 0 0 1.0 4008001200 结果：NS算法对邻域参数的敏感度较低，因此在 数据点的下标 (c)WNaNG2 (d)离群因子离散图2 各个数据集中，其检测结果不易随着邻域参数的 1.0 27 变化产生剧烈波动：其余算法则对邻域参数较为 敏感，特别是当数据集分布不规则时，如最后两 0.5 18 个数据集中，邻域参数的选取会严重影响其算法 s出22 结果。 0.5 1.0 0 4008001200 数据点的下标 产生上述情况的原因：为了降低邻域参数对 (e)WNaNG3 ()离群因子离散图3 算法的影响，增强算法的适应性，往往会在某些 1.0 情况牺牲一部分离群检测准确率，如NS算法。 而本文提出的WNaNG算法合理地利用了自适应 09 50 的邻居特性，因而在保证了检测准确率的情况下 0.5 1.0 0 4008001200 移除了邻域参数的影响。本算法在与其余算法进 数据点的下标 (g)WNaNG4 (h)离群因子离散图4 行比较时检测结果呈现一条直线，并不是代表算 法的检测结果不会随着k值的变化而产生变化， 80 60 而是算法无需人为设置参数k。因此可以得到结 论：WNaNG算法不仅解决了邻域参数的选取问 20 题，更能在具有不同特性的数据集中取得稳定且 0.5 0 0 4008001200 数据点的下标 准确的离群检测结果。本文将进一步讨论WN (i)WNaNG5 )离群因子离散图5 aNG算法利用自然邻居离群因子查找局部离群点 图6局部离群点与自然邻居离群因子离散图 的实验结果。 Fig.6 Local outliers and NaNOF scatter 图6展示了5个不同分布特点的数据集利用 3.2真实数据集实验 自然邻居离群因子进行局部离群点检测的检测 真实数据集中本文采用的对比算法为KNN、 结果。从实验结果中可以看到，在前两个数据集 LOF、NFLO和NS算法，算法对应的两个数据集 中，自然邻居离群因子的分布相对较为均匀，对 分别为UCI网站的CANCER和RIS,采用的评价 应的数据集中局部离群点的特征也较弱；而在后 指标是离群检测的ROC曲线(receiver operating 几个数据集中，自然邻居离群因子的分布呈现较 characteristic curve),其横、纵坐标为离群点检测率 大的差异，能够通过分布图明显地划分出一个或 和离群点数目，通过积分面积验证数据集在对应 者多个自然邻居离群因子突变界限，而这种情 的k值选择中离群检测的效率。在两个人工数据 况也与实际数据分布相吻合，其数据集中的局部 集的实验结果中，基于加权自然邻居邻域图的数 离群点在分布上也呈现出多层级的特点，即不同 据挖掘算法由于不需要邻域参数，因此图中所展 范围的离群点其局部离群特征也具有较大的差 示的k为算法自适应得出的对应数据集的自然邻 异性。 居特征值，其余算法则是其对应的邻域参数k的
纵观所有子图，WNaNG 算法的普适性高于 其余算法，能够在 6 个数据集中均取得令人满意 的结果。若对每一个算法在各个数据集中均选择 一个最优的参数 k 与本算法相比较，在数据集 1 中其余 5 种算法的最优算法略高于本算法，而在 其余几个数据集中，其最优值基本仅能与本算法 取得相似的检测效果，大部分的邻域参数值所对 应的检测效果均与本算法有一定的差距。 从算法对邻域参数的适应性上看，本算法完 全摆脱了邻域参数的影响，并取得了令人满意的 结果；INS 算法对邻域参数的敏感度较低，因此在 各个数据集中，其检测结果不易随着邻域参数的 变化产生剧烈波动；其余算法则对邻域参数较为 敏感，特别是当数据集分布不规则时，如最后两 个数据集中，邻域参数的选取会严重影响其算法 结果。 产生上述情况的原因：为了降低邻域参数对 算法的影响，增强算法的适应性，往往会在某些 情况牺牲一部分离群检测准确率，如 INS 算法。 而本文提出的 WNaNG 算法合理地利用了自适应 的邻居特性，因而在保证了检测准确率的情况下 移除了邻域参数的影响。本算法在与其余算法进 行比较时检测结果呈现一条直线，并不是代表算 法的检测结果不会随着 k 值的变化而产生变化， 而是算法无需人为设置参数 k。因此可以得到结 论：WNaNG 算法不仅解决了邻域参数的选取问 题，更能在具有不同特性的数据集中取得稳定且 准确的离群检测结果。本文将进一步讨论 WNaNG 算法利用自然邻居离群因子查找局部离群点 的实验结果。 图 6 展示了 5 个不同分布特点的数据集利用 自然邻居离群因子进行局部离群点检测的检测 结果。从实验结果中可以看到，在前两个数据集 中，自然邻居离群因子的分布相对较为均匀，对 应的数据集中局部离群点的特征也较弱；而在后 几个数据集中，自然邻居离群因子的分布呈现较 大的差异，能够通过分布图明显地划分出一个或 者多个自然邻居离群因子突变界限，而这种情 况也与实际数据分布相吻合，其数据集中的局部 离群点在分布上也呈现出多层级的特点，即不同 范围的离群点其局部离群特征也具有较大的差 异性。 (a) WNaNG1 (c) WNaNG2 (e) WNaNG3 0 200 400 600 数据点的下标 5 10 15 自然离群因子f (b) 离群因子离散图 1 0 400 800 1 200 数据点的下标 15 30 45 自然离群因子f (d) 离群因子离散图 2 400 800 1 200 数据点的下标 0 9 18 27 自然离群因子 f (f) 离群因子离散图 3 400 800 1 200 数据点的下标 0 25 50 75 100 自然离群因子 f (h) 离群因子离散图 4 0 400 800 1 200 数据点的下标 20 40 60 80 自然离群因子 f (j) 离群因子离散图 5 0 0.5 1.0 0 0.5 1.0 X Y 0 0.5 1.0 0 0.5 1.0 X Y 0.5 1.0 Y (g) WNaNG4 0 0.5 1.0 X (i) WNaNG5 0 0.5 1.0 0.5 1.0 X Y 0 0.5 1.0 0 0.5 1.0 X Y 图 6 局部离群点与自然邻居离群因子离散图 Fig. 6 Local outliers and NaNOF scatter 3.2 真实数据集实验 真实数据集中本文采用的对比算法为 KNN、 LOF、INFLO 和 INS 算法，算法对应的两个数据集 分别为 UCI 网站的 CANCER 和 IRIS，采用的评价 指标是离群检测的 ROC 曲线 (receiver operating characteristic curve)，其横、纵坐标为离群点检测率 和离群点数目，通过积分面积验证数据集在对应 的 k 值选择中离群检测的效率。在两个人工数据 集的实验结果中，基于加权自然邻居邻域图的数 据挖掘算法由于不需要邻域参数，因此图中所展 示的 k 为算法自适应得出的对应数据集的自然邻 居特征值，其余算法则是其对应的邻域参数 k 的 第 5 期 冯骥，等：基于自然邻居邻域图的无参数离群检测算法 ·1003·
·1004· 智能系统学报 第14卷 取值。 到，以离群点检测命中率作为检测结果时，INS 图7中的实验结果分为顶部和底部两组，顶 和本算法的表现相对较差。这主要是由于，在 部的实验结果为算法在对应的邻域参数k值的 CANCER数据集中，部分离群点被算法归为了 范围中选取得到的最差实验结果，而底部为该 簇，继而难以被检测出来，而其他3个算法能够 范围中最好的实验结果。从当前数据集可以看 更快地随着参数n的增加而找到那部分离群点。 ←15 ←15 ←15 ←15 ←15 10 10 10 5 面积：3265 面积：3166 面积：1897.5 5 =19 =43 面积423.5厂 面积：1830 k=10 k=50 k=10 0 50100150200250 0 50100150200250 0 50100150200250 0 50100150200250 0 50100150200250 离群点数量/个 离群点数量/个 离群点数量/个 离群点数量/个 离群点数量/个 (a)Lof最差结果 b)KNN最差结果 (c)NFLO最差结果 (d)Ins最差结果 (e)NaNG最差结果 ←15 15 15 ←15 10 10 10 10 面积：1294.5 k=10 5 面积：3335.5 面积：3345 面积：2406 5 面积：1830 k=10 =10 名 k=10 k=10 50100150200250 0 50100150200250 0 50100150200250 0 50100150200250 0 50100150200250 离群点数量/个 离群点数量/个 离群点数量/个 离群点数量/个 离群点数量/个 ()Lof最优结果 (g)KNN最优结果 (h)INFLO最优结果 (i)Ins最优结果 NaNG最优结果 图7 CANCER数据集的ROC曲线下面积 Fig.7 Area under the ROC curves of CANCER 图8的布局和图7相同，也是由最差实验结 因此WNaNG算法的结果有了明显的好转。特 果和最佳实验结果组成。在RIS数据集中，因 别是当n=50时，仅本算法就能够找到所有的离 为离群点中离群簇的情况比CANCER更少， 群点。 18 18 K18 ←18 18 12 12 12 12 6 6 =13 k=10 =12 6 k=18 6 =10 0 0 0 0 0 38 6 76 38 6 8 6 38 6 离群点数量/个 离群点数量/个 离群点数量个 离群点数量/个 离群点数量/个 (a)Lof最差结果 (b)KNN最差结果 (c)INFLO最差结果 (dIns最差结果 (e)NaNG最差结果 18 18 18 18 18 m n 12 新12 12 12 新12 6 的 6 6 6 k=23 k=15 k=50 k=44厂 =10 0 0 76 38 76 38 76 38 76 38 16 离群点数量/个 离群点数量/个 离群点数量/个 离群点数量/个 离群点数量/个 (①Lof最优结果 (g)KNN最优结果 (h)INFLO最优结果 ()lns最优结果 j)NaNG最优结果 图8RIS数据集的ROC曲线下面积 Fig.8 Area under the ROC curves of IRIS
取值。 图 7 中的实验结果分为顶部和底部两组，顶 部的实验结果为算法在对应的邻域参数 k 值的 范围中选取得到的最差实验结果，而底部为该 范围中最好的实验结果。从当前数据集可以看 到，以离群点检测命中率作为检测结果时，INS 和本算法的表现相对较差。这主要是由于，在 CANCER 数据集中，部分离群点被算法归为了 簇，继而难以被检测出来，而其他 3 个算法能够 更快地随着参数 n 的增加而找到那部分离群点。 离群点数量/个 0 50 100150200250 5 10 15 正确的离群点数目/个 (a) Lof最差结果 面积:3 265 k=19 0 50 100150200250 5 10 15 正确的离群点数目/个 离群点数量/个 (f) Lof最优结果 面积:3 335.5 k=10 0 50 100150200250 5 10 15 正确的离群点数目/个 离群点数量/个 (b) KNN最差结果 面积:3 166 k=43 50 100 150 200 250 离群点数量/个 0 5 10 15 正确的离群点数目/个 (g) KNN最优结果 面积:3 345 k=10 0 50 100150200 5 10 15 正确的离群点数目/个 离群点数量/个 (c) INFLO最差结果 面积:1 897.5 k=10 50 100 150 200 离群点数量/个 0 5 10 15 正确的离群点数目/个 (h) INFLO最优结果 面积:2 406 k=10 250 250 0 50 100150200250 5 10 15 正确的离群点数目/个 离群点数量/个 (d) Ins最差结果 面积:423.5 k=50 50 100 150 200 250 离群点数量/个 0 5 10 15 正确的离群点数目/个 (i) Ins最优结果 面积:1 294.5 k=10 0 50 100150200250 5 10 15 正确的离群点数目/个 离群点数量/个 (e) NaNG最差结果 面积:1 830 k=10 50 100 150 200250 离群点数量/个 0 5 10 15 正确的离群点数目/个 (j) NaNG最优结果 面积:1 830 k=10 图 7 CANCER 数据集的 ROC 曲线下面积 Fig. 7 Area under the ROC curves of CANCER 图 8 的布局和图 7 相同，也是由最差实验结 果和最佳实验结果组成。在 IRIS 数据集中，因 为离群点中离群簇的情况 比 CANCER 更少， 因此 WNaNG 算法的结果有了明显的好转。特 别是当 n=50 时，仅本算法就能够找到所有的离 群点。 (a) Lof最差结果 (f) Lof最优结果 (b) KNN最差结果 (g) KNN最优结果 (c) INFLO最差结果 (h) INFLO最优结果 (d) Ins最差结果 (i) Ins最优结果 (e) NaNG最差结果 (j) NaNG最优结果 38 76 离群点数量/个 0 6 12 18 正确的离群点数目/个 38 76 离群点数量/个 0 6 12 18 正确的离群点数目/个 38 76 离群点数量/个 0 6 12 18 正确的离群点数目/个 38 76 离群点数量/个 0 6 12 18 正确的离群点数目/个 38 76 离群点数量/个 0 6 12 18 正确的离群点数目/个 k=13 k=10 k=12 k=18 k=10 38 76 离群点数量/个 0 6 12 18 正确的离群点数目/个 38 76 离群点数量/个 0 6 12 18 正确的离群点数目/个 38 76 离群点数量/个 0 6 12 18 正确的离群点数目/个 38 76 离群点数量/个 0 6 12 18 正确的离群点数目/个 38 76 离群点数量/个 0 6 12 18 正确的离群点数目/个 k=23 k=15 k=50 k=44 k=10 图 8 IRIS 数据集的 ROC 曲线下面积 Fig. 8 Area under the ROC curves of IRIS ·1004· 智 能 系 统 学 报 第 14 卷
第5期 冯骥，等：基于自然邻居邻域图的无参数离群检测算法 ·1005· 总结上述两个人工数据集的实验结果可以发 tions,2011,38(8:9587-9596 现：WNaNG算法的离群检测结果不需要邻域参 [7]CAMPELLO R J G B,MOULAVI D,ZIMEK A,et al. 数，因此不存在邻域选择影响算法效率的问题； Hierarchical density estimates for data clustering,visualiz- 算法在两个数据集中均表现较为稳定，对不同的 ation,and outlier detection[J].ACM transactions on know- 数据集均能获得较好的效果。NS算法需要邻域 ledge discovery from data,2015,10(1):5. 参数，虽然其对参数的容忍度较高，但从本实验 [8]苟和平，景永霞，冯百明，等.基于DBSCAN聚类的改进 中依然可以看到参数取值的最差情况和最好情况 KNN文本分类算法[).科学技术与工程，2013,13(1)： 219-222 所对应的检测结果差距较大。其余3个算法在不 GOU Heping,JING Yongxia,FENG Baiming,et al.An 同数据集、不同参数的情况下表现出了较大的波 improved KNN text categorization algorithm based on DB- 动，且针对不同数据集参数的最优取值之间没有 SCAN[J].Science technology and engineering,2013, 规律，需要根据具体问题独立尝试。 13(1):219-222. 4结束语 [9]周芳芳，高飞，刘勇刚，等.基于密度距离图的交互式体 数据分类方法.软件学报，2016,27(5)：1061-1073 针对离群检测中邻域参数、离群点总数参 ZHOU Fangfang,GAO Fei,LIU Yonggang,et al.Interact- 数以及局部离群点等问题，本文结合自然邻居 ive volume data classification based on density-distance 思想提出了一种自适应的离群检测算法WN- graph[J].Journal of software,2016,27(5):1061-1073. aNG。该算法在不同的数据集中运行时无需人 [10]周国兵，吴建鑫，周嵩.一种基于近邻表示的聚类方法 为设置邻域参数，并能够根据数据集自身的分 [).软件学报，2015,26(11)：2847-2855. 布特征获得令人满意的检测结果。另外，WN ZHOU Guobing,WU Jianxin,ZHOU Song.Clustering method based on nearest neighbors representation[]. aNG能够更为准确地挖掘出局部离群点和全局 Journal of software,2015,26(11):2847-2855 离群点并予以区分，这也为离群点解释、释义空 [11]王习特，申德荣，白梅，等.BOD:一种高效的分布式离 间的构建等数据挖掘的后续步骤提供了强有力 群点检测算法).计算机学报，2016,39(1)：36-51 的支持。 WANG Xite,SHEN Derong,BAI Mei,et al.BOD:an ef- 参考文献： ficient algorithm for distributed outlier detection[J]. Chinese journal of computers,2016,39(1):36-51. [1]BOLTON R J.HAND D J.Statistical fraud detection:a re- [12]陆海青，葛洪伟.自适应灰度加权的鲁棒模糊C均值图 view[J].Statistical science,2002,17(3):235-255. 像分割).智能系统学报，2018,13(4)584-593. [2]DENG Hongmei.XU R.Model selection for anomaly de- LU Haiqing,GE Hongwei.Adaptive gray-weighted ro- tection in wireless ad hoc networks[Cl//Proceedings of bust fuzzy C-means algorithm for image segmentation[J]. 2007 IEEE Symposium on Computational Intelligence and CAAI transactions on intelligent systems,2018,13(4): Data Mining.Honolulu,USA,2007:540-546. 584593. [3]DURAN O,PETROU M.A Time-efficient method for an- [13]赵冠哲，齐建鹏，于彦伟，等.移动社交网络异常签到在 omaly detection in hyperspectral images[J].IEEE Transac- 线检测算法[U.智能系统学报，2017,12(5)：752-759， tions on geoscience and remote sensing,2007,45(12): ZHAO Guanzhe,QI Jianpeng,YU Yanwei,et al.Online 38943904. check-in outlier detection method in mobile social net- [4]PODGORELEC V,HERICKO M,ROZMAN I.Improv- works[J].CAAI transactions on intelligent systems,2017. ing mining of medical data by outliers prediction[C]//Pro- 12(5):752-759 ceedings of the 18th IEEE Symposium on Computer-Based [14]张美琴，白亮，王俊斌.基于加权聚类集成的标签传播 Medical Systems.Dublin,Ireland,2005:91-96. 算法[.智能系统学报，2018,13(6)：994-998. [5]NASI J.SORSA A.LEIVISKA K.Sensor validation and ZHANG Meiqin,BAI Liang,WANG Junbin.Label outlier detection using fuzzy limits[C]//Proceedings of the propagation algorithm based on weighted clustering en- 44th IEEE Conference on Decision and Control.Seville, semble[J].CAAI transactions on intelligent systems. Spain,2005:7828-7833 2018.13(6):994-998 [6]KIM S,CHO N W,KANG B,et al.Fast outlier detection [15]HA J,SEOK S,LEE J S.Robust outlier detection using for very large log data[J].Expert systems with applica- the instability factor[J].Knowledge-based systems,2014
总结上述两个人工数据集的实验结果可以发 现：WNaNG 算法的离群检测结果不需要邻域参 数，因此不存在邻域选择影响算法效率的问题； 算法在两个数据集中均表现较为稳定，对不同的 数据集均能获得较好的效果。INS 算法需要邻域 参数，虽然其对参数的容忍度较高，但从本实验 中依然可以看到参数取值的最差情况和最好情况 所对应的检测结果差距较大。其余 3 个算法在不 同数据集、不同参数的情况下表现出了较大的波 动，且针对不同数据集参数的最优取值之间没有 规律，需要根据具体问题独立尝试。 4 结束语 针对离群检测中邻域参数、离群点总数参 数以及局部离群点等问题，本文结合自然邻居 思想提出了一种自适应的离群检测算法 WNaNG。该算法在不同的数据集中运行时无需人 为设置邻域参数，并能够根据数据集自身的分 布特征获得令人满意的检测结果。另外，WNaNG 能够更为准确地挖掘出局部离群点和全局 离群点并予以区分，这也为离群点解释、释义空 间的构建等数据挖掘的后续步骤提供了强有力 的支持。 参考文献： BOLTON R J, HAND D J. Statistical fraud detection: a review[J]. Statistical science, 2002, 17(3): 235–255. [1] DENG Hongmei, XU R. Model selection for anomaly detection in wireless ad hoc networks[C]//Proceedings of 2007 IEEE Symposium on Computational Intelligence and Data Mining. Honolulu, USA, 2007: 540–546. [2] DURAN O, PETROU M. A Time-efficient method for anomaly detection in hyperspectral images[J]. IEEE Transactions on geoscience and remote sensing, 2007, 45(12): 3894–3904. [3] PODGORELEC V, HERICKO M, ROZMAN I. Improving mining of medical data by outliers prediction[C]//Proceedings of the 18th IEEE Symposium on Computer-Based Medical Systems. Dublin, Ireland, 2005: 91–96. [4] NASI J, SORSA A, LEIVISKA K. Sensor validation and outlier detection using fuzzy limits[C]//Proceedings of the 44th IEEE Conference on Decision and Control. Seville, Spain, 2005: 7828–7833. [5] KIM S, CHO N W, KANG B, et al. Fast outlier detection for very large log data[J]. Expert systems with applica- [6] tions, 2011, 38(8): 9587–9596. CAMPELLO R J G B, MOULAVI D, ZIMEK A, et al. Hierarchical density estimates for data clustering, visualization, and outlier detection[J]. ACM transactions on knowledge discovery from data, 2015, 10(1): 5. [7] 苟和平, 景永霞, 冯百明, 等. 基于 DBSCAN 聚类的改进 KNN 文本分类算法 [J]. 科学技术与工程, 2013, 13(1): 219–222. GOU Heping, JING Yongxia, FENG Baiming, et al. An improved KNN text categorization algorithm based on DBSCAN[J]. Science technology and engineering, 2013, 13(1): 219–222. [8] 周芳芳, 高飞, 刘勇刚, 等. 基于密度-距离图的交互式体 数据分类方法 [J]. 软件学报, 2016, 27(5): 1061–1073. ZHOU Fangfang, GAO Fei, LIU Yonggang, et al. Interactive volume data classification based on density-distance graph[J]. Journal of software, 2016, 27(5): 1061–1073. [9] 周国兵, 吴建鑫, 周嵩. 一种基于近邻表示的聚类方法 [J]. 软件学报, 2015, 26(11): 2847–2855. ZHOU Guobing, WU Jianxin, ZHOU Song. Clustering method based on nearest neighbors representation[J]. Journal of software, 2015, 26(11): 2847–2855. [10] 王习特, 申德荣, 白梅, 等. BOD: 一种高效的分布式离 群点检测算法 [J]. 计算机学报, 2016, 39(1): 36–51. WANG Xite, SHEN Derong, BAI Mei, et al. BOD: an efficient algorithm for distributed outlier detection[J]. Chinese journal of computers, 2016, 39(1): 36–51. [11] 陆海青, 葛洪伟. 自适应灰度加权的鲁棒模糊 C 均值图 像分割 [J]. 智能系统学报, 2018, 13(4): 584–593. LU Haiqing, GE Hongwei. Adaptive gray-weighted robust fuzzy C-means algorithm for image segmentation[J]. CAAI transactions on intelligent systems, 2018, 13(4): 584–593. [12] 赵冠哲, 齐建鹏, 于彦伟, 等. 移动社交网络异常签到在 线检测算法 [J]. 智能系统学报, 2017, 12(5): 752–759. ZHAO Guanzhe, QI Jianpeng, YU Yanwei, et al. Online check-in outlier detection method in mobile social networks[J]. CAAI transactions on intelligent systems, 2017, 12(5): 752–759. [13] 张美琴, 白亮, 王俊斌. 基于加权聚类集成的标签传播 算法 [J]. 智能系统学报, 2018, 13(6): 994–998. ZHANG Meiqin, BAI Liang, WANG Junbin. Label propagation algorithm based on weighted clustering ensemble[J]. CAAI transactions on intelligent systems, 2018, 13(6): 994–998. [14] HA J, SEOK S, LEE J S. Robust outlier detection using the instability factor[J]. Knowledge-based systems, 2014, [15] 第 5 期 冯骥，等：基于自然邻居邻域图的无参数离群检测算法 ·1005·
·1006· 智能系统学报 第14卷 63(2):15-23 冉瑞生，男，1976年生，教授，博 [16]冯骥，张程，朱庆生.一种具有动态邻域特点的自适应 士，主要研究方向为模式识别、机器学 最近邻居算法U.计算机科学，2017,44(12)：194-201. 习。发表学术论文20余篇。 FENG Ji,ZHANG Cheng,ZHU Qingsheng.Adaptive nearest neighbor algorithm with dynamic neighborhood [J].Computer science,2017,44(12):194-201. 作者简介： 魏延，男，1970年生，教授，博士 冯骥，男，1986年生，讲师.博士 中国大数据应用联盟人工智能专家委 主要研究方向为机器学习和数据挖 员会委员，中国计算机学会教育专委 掘。发表学术论文10余篇。 会委员，全国高等学校计算机教育研 究会理事，主要研究方向为机器学习 与智能计算、数据挖掘、支持向量机理 论与算法应用。主持或参与重庆市科 研项目9项。发表学术论文40余篇。 2019第九届中国智能产业高峰论坛 驱动未来，智能无界。由中国人工智能学会主办的“2019第九届中国智能产业高峰论坛”将于2019年 10月26一27日在西安隆重召开。 习近平总书记曾在讲话中指出：“当前，以互联网、大数据、人工智能等为代表的现代信息技术日新月 异，新一轮科技革命和产业变革蓬勃推进，智能产业快速发展，对经济发展、社会进步、全球治理等方面产生 重大而深远影响。”基于此，本届高峰论坛将发挥往届优势，就智能产业发展的关键问题，展开观点交锋和 学术交流，推动智能产业规模化发展与智能技术的突破，加强智能科技的普及与人才培养。 随着A+5G应用场景的亮相.人工智能扎根各个行业，渗透生活点滴。酷炫的智能产品、全新的交互体 验，一幅A1生活的新画卷在慢慢铺展，人工智能已成为真正拉动经济发展的重要引擎。本届峰会，高规格、 强阵容的嘉宾团将紧扣当下热点，一一勾勒人工智能的发展蓝图。 作为2011年学会创建的首批品牌活动之一，中国智能产业高峰论坛从纯学术活动完成了向产业应用的 转型，并取得了不俗反响。峰会的召开，对我国人工智能的科学研究及在各行业落地有着指导作用与战略 意义。未来，学会将继续深入学习贯彻习近平总书记重要讲话精神，将加快数字产业化、产业数字化为己 任，推动数字经济和实体经济深度融合
63(2): 15–23. 冯骥, 张程, 朱庆生. 一种具有动态邻域特点的自适应 最近邻居算法 [J]. 计算机科学, 2017, 44(12): 194–201. FENG Ji, ZHANG Cheng, ZHU Qingsheng. Adaptive nearest neighbor algorithm with dynamic neighborhood [J]. Computer science, 2017, 44(12): 194–201. [16] 作者简介： 冯骥，男，1986 年生，讲师，博士， 主要研究方向为机器学习和数据挖 掘。发表学术论文 10 余篇。 冉瑞生，男，1976 年生，教授，博 士，主要研究方向为模式识别、机器学 习。发表学术论文 20 余篇。 魏延，男，1970 年生，教授，博士， 中国大数据应用联盟人工智能专家委 员会委员，中国计算机学会教育专委 会委员，全国高等学校计算机教育研 究会理事，主要研究方向为机器学习 与智能计算、数据挖掘、支持向量机理 论与算法应用。主持或参与重庆市科 研项目 9 项。发表学术论文 40 余篇。 2019 第九届中国智能产业高峰论坛 驱动未来，智能无界。由中国人工智能学会主办的“2019 第九届中国智能产业高峰论坛”将于 2019 年 10 月 26—27 日在西安隆重召开。 习近平总书记曾在讲话中指出：“当前，以互联网、大数据、人工智能等为代表的现代信息技术日新月 异，新一轮科技革命和产业变革蓬勃推进，智能产业快速发展，对经济发展、社会进步、全球治理等方面产生 重大而深远影响。”基于此，本届高峰论坛将发挥往届优势，就智能产业发展的关键问题，展开观点交锋和 学术交流，推动智能产业规模化发展与智能技术的突破，加强智能科技的普及与人才培养。 随着 AI+5G 应用场景的亮相，人工智能扎根各个行业，渗透生活点滴。酷炫的智能产品、全新的交互体 验，一幅 AI 生活的新画卷在慢慢铺展，人工智能已成为真正拉动经济发展的重要引擎。本届峰会，高规格、 强阵容的嘉宾团将紧扣当下热点，一一勾勒人工智能的发展蓝图。 作为 2011 年学会创建的首批品牌活动之一，中国智能产业高峰论坛从纯学术活动完成了向产业应用的 转型，并取得了不俗反响。峰会的召开，对我国人工智能的科学研究及在各行业落地有着指导作用与战略 意义。未来，学会将继续深入学习贯彻习近平总书记重要讲话精神，将加快数字产业化、产业数字化为己 任，推动数字经济和实体经济深度融合。 ·1006· 智 能 系 统 学 报 第 14 卷
