1 Sujets avancés

1.1 Le traitement des variables manquantes

A COMPLETER

1.2 Le traitement des variables continues: l’utilisation des histogrammes

L’algorithme de détermination des critères de partition (split-finding algorithm) est un enjeu de performance essentiel dans les méthodes ensemblistes. En effet, l’algorithme le plus simple qui consiste à énumérer tous les critères de partition possibles (en balayant toutes les valeurs de toutes les variables) s’avère très coûteux à utiliser dès lors que les données contiennent soit un grand nombre de variables, soit des variables continues prenant un grand nombre de valeurs. C’est pourquoi cet algorithme a fait l’objet de multiples améliorations et optimisations visant à réduire leur coût computationnel sans dégrader la qualité des critères de partition.

L’utilisation d’histogrammes (histogram-based algorithms) est une approche efficace qui permet de réduire de manière significative le coût computationnel lié à la recherche des splits optimaux en discrétisant les variables continues. Elle est proposée par toutes les implémentations courantes du gradient boosting (XGBoost, LightGBM, CatBoost et scikit-learn). Elle comprend deux caractéristiques principales:

• Discrétisation: avant le début de l’entraînement, chaque variable continue est discrétisée en un nombre limité d’intervalles (bins), construits le plus souvent à partir de ses quantiles. Ce processus est appelé binning. Par exemple, une variable continue uniformément distribuée de 0 à 100 peut être divisée en dix intervalles (\([0, 10), [10, 20), \dots, [90, 100)\)). Le nombre maximal de bins est un hyperparamètre qui peut parfois jouer un rôle important.
• Énumération restreinte: l’algorithme de détermination des critères de partition ne considère que les bornes des intervalles précédemment définies (10, 20, 30, etc. dans l’exemple précédent) et non l’ensemble des valeurs prises par les variables continues. Cette modification se traduit par une nette accélération de l’entraînement, dans la mesure où le nombre de bins est en général beaucoup plus faible que le nombre de valeurs uniques des variables continues.

1.3 Le traitement des variables catégorielles

1.3.1 Une diversité d’approches

A l’origine, les arbres CART ont été conçus pour partitionner l’espace en utilisant exclusivement des variables numériques, et ne pouvaient pas mobiliser les variables catégorielles sans un retraitement préalable. Plusieurs méthodes d’encodage (one-hot-encoding, ordinal encoding, target encoding) ont donc été développées pour surmonter ce problème en transformant les variables catégorielles en variables numériques; elles ne sont d’ailleurs pas spécifiques aux méthodes ensemblistes à base d’arbres. Depuis le milieu des années 2010, une nouvelle approche efficace et spécifique aux méthodes ensemblistes a été introduite dans les implémentations du gradient boosting (native support for categorical features). Ce paragraphe présente ces différentes approches des variables catégorielles, et précise quelle approche est proposée par les différentes implémentations.

Les trois approches d’encodage les plus courantes sont les suivantes:

• Le one-hot encoding consiste à transformer une variable catégorielle en une série de variables binaires qui représentent chacune une modalité de la variable; pour chaque observation, seule la colonne correspondant à la modalité de la variable catégorielle aura la valeur 1, et toutes les autres auront la valeur 0. Cette approche permet de représenter des catégories de manière numérique de façon très simple et sans leur attribuer un ordre. Toutefois, le one-hot encoding augmente fortement la dimensionnalité des données (ce qui ralentit l’entraînement et augmente les besoins en mémoire), et est inutilisable lorsque les variables catégorielles présentent un nombre de modalités¹.

• L’ordinal encoding consiste à attribuer un entier unique à chaque modalité d’une variable catégorielle. Par exemple, la catégorie “Sans diplôme” sera encodée par la valeur 0, la catégorie “Baccalauréat ou moins” sera encodée par 1, etc. Simple à mettre en œuvre, cette approche permet de remplacer la variable catégorielle par une unique variable numérique et est donc utile pour traiter les variables présentant un grand nombre de modalités, pour lesquelles le one-hot encoding est impraticable. Elle est particulièrement adaptée aux variables catégorielles qui sont naturellement ordonnées (exemples: niveau de diplôme, catégorie d’âge, étage d’un appartement…). En revanche, cette approche est peu adaptée aux variables non ordonnées (exemples: secteur d’activité, département, pays…) car elle introduit un ordre fictif qui peut perturber les modèles qui interprètent les entiers comme des valeurs ordonnées.

