Journal of Robotics, Networking and Artificial Life, Vol. 2, No. 2 (September 2015), 73-78

On-line Rule Updating System Using Evolutionary
Computation for Managing Distributed Database
Wirarama Wedashwara, Shingo Mabu, Masanao Obayashi and Takashi Kuremoto

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

Abstract
This research proposes a decision support system of database cluster optimization using genetic network
programming (GNP) with on-line rule based clustering. GNP optimizes cluster quality by reanalyzing weak pointsof each cluster and maintaining rules stored in each cluster. The maintenance of rules includes: 1) adding new
relevant rules; 2) moving rules between clusters; and 3) removing irrelevant rules. The simulations focus on
optimizing cluster quality response against several unbalanced data growth to the data-set that is working withstorage rules. The simulation results of the proposed method show its priority comparing to GNP rule based
clustering without on-line optimization.

Keywords: Genetic Network Programming, Rule Based Clustering, Cluster Optimization

1. Introduction
Nowadays many large scale database systems with very
high data growth are being utilized to improve theglobal human activity, such as communication, social
networking, transaction, banking, etc. A distributed
database management system becomes one of thesolutions to improve data access speed by organizing
data in multiple storages for multiple types of user
accesses. Problems of distributed database management
systems are not only how to manage the large number ofdata, but also how to organize data patterns in the
distributed storages. Clever data organization is one of
the best ways to improve the retrieval speed and reduce
the number of disk I/Os and thereby reduce the query
response time.
In this paper, we propose a decision support systemfor database cluster optimization using Genetic Network
Programming (GNP) with on-line rule based clustering.

In the proposed system, an on-line algorithm is utilized
to maintain the cluster adaptability against several
unbalanced data growth. For example, the unbalanced
data growth occurs when different kinds of items (data)comparing to the items stored in the current database
begin to be stored as the time goes on (the trend of data
is changed).
This paper is organized as follows. Section 2
describes a management of distributed database, section
3 describes the on-line rule updating system, section 4shows the simulation results, and finally section 5 isdevoted to conclusions.
2. Management of Distributed Database
2.1. Rule Based Clustering
Rule based clustering is one of the solutions to provide
automatic database clustering and interpretation of data
storage patterns. Rule based clustering represents data

Published by Atlantis Press
Copyright: the authors
73

Wirarama Wedashwara, Shingo Mabu, Masanao Obayashi, Takashi KuremotoFig. 1. GNP Implementation on Cluster Optimization.
Table 1. Gene Structure of GNP
Corresponding to the Program in Fig. 1.

node transition; judgment nodes represent attributes tobe examined in a database; and processing nodes
represents the cluster numbers to which rules are
assigned. The node preparation for GNP rule extraction
contains two phases: node definition and nodearrangement. The purpose of node definition is topreparing judgment nodes that will be combined tocreate rules, and node arrangement is to select importantnodes for efficiently extracting a large number of rules.
The node arrangement is executed by the following two
sequential processes. The first process is to findtemplate rules and the second process is to generate
rules combining templates created in the first process.
Templates are extracted to obtain combinations of
attributes that frequently happen in the data-set. In thetemplate extraction process, only a few numbers of
attributes are used in GNP rule extraction. It aims toincrease the possibility to get templates with highsupport * . This node arrangement method has shown
better clustering results compared to the method without
template rules (i.e., all the attributes are simultaneously
used in the rule extraction process)9. The rule generationin both processes is carried out by evolution (crossoverand mutation) of the graph structures1, 2.

i

NTi

Ai

Ri

Ci

1

1

0

0

4

2

1

0

0

7

3

1

0

0

9

4

2

A

1

5

5

2

A

2

6

6

2

B

1

7

7

2

D

2

8,12

8

2

C

2

5

9

2

C

1

10,13

10

2

D

1

11,15

11

2

B

3

4,14

12

3

1

1

0

2.3. Silhouette

13

3

2

1

0

14

3

3

2

0

15

3

4

2

0

Silhouette value is used to evaluate the clusteringresults.
Silhouette provides a succinct graphicalrepresentation of how well each object lies within(1) itscluster5, 8. Silhouette value is calculated by Eq. (1).

patterns as rules by analyzing database structures onboth of attributes and records3,4. Each clusters
partitioned with different rule pool which each rule havea similarity to rules in internal cluster and dissimilarity
to rules in external cluster.

s

1  a / b if a  b  0if a  bb / a  1 if a  b


2.2. Genetic Network Programming
Genetic network programming (GNP), an evolutionary
optimization technique with directed graph structures, isused for data classification. GNP has a distinguishedrepresentation ability with compact programs, which isderived from the re-usability of nodes that is inherently
equipped function of the graph structures. For the
purpose of rule based clustering, GNP is useful tohandle rule extraction from data-sets by analyzing therecords.
A graph structure of GNP consists of three kinds ofnodes: start nodes, judgment nodes and processing
nodes. Start nodes represent the start positions of thebamaxa, b

*Support shows the occurrence frequency of the rule in the database.

Published by Atlantis Press
Copyright: the authors74

On-line Rule Updating

Table 2. Example of Rule Extraction for Cluster Optimization.
Start Node123

Extracted Rules
A1^B1

Support3

Processing Node
P1

Optimization
Add rule to cluster 1

A1^B1^D2

1

P1

Add rule to cluster 1

A1^B1^D2^C2

1

P1

Add rule to cluster 1

D2^C2

2

P2

Add rule to cluster 2

D2^C2^A2

1

P2

Add rule to cluster 2

D2^C2^A2^B1

0

P2

Add rule to cluster 2

C1^D1

2

P3

Remove rule from cluster 3

C1^D1^B3

1

P4

Remove rule from cluster 4

C1^D1^B3^A1

1

P1

Add rule to cluster 1s: Silhouette value for a single sample. The Silhouette
value for a set of samples is given as the mean of the
Silhouette values of each sample, a: mean distance
between a sample and all the other points in the samecluster, b: mean distance between a sample and all theother points in the second nearest cluster. A goodclustering result will make the silhouette value be close
to 1.0 and a bad clustering result will make it be close to-1.0. Silhouette value is used as a threshold (condition)of the rule updating.
3. An On-line Rule Updating System
GNP is used to extract rules from a data-set byanalyzing all the records. Phenotype and genotype
structures of GNP are described in Fig. 1 and Table 1,
respectively. In Fig. 1, each node has its own node
number i (1–15), and in Table 1, the node informationof each node number is described. The program size
depends on the number of nodes, which affects theamount of rules created by the program. 1) Start nodes(rectangle) represent the start points of the sequences of
judgment nodes which are executed sequentiallyaccording to their connections. Multiple placements ofstart nodes will allow one individual to extract a variety
of rules. 2) Judgment nodes (hexagon) represent
attributes of the data-set which are represented by Ai (inTable 1) showing an index of attribute such as price,stock, etc., and Ri showing a range index of attribute Ai.
For example, Ai=A represents price attribute, and Ri=1
represents value range [0,50] and Ri=2 represents value
range [51,80]. 3) Processing nodes (round) show the end
points of the sequences of judgment nodes andprocesses the rule updating in a cluster whose cluster
number is described as Ai in the processing node . Rishows the function of the rule updating, that is, Ri =1

Fig. 2. Example of Silhouette Valuesmeans adding the rule, and Ri =2 means removing therule. For example, P1 in Fig. 1 (node number i=12 inTable 1) processes an addition of extracted rules tocluster number 1. Multiple placement of processing
nodes will make one individual extract variety of rules.
The sequences of nodes starting from each start node
(S1,S2,S3) are represented by dotted lines a, b and c. A
node sequence flows until support for the next
combination of the judgment node (attribute) does notsatisfy the threshold. In the node sequence, if the nodes
with the attributes that have already appeared in theprevious node sequence appear, the nodes will beskipped. Candidate rules extracted by the program ofFig. 1 are shown in Table 2.
When updating rules in each cluster, it is importantto find attributes that are not matched with the latest
data. Therefore, the attributes to be considered in therule updating are determined by the following procedure.
Fig. 3 shows an example of the Silhouette values when
Silhouette values are calculated between each attributeand data in a cluster. In Fig. 2, threshold is set at 0.85,
and only the attributes with Silhouette values under 0.85

Published by Atlantis Press
Copyright: the authors
75

Wirarama Wedashwara, Shingo Mabu, Masanao Obayashi, Takashi Kuremoto

