Avant le début de la formation, les données doivent être nettoyées, transformées et souvent échantillonnées pour s'assurer que l'ensemble de données obtenu est à la fois maniable et représentatif. Le tri des algorithmes, bien qu'il soit traditionnellement associé aux opérations de base de données et aux optimisations de recherche, est également crucial à cette étape du prétraitement. En imposant un ordre logique aux points de données — que ce soit par une valeur de caractéristique, un horodatage ou une étiquette de classe — le tri des algorithmes permet de déverrouiller des stratégies d'échantillonnage efficaces qui réduisent les frais généraux de calcul et améliorent la validité statistique des ensembles de formation.

Le rôle du tri dans le prétraitement des données pour l'apprentissage automatique

Le prétraitement des données consomme une partie importante du temps dans tout projet d'apprentissage automatique. Le tri est l'une des opérations de prétraitement les plus fondamentales parce qu'il transforme des collections non ordonnées en structures qui supportent la récupération rapide et la sélection de sous-ensembles. Lorsque les données sont triées, les algorithmes peuvent exploiter la localité, réduire l'accès à la mémoire aléatoire et appliquer des techniques telles que la recherche binaire pour localiser des sous-ensembles spécifiques dans le temps logarithmique.

Gains d'efficacité dans la récupération de données

Par exemple, sélectionner le premier 1 % des transactions par valeur à partir d'une liste non triée d'un milliard d'entrées implique de scanner chaque enregistrement. Avec les données triées, la même opération se réduit à un simple calcul d'index. De même, les requêtes qui demandent tous les enregistrements dans une plage donnée peuvent être répondues dans le temps où est le nombre de résultats, plutôt que . Cette efficacité est critique lorsque l'échantillonnage est effectué de façon répétée pendant le réglage hyperparamétrique ou la validation croisée.

Permettre des techniques d'échantillonnage avancées

De nombreuses méthodes d'échantillonnage dépendent d'une représentation ordonnée de la population. L'échantillonnage stratifié nécessite le regroupement des données par strates; l'échantillonnage systématique nécessite un intervalle fixe; l'échantillonnage des réservoirs peut bénéficier d'un ordre trié pour maintenir l'équité dans les contextes de diffusion en continu.

Algorithmes de tri des clés et leur application dans l'échantillonnage des données

Différents algorithmes de tri offrent différents compromis en termes de vitesse, d'utilisation de la mémoire, de stabilité et de parallélisation. Le choix de l'algorithme peut affecter considérablement les performances globales d'un pipeline d'échantillonnage.

QuickSort: Vitesse et partitionnement

QuickSort est un algorithme de partage et de conquête qui sélectionne un pivot, divise le tableau en éléments inférieurs et supérieurs au pivot, et trie récursivement les partitions. Avec la complexité temporelle moyenne de et des facteurs de constante faible, QuickSort est souvent la valeur par défaut dans de nombreuses bibliothèques standard (par exemple, C++ , l'hybride TimSort de Python).

Cependant, QuickSort n'est pas stable et peut se dégrader en sur des partitions très déséquilibrées si une stratégie de sélection de pivot est utilisée. Des implémentations modernes comme l'introsort l'atténuer en passant à HeapSort lorsque la profondeur de récursion dépasse un seuil.

FusionSort : Tri stable et externe

MergeSort divise les données en petits morceaux, trie chaque morceau, puis les fusionne. Sa performance et stabilité la pire des situations (préservant l'ordre relatif des éléments égaux) le rendent idéal pour les ensembles de données qui ne s'intègrent pas entièrement dans la RAM. MergeSort est la base de nombreux algorithmes de tri externes utilisés dans les systèmes de bases de données et les cadres distribués comme Apache Hadoop et Spark. Lorsqu'on échantillonne à partir d'un ensemble de données qui réside sur disque, une approche basée sur MergeSort peut trier les données de façon en streaming, ne consommant qu'une fraction de la mémoire.

La stabilité est cruciale lorsque des clés secondaires existent. Par exemple, si vous triez par horodatage et puis par l'identifiant du client, un tri stable préserve la commande d'horodatage pour les enregistrements avec le même identifiant du client. Ceci est essentiel pour l'échantillonnage stratifié série chronologique où vous devez maintenir l'ordre chronologique dans chaque strate.

HeapSort : Performance garantie

HeapSort construit un heap max (ou min-heap) à partir des données et extrait à plusieurs reprises l'élément le plus important. Il fonctionne dans le temps le plus défavorable et n'utilise que espace auxiliaire. Bien que plus lent en pratique que QuickSort en raison de la mauvaise localisation du cache, HeapSort fournit une limite du pire cas garantie qui est valable dans les systèmes d'échantillonnage en temps réel où la latence doit être prévisible. Par exemple, lorsque l'échantillonnage d'un nombre fixe d'enregistrements d'un flux de données continu, un heap peut maintenir un échantillon trié sans avoir à trier l'ensemble des données.

Tri de comptage et radix Tri : Tri non comparatif pour entiers

Lorsque les valeurs clés sont des entiers avec une plage limitée (p. ex. ID de classe 0–100, caractéristiques quantifiées), des algorithmes de tri non comparatifs comme le tri de comptage et le tri de radix peuvent atteindre une complexité temporelle linéaire . Ces algorithmes sont particulièrement utiles pour l'échantillonnage stratifié lorsque les strates sont définies par des caractéristiques catégoriques. En comptant les occurrences de chaque catégorie et en plaçant les enregistrements directement dans des seaux, ils éliminent les frais généraux du tri de comparaison.

Pour les données à haute dimension, le tri de seau ou le tri de bin peuvent être combinés avec ces méthodes pour séparer rapidement les données pour l'échantillonnage stratifié ou en grappe.

Méthodes d'échantillonnage fondées sur le tri en détail

Échantillonnage stratifié avec étiquettes triées

Sans trier, l'échantillonnage stratifié nécessite soit des tables de hachage pour chaque strate, soit des passages multiples sur les données. Le tri de l'ensemble de données par la clé de strate (p. ex., étiquette de classe) permet de diviser les données en blocs contigus, une par strate. Ensuite, à l'intérieur de chaque bloc, un simple échantillon aléatoire peut être tiré en sélectionnant des éléments à des décalages aléatoires. Cette approche réduit la complexité de par strate à une seule sorte de l'ensemble des données suivies par opérations d'indice par élément d'échantillon.

Dans Python, cela est facilement accompli en triant un DataFrame avec et puis en utilisant . Cependant, trier un DataFrame entier peut être coûteux; pour les très grands ensembles de données, scikit-learn StratifiedShuffleSplit fournit une implémentation optimisée qui évite un tri complet en utilisant la partition basée sur le hash.

Échantillonnage systématique après tri

Pour s'assurer que l'échantillon est représentatif, l'ensemble de données doit d'abord être trié par une clé qui est en corrélation avec les variables d'intérêt. Par exemple, lorsque l'échantillonnage des dossiers des clients pour une enquête, le tri par âge permet de s'assurer que l'échantillon systématique couvre toutes les tranches d'âge proportionnellement. L'étape de tri garantit que l'intervalle d'échantillonnage est appliqué à un ordre significatif, réduisant ainsi le risque de biais de périodicité qui pourrait survenir si l'ensemble de données n'était pas ordonné.

L'échantillonnage systématique après tri est particulièrement efficace pour les ensembles de données de grande taille et stockées de façon séquentielle (p. ex., fichiers journaux, archives de séries chronologiques) parce que l'ordre trié s'harmonise avec l'ordre de stockage physique, minimisant ainsi les E/S aléatoires.

Échantillonnage du réservoir et rôle du tri

L'échantillonnage du réservoir est une famille d'algorithmes pour sélectionner un échantillon aléatoire de taille fixe à partir d'un flux de longueur inconnue. Bien que l'échantillonnage du réservoir ne nécessite pas nécessairement de tri, le tri peut améliorer ses performances de deux façons. Premièrement, si le flux arrive dans un ordre biaisé (par exemple, les éléments initiaux diffèrent des éléments ultérieurs), le tri du réservoir après chaque insertion peut aider à maintenir un échantillon représentatif en permettant une sélection pondérée. Deuxièmement, pour l'échantillonnage du réservoir distribué, chaque noeud peut trier son échantillon local avant de fusionner, simplifier l'agrégation finale.

Pour les ensembles de données hors ligne, un réservoir trié peut être construit en balançant les données une fois et en maintenant une liste triée d'indices échantillonnés, permettant un ajout et une suppression efficaces.Les bibliothèques comme Python comptent sur le tri interne pour produire un ordre cohérent d'éléments sélectionnés.

Avantages pratiques et compromis

Complexité informatique réduite

Le meilleur avantage du tri est la réduction de la complexité temporelle pour les opérations en aval. L'échantillonnage à partir d'un tableau trié peut être pour l'accès aléatoire ou pour les requêtes de portée. Sans tri, beaucoup de ces opérations nécessiteraient des analyses. Pour les ensembles de données à des millions de points, cela peut se traduire par des heures de calcul sauvegardées lors de la sélection itérative ou de la validation croisée des modèles.

Cependant, l'étape de tri elle-même ajoute complexité. Dans la pratique, cela est acceptable parce que le tri est un coût unique qui peut être amorti sur de nombreuses opérations d'échantillonnage. Pour des ensembles de données extrêmement importants, des algorithmes de tri distribués (p. ex., le tri basé sur MapReduce) sont disponibles et le coût peut être parallélisé entre les grappes.

Mémoire et considérations d'E/S

Le tri en mémoire exige que l'ensemble des données soit chargé en RAM, ce qui est souvent invraisemblable pour les données à échelle de téraoctet. Les algorithmes de tri externes, tels que ceux mis en place dans les systèmes de base de données, traitent les données hors-cœur en utilisant des stratégies basées sur la fusion. Lorsqu'on effectue un échantillonnage à partir de ces ensembles de données, il est généralement plus efficace d'effectuer un tri partiel – par exemple, trier seulement les clés nécessaires à la stratification – et ensuite diffuser les données.

Pour les données de séries chronologiques, le tri par horodatage peut également améliorer la compression et réduire l'empreinte de stockage, ce qui profite indirectement aux performances d'E/S lors de l'échantillonnage.

Exactitude vs Surtête

Le triage améliore l'efficacité de l'échantillonnage, mais il peut introduire un biais si l'ordre de tri est utilisé par inadvertance comme substitut du hasard. Par exemple, le tri par une clé non aléatoire et ensuite le premier éléments ne sont pas une méthode d'échantillonnage valide; il crée une sélection déterministe qui peut ne pas représenter la population. Le tri doit toujours être combiné avec un mécanisme de sélection aléatoire approprié.

Dans la pratique, les avantages l'emportent de loin sur les coûts lorsque la stratégie d'échantillonnage exige des données triées (p. ex., échantillonnage stratifié ou systématique).

Exemples et cas d'utilisation dans le monde réel

Formation Ensembles de données équilibrés

Les ensembles de données de classification asymétriques (p. ex. détection de fraude avec 99 % de la normale, 1 % de la fraude) nécessitent souvent un échantillonnage stratifié pour préserver la classe minoritaire. Le tri de l'ensemble de données par étiquette de classe permet d'extraire rapidement tous les échantillons de fraude. Ensuite, sous-échantillonnage de la classe majoritaire ou suréchantillonnage de la classe minoritaire devient simple. Dans la pratique, les data scientists utilisent avec le paramètre , qui trie en interne les étiquettes de classe avant de diviser.

Échantillonnage des données de la série chronologique

Pour les données de séries chronologiques, comme les relevés de capteurs ou les transactions financières, il est essentiel de trier par horodatage pour éviter les fuites de données. Un ordre trié permet de prélever des échantillons de formation à partir d'une fenêtre temporelle contiguë et de faire en sorte que les ensembles de validation proviennent d'une période ultérieure.

Échantillonnage distribué à grande échelle

Dans les cadres de calcul distribués comme Apache Spark, l'échantillonnage est souvent effectué lors de la mise en place de données. Le tri par touches de partition avant l'échantillonnage améliore l'équilibrage de la charge et réduit les frais généraux du réseau. La méthode Spark pour l'échantillonnage stratifié des premières données de groupes par la clé de strate à l'aide d'un partitionneur de hachage, essentiellement un tri distribué sur la clé.

Pour l'apprentissage automatique accéléré par GPU, des bibliothèques comme RAPIDS cudf trient les données sur le GPU en utilisant le tri parallèle radix, réalisant des vitesses des ordres de grandeur plus rapides que le tri CPU. Ceci permet un échantillonnage en temps quasi réel des données en streaming pour les modèles d'apprentissage en ligne.

Considérations avancées : Tri dans les environnements distribués et GPU

Les algorithmes comme Sample Trient partition des données par les clés d'échantillonnage et ensuite redistribuent les enregistrements à la partition correcte. C'est la base du tri parallèle dans les bases de données et les cadres de données massives. Pour l'échantillonnage, si l'objectif est d'obtenir un échantillon stratifié, la même logique de partitionnement peut être réutilisée pour s'assurer que chaque strate est traitée sur un seul nœud, réduisant le trafic réseau croisé.

Le tri GPU est devenu de plus en plus pertinent pour les pipelines d'apprentissage profond. La bibliothèque CUB et la cuDF de NVIDIA mettent en œuvre des radix haute performance et fusionnent des sortes qui trient des milliards d'éléments en secondes. Combinés à des échantillonnages en ligne, ces outils permettent de former des modèles sur des sous-ensembles échantillonnés dynamiquement qui sont toujours triés en mémoire, permettant une création efficace de mini-batch avec un latence minimale.

Lors du choix d'un algorithme de tri pour un pipeline d'échantillonnage, les praticiens devraient tenir compte de la taille des données, du type de clé, du budget de mémoire et du parallélisme. Il n'existe pas de solution unique; il est recommandé de comparer l'étape de tri sur du matériel représentatif pour éviter les goulets d'étranglement.

Les pensées finales

Les algorithmes de tri sont bien plus qu'un concept de manuel, ils sont un outil pratique d'échantillonnage efficace, évolutif et statistiquement rationnel des données dans l'apprentissage automatique. De la stratification des distributions de classes à l'accélération de l'analyse des séries chronologiques, la capacité de commander des méthodes d'échantillonnage déverrouille les données qui, autrement, ne seraient pas pratiques pour les ensembles de données modernes.