NumPy 数组排名的双重 argsort

NumPy中双重argsort实现数组排名的数学原理

应用np.argsort(np.argsort(x))两次即可获得数组中元素的排名，无需专用函数。该方法适用于具有唯一值的数组，并能处理重复值的原始位置。与从1开始计数的scipy.stats.rankdata不同，双重argsort使用零基索引，相当于method='ordinal'方法。

考虑数组a = [13, 0, 47, 52, 27]。排序后的版本为s = [0, 13, 27, 47, 52]。第一次argsort给出索引[1, 0, 4, 2, 3]，第二次得到排名[1, 0, 3, 4, 2]，与rankdata(a, method='ordinal') - 1匹配。

import numpy as np
from scipy.stats import rankdata

a = np.array([13, 0, 47, 52, 27])
print("a:", a)
s = np.sort(a)
print("s = sort(a):", s)
m = np.argsort(a)
print("m = argsort(a):", m)
p = np.argsort(m)
print("p = argsort(argsort(a)):", p)
r = rankdata(a, method="ordinal") - 1
print("r = rank(a):", r)

输出：

a: [13 0 47 52 27]
s = sort(a): [0 13 27 47 52]
m = argsort(a): [1 0 4 2 3]
p = argsort(argsort(a)): [1 0 3 4 2]
r = rank(a): [1 0 3 4 2]

问题形式化

定义：

• a = (a_1, ..., a_N) — 原始数组。
• s = (s_1, ..., s_N) — 升序排序后的数组。
• m = argsort(a) — 索引，其中a_{m_i} = s_i。
• p = argsort(m) — 双重argsort。
• r = (r_1, ..., r_N) — 排名，其中s_{r_i} = a_i。

目标：证明对所有i，p_i = r_i。

对于重复值，双重argsort将较低排名分配给原始索引较小的元素，确保排名唯一。

逐步证明

• 数组m是{1, ..., N}的一个排列，所有m_i唯一：对于i ≠ k，m_i ≠ m_k。

• p = argsort(m)将m按升序排列：m_{p_1} < m_{p_2} < ... < m_{p_N}，因为不可能有相等情况。因此，对所有i，m_{p_i} = i。

• 根据argsort属性：a_{m_i} = s_i。代入i = p_k：a_{m_{p_k}} = s_{p_k}。

• 从步骤2，m_{p_k} = k，所以a_k = s_{p_k}。

• 这意味着p_k是a_k在排序数组s中的位置，即排名：p_i = r_i。

该证明确认了对于任何维度的数组，使用NumPy的稳定排序都是正确的。

实际应用方面

• 稳定性：NumPy argsort是稳定的，因此相等元素保持其索引顺序。
• 性能：对于大型数组，双重argsort比rankdata更快，无需方法定制。
• 限制：仅适用于实数或整数数组；对于字符串数组，使用字典顺序。

使用场景列表：

• 在数据科学流程中计算百分位数。
• 在机器学习模型中排名特征以进行归一化。
• 基于预测排名构建混淆矩阵。
• 分析时间序列以识别局部极值。

关键要点

• 双重argsort(argsort(x))相当于使用序数方法的零基排名。
• 证明依赖于排列属性和argsort组合。
• 对于重复值，排名唯一且取决于原始顺序。
• 对于简单情况，比rankdata更高效，无需额外参数。
• 适合中高级开发人员在数据处理任务中使用。

— Editorial Team