Incremental Hyperplane Partitioning for Classification

Incremental Hyperplane Partitioning for Classification

Tao Yang (Department of Computer Science and Software Engineering, Xi’an Jiaotong-Liverpool University, Suzhou, China), Sheng-Uei Guan (Department of Computer Science and Software Engineering, Xi’an Jiaotong-Liverpool University, Suzhou, China), Jinghao Song (Department of Computer Science and Software Engineering, Xi’an Jiaotong-Liverpool University, Suzhou, China), Binge Zheng (Department of Computer Science and Software Engineering, Xi’an Jiaotong-Liverpool University, Suzhou, China), Mengying Cao (Department of Computer Science and Software Engineering, Xi’an Jiaotong-Liverpool University, Suzhou, China) and Tianlin Yu (Department of Computer Science and Software Engineering, Xi’an Jiaotong-Liverpool University, Suzhou, China)
Copyright: © 2013 |Pages: 13
DOI: 10.4018/jaec.2013040106
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

The authors propose an incremental hyperplane partitioning approach to classification. Hyperplanes that are close to the classification boundaries of a given problem are searched using an incremental approach based upon Genetic Algorithm (GA). A new method - Incremental Linear Encoding based Genetic Algorithm (ILEGA) is proposed to tackle the difficulty of classification problems caused by the complex pattern relationship and curse of dimensionality. The authors solve classification problems through a simple and flexible chromosome encoding scheme, where the partitioning rules are encoded by linear equations rather than If-Then rules. Moreover, an incremental approach combined with output portioning and pattern reduction is applied to cope with the curse of dimensionality. The algorithm is tested with six datasets. The experimental results show that ILEGA outperform in both lower- and higher-dimensional problems compared with the original GA.
Article Preview

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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2017): 3 Released, 1 Forthcoming
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing