J2Medium★ 工业基石 (核心高频)Part J · 推荐系统与搜索指标
AUC-ROC 排序法实现(并列 Ties 处理)
推荐排序与风控评估核心,从 Wilcoxon-Mann-Whitney 统计检验角度,基于秩排序 O(N log N) 并列均值求解。
⏱️ 时间复杂度:
O(N log N) 排序开销💾 空间复杂度:
O(N)🎯 免登录实战自测闭环(先做再看答案)
按「机制回忆 → 关键行填空 → 边界反例 → 追问与错题记录」顺序自测,进度自动保存在本地。
Step 1 · 机制口述与数值稳定性自检
Step 2 · 核心代码关键行补全
import numpy as np
def calculate_auc_roc_fast(y_true: np.ndarray, y_score: np.ndarray) -> float:
"""
基于秩排序与并列平均的高效 AUC 计算。
"""
y_true = np.asarray(y_true, dtype=bool)
y_score = np.asarray(y_score, dtype=np.float64)
n_pos =
n_neg = len(y_true) - n_pos
if n_pos == 0 or n_neg == 0:
return 0.5
# 升序排序
order = np.argsort(y_score)
sorted_scores = y_score[order]
sorted_labels = y_true[order]
# 计算并列分数的平均秩 (从 1-indexed)
ranks = np.empty(len(y_score), dtype=np.float64)
i = 0
n = len(y_score)
while i < n:
j = i
# 寻找打分相同的连续段
while j < n and sorted_scores[j] == sorted_scores[i]:
j += 1
# 计算平均秩: (i+1 + ... + j) / (j - i) = (i + 1 + j) / 2.0
avg_rank = (i + 1 + j) / 2.0
ranks[i:j] = avg_rank
i = j
# 求所有正样本的秩和
sum_pos_ranks = np.sum(ranks[sorted_labels])
# 核心公式: (Sum_R - M*(M+1)/2) / (M * N)
auc =
return float(auc)
Step 3 · 反例与边界断言核对
Step 4 · 面试追问盲答与错题记录
Q1: GAUC(Group AUC)相比全局 AUC 为什么在推荐系统中更能反映算法对真实用户体验的提升?
💡
实战一句话记忆口诀
打分升序排座位,并列各取平均位,正例排位相加扣,除以正负总对数
📐 核心数学公式与机理推导
### 概率定义与 Wilcoxon 秩检验等价性
AUC(Area Under ROC Curve)在物理上严格等价于:随机抽取一个正样本和一个负样本,模型对正样本预测打分高于负样本的概率:
直接枚举所有正负样本对需要 ( 为正例数, 为负例数)。
高效排序法(Mann-Whitney U 检验):
1. 将所有 个样本按模型预测概率从小到大升序排序;
2. 赋予每个样本排序序号 Rank(从 1 到 );
3. 并列处理(Ties Handling):若多个样本打分完全相同,其 Rank 必须取这组样本的平均序号;
4. 正样本的 Rank 之和减去正样本内部两两组合的位次和 ,再除以总对数 。
整体耗时直接由排序算法决定的 。
AUC(Area Under ROC Curve)在物理上严格等价于:随机抽取一个正样本和一个负样本,模型对正样本预测打分高于负样本的概率:
直接枚举所有正负样本对需要 ( 为正例数, 为负例数)。
高效排序法(Mann-Whitney U 检验):
1. 将所有 个样本按模型预测概率从小到大升序排序;
2. 赋予每个样本排序序号 Rank(从 1 到 );
3. 并列处理(Ties Handling):若多个样本打分完全相同,其 Rank 必须取这组样本的平均序号;
4. 正样本的 Rank 之和减去正样本内部两两组合的位次和 ,再除以总对数 。
整体耗时直接由排序算法决定的 。
🔄 张量维度与形状流转说明
scores, labels -> argsort 升序 -> 处理 ties 求平均秩 -> 提取正样本 rank 求和 -> 代入闭式解 -> 标量 AUC
🛡️ 数值稳定性自检与边界要点
- 打分相同时必须赋予平均秩(例如第 2、3 位并列,秩均为 2.5),否则在二值输出或离散打分下计算结果会严重失真
- 全正或全负样本无法定义 AUC,需捕获异常返回 0.5
💻 完整参考代码实现
import numpy as np
def calculate_auc_roc_fast(y_true: np.ndarray, y_score: np.ndarray) -> float:
"""
基于秩排序与并列平均的高效 AUC 计算。
"""
y_true = np.asarray(y_true, dtype=bool)
y_score = np.asarray(y_score, dtype=np.float64)
n_pos = np.sum(y_true)
n_neg = len(y_true) - n_pos
if n_pos == 0 or n_neg == 0:
return 0.5
# 升序排序
order = np.argsort(y_score)
sorted_scores = y_score[order]
sorted_labels = y_true[order]
# 计算并列分数的平均秩 (从 1-indexed)
ranks = np.empty(len(y_score), dtype=np.float64)
i = 0
n = len(y_score)
while i < n:
j = i
# 寻找打分相同的连续段
while j < n and sorted_scores[j] == sorted_scores[i]:
j += 1
# 计算平均秩: (i+1 + ... + j) / (j - i) = (i + 1 + j) / 2.0
avg_rank = (i + 1 + j) / 2.0
ranks[i:j] = avg_rank
i = j
# 求所有正样本的秩和
sum_pos_ranks = np.sum(ranks[sorted_labels])
# 核心公式: (Sum_R - M*(M+1)/2) / (M * N)
auc = (sum_pos_ranks - n_pos * (n_pos + 1) / 2.0) / (n_pos * n_neg)
return float(auc)
🧪 本地测试与正确性断言
可直接复制到本地 Python / Jupyter 验证:
import numpy as np
# 简单测试用例
y_true = np.array([0, 0, 1, 1])
y_score = np.array([0.1, 0.4, 0.35, 0.8])
# 顺序: 0.1(0, rank1), 0.35(1, rank2), 0.4(0, rank3), 0.8(1, rank4)
# 正样本秩: 2 + 4 = 6; 6 - 2*3/2 = 3; 3 / (2*2) = 0.75
assert calculate_auc_roc_fast(y_true, y_score) == 0.75
# 完美预测
assert calculate_auc_roc_fast(np.array([0, 1]), np.array([0.1, 0.9])) == 1.0
print("✓ AUC-ROC 排序法实现自测通过")🎯 核心工程追问与标准应答
Q1:GAUC(Group AUC)相比全局 AUC 为什么在推荐系统中更能反映算法对真实用户体验的提升?
全局 AUC 容易被“高活跃但全点击”的重度用户或大盘曝光偏置拉偏(辛普森悖论);GAUC 按照每个独立 User 分别在各自的历史展现列表中计算 AUC 并以展示量加权平均:,剔除了用户间固有点击意愿的基础偏差,衡量的是推荐模型在单个用户内部排序的相对保真度。
⚡
想检验本题的肌肉记忆?进入 3 阶闪卡主动回忆盲测
隐藏答案遮罩,自测:审题锚点 ➔ 数理公式机理 ➔ 工业标杆代码与连环追问。3 分钟攻破认知盲区!