[译]PR曲线和ROC曲线的关系
在看西瓜书第二章讲模型评估的时候, 用到了PR曲线和ROC曲线, 但是书里讲的太扯了, 这里翻译了一篇论文.
原文: Jesse Davis, Mark Goadrich (2006).The Relationship Between Precision-Recall and ROC Curves
概述
ROC曲线在机器学习中常被用来表现二分类问题结果好坏. 然而当处理高度偏斜的数据集时, PR曲线能提供关于算法性能的更好描述. 本文中我们展现了ROC空间和PR空间的内在联系, 一条曲线在ROC空间中”支配(dominate)”, 当且仅当它在PR空间中dominates. 一个结论是, 一条’可实现的PR曲线’, 在ROC空间中会有凸包这类的特征. 我们展示了一个计算这个曲线的有效算法. 最后, 我们也注意到两种曲线在算法设计中的不同. 例如在PR空间中的点之间进行线性插值是错误的. 而且, 能使ROC曲线的AUC面积优化的算法, 不保证能优化AUC-PR.
1. 内容介绍
在机器学习中, 当前的研究在进行新算法理论验证时, 已经不再是简单的算出准确率作为评估标准了, 尤其是在评估一些输出分类结果的算法的时候. Provost et al. (1998)讨论了简单的使用准确率会存在误导. 他们推荐在评估二分类问题时使用ROC曲线, 它能展现 正确预测的正分类的样本数量 和 错误预测的负分类的样本数量. 然而, 当遇到分类极为偏斜的数据集时, ROC曲线对算法性能给出了过于乐观的评估. Drummond and Holte (2000; 2004)推荐使用代价曲线来定位这个问题. 代价曲线是ROC曲线的一个优秀的替代品, 但是讨论它不在本文的范畴.
PR曲线经常用于信息检索领域, 被认为可以作为ROC曲线在偏斜数据集任务上的替代. ROC空间和PR空间的重要区别是曲线的视觉表现不同. 从PR曲线中可以看出很多算法间的差异, 而他们在ROC空间则差异很不明显. 图1(a)和1(b)展示了一些ROC和PR曲线的例子. 这些曲线取自高度偏斜的癌症检测数据集上的一个模型. ROC空间的目标是图的左上角, 在图1(a)中看出他们非常接近最优. PR空间的目标是右上角, 在图1(b)可以看出算法仍有很大的提升空间.
在ROC空间中两个算法的性能类似, 然而在PR空间中我们明显看出算法2比算法1更优. 这个差异存在的原因是, 在这个问题中负例样本数量远远超出正例样本, 导致的一个现象就是, 在ROC分析中, 假正(false positive)样本提高很大的量级, 只能引起FPR很小的变化, 另一方面, 准确率是用假正(fp)和真正(tp)去比较, 就会捕捉更多负样本对算法性能带来的影响. 第二节为不熟悉的读者定义了准确率和召回率等术语.
两种空间的联系、ROC空间的有趣特征算法在PR空间中的反映等等, 我们认为是很重要的研究. 我们发现对于任何数据集、固定的正负样本数量, 给定算法的两种曲线包含”相同的点”. 因此算法1和算法2在图1b中的PR曲线, 某种程度上等价于图1a中算法1和算法2的ROC曲线. 基于ROC和PR曲线的等价性, 我们首先证明了一条曲线在ROC空间中”支配(dominate)”, 当且仅当它在PR空间中dominate. 其次, 我们介绍了PR空间中对ROC凸包的模拟, 我们把它叫’可实现PR曲线’. 同样基于这种等价性, 我们提出了计算’可实现PR曲线’的方法. 第三, 我们证明了在PR空间中线性插值是无效的. 最后, 我们展示了一个算法能优化AUC-ROC并不能保证会优化AUC-PR.
2. 回顾ROC和PR定义
在二分类问题中, 分类器给样本打上’正’或’负’的标签. 分类器的结果可以展现为一个叫混淆矩阵(confusion matrix)或列联表(contingency table)的结构中. 混淆矩阵分为4个类别:
- 真正(True Positives) 是被正确标注为正的样本
- 假正(False Positives) 是被错误标注为正的样本
- 真负(True Negatives) 是被正确标注为负的样本
- 假负(False Negatives) 是被错误标注为负的样本
图2(a)展示了一个混淆矩阵. 混淆矩阵可以用来构建ROC和PR曲线中的一个点. 给定一个混淆矩阵, 我们可以定义两个空间用到的一些指标, 如图2(b). 在ROC空间中, x轴表示假正例率(FPR), y轴表示真正例率(TPR). FPR衡量负样本中被错误标注为正的比例, TPR衡量正样本中被正确标注的比例. 在PR空间中, x轴表示召回率(Recall), y轴表示准确率(Precision), 召回率和真正例率是一样的, 准确率衡量被分类为正的样本中实际为正的比例. 图2(b)给出了每个指标的定义. 我们把这些指标看做混淆矩阵上的函数, 因此给定混淆矩阵A, RECALL(A)返回A对应的召回率.
3. ROC空间和PR空间的关系
ROC和PR曲线通常被用来衡量给定机器学习算法在给定数据集上的性能. 每个数据集包含固定数量的正负样本. 这里我们展示两种空间的深层联系.
定理3.1: 对于给定数据集和正负样本, 在满足条件
Recall≠0时, ROC空间的曲线和PR空间的曲存在一对一关系, 两条曲线对应完全相同的混淆矩阵.
证明: 注意到, 在数据集固定时, ROC空间的一点唯一地对应一个混淆矩阵(译者: 数据集固定, 总样本量, 总正/负样本量确定, 混淆矩阵一共四个值, 通过ROC一个点可以确定两个, 用总正/负样本量减一下, 另外两个也是确定的; PR曲线中类似). 而在PR曲线中因为我们忽略了TN值, 这样有的人可能担心一个点对应多个混淆矩阵. 然而, 当正负样本数固定, 有了其余三个值, TN也能被唯一确定. 当Recall等于0时, 我们没法确定TP值, 也就不能找到唯一的混淆矩阵了.
因此, 在混淆矩阵和PR空间中的点之间有一对一的映射关系. 这意味着在ROC空间和PR空间的点(每个点都由一个混淆矩阵定义)之间也有一对一关系; 由此我们可以将ROC空间的曲线转化为PR曲线, 反之亦然.
为导出我们下一个定理, 需要定义一个重要的概念:
一条曲线支配另一条曲线(one curve dominates another curve) 意思是那条曲线在它的下方或等于它;
定理3.2: 对于固定的正负样本量, 在ROC空间中一条曲线支配另一条曲线, 当且仅当前者在PR空间中也支配后者.
证明:
断言1: 当一条曲线在ROC空间中dominates, 它在PR空间中也dominates.
使用反证法, 假设我们有曲线I和曲线II(如图3所示), 曲线I在ROC空间中dominates曲线II, 我们把他们转化到PR空间, 假设曲线I不再dominates曲线II, 那么在PR空间必然存在某一点A在曲线II上, 点B在曲线I上, 两个点Recall相同, 点B的Precision更低. 换句话说, PRECISION(A) > PRECISION(B), RECALL(B) = RECALL(B).
因为Recall等于TPR, 即TPR(A) = TPR(B). 且在ROC空间上曲线I domintes, 所以FPR(A) >= FPR(B). 总的正例和负例数量是固定的, 又有TPR(A) = TPR(B), 根据TPR公式, 现在我们有TP_A = TP_B. 又因为FPR(A) >= FPR(B), 根据FPR公式能够推出FP_A >= FP_B. 根据PRECSION公式, 可以推出PRECISION(A) <= PRECISION(B), 和我们最初的假设矛盾.
断言2: 当一条曲线在PR空间中dominates, 它在ROC空间中也dominates.
(译者, 证明略, 和上面类似)
在ROC空间中凸包(convex hull)是一个重要概念. 对于ROC空间中的点的子集, 凸包满足如下3个条件:
- 相邻点之间使用线性插值
- 没有点落在最终曲线上方
- 对于构建最终曲线上的任意两点, 两点间连接的直线小于等于曲线
图5(a)展示了ROC空间凸包的例子. 关于如何为具体的算法构建凸包, 可以看Cormen et al. (1990).
在PR空间中存在和ROC中凸包类似的曲线, 我们叫’可实现PR曲线’(achievable PR curve), 然而它不能用线性插值实现. ROC空间中的支配问题直接和凸包模拟有关.
推论3.1: 对于PR空间的点的集合, 存在一条’可实现PR曲线’, 它dominate所有其他用这些点构造的有效曲线.
证明: 首先, 把这些点转到ROC空间(定理3.1), 用这些点在ROC空间构造出凸包曲线, 根据定义, 凸包dominates所有其他用这些点线性插值产生的曲线. 因此把ROC凸包曲线的点转换回PR空间, 会生成一条dominate的曲线(如图5(b),图5(c)). 可由定理3.2推出. 这条可实现PR曲线, 排除了ROC空间上凸包曲线下方的点.
凸包是从ROC空间给定点构造的最佳的合法的曲线. 包括我们在内的许多研究者主张PR曲线在高度偏斜数据集情况时更可取, 因此当我们第一次计算凸包曲线并转化到PR空间时, 惊喜的发现了’可实现PR曲线’. 一个空间中的最佳曲线对应在另一个空间也是最佳曲线.
在构建ROC空间的凸包或PR空间的’可实现PR曲线’时, 有一个重要的方法上的问题必须要提出. 当给一个输出概率(probability)的算法构造ROC曲线时, 经常采用这样的方式: 首先找到测试集每个样本是正例的概率, 然后对列表排序, 升序遍历列表.
为简化讨论, 用class(i)表示列表第i个样本的真实分类, 用prob(i)表示第i个样本的正例的概率. 对于每个i, 若class(i) ≠ class(i+1), prob(i) < prob(i+1), 那么可以创建一个分类器, 所有样本j(j>=i+1)都标注为正, 其他都为负.
因此ROC或PR空间的每一个点, 对应着一个特定的分类器, 它带有一个标记样本为正的概率的阈值. 构造凸包可以看做构造一个新分类器, 这个新分类器只挑出最佳的点. 因此通过在测试集上的性能表现来构造凸包方法上存在错误. 为解决这个问题, 凸包必须由一个调整后的集合构建: 首先使用上面的方法找到阈值的可选集; 然后使用调整数据构造凸包; 最后我们使用调整数据上选出的阈值来给测试数据构建ROC或PR曲线. 尽管这条曲线不保证是测试数据的凸包, 但它保留了训练集和测试集的差异(split).
4. 插值和AUC
在每个空间上如何进行插值是实践中很关键性的问题. 在ROC空间上, 可以很直接地在临近点之间连接一条直线进行插值. One can achieve any level of performance on this line by flipping a weighted coin to decide between the classifiers that the two end points represent. (译者: ROC曲线横纵坐标两个值的分母是固定的, 分子是TP和FP, 两者当然是线性变化的)
然而, 在PR空间, 插值问题更加复杂. 由于PR曲线准确率指标的分母中是FP而不是FN(译者: Precision=TP/TP+FP), 导致召回率变化时, 准确率不一定是线性变化的. 这种情况下, 使用线性插值就是错误的, 会对算法性能产生过于乐观的评估. 推论3.1展示里如何用ROC空间的凸包转换成PR空间的’可实现PR曲线’, 这是一种正确的插值. 然而一条曲线包含无数个点, 我们需要一种实践上可以实现的近似方法. 这里我们扩展了Goadrich et al. (2004)提出的PR空间插值方法.
PR曲线上的任意点A, 都是由混淆矩阵中的真正例TP_A和假正例FP_A的数量生成的. 假设我们在PR空间上有距离较远的两个点A和B, 为了找到可插入的点, 我们必须在TP_A和TP_B, FP_A和FP_B之间插值. 我们算出增加一个正例需要多少个负例, 叫做本地偏斜: FP_B - FP_A / TP_B - TP_A. 现在, 对于任意1 ≤ x ≤ TP_B − TP_A, 可以创造新的点TP_A + x, 如TP_A+1, TP_A+2 … 然后通过本地偏斜为每个点计算出对应的FP(calculate corresponding FP by linearly increasing the false positives for each new point by the local skew). 我们得出的PR曲线中间点就是:
举例来说, 我们有一个20正例2000负例的数据集, TP_A=5, FP_A=5, TP_B=10, FP_B=30. 表1展示了A和B之间正确插值的中间点, 本地偏斜为5, 即每个正例对应5个负例. 注意插值结果中的准确率不是在0.50和0.25间线性变化的.
通常情况下, 使用曲线下方区域面积作为衡量算法在整个空间上的性能的一个简单指标. (Bradley, 1997; Davis et al., 2005;…). ROC曲线下区域(AUC-ROC)可以通过每个ROC点之间做梯形区域的方法计算, 这和Wilcoxon-MannWhitney statistic是等价的. 通过增加我们算出的PR曲线中间点, 我们可以用对应的梯形法来估计PR曲线下面积了(AUC-PR).
当PR曲线中的两个点距离较远且本地偏斜较高时, 使用错误的插值方法给算AUC-PR带来的影响特别显著. 考虑图6中的曲线, 从点(0.01,1)扩展到两个端点(0,1)和(1,0.008)(对于这个例子, 我们的数据集包含433个正例, 56164个负例). 使用我们描述的方法插值得到AUC-PR为0.031, 使用线性连接方法得到AUC-PR为0.50, 高估了数倍.
现在讨论完PR空间的插值, 我们可以给出找到’可实现PR曲线’的完整算法了. 首先找到ROC空间的凸包. 然后对于凸包中的每个点, 我们用它对应的混淆矩阵找到PR空间中的对应点. 最后在这些点之间使用正确插值方法即可.
5. AUC优化
许多研究者使用AUC-ROC作为他们的算法的启发式搜索线索. Ferri et al. (2002)调整决策树使用AUC-ROC作为分支判别标准, Cortes and Mohri (2003)展示了提示算法RankBoost也很适合利用AUC-ROC, Joachims (2005)提出可以用SVM来优化AUC-ROC和其他排序指标, Prati and Flach (2005)使用一种规则选择算法直接在ROC空间中创建凸包, Yan et al. (2003)和Herschtal and Raskutti (2004) 都发现了在神经网络中优化AUC-ROC的方式. 而且, ILP算法例如Aleph (Srinivasan, 2003)可以改成使用ROC或PR空间的启发式方法.
确知ROC空间的凸包可以转换为PR空间中的’可实现PR曲线’, 这引出了另一个开放问题: 一个能优化AUC-ROC的算法是否也优化AUC-PR? 答案通常是NO, 我们接下来用例子证明.
图7(a)展示了ROC空间中两条有交叠的曲线, 数据集是20个正例2000个负例, 每条曲线本身是凸包. 曲线I的AUC-ROC是0.813, 曲线II的AUC-ROC是0.875, 因此一个优化AUC-ROC的算法, 在两者中排序做选择, 会选择曲线II. 然而, 图7(b)中, 同样的曲线转换到PR空间, 差异十分剧烈. 由于超过一半的正例的排序很高, 曲线I的AUC-PR高达0.514, 而曲线II的AUC-PR则是小的多的0.038, 因此为了优化AUC-PR, 会做出一个完全相反的结论, 选择曲线I. 这是因为PR空间上的主要激励来自于在低召回范围内达到更高的准确率. 尽量如此, 基于定理3.2, 对于优化AUC-PR的算法来讲ROC曲线也是有用的. 算法可以在ROC空间中找到凸包, 转换到PR空间中的’可实现RP曲线’, 根据这条曲线下的面积给分类器打分.
6. 总结
本论文得出4项重要结论. First, for any dataset, the ROC curve and PR curve for a given algorithm contain the same points. This equivalence, leads to the surprising theorem that a curve dominates in ROC space if and only if it dominates in PR space. Second, as a corollary to the theorem we show the existence of the PR space analog to the convex hull in ROC space, which we call an achievable PR curve. Remarkably, when constructing the achievable PR curve one discards exactly the same points omitted by the convex hull in ROC space. Consequently, we can efficiently compute the achievable PR curve. Third, we show that simple linear interpolation is insufficient between points in PR space. Finally, we show that an algorithm that optimizes the area under the ROC curve is not guaranteed to optimize the area under the PR curve.