Soft Comput
DOI 10.1007/s00500-016-2266-z

FOCUS

Genetic algorithm with a structure-based representation
for genetic-fuzzy data mining
Chuan-Kang Ting1 · Ting-Chen Wang1 · Rung-Tzuo Liaw1 · Tzung-Pei Hong2,3© Springer-Verlag Berlin Heidelberg 2016

Abstract Mining association rules is an important data mining technology aiming to find the relationship among itemsin the databases. Genetic-fuzzy data mining uses evolutionary algorithm, such as genetic algorithm (GA), to optimize
the membership functions for mining fuzzy association rules,
and has received considerable success. The increase in data,
especially in big data analytics, poses serious challenges to
GA in the effectiveness and efficiency of finding appropriate membership functions. This study proposes a GA for
enhancing genetic-fuzzy mining of association rules. First,
we design a novel chromosome representation considering
the structures of membership functions. The representation
facilitates arrangement of membership functions. Second,
this study presents two heuristics in the light of overlap andcoverage for removing inappropriate arrangement. A seriesof experiments is conducted to examine the proposed GA on
different amounts of transactions. The experimental results
Communicated by C.-H. Chen.

B Chuan-Kang Ting

ckting@cs.ccu.edu.tw
Ting-Chen Wang
wtc102p@cs.ccu.edu.tw
Rung-Tzuo Liaw
lrt101p@cs.ccu.edu.tw
Tzung-Pei Hongtphong@nuk.edu.tw

1

Department of Computer Science and Information
Engineering, National Chung Cheng University, Chiayi,
Taiwan2

Department of Computer Science and Information
Engineering, National University of Kaohsiung, Kaohsiung,Taiwan3

Department of Computer Science and Engineering, National
Sun Yat-sen University, Kaohsiung, Taiwan

show that GA benefits from the proposed representation.
The two heuristics help to explore the structures of membership functions and achieve significant improvement on
GA in terms of solution quality and convergence speed. The
satisfactory outcomes validate the high capability of the proposed GA in genetic-fuzzy mining of association rules.
Keywords Genetic algorithm · Chromosome
representation · Membership function · Fuzzy association
rules · Genetic-fuzzy data mining

1 Introduction
With the rapid increase in data amount, data analytics
emerges to leverage and transform the information hidden in
the data into explicit knowledge. Data mining aims to explore
the data for valuable information and plays a key role indata analytics (Fayyad et al. 1996a, b; Piatesky-Shapiro et al.
1996). Several data mining technologies have been proposed
to discover knowledge for different purposes, such as classification (Chang and Lin 2011), clustering (Wagstaff et al.
2001), and association rules (Hong et al. 2008).
Mining association rules is a significant technology ofdata mining. It attempts to find the relationship among
items, also known as homogeneous group or affinity group,from the database and has achieved many successful stories, e.g., prediction of customer’s behavior in Walmart.
The Apriori algorithm is well known for mining association
rules (Agrawal and Srikant 1994). This method establishes
association rules based on frequent itemsets according toa user-defined minimum confidence. Srikant and Agrawal(1996) extended the rules into quantitative association rules,
which can deal with data with quantitative values or categories. They presented a method similar to the Apriori

123

C.-K. Ting et al.

Given an itemset I = {I1 , . . . , Im } with m items and a
database D = {T1 , . . . , Tn } with n transactions Tk ⊆ I , anassociation rule X → Y represents the possibility: if X ⊆Ti then Y ⊆ Ti . The importance of an association rule isordinarily measured by two metrics: support and confidence.

algorithm but requiring an additional preprocess of data
discretization. Recently, fuzzy set theory is introduced to different aspects of association rules (Chan and Au 1997; Hongand Lee 1996; Kuok et al. 1998). In particular, Hong et al.
(1999, 2006, 2008) proposed the fuzzy transaction data mining algorithm (FTDA) by adopting fuzzy sets to analogue thevalues of original data. In the FTDA, quantitative values ofdata are transformed into fuzzy values according to membership functions. The results are known as fuzzy association
rules. The FTDA holds the advantages in extension, tolerance, and suitability for nonlinear systems.
In view of its recognized capability in global search,genetic algorithm (GA) is commonly used to find the optimal setting for membership functions. Although GA has
obtained some promising results, there exist two key issues
at the design of GA for fuzzy association rule mining. First,
the common chromosome representation for genetic-fuzzydata mining comprises the vertex positions but omits the
structure information of membership function. Second, therelationship between membership functions involves overlap
and coverage. However, it is ordinarily not considered in thedesign of GA.
This study aims to address the above two issues andimprove GA on mining fuzzy association rules. Specifically,
we propose a chromosome representation considering thestructure of membership functions and their relationship.
Using the new representation, two heuristics are developed
to eliminate inappropriate arrangement of membership functions and reduce the search space. These enhancements arehelpful for the genetic-fuzzy system to mine association rules
among transactions. This study carries out a series of experiments to examine the performance of the proposed GA in
different data scales.
The remainder of this paper is organized as follows. Section 2 introduces association rules and fuzzy association
rules. Section 3 sheds light on the proposed GA. The experimental results are presented and discussed in Sect. 4. Finally,
we draw conclusions and recommend the directions for future
work in Sect. 5.

