第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 算法不仅解决了邻域参数的选取问 题，更能在具有不同特性的数据集中取得稳定且 准确的离群检测结果。本文将进一步讨论 WN￾aNG 算法利用自然邻居离群因子查找局部离群点 的实验结果。 图 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·