Dvojitý argsort pro rangy NumPy polí

Matematické zdůvodnění dvojitého argsort pro řazení polí v NumPy

Dvojité použití np.argsort(np.argsort(x)) umožňuje získat pořadí prvků pole bez specializovaných funkcí. Toto funguje pro pole s jedinečnými hodnotami a bere v úvahu původní pozice při duplikátech. Na rozdíl od scipy.stats.rankdata, která začíná od 1, dvojitý argsort používá nulovou indexaci a metodu ekvivalentní method='ordinal'.

Uvažujme pole a = [13, 0, 47, 52, 27]. Seřazená varianta s = [0, 13, 27, 47, 52]. První argsort dává indexy [1, 0, 4, 2, 3], druhý — pořadí [1, 0, 3, 4, 2], shodné s 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)

Výstup:

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]

Formalizace úlohy

Označme:

• a = (a_1, ..., a_N) — původní pole.
• s = (s_1, ..., s_N) — seřazené vzestupně.
• m = argsort(a) — indexy, kde a_{m_i} = s_i.
• p = argsort(m) — dvojitý argsort.
• r = (r_1, ..., r_N) — pořadí, kde s_{r_i} = a_i.

Cíl: dokázat p_i = r_i pro všechna i.

Při duplikátech dvojitý argsort přiřadí menší pořadí prvku s menším původním indexem, zajišťuje jedinečnost pořadí.

Krok za krokem důkaz

• Pole m — permutace {1, ..., N}, všechna m_i jsou jedinečná: m_i ≠ m_k při i ≠ k.

• p = argsort(m) uspořádá m vzestupně: m_{p_1} < m_{p_2} < ... < m_{p_N}, protože rovnosti nejsou možné. Tudíž m_{p_i} = i pro všechna i.

• Z vlastnosti argsort: a_{m_i} = s_i. Dosadíme i = p_k: a_{m_{p_k}} = s_{p_k}.

• Podle kroku 2, m_{p_k} = k, proto a_k = s_{p_k}.

• To znamená, že p_k — pozice a_k v seřazeném poli s, tj. pořadí: p_i = r_i.

Důkaz potvrzuje správnost pro pole libovolné dimenze při stabilním řazení NumPy.

Praktické aspekty použití

• Stabilita: NumPy argsort je stabilní, proto při stejných prvcích se zachovává pořadí podle indexů.
• Výkon: Dvojitý argsort je rychlejší než rankdata pro velká pole bez nastavení metody.
• Omezení: Funguje pouze pro reálná nebo celočíselná pole; pro řetězcová — přes lexikografické řazení.

Seznam scénářů použití:

• Výpočet percentilů v data science pipeline.
• Řazení feature v ML modelech před normalizací.
• Konstrukce confusion matrix podle předpovězených pořadí.
• Analýza časových řad pro identifikaci lokálních extrémů.

Co je důležité

• Dvojitý argsort(argsort(x)) je ekvivalentní pořadí s nulovou indexací a ordinal-metodou.
• Důkaz se opírá o vlastnosti permutací a kompozici argsort.
• Při duplikátech jsou pořadí jedinečná a závisí na původním pořadí.
• Efektivnější než rankdata pro jednoduché případy bez dalších parametrů.
• Vhodné pro middle/senior-vývojáře v úlohách zpracování dat.

— Editorial Team