Ph.D Dominique Gay

Calcul de motifs sous contraintes pour la classification supervisée

Download Draft here

Date de soutenance : 30/11/2009

Lieu (établissement): Université de Nouvelle Calédonie, Nouméa

Thèse en convention multi sceaux avec l'INSA de Lyon

Jury              

Pr. Henri Bonnel (Président, Université de Nouvelle Calédonie)

Pr. Jean-François Boulicaut (Co-directeur de thèse, INSA Lyon)

Dr. Marc Boullé (Examinateur, France Telecom R & D, Lannion)

Pr. Bruno Crémilleux (Rapporteur, Université de Caen)

Dr. Eibe Franck (Examinateur, University of Waikato, New Zealand)

Dr. Nazha Selmaoui-Folcher (Co-directrice de la thèse, Université de Nouvelle Calédonie)

Pr. Ho Tu Bao (Rapporteur, Japan Advanced Institute of Science and Technology)

Résumé. Ces dernières années, l'extraction de motifs locaux (itemsets fréquents et règles d'association) a suscité beaucoup d'entrain pour la classification supervisée. Cette thèse traite du calcul et de l'usage de motifs sous contraintes pour la classification supervisée. Nous nous attaquons à deux problèmes difficiles en classification supervisée à base de motifs et proposons deux contributions méthodologiques. D'un côté, lorsque les attributs sont bruités, les performances des classifieurs peuvent être désastreuses. Les méthodes existantes consistent à corriger les valeurs d'attributs ou supprimer les objets bruités -- ce qui génère une perte d'information. Dans ce mémoire, nous proposons une méthode générique de construction de descripteurs robustes au bruit d'attributs -- sans modifier les valeurs d'attributs ni supprimer les objets bruités. Notre approche se déroule en deux étapes : premièrement nous extrayons l'ensemble des règles delta-fortes de caractérisation. Ces règles offrent des propriétés de corps minimal, de non-redondance et sont basées sur les itemsets delta-libres et leur delta-fermeture -- qui ont déjà fait leur preuve pour la caractérisation de groupements dans des contextes bruités. Deuxièmement, nous construisons un nouveau descripteur numérique robuste pour chaque règle extraite. Les expérimentations menées dans des données bruitées, montrent que des classifieurs classiques sont plus performants en terme de précision sur les données munies des nouveaux descripteurs que les données avec les attributs originaux. D'autre part, lorsque la distribution des classes est inégale, les approches existantes de classification à base de motifs ont tendance à être biaisées vers la classe majoritaire. La précision sur la (ou les) classe majoritaire est alors élevée au détriment de la précision sur la (ou les) classes minoritaires. Nous montrons que ce problème est dû au fait que les approches existantes ne tiennent pas compte de la répartition des classes et/ou de la fréquence relative des motifs dans chacune des classes de la base. Pour pallier à ce problème, nous proposons un nouveau cadre de travail dans lequel nous extrayons un nouveau type de motifs : les règles de caractérisation "One-Versus-Each" (OVE-règles). Ce nouveau cadre de travail nécessite le paramétrage d'un nombre conséquent de seuils de fréquence et d'infréquence. Pour ce faire, nous proposons un algorithme d'optimisation de paramètres ainsi qu'un algorithme d'extraction OVE-règles. Les expérimentations montrent que l'approche baptisée fitcare est plus performante en terme de précision sur les classes mineures que les approches existantes sur des données UCI multi-classes disproportionnées et sur des données de diagnostic de méningite aiguë. L'application de notre méthode de classification associative à l'analyse de données d'érosion des sols en Nouvelle-Calédonie a montré la pertinence de notre proposition pour caractériser les phénomènes d'érosion.

Abstract. Recent advances in local pattern mining (eg. frequent itemsets or association rules) has shown to be very useful for classification tasks. This thesis deals with local constraint-based pattern mining and its use in classification problems. We suggest methodological contributions for two difficult classification tasks. First, when training classifiers, the presence of attribute-noise can severely harm their performance. Existing methods try to correct noisy attribute values or delete noisy objects -- thus leading to some information loss. In this thesis, we propose a application-independent method for noise-tolerant feature construction -- without modifying attribute values or deleting any objects. Our approach is two-step : Firstly, we mine a set delta-strong characterization rules. These rules own fair properties such as a minimal body, redundancy-awareness and are based on delta-freeness and delta-closedness -- both have already served as a basis for a fault-tolerant pattern and for cluster characterization in noisy data sets. Secondly, from each extracted rule, we build a new numeric robust descriptor. The experiments we led in noisy environments have shown that classic classifiers are better in term of accuracy on data sets with new robust features than on original data -- thus validating our approach. Next, when class distribution is imbalanced, existing pattern-based classification methods show bias towards the majority class. In this case, accuracy results for the majority class are abnormally high to the expense of poor accuracy results for the minority class(es). In this thesis, we explain the whys and whens of this bias. Existing methods do not take into account the class distribution or the error repartition of mined patterns in the different classes. In order to overcome this problem, we suggest a new framework deal with a new pattern type to be mined : the "One-Versus-Each"-characterization rules (OVE). This new framework leads to the tuning of several frequency and infrequency thresholds. Therefore, we propose fitcare an optimisation algorithm for automatic parameter tuning in addition to an extraction algorithm for OVE-characterization rule mining. the experimentations in imbalanced multi-class data sets have shown that fitcare is significantly more accurate than existing approaches on minor class prediction. The application of our OVE framework to a soil erosion data analysis scenario has shown the added-value of our proposal. It has also given rise to a soil erosion characterization that has been validated by domain experts.

Publications liées à la thèse

N. Selmaoui, C. Leschi, D. Gay, J-F. Boulicaut. Feature Construction and Delta-Free Sets in 0/1 Samples. Proceedings of the 9th International Conference on Discovery Science DS'06, Barcelona, Spain, October 2006. Springer LNAI 4265, pp. 363–367.

D. Gay, N. Selmaoui, J-F. Boulicaut. Pattern-based decision tree construction. Proceedings 2nd International Conference on Digital Information Management ICDIM 2007, Lyon (F), October 2007, IEEE Computer Press. pp. 291-296.

D. Gay, N. Selmaoui, J-F. Boulicaut. Feature construction based on closedness properties is not that simple. Proceedings 12th Pacific-Asia Conf. on Knowledge Discovery and Data Mining  PaKDD 2008, Osaka, Japan, 20-23 May, 2008. Springer LNCS 5012, pp. 112–123.

L. Cerf, D. Gay, N. Selmaoui, J-F. Boulicaut. A parameter-free associative classification method.  Proceedings 10th International Conference on Data Warehousing and Knowledge Discovery DaWaK'08, Torino, Italy, September 1-5, 2008. Springer LNCS 5182, pp. 293-314.

D. Gay, N. Selmaoui, J-F. Boulicaut. Application-independent feature construction from noisy samples. Proceedings 13th Pacific-Asia Conference on Knowledge Discovery and Data Mining PaKDD'09, Bangkok, Thailand, 27-30 April 2009. Springer LNCS 5476, pp. 965-972.

N. Selmaoui, D. Gay, J-F. Boulicaut. Construction de descripteurs pour apprendre à classer à partir d'exemples bruités.  Actes 9ème Journées Francophones Extraction et Gestion de Connaissances EGC'09, Strasbourg (F), 27-30 janvier 2009, Cepadues-Editions, RNTI-E-15,  pp. 91-102.