- Title
- Combinatorial optimization methods for the (alpha,beta)-k Feature Set Problem
- Creator
- Salehipour, Amir
- Relation
- University of Newcastle Research Higher Degree Thesis
- Resource Type
- thesis
- Date
- 2019
- Description
- Research Doctorate - Doctor of Philosophy (PhD)
- Description
- This PhD research thesis proposes novel and efficient combinatorial optimization-based solution methods for the (alpha,beta)-k Feature Set Problem. The (alpha,beta)-k Feature Set Problem is a combinatorial optimization-based feature selection approach proposed in 2004, and has several applications in computational biology and Bioinformatics. The (alpha,beta)-k Feature Set Problem aims to select a minimum cost set of features such that similarities between entities of the same class and differences between entities of different classes are maximized. The developed solution methods of this research include heuristic and exact methods. While this research focuses on utilizing exact methods, we also developed mathematical properties, and heuristics and problem-driven local searches and applied them in certain stages of the exact methods in order to guide exact solvers and deliver high quality solutions. The motivation behind this stems from computational difficulty of exact solvers in providing good quality solutions for the (alpha, beta)-k Feature Set Problem. Our proposed heuristics deliver very good quality solutions including optimal, and that in a reasonable amount of time. The major contributions of the presented research include: 1) investigating and exploring mathematical properties and characteristics of the (alpha,beta)-k Feature Set Problem for the first time, and utilizing those in order to design and develop algorithms and methods for solving large instances of the (alpha,beta)-k Feature Set Problem; 2) extending the basic modeling, algorithms and solution methods to the weighted variant of the (alpha,beta)-k Feature Set Problem (where features have a cost); and, 3) developing algorithms and solution methods that are capable of solving large instances of the (alpha,beta)-k Feature Set Problem in a reasonable amount of time (prior to this research, many of those instances pose a computational challenge for the exact solvers). To this end, we showed the usefulness of the developed algorithms and methods by applying them on three sets of 346 instances, including real-world, weighted, and randomly generated instances, and obtaining high quality solutions in a short time. To the best of our knowledge, the developed algorithms of this research have obtained the best results for the (alpha,beta)-k Feature Set Problem. In particular, they outperform state-of-the-art algorithms and exact solvers, and have a very competitive performance over large instances because they always deliver feasible solutions, and obtain new best solutions for a majority of large instances in a reasonable amount of time.
- Subject
- feature selection; combinatorial optimization; integer programming; heuristics; matheuristics
- Identifier
- http://hdl.handle.net/1959.13/1400399
- Identifier
- uon:34767
- Rights
- Copyright 2019 Amir Salehipour
- Language
- eng
- Full Text
- Hits: 721
- Visitors: 1337
- Downloads: 428
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT01 | Thesis | 1 MB | Adobe Acrobat PDF | View Details Download | ||
| View Details Download | ATTACHMENT02 | Abstract | 188 KB | Adobe Acrobat PDF | View Details Download |