Informations de référence techniques sur l’algorithme Arbres de décision Microsoft

L’algorithme Microsoft Decision Trees est un algorithme hybride qui incorpore différentes méthodes pour créer une arborescence et prend en charge plusieurs tâches analytiques, notamment la régression, la classification et l’association. L’algorithme Microsoft Decision Trees prend en charge la modélisation des attributs discrets et continus.

Cette rubrique explique l’implémentation de l’algorithme, explique comment personnaliser le comportement de l’algorithme pour différentes tâches et fournit des liens vers des informations supplémentaires sur l’interrogation des modèles d’arbre de décision.

Implémentation de l’algorithme d’arbres de décision

L’algorithme Microsoft Decision Trees applique l’approche bayésienne pour apprendre des modèles d’interaction causale en obtenant des distributions postérieures approximatives pour les modèles. Pour obtenir une explication détaillée de cette approche, consultez le document sur le site Microsoft Research, par Structure et Apprentissage des paramètres.

La méthodologie d’évaluation de la valeur d’information des a priori nécessaires à l’apprentissage est basée sur l’hypothèse d’équivalence de vraisemblance. Cette hypothèse indique que les données ne doivent pas aider à discriminer les structures réseau qui représentent autrement les mêmes assertions d’indépendance conditionnelle. Chaque cas est supposé avoir un seul réseau antérieur bayésien et une seule mesure de confiance pour ce réseau.

À l’aide de ces réseaux précédents, l’algorithme calcule ensuite les probabilités postérieures relatives des structures réseau en fonction des données d’apprentissage actuelles et identifie les structures réseau qui ont les probabilités postérieures les plus élevées.

L’algorithme Microsoft Decision Trees utilise différentes méthodes pour calculer le meilleur arbre. La méthode utilisée dépend de la tâche, qui peut être une régression linéaire, une classification ou une analyse d’association. Un modèle unique peut contenir plusieurs arborescences pour différents attributs prédictibles. De plus, chaque arborescence peut contenir plusieurs branches, en fonction du nombre d’attributs et de valeurs présents dans les données. La forme et la profondeur de l’arborescence créées dans un modèle particulier dépendent de la méthode de scoring et d’autres paramètres utilisés. Les modifications apportées aux paramètres peuvent également affecter l’endroit où les nœuds sont fractionnés.

Construction de l'arbre

Lorsque l’algorithme Microsoft Decision Trees crée l’ensemble de valeurs d’entrée possibles, il effectue une sélection de fonctionnalités pour identifier les attributs et les valeurs qui fournissent le plus d’informations, et supprime de la considération les valeurs qui sont très rares. L’algorithme regroupe également des valeurs dans des bacs pour créer des regroupements de valeurs qui peuvent être traités en tant qu’unité pour optimiser les performances.

Une arborescence est générée en déterminant les corrélations entre une entrée et le résultat ciblé. Une fois que tous les attributs ont été corrélés, l’algorithme identifie l’attribut unique qui sépare le mieux les résultats. Ce point de la meilleure séparation est mesuré à l’aide d’une équation qui calcule le gain d’informations. L’attribut qui a le meilleur score pour le gain d’informations est utilisé pour diviser les cas en sous-ensembles, qui sont ensuite analysés de manière récursive par le même processus, jusqu’à ce que l’arborescence ne puisse plus être fractionnée.

L’équation exacte utilisée pour évaluer le gain d’informations dépend des paramètres définis lors de la création de l’algorithme, du type de données de la colonne prévisible et du type de données de l’entrée.

Entrées discrètes et continues

Lorsque l’attribut prédictible est discret et que les entrées sont discrètes, le comptage des résultats par entrée est une question de création d’une matrice et de génération de scores pour chaque cellule de la matrice.

Toutefois, lorsque l’attribut prédictible est discret et que les entrées sont continues, les entrées des colonnes continues sont automatiquement discrétisées. Vous pouvez accepter la valeur par défaut, et Analysis Services déterminera le nombre optimal de partitions, ou vous pouvez contrôler la façon dont les entrées continues sont discrétisées en définissant les propriétés DiscretizationMethod et DiscretizationBucketCount. Pour plus d’informations, consultez Modifier la discrétisation d’une colonne dans un modèle d’exploration de données.

Pour les attributs continus, l’algorithme utilise la régression linéaire pour déterminer où un arbre de décision fractionne.

Lorsque l’attribut prédictible est un type de données numérique continu, la sélection de caractéristiques est également appliquée aux sorties, afin de réduire le nombre possible de résultats et de générer le modèle plus rapidement. Vous pouvez modifier le seuil de sélection des fonctionnalités et ainsi augmenter ou diminuer le nombre de valeurs possibles en définissant le paramètre MAXIMUM_OUTPUT_ATTRIBUTES.

