评估在线不平衡学习的PAUC

原始论文《Prequential AUC: properties of the area under the ROC curve for data streams with concept drift》
由于正常的AUC需要计算整体数据集上，每个数据的预测置信度的排名。那么我们首先要求我们的在线学习算法在进行预测时也返回预测为某个类别的概率数值，并将其限制为二分类。

然后再在每个例子后使用一个特殊的排序结构结合滑动窗口遗忘机制来增量计算AUC。因为我们无法记得所有的例子，无法按照AUC的原始计算方式来对所有实例排序。为了使AUC在计算上可行并适用于不断发展的概念，必须使用滑动窗口进行计算。分数的滑动窗口将分析限制在最新的数据上，但要计算AUC，必须对分数进行排序。为了有效地维护一组排序的分数，我们建议使用红黑树数据结构。

伪代码为：

具体的文字描述为：

• 对于每个传入的标记示例，分类器分配给该示例的分数被插入到窗口（第15行）以及红黑树（第10行）中，如果已经超过示例窗口，则删除最旧的分数（第5行和第15行）
• 红黑树根据分数以降序排序，如果分数在负数之前是正数，则根据到达时间以升序排序。通过这种方式，我们保持了一个便于计算AUC的结构，并确保滑动窗口中最旧的分数将在红黑树中被及时找到。
• 在滑动窗口和树已经被更新之后，通过对在每个阴性示例之前出现的阳性示例的数量求和（第18-28行）并通过所有可能的对pn（第29行）将该值归一化来计算AUC，其中p是窗口中阳性的数量，并且n是阴性的数量。
• 在第26行中，我们通过减少AUC的增量来考虑阳性和阴性示例之间的分数关系。

例子如下图所示：

窗口W包含六个例子，所有这些例子都已经插入到红黑树中。如前所述，树中的示例根据得分s降序排序（深度优先搜索），肯定在否定之前，并且根据到达时间t升序排序。当一个新的实例被分类器评分时（t：7，l：+，s：0.80），最旧的实例（t：1）将从窗口和树中删除。在插入新的评分示例之后，通过以深度优先搜索方式遍历树并对算法1的第17-29行中呈现的标签进行计数来计算AUC。

并且经过实验证明，随时间平均的序贯AUC与在整个流上计算的AUC高度一致且具有显著判别性。