will be selected for the attributes of the judgment nodes
in the rule updating process. In Fig. 2, the attribute ofprice is not included in the rule updating of GNP
because its silhouette values are never under 0.85 (ruleupdating is not necessary), however, the values of stock
and weight for some data are under 0.85, thus those
attributes are included in GNP for updating rules. Eachcluster has dominant values of attributes which are theanchors of cluster quality, which then influence thesilhouette values. For example, when 10 [kg] is adominant value for the attribute of weight in a cluster,larger values than 10 [kg] would have a lower silhouetteand should be moved to another cluster to improve thecluster quality.
In summary, the proposed method consists of two
processes:
1) Main rule extraction process, which is a standard
rule extraction with GNP considering all the attributes
in a data-set. This process is executed to make initialclusters for the initial data-set;2) Rule updating process, which is executed for only
the data that have lower silhouette values than thethreshold. This process is repeated until good averagevalue of silhouette (cluster quality) is obtained.
The flowchart of the above processes is shown in Fig.
3.
4. Simulation
Two kinds of simulations were carried out:
Simulation I: Comparison of silhouette values
between different rule updating frequencies;
Simulation II: Comparison of silhouette values anditerations between different setting of thresholds.
4.1. Simulation Environment
The initial data-set used in the simulations contains
1000 data with eight attributes. The data-set is createdby randomly determining the attribute values in the
fixed ranges of each attribute. For example, attribute 1
has an integer value between 1 and 10, while attribute 2
has a value between 1000 and 2000. To evaluate theadaptability of the proposed method, the number of data
will be increased by adding randomly generated data or
decreased by deleting data selected randomly.
4.2. Comparison of Silhouette Values between
Different Rule Updating Frequencies
The first simulation focuses on verifying the cluster
adaptability against several unbalanced data growth ofthe data-set, where cluster adaptability is evaluated bysilhouette values.

Fig. 3. Flowchart of Proposed Method

The adaptability is evaluated in terms of thefollowing two points:
1) The number of data in the data-set is changing as
the time goes on. The initial number of data is 1000,
then every time step, 1000 new data is added to thedata-set. After the number of data reaches 6000, 1000
data is decreased every time step;2) The rule updating is executed every after thepredefined number of new data are given to the data-set(the predefined number is called "rule updating
frequency"). For example, if the rule updating frequency
is 1000, the rule updating is executed every increments
or decrements of 1000 data.
The comparisons of the simulation results werecarried out between four settings, i.e., the proposed
method with rule updating frequency of 1000, 2000 and
4000, and the clustering method of standard GNP
without on-line rule updating.
The silhouette values obtained by the four methods
are shown in Table 3. Star marks (*) on the side ofsilhouette values indicate the times when the rule
updating is carried out. In the case of the rule updating
frequency of 4000, the increment of silhouette values instep 5 and 9 can be observed, which means that the rule
updating is effectively carried out. The best results are
obtained by the rule updating frequency of 1000, where
silhouette values are stable with relatively high levelcompared to other frequency parameters. In step 3,
although the rule updating is carried out by rule update
frequency 1000 and 2000, the silhouette values
decreases, because the degree of the data change isrelatively large in this step.

Published by Atlantis Press
Copyright: the authors76On-line Rule Updating

Table 3. Simulation Result of Rule Updating Frequency and Number of Data Comparison.

+1000
+1000
+1000
+1000

No rule updating
0.967
0.945
0.902
0.892
0.882

Silhouette values
frequency: 1000
frequency: 2000
0.967
0.967
0.965*
0.944
0.923*
0.915*
0.935*
0.902
0.912*
0.909*

frequency: 4000
0.967
0.947
0.899
0.895
0.903*

+1000
-1000
-1000
-1000
-1000

0.812
0.787
0.765
0.723
0.698

0.902*
0.892*
0.901*
0.912*
0.909*

0.897
0.901*
0.888
0.892*
0.879

0.887
0.821
0.797
0.815*
0.802

0.832

0.938

0.923

0.885

Step

Number of Data

Increment/Decrement

1
2
3
4
5

1000 (Default)
2000
3000
4000
5000

6
7
8
9
10

6000
5000
4000
3000
2000

Average

Table 4. Comparison of Silhouette Values and Iteration between Different Setting of Threshold.
Number of iteration for each threshold of Silhouette value
Step

Number of Data

Increment

1.0

0.85

0.7

0.5

Sil

Iter

Sil

Iter

Sil

Iter

Sil

Iter

1

1000 (Default)

-

0.971

153

0.971

153

0.971

153

0.971

153

2

2000

+1000

0.945

165

0.935

53

0.923

45

0.912

15

3

3000

+1000

0.902

201

0.913

65

0.902

53

0.895

8

4

4000

+1000

0.905

265

0.907

89

0.873

75

0.846

11

5

5000

+1000

0.902

354

0.913

102

0.851

89

0.802

9

6

6000

+1000

0.878

402

0.837

112

0.898

99

0.816

12

0.924

278

0.905

133

0.935

126

0.893

83

Average
Sil: Silhouette value, Iter: iteration

4.3. Iterations between Different Setting ofThresholds
The second simulation focuses on comparing theiteration time and silhouette values with different
settings of thresholds for several unbalanced data
growth of the data-set. Iteration time in this simulationmeans the number of individuals generated to cover all
the data in the evolution for the rule updating. Lower
iteration time is required to minimize hardware resource
usage, so on-line processing in this paper means that there-organizing the clusters can be executed in lessiteration time than the method without on-line rule
updating. Data-set used in the simulations has 1000 datawith 8 attributes. The adaptability is evaluated in termsof the following two points. 1) The number of data inthe database is changed as the time goes on. The initial
number of data is 1000, then every time step, 1000 new