Υ j,k is determined by the quantity v j of the j-th item in thei-th transaction Ti .

2 Mining fuzzy association rules

Definition 3 The fuzzy support of region Υ j,k is calculatedbyAssociation rules infer the coexistence of items and play animportant role in data analytics (Agrawal et al. 1993). An
association rule can be generally expressed by the following
mathematical form:
X → Y,(1)

where X and Y are sets of items. In the famous example ofWalmart, the association rule {br ead, cheese} → {milk}infers “If buying bread and cheese, then buying milk”.

123

Definition 1 (Support) The support of association rule X →Y is defined by the probability that X and Y coexist, i.e.,
Support (X → Y ) = P (X ∪ Y ).

(2)

Definition 2 (Confidence) The confidence of association
rule X → Y is defined by the probability that Y exists given
X exists, i.e.,
Confidence (X → Y ) = P (Y |X ) =P (X ∪ Y ).
P (X )(3)

The Apriori algorithm (Agrawal and Srikant 1994) is wellknown for mining association rules. Given the minimum support suppor tmin , the Apriori algorithm progressively selects
the large itemsets L = {L 1 , . . . , L m } from all candidate
itemsets C = {C1 . . . , Cm }. The items in the large itemsets
obtained are then arranged as association rules according toa predetermined minimum confidence con f idencemin . The
time complexity of the Apriori algorithm is O (2m ) in thatthe size of candidate itemsets C is exponential to the numberof items m in the itemset I .
Hong et al. (1999, 2006) extended association rules byconsidering quantity of items and introducing the notion of
fuzzy sets. They proposed constructing fuzzy association
rules using the fuzzy support and fuzzy confidence basedon the membership functions for all m items in the databaseD.
Let Υ j,k denote the fuzzy region of k-th membership func(i)tion for item I j . The fuzzy membership value f j,k of region
(i)

n

 1
(i)
FuzzySupport Υ j,k =f j,k .
n

(4)

i=1



If a fuzzy region Υ j,k has FuzzySupport Υ j,k ≥ suppor tmin ,it is then included to the large 1-itemset L 1 like the Apriorialgorithm.
For a set of fuzzy regions Υ = {Υ1 , . . . , Υ p }, its fuzzy
value in transaction Ti is given by the intersection of mem(i)bership values f Υk , i.e.,

Genetic algorithm with a structure-based representation for genetic-fuzzy data mining
(i)

fΥ =

p


(i)

f Υk ,(5)k=1

which is commonly implemented by taking the minimum
function as the intersection operator. Hence, the fuzzy valueof Υ can be computed by
(i)

(i)

f Υ = min f Υk .

(6)1≤k≤ pBased on the above equation, the fuzzy support of Υ isdefined as follows.
Definition 4 (Fuzzy support) The fuzzy support of Υ isdefined by
1  (i)fΥ .
nn

FuzzySupport (Υ ) =

(7)

i=1

If the fuzzy support of Υ is greater than the minimum support
suppor tmin , Υ is then added to the large p-itemset L p . The
collection of large itemsets continues until L p = ∅.
The fuzzy association rules are built upon the large itemsets and their fuzzy confidence. Given a large p-itemset
L p = {Υ1 , . . . , Υ p }, the candidate rules have the followingform:
X → Y,X, Y ⊂ L p and X ∩ Y = ∅,(8)

where X and Y are two disjoint subsets of L p representing
the antecedent and consequent, respectively. The candidate
rules need to be further examined to see if they satisfy theminimum confidence.
Definition 5 (Fuzzy confidence) The fuzzy confidence of acandidate rule R : X → Y associated with L p is defined by
FuzzyConfidence (R) =FuzzySupport(X ∪ Y ).
FuzzySupport(X )(9)

If a candidate rule has fuzzy confidence greater than or equal
to the minimum confidence, then it is qualified as a fuzzy
association rule. Note that all possible candidate rules for thelarge itemset L p need to be examined.
As above indicated, the membership functions exert asignificant influence over fuzzy association rules. Optimization of membership functions serves as a key task in fuzzy
association rule mining. Several studies propose using evolutionary algorithms to optimize the parameters of membershipfunctions. Hong et al. (1999, 2006) developed GAs for
fuzzy transaction data mining. Experimental results showthat GAs can find appropriate settings for membership functions. In addition, they presented the divide-and-conquer

