Journal of Robotics, Networking and Artificial Life, Vol. 3, No. 1 (June 2016), 45-49

An Evolutionary Algorithm for Making Decision Graphs for Classification Problems
Shingo Mabu

Graduate School of Science and Engineering, Yamaguchi University, Tokiwadai2-16-1
Ube, Yamaguchi 755-8611, Japan
Masanao Obayashi

Graduate School of Science and Engineering, Yamaguchi University, Tokiwadai2-16-1
Ube, Yamaguchi 755-8611, Japan
Takashi Kuremoto

Graduate School of Science and Engineering, Yamaguchi University, Tokiwadai2-16-1
Ube, Yamaguchi 755-8611, Japan
E-mail: mabu@yamaguchi-u.ac.jp, m.obayas@yamaguchi-u.ac.jp, wu@yamaguchi-u.ac.jp

Abstract
As the exponential increase of data in the world, machine learning, pattern recognition, data mining etc. are
attracting more attentions recently. Classification is one of the major research in pattern recognition and a large
number of methods have been proposed such as decision trees, neural networks (NNs), support vector machines(SVMs). In order to easily understand and analyze the reason of the classification results, decision trees are usefulcomparing to NNs and SVMs. In this paper, to enhance the classification ability of decision trees, a new
evolutionary algorithm for creating decision graphs is proposed as a superset of decision trees, where multi-root
nodes and majority voting mechanism based on Maximum a posteriori are introduced. In the performance
evaluation, it is clarified that the proposed method shows better classification ability than decision trees.
Keywords: evolutionary computation, decision graph, classification, majority vote, multi root nodes

1. Introduction
In the research fields of pattern recognition and machinelearning, a large number of classification algorithms
have been proposed1, such as neural networks (NNs),
support vector machines (SVMs)1 and decision trees2.
NNs and SVMs mathematically create decisionboundaries to separate classes with high accuracy andhave applied to many applications such as intrusion
detection3, prediction of stock market indexes4. As forthe decision trees, typical learning algorithms areclassification and regression tree (CART)5, ID3 andC4.52. NNs, SVMs and their extended algorithms cancreate distinguished decision boundaries for accurateclassification, however, they are black box models, thus
the reason of the classification results is difficult to beshown to the end-users. On the other hand, decision
trees can visually show the rules of classification
explicitly by the tree structures, therefore, it is usefulwhen users want to know the created rules and analyze
the relationships between attributes in databases.
However, when dealing with databases with a large

Published by Atlantis Press
Copyright: the authors
45

Shingo Mabu, Masanao Obayashi, Takashi Kuremoto

number of attributes, many rules have to be created by
one tree, then the size of the tree would become toolarge. A large tree structure would cause over-fitting to
the training data and decrease the generalization ability,
therefore, a pruning of tree is to be executed. To
enhance the generalization abilities of decision trees,
some extended algorithms have been also proposed6.
In this paper, to enhance the representation ability ofdecision tree and obtain better classification accuracy,
directed-graph based classifier with recurrent
connections and its evolutionary algorithm areproposed. In the case of tree structure, the classification
procedure starts from the root node, selects appropriatebranches at non-terminal nodes, and finally classifies
the data at the reached terminal node. Therefore, thenode transition flows from the top layer to the bottomlayers. In the case of graph structure, 1) any nonterminal nodes can become root nodes, and 2) the samenodes can be shared by several rules, therefore, manyrules can be created by the smaller number of nodes andthe program structure becomes quite compact.
In addition, this paper proposes some specificmechanisms to enhance the classification abilities ofdecision graph. First, multi root nodes are introduced tocreate various kinds of rules, while the standard
decision tree uses one root node. Second, majority
voting mechanism is introduced to enhance thegeneralization ability. In the proposed method, theclassification process starts from one of the root nodes,
selects branches at non-terminal nodes, and classifies adata into a certain class (vote for a certain class) at thetransient terminal node. However, the transient terminal
node has a connection to the next non-terminal node,
therefore, the classification process continues and thesame process is repeated until the fixed number of votes
are executed. This multi-voting mechanism is expected
to show better generalization ability.
The rest of this paper is organized as follows. In
section 2, the basic structure of evolutionary decisiongraph and its gene expression is explained. In section 3,
an evolutionary algorithm of decision graphs and how toclassify data are explained. In section 4, after
benchmark problems of classification and simulation
conditions are explained, the results and analysis aredescribed. Section 5 is devoted to conclusions.

