Présentation

Anciennes versions

Sipina

Le site web de SIPINA a été transféré à l'adresse suivante (URL) : http://sipina-arbres-de-decision.blogspot.fr/


Ricco Rakotomalala.

Jeudi 27 mars 4 27 /03 /Mars 16:02
Description. ASSISTANT 86 fait partie des méthodes dérivées de ID3 (Quinlan, 1979). Elle introduit un certain nombre d'améliorations destinées à mieux guider l'induction.

L'arbre construit est forcément binaire. Lors de la segmentation, ASSISTANT cherche la combinaison qui maximise le gain d'entropie. L'implémentation de SIPINA utilise un algorithme glouton. Il n'est pas question de tester toutes les configurations possibles, surtout lorsque les variables candidates prennent un grand nombre de modalités.

Plusieurs paramètres sont introduits pour contrôler la taille de l'arbre.

Paramètres.
Attribute suitability : Le gain d'entropie (multiplié par l'effectif) sur un nœud est comparé à ce seuil, s'il est plus petit, la segmentation est refusée. Plus ce seuil sera augmenté, plus l'arbre sera réduit. Ce paramètre est assez difficile à manipuler. Nous n'avons pas de référentiel facile à interpréter.
Class frequency : Que l'on appelle seuil de spécialisation dans d'autres logiciels. Si une des modalités de la variable à prédire a une fréquence plus élevée que ce seuil, la segmentation n'est pas réalisée. Ce paramètre varie entre 0 et 100%, plus il sera proche de 100%, plus grand sera l'arbre de décision.
Node weight : Il s'agit de la taille minimum avant segmentation, mais exprimée en termes relatifs. Si le " poids " d'un sommet est plus petit que ce seuil (poids du sommet : effectif du sommet / effectif total), la segmentation n'est pas tentée. Ce paramètre varie entre 0 et 100%. Si on le fixe à 100%, seul la racine sera (éventuellement) segmentée.

Référence. B. Cestnik, I. Kononenko, I. Bratko, " ASSISTANT 86: A Knowledge Elicitation Tool for Sophistical Users ", Proc. of the 2nd European Working Session on Learning, pp.31-45, 1987.
Par Sipina - Publié dans : Algos et méthodes
Voir les 0 commentaires
Jeudi 27 mars 4 27 /03 /Mars 15:23
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.
Par Sipina - Publié dans : Algos et méthodes
Voir les 0 commentaires
Jeudi 27 mars 4 27 /03 /Mars 14:36
Description. ID3-IV (1986) est la (une des) dernière version de ID3, avant que Quinlan ne se tourne vers le post-élagage avec C4 puis C4.5 (et les autres versions commerciales, non publiées qui s'en suivront).

Par rapport à l'algorithme originel (ID 3 - Quinlan, 1979), il apporte un certain nombre d'améliorations, dont une nouvelle stratégie de pré-élagage basée sur un test d'indépendance du KHI-2. Lorsque la segmentation n'est plus significative, le sommet n'est plus segmenté.

Paramètres.
Confidence level : Risque du test d'indépendance du KHI-2 sur un nœud à segmenter. Une p-value du test plus grande que ce  constitue une règle d'arrêt de l'expansion de l'arbre.

Référence. J. Quinlan, " Induction of Decision Trees ", in Machine Learning, 1, pp.81-106, 1986.
Par Sipina - Publié dans : Algos et méthodes
Voir les 0 commentaires
Jeudi 27 mars 4 27 /03 /Mars 14:19
Description. Catlett (1991) est certainement un des premiers data miner de l’histoire. Son seul tort est d’avoir eu raison trop tôt. En effet, plusieurs années avant la grande vague du data mining et l’article fondateur de Fayyad (1996), il a présenté une thèse de doctorat essentiellement tournée vers l’optimisation des algorithmes de machine learning, en l’occurrence les arbres de décision, dans le traitement des très grandes bases de données.

Le titre de sa thèse, « Megainduction : Machine learning on very large databases », est assez édifiant. Il a ainsi proposé des solutions ad hoc, qui se justifient essentiellement lorsque l’on doit appréhender de gros volumes.

La méthode « A limited search induction tree algorithm » fait partie justement des solutions préconisées dans sa thèse de doctorat. L’idée est simple, on fixe a priori le nombre de segmentations à réaliser lors de la construction de l’arbre. En dehors du contexte megainduction, la solution peut paraître un tantinet arbitraire. Mais elle vaut autant qu’une autre. En effet, il est très difficile de définir une règle d’arrêt simple et crédible lors de l’expansion de l’arbre. Le post élagage, même s’il est plus efficace pour déterminer la bonne taille de l’arbre, impose la construction dans un premier temps de l’arbre maximum, rédhibitoire sur de très grandes bases.

Paramètres.
Number of max splits : nombre maximum de segmentations que l’on peut introduire lors de la construction de l’arbre

Référence. J. Catlett, « Megainduction : Machine learning on very large databases », PhD Thesis, School of Computer Science, University of Technology, Sydney, Australia, 1991.

Par Sipina - Publié dans : Algos et méthodes
Voir les 0 commentaires
Jeudi 27 mars 4 27 /03 /Mars 12:27
Stratégie d'échantillonnage pour les arbres de décision. Dans tous les algorithmes d'induction d'arbres, SIPINA introduit une option d'échantillonnage. L'idée est la suivante : plutôt que de travailler sur l'ensemble des individus disponibles sur chaque noeud pour choisir la variable de segmentation, nous proposons d'extraire un sous-échantillon et de calculer sur ces observations les indicateurs appropriés (gain d'entropie, statistique du khi-2, indice de Gini, etc.).

