Doppel-Argsort für Ränge von NumPy-Arrays

Die mathematische Logik hinter doppeltem Argsort für Array-Rangierung in NumPy

Die Anwendung von np.argsort(np.argsort(x)) zweimal liefert Elementränge in einem Array ohne spezialisierte Funktionen. Dies funktioniert für Arrays mit eindeutigen Werten und berücksichtigt bei Duplikaten die ursprünglichen Positionen. Im Gegensatz zu scipy.stats.rankdata, das bei 1 beginnt, verwendet doppeltes Argsort nullbasierte Indizierung und entspricht dem method='ordinal'-Ansatz.

Betrachten Sie das Array a = [13, 0, 47, 52, 27]. Die sortierte Version ist s = [0, 13, 27, 47, 52]. Das erste argsort liefert Indizes [1, 0, 4, 2, 3], das zweite ergibt Ränge [1, 0, 3, 4, 2], was mit rankdata(a, method='ordinal') - 1 übereinstimmt.

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)

Ausgabe:

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]

Das Problem formalisieren

Definitionen:

• a = (a_1, ..., a_N) — das ursprüngliche Array.
• s = (s_1, ..., s_N) — aufsteigend sortiert.
• m = argsort(a) — Indizes, wo a_{m_i} = s_i.
• p = argsort(m) — das doppelte Argsort.
• r = (r_1, ..., r_N) — Ränge, wo s_{r_i} = a_i.

Ziel: Beweisen, dass p_i = r_i für alle i gilt.

Bei Duplikaten weist doppeltes Argsort dem Element mit dem kleineren ursprünglichen Index einen niedrigeren Rang zu, was eindeutige Ränge sicherstellt.

Schritt-für-Schritt-Beweis

• Array m ist eine Permutation von {1, ..., N}, alle m_i sind eindeutig: m_i ≠ m_k für i ≠ k.

• p = argsort(m) ordnet m aufsteigend: m_{p_1} < m_{p_2} < ... < m_{p_N}, da Gleichheiten unmöglich sind. Somit gilt m_{p_i} = i für alle i.

• Aus der Argsort-Eigenschaft: a_{m_i} = s_i. Ersetze i = p_k: a_{m_{p_k}} = s_{p_k}.

• Aus Schritt 2: m_{p_k} = k, also a_k = s_{p_k}.

• Das bedeutet, p_k ist die Position von a_k im sortierten Array s, also der Rang: p_i = r_i.

Der Beweis bestätigt die Korrektheit für Arrays beliebiger Dimension mit NumPys stabiler Sortierung.

Praktische Anwendungsaspekte

• Stabilität: NumPy argsort ist stabil, daher behalten gleiche Elemente ihre Indexreihenfolge.
• Performance: Doppeltes Argsort ist schneller als rankdata für große Arrays ohne Methodenanpassung.
• Einschränkungen: Funktioniert nur für reelle oder ganzzahlige Arrays; für String-Arrays verwenden Sie lexikografische Ordnung.

Anwendungsszenarien:

• Berechnung von Perzentilen in Data-Science-Pipelines.
• Rangierung von Features in ML-Modellen vor der Normalisierung.
• Erstellung von Konfusionsmatrizen basierend auf vorhergesagten Rängen.
• Analyse von Zeitreihen zur Identifizierung lokaler Extrema.

Wichtige Erkenntnisse

• Doppeltes argsort(argsort(x)) entspricht nullbasierten Rängen mit der ordinalen Methode.
• Der Beweis basiert auf Permutationseigenschaften und Argsort-Komposition.
• Bei Duplikaten sind Ränge eindeutig und hängen von der ursprünglichen Reihenfolge ab.
• Effizienter als rankdata für einfache Fälle ohne zusätzliche Parameter.
• Geeignet für mittlere bis erfahrene Entwickler in Datenverarbeitungsaufgaben.

— Editorial Team