strategy to improve the efficiency of genetic-fuzzy data
mining (Hong et al. 2008). Cai et al. (2010) adopted
nonlinear particle swarm optimization (PSO) for mining
fuzzy association rules. In the PSO algorithm, a particle represents all the parameters of membership functions.
Mishra et al. (2011) applied PSO to mine fuzzy frequent
patterns from gene expression data. The initial population is generated by the frequent pattern growth method,
and the fitness is defined as the mean-squared residue
score.
Aside from membership functions, the minimum supportand minimum confidence are two important parameters tobe determined. Asadollahpoor-Chamazi et al. (2013) devised
an adaptive strategy for setting the minimum support threshold in a cluster-based GA. Chen et al. (2013) presented afuzzy coherent rule mining algorithm, in which the fuzzycoherent rules are defined by four conditions that are used
to replace the minimum support. Instead of generating rules,
Alcalá-Fdez et al. (2011) used GA to select fuzzy association rules in the fuzzy rule-based classification system. Lee
et al. (2014, 2016) devised a radio frequency identificationbased recursive process mining system, where GA evolves
a population of fuzzy rules rather than membership functions to find the relations of process parameters and productquality. The cost of calculating the support values is anotherissue at fuzzy association rule mining. To reduce the computational cost, Chen et al. (2008) proposed dividing the
population into several clusters and calculating only the
support value of representative chromosome of each cluster.
Some studies consider multiple objectives in mining of
fuzzy association rules and formulate it as a multi-objective
optimization problem (Fazzolari et al. 2013). For example, Qodmanan et al. (2011) took account of support andconfidence, and Meng and Pei (2012) included linguistic
quantifier and truth in the fitness function. The proposed
methods remove the need to specify the minimum supportand minimum confidence. Minaei-Bidgoli et al. (2013) considered more objectives in fuzzy association rule mining:support, confidence, comprehensibility (Wakabi-Waiswa andBaryamureeba 2008), and interestingness (Liu et al. 2000).
Their multi-objective evolutionary algorithm adopts Michigan approach, which encodes an association rule as asingle chromosome. Antonelli et al. (2014) developed amulti-objective evolutionary learning scheme for fuzzy rulebased classifiers with two objectives, namely accuracy andrule complexity. In the course of evolution, the association
rules and membership function parameters are optimized
concurrently. Rudziǹski (2016) considered the objectives
concerning the root-mean-square error and interpretability,
and adopted Pittsburgh approach for representation of association rules.

123

C.-K. Ting et al.
1

3 Optimization of membership functions
The membership functions play an essential role in mining
fuzzy association rules since they determine the fuzzy valueof a quantity. The setting for membership functions is key
to the expressiveness and interpretability of fuzzy sets andtherefore affects the validity of fuzzy association rules. Finding appropriate membership functions for fuzzy association
rule mining has been formulated as an optimization problem(Hong et al. 2008).
This study develops a GA using a novel chromosome
representation for fuzzy association rule mining. First, theparameters of membership functions are represented as achromosome. In this study, we propose a novel chromosome representation that additionally considers the structureof membership functions. Then, the GA generates a population of chromosomes as the basis of evolution. By mimicking
the nature evolution, the evolutionary process of GA involves
parent selection, crossover, mutation, and survival selection.
More details about the proposed GA are described below.

0
c1,1

c1,2 c2,1 c1,3 c2,2

c3,1 c2,3

c3,2

c3,3

Fig. 1 Example of three membership functions
1.2

4.5

6.2

2.3

10.8

12.0

0.1

5.7

45

9.5

sorting
0.1

1.2

2.3

4.5

5.7

structure
6.2

9.5

10.8

12.0

1

4

2

3

5

7

8

6

9

3.1 Representation
In genetic-fuzzy mining of association rules, GA is usuallyused to find appropriate membership functions for a given
item. The common membership functions include triangular,
trapezoidal, Gaussian, and bell functions; in particular, thetriangular function is most widely used due to its simplicity
and effectiveness. This study thus adopts the triangular function for membership functions, while other shape functions
are also applicable. The fuzzy region associated with a triangular membership function is parameterized by the threevertices of a triangle. Accordingly, for an item with  linguistic terms, a chromosome can be represented by 3 real-valued
genes to determine the  membership functions. Let ci, j be
the j-th parameter of i-th membership function for a given
item. A membership function must satisfy the following two
constraints:
ci,1 ≤ ci,2 ≤ ci,3

(10)

c1,2 ≤ c2,2 ≤ · · · ≤ cl,2 .

(11)

The first constraint maintains the triangular shape, and thesecond constraint ensures the order of linguistic terms. Figure 1 illustrates a legal membership function that satisfies theabove constraints. Note that the genetic operators may bringabout chromosomes violating the constraints. The genes ofthese illegal chromosomes will then be reordered to fix the
problem.
This study proposes a novel chromosome representationby considering the structure, in addition to the parameters,of membership functions. That is, a chromosome is composed of two parts: (1) parameters and (2) structure type.

123

Fig. 2 Example of chromosome representation