• Le target encoding consiste à remplacer chaque modalité d’une variable catégorielle par la moyenne de la variable cible pour cette modalité. Cette approche est notamment proposée par CatBoost² et par scikit-learn³. Comme l’ordinal encoding, cette approche permet d’obtenir une unique variable numérique et est donc utile pour traiter les variables présentant un grand nombre de modalités. Par ailleurs, le target encoding fonctionne bien avec la méthode des histogrammes décrite précédemment, dans la mesure où les valeurs encodées sont par construction ordonnées en fonction de leur association avec la variable cible. Toutefois, il est important d’utiliser le target encoding en lissant la moyenne ou en recourant à une validation croisée car il est sujet au surapprentissage. De plus, les implémentations existantes réalisent l’encodage une seule fois avant l’entraînement au niveau de l’ensemble des données d’entraînement, pas au niveau de chaque split; l’ordre des modalités qui résulte de l’encodage peut être peu pertinent sur certaines parties des données d’entraînement si celles-ci présentent un haut degré d’hétérogénéité.

La dernière approche, appelée support natif des variables catégorielles (native support for categorical features) n’est pas un encodage et est une spécificité des implémentations du gradient boosting. Cette approche a été introduite par LightGBM, puis reprise par XGBoost et scikit-learn. Dans cette approche, l’objectif est de déterminer le meilleur split directement à partir des modalités d’une variable catégorielle, en les séparant en deux sous-ensembles (par exemple : {‘A’, ‘B’, ‘C’} et {‘D’, ‘E’, ‘F’} pour une variable comportant six modalités). La difficulté est qu’il est souvent impossible en pratique de trouver le partitionnement optimal par une énumération exhaustive des partitions possibles, car il existe \(2^{k-1} - 1\) partitions possibles pour une variable à \(k\) modalités. C’est pourquoi le support natif des variables catégorielles repose sur une autre méthode plus efficace dont l’optimalité a été démontrée par Fisher (1958): à chaque split, les modalités sont triées selon \(-\frac{\sum_{i} g_i}{\sum_{i} h_i}\) ⁴, puis le meilleur split est choisi en testant les différentes divisions possibles de cette liste triée. Par exemple, si pour un split donné les modalités sont triées dans l’ordre ABDFEC, l’algorithme examinera les \(k-1\) splits A|BDFEC, AB|DFEC, ABD|FEC, etc. Cette approche peut être considérée comme une variante optimisée du target encoding, avec deux différences notables: l’encodage des modalités se fait à partir du gradient et de la hessienne de la fonction de perte (et non à partir de \(y\)), et cet encodage a lieu à chaque split et non une seule fois avant l’entraînement. Par ailleurs, cette approche peut rencontrer des difficultés quand les variables catégorielles comprennent un nombre très élevé des modalités (au-delà de quelques centaines).

1.3.2 Comparaison des différents approches

Déterminer quelle approche des variables catégorielles est adaptée dans une situation donnée n’est pas toujours aisé. Les cas d’usage des différentes approches peuvent être résumés comme ceci:

• le one-hot-encoding est adapté uniquement aux variables catégorielles comprenant peu de modalités;
• l’ordinal encoding est adapté aux variables catégorielles qui sont naturellement ordonnées, et ce quel que soit le nombre de modalités (car la variable catégorielle est implicitement convertie en variable numérique);
• le target encoding est adapté aux variables catégorielles comprenant un grand nombre de modalités et non naturellement ordonnées;
• le support natif des variables catégorielles est adapté à tous les types de variables catégorielles, à l’exception de celles qui comprennent un nombre très élevé des modalités (au-delà de quelques centaines).

Comparé aux autres approches, le support natif des variables catégorielles comporte plusieurs avantages: il permet de réduire le nombre de splits, d’obtenir des arbres plus simples et d’augmenter l’efficacité computationnelle de l’entraînement des arbres. Ces avantages apparaissent clairement avec un exemple⁵. Imaginons qu’on s’intéresse à une variable catégorielle prenant les modalités ABCDEF, et que sur une feuille donnée de l’arbre, le meilleur partitionnement sur cette variable soit ACF - BDE. Une approche de one-hot-encoding aura besoin de trois splits pour approximer ce partitionnement: un premier pour séparer A et BCDEF, un deuxième pour séparer C et BDEF et un troisième pour séparer F et BCDE (l’ordre des splits pouvant différer). Une approche d’ordinal encoding aura besoin de quatre splits: un split pour isoler A, un split pour isoler F, et deux splits pour isoler C (car C est au milieu de l’ordre des modalités). Enfin, une approche de target encoding aura besoin d’un nombre variable de splits, qui dépend de l’ordre des modalités dans l’encoding: si le target encoding a trié les modalités dans l’ordre ACFBDE, alors un unique split suffira; si l’ordre est très différent, alors il faudra davantage de splits. Inversement, le support natif des variables catégorielles identifiera immédiatement le partitionnement optimal, et ne fera qu’un seul split, ce qui simplifie la structure de l’arbre et accélère l’entraînement.