Fig. 1. Basic structure of evolutionary decision graph

2. Structure of Evolutionary Decision Graph2.1. Basic structure
The basic structure of the decision graph is shown in
Fig. 1, where there are three components: root nodes,internal nodes and transient terminal nodes. Here, root
nodes and internal nodes are called non-terminal nodes.
Root nodes have a function to start node transition anddecide the next non-terminal node to which the current
node transfers. The proposed decision graph has multiroot nodes, and the node transition starts from each root
node one by one, which results in considering various
kinds of rules to make classification. The function of
non-terminal nodes is the same as standard decision treewith multiple branches. In Fig 1, each non-terminal
node has its own attribute Ai, 𝑖 ∈ {1,2, ⋯ , 𝑛} to be
judged, and when a data is inputted to the decisiongraph, an appropriate branch is selected according to thevalue of the data. The function of transient terminal
node is to determine the class of the inputted data, andcast one vote to the class. For example, if the transientterminal node determines the class as "class 1", class 1gets one vote. After the voting, the node transition
continues depending on the connection from thetransient terminal node. The detailed mechanism ofmaking classification at each transient terminal node is
explained in section 3.2.
2.2. Gene Structure
Fig. 2 shows the gene structure of node number k in adecision graph. NFk shows a node function number:
NFk=0 is a root node, 1 is an internal node, and 2 is atransient terminal node. ATTk shows an attribute number

Published by Atlantis Press
Copyright: the authors46

An Evolutionary Algorithm fordetermined) depending on the complexity of the target
problem. Second, the values of ATTk are randomlydetermined. ATTk of non-terminal nodes are determinedby randomly selecting one of the attributes in a database.
ATTk of transient terminal nodes are determined by
maximum posterior probabilities explained in section
3.2. Finally, the branch connections are determined asfollows. bk1 of transient terminal nodes are determinedby randomly selecting one node number from nonterminal nodes. bk1, bk2, ..., bkn of non-terminal nodes aredetermined by randomly selecting one node numberfrom all the nodes.

Fig. 2. Gene Structure of evolutionary decision graph3.2. Node transition for determining voting classat transient terminal nodes

Fig. 3. Flowchart of training
evolutionary decision graphandtesting

phasesinto be judged at non-terminal node k, or a class attributeto be assigned at transient terminal node k. bk1, bk2, ...,
bkn shows the next node number connected from node k.
Transient terminal nodes have one branch to the next
node, thus only bk1 is used at each node. Non-terminal
nodes use bk1, bk2, ..., bkn depending on the possible
number of branches for ATTk.
3. Evolutionary algorithm of decision graphs
Fig. 3 shows the flow of the whole implementation ofevolutionary decision graph. In the training phase, after
initializing the individuals, voting classes at transientterminal nodes are determined by posterior
probabilities,
and the classification accuracy for training data isobtained as the fitness for evolution. Then, evolutionary
operations such as selection, crossover and mutation arecarried out. The elite individual obtained in the final
generation is picked up for the testing phase.

