离群点检测算法的评价指标

宁 进，陈雷霆，3，罗子娟，周 川*，曾慧茹

（1.电子科技大学计算机科学与工程学院，成都 611731；2.数字媒体技术四川省重点实验室（电子科技大学），成都 611731；3.电子科技大学广东电子信息工程研究院，广东东莞 523808；4.中国电子科技集团公司第二十八研究所信息系统工程重点实验室，南京 210007）

0 引言

离群点，也可称为异常点，是数据集中与大多数点不一致，或是由不同机制产生的数据［1］。例如在海上安防系统［2］中，入侵船只被看作是异常点，需要拦截。雷达数据处理中［3］，噪声被看作是离群点，需要过滤以防止干扰建模。

近年来，离群点检测算法依然是数据挖掘的热点方向。各种基于统计、基于邻近性、基于分类、基于聚类、基于集成的方法等［4-5］层出不穷，以取得更好的离群点检测效果。离群点检测算法的输出通常为离群得分，得分越高，越可能是离群点。基于统计的方法对正常数据建模，用与正常模式的偏离程度来表示离群得分。基于邻近性的方法用与邻居差异程度来表示离群得分。基于分类的方法用与分界线的偏离程度来衡量离群得分。基于聚类的方法视离群点为聚类的副产物，用与正常簇的偏离程度来衡量离群得分。基于集成的方法通过集成多个结果得到最终的离群得分。

由于离群点本身的少量、多变，以及难以预知、难以建模的特点，离群点检测算法常采用无监督方法。再加上缺少离群点的标签，使得离群点检测的评价变得困难。离群点检测一般使用外部度量来进行评价，这种度量需要已有的真实标签来进行。现有的离群点检测算法评价指标主要分为三类，如图1。第一种是阈值法，在离群得分的基础上，利用所设置的阈值来划分预测的离群点集。将预测的离群点集与真实的离群点标签作对比，用检测率、精确度等统计值来评价算法效果。第二种是曲线法，将阈值法的全参数下的指标绘制连续的曲线，曲线越“凸”，表示算法效果越好。第三种是整合法，用曲线下的面积来衡量算法效果，值越大，表示算法的效果越好。

图1 离群点检测算法评价指标Fig.1 Evaluation metrics of outlier detection algorithm

近年来，一些改进的方法也被提出来了。例如Zhang等［6］提出了一种带标准化的精确度的均值，以包含离群度排位信息；但是，这种方法在没有调整的时候会产生错误［7］。Klement 等［8］针对受试者工作特征（Receiver Operating Characteristic，ROC）曲线丢失离群得分信息的问题，提出了一种平滑的ROC 曲线，通过对ROC 曲线加入平滑分量以保留离群得分信息，对评价算法的差异更具有一致性。此外，Marques 等［9］提出了一种不需要真实标签的内部评价方式，这种方式基于离群得分的相对评价，但是计算复杂度太高。

尽管已有很多适合的评价指标，但很多离群点检测文献仍然存在评价方法选择不当、使用不当的问题，使得所得出的结论站不住脚。例如，如果错将正常点标记1，异常点标记0，得出的评价指标虚高。再例如，使用阈值法时，阈值设置不合理，得出的指标结果偏差也大。此外，离群点检测算法的评价要求常常分为两类：一类要求高真正率，例如在疾病检测中，要求检测到所有患病者，即使存在将正常人归为患病类；二类要求低假正率。例如在垃圾邮件检测中，要求不能把有用邮件误归为垃圾邮件，即使漏检部分真正的垃圾邮件。总之，由于离群点检测算法的特殊性，目前，仍然缺乏针对离群点检测问题的专门的系统评价方法研究。

本文首先对离群点检测算法的已有评价指标做了一个详细的整理，为研究者评价所提出的算法提供评价指标的说明和参考；然后针对已有指标不能区分一类和二类要求的问题，提出了一类高真正率评价指标（High True positive rate-Area Under Curve，HT_AUC）和二类低假正率评价指标（Low False positive rate-Area Under Curve，LF_AUC），通过计算证明和在真实数据集上与已有方法的对比实验，说明了本方法的适用性。

1 常用的离群点检测算法评价指标

设N个点的离散数据集D中，O表示真实的离群点集（令集合大小|O|=n），NO表示正常点集（令集合大小|NO|=m）。离群点检测算法大多返回离群得分（Outlier Score，OS）［1］，可以是距离、密度、概率等。离群得分越高，越可能是离群点。OS(p)表示点p的离群得分。rank(p)表示点p的离群得分在OS 中的排位，离群得分越高，rank值越小，位次越高。离群点的标签应是正类（这里用“1”表示）；正常点的标签应是负类（这里用“0”表示）。

1.1 阈值法

步骤1 设定阈值。