L'expérimentation montre que l'ordonnancement des variables de segmentation sur chaque noeud reste le même, et de fait, les caractéristiques des arbres produits, notamment les performances en prédiction, sont préservées.

L'intérêt de cette approche est le gain de temps lors de la construction de l'arbre. Il peut être déterminant sur les grandes bases, surtout lorsqu'elles comportent un nombre important de variables continues, nécessitant la répétition du tri des données lors de la discrétisation.

L'échantillonnage sur un noeud est toujours sans remise. Il peut être représentatif (aléatoire simple), équilibré (le même nombre d'observations pour chaque modalité de la variable à prédire), ou stratifié (respectant les proportions de la totalité des observations sur le noeud).

Changement de stratégie dans Tanagra. Notons que par la suite, dans TANAGRA, nous avons adopté une autre stratégie. Toutes les variables continues sont triées une fois pour toutes avant l'induction. Un tableau d'index permet de conserver l'ordre des observations. Lors du traitement d'un noeud, nous y puisons les individus présents. La phase de tri n'est donc plus nécessaire puisque les observations sont déjà ordonnées. Le prix de cette approche est la nécessité de conserver en mémoire le tableau d'index, à savoir 4 octets par observation et par variable. Pourquoi ce revirement ? La raison est simplement pragmatique. En 1998, on disait d'une machine qu'elle était performante lorsqu'elle disposait de 256 Mo de RAM. En 2004, et plus récemment encore, un ordinateur avec 2Go de RAM est tout à fait courant.

Mots clés : arbres de décision, échantillonnage, optimisation des calculs, traitement des grandes bases de données
Référence : J.H. Chauchat, R. Rakotomalala, « A new sampling strategy for building decision trees from large databases », Proc. of IFCS-2000, pp. 199-204, 2000.

 

Par Sipina - Publié dans : Algos et méthodes
Voir les 0 commentaires
Mardi 25 mars 2 25 /03 /Mars 12:26
SIPINA propose des fonctionnalités de statistiques descriptives. Peu de personnes le savent. En soi l'information n'est pas éblouissante, il existe un grand nombre de logiciels libres capables de produire les indicateurs de la description statistique.

L'affaire devient plus intéressante lorsque l'on couple ces outils avec l'induction d'un arbre de décision. La richesse de la phase exploratoire est décuplée. En effet, chaque nœud d'un arbre correspond à une sous population décrite par une règle. Ce groupe a été constitué de manière à ce que seule une des modalités de la variable à prédire soit représentée. C'est l'objectif de l'apprentissage. Mais qu'en est-il des autres variables ?

