Evolutionary feature creation for ensembles

Cadena, Carlos (2008). Evolutionary feature creation for ensembles. Mémoire de maîtrise électronique, Montréal, École de technologie supérieure.

Prévisualisation	PDF Télécharger (82MB) | Prévisualisation
Prévisualisation	PDF Télécharger (11MB) | Prévisualisation

Résumé

Evolutionary feature creation for ensembles is about the generation of new attributes useful to build classifiers and ensembles of classifiers (EoC), based on evolutionary algorithms. The new attributes consist in transformations applied to the original raw features into a different space with the same or smaller cardinality, so that the subsequent classification process is simpler to be executed and provide better results. The feature creation process is intended towards the generation of ensembles using the built classifiers.

Bot's method is based on Genetic Programming (GP) (Koza, 1992), which "builds the features" that define the classifier. GP is used because it has the ability to discover underlying data relationships and express them mathematically (Kishore et al, 2000) establishing the structure and values of the solution (Guo et al., 2005). As the evolution progresses, GP discards the raw features that are not useful to solve the problem. Thus, by applying genetic programming we are doing feature construction and a sort of feature selection at the same time.

The method to generate the classifiers is based on a method proposed in (Bot, 2001) and it is called here Bot's method because of its author. Bot's method uses GP and consists in creating one feature at a time and guiding the evolution of new evolved features with the aid of the improvement in recognition rate of the proposed new feature in conjunction with the already evolved features. Bot's method improves performance with each new evolved feature by adding diversity and eluding the over-fitting phenomenon. We have improved Bot's method in two ways: adding a global validation procedure to control the over-fitting and setting it with the island method.

The classifiers created by building the features based on GP are called evolved classifiers and they represent the elements of the ensembles to be generated. We choose random subspaces method (Ho, 1998b) to generate ensembles and we have proposed two strategies to create EoC. In the first one, we combine the votes from each evolved classifier feature by feature. The performance obtained is slightly better than an ensemble of raw random subspaces. What is more, the same performance level of an ensemble of raw random subspaces is attained after some features. As a result, we can build EoC to assure certain performance with the minimum number of evolved features. This reduces the complexity of the ensemble without reducing the performance. The second strategy proposed is to create the ensembles based on finding for each base classifier, the maximum number of evolved features before over-fitting the optimization data set. The base classifiers have then different number of evolved features but each one provides the best recognition rate controlling at maximum the over-fitting. Also, in this case we built ensembles with better performance than the ensemble of raw random subspaces. Furthermore, our performance results with cardinality of 9 to 12 evolved classifiers are close to the best ensembles reported in (Tremblay, 2004) with cardinality in the order of 30 base classifiers.

Titre traduit

Une méthode évolutionnaire pour la construction de caractéristiques adaptée aux ensembles de classificateurs

Résumé traduit

La construction de caractéristiques par techniques évolutives pour la génération d'ensembles consiste en la génération de nouveaux attributs utiles pour la mise en oeuvre de classificateurs (ou ses ensembles de classificateurs (EoC)) plus performants. Les nouveaux attributs sont définis par des transformations appliquées aux caractéristiques initiales avec une projection dans un autre espace de représentation de cardinalité identique ou inférieure, de sorte que la classificafion est plus simple d'exécufion et peut fournir de meilleurs résultats. La construction des caractéristiques est généralement destinée à la génération d'ensembles qui utilisant les classificateurs déjà construits.

La méthode pour produire les classificateurs est basée sur la procédure proposée par (Bot, 2001) et appelée ici la méthode de Bot. La méthode utilise la programmafion génétique (Koza, 1992) (PG), car elle a la capacité de découvrir des relations sous-jacentes dans les données et de les exprimer mathématiquement (Kishore et al., 2000). La méthode de Bot consiste à créer une caractéristique à la fois et d'orienter l'évolution des nouvelles caractéristiques évoluées avec le taux de reconnaissance de la nouvelle caractéristique proposée en collaboration avec les caractéristiques déjà évoluées. Cette méthode améliore les performances lors de chaque nouvelle caractéristique évoluée en ajoutant de la diversité et en évitant l'impact négatif du surapprentissage. Nous proposons deux stratégies pour améliorer la méthode de Bot: (1) l'utilisation de la validafion globale (Radtke et al, 2006) qui permet de raffiner le critère d'arrêt et de contrôler le surapprentissage et (2) la mise en oeuvre de la version parallèle de l'algorithme de Bot en utilisant la méthode des îles.

Les classificateurs créés par la construction des caractéristiques basée sur des évolutions de PG sont appelés classificateurs évolués et ils représentent les éléments des ensembles. Nous avons utilisé la méthode des sous-espaces aléatoires (Ho, 1998b) pour générer des ensembles et nous avons proposé deux stratégies pour créer ces ensembles. Dans la première stratégie, nous combinons les votes de chaque classificateur évolué, caractéristique par caractéristique. La performance obtenue est légèrement supérieure à un ensemble de sous-espaces aléatoires non évolués. En plus, le même niveau de performance qu'un ensemble de sous-espaces aléatoires non évolués est obtenu au bout de quelques caractéristiques. Par conséquent, nous pouvons construire des ensembles de classificateurs qui assurent un niveau satisfaisant de performance avec un nombre minimal de caractéristiques évoluées. Cela réduit la complexité de l'ensemble, sans réduire la performance. La deuxième stratégie proposée pour créer les ensembles est basée sur la recherche du nombre de caractéristiques évoluées pour chaque classificateur, de façon à contrôler le surapprentissage. Les classificateurs évolués ont donc un nombre différent de caractéristiques, mais chacun offre le meilleur taux de reconnaissance en contrôlant le surapprentissage. Dans ce cas, nous avons construit des ensembles avec des performances supérieures à l'ensemble des sous-espaces aléatoire non évoluées. De plus, les
résultats expérimentaux obtenus avec des ensembles de cardinalité variant de 9 à 12, sont proches de la meilleure performance obtenue pour les ensembles rapportés par Tremblay, 2004), avec une cardinalité d'environ 30 classificateurs de base.

Type de document:	Mémoire ou thèse (Mémoire de maîtrise électronique)
Renseignements supplémentaires:	"Thesis presented to École de technologie supérieure in partial fulfillment of the requirements for the degree of master of engineering." Bibliogr. : f.[223]-229.
Mots-clés libres:	algorithme, caracteristique, construction, classificateur, ensemble, evolutionnaire, methode
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Sabourin, Robert
Codirecteur:	Codirecteur Maupin, Patrick
Programme:	Maîtrise en ingénierie > Génie
Date de dépôt:	05 août 2010 12:58
Dernière modification:	06 déc. 2016 22:51
URI:	https://espace.etsmtl.ca/id/eprint/105

Gestion Actions (Identification requise)

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