Journal of Robotics, Networking and Artificial Life, Vol. 4, No. 3 (December 2017) 239–242___________________________________________________________________________________________________________A Rule-Based Classification System Enhanced by Multi-Objective Genetic Algorithm
Shingo Mabu
Graduate School of Sciences and Technology for Innovation, Yamaguchi University, Tokiwadai 2-16-1
Ube, Yamaguchi 755-8611, JAPANKenzoh Azakami
Graduate School of Science and Engineering, Yamaguchi University, Tokiwadai 2-16-1
Ube, Yamaguchi 755-8611, JAPANMasanao Obayashi
Graduate School of Sciences and Technology for Innovation, Yamaguchi University, Tokiwadai 2-16-1 Address
Ube, Yamaguchi 755-8611, JAPANTakashi Kuremoto
Graduate School of Sciences and Technology for Innovation, Yamaguchi University, Tokiwadai 2-16-1 Address
Ube, Yamaguchi 755-8611, JAPANE-mail: {mabu, v001vk, m.obayas, wu}@yamaguchi-u.ac.jp

Abstract
Recent years, data mining techniques have been developed for extracting rules from big data. However, there aresome problems to be considered, for example, it is difficult to judge which rules are important and which are notimportant; and even in simple classification problems with the small number of classes, a various sub-patterns to beconsidered potentially exist in each class. To solve the above problems, a rule clustering algorithm using
multi-objective genetic algorithm is proposed.

and enhance the classification system. In this paper, arule clustering algorithm using the multi-objective
genetic algorithm (MOGA) is proposed to enhance theconventional classification system. To confirm theeffectiveness of the proposed method, the accuracy ofthe conventional method and proposed method iscompared. In addition, the accuracy of the proposed
method and other classification methods: Tree-basedclassifier (J4.8), Multi-Layer Perceptron (MLP),
Support Vector Machine (SVM) is also compared. The
data used for the comparisons are Credit approval, PimaIndian, and German, which were downloaded from UCI
machine learning repository [3].

1. Introduction
Data mining is a technique of extracting effective rules
from big data. However, data mining has some problems
to be considered. That is, a large number of rules areextracted, so it is difficult to judge which are theimportant rules and which are not important; and evenin simple classification problems, e.g., two-classproblems, a variety of patterns potentially exist in eachclass, which makes the problems more difficult. In theconventional method [1], a genetic algorithm(GA)-based clustering was applied to the classassociation rules extracted by genetic network
programming (GNP) [2] to solve the above problems

Copyright © 2017, the Authors. Published by Atlantis Press.
This is an open access article under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
239

Journal of Robotics, Networking and Artificial Life, Vol. 4, No. 3 (December 2017) 239–242___________________________________________________________________________________________________________In [4], a multi-objective evolutionary algorithm isapplied to making rule-based classifiers. It is important
for rule-based classifiers to implement information
granulation and obtain effective input variables, whichis effectively solved by multi-objective optimization. In[5], a fuzzy-rule-based credit classification system isproposed. The accuracy and interpretability areimportant in credit classification; thus, this method
introduces three objectives related to accuracy andinterpretability and uses multi-objective geneticoptimization. In [6], an integrated algorithm forsimultaneous feature selection and designing ofclassifiers using multi-objective genetic programming.
This method minimizes three objectives such as false
positives, false negatives and the number of leaf nodes
in the tree of genetic programming. Comparing to theabove methods, the objective of the proposed method inthis paper is different. In detail, after GNP extracts alarge number of rules, the extracted rules are distributed
to several clusters using MOGA, which means that theproposed method automatically generates sub-classes
that potentially exist in the original classes. The
proposed method aims to improve classification
accuracy by adapting to various situations.

Fig. 1．Flow of rule extraction by GNP

2. Association rule extraction by GNP

Fig. 2．Structure of GNP in rule extraction

In the conventional method, a clustering using GA wasapplied to the rules extracted by GNP. In this section,
the method of extracting class association rules isexplained.

2.3 Evolution of GNP
After storing rules, crossover and mutation areperformed. In GNP, the crossover is performed by
selecting two individuals, and the selected individuals
exchange their node connections with each other. Themutation selects one individual, and connections ofnodes are randomly changed. Fitness is calculated by Eq.
(1). Eq. (1) means individuals that extract important
rules are highly evaluated.

2.1 Class association rule
As X is the antecedent, and Y is the consequent, anassociation rule is denoted by X⇒Y. For example, a rule“people who buy milk and egg also buy bread” , isdenoted by {milk, egg}⇒{bread}. A class association
rule is denoted by (A1=1)∧(A2=1)⇒class1, where theconsequent is changed to a class label.

Fitness=R∑ [χ (r ) + 10(n(r ) − 1)] + α
2r =1

2.2 Rule extraction by GNPnew(1)χ 2 (r ) : χ 2 value of class association rule rn(r) : Length of rule r
α new : Reward when a new rule is foundClass association rules are extracted by GNP from a
database with attributes of binary values and class labels(Fig. 1). GNP has a structure as shown in Fig. 2. GNP
consists of initial nodes and attribute nodes for rule
extraction. According to the transition of attribute nodes,
many candidate rules are generated. The node transition
is repeated by a predefined number of times. The
candidate rules that satisfy the evaluation criteria are
stored in a rule pool. The evaluation criteria are support,

R : Set of the extracted rule numbers

The crossover and mutation are repeated by apredefined number of times.
3.

confidence, and χ .
2Conventional rule clustering by GA

In this section, the conventional GA clustering for theclass association rules is explained.

240

Journal of Robotics, Networking and Artificial Life, Vol. 4, No. 3 (December 2017) 239–242___________________________________________________________________________________________________________Fig. 4. Example of Pareto solutions