L'arbre a une qualité rare, elle met en avant les meilleures variables dans l'induction. Mais elle a le défaut de ses qualités, elle ne donne pas directement d'informations sur les variables qui ont été écartées, encore moins sur les relations entre ces variables. La possibilité de calculer simplement des statistiques descriptives sur les sous populations permet à l'utilisateur d'étudier finement les spécificités de ces groupes, et par là même de mieux caractériser la règle produite par l'induction. C'est ce que nous essayions de mettre en valeur dans ce didacticiel.

Nous utilisons les données HEART_DISEASE_MALE.XLS . Il s'agit de prédire l'occurrence d'un maladie cardiaque (DISEASE) à partir des caractéristiques des individus (AGE, SUCRE dans le sang, etc.). Les données, 209 observations, sont restreintes aux individus de sexe masculin

Mots clés : statistiques descriptives, arbres de décision, exploration interactive
Lien : fr_sipina_descriptive_statistics.pdf
Données : heart_disease_male.xls
Par Sipina - Publié dans : Doc. et tutoriels
Voir les 0 commentaires
Mercredi 19 mars 3 19 /03 /Mars 13:59

WEKA est un logiciel de Data Mining libre très populaire dans la communauté « Machine Learning ». Il intègre un grand nombre de méthodes, articulées essentiellement autour des approches supervisées et non supervisées.

WEKA possède un format de fichier propriétaire (*.ARFF), qui est un format texte, avec des spécifications ad hoc sur documenter les variables. Importer un fichier ARFF ne pose donc pas de problèmes particuliers, dès lors que l’on sait appréhender un fichier texte.

Dans ce didacticiel, nous montrons comment charger un fichier ARFF dans SIPINA. L’importation est directe, il s’agit simplement de connaître la bonne procédure. Nous profitons de cet exemple pour montrer comment subdiviser aléatoirement un ensemble de données pour : construire l’arbre sur l’échantillon d’apprentissage, l’évaluer sur l’échantillon test. Nous utilisons la méthode C4.5 (Quinlan, 1993).

Mots clés : WEKA, format de fichier ARFF, arbres de décision, C4.5, subdivision apprentissage et test, évaluation des classifieurs
Lien : fr_sipina_weka_file_format.pdf
Données : ionosphere.arff

Par Sipina - Publié dans : Doc. et tutoriels
Voir les 0 commentaires
Mardi 18 mars 2 18 /03 /Mars 06:51
Un texte, un peu ancien et assez succinct, qui décrit les principales fonctionnalités de SIPINA : chargement de données, avec le format propriétaire binaire (*.fdm) ; choix de la méthode d'apprentissage ; définition de la variable à prédire et des variables prédictives ; sélection des individus en apprentissage et en test ; création et lecture d'un arbre de décision.

Le principal intérêt de ce document est qu'il essaie de recenser les éléments d'interface du logiciel : barre d'outils, explorateur de projets, barre d'état, etc.

Mots-clés : interface SIPINA, arbres de décision
Lien : french_introduction_sipina_research.pdf

Un texte, un peu ancien et assez succinct, qui décrit les principales fonctionnalités de SIPINA : chargement de données, avec le format propriétaire binaire (*.fdm) ; choix de la méthode d'apprentissage ; définition de la variable à prédire et des variables prédictives ; sélection des individus en apprentissage et en test ; création et lecture d'un arbre de décision.

Le principal intérêt de ce document est qu'il essaie de recenser les éléments d'interface du logiciel : barre d'outils, explorateur de projets, barre d'état, etc.
Un texte, un peu ancien et assez succinct, qui décrit les principales fonctionnalités de SIPINA : chargement de données, avec le format propriétaire binaire (*.fdm) ; choix de la méthode d'apprentissage ; définition de la variable à prédire et des variables prédictives ; sélection des individus en apprentissage et en test ; création et lecture d'un arbre de décision.

Le principal intérêt de ce document est qu'il essaie de recenser les éléments d'interface du logiciel : barre d'outils, explorateur de projets, barre d'état, etc.
Un texte, un peu ancien et assez succinct, qui décrit les principales fonctionnalités de SIPINA : chargement de données, avec le format propriétaire binaire (*.fdm) ; choix de la méthode d'apprentissage ; définition de la variable à prédire et des variables prédictives ; sélection des individus en apprentissage et en test ; création et lecture d'un arbre de décision.

Le principal intérêt de ce document est qu'il essaie de recenser les éléments d'interface du logiciel : barre d'outils, explorateur de projets, barre d'état, etc.