The structure type is indexed according to the deploymentof membership functions. Figure 2 illustrates a chromosome
and its corresponding membership functions. The first 3
real-valued genes represent the parameters of  membershipfunctions, and the last integer-valued gene indicates the structure type. When forming the membership functions, the 3
parameters are first sorted and then arranged according to thestructure index; for example, in Fig. 2 the lowest value 0.1
corresponds to the first parameter, the second lowest value
1.2 corresponds to the fourth parameter, and so forth.
The number of structure types is dependent upon theformation of membership functions. For three triangularmembership functions, there exist 93 structure types that satisfy constraints (10) and (11) on shape and order. In addition
to shape and order, two factors are crucial to the membershipfunctions for fuzzy association rules: coverage and overlap.
The former represents the range covered by all membershipfunctions for an item, while the latter is measured by thearea covered by two membership functions. In fuzzy systems,
the interpretability is associated with coverage and overlapof membership functions. According to coverage and overlap, we classify the 93 structure types into four categories inTable 1. The first category consists of 12 structure types. As
Fig. 3a illustrates, the structure types in this category haveGenetic algorithm with a structure-based representation for genetic-fuzzy data mining

full coverage and appropriate overlap between membershipfunctions. The second category includes 8 structure types,
which have appropriate overlap but incomplete coverage. The
third category has the largest number 69 of structure types.
Although these structure types can achieve full coverage,
the overlap between membership functions is inappropriate.
For example, the four structure types in Fig. 3c incur needless overlap of the first and third membership functions. The
fourth category comprises 4 structure types with partial coverage and inappropriate overlap.
Introducing structure type to chromosome representation facilitates development of heuristics for filtering out
improper membership functions. This study proposes twoheuristics considering coverage and overlap in membershipfunctions:– Coverage:
ci−1,1 ≤ ci,1 ≤ ci−1,3

(12a)

(a)
1

1

2

4

3

5

7

6

8

9

0

1

2

4

3

7

5

8

6

9

4

2

3

5

7

8

6

9

0

1

4

2

5

3

7

6

8

9

Inappropriate

694

ci+1,1 ≤ ci,3 ≤ ci+1,3(12b)– Overlap:
ci,3 ≤ ci+2,1(13)

The above inequalities secure the full coverage and appropriate overlap. Among the 93 structure types, only 12 structure
types of the first category are selected according to the twoheuristics, which guarantee proper arrangement of membership functions.

0

1

1

2

3

4

5

7

6

8

9

0

1

2

3

0

4

7

5

8

6

9

7

8

9

8

6

9

7

8

9

Type 5
1

1

4

2

3

5

6

7

8

9

0

1

4

2

Type 43536Type 48

(d)
1

2

4

5

6

7

8

3

9

0

1

1

2

7

Type 18

3

4

5

6

8

9

2

7

5

3

Type 63

1

2

3

8

6

9

0

7

4

5

6

8

9

4

7

2

5

8

Type 74

1

2

3

3

6

9

0

7

4

5

Type 7110Type 61

40

1Type 331

1

8Type 49

1

0

12

1

(c)

1

Appropriate

Overlap

Type2

1

Type 450PartialType 12

1

1

Full

1

Type 90

Coverage

(b)

1

0

Table 1 Classification of membership function structures

1

1

2

4

5

6

3

7

8

9

Type 16

0

1

4

2

5

6

3

Type 51

Fig. 3 Example structure types of the four categories. a Category I, b category II, c category III, d category IV

123

C.-K. Ting et al.

The proposed representation using the above heuristics
holds two significant advantages. First, it can effectively filter
out the structures inappropriate for coverage and overlap ofmembership functions. Second, the two heuristics decrease
the number of structure types and thus reduce the search spaceof GA. These advantages are beneficial for the convergence
speed and solution quality of the GA.

fitness of a chromosome is evaluated by the fitness function
based on fuzzy support, overlap, and coverage.
Definition 6 (Overlap factor) The overlap factor of chromosome Ck is defined by
Overlap (Ck ) =




 

max ovlratio Υi , Υ j , 1 − 1

(14)

i< j

3.2 Genetic operators
with
The genetic operators of GA include parent selection,
crossover, mutation, and survival selection. The parent selection operator picks two chromosomes from the population as
the parents for subsequent reproduction. In this study, we
adopt the well-known k-tournament selection, which picks
as a parent the best of k chromosomes randomly selectedfrom the population. Performing the tournament selection
twice yields a pair of parents.
The crossover and mutation operators generate new candidate solutions, namely offspring, by exchanging parental
information and slightly altering the composition, respectively. This study employs the max-min arithmetical (MMA)
crossover and creep mutation that are widely used in geneticfuzzy data mining (Herrera et al. 1997; Hong et al. 2008). The
MMA crossover generates four candidates in different ways:
The first two are the maximum and the minimum of the twoparents, respectively; and the other two are produced by thewhole arithmetic crossover. The best two of the candidates
are selected as offspring. The creep mutation probabilistically changes some parameters to random values. As forstructure, the type number is mutated by random resetting.
The survival selection determines the chromosomes surviving into the next generation. The principle “survival of
the fittest” is generally used in the survival selection. In thisstudy, we utilize the (μ + λ) survival selection, which considers both parent and offspring populations in the competition
for survival.

 The area covered by both Υi and Υ jovlratio Υi , Υ j =.
