- 正确答案：AUC（Area Under the ROC Curve）是衡量二分类模型排序能力的核心指标，其值等于所有正样本预测得分大于负样本预测得分的概率，等价于ROC曲线下的面积。可通过以下两种主流方法实现：（1）基于排序+累计计数的O(n log n)算法；（2）基于梯形法则对离散ROC点积分的O(n)变体（需先按score降序排列并去重分组）。标准实现应正确处理边界、重复分数、全正/全负样本等corner case。 - 解答思路：第一步：明确输入——真实标签y_true（0/1数组）和预测得分y_score（float数组），长度一致；第二步：理解AUC几何定义——ROC曲线以FPR为横轴（x = FP / (FP + TN)）、TPR为纵轴（y = TP / (TP + FN)），当按预测分降序遍历样本时，每遇到一个正样本，TPR上升；每遇到一个负样本，FPR上升；ROC曲线由这些阶梯点连成；第三步：利用“AUC = 正负样本对中正样本score > 负样本score 的比例”这一概率解释，转化为统计所有正负对中满足条件的数量；但直接双重循环O(n²)不可取，故采用排序后双指针累计法：将所有样本按score从高到低排序，遍历过程中维护已见负样本数（即当前FPR分母相关量），每遇到一个正样本，将其与所有已遍历的负样本构成有效对，累加贡献；第四步：注意重复score的处理——相同score的样本应视为“同时触发”，即在计算时，需将同分组内正负样本间不产生区分（score相等不算“大于”），因此必须将同分样本聚类，在跨分组时才累计；更稳健做法是：排序后，对每个唯一score，统计该分组内正样本数p_i和负样本数n_i，再累加 p_i * (cum_neg_before)，其中cum_neg_before是严格更高score的所有负样本总数；最后再加上同分组内正负组合的“平局修正项”（实际AUC定义中score相等不计入分子，故无需加）；第五步：归一化——分子为所有正负对中正>负的对数，分母为总正负对数（pos_count * neg_count），若无负样本或无正样本，AUC无定义，应返回NaN或抛异常。 - 深度知识讲解： AUC本质是Mann-Whitney U统计量的标准化形式：U = sum_{i: y_i=1} rank_i − pos_count*(pos_count+1)/2，而AUC = U / (pos_count * neg_count)。这揭示了其非参数检验属性——不依赖分布假设，仅依赖排序。底层数据结构关键点：需支持稳定排序（因相同score的样本顺序不影响结果，但Python sorted默认稳定，可利用）；需高效聚合——用字典或Counter统计各score下正负频次；时间复杂度瓶颈在排序O(n log n)，后续扫描O(n)；空间复杂度O(n)存排序索引或频次表。实现原理上，经典scikit-learn的_auc_binary函数采用“排序+前缀和”策略：先argsort得到降序索引，然后计算每个正样本位置左侧（即更高分）的负样本数量之和；该方法隐含要求排序稳定性以保证同分时负样本排在正样本前（实际通过调整排序键规避：如(-score, y_true)确保负样本在同分中优先？不，正确做法是：同分时顺序无关，只要在累加时只计“严格更高分”的负样本即可）。进阶考点：如何在线流式更新AUC？需维护平衡BST或Fenwick Tree动态统计逆序对；多标签场景下macro/micro AUC的区别；AUC与KS统计量关系（KS = max(TPR−FPR)）；校准后AUC不变性（因只依赖排序，不依赖概率绝对值）。 - 代码示例（完整、鲁棒、带注释）： def auc(y_true, y_score): import numpy as np y_true = np.asarray(y_true) y_score = np.asarray(y_score) if len(y_true) != len(y_score): raise ValueError("y_true and y_score must have the same length") if len(y_true) == 0: raise ValueError("at least one sample is required") # 统计正负样本数 pos = y_true == 1 neg = y_true == 0 n_pos = np.sum(pos) n_neg = np.sum(neg) # AUC无定义情形 if n_pos == 0 or n_neg == 0: return float('nan') # 合并score和label，按score降序排列；同分时任意顺序均可（因只计严格大于） pairs = sorted(zip(y_score, y_true), key=lambda x: x[0], reverse=True) # 遍历排序后序列，累计：对每个正样本，统计其之前（即score更高）的负样本数 cum_neg = 0 auc_score = 0.0 i = 0 while i < len(pairs): # 聚类当前相同score的所有样本 curr_score = pairs[i][0] j = i while j < len(pairs) and abs(pairs[j][0] - curr_score) < 1e-12: # 浮点容差 j += 1 # 统计该score块内正负数量 block_pos = 0 block_neg = 0 for k in range(i, j): if pairs[k][1] == 1: block_pos += 1 else: block_neg += 1 # 当前块中每个正样本，可与cum_neg个更高分负样本配对 → 贡献 block_pos * cum_neg auc_score += block_pos * cum_neg # 更新cum_neg：将当前块的负样本加入，供后续更低分的正样本使用 cum_neg += block_neg i = j # 归一化：总正负对数 total_pairs = n_pos * n_neg return auc_score / total_pairs # 测试用例 print(auc([1, 0, 1, 0, 1], [0.9, 0.2, 0.8, 0.3, 0.7])) # 期望：0.8（手动验证：正样本score=[0.9,0.8,0.7]，负=[0.2,0.3]；高于0.2的正有3个，高于0.3的正有3个 → 3+3=6，6/(3*2)=1.0？错——重新算：正样本按score降序为[0.9,0.8,0.7]，负为[0.2,0.3]；对负0.2：3个正>它；对负0.3：3个正>它；共6，6/6=1.0。但实际排序后pairs=[(0.9,1),(0.8,1),(0.7,1),(0.3,0),(0.2,0)]，遍历时：前3个正，cum_neg=0，auc_score=0；第4个负，cum_neg→1；第5个负，cum_neg→2；结束。auc_score=0 → 错！根本错误：上述代码逻辑反了——应是在遇到负样本时累加其对后续正样本的贡献，而非正样本对之前负样本的贡献。正确逻辑是：按score降序遍历，维护已见负样本数cum_neg；每遇到一个正样本，它比所有已见负样本score高，因此贡献cum_neg；所以正样本必须在负样本之后处理？不，是降序，高分在前，所以正样本若分高，则其前面没有负样本，贡献0；只有当正样本出现在负样本“后面”（即分更低）时，前面的负样本分更高，不能被它超过。因此必须反过来：按score升序遍历，或更标准做法——按score降序，但统计的是“该正样本能超过多少已出现的负样本”，而由于降序，已出现的负样本分 >= 当前正样本分，仅当严格大于时才计。因此正确做法是：先排序（score降序），然后从左到右，遇到负样本，cum_neg++；遇到正样本，auc_score += cum_neg（因为cum_neg个负样本分都比它高，不满足“正>负”）——等等，这反而统计的是正<负的数量！彻底纠正：AUC = P(score_pos > score_neg)，即对每个正样本，数有多少负样本score严格小于它。因此，应按score升序遍历：每遇到负样本，neg_count++；每遇到正样本，它大于所有已遍历的负样本（因其score更大），故加neg_count。所以正确顺序是升序！修正代码： def auc(y_true, y_score): import numpy as np y_true = np.asarray(y_true) y_score = np.asarray(y_score) if len(y_true) != len(y_score): raise ValueError("y_true and y_score must have the same length") if len(y_true) == 0: raise ValueError("at least one sample is required") pos = y_true == 1 neg = y_true == 0 n_pos = np.sum(pos) n_neg = np.sum(neg) if n_pos == 0 or n_neg == 0: return float('nan') # 关键：按score升序排列 → 遍历时，当前样本score最小，所有已遍历样本score <= 它 # 所以当遇到正样本时，所有已遍历的负样本score <= 当前正样本score，其中严格小于的才计 # 但升序中，已遍历负样本score <= 当前，要统计严格小于，需排除等于 # 因此仍需分组：按score升序，同分组内先处理负样本（使其不被同分正样本计），再处理正样本 pairs = sorted(zip(y_score, y_true), key=lambda x: (x[0], x[1])) # 同分时负(0)排正(1)前 auc_score = 0.0 cum_neg = 0 # 已遍历且score严格小于当前分组的负样本数 i = 0 while i < len(pairs): curr_score = pairs[i][0] j = i while j < len(pairs) and abs(pairs[j][0] - curr_score) < 1e-12: j += 1 # 同分组内：先统计负样本数（它们score等于curr_score，对后续更高分正样本有用，但对当前分组正样本不贡献，因不严格小于） # 所以：先遍历组内所有负样本，cum_neg += count_neg_in_block # 再遍历组内正样本，每个贡献 cum_neg（因cum_neg个负样本score < curr_score） block_neg = 0 block_pos = 0 for k in range(i, j): if pairs[k][1] == 0: block_neg += 1 else: block_pos += 1 # 当前分组负样本score == curr_score，它们对当前分组正样本无贡献（因不严格小于），但对后续更高分正样本有贡献 # 所以先加block_neg到cum_neg，再用cum_neg乘block_pos auc_score += block_pos * cum_neg cum_neg += block_neg i = j return auc_score / (n_pos * n_neg) # 验证：y_true=[1,0,1,0,1], y_score=[0.9,0.2,0.8,0.3,0.7] # pairs升序：[(0.2,0),(0.3,0),(0.7,1),(0.8,1),(0.9,1)] → 分组：0.2(1负),0.3(1负),0.7(1正),0.8(1正),0.9(1正) # i=0: curr=0.2, block_neg=1, block_pos=0 → auc=0, cum_neg=1 # i=1: curr=0.3, block_neg=1, block_pos=0 → auc=0, cum_neg=2 # i=2: curr=0.7, block_neg=0, block_pos=1 → auc += 1*2 = 2, cum_neg=2 # i=3: curr=0.8, block_neg=0, block_pos=1 → auc += 1*2 = 4, cum_neg=2 # i=4: curr=0.9, block_neg=0, block_pos=1 → auc += 1*2 = 6 # total_pairs = 3*2 = 6 → auc = 6/6 = 1.0 —— 但直观上0.2和0.3均小于所有三个正分，故确实应为1.0。 # 若y_score=[0.1,0.2,0.3,0.4,0.5], y_true=[0,0,1,1,1]，则正分0.3/0.4/0.5，负分0.1/0.2 → 所有3*2=6对均满足，AUC=1.0。 # 若y_score=[0.1,0.2,0.3,0.4,0.5], y_true=[1,1,0,0,1]，则正：0.1,0.2,0.5；负：0.3,0.4；正>负对：仅0.5>0.3,0.5>0.4 → 2对，AUC=2/6≈0.333。 # 升序分组代码正确。

滴滴搜素算法实习一面 强度好大

全站热榜

创作者周榜

滴滴搜素算法实习一面强度好大