Incremental Hyper-Sphere Partitioning for Classification

Incremental Hyper-Sphere Partitioning for Classification

Jinghao Song (Department of Computer Science and Software Engineering, Liverpool University, Jiangsu, China), Sheng-Uei Guan (Department of Computer Science and Software Engineering, Xi'an Jiaotong-Liverpool University, Jiangsu, China) and Binge Zheng (Department of Computer Science and Software Engineering, Liverpool University, Jiangsu, China)
Copyright: © 2014 |Pages: 17
DOI: 10.4018/ijaec.2014040105
OnDemand PDF Download:
List Price: $37.50


In this paper, an Incremental Hyper-Sphere Partitioning (IHSP) approach to classification on the basis of Incremental Linear Encoding Genetic Algorithm (ILEGA) is proposed. Hyper-spheres approximating boundaries to a given classification problem, are searched with an incremental approach based on a unique combination of genetic algorithm (GA), output partitioning and pattern reduction. ILEGA is used to cope with the difficulty of classification problems caused by the complex pattern relationship and curse of dimensionality. Classification problems are solved by a simple and flexible chromosome encoding scheme which is different from that was proposed in Incremental Hyper-plane Partitioning (IHPP) for classification. The algorithm is tested with 7 datasets. The experimental results show that IHSP performs better compared with those classified using hyper-planes and normal GA.
Article Preview

1. Introduction

Evolutionary Algorithms, Neural Networks, Fuzzy Logic and many other methods were heavily used to generate solutions for classification and clustering problems. Genetic Algorithms are considered to be the most typical algorithms among Evolutionary Algorithms for classification problems which refer to assigning an input pattern into one of a given number of output categories. Furthermore, rule-based genetic algorithms were used by many researchers either in supervised or unsupervised learning (Lanzi et al., 2000). Corcoran and Sen (1994) classified the attributes in the static domain with rule-based GA, which has achieved a relatively low error rate. ILEGA (Yang, Guan & Song, 2013) solved classification problems with better flexibility using an incremental approach together with some innovative linear encoding rule. Moreover, such an incremental approach adopted for GA-based classifiers in a dynamic environment where training samples or new attributes may become available over time (Zhu & Guan, 2005), can obviously reduce the complexity of deriving a reasonable solution for classification. A similar incremental approach has also been exploited with artificial neural network to enhance the learning performance (Guan & Li, 2001). Incremental learning methods were utilized by Yamauchi et al. (1999) earlier for a different purpose, i.e. incremental pattern learning. In their approach, a small part of past learnt patterns will be relearnt with new patterns. In contrast, the algorithm introduced in this paper will only incrementally add new experts and learnt patterns will not be relearnt so that the training complexity will be reduced over time.

In the previous work, ILEGA with IHPP was proposed to solve classification problems with a higher classification rate compared with normal genetic algorithms. A classifier consisting of expert groups that are able to classify certain class of patterns, is served as the basis of the solution. Each expert group contains a unconstrained number of experts that are capable of dealing with a specific number of patterns in a specific class. Furthermore, a linear encoding scheme is applied in the specification of a chromosome so that the process of generating and decoding rules becomes simple, fast and flexible. Hyper-planes represented by linear equations mark the boundary of the patterns with more precision as the number of rules in every expert increases gradually. With the aid of genetic algorithm based optimization, several hyper-planes will form an expert which will be proficient in classifying a region enclosing certain class of patterns. The results of this approach has shown superiority to normal GA in many aspects.

ILEGA is again applied in this paper to overcome the difficulties which are caused by either the complexity of pattern relationship or rapid expansion of the solution space. Rather than encoding with If-Then rules in general expert systems, the chromosomes are still encoded with a linear encoding scheme, which is more flexible and robust. Together with IHSP, it can gain almost the same or better results in classification accuracy compared with IHPP and normal genetic algorithm. In addition, hyper-sphere partitioning generally has better performance in speed in most of the situations tested. Thus, IHSP is deemed to be effective and efficient.

We first elaborate the motivation of this algorithm in Section II. Then the design and benefits of this algorithm are illustrated in Section III. The experimental results on four artificial datasets and three benchmark datasets from UCI are reported in Section IV. The conclusions and suggestions for further studies are drawn in Section V.

Complete Article List

Search this Journal:
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