1.3.3 Approches intégrées aux implémentations des méthodes ensemblistes

Certaines implémentations des méthodes ensemblistes prennent en charge directement certaines des quatre approches présentées ci-dessus, auquel cas il est possible d’entraîner le modèle sur des données contenant des variables catégorielles sans preprocessing particulier; dans les autres cas, il faut préparer les données en amont de l’entraînement et de la prédiction, par exemple en utilisant un ColumnTransformer de scikit-learn (OneHotEncoder(), TargetEncoder(), OrdinalEncoder()). Le tableau et les notes ci-dessous résument quelles approches sont proposées par chaque implémentations des méthodes ensemblistes.

Table 1: Preprocessing des variables catégorielles dans les implémentations des méthodes ensemblistes

Approche	ranger	scikit-learn	XGBoost	LightGBM	CatBoost
One-hot-encoding
Ordinal encoding
Target encoding
Support natif des variables catégorielles

• ranger: le traitement des variables catégorielles (factors) est contrôlé par l’argument respect.unordered.factors, qui peut prendre trois valeurs: ignore (ordinal encoding), order (target encoding) et partition (essayer toutes les combinaisons possibles). L’usage de cet argument est détaillé dans la documentation de la fonction ranger(). L’usage de la modalité partition n’est pas recommandé. En revanche, ranger ne prend pas en charge le one-hot-encoding.

• LightGBM: cette implémentation utilise par défaut le one-hot-encoding pour les variables catégorielles comprenant 4 modalités ou moins, et le support natif des variables catégorielles pour les autres. Ce seuil peut être modifié via le paramètre max_cat_to_onehot. En revanche, LightGBM ne prend pas en charge ni l’ordinal encoding ni le target encoding.

• XGBoost: le traitement des variables catégorielles est contrôlé par l’argument enable_categorical. Si enable_categorical = True (en Python), alors XGBoost applique le support natif des variables catégorielles. Par ailleurs, le paramètre max_cat_to_onehot permet d’utiliser le one-hot-encoding pour les variables catégorielles comprenant moins de max_cat_to_onehot modalités, et le support natif pour les autres (voir la documentation). En revanche, XGBoost ne prend pas en charge ni l’ordinal encoding ni le target encoding.

• CatBoost: cette implémentation est celle qui propose le plus d’options relatives aux variables catégorielles. Par défaut, elle utilise le one-hot-encoding pour les variables catégorielles comprenant peu de modalités, et une variante de target encoding aux autres. Le seuil par défaut varie selon le type de tâche et peut être modifié via le paramètre one_hot_max_size. La documentation de CatBoost propose un notebook qui détaille les différents hyperparamètres.

• scikit-learn: l’implémentation du gradient boosting (HistGradientBoostingClassifier, HistGradientBoostingRegressor) propose le support natif des variables catégorielles. Cette implémentation ne propose pas de one-hot-encoding pour les variables catégorielles comprenant peu de modalités, et ne prend pas en charge ni l’ordinal encoding ni le target encoding.

References

Fisher, Walter D. 1958. “On Grouping for Maximum Homogeneity.” Journal of the American Statistical Association 53 (284): 789–98.

Prokhorenkova, Liudmila, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin. 2018. “CatBoost: Unbiased Boosting with Categorical Features.” Advances in Neural Information Processing Systems 31.

Footnotes

1. Il est bien sûr possible de n’encoder que les modalités les plus fréquentes, et de regrouper toutes les autres dans une seule variable binaire.

2. Le target encoding utilisé par CatBoost est présenté en détail dans Prokhorenkova et al. (2018) et sur ce billet de blog.

3. Voir cet exemple dans la documentation de scikit-learn.

4. Il s’agit de l’équation donnant le poids optimal d’une feuille terminale, avec \(\lambda = 0\).

5. Cet exemple s’appuie sur la documentation de scikit-learn.