Static and dynamic overproduction and selection of classifier ensembles with genetic algorithms

Miranda Dos Santos, Eulanda (2008). Static and dynamic overproduction and selection of classifier ensembles with genetic algorithms. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation	PDF Télécharger (57MB) | Prévisualisation
Prévisualisation	PDF Télécharger (9MB) | Prévisualisation

Résumé

The overproduce-and-choose sttategy is a static classifier ensemble selection approach, which is divided into overproduction and selection phases. This thesis focuses on the selection phase, which is the challenge in overproduce-and-choose strategy. When this phase is implemented as an optimization process, the search criterion and the search algorithm are the two major topics involved. In this thesis, we concentrate in optimization processes conducted using genetic algorithms guided by both single- and multi-objective functions. We first focus on finding the best search criterion. Various search criteria are investigated, such as diversity, the error rate and ensemble size. Error rate and diversity measures are directly compared in the single-objective optimization approach. Diversity measures are combined with the error rate and with ensemble size, in pairs of objective functions, to guide the multi-optimization approach. Experimental results are presented and discussed.

Thereafter, we show that besides focusing on the characteristics of the decision profiles of ensemble members, the control of overfitting at the selection phase of overproduce-and-choose strategy must also be taken into account. We show how overfitting can be detected at the selection phase and present three strategies to control overfitting. These strategies are tailored for the classifier ensemble selection problcm and compared. This comparison allows us to show that a global validation strategy should be applied to control overfitting in optimization processes involving a classifier ensembles selection task. Furthermore, this study has helped us establish that this global validation strategy can be used as a tool to measure the relationship between diversity and classification performance when diversity measures are employed as single-objective functions.

Finally, the main contribution of this thesis is a proposed dynamic overproduce-and-choose strategy. While the static overproduce-and-choose selection strategy has traditionally focused on finding the most accurate subset of classifiers during the selection phase, and using it to predict the class of all the test samples, our dynamic overproduce-and- choose strategy allows the selection of the most confident subset of classifiers to label each test sample individually. Our method combines optimization and dynamic selection in a two-level selection phase. The optimization level is intended to generate a population of highly accurate classifier ensembles, while the dynamic selection level applies measures of confidence in order to select the ensemble with the highest degree of confidence in the current decision. Three different confidence measures are presented and compared. Our method outperforms classical static and dynamic selection strategies.

Titre traduit

Surproduction et sélection statique et dynamique des ensembles de classificateurs avec algorithmes génétiques

Résumé traduit

La stratégie de "surproduction et choix" est une approche de sélecfion stafique des ensembles de classificateurs, et elle est divisée en deux étapes: une phase de surproduction et une phase de sélecfion. Cette thèse porte principalement sur l'étude de la phase de sélection, qui constitue le défi le plus important dans la stratégie de surproduction et choix. La phase de sélection est considérée ici comme un problème d'optimisation mono ou multicritère.
Conséquemment, le choix de la fonction objectif et de l'algorithme de recherche
font l'objet d'une attention particulière dans cette thèse. Les critères étudiés incluent
les mesures de diversité, le taux d'erreur et la cardinalité de l'ensemble. L'optimisafion
monocritère permet la comparaison objective des mesures de diversité par rapport à la performance
globale des ensembles. De plus, les mesures de diversité sont combinées avec
le taux d'erreur ou la cardinalité de l'ensemble lors de l'optimisation multicritère. Des
résultats expérimentaux sont présentés et discutés.

Ensuite, on montre expérimentalement que le surapprentissage est potentiellement présent
lors la phase de sélection du meilleur ensemble de classificateurs. Nous proposons
une nouvelle méthode pour délecter la présence de surapprentissage durant le processus
d'optimisation (phase de sélection). Trois stratégies sont ensuite analysées pour tenter de
contrôler le surapprentissage. L'analyse des résultats révèle qu'une stratégie de validation
globale doit être considérée pour contrôler le surapprentissage pendant le processus
d'optimisation des ensembles de classificateurs. Cette étude a également permis de vérifier
que la stratégie globale de validation peut être ufilisée comme outil pour mesurer empiriquement
la relation possible entre la diversité et la performance globale des ensembles
de classificateurs.

Finalement, la plus importante contribufion de cette thèse est la mise en oeuvre d'une
nouvelle stratégie pour la sélecfion dynamique des ensembles de classificateurs. Les
approches traditionnelles pour la sélecfion des ensembles de classificateurs sont essentiellement
stafiques, c'est-à-dire que le choix du meilleur ensemble est définitif et celui-ci
servira pour classer tous les exemples futurs. La stratégie de surproduction et choix dynamique
proposée dans cette thèse permet la sélection, pour chaque exemple à classer, du
sous-ensemble de classificateurs le plus confiant pour décider de la classe d'appartenance.

Notre méthode conciHc l'opfimisafion et la sélection dynamique dans une phase de
sélection à deux niveaux. L'objectif du premier niveau est de produire une population
d'ensembles de classificateurs candidats qui montrent une grande capacité de généralisation,
alors que le deuxième niveau se charge de sélecfionner dynamiquement l'ensemble
qui présente le degré de cerfitude le plus élevé pour décider de la classe d'appartenance de
l'objet à classer. La méthode de sélection dynamique proposée domine les approches conventionnelles
(approches statiques) sur les problèmes de reconnaissance de formes étudiés
dans le cadre de cette thèse.

Type de document:	Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires:	"Thesis presented to École de technologie supérieure in partial fulfillment of the requirements for the degree of doctor of philosophy". Bibliogr. : f. [153]-161.
Mots-clés libres:	algorithme, classificateur, dynamique, ensemble, genetique, optimisation, phase, selection, statique, surproduction
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Sabourin, Robert
Codirecteur:	Codirecteur Maupin, Patrick
Programme:	Doctorat en génie > Génie
Date de dépôt:	10 août 2010 17:56
Dernière modification:	20 déc. 2016 20:49
URI:	https://espace.etsmtl.ca/id/eprint/110

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt