Double argsort pour les rangs des tableaux NumPy

La justification mathématique du double argsort pour le classement des tableaux dans NumPy

L'application de np.argsort(np.argsort(x)) deux fois donne les rangs des éléments dans un tableau sans fonctions spécialisées. Cela fonctionne pour les tableaux avec des valeurs uniques et tient compte des positions originales en cas de doublons. Contrairement à scipy.stats.rankdata, qui commence à 1, le double argsort utilise une indexation basée sur zéro et est équivalent à l'approche method='ordinal'.

Considérons le tableau a = [13, 0, 47, 52, 27]. La version triée est s = [0, 13, 27, 47, 52]. Le premier argsort donne les indices [1, 0, 4, 2, 3], le second produit les rangs [1, 0, 3, 4, 2], correspondant à 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)

Sortie :

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]

Formalisation du problème

Définissons :

• a = (a_1, ..., a_N) — le tableau original.
• s = (s_1, ..., s_N) — trié par ordre croissant.
• m = argsort(a) — indices où a_{m_i} = s_i.
• p = argsort(m) — le double argsort.
• r = (r_1, ..., r_N) — rangs où s_{r_i} = a_i.

Objectif : prouver p_i = r_i pour tout i.

Avec des doublons, le double argsort attribue un rang inférieur à l'élément avec l'indice original le plus petit, garantissant des rangs uniques.

Preuve étape par étape

• Le tableau m est une permutation de {1, ..., N}, tous les m_i sont uniques : m_i ≠ m_k pour i ≠ k.

• p = argsort(m) ordonne m par ordre croissant : m_{p_1} < m_{p_2} < ... < m_{p_N}, car les égalités sont impossibles. Ainsi, m_{p_i} = i pour tout i.

• D'après la propriété de argsort : a_{m_i} = s_i. Substituons i = p_k : a_{m_{p_k}} = s_{p_k}.

• D'après l'étape 2, m_{p_k} = k, donc a_k = s_{p_k}.

• Cela signifie que p_k est la position de a_k dans le tableau trié s, c'est-à-dire le rang : p_i = r_i.

La preuve confirme la justesse pour les tableaux de toute dimension avec le tri stable de NumPy.

Aspects pratiques d'application

• Stabilité : Le argsort de NumPy est stable, donc les éléments égaux conservent leur ordre d'indice.
• Performance : Le double argsort est plus rapide que rankdata pour les grands tableaux sans personnalisation de méthode.
• Limitations : Fonctionne uniquement pour les tableaux réels ou entiers ; pour les tableaux de chaînes, utilisez l'ordre lexicographique.

Liste des scénarios d'utilisation :

• Calculer des percentiles dans les pipelines de science des données.
• Classer des caractéristiques dans les modèles de ML avant normalisation.
• Construire des matrices de confusion basées sur des rangs prédits.
• Analyser des séries temporelles pour identifier des extrema locaux.

Points clés à retenir

• Le double argsort(argsort(x)) est équivalent aux rangs basés sur zéro avec la méthode ordinale.
• La preuve repose sur les propriétés des permutations et la composition de argsort.
• Avec des doublons, les rangs sont uniques et dépendent de l'ordre original.
• Plus efficace que rankdata pour les cas simples sans paramètres supplémentaires.
• Adapté aux développeurs de niveau intermédiaire à senior dans les tâches de traitement de données.

— Editorial Team