第 271 题：实现AUC计算，支持大规模数据的流式更新。
题目
实现AUC计算，支持大规模数据的流式更新。
完整讲解
一、AUC 的定义与等价形式
- 定义：ROC 曲线下面积，等价于随机取一正样本与一负样本，正样本得分大于负样本的概率。若正负样本数分别为 $P,N$，则
\(\text{AUC} = \frac{\sum_{i \in \text{pos}} \sum_{j \in \text{neg}} \mathbb{I}[s_i > s_j]}{P \cdot N}.\)
二、流式更新与大规模
- 难点：数据无法一次性加载；需增量维护足以计算 AUC 的统计量，且控制内存与扫描次数。
- 等价计算：对得分排序后，AUC = (正样本的秩和 - P(P+1)/2) / (P·N)；秩和可拆成「每个正样本的秩」之和。流式中维护「当前已见样本中，得分低于某值的正/负个数」，新样本到来时更新这些计数并累加贡献。
- 近似与分桶：得分分桶（如 100 桶），每桶内维护正负计数；用桶中心或桶内线性插值估计秩，得到近似 AUC，误差与桶数相关；适合超大规模与流式。
- 分布式：按 key（如日期、实验）分片，每片局部算「正负对」或秩和，再汇总；注意跨片正负对的合并（若允许全局排序则需全局秩，否则可近似或分段合并）。
三、实现要点
- 单机流式：维护有序结构（如平衡树）或分桶计数，每来一批更新并累加 AUC 分子；或使用在线公式（如 Welford 式扩展）。注意数值稳定性与边界（全正/全负）。
面试要点
- 能写出 AUC 的等价形式（正负对比较、秩和公式），并说明流式下的难点。
- 能说清流式/大规模的实现思路：增量秩和、分桶近似、分布式分片汇总。
记忆要点
- AUC = 随机正样本得分>随机负样本的概率；等价于秩和公式 (秩和 - P(P+1)/2)/(P·N)。
- 流式：增量维护秩或正负对计数；分桶近似降内存；分布式按片算再汇总。