另一种是TOPr（1 ≤r≤N，评价的时候只要真实的标签可用，那么r就可以设为n），表示将离群得分排在前r的点判为离群点。

步骤2 计算评价指标对。

离群点检测算法所采用的评价指标对主要有3 组，分别是精确度（Precision）和召回率（Recall）［11-13］，真正率（True Positive Rate，TPR）和假正率（False Positive Rate，FPR）［14-15］，检测率（Detection Rate，DR）和排位力（Rank power，Rp）［16-17］。计算方法如表1。其中：TP表示将离群点标记为离群点的量；FP表示将正常点标记为离群点的量；FN表示将离群点标记为正常点的量；TN表示将离群点标记为离群点的量。

表1 阈值法的评价指标计算方法Tab.1 Evaluation metrics calculation method of threshold method

Recall=TPR=DR，也称为检测准确率，表示预测出的真实离群点数量占所有的真实离群点数量的比，值越高，表示算法效果越好。但这个单一的指标存在着漏洞，即越大，检测准确率越高。当算法预测所有数据为离群点，即时，检测准确率为1。所以，只有这一个指标还不足以说明算法的效果。Precision表示预测出的真实离群点数量占预测的离群点数量的比，值越高，表示算法效果越好。FPR表示预测错误的离群点（真实的正常点预测为离群点）占正常点数量的比，值越低，表示算法效果越好。Rp反映了预测的真实离群点在rank中的排位情况，值越高，表示算法的效果越好。所有的离群点排位在rank前列时，Rp=1。Precision、FPR和Rp作为检测准确率的补充增强，可以弥补检测准确率的漏洞；此外Rp还利用了rank信息，对算法要求更高。

阈值法简单有效，可以直接评价离群点检测算法实验结果的优劣。但是有如下3个缺陷：

1）参数依赖。例如，α值太高（或者r太小），漏标多，评价值会偏低；α值太低（或者r太大），错标多，评价值会偏高。

2）参数设置困难。大部分论文在使用这种方法评价算法时，会设置r=|O|，这需要提前知道数据集中有多少真实的离群点。然而在实际应用中，很难提前获取真实离群点的量。

3）丢失了rank 和score 信息。不能表示算法结果的整体好坏。此外，即使是Rp利用了部分rank 信息，仍然区分不了如下情况。例如表2：取r=4 的时候，检测准确率DR1=DR2=0.5，Rp1=Rp2=0.6，这种情况下，算法1 和算法2 的评价结果相同，无法区分好坏。

表2 Rank Power的例子Tab.2 Examples of Rank Power

4）对于Precision 和Recall，在参数相同的情况下，一些好的算法常常要么高Precision 低Recall，要么低Precision 高Recall。

1.2 曲线法

为了摆脱参数依赖，整合rank信息，以更精确地评价各个算法的优劣。通过从1 到N变化参数r，得到对应的N组Precision 和Recall。依次连接每对（Recall（r），Precision（r））点绘制Precision-Recall（PR）曲线［1，18］（如图2（a））。同样，通过从1 到N变化参数r，依次得到对应的TPR（r）和FPR（r），FPR 作横坐标，TPR 作纵坐标，绘制ROC 曲线［19-21］（如图2（b））。由于ROC 曲线比PR 曲线更直观，且具有单调性，所以一般情况下，多使用ROC 曲线。ROC 曲线越“凸”，表示算法的效果越好。smROC［8］在ROC曲线的基础上增加了离群得分信息，使得修改的ROC曲线更加平滑（如图2（c））。

图2 PR curve、ROC curve和smROC curve的示例Fig.2 Examples of PR curve，ROC curve and smROC curve

ROC 曲线应用在离群点检测算法的结果评价上，具有直观、简便、精确的优点，且不受离群点检测数据集类别的有偏性的影响，在一定程度上是很成功的，具有广泛的应用；但仍然有如下缺陷：

1）不够清楚。很多时候，一个算法不会完全地比另一个算法“凸”，例如图2（b），或者更加错综复杂，算法的优劣需要进一步分情况讨论。

2）不能扩展。大部分离群点检测算法都有除阈值以外的其他参数依赖，例如，基于邻近性的算法依赖参数k（邻域的大小），基于一类支持向量机算法依赖核函数的选择，用ROC 曲线只能展示特定参数下算法的差异。

1.3 整合法

为了验证算法与非阈值参数的关系，通常需要整合曲线，直接用一个数值来体现算法综合能力。使得该数值既有阈值法的简单直观性，并保留曲线法的精确性。已经知道，曲线法评价好的算法比坏的算法更“凸”，于是可以用一种曲线的整合形式，即曲线下的面积（Area Under Curve，AUC）来评价算法。数值越高，表示算法效果越好。

PR_AUC［22-23］是PR 曲线下的面积，可以由离群点的平均精确度计算。