Fig. 3．Rule clustering by GA

3.1 Individual initializationaDij2 = ∑ (ceik − ce jk ) ,First, several integer arrays are prepared, where thenumber of arrays is the same as the number of classes,
and the length of each array is the same as the numberof rules in the corresponding classes. All the arrays areinitialized by random integer values ranging from 1 to n,
where n means the number of subclasses. The random
values in the arrays show the cluster numbers to which
each rule is assigned. The flow of GA clustering isshown in Fig. 3.

ni

Si2 = ∑r =1ceik =The fitness of GA is defined as the classification
accuracy for training data, and the individuals forcrossover and mutation are selected by tournamentselection. Then, the crossover exchanges the genes ofthe selected individuals, and the mutation changes thegenes randomly.

k =1

ikrik

2

1 ni
∑ erik ,ni r =1(3)(4)

higher as the values of the evaluation functions arelarger.
4.1. Multi-objective algorithm

In this section, a class association rule clustering using
MOGA is explained. In the conventional method, thefitness is based only on the classification accuracy forthe training data. Therefore, the direction of theevolution is biased toward the correct classification for
the training data, which loses the generalization
performance for new data. The proposed method adds
two new criteria, optimizes these three criteria
simultaneously, and aims to enhance the clustering
accuracy. The two new criteria are inter-cluster varianceand intra-cluster variance∑ (ce − e ) ,Inter-cluster variance, intra-cluster variance andaccuracy are used as evaluation functions( f1 = accuracy , f 2 = Dij2 , f 3 = 1 / Si2 ). The evaluation is

Proposed rule clustering by Multi-Objective
Genetic Algorithm (MOGA)

and intra-cluster variance. Inter-cluster varianceawhere,ththerik : value of k attribute of r rule in cluster i,
a : the total number of attributes in a database,ni : the number of rules in cluster i.

3.2 Evolution of individuals

4.

(2)

2

k =1

Considering the trade-off between the evaluation
functions, MOGA is applied to the optimization.
4.2.1 . Pareto solution
An example of Pareto solutions of the individuals in
MOGA are shown in Fig. 4, where each axis
corresponds to each evaluation function. The individuals
that are not inferior to any other individuals are called
Pareto solutions (non-dominated solutions).

Dij2

Si2 are calculated by241

Journal of Robotics, Networking and Artificial Life, Vol. 4, No. 3 (December 2017) 239–242___________________________________________________________________________________________________________Table 1. Comparison of the classification accuracy

DatasetGermanPima Indian
Credit approval

Conventional
method
72.5
77.1
86.6

Classification accuracy [%]Proposed
J4.8
method
75.3
71.5
80.4
75.8
88.0
86.4

MOGA obtains the plural number of Pareto solutions(elite individuals), not one elite individual unlike
standard GA. The evolution of MOGA is performed bycrossover and mutation. For selecting crossover andmutation individuals, individuals are ranked, where theindividual rank is defined by the number of superior
individuals to itself, i.e., the rank of Pareto solution is 0.

72.5
77.1
82.4

76.0
77.1
85.9

References
1.

Simulation results

The datasets named German, Pima Indian and Credit
approval are used for evaluating the classification
accuracy. The results of the accuracy obtained by theproposed method, conventional method, J4.8, MLP andSVM are shown in Table 1. The accuracy of theproposed method is the best one obtained by the Paretosolutions. From Table 1, the proposed method showshigher accuracy than the conventional method and also
shows comparable or higher accuracy than J4.8, MLP,and SVM.
As for the computational time, the proposed method
takes larger training time than other classifiers. Thus, itdoes not fit to online learning. However, we supposethat the proposed method is trained offline like typicalevolutionary algorithms to obtain better classification
accuracy. From the simulation results, the proposed
method shows comparative or better accuracy than othermethods and even a small improvement is effective toincrease the number of accurate classifications whenapplied to big databases.
6.

SVM

the proposed method with MOGA generated solutions
with high accuracy. The future work will develop amethod selecting the best solutions from the generated
Pareto solutions. In addition, the Pareto solutions should
be analyzed in detail to find the importance of each
evaluation function.

4.2.2 . Evolution in the proposed method

5.

MLP

2.

3.

4.

5.

6.

Conclusion

To enhance the performance of the classification systemusing class association rules, MOGA was applied to therule clustering, and its classification ability wasevaluated using three datasets. The results showed that242

K. Azakami, S. Mabu, M. Obayashi, A. Kuremoto,
Performance Enhancement of Classification Systems byClustering Class Association Rules with Pruning and Its
Evaluation,
The
Conference
Recordof66th
Chugoku-branch Joint Convention of Institutes ofElectrical and Information Engineers, (2015)
K. Shimada, K. Hirasawa, and J. Hu, Genetic network
programming with acquisition mechanisms of association
rules, Journal of Advanced Computational Intelligence andIntelligent Informatic, 10(1) (2006) 102-111.
UCI Machine Learning Repository,
URL:http://archive.ics.uci.edu/ml/datasets.html/(accessed 2016-5-20)
M. Antonelli, P. Ducange, B. Lazzerini, and F. Marcelloni,
Multi-objective evolutionary design of granular rule-basedclassifiers, Granular Computing, 1(1) (2016) 37-58.
M. B. Gorzałczany, F. Rudziński, A multi-objective genetic
optimization for fast, fuzzy rule-based credit classification
with balanced accuracy and interpretability, Applied SoftComputing, 40 (2016) 206-220
K. Nag and N. R. Pal, A multiobjective genetic
programming-based ensemble for simultaneous feature
selection and classification, IEEE transactions on
cybernetics, 46(2) (2016) 499-510.