To classify a data into an appropriate class, which classis assigned to each transient terminal node is very
important. In this subsection, the procedure of assigning
voting classes to each transient terminal node based on
maximum posterior probabilities is explained in detail.
First, how to execute node transition is explained
before introducing the class assignment mechanism.
When a training data (tuple) d in a database is inputted,
the node transition starts from root node 0 (node numberk=0). The attribute ATT0 of data d is examined and oneof the branches among b01, b02, ..., b0n is selected (here,suppose b01 is selected). If the selected node b01 is a
non-terminal node, the same procedure as the root nodeis executed to determine the next node. Fig. 4 shows anexample of the branch selection, where, in Fig. 4 (a), thevalue of attribute ATTk of data d is in the range of[0,0.3], and its corresponding branch is bk1, thus thecurrent node transfers to node bk1. Fig. 4 (b) shows the3.1. Initialization of an individualFirst, the numbers of root nodes, internal nodes andtransient terminal nodes are determined (NFk isFig. 4. An example of attribute division and branch decision

Published by Atlantis Press
Copyright: the authors
47

Shingo Mabu, Masanao Obayashi, Takashi Kuremotocase of binary branch where each non-terminal node
executes yes-no branch selection. After repeating thebranch selections at non-terminal nodes, if the current
node reaches a transient terminal node t (Here, t shows
the node number of transient terminal nodes), counter
Ni(t) increases by one, where i shows the class numberof training data d. The current node transfers to the next
node bk1 and continues the node transition until transientterminal nodes are visited predefined number of times,
e.g., 10. However, if the node transition visits the sametransient terminal nodes that have been already visited,
the node transition restarts from the next root node, i.e.,root node 1, to avoid the transition loop. In summary,the node transition starts from root node 0, and every
time when a transition loop occurs, the node transition
restarts from root node 1, 2, 3,... in the numerical order.
By repeating the above node transition from the firstdata to the last one, the values of counters Ni(t) of all thetransient terminal nodes can be obtained. Then, theposterior probabilities of class i at transient terminal
nodes t are calculated byp(Ci |t) =Ni (t)N(t)

3.4. Genetic Operations in Evolutionary Decision
Graphs
The individuals are evolved by selection, crossover andmutation. The genetic operations of evolutionary
decision graphs are based on Ref. 7. In crossover, twoparent individuals are selected by tournament selection
and randomly selected nodes with the probability of PC
are exchanged between the parents. In mutation, one
individual is selected by tournament selection, and theconnections, attributes in non-terminal nodes, and root
nodes are randomly changed with the probability of Pm.
Table 1. Dataset information
dataset

(1)

303
208
155
178
569

1360
191330# of classes
22
2
32

Table 2. Simulation condition(2)# of generations

2000# of individuals
crossover rate
mutation rate

503
0.1
0.02

# of nodes

200
5050
100

root nodesinternal nodes
transient terminal nodes

3.3. Node transition for classifying data

After the procedure described in sections 3.1 and 3.2,
the classification of data d is carried out and fitness forevolution is obtained as follows.
The procedure of node transition is the same as
section 3.2 except that, at transient terminal nodes,voting to one of the classes is carried out instead ofcounting the number of visits Ni(t). When nodetransition reaches a transient terminal node t, it casts avote to class ATTt, then the current node transfers to thenext node bt1. The node transition continues until thepredefined number of voting finishes. Finally, the classthat wins the highest votes becomes the classification
result. The above process is repeated for all the data d,then the classification accuracy is calculated as thefitness of the individual.

# of attributes

Heart disease
SonarHepatitis
Wine
Breast cancer

where, N(t) is the number of data visiting node t.
Finally, voting class (ATTt in Fig. 2) at transientterminal node t is determined by
ATTt = arg maxj 𝑃�𝐶𝑗 �𝑡�# of data

4. Simulations
The classification accuracy is evaluated using
benchmark datasets downloaded from UCI machinelearning repository8. The information of the datasets isshown in Table 1. The objective of this paper is to showthe advantage over the conventional decision tree, butfor more reference, the comparison with support vector
machine (SVM) is also implemented. The parameters of
the proposed method are set as shown in Table 2. The
simulations are implemented by 10-fold cross validation,and the mean classification accuracy is calculated. In
the training, some variations are given to the training

Published by Atlantis Press
Copyright: the authors48

An Evolutionary Algorithm fordataset to avoid over fitting. In detail, 10% of thetraining data consists of the data misclassified by theelite individual in the previous generation, and the restof 90% of the training data are generated by bootstrap
sampling9. The continuous attributes in the original
datasets are binarized by the Fayyad and Irani's entropy
based method10 executed by WEKA software11 .
4.1. Simulation results
The performance evaluation is executed using the elite
individual obtained in the last generation in the training
phase. Table 3 shows the classification accuracy
obtained by the proposed decision graph, decision treeand SVM. From Table 3, we can see that the mean
accuracy obtained by decision graph is better thandecision tree. In addition, decision graph obtains higher
accuracy than decision tree in four datasets out of five.
Comparing the accuracy obtained by decision graphwith that by SVM, decision graph shows comparable
result, and decision graph obtains higher accuracy than
SVM in three datasets out of five. Although the mean
accuracy for the five datasets is almost the same as
SVM, decision graph can show the classification rules
to users like decision tree, therefore, when we want toknow and analyze the obtained rules, decision graph canbe an useful method. In the future, we will execute
simulations using more datasets and analyze thegenerated classification rules and characteristics of thedecision graph.
5. Conclusions
This paper proposed an evolutionary algorithm forcreating decision graphs for classification problems. To
enhance the classification abilities of the decision graph,some specific mechanisms such as multi-root nodes,
unique genetic operators and majority voting weredevised. From the simulation results, it was clarified
that the proposed evolutionary algorithm improve thefitness (accuracy) of the individuals, and showed betterclassification accuracy comparing with decision tree andcomparable accuracy to SVM. In the future, we willconsider to apply impurity measures to the evaluation
function of the evolutionary algorithm to clearly
determine the decision boundaries of classes andimprove the classification accuracy.

Table 3. Testing results for benchmark datasets
Classification accuracy [%]datasetHeart disease
Sonar
Hepatitis
Wine
Breast cancer
mean

Decision graph
84.8
82.2
66.9
94.4
94.9
84.6

Decision tree
78.5
71.2
67.1
93.8
93.1
80.7

SVM
83.8
76.0
66.5
98.3
97.7
84.4

References
1.
2.
3.

4.

5.
6.
7.

8.
9.
10.

11.

C. M. Bishop, et al., Pattern recognition and machinelearning (Springer New York, 2006).
J. R. Quinlan, C4.5: programs for machine learning,(Morgan kaufmann, 1993).
S. J. Horng, M. Y. Su, Y. H. Chen, T. W. Kao, R. J.
Chen, J. L. Lai, and C. D. Perkasa, A novel intrusion
detection system based on hierarchical clustering andsupport vector machines, Expert systems withApplications 38(1) (2011) 306–313.
E. Guresen, G. Kayakutlu, and T. U. Daim, Using
artificial neural network models in stock market index
prediction, Expert Systems with Applications, 38(8)(2011) 10389–10397.
L. Breiman, J. Friedman, C. J. Stone, and R. A. Olshen,
Classification and regression trees, (CRC press, 1984).
L. Breiman, Random forests, Machine learning, 45(1)(2001) 5–32.
S. Mabu, K. Hirasawa, and J. Hu, A graph-based
evolutionary algorithm: Genetic network programming(GNP) and its extension using reinforcement learning,
Evolutionary Computation, 15(3) (2007) 369–398.
UCI machine learning repository. Online available:archive.ics.uci.edu/ml/
Bradley Efron and Robert. J. Tibshirani, An Introduction
to the Bootstrap, (Springer, 1993).
U. M. Fayyad and K. B. Irani, Multi-interval
discretization of continuous valued attributes forclassification learning, in Proc. of the 13th International
Joint Conference on Artificial Intelligence, (MorganKaufmann, 1993), pp. 1022–1027.
Waikato environment for knowledge analysis, open
source project for machine learning, Online available:
www.cs.waikato.ac.nz/ml/weka/

Published by Atlantis Press
Copyright: the authors
49