Dynamic selection of ensemble of classifiers using meta-learning

Menelau Oliveira E Cruz, Rafael (2016). Dynamic selection of ensemble of classifiers using meta-learning. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation

PDF Télécharger (3MB) | Prévisualisation

Résumé

Dynamic ensemble selection systems work by estimating the level of competence of each classifier from a pool of classifiers. Only the most competent ones are selected to classify each specific test sample. The classifiers’ competences are usually estimated over the neighborhood of the test sample, according to a given criterion, such as the local accuracy estimates or the confidence of the base classifier, computed over the neighborhood of the test sample. However, using only one selection criterion can lead to poor estimation of the classifier’s competence. Consequently, the system end up not selecting the most appropriate classifier for the classification of the given test sample.

In this thesis, dynamic ensemble selection is formalized as a meta-problem. From a metalearning perspective, the dynamic ensemble selection problem is considered as another classification problem, called the meta-problem. The meta-features of the meta-problem are the different criteria used to measure the level of competence of the base classifier. Each set captures a different property of the behavior of the base classifier, and can be seen as a different criterion for estimating the competence level of a base classifier; such criteria include, the classification performance in a local region of the feature space and the classifier confidence for the classification of the input sample. The meta-classifier is trained, based on the defined set of meta-features, to predict the competence level of a given base classifier for the classification of a new test sample. Thus, several criteria can be used in conjunction for a better estimation of the classifiers’ competences.

In Chapter 2, a novel dynamic ensemble selection framework using meta-learning is proposed, called META-DES. Five distinct sets of meta-features, each corresponding to a different criterion for measuring the level of competence of a classifier for the classification of input samples are introduced for this specific meta-problem. The meta-features are extracted from the training data and used to train a meta-classifier to predict whether or not a base classifier is competent enough to classify an input instance. During the generalization phase, the meta-features are extracted from the query instance and passed down as input to the meta-classifier. The metaclassifier estimates whether a base classifier is competent enough to be added to the ensemble. Experiments are conducted over several small sample size classification problems, i.e., problems with a high degree of uncertainty due to a lack of training data. Experimental results show the proposed meta-learning framework greatly improves classification accuracy when compared against current state-of-the-art dynamic selection techniques.

In Chapter 3, a step-by-step analysis of each phase of the META-DES framework is conducted. We show how each set of meta-features is extracted as well as their impact on the estimation of the competence level of the base classifier. Moreover, an analysis of the impact of several factors on the system performance is carried out; these factors include, the number of classifiers in the pool, the use of different linear base classifiers, as well as the size of the validation data. Experimental results demonstrate that using the dynamic selection of linear classifiers through the META-DES framework, it is possible to solve complex non-linear classification problems using only a few linear classifiers.

In Chapter 4, a novel version of the META-DES framework based on the formal definition of the Oracle, called META-DES.Oracle is proposed. The Oracle is an abstract method that represents an ideal classifier selection scheme. A meta-feature selection scheme using an overfitting cautious BPSO is proposed for improving the performance of the meta-classifier. The difference between the outputs obtained by the meta-classifier and those presented by the Oracle is minimized. Thus, the meta-classifier is expected to provide results that are similar to those of the Oracle. Experiments carried out using 30 classification problems demonstrate that the optimization procedure based on the Oracle definition leads to a significant improvement in classification accuracy when compared to previous versions of the META-DES framework.

Finally, in Chapter 5, two techniques are investigated in order to improve the generalization performance of the META-DES framework as well as any other dynamic selection technique. First, a prototype selection technique is applied over the validation data to reduce the amount of overlap between the classes, producing smoother decision boundaries. During generalization, a local adaptive K-Nearest Neighbor algorithm is employed for a better definition of the neighborhood of the test sample. Thus, DES techniques can better estimate the classifiers’ competences. Experiments were conducted using 10 state-of-the-art DES techniques over 30 classification problems. The results demonstrate that the use of prototype selection in editing the validation data and the local adaptive distance significantly improve the classification accuracy of dynamic selection techniques.

Titre traduit

Méta-apprentissage pour la sélection dynamique des ensembles de classifieurs

Résumé traduit

Les systèmes de sélection dynamique des ensembles de classifieurs fonctionnent en estimant le niveau de compétence de chaque classifieur estimé dans une région de compétence. Seuls les plus compétents sont choisis dynamiquement pour classer chaque échantillon de test. Le niveau de compétence des classifieurs est généralement estimé à partir du voisinage de l’échantillon à classer, selon un critère donné, comme la performance locale ou la confiance du classifieur de base, calculée sur ce voisinage. Cependant, en utilisant un seul critère de sélection, cela peut conduire à une mauvaise estimation de la compétence du classifieur et par conséquent, sélectionner des classifieurs incompétents.

Dans cette thèse, le mécanisme de sélection dynamique d’un classifieur est formulé comme un méta-problème. Les méta-caractéristiques permettant de représenter ce méta-problème sont les différents critères utilisés normalement pour mesurer le niveau de compétence du classifieur de base. Chaque méta-caractéristique capture une propriété différente du comportement du classifieur de base, et peut être considéré comme un critère différent pour estimer le niveau de compétence d’un classifieur de base telles que la performance de classification dans une région locale de l’espace de caractéristiques et de la confiance du classifieur pour la classification de l’échantillon d’entrée. Ainsi, plusieurs critères peuvent être utilisés conjointement pour une meilleure estimation des compétences des classifieurs.

Dans le chapitre 2, une nouvelle technique de sélection dynamique des ensemble de classifieurs utilisant le méta-apprentissage est proposé, appelé META-DES. Cinq ensembles distincts de méta-caractéristiques, chacun correspondant à un critère différent pour mesurer le niveau de compétence d’un classifieur pour la classification des échantillons d’entrée sont introduits pour ce méta-problème. Les méta-caractéristiques sont extraites des données de validation et utilisées pour entraîner un méta-classifieur pour prédire le niveau de compétence des classifieurs étant donné un exemple à classer. Au cours de la phase de généralisation, les méta-caractéristiques sont extraites de l’instance de requête et transmisent en entrée du métaclassifieur, lequel détermine si un classifieur de base est assez compétent pour être ajouté à l’ensemble. Des expériences sont menées sur plusieurs problèmes de reconnaissance. Les résultats expérimentaux montrent que le META-DES améliore considérablement la performance en classification lorsqu’on les compare à l’état de l’art dans le domaine de la sélection dynamique.

Une analyse étape par étape de chaque processus du système META-DES est présentée au chapitre 3. Nous montrons comment chaque ensemble de méta-caractéristiques est extrait, ainsi que leur impact sur l’estimation du niveau de compétence du classifieur de base. En outre, une analyse de l’impact de plusieurs facteurs sur la performance du système est réalisée sur le problème synthétique P2 : par exemple, le nombre de classifieurs inclus dans le bassin, de même que la taille des données de validation sont considérés. Les résultats expérimentaux montrent que la sélection dynamique de classifieurs à fonctions discriminantes linéaires à travers le schéma META-DES, permet de résoudre les problèmes de classification caractérisés par une frontière de décision de géométrie complexe.

Dans le chapitre 4, une nouvelle version du schéma META-DES optimisé en fonction de la performance de l’Oracle, appelé META-DES.Oracle est proposée. L’Oracle est une méthode abstraite qui représente un mécanisme de sélection de classifieur idéal. Une sélection de métacaractéristiques effectuée à l’aide d’une optimisation par essaims particulaires (OEP, ou PSO en anglais) est proposée pour améliorer la performance du méta-classifieur. La différence entre les résultats obtenus par le méta-classifieur et ceux présentés par Oracle est minimisé. L’objectif visé est d’augmenter la performance en sélection du méta-classifieur pour approcher celle de l’Oracle. Les expériences réalisées à l’aide de 30 problèmes de classification démontrent que la procédure d’optimisation basée sur la performance de l’Oracle conduit à une amélioration significative de la précision de la classification par rapport aux versions précédentes du METADES.

Enfin, au chapitre 5, deux techniques sont analysées afin d’améliorer la performance en généralisation du META-DES, ainsi que des autres techniques de sélection dynamique proposées dans la littérature. Tout d’abord, une technique de sélection de prototypes est appliquée sur les données de validation pour réduire la quantité de chevauchement entre les classes. Au cours de la généralisation, un algorithme K-plus proches voisins adaptatif est utilisé pour une meilleure définition du voisinage de l’échantillon d’essai. Le but visé est d’améliorer l’estimation du niveau de compétence des classifieurs dans la région de compétence en donnant plus d’importance aux exelples qui sont éloignés de la frontière entre les classes. Des expériences ont été effectuées en utilisant 10 techniques de sélection et plus de 30 problèmes de classification. Les résultats démontrent que l’utilisation conjointe de la sélection de prototypes pour éditer des données de validation et la distance d’adaptation locale améliorent sensiblement la précision de la classification des techniques de sélection dynamique.

Type de document:	Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires:	"Manuscript-based thesis presented to École de technologie supérieure in partial fulfillment of the requirements for the degree of doctor of philosophy". Bibliographie : pages 251-261.
Mots-clés libres:	Systèmes de classeurs. Reconnaissance des formes (Informatique) Optimisation mathématique. classifieur, compétence, dynamique, ensemble, méta-apprentissage, sélection, ensemble de classifieurs, sélection dynamique de classifieurs, optimisation par essaims de particles, classifieurs linéaires, perceptrons
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Sabourin, Robert
Codirecteur:	Codirecteur Cavalcanti, George D. C.
Programme:	Doctorat en génie > Génie
Date de dépôt:	03 août 2016 19:09
Dernière modification:	10 déc. 2016 17:23
URI:	https://espace.etsmtl.ca/id/eprint/1703

Gestion Actions (Identification requise)

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