Metaheuristics Applied to the Feature Selection Problem
Tom Fredrik Blenning Klaussen · Duo Research Archive (University of Oslo) · 2006
The thesis is concentrated around the problem of feature selection, which is an important field in pattern analysis and computer vision. The thesis consists of 9 chapters. In the first chapter I give an introduction to the problem and the theory involved. In chapter 2 I introduce the feature selection problem. In chapter 3 I look at discrete optimization problems. In chapter 4 I look at what others have done before. In chapter 5 I analyze the problem. In chapter 6 I present some new methods for the feature selection problem, alongside pseudocode for the implementation of previously known methods. In chapter 7 I discuss the numerical difficulties that arise. In chapter 8 I look at some experimental results. In chapter 9 I draw some conclusions and sum up future work. The novelties I present are foremost the Guided Roaming SA, HuffPuff, Roaming Search and Roaming SA algorithms. There are also the adaptations ILS, VNS, Optimal Path Relinking and Inverse Path Relinking. The problem formulation in (7.13) is quite obvious, allthough to the best of my knowledge it has never been shown before. The visualization algorithm is also new. The thesis was originally meant to be about metaheuristics, and I originally intended to develop a small program to do the classification work for me. During the course of the work with the thesis, however, the library grew, and ended up as almost 16000 lines of c++ code. The numerical difficulties necessitated the study of several numerical techniques, including regularization which was done as a stabilizing technique for numerics, rather than in its own right for classification. The library implements among other things function caching, which has been imperative to the speed of many of the local search algorithms, as it precludes reevalutation of most recently evaluated functions. Since the feature selection problem is a problem which involves several professions, I have added a glossary in the end which aims at resolving some nomenclature issues. The words that I explain in the glossary are marked by an underline in the text.