证明 在PR 曲线中，随着r的增加，当第r个数据点真实标签为1 时，Precision 变为Precision（r），Recall 增加1/n，对应变化面积为。当第r个数据点真实标签为0 时，Recall 不变，Precision 减少，曲线垂直下降，变化面积为0，所以PR_AUC可以计算如下：

ROC_AUC［24-25］是ROC 曲线下的面积，也可由数据集中离群点-正常点对的均值来计算。

证明 离散情况下，在ROC 曲线中随着r增加，当第r个数据点真实标签为1 时，TPR 增加1/n，FPR 不变，对应ROC 曲线垂直上升，变化面积为0。当第r个数据点真实标签为0时，TPR 不变，FPR 增加1/m，对应变化面积为TPR(rank(i))，所以ROC_AUC可以计算如下：

用曲线法评价离群点检测算法效果时，不受数据集中离群点比例的影响。但整合为ROC_AUC 后，只要求曲线像左上角“凸”，很难保证算法同时有高真正率和低假正率，丢失了曲线的细节信息，不能同时满足一类和二类要求。例如表3中，算 法1 的ROC_AUC1==0.8，算 法2 的=0.8。算法1 和算法2 的ROC_AUC值相同，但实际差别很大。算法1 在r=4 时，就能检测出所有离群点，而算法2 在r=6 的时候才能检测出所有离群点；算法r=2时，能检测出2个离群点，且未将正常点误判为离群点，而算法1无论r等于多少，都存在将正常点误判为离群点。

在实际应用中，对于算法1 和算法2 有着不同的适用场景。算法1 适合要求高检测准确率的场景，即要求所有离群点的rank 靠前，例如疾病检测；算法2 适合要求低错误率的场景，即要求所有正常点的rank靠后，例如垃圾邮件检测。

代价敏感（Meta Cost）方法［1］通过引入代价因子，作为TPR和FPR的权衡。代价因子c（Y，n）表示将正常点预测为离群点的代价，c(N，y)表示将离群点预测为正常点的代价。通过修改I函数，每项不等式右乘，为不同类型的错误分类设置不同的代价。当设置c(Y，n) ＞c(N，y)时，表示正常点预测为离群点的代价更高，最终的meta_AUC 比ROC_AUC 更小；当设置c(Y，n) ＜c(N，y)时，表示离群点预测为正常点的代价更高，最终的meta_AUC 比ROC_AUC 更大。这种方法通过设置两个代价因子来权衡参数依赖，需要依靠经验设置。代价因子的可解释性较弱，不便于使用。

表3 ROC_AUC的例子Tab.3 Examples of ROC_AUC

综上述，阈值法适合在应用决策时使用，曲线法适合算法效果的精确展示，整合法适合在参数控制时使用。已有的离群点检测评价方式常常采用以上指标的综合方案［8］，以便优势互补，充分验证算法的效果。

2 方法

2.1 高真正率和低假正率指标

定义1一类高真正率要求：要求TPR 接近1，对应ROC曲线向顶部“凸”。

定义2二类低假正率要求：要求FPR 接近0，对应ROC曲线向左部“凸”。

例如在疾病检测中，将患病（标签为“1”）错标记为正常（“0”），会导致该患者得不到治疗。如果是传染病，漏检还会发生进一步传染，产生严重的后果。因此，疾病检测系统要求一类高真正率，检测到所有患病者，即使存在将正常人归为患病类，可以进一步检测排除“疑似类”。在垃圾邮件检测中，将重要邮件（标签为“0”）误判为垃圾邮件（标签为“1”），会给收件人带来难以估量的影响。因此垃圾邮件检测系统要求二类要求低假正率，要求不能把重要邮件误判为垃圾邮件，即使漏检部分真正的垃圾邮件。

为了同时解决已有整合法的信息丢失和参数依赖的问题，适应一类高真正率和二类低假正率要求，本文提出了HT_AUC和LF_AUC。

其中：α∈[0，1]是控制变量，表示求算法的ROC曲线在FPR＞α时具有高TPR，H表示NO中rank 值在后的点的集合。式（1）中第一个加项表示ROC 曲线后1-α部分曲线的面积，第二个加项表示忽略ROC曲线前α部分曲线的面积，适应一类要求。

其中：α∈[0，1]是控制变量，表示求算法的ROC曲线在TPR＜α时具有低FPR，L表示O中rank 值在前α*n的点的集合。式（2）中第一个加项表示ROC曲线下面α部分曲线的面积，第二个加项表示忽略ROC 曲线后1-α部分曲线的面积，适应二类要求。

例如，表3中算法1和算法2，取α=0.2，可以计算出：

HT_AUC1＞HT_AUC2，说明算法1 更能适应一类要求，LF_AUC2＞LF_AUC1，说明算法2更能适应二类要求。

2.2 证明