Un texte, un peu ancien et assez succinct, qui décrit les principales fonctionnalités de SIPINA : chargement de données, avec le format propriétaire binaire (*.fdm) ; choix de la méthode d'apprentissage ; définition de la variable à prédire et des variables prédictives ; sélection des individus en apprentissage et en test ; création et lecture d'un arbre de décision.

Le principal intérêt de ce document est qu'il essaie de recenser les éléments d'interface du logiciel : barre d'outils, explorateur de projets, barre d'état, etc.
_bug_fck
Par Sipina - Publié dans : Doc. et tutoriels
Voir les 0 commentaires
Lundi 17 mars 1 17 /03 /Mars 06:44

Déploiement de modèles. Le déploiement des modèles est une activité clé du Data Mining. Dans le cas de l’apprentissage supervisé, il s’agit de classer de nouveaux individus à partir des valeurs connues des variables prédictives introduites dans le modèle. SIPINA peut directement appliquer un arbre de décision sur un nouveau fichier non étiqueté. Petite contrainte néanmoins, le processus de déploiement doit être consécutif à l’apprentissage.  Il n’est pas possible de distribuer un modèle pour l’appliquer sur de nouveaux individus en dehors de l’environnement SIPINA.

Evaluation des performances. Prédire sur des nouveaux individus, c’est bien. Mais il faut pouvoir annoncer à l’avance les performances à venir. En effet, une affectation erronée produit des conséquences négatives (ex. diagnostiquer l’absence d’une maladie chez une personne souffrante fera qu’elle ne sera pas soignée). Pouvoir évaluer la fiabilité d’un modèle prédictif est primordiale pour la décision de sa mise en production (ou non). Nous utiliserons la méthode bootstrap dans ce didacticiel. Le but est de fournir une mesure crédible de la performance de l’arbre construit sur la totalité des données disponibles.

Ce tutoriel montre comment, avec SIPINA, construire un arbre de décision, l’appliquer sur un fichier de données non étiqueté. Par la suite, les performances en prédiction sont estimées par bootstrap. Le même schéma sera appliqué dans un second temps en utilisant l’analyse discriminante.

Mots clés :
déploiement de modèles, arbres de décision, évaluation des classifieurs, bootstrap, méthodes de ré échantillonnage
Lien : fr_sipina_deployment.pdf
Données : wine_deployment.xls

Par Sipina - Publié dans : Doc. et tutoriels
Voir les 0 commentaires
Mardi 11 mars 2 11 /03 /Mars 20:57

Sipina et Orange sont parmi les très rares logiciels libres à intégrer des fonctionnalités interactives dans la construction d'un arbre de décision. Pourtant, cette particularité, c.-à-d. la possibilité pour un expert de guider la construction du modèle en accord avec les connaissances du modèle, constitue un des atouts majeurs de cette technique par rapport aux autres méthodes de data mining.
 
Ce tutoriel compare les potentialités des logiciels Sipina et Orange dans une session d'élaboration interactive d'un arbre de décision. Les points suivants sont abordés : (1) importation d'un fichier texte ; (2) partitionnement d'un fichier en ensemble d'apprentissage et ensemble test, en utilisant une variable supplémentaire qui désigne le rôle des individus ; (3) induction et évaluation des performances d'un arbre ; (4) élagage manuel de l'arbre ; (5) choix de la variable de segmentation sur un nœud.
 
Le fichier IRIS est utilisé. Pas vraiment original à vrai dire, mais au moins on devine à l'avance la teneur des résultats que l'on devrait obtenir.
 
Mots clés : arbre de décision, analyse interactive, apprentissage et évaluation des classifieurs, fichier texte
 
Lien : http://eric.univ-lyon2.fr/~ricco/tanagra/fichiers/fr_Tanagra_Interactive_Tree_Builder.pdf
 
Données : http://eric.univ-lyon2.fr/~ricco/tanagra/fichiers/iris_tree.txt

Par Sipina - Publié dans : Doc. et tutoriels
Voir les 0 commentaires
 
Créer un blog gratuit sur over-blog.com - Contact - C.G.U. - Rémunération en droits d'auteur - Signaler un abus - Articles les plus commentés