/fdata%2F1847577%2Favatar-blog-1036432751-tmpphpHiLy0R.gif){kind=avatar}
28 mars 2008
5
28
/03
/mars
/2008
06:59
Description. La méthode de référence au sein de la communauté « apprentissage automatique ». Vers la fin des années 1980, Quinlan a publié d'innombrables variantes de son algorithme de base, ID3 (Quinlan, 1979). Avec C4, puis C4.5, il est arrivé à une sorte d'aboutissement dont il a résumé les grandes lignes dans son ouvrage « C4.5: Programs for Machine Learning ».
Au premier abord, cet ouvrage laisse perplexe. Près de 60% du texte (pages 109 à 288) est constitué du code source en C de son programme. On se sent un peu spolié de l'avoir payé aussi cher.
Pour ce qui est du texte utile (pages 1 à 107), on est étonné dans un premier temps du faible niveau technique, avec très peu de formules ou de démonstrations.
Dans un second temps, on se rend compte que l'auteur a réellement pris beaucoup de recul par rapport à la méthode, allant avant tout à l'essentiel, sans essayer de noyer tout cela dans un charabia pseudo-mathématique comme on le voit trop souvent hélas dans les monographies. L'exposé est très clair, accessible pour des non spécialistes. L'auteur s'attache à mettre en évidence la quintessence de l'induction par arbres. Il aborde les sujets clés tels que le choix des variables de segmentation, le post-élagage, l'extraction des règles à partir d'un arbre, la discrétisation floue lors du traitement des variables continues, etc.
Notre implémentation s'appuie sur deux aspects essentiels de C4.5, décrits dans l'ouvrage : le choix de la variable de segmentation avec le gain ratio ; le post élagage avec le principe de l'erreur pessimiste. Notons que Quinlan lui même avait mis en ligne le code source de son application. Au fil des versions, un nombre très important d'options destinées à bonifier l'apprentissage, mais ne remettant pas en cause le principal, se sont greffées (jusqu'à la Release 8). Nous ne les avons pas implémentées.
Les qualités de C4.5 ne sont plus à démontrer. Par rapport aux autres techniques, nous dirons qu'elle a tendance à produire des arbres plus grands, plus profonds. Ceci d'autant plus que l'effectif du fichier est important.
Une version commerciale C5.0 a vu le jour par la suite, son contenu scientifique n'est pas connu.
Paramètres.
CL (confidence level) for pessimistic pruning : Niveau de confiance pour le calcul de l'erreur pessimiste, qui est simplement la borne haute de l'intervalle de confiance de l'erreur.
Size of leaves : Taille minimum des feuilles issues de la segmentation. Il faut que 2 des feuilles au moins ait un effectif supérieur ou égal à ce seuil pour que la segmentation soit acceptée.
Références.
R. Quinlan, « C4.5: Programs for Machine Learning », Morgan Kaufman Publishers, 1993.
R. Kohavi, R. Quinlan, « Decision Tree Discovery », in Handbook of Data Mining and Knowledge Discovery, Klosgen & Zytkow Editors, Chapter 16.1.3, pages 267-276, Oxford University Press, 2002.
Au premier abord, cet ouvrage laisse perplexe. Près de 60% du texte (pages 109 à 288) est constitué du code source en C de son programme. On se sent un peu spolié de l'avoir payé aussi cher.
Pour ce qui est du texte utile (pages 1 à 107), on est étonné dans un premier temps du faible niveau technique, avec très peu de formules ou de démonstrations.
Dans un second temps, on se rend compte que l'auteur a réellement pris beaucoup de recul par rapport à la méthode, allant avant tout à l'essentiel, sans essayer de noyer tout cela dans un charabia pseudo-mathématique comme on le voit trop souvent hélas dans les monographies. L'exposé est très clair, accessible pour des non spécialistes. L'auteur s'attache à mettre en évidence la quintessence de l'induction par arbres. Il aborde les sujets clés tels que le choix des variables de segmentation, le post-élagage, l'extraction des règles à partir d'un arbre, la discrétisation floue lors du traitement des variables continues, etc.
Notre implémentation s'appuie sur deux aspects essentiels de C4.5, décrits dans l'ouvrage : le choix de la variable de segmentation avec le gain ratio ; le post élagage avec le principe de l'erreur pessimiste. Notons que Quinlan lui même avait mis en ligne le code source de son application. Au fil des versions, un nombre très important d'options destinées à bonifier l'apprentissage, mais ne remettant pas en cause le principal, se sont greffées (jusqu'à la Release 8). Nous ne les avons pas implémentées.
Les qualités de C4.5 ne sont plus à démontrer. Par rapport aux autres techniques, nous dirons qu'elle a tendance à produire des arbres plus grands, plus profonds. Ceci d'autant plus que l'effectif du fichier est important.
Une version commerciale C5.0 a vu le jour par la suite, son contenu scientifique n'est pas connu.
Paramètres.
CL (confidence level) for pessimistic pruning : Niveau de confiance pour le calcul de l'erreur pessimiste, qui est simplement la borne haute de l'intervalle de confiance de l'erreur.
Size of leaves : Taille minimum des feuilles issues de la segmentation. Il faut que 2 des feuilles au moins ait un effectif supérieur ou égal à ce seuil pour que la segmentation soit acceptée.
Références.
R. Quinlan, « C4.5: Programs for Machine Learning », Morgan Kaufman Publishers, 1993.
R. Kohavi, R. Quinlan, « Decision Tree Discovery », in Handbook of Data Mining and Knowledge Discovery, Klosgen & Zytkow Editors, Chapter 16.1.3, pages 267-276, Oxford University Press, 2002.
Partager cet article