Pour obtenir une explication plus détenue sur le fonctionnement de l’algorithme Microsoft Decision Trees avec des colonnes prévisibles discrètes, consultez Learning Bayesian Networks : The Combination of Knowledge and Statistical Data. Pour plus d’informations sur le fonctionnement de l’algorithme Arbres de décision Microsoft avec une colonne prévisible continue, consultez l’annexe des modèles d’arborescences régressives automatiques pour Time-Series Analysis.

Méthodes de scoring et sélection des fonctionnalités

L’algorithme Microsoft Decision Trees propose trois formules pour l'évaluation du gain d'information : l’entropie de Shannon, le réseau bayésien avec un priori K2, et le réseau bayésien avec une distribution uniforme de Dirichlet des priors. Les trois méthodes sont bien établies dans le champ d’exploration de données. Nous vous recommandons d’expérimenter différents paramètres et méthodes de scoring pour déterminer les meilleurs résultats. Pour plus d’informations sur ces méthodes de scoring, consultez Sélection des fonctionnalités.

Tous les algorithmes d’exploration de données Analysis Services utilisent automatiquement la sélection des fonctionnalités pour améliorer l’analyse et réduire la charge de traitement. La méthode utilisée pour la sélection de fonctionnalités dépend de l’algorithme utilisé pour générer le modèle. Les paramètres d’algorithme qui contrôlent la sélection des fonctionnalités pour un modèle d’arbre de décision sont MAXIMUM_INPUT_ATTRIBUTES et MAXIMUM_OUTPUT.

Extensibilité et performance

La classification est une stratégie d’exploration de données importante. En règle générale, la quantité d’informations nécessaires pour classer les cas augmente en proportion directe du nombre d’enregistrements d’entrée. Cela limite la taille des données qui peuvent être classifiées. L’algorithme Microsoft Decision Trees utilise les méthodes suivantes pour résoudre ces problèmes, améliorer les performances et éliminer les restrictions de mémoire :

• Sélection de fonctionnalités pour optimiser la sélection d’attributs.

• Notation bayésienne pour contrôler la croissance des arbres.

• Optimisation du binning pour les attributs continus.

• Regroupement dynamique de valeurs d’entrée pour déterminer les valeurs les plus importantes.

L’algorithme Microsoft Decision Trees est rapide et évolutif et a été conçu pour être facilement parallélisé, ce qui signifie que tous les processeurs fonctionnent ensemble pour créer un modèle unique et cohérent. La combinaison de ces caractéristiques rend le classifieur d’arbre de décision un outil idéal pour l’exploration de données.

Si les contraintes de performances sont graves, vous pouvez améliorer le temps de traitement pendant l’entraînement d’un modèle d’arbre de décision à l’aide des méthodes suivantes. Toutefois, si vous le faites, sachez que l’élimination des attributs pour améliorer les performances de traitement modifie les résultats du modèle et peut-être le rendre moins représentatif de la population totale.

• Augmentez la valeur du paramètre COMPLEXITY_PENALTY pour limiter la croissance de l’arborescence.

• Limitez le nombre d’éléments dans les modèles d’association pour limiter le nombre d’arbres générés.

• Augmentez la valeur du paramètre MINIMUM_SUPPORT pour éviter le surajustement.

• Limitez le nombre de valeurs discrètes pour n’importe quel attribut à 10 ou moins. Vous pouvez essayer de regrouper des valeurs de différentes manières dans différents modèles.

  Remarque

  Vous pouvez utiliser les outils d’exploration de données disponibles dans SQL Server 2014 Integration Services (SSIS) pour visualiser la distribution des valeurs dans vos données et regrouper vos valeurs correctement avant de commencer l’exploration de données. Pour plus d’informations, consultez la tâche de profilage des données ainsi que le module de visualisation. Vous pouvez également utiliser les compléments d’exploration de données pour Excel 2007 pour explorer, regrouper et réétiqueter des données dans Microsoft Excel.

Personnalisation de l’algorithme d’arbres de décision

L’algorithme Microsoft Decision Trees prend en charge les paramètres qui affectent les performances et la précision du modèle d’exploration de données résultant. Vous pouvez également définir des indicateurs de modélisation sur les colonnes du modèle d’exploration de données ou les colonnes de structure d’exploration de données pour contrôler la façon dont les données sont traitées.

Définition des paramètres d’algorithme

Le tableau suivant décrit les paramètres que vous pouvez utiliser avec l’algorithme Microsoft Decision Trees.

PÉNALITÉ_COMPLEXITÉ
Contrôle la croissance de l’arbre de décision. Une valeur faible augmente le nombre de fractionnements, et une valeur élevée diminue le nombre de fractionnements. La valeur par défaut est basée sur le nombre d’attributs d’un modèle particulier, comme décrit dans la liste suivante :

• Pour 1 à 9 attributs, la valeur par défaut est 0,5.

