Le grand intérêt des arbres de décision est qu'ils combinent l'approche logique et l'approche statistique, pour donner un modèle expressif et lisible flou (c'est à dire, probabiliste et non déterministe). Ainsi ils produisent un modèle qui peut être traduit sous forme de règles, exprimant une conditionnalité complexe (avec disjonctions) des valeurs discrètes à prédire.

Exemple d'arbre de décision

select ciel
  case soleil: select humidité
      case elevée : return "non"; break;
      case normale : return "oui"; break;
 
  case couvert : return "oui"; break;
 
  case pluie: select vent
      case fort: return "non"; break;
      case faible: return "oui"; break
      

Expression sous forme logique (règle) :

(ciel==soleil et humidité==normale) ou (ciel==couvert) ou (ciel==pluie et vent==faible)

• fonction cible (valeurs à prédire) à valeurs discrètes
• expression disjonctive vraisemblable
• erreurs possible dans les exemples (règles floues les supportent mieux)
• valeurs “causes” ou précurseurs de type catégoriel

• identifier l'attribut le plus clivant; le mettre à la racine, avec chacune de ses valeurs potentiel comme noeud fils
• classer les exemples dans les noeuds fils
• si tous les exemples dans un noeud fils sont homogènes, c'est à dire sa valeur semble filtrer à une seule valeur de la variable dépendante, affecter cette valeur au noeud;
• sinon, étendre en lui rajoutant des noeuds fils pour ses valeurs potentielles et refaire une évaluation, etc.

Comment juger si un attribut est plus clivant qu'un autre? Utiliser l'entropie, ou contenu en information (son contraire).

• Entropie : S = -p \log_2 p - (1-p) \log_2 (1-p) où p est le taux d'exemples positifs dans l'ensemble (jeu d'apprentissage).
• S = -\sum_{v\in Valeurs\left(A\right)} \; p_v\; \log p_v où les p_v sont les fréquences avec lesquelles la variable prend chacune des valeurs possibles, plus généralement.

C'est une mesure de l'homogénéité des exemples : plus l'entropie est élevée , plus les occurrences sont équiprobables, ce qui correspond à un manque d'information pour faire une bonne prédiction.

Dans notre exemple, nous avons 9 V et 5 F : -\frac{9}{14} \log \frac{9}{14} - \frac{5}{14} \log \frac{5}{14} = 0,940 est l'entropie initiale. Quel attribut peut le réduire le plus fortement? Pour savoir, nous devons calculer, pour chaque attribut, l'entropie associée à chacune de ses valeurs et pondéré par la fréquence de cette valeur.

• Humidité : 0,940 - (7/14)* 0,985 - (7/14)* 0,592 = 0.151
  • Elevée, fréq. 7/14, classement=[3+,4-] ⇒ s([3,4]) = 0.985 ⇒ contribution au gain = (7/14)* 0,985
  • Normale, fréq. 7/14, classement=[6+, 1-] ⇒ s([6,1]) = 0,592 ⇒ contribution au gain = (7/14)* 0,592
• Vent : 0.940 - (8/14)*0.811 - (6/14)* 1.000 = 0,048
  • faible, fréq. 8/14; classement=[6+,2-] ⇒ s([6,2])=0.811 ⇒ contribution = (8/14)*0.811
  • fort, fréq. = 6/14; classement=[3+,3-] ⇒ s([3,3])= 1.00 ⇒ contribution = (6/14)* 1.000
• Ciel : 0.940 - (5/14)* 0,971 - 0 - (5/14)* 0,971 = 0,246
  • soleil, fréq. = 5/14; classement=[2+,3-] ⇒ s([2,3])=0.971 ⇒ contribution = (5/14)* 0.971
  • couvert, fréq. = 4/14; classement=[4+,0-] ⇒ s([4,0])=0.000 ⇒ contribution = (4/14) *0 = 0
  • pluie, fréq. = 5/14; classement=[3+,2-] ⇒ s([3,2])=0.971 ⇒ contribution = (5/14)* 0.971
• Température : 0,940 - (4/14)*1,000 - (6/14)*0,918 - (4/14)*0,811 = 0,029
  • chaud, fréq. = 4/14; classement=[2+,2-] ⇒ s([2,2])=1,000 ⇒ contribution = (4/14)*1,000
  • doux, fréq. = 6/14; classement=[4+,2-] ⇒ s([4,2])=0,918 ⇒ contribution = (6/14)*0,918
  • froid, fréq. = 4/14; classement=[3+,1-] ⇒ s([3,1])=0,811 ⇒ contribution = (4/14)*0,811

Donc, puisque max{0.151 0,048 0,246 0,029}=0,246, nous choisons ciel comme attribut racine, et poursuivons l'évaluation des gains potentiels si on affine dans chacun de ses trois fils. Nous constatons que pour “couvert” la valeur de la variable dépendante est toujours ”+” donc on s'arrête là en ce qui le concerne, et n'étudions que ses deux frères. Etc.

Dans cet algorithme, l'apprentissage est une recherche dans un espace d'hypothèses (les arbres de séquences de décisions), guidé par le gain incrémental à chaque instant mesuré par une fonction (entropie). Cela suppose que l'espace d'hypothèses est complet, ce qui est le cas, et les choix sont faits sur la base de critères statistiques. Mais ce n'est pas une recherche exhaustive, car c'est une recherche en largeur d'abord qui ne retourne pas en arrière pour mettre en question les séquences des attributs. C'est un algorithme “greedy”, qui préfère produire les règles les plus courtes.

C'est, je crois, une question de degrés de liberté. Pour palier,

• arrêter la croissance de l'arbre quand la division des données n'est plus crédible (statistiquement significative?) : si chaque feuille a un cas, par exemple, on n'a qu'une énumération de cas particuliers!
• générer l'arbre entier (lequel?) puis élaguer après mesures des performances sur un jeu de données de validation

En faire un attribut discret. Par exemple, pour la température, grouper les températures en tranches.

Si un attribut a beaucoup de valeurs, il sera favorisé, pour peu que leur répartition (de fréquences) ne soit pas uniforme. On peu escompter le gain d'information par une indice de saucissonnage.

• \displaystyle SplitInformation\left(S,A\right) = - \sum_{i=1}^{c} \frac{|S_i|}{|S|}\log_2 \frac{|S_i|}{|S|}
• \displaystyle GainRation\left(G,A\right) = \frac{Gain\left(S,A\right)}{SplitInformation\left(S,A\right)}

• substituer la valeur la plus commune parmi les exemple de ce noeud
• utiliser la valeur la plus commune
• faire une loi de répartition des valeurs (et simuler avec chaque valeur?)

Dans certains domaines, le coût d'obtention d'informations (attributs) peut être élevé, le délai d'acquisition peut être long (robotique, diagnostique médicale, e.g.). Des indices pour évaluer à la louche l'intérêt d'utiliser de tels attributs sont proposées:

• \displaystyle \frac{Gain^2\left(S,A\right)}{Cout\left(A\right)}
• \displaystyle \frac{2^{Gain\left(S,A\right)}-1}{\left(Cout\left(A\right)+1\right)^w},\; w\in [0,1]