algorithm - 当一个标签改变时，有效地重新计算 ROC 下的区域

Question

假设您有一个带有二进制标签的分数列表(为简单起见，假设没有关系)，并且我们使用这些标签来计算相关受试者工作特征 (ROC) 曲线下的面积。对于一组 n 个分数，这个计算在 O(n log n) 时间内很简单——您只需对列表进行排序，然后按排序顺序遍历列表，保持您正在运行的正面标记示例的总数。到目前为止已经看到了。每次看到负面标签时，您都会添加正面数量，最后将所得总和除以正面数量乘以负面数量的乘积。

现在，完成该计算后，假设有人过来并恰好翻转了一个标签(从正面到负面，反之亦然)。分数本身不会改变，所以你不需要重新排序。通过重新遍历排序列表，可以在 O(n) 时间内计算出新的曲线下面积 (AUC)。我的问题是，是否有可能以比 O(n) 更好的方式计算新的 AUC？即，我是否必须重新遍历整个排序列表才能获得新的 AUC？

我想我可以在 O(1) 时间内重新计算，方法是在排名列表的每个位置存储一个计数，计算该位置上方的正数和负数。但随着更多标签被翻转，我将需要重复计算 AUC。而且我认为，如果我依赖那些存储的值，那么下次更新它们将是 O(n)。

Answer 1

是的，可以在 O(log(n)) 中计算 AUC。您需要两组分数，一组用于正数，一组用于负数，它们提供以下操作:

1. 查询得分高于(或低于)给定值(被翻转标签的得分)的项目数。
2. 插入和删除元素。

如前所述，了解高于/低于给定位置的正数可以让您有效地更新 AUC。之后，您必须从正数/负数集合中删除该项目并分别插入负数/正数。平衡搜索树可以在 O(log(n)) 中完成这两个操作。

此外，分数的实际值无关紧要，只有位置相关。这导致使用二叉索引树的非常简单和有效的实现。参见 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees解释。另外，你真的不需要维护两套。由于您已经知道给定位置上方的正负总数，因此一组就足够了。