Evolutionary Rule Learning for High Dimensional Classification Problems: Investigations and Remedies

This thesis investigates the problem of high-dimensional data classification using evolutionary rule learning algorithms. High-dimensional data analysis problems are now commonplace due to the rapid advancement in technology which has resulted in the collection of large data sets in various domains. A systematic analysis of LCS, widely accepted as the flagship evolutionary rule learning algorithm, is performed to determine the causes leading to its performance degradation in high-dimensional classification problems. First, empirical investigation of the performance of a supervised LCS in increasing dimension real-valued classification problems is performed. The systematic study allows us to establish that the extant learning bounds are necessary but are not sufficient to meet the challenge of higher dimensional real-valued spaces. A theoretical analysis is then conducted that derives new learning bounds for system convergence in these problems.A novel divide-and-conquer methodology is developed that aims at improving system scalability using the mathematically grounded rough set theory. The proposed model, RELCS, provides a solution to the sparsity problem caused by high dimensionality through projecting high-dimensional feature space into a set of smaller but representational sub-spaces. Then, a set of LCSs are trained independently on each of these sub-spaces. Finally, the outputs from each LCS in the ensemble are fused to generate the final prediction.A novel decoupling approach is proposed that aims at addressing the stalling of genetic search in high-dimensional spaces, caused by data sparsity and forgetting. A Michigan-style evolutionary rule learning system is developed that aims at modifying the multivariate search problem faced by the genetic algorithm in LCSs to a univariate search problem. This is achieved by decoupling the two search processes (finding optimal feature bounds, conjuncts, and their optimal combination, disjunct, for each rule) conducted implicitly by a genetic algorithm in LCSs. This approach allows keeping the nice features of LCS, that is the online learning and interpretability, intact while significantly reducing the load on system resources. The resultant system provides significantly better generalization capabilities as well as model complexity. The results of different parts of the research are tested and validated using a proposed synthetic binary classification problem and real-world problems