• Pour les attributs 10 à 99, la valeur par défaut est 0,9.

• Pour 100 attributs ou plus, la valeur par défaut est 0,99.

FORCE_REGRESSOR
Force l’algorithme à utiliser les colonnes spécifiées comme régresseurs, quelle que soit l’importance des colonnes calculées par l’algorithme. Ce paramètre est utilisé uniquement pour les arbres de décision qui prédisent un attribut continu.

[Disponible uniquement dans certaines éditions de SQL Server ]

ATTRIBUTS_D'ENTRÉE_MAXIMAUX
Définit le nombre d’attributs d’entrée que l’algorithme peut gérer avant d’appeler la sélection de fonctionnalités.

La valeur par défaut est 255.

Définissez cette valeur sur 0 pour désactiver la sélection des fonctionnalités.

[Disponible uniquement dans certaines éditions de SQL Server]

MAXIMUM_OUTPUT_ATTRIBUTES
Définit le nombre d’attributs de sortie que l’algorithme peut gérer avant d’appeler la sélection des fonctionnalités.

La valeur par défaut est 255.

Définissez cette valeur sur 0 pour désactiver la sélection des fonctionnalités.

[Disponible uniquement dans certaines éditions de SQL Server]

MINIMUM_SUPPORT
Détermine le nombre minimal de feuilles requis pour générer une division dans l'arbre de décision.

La valeur par défaut est 10.

Vous devrez peut-être augmenter cette valeur si le jeu de données est très volumineux, pour éviter le surentraînement.

SCORE_METHOD
Détermine la méthode utilisée pour calculer le score de fractionnement. Les options suivantes sont disponibles :

La valeur par défaut est 4 ou BDE.

Pour obtenir une explication de ces méthodes de scoring, consultez Sélection des fonctionnalités.

MÉTHODE_DE_PARTAGE
Détermine la méthode utilisée pour fractionner le nœud. Les options suivantes sont disponibles :

La valeur par défaut est 3.

Indicateurs de modélisation

L’algorithme Microsoft Decision Trees prend en charge les indicateurs de modélisation suivants. Lorsque vous créez la structure d’exploration de données ou le modèle d’exploration de données, vous définissez des indicateurs de modélisation pour spécifier la façon dont les valeurs de chaque colonne sont gérées pendant l’analyse. Pour plus d’informations, consultez Indicateurs de modélisation (exploration de données).

Régresseurs dans les modèles d’arbre de décision

Même si vous n’utilisez pas l’algorithme Microsoft Linear Regression, tout modèle d’arbre de décision qui a des entrées et sorties numériques continues peut potentiellement inclure des nœuds qui représentent une régression sur un attribut continu.

Vous n’avez pas besoin de spécifier qu’une colonne de données numériques continues représente un régresseur. L’algorithme Microsoft Decision Trees utilise automatiquement la colonne comme régresseur potentiel et partitionne le jeu de données dans des régions avec des modèles significatifs, même si vous ne définissez pas l’indicateur REGRESSOR sur la colonne.

Toutefois, vous pouvez utiliser le paramètre FORCE_REGRESSOR pour garantir que l’algorithme utilisera un régresseur particulier. Ce paramètre ne peut être utilisé qu’avec les algorithmes Microsoft Decision Trees et Microsoft Linear Regression. Lorsque vous définissez l’indicateur de modélisation, l’algorithme tente de trouver des équations de régression de la forme a*C1 + b*C2 + ... pour ajuster les modèles dans les nœuds de l’arborescence. La somme des résidus est calculée et si l’écart est trop grand, un fractionnement est forcé dans l’arbre.

Par exemple, si vous prévoyez un comportement d’achat client à l’aide de Income en tant qu’attribut et que vous définissez l’indicateur de modélisation REGRESSOR sur la colonne, l’algorithme essaie d’abord d’ajuster les valeurs de revenu à l’aide d’une formule de régression standard. Si l’écart est trop grand, la formule de régression est abandonnée et l’arborescence sera fractionnée sur un autre attribut. L’algorithme d’arbre de décision tentera ensuite d’ajuster un régresseur pour le revenu dans chacune des branches après la division.

Spécifications

Un modèle d’arbre de décision doit contenir une colonne clé, des colonnes d’entrée et au moins une colonne prévisible.

Colonnes d’entrée et prévisionnelles

L’algorithme Microsoft Decision Trees prend en charge les colonnes d’entrée spécifiques et les colonnes prévisibles répertoriées dans le tableau suivant. Pour plus d’informations sur ce que signifient les types de contenu lorsqu’ils sont utilisés dans un modèle d’exploration de données, consultez Content Types (Exploration de données).

Voir aussi

Algorithme d’arbres de décision Microsoft
Exemples de requêtes de modèle d’arbre de décision
Contenu du modèle d’exploration de données pour les modèles d’arbre de décision (Analysis Services - Exploration de données)