min ci,3 − ci,2 , c j,2 − c j,1(15)

The ratio of overlap ovlratio Υi , Υ j is determined by the
proportion of the area covered by both membership functions
to the smaller of (ci,3 − ci,2 ) and (c j,2 − c j,1 ), which standfor the right half of the left membership function and theleft half of the right membership function, respectively. The
overlap factor is nonnegative, and its best value is zero. Notethat zero overlap factor indicates adequate overlap, insteadof nonoverlap, of all pairs of membership functions.
Definition 7 (Coverage factor) The coverage factor of chromosome Ck is defined by
Coverage (Ck ) =

123

(16)

Coverage factor is inversely proportional to the range coveredby all membership functions. Therefore, a small coveragefactor is preferred, and its best value is 1 for full coverage ofthe item’s quantity.
The fitness evaluation considers the fuzzy support as wellas the suitability. The suitability is defined as the sum of
overlap and coverage factors. Formally, the fitness value ofchromosome Ck is computed by

3.3 Fitness evaluation
The fitness function guides the search direction and strongly
affects the performance of GA. For mining fuzzy association rules, the fitness function usually uses the fuzzy support
according to the largest itemset. However, this method
requires iterative calculations and is hard to be paralleled.
Hong et al. (2008) proposed using the divide-and-conquer
strategy to address this issue. Specifically, they used separate
populations for the items and considered the fuzzy supportof large 1-itemset L 1 in the fitness evaluation. In addition,
the fitness function takes the coverage and overlap of membership functions into account.
In view of the above advantages, we utilize the fitness
function proposed by Hong et al. (2008). For a given item, themax (I ).
range (Υ1 , . . . , Υl )f (Ck ) =X ∈L 1 FuzzySupport (X )Overlap (Ck ) + Coverage (Ck )

.

(17)

Note that the fitness function considers only the large 1itemset L 1 obtained from the membership functions set Ck .
The exclusion of L >1 is beneficial for balance of computation time and quality in calculating fuzzy support (Hong et al.
2008).
As an example, the fitness value of the chromosome in
Fig. 2 is calculated as follows. First, the overlap ratios for thethree membership functions are computed using (15):ovlratio (Υ1 , Υ2 ) =4.5 − 1.2
= 1.5
min(4.5 − 2.3, 5.7 − 1.2)

Genetic algorithm with a structure-based representation for genetic-fuzzy data mining

Overlap (Ck ) = (max(1.5, 1) − 1) + (max(0, 1) − 1)

Table 2 Parameter setting+ (max(1.39, 1) − 1)

Parameter

Value

Representation

Real numbers (parameters) + integer (structure)

Parent selection

2-tournament

Crossover

MMA (d = 0.35)

Crossover rate

pc = 0.8

Mutation

Creep (ε = 3)

Mutation rate

pm = 0.01

Survival selection

μ+λPopulation size

50

#Generations

500= 0.89The coverage factor is calculated by (16):Coverage (Ck ) =12.0= 1.0084
12.0 − 0.1

Suppose the item exists in five transactions with quantities
1, 5, 8, 11, and 6. We use (4) to calculate the fuzzy supportof each region:
1 1 − 0.1
+0+0+0+0
FuzzySupport (Υ1 ) =5 2.3 − 0.1

0=0min(4.5 − 2.3, 9.5 − 6.2)
10.8 − 6.2
ovlratio (Υ2 , Υ3 ) == 1.39min(10.8 − 5.7, 9.5 − 6.2)
ovlratio (Υ1 , Υ3 ) =Using (14), we can obtain the overlap factor= 0.08
10.8 − 8
5 − 1.2
1+
0+
FuzzySupport (Υ2 ) =5
5.7 − 1.2 10.8 − 5.7
10.8 − 6+0 +10.8 − 5.7(a) 8.5

(b) 9

8

8.5
8
7.5

7

Fitness

Fitness

7.5

6.5
6

6.5
6

5.5

5.5
GA
GA93
GA12

5
4.5

7

50

100

150

200

250

300

350

400

GA
GA93
GA12

5
450

4.5

500

50

100

150

Generations

(d) 9

9

8.5

8.5

8

8

300

350

400

450

500

450

500

7.5

7.5

Fitness

Fitness

250

Generations(c) 9.5

7
6.5

7
6.5
6

6

5.5

5.5

GA
GA93
GA12

5
4.5

200

50

100

150

200

250

300

Generations

350

400

GA
GA93
GA12

5
450

500

4.5

50

100

150

200

250

300

350

400

Generations

Fig. 4 Progress of MBF against generations for GA, GA93 , and GA12 on different datasets. a 10 k transactions, b 30 k transactions, c 50 ktransactions, d 90 k transactions

123

C.-K. Ting et al.

= 0.47
8 − 6.2
1
0+0+
FuzzySupport (Υ3 ) =+1+0
5
9.5 − 6.2

