Incremental Hyperplane Partitioning for Classification

2. Motivation

People from different background have been working on solving classification problems for years. However, many real-world classification problems, especially those with high-dimension, cannot yet be solved easily by conventional methods. Genetic algorithm (GA) is one of the intelligence algorithms proposed as a solution for classification problem during the past decades. Nevertheless, it still cannot provide high accuracy for some difficult classification problems. As that has been mentioned above, the difficulties of solving classification problems may come from either the complexity of the problem itself or the rapidly increased solution space. Therefore, in our analysis, the difficulty of a problem may derive from two aspects: first, people prefer to encode a set of If-Then rules into chromosomes when using GA to solve classification problems, which will lead to the formation of some rectangular subspaces in the pattern space. The problem will become harder when the complexity of spatial relationship between patterns increases using this encoding scheme. For instance, the problem will be easy to solve if the patterns can be partitioned by a set of hyper-planes that parallel to the axes, while it will become hard to solve if the patterns need to be partitioned by surfaces when using If-Then Rule encoded GA. On the other hand, the increase of problem dimensions will lead to the increase in problem complexity dramatically since with the increasing number of attributes, the solution space will also increase rapidly. This results in the significant growth of the problem difficulty. In the worst case, the initial fitness for all the chromosomes in the population will likely be zero due to the large solution space. As a consequence, the selector operator will have no clue in selecting better chromosomes and thus GA will degenerate to a random search algorithm. Due to all the reasons given above, ILEGA is proposed.