Podwójny argsort dla rang tablic NumPy

Matematyczne uzasadnienie podwójnego argsort do rangowania tablic w NumPy

Podwójne zastosowanie np.argsort(np.argsort(x)) pozwala uzyskać rangi elementów tablicy bez specjalistycznych funkcji. Działa to dla tablic z unikalnymi wartościami i uwzględnia oryginalne pozycje w przypadku duplikatów. W przeciwieństwie do scipy.stats.rankdata, która zaczyna od 1, podwójny argsort używa indeksowania od zera i metody równoważnej method='ordinal'.

Rozważmy tablicę a = [13, 0, 47, 52, 27]. Posortowana wersja s = [0, 13, 27, 47, 52]. Pierwszy argsort daje indeksy [1, 0, 4, 2, 3], drugi — rangi [1, 0, 3, 4, 2], zgodne z 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)

Wynik:

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]

Formalizacja zadania

Oznaczmy:

• a = (a_1, ..., a_N) — oryginalna tablica.
• s = (s_1, ..., s_N) — posortowana rosnąco.
• m = argsort(a) — indeksy, gdzie a_{m_i} = s_i.
• p = argsort(m) — podwójny argsort.
• r = (r_1, ..., r_N) — rangi, gdzie s_{r_i} = a_i.

Cel: udowodnić p_i = r_i dla wszystkich i.

Przy duplikatach podwójny argsort przypisuje mniejszą rangę elementowi z mniejszym oryginalnym indeksem, zapewniając unikalność rang.

Dowód krok po kroku

• Tablica m — permutacja {1, ..., N}, wszystkie m_i są unikalne: m_i ≠ m_k przy i ≠ k.

• p = argsort(m) porządkuje m rosnąco: m_{p_1} < m_{p_2} < ... < m_{p_N}, ponieważ równości są niemożliwe. Zatem m_{p_i} = i dla wszystkich i.

• Z własności argsort: a_{m_i} = s_i. Podstawmy i = p_k: a_{m_{p_k}} = s_{p_k}.

• Z kroku 2, m_{p_k} = k, więc a_k = s_{p_k}.

• To oznacza, że p_k — pozycja a_k w posortowanej tablicy s, czyli ranga: p_i = r_i.

Dowód potwierdza poprawność dla tablic dowolnego wymiaru przy stabilnym sortowaniu NumPy.

Praktyczne aspekty zastosowania

• Stabilność: NumPy argsort jest stabilny, więc przy równych elementach zachowuje kolejność według indeksów.
• Wydajność: Podwójny argsort jest szybszy niż rankdata dla dużych tablic bez konfiguracji metody.
• Ograniczenia: Działa tylko dla tablic rzeczywistych lub całkowitych; dla tekstowych — przez porządek leksykograficzny.

Lista scenariuszy użycia:

• Obliczanie percentyli w pipeline'ach data science.
• Rangowanie cech w modelach ML przed normalizacją.
• Budowanie macierzy pomyłek na podstawie przewidywanych rang.
• Analiza szeregów czasowych do wykrywania lokalnych ekstremów.

Co jest ważne

• Podwójny argsort(argsort(x)) jest równoważny rangom z indeksowaniem od zera i metodą ordinal.
• Dowód opiera się na własnościach permutacji i kompozycji argsort.
• Przy duplikatach rangi są unikalne i zależą od oryginalnej kolejności.
• Skuteczniejszy niż rankdata dla prostych przypadków bez dodatkowych parametrów.
• Odpowiedni dla middle/senior-developerów w zadaniach przetwarzania danych.

— Editorial Team