Accueil > Développements > Classification supervisée par règles d’associations

Classification supervisée par règles d’associations

Un simple classifieur avec apriori et perl

jeudi 23 septembre 2010, par Eric Sanjuan

Ceci est une première application de cours d’informatique Décisionnelle en master. Il s’agit de de se familiariser avec une méthode très intuitive pour données catégorielles (qualitatives) aux notions de :
- classification supervisée
- apprentissage
- évaluation d’un classifieur.

Introduction

On considère une tâche de classification supervisée.
Les données sont
ici sur le site du machine learning repository
Il s’agit de décider pour chaque client bancaire si on peut lui accorder
un crédit ou pas.

Nous allons utiliser l’une des méthodes les plus simples :
les règles d’association en utilisant des programmes libres.

Tout le code et binaires nécessaires est en pièce jointe.
Il est destiné à fonctionner sur une machine Linux - 64.

Il s’agit d’une méthode pour données qualitatives (catégorielles).

Description des données

Les données consistent en des variables descriptives de clients bancaires. Dans la version que nous utilisons, les variables numériques ont été dichotomisées (transformées en catégories), pour simplifier leur traitement. Cependant il existe des méthodes telles que la régression logistique qui peuvent manipuler les deux types à la fois.

La dernière colonne indique s’il s’agit d’un "bon" (1) ou d’un "mauvais" (2) client. C’est cette variable qu’il faut prédire sachant que ce que l’on craint surtout est de récupérer un "mauvais" client. Perdre un "bon" client est moins grave.

Descriptif du package

Le package comprend :
- les données initiales dans german.data
- la mêmes données mais formatés en items et avec la variable à prédire en premier champ dans german.txt
- le script apriori.sh pour lancer un apprentissage :

bash apriori.sh german


- le script utilise la programme apriori dont les sources sont libres est accessibles sur le site WikiBooks.
- le résultat dans le cas de ces données se trouve dans german_rules1.txt pour l’ensemble des règles extraites, et dans german_rules.txt pour uniquement les règles qui permettent de décider. La conclusion des règles se trouve à gauche, les prémisses à droite (dans le style ProLog). Chaque règle est suivie d’une indication de son support (proportion des individus validant ses prémisses et sa conclusion) et de sa confiance (proportion des individus qui validant ses prémisses qui valident aussi sa conclusion). Pour obtenir plus de règles, il faut modifier les paramètres dans l’appel à apriori se trouvant dans le script apriori.sh. On peut aller chercher de plus longues règles avec un paramètre "-n5" ou "-n6" mais attention, la complexité augmente de manière exponentielle. On peut aussi aller cherche des règles plus rares qui s’appliquent à moins d’individus sur les données d’apprentissage, mais là on risque des phénomènes de sur-apprentissage. Dans les deux cas il faut manipuler ces paramètres avec prudence.
- Une fois les règles générées, on peut les appliquer à de nouvelles entrées avec le simple programme perl rlclassif.pl. Dans ce cas il suffit de taper :

perl rlclassif.pl german_rules.txt german_test.txt

le premier fichier devant contenir les règles apprises, le deuxième les nouvelles instances à classer. Ici il s’agit des mêmes uniquement pour évaluer la performance maximale du classifieur. Ensuite il faut le tester sur des données autres que celles d’apprentissage.
Le résultat de l’application des règles se trouve dans german_pred.txt. A noter que dans ce cas quand on ne trouve pas de règle fiable pour décider que c’est un "bon" client, on préfère le classer "mauvais" ...

- Enfin on calcule les "f-score" pour évaluer le système avec la commande :

perl Fscore.pl german_gold.txt german_pred.txt

où le premier fichier contient les valeurs de référence et le deuxième le résultat de la prédiction.

Evaluation de la méthode

Utiliser le F-score pour évaluer la performance du classifieur pose le soucis que l’on met sur le même plan l’erreur de rater un bon client de celle de récupérer un mauvais client, or cette dernière est jugé 5 fois plus grave par les banques.
Il faut donc au moins regarder non pas le F-score moyen mais le F-score par catégorie.

Le F-score est la moyenne harmonique de la précision P (nombre d’erreurs dans les cas détectés) et du rappel ou couverture R (nombre de bons cas détectés sur le nombre total de cas possibles) :


F_1 = 2 \times \frac{P\times R}{P + R}

Ainsi le F-score sur la détection des "bons" clients est une moyenne qui tient compte du nombre de la proportion d’erreurs dans le détection de bons clients (précision) et de la proportion totale de bons clients détectés. Ici on attache une grande importance à le précision de la décision "bon client", moins à son rappel. Dans le cas où l’on donne plus de poids à la précision on peut définir un Fb-score :


F_\beta = (1+\beta^2) \times \frac{P\times R}{\beta^2 \times P + R}

où on prendrait \beta=5 pour suivre les recommandations dans le descriptif des données.

Ceci pour le calcul de la performance sur la classe des "bons".

Dans tous les cas, il faut faut ensuite mettre en place une boucle d’évaluation où on extrait aléatoirement entre 80% et 90% des données pour l’apprentissage, et où on teste sur les données restantes (en ayant bien sûr caché la variable de décision). Un outil tel que Weka permet de faire cela facilement, mais il est en java ce qui le limite assez en utilisation de la mémoire et il requiert de recoder en java des méthodes généralement optimisées en C.

Il est aussi intéressant d’essayer de tracer la courbe d’apprentissage. Cela consiste à calculer la performance du classifieur en réduisant de plus en plus la taille de l’échantillon d’apprentissage. Quand on la lit dans le sens croissant, du plus petit au plus grand échantillon on trouve une courbe qui croît très vite au départ, puis qui stagne longuement avant de reprendre légèrement sur de très larges échantillons. Situer le point de stagnation est important pour optimiser l’ensemble des règles. Sur ces données d’essais, l’échantillon de 1000 apparaît trop petit pour pouvoir le faire.

Conclusion

La méthode par règles d’association s’apparente à celle des arbres de décision pour les données catégorielles. Chaque règle pouvant être vue comme le parcours dans un arbre de décision binaire. Cependant les arbres de décisions essayent de couper dans le nombre de parcours à explorer tandis qu’ici on explore tout, d’où l’explosion combinatoire.

Les règles d’associations viennent en fait de la culture bases de données relationnelles, il s’agit en fait de dépendances fonctionnelles partielles et on peut en fait facilement les décrire en SQL. Pour les passionnées de SQL c’est d’ailleurs un bon exercice et avec les performances actuelles des SGBDR ce n’est pas inutile.


Pour ceux qui aiment java, vous pouvez essayer de refaire cette expérimentation avec les classifieurs par règles implantés dans Weka. Il serait même intéressant de comparer les résultats. Weka est une application, complète de fouille de données avec une interface qui permet de bâtir des flux de traitements. Personnellement je suis beaucoup plus à l’aise avec des "tubes" et des flux de données dans LiNUX, mais Weka reste intéressant. Un point supplémentaire pour weka est qu’il intègre désormais un application compète avec la solution Pentaho d’intelligence économique qui est à suivre de prêt.