4 Experimental results= 0.31Given a minimum support 0.25, the large 1-itemset is
L 1 = {Υ2 , Υ3 } in that Υ2 and Υ3 have fuzzy support greaterthan 0.25. Summing their fuzzy support values yields
FuzzySupport (Ck ) = 0.47 + 0.31 = 0.78
Hence, the fitness valuef (Ck ) =0.78
= 0.410.89 + 1.0084

As aforementioned, this study proposes two heuristics forthe structure types considering overlap and coverage. The
two heuristics guarantee that the coverage factor is smaller); in addition, they help to eliminate the gap
than cmax(Il,3 −c1,1
between membership functions and avoid strong overlap.
Table 3 MBF and p-values for
GA, GA93 , and GA12 on thedata of different sizes#Tr. (k)This study conducts a series of experiments to examine theperformance of the proposed GA on optimization of membership functions for fuzzy association rule mining. In theexperiments, we investigate the effects of the proposed chromosome representation and the two heuristics about coverage
and overlap. The test algorithms include GA (Hong et al.
2008), GA93 (GA using the novel representation), and GA12
(GA93 applying the two heuristics), where the subscripts 93
and 12 account for the numbers of structure types. Table 2
summarizes the parameter setting for the test algorithms. The
minimum support is set to 0.04. Different data sizes are tested
in the experiments, including 10, 30, 50, 70, and 90 k transactions, each of which consists of 64 items (Hong et al. 2008).
Each experiment includes 30 independent runs of each algorithm.
Figure 4 shows the progress of mean best fitness (MBF)
over generations for the test algorithms on different datasets.
According to the results, GA using the proposed representa-

MBF

p-value

GA

GA93

GA12

GA:GA93

GA:GA12GA93 :GA12

10

8.16

8.40

8.47

+2.64E−14+6.16E−23+1.56E−03

30

8.14

8.80

8.89

+4.86E−34+1.69E−47+1.51E−05

50

8.18

9.09

9.16

+7.27E−47+6.88E−49+1.78E−04

70

8.15

8.73

8.82

+2.15E−30+4.22E−45+1.27E−04

90

8.15

8.75

8.88

+9.69E−27+2.72E−46+1.10E−06

The p-values account for the results of t-test on the MBF obtained from X and Y algorithms (denoted by
X :Y ), where positive p-values indicate that Y is superior to X . Boldfaced MBF marks the best result among
the three algorithms; boldfaced p-values denote the statistical significance with confidence level α = 0.01
Table 4 Overlap, coverage,
suitability, and fuzzy support ofmembership functions obtained
from GA, GA93 , and GA12 on
the data of different sizes#Tr. (k)
10

30

50

70

90

Algorithm

Overlap

Coverage

Fuzzy support
11.02

GA

23.23

64.20

87.43

GA93

6.92

64.13

71.05

9.27

GA12

0.17

64.10

64.27

8.51
10.96

GA

23.01

64.16

87.17

GA93

5.76

64.12

69.88

9.57

GA12

0.18

64.11

64.28

8.93
10.98

GA

22.74

64.18

86.92

GA93

5.93

64.13

70.06

9.89

GA12

0.13

64.10

64.23

9.19
11.05

GA

23.54

64.20

87.74

GA93

6.48

64.13

70.60

9.58

GA12

0.14

64.10

64.24

8.85
11.05

GA

23.60

64.18

87.78

GA93

7.10

64.13

71.23

9.67

GA12

0.13

64.10

64.23

8.91

Boldface marks the best result among the three algorithms

123

Suitability

Genetic algorithm with a structure-based representation for genetic-fuzzy data mining(a) 60(b) 60

GA
GA93
GA12

50

50
40

Overlap40

Overlap

GA
GA93
GA12

30

30

20

20

10

10

0

50

100

150

200

250

300

350

400

450

0

500

50

100

150

Generations

300

350

(d) 78

GA
GA93
GA12

76

400

450

500

450

500

450

500

GA
GA93
GA12

76
74

Coverage

74

Coverage

250

Generations(c) 78

72
70

72
70

68

68

66

66

64

50

100

150

200

250

300

350

400

450

64

500

50

100

150

Generations

11

11

10.5

10.5

Fuzzy Support(f) 11.5

10
9.5
9
8.5
8

250

300

350

400

10
9.5
9
8.5
8

GA
GA93
GA12

7.5
7

200

Generations(e) 11.5

Fuzzy Support

200

50

100

150

200

250

300

350

400

GA
GA93
GA12

7.5
450

500

Generations

7

50

100

150

200

250

300

350

400

Generations

Fig. 5 Variation of overlap (top), coverage (middle), and fuzzy support(bottom) of membership functions obtained from GA, GA93 , and GA12
among 64 items on the data of 10 k (left) and 90 k (right) transactions.

a Overlap (10 k transactions), b overlap (90 k transactions), c coverage(10 k transactions), d coverage (90 k transactions), e fuzzy support (10 ktransactions), f fuzzy support (90 k transactions)tion, i.e., GA93 and GA12 , converges faster than the original
GA does, validating the effectiveness of the new representation on improving the search efficiency of GA. In addition, thefaster convergence of GA12 than GA93 indicates the advantages of the two heuristics.

Table 3 presents the MBF obtained from the three test
algorithms for all 64 items. The table also lists the p-valuesof one-tailed t-test on the MBF values. With confidence level
α = 0.01, the t-test results indicate that GA using the new
representation, namely GA93 and GA12 , achieves signifi-

123

C.-K. Ting et al.

(a)

(b)

(c)

1

1

1

0

0

2

4

6

8

10

12

0

0

2

4

6

8

10

12

0

(d)

(e)

(f)

1

1

1

0

0

2

4

6

8

10

12

0

0

2

4

6

8

10

12

0

(g)

(h)

(i)

1

1

1

0

0

2

4

6

8

10

12

0

0

2

4

6

8

10

12

0

0

2

4

6

8

10

12

0

2

4

6

8

10

12

0

2

4

6

8

10

12

Fig. 6 Comparison of membership functions obtained from GA, GA93
and GA12 on the data of 10 k (left), 50 k (center), and 90 k (right) transactions. a GA (10 k transactions), b GA (50 k transactions), c GA (90 ktransactions), d GA93 (10 k transactions), e GA93 (50 k transactions),f GA93 (90 k transactions), g GA12 (10 k transactions), h GA12 (50 ktransactions), i GA12 (90 k transactions)cantly higher fitness than the original GA does; meanwhile,
GA12 significantly outperforms GA93 on all datasets. These
superior outcomes validate the benefits of the representationand two heuristics.
Next, we investigate the influences of the proposed representation and heuristics on the overlap, coverage, and fuzzy
support of membership functions obtained. As Table 4 indicates, GA benefits from the two heuristics in coverage andoverlap: GA93 and GA12 obtain better coverage and overlap than GA does. In addition, GA12 gains the best coverage
and overlap among the three test algorithms. Figure 5 further shows that GA12 can find membership functions withgood overlap and converge faster than other approaches do.
In general, GA12 and GA93 achieve membership functions
with better suitability; nonetheless, they lead to lower fuzzy
support than GA. The results on Table 4 and Fig. 5 reflect
the trade-off between suitability and fuzzy support. The twoheuristics impose constraints on structure types for highsuitability; on the other hand, they discourage sacrificing
suitability for fuzzy support. As Fig. 6 shows, GA gains thehighest fuzzy support at the cost of suitability; in particular,
the overlap of membership functions obtained from GA isso high that the fuzzy regions become trivial. By contrast,
GA93 and GA12 maintain adequate overlap and full coverage while pursuing high fuzzy support, which results in morereasonable membership functions and better fitness.

123

5 Conclusions
This study proposes a GA for optimization of membershipfunctions for fuzzy association rule mining. For the GA,
we design a novel chromosome representation that considers structure types in addition to parameters of membership

Genetic algorithm with a structure-based representation for genetic-fuzzy data mining

functions. Based on the new representation, two heuristics
are developed for securing the coverage and moderating theoverlap of membership functions. The heuristics can filter out
inappropriate arrangement of membership functions; moreover, they help to reduce the search space. For example,
the number of structure types is reduced from 93 to 12 forthree membership functions; that is, 81 inappropriate structure types are filtered out in light of coverage and overlap.
A series of experiments is carried out to examine the performance of the proposed GA. The experimental results on
10–90 k transactions show that the proposed GA achieves
significant performance improvement. The new representation and two heuristics enhance the coverage and overlapof membership functions; in addition, they improve the fitness value and convergence speed of GA. These preferable
outcomes show the utility of the proposed chromosome representation and heuristics for the GA. They also validate theeffectiveness and efficiency of the GA in finding appropriate
membership functions for mining fuzzy association rules.
Future work may further expand the use of the structure types and design of local search operator. The structure
type reflects the relationship between membership functions
and facilitates designing strategies for their arrangement. In
addition to overlap and coverage, advanced heuristics arepromising for enhancing the performance of GA on fuzzy
association rule mining.
Acknowledgments The authors would like to thank the editor andreviewers for their valuable comments and suggestions.
Compliance with ethical standards
Conflict of interest The authors declare that they have no conflict ofinterest.
Ethical approval This article does not contain any studies with humanparticipants or animals performed by any of the authors.

References
Agrawal R, Imielinski T, Swami AN (1993) Mining association rules
between sets of items in large databases. In: Proceedings of the
ACM SIGMOD International Conference on Management of Data
Agrawal R, Srikant R (1994) Fast algorithms for mining association
rules. In: Proceedings of the international conference on very large
data bases, pp 487–499
Alcalá-Fdez J, Alcalá R, Herrera F (2011) A fuzzy association rulebased classification model for high-dimensional problems withgenetic rule selection and lateral tuning. IEEE Trans Fuzzy Syst
19(5):857–872
Antonelli M, Ducange P, Marcelloni F (2014) A fast and efficient
multi-objective evolutionary learning scheme for fuzzy rule-basedclassifiers. Inf Sci 283(1):36–54
Asadollahpoor-Chamazi M, Minaei-Bidgoli B, Nasiri M (2013) Deriving support threshold values and membership functions using
the multiple-level cluster-based master-slave IFG approach. Soft
Comput 17(7):1227–1239

Cai G-R, Li S-Z, Chen S-L (2010) Mining fuzzy association rules byusing nonlinear particle swarm optimization. Quant Log Soft Comput 82:621–630
Chan K, Au WH (1997) Mining fuzzy association rules. In: Proceedings of the international conference on information and knowledge
management, pp 209–215
Chang C-C, Lin C-J (2011) LIBSVM: a library for support vector
machines. ACM Trans Intell Syst Technol 2(27):1–27
Chen C-H, Li A-F, Lee Y-C (2013) A fuzzy coherent rule mining algorithm. Appl Soft Comput 13(7):3422–3428
Chen C-H, Tseng V-S, Hong T-P (2008) Cluster-based evaluation infuzzy-genetic data mining. IEEE Trans Fuzzy Syst 16(1):249–262
Fayyad UM, Piatetsky-Shapiro G, Smyth P (1996a) From data mining
to knowledge discovery in databases. AI Mag 17:37–54
Fayyad UM, Piatetsky-Shapiro G, Smyth P (1996b) Advances inknowledge discovery and data mining. In: From data mining toknowledge discovery: an overview, AAAI, pp 1–34
Fazzolari M, Alcala R, Nojima Y, Ishibuchi H, Herrera F (2013) A
review of the application of multiobjective evolutionary fuzzy systems: current status and further directions. IEEE Trans Fuzzy Syst
21(1):45–65
Herrera F, Lozano M, Verdegay JL (1997) Fuzzy connectives based
crossover operators to model genetic algorithms population diversity. Fuzzy Sets Syst 92(1):21–30
Hong T-P, Chen C-H, Lee Y-C, Wu Y-L (2008) Genetic-fuzzy data mining with divide-and-conquer strategy. IEEE Trans Evol Comput
12(2):252–265
Hong T-P, Chen C-H, Wu Y-L, Lee Y-C (2006) A GA-based fuzzy mining approach to achieve a trade-off between number of rules andsuitability of membership functions. Soft Comput 10(11):1091–
1101
Hong T-P, Kuo C-S, Chi S-C (1999) Mining association rules fromquantitative data. Intell Data Anal 3(5):363–376
Hong T-P, Lee C-Y (1996) Induction of fuzzy rules and membershipfunctions from training examples. Fuzzy Sets Syst 84(1):33–47
Kuok CM, Fu A, Wong MH (1998) Mining fuzzy association rules indatabases. ACM SIGMOD Rec 27(1):41–46
Lee CK-H, Choy K-L, Ho GT-S, Lam CH-Y (2016) A slippery
genetic algorithm-based process mining system for achieving better quality assurance in the garment industry. Expert Syst Appl
46:236–248
Lee CK-H, Ho GT-S, Choy K-L, Pang GK-H (2014) A RFID-based
recursive process mining system for quality assurance in the garment industry. Intern J Prod Res 52(14):4216–4238
Liu B, Hsu W, Chen S, Ma Y (2000) Analyzing the subjective interestingness of association rules. IEEE Intell Syst Their Appl
15(5):47–55
Meng D, Pei Z (2012) Extracting linguistic rules from data sets using
fuzzy logic and genetic algorithms. Neurocomputing 78(1):45–54
Minaei-Bidgoli B, Barmaki R, Nasiri M (2013) Mining numericalassociation rules via multi-objective genetic algorithms. Inf Sci
233(1):15–24
Mishra S, Mishra D, Satapathy SK (2011) Particle swarm optimization
based fuzzy frequent pattern mining from gene expression data.
In: Proceedings of the international conference on computer &communication technology, pp 15–20
Piatesky-Shapiro G, Brachman R, Klösgen W, Simoudis E (1996)
An overview of issues in developing industrial data mining andknowledge discovery applications. In: Proceedings of knowledge
discovering and data mining, pp 89–95
Qodmanan HR, Nasiri M, Minaei-Bidgoli B (2011) Multi objective
association rule mining with genetic algorithm without specifying minimum support and minimum confidence. Expert Syst Appl38(1):288–298

123

C.-K. Ting et al.
Rudzinski F (2016) A multi-objective genetic optimization ofinterpretability-oriented fuzzy rule-based classifiers. Appl Soft
Comput 38:118–133
Srikant R, Agrawal R (1996) Mining quantitative association rules inlarge relational tables. ACM SIGMOD Rec 25(2):1–12
Wagstaff K, Cardie C, Rogers S, Schroedl S (2001) Constrained Kmeans clustering with background knowledge. In: Proceedings ofthe international conference on machine learning, pp 577–584

123

Wakabi-Waiswa P, Baryamureeba V (2008) Extraction of interesting
association rules using genetic algorithms. Int J Comput ICT Res
2:1139–1818