data is added to the database. 2) Several settings ofthresholds for selecting attributes are analyzed. In thiscase, the silhouette values of each attribute with thecurrent rules in the cluster is calculated, and if thesilhouette values are lower than the minimum value, i.e.,a threshold, the attributes showing the lower silhouette
values are included in the rule updating process. For
example, if the threshold is 0.5, the attributes withsilhouette values being lower than 0.5 will be added to
the rule updating process. Higher threshold increases thenumber of attributes to be reanalyzed in the rule
updating process, which would increase the iteration
times. The comparisons of the simulation results arecarried out between four settings of thresholds, i.e., theproposed method with the threshold of 0.5, 0.7, 0.85,
and 1.0. The threshold 1.0 means that all attributes will
be added to the rule updating process.
The silhouette values and iteration times obtained by
the four settings of thresholds are shown in Table. 4.

Published by Atlantis Press
Copyright: the authors
77Wirarama Wedashwara, Shingo Mabu, Masanao Obayashi, Takashi Kuremoto

The setting of 0.7 shows the best average silhouette thatis slightly better than the higher threshold of 1.0 and
0.85. This result shows that the higher thresholds do notalways have better re-clustering results. This kind of
situations are caused when more attributes are containedin the rule updating process, that is, the possibility toruin the placement of data, that have been already
optimized in the clusters, would increase. Thresholdsetting of 0.5 has the lowest average silhouette value.
This is because the small number of attributes containedin the rule updating process also does not sufficiently
optimize the cluster quality. On the other hand, in thecomparison of the iteration time, the lowest thresholdsetting of 0.5 results in the lowest iteration time, and thehighest threshold setting of 1.0 results in the highest
iteration time. Higher thresholds tend to include more
attributes in the rule updating, which will require moreiteration times to process many attributes. So when we
use the proposed on-line clustering mechanism, thebalance between the cluster quality (silhouette values)
and the iteration times need to be determined
appropriately.

6.

7.

8.

9.

strategy in the 0-1 knapsack problem, Genetic andEvolutionary Computing, 3rd International Conferenceon (2009) 105-107.
Sylvain Guinepain and Le Gruenwald. Using clustercomputing to support automatic and dynamic databaseclustering, Cluster Computing IEEE International
Conference, (2008) 394–401.
Sylvain Guinepain and Le Gruenwald. Automatic
database clustering using data mining. Database andExpert Systems Applications, DEXA IEEE 06(17)(2006) 124–128.
Yanchi Liu, Zhongmou Li, Hui Xiong, Xuedong Gao,and Junjie Wu. Understanding of internal clustering
validation measures, Data Mining (ICDM) IEEE 10th
International Conference, 10 (2010) 911–916.
Wirarama Wedashwara, Shingo Mabu, Masanao
Obayashi and Takashi Kuremoto. Implementation of
Genetic Network Programming and Knapsack Problem
for Record Clustering on Distributed Database, SICE
Annual Conference (SICE), 2014 Proceedings of the.
IEEE, (2014) 935-940.

5. Conclusions
This paper proposed a new on-line rule updating systemfor distributed database with unbalanced data growth.
The simulation results of the proposed method showed
the better clustering results and iteration time comparing
to GNP rule-based clustering without on-line
adaptation. In the future, we will apply fuzzy
membership functions to attribute judgment to makerules with better clustering ability.
References
1.

2.

3.

4.

5.

Kaoru Shimada, Kotaro Hirasawa, and Jinglu Hu.
Genetic network programming with acquisition
mechanisms of association rules, JACIII. 10(1) (2006)
102–111.
Shingo Mabu, Ci Chen, Nannan Lu, Kaoru Shimada,and Kotaro Hirasawa. An intrusion-detection model
based on fuzzy class-association-rule mining using
genetic network programming Systems, Man, andCybernetics, Part C: Applications and Reviews, IEEE
Transactions on. 41(1) (2011) 130–139.
Mansoori, E.G., FRBC: A Fuzzy Rule-Based Clustering
Algorithm, Fuzzy Systems, IEEE Transactions. 19(5)(2011) 960-971.
Sinaee, M.; Mansoori, E.G., Fuzzy Rule Based
Clustering for Gene Expression Data, Intelligent Systems
Modelling & Simulation (ISMS), 4th International
Conference (2013) 7-11.
Zhao, JiangFei and Huang, TingLei and Pang, Fei andLiu, YuanJie, Genetic algorithm based on greedy

Published by Atlantis Press
Copyright: the authors78