本方法通过调整参数α控制一类高真正率或者二类低假正率要求的程度。对于HT_AUC，表示在容忍FPR=α的情况下整合TPR 越高越好，α越小越接近ROC_AUC；对于LF_AUC，表示在满足TPR=α的情况下整合FPR 越低越好，α越大越接近ROC_AUC。相较于Meta Cost 中的代价因子，本文方法的参数可解释性更强，更容易设置，参数依赖性更低。

3 实验结果与分析

3.1 实验准备

数据集取自UCI 的30 个真实数据集［26］，表4 展示了这些真实数据集的特征。将数量稀少的类或者特选类中的数据点作为离群点，剩余的数据点作为正常点。

1）一类和二类要求。为了验证本文评价方法的有效性，本文首先细化一类要求：要求在FPR=40%时，离群点检测算法的TPR越高，算法效果越好。这种要求表示在同等容错下，检测准确率越高的算法越能满足高真正率要求。然后细化二类要求：要求在TPR=80%时，离群点检测算法的FPR越低，算法效果越好。这种要求表示在同等检测率下，检测错误率越低的算法越能满足低假正率要求。实验平台为3.4 GHz CPU，8 GB RAM，Windows10 系统，PyCharm 社区版，采用Python编程。

2）离群点检测方法。使用下列4 种经典的离群点检测算法［18，27］作为评价指标的对比算法：局部异常因子（Local Outlier Factor，LOF）、K最近邻（KNearest Neighbor，KNN）、孤立森林（Isolation Forest，IF）、不稳定因子（INStability factor，INS）。这4 种不同类型的算法在每个数据集上的检测结果有不同程度的差异，本实验的目的即比较出更能区分这些算法在不同要求下效果优劣的评价指标。

3）对比方法。将本文提出的HT_AUC 和LF_AUC 方法与已有的PR_AUC，ROC_AUC 以及meta_AUC（代价比分别设为1.25 和0.8）作对比。一类要求的评价方法对比策略：以每个算法在FPR=40%时的TPR 值作为基准指标，按从大到小对算法排序，再对比HT_AUC 与其他3 个方法的评价排序，与基准指标越接近（排序的欧式距离越小）的评价方法越好；同理，二类要求的评价方法对比策略：以每个算法在TPR=80%时的FPR 值作为基准指标，按从小到大对算法排序，再对比HT_AUC 与其他3 个算法的评价排序，与基准指标越接近（排序的欧式距离越小）的评价方法越好。

表4 真实数据集的描述Tab.4 Description of real-world datasets

3.2 结果及分析

图3记录了HT_AUC与对比方法在30个真实数据集上的实验结果。可以看出，meta_AUC 在大部分数据集上具有最高的差异度，也就是与基准指标的差异最大，这是由于代价因子的影响。PR_AUC 和ROC_AUC 的方法大部分时候与基准指标差异不大，能基本满足一类高真正率要求。HT_AUC 在大部分情况下结果和ROC_AUC 一致，部分数据集上能展示出更好的效果。因此，可以得出结论，HT_AUC 比其他指标更能满足一类高真正率要求。

图4 记录了LF_AUC 与对比方法在30 个真实数据集上的实验结果。同样的，meta_AUC 在大部分数据集上与基准指标的差异较大。PR_AUC 和ROC_AUC 的方法大部分时候与基准指标差异不大，能基本满足二类低假正率要求。LF_AUC在大部分情况下结果和ROC_AUC 一致，其余数据集上能展示出更好的效果。因此，也可以得出结论，LF_AUC 比其他指标更能满足二类低真正率要求。

图3 HT_AUC与传统评价方法的结果对比Fig.3 Result comparison of the proposed HT_AUC and traditional methods

图4 LF_AUC与传统评价方法的结果对比Fig.4 Result comparison of the proposed LF_AUC and traditional methods

整体来看，所提出HT_AUC 和LF_AUC 指标相较于其他方法，与基准指标的差异最小，更能满足一类高真正率要求和二类低真正率要求。该方法可作为具有特别要求系统的评价指标，例如要求一类高真正率的疾病检测可使用HT_AUC 指标，要求二类低假正率的垃圾邮件检测可使用LF_AUC指标。

4 结语

本文对离群点检测领域内常见的评价方法作了归纳整理，并提出了满足一类高真正率要求的HT_AUC 指标和满足二类低假正率要求的LF_AUC 指标。已有离群点检测评价方式建议采用两类以上的评价指标，以便优势互补，充分验证算法的效果。其中，阈值法适合工业选择时使用，曲线法适合算法效果的精确展示，整合法适合在参数控制时使用。实验结果表明，如果应用对算法的真正率和假正率有特殊要求，采用所提出的HT_AUC 和LF_AUC 指标，能更好地评价所使用的算法。本文所涉及的数据对象主要是离群数据集，未来将继续对序列离群点检测算法的评价方法进行研究。