GID3 (Cheng et al., 1988)

Description. GID3 est une " généralisation " de ID3 dans le sens où, lors d'une segmentation, les modalités non informatives de la variable de partitionnement sont fusionnées. L'objectif est de ne produire de feuilles que pour les modalités importantes, et de mettre dans un lot à part (modalité " autres ") celles qui ne sont pas pertinentes pour la prédiction des valeurs de la classe.

Schématiquement, lors d'une segmentation, la technique consiste à détecter la modalité qui minimise l'entropie de Shannon. Puis, on évalue les autres feuilles enfants par rapport à cette référence : si l'entropie est significativement plus élevée, elle est fusionnée avec la feuille " autres ".

Pour déterminer le seuil de signification, les auteurs proposent le paramètre " tolerance level (TL) " : si l'entropie de la feuille est plus grand que " TL * Min ", elle est considérée comme non informative.

Paramètres.
Confidence level : Risque du test d'indépendance lors de la segmentation d'un nœud. Si la p-value du test du KHI-2 est plus grand que ce seuil, le partitionnement est rejeté.
Tolerance level : niveau de tolérance pour la fusion des sommets. Si on fixe une valeur < 1, toutes les feuilles issues de la segmentation seront systématiquement fusionnées. Si TL =1, on aura un arbre binaire. Si TL est très grand, on obtient un arbre identique à ID3-IV (Quinaln, 1986).

Référence. J. Cheng, U. Fayyad, K. Irani, Z. Qian, " Improved decision trees: a generalized version of ID3 ", Proc. of 5th International Conference on Machine Learning, pp.100-108, 1988.