Noname manuscript No.
(will be inserted by the editor)

Mining Fuzzy Association Rules Using a Memetic Algorithm
Based on Structure Representation
Chuan-Kang Ting · Rung-Tzuo Liaw · Ting-Chen Wang · Tzung-Pei
Hong

the date of receipt and acceptance should be inserted later

Abstract The association rules render the relationshipamong items and have become an important targetof data mining. The fuzzy association rules introduce
fuzzy set theory to deal with the quantity of items in
the association rules. The membership functions playa key role in the fuzzification process and, therefore,
significantly affect the results of fuzzy association rulemining. This study proposes a memetic algorithm (MA)for optimizing the membership functions in fuzzy association rule mining. The MA adopts a novel chromosome representation that considers the structures ofmembership functions. Based on the structure representation, we develop a local search operator to improvethe efficiency of the MA in exploring good membership functions. Two local search strategies for the MA
are further investigated. This study conducts a series ofexperiments to examine the proposed MA on different
amounts of transactions. The experimental results showthat the MA outperforms state-of-the-art evolutionary
algorithms in terms of solution quality and convergence
speed. These preferable results show the advantages ofthe structure-based representation and the local search
in improving the performance. They also validate thehigh capability of the proposed MA in mining fuzzy
association rules.

C.-K. Ting · R.-T. Liaw · T.-C. Wang
Department of Computer Science and Information Engineering
National Chung Cheng University, Taiwan
E-mail: {ckting, lrt101p, wtc102p}@cs.ccu.edu.tw
T.-P. Hong
Department of Computer Science and Information Engineering
National University of Kaohsiung, Taiwan
Department of Computer Science and Engineering
National Sun Yat-sen University, Taiwan
E-mail: tphong@nuk.edu.tw

Keywords Memetic computing · Genetic algorithm ·Structure representation · Local search · Fuzzy
association rules · Membership function

1 Introduction
Data mining explores the information hidden in thedata and transforms it into explicit valuable knowledge [10]. Several data mining technologies have been
proposed to discover knowledge for different purposes,
such as classification, clustering, and association rules[9]. Mining association rules is an important data mining technology aiming to find the relationship among
items, also known as a homogeneous group or an affinity group, from the database and has achieved manysuccessful stories, e.g., the prediction of customers’ behavior in Walmart.
The Apriori algorithm is well-known for mining association rules [1]. This method establishes association
rules based on the frequent itemsets according to a userdefined minimum confidence. Srikant and Agrawal [31]extended the rules into quantitative association rules,
which can tackle the data of quantitative values or categories. They presented a method similar to the Apriori algorithm but requiring an additional preprocessof data discretization. The fuzzy set theory is introduced to different aspects of association rules [6, 17, 19].
In particular, Hong et al. [15, 16] proposed the fuzzy
transaction data mining algorithm (FTDA) by adopting fuzzy sets to analogue the values of original data. In
the FTDA, quantitative values of data are transformed
into fuzzy values according to the membership functions. The results are known as the fuzzy association
rules. The FTDA holds the advantages in suitability,
tolerance, and extension for nonlinear systems.

2

Chuan-Kang Ting et al.

The membership functions establish the mappingfrom a quantity to a fuzzy value and thus exert a significant influence on fuzzy association rule mining. Recently, some studies adopt genetic algorithm (GA) to
optimize the membership functions and receive promising results. However, two important issues remain open
in the genetic-fuzzy association mining. First, the current variants of GA ordinarily use integers or real values as the chromosome representation for membershipfunctions. The structure of membership functions plays
a crucial role but is not considered in the chromosome
representation. Second, GA is well known for good global
search but performs poorly at local search. This weakness makes it harder for GA to find the best membership functions for fuzzy data mining, especially in alarge number of transactions.
This paper proposes a memetic algorithm (MA) toaddress the above issues. Beyond Darwinian genetics,
MA considers the Lamarckian or Baldwinian effect byintegrating local search into evolutionary algorithms.
This integration has been widely shown as to be effective in improving the performance of evolutionary algorithms [12, 18, 26, 33]. The proposed MA considers the
structure of membership functions in the chromosome
representation. The novel representation facilitates local search in the various structures of membership functions. This study accordingly designs a local search operator and incorporates it into a GA as an MA for
enhancement of its search capability, which is helpful
for the genetic-fuzzy system to mine association rules
among a large amount of transactions. In addition, twostrategies for the local search are investigated. A seriesof experiments, including 10,000 to 1,000,000 transactions, is conducted to examine the performance of the
proposed MA in different data scales.
The remainder of this paper is organized as follows. Section 2 introduces fuzzy association rule mining. Section 3 sheds light on the proposed MA. Section 4
presents and discusses the experimental results. Finally,
we draw conclusions and recommend the directions for
future work in Section 5.

the transactions in Walmart infers “If buying bread andcheese, then buying milk ”.
Given an itemset I = {I1 , . . . , Im } with m items anda database D = {T1 , . . . , Tn } with n transactions Tk ⊆I, an association rule X → Y represents the possibility:
if X ⊆ Ti then Y ⊆ Ti . Two metrics, namely support
and confidence, are adopted to measure an association
rule.

2 Mining Fuzzy Association Rules

FuzzySupport (Rj,k ) =The association rules reveal the coincidence of items
among transactions. This information is important andcommonly used in the analysis of customers’ behavior
and business intelligence. An association rule has a general form:

If a fuzzy region Rj,k has FuzzySupport (Rj,k ) ≥ θsupp ,it is included to the large 1-itemset L1 like the Apriorialgorithm.
For a set of fuzzy regions R = {R1 , . . . , Rp }, its
fuzzy value in transaction Ti is computed by the inter(i)section of the membership values fRk , i.e.,

Definition 1 (Support) The support of association
rule X → Y is defined by the probability that X andY 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)

Agrawal and Srikant [1] proposed the Apriori algorithm
to mine the association rules. Given a minimum support θsupp , the algorithm selects large itemsets L ={L1 , . . . , Lp } from the candidate itemsets C = {C1 . . . , Cp }progressively. The large itemsets obtained are used togenerate the candidate association rules. An associate
rule is valid if its confidence is greater than or equal toa predetermined minimum confidence θconf .
The original association rules consider the existenceof items but ignore their quantity. To address this issue, Hong et al. [16] introduced the notion of fuzzy sets
to association rules, thereby considering the quantityof items. The fuzzy association rules involve the fuzzy
support and fuzzy confidence based on the membershipfunctions.
Given a database D with n transactions among mitems. Let Rj,k denote the fuzzy region of the k-th membership function for item Ij . The fuzzy membership(i)value fj,k of region Rj,k is determined by the quantity(i)vj of the j-th item in the i-th transaction Ti .
Definition 3 The fuzzy support of region Rj,k is calculated byn

X → Y,(1)

where X and Y are sets of items. For example, theassociation rule {bread, cheese} → {milk} mined from

(i)
fR =

p
\
k=1

(i)

fRk .

1 X (i)f .
n i=1 j,k

(4)

(5)

Mining Fuzzy Association Rules Using a Memetic Algorithm Based on Structure Representation

The minimum function is widely used as the intersection operator in fuzzy systems. The fuzzy value of R is
therefore(i)(i)

fR = min fRk .

(6)

1≤k≤p

Based on the above equation, the fuzzy support of
R is defined as follows.
Definition 4 (Fuzzy Support) The fuzzy support of
R is defined byn

1 X (i)FuzzySupport (R) =f .
n i=1 R(7)

If the fuzzy support of R is greater than the minimum
support θsupp , R is added to the large p-itemset Lp . The
collection of large itemsets continues until Lp = ∅.
The fuzzy association rules are built upon the large
itemsets and their fuzzy confidence. Given a large pitemset Lp = {R1 , . . . , Rp }, a candidate rule has theform:
X → Y,X, Y ⊂ Lp and X ∩ Y = ∅,(8)

where X and Y are two disjoint subsets of Lp , which
represent the antecedent and consequent, respectively.
The candidate rules need to be further examined on
their confidence values.
Definition 5 (Fuzzy Confidence) The fuzzy confidence of a candidate rule R : X → Y associated with
Lp 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 θconf , then it isqualified as a fuzzy association rule. All the candidate
rules generated from the large itemset Lp must be examined.
The membership functions determine the mappingof fuzzy values, and thus, exert a significant influence on
the fuzzy association rules. The common membershipfunctions include the triangular, trapezoidal, Gaussian,and bell functions. Each membership function has certain parameters to tune concerning the fuzziness. For
example, in the most widely used type of membershipfunction, namely the triangular function, there exist
three parameters (vertices) to be set. The optimizationof membership functions, therefore, becomes a key task
in fuzzy association rule mining. To address this task,
several studies utilize evolutionary algorithms in viewof their high capability in optimization. Hong et al. [16]developed GAs for fuzzy data mining and showed thatGAs can gain the appropriate membership functions

3

for the fuzzy association rules. They further proposedusing a divide-and-conquer strategy to increase the efficiency of genetic-fuzzy data mining [15]. Chen et al. [8]devised a cluster-based method to reduce the computational cost at evaluation. The proposed method divides
the population into several clusters and adopts the support value of a representative chromosome in each cluster for evaluation. Alcalá-Fdez et al. [2] used GA toselect the fuzzy association rules rather than optimize
the membership functions. Lee et al. [20] proposed using GA to directly evolve a population of fuzzy rules
instead of membership functions in mining of the process parameters and product quality. Moreover, Chen etal. [7] presented a fuzzy coherent rule mining algorithm
to deal with the issue of setting the minimum support.
In addition to GA, particle swarm optimization (PSO)
and other evolutionary algorithms are adopted to optimize the parameters of membership functions. Cai etal. [5] devised a nonlinear PSO method for mining fuzzy
association rules, where a particle represents all the parameters of membership functions. Mishra et al. [24]applied PSO to mine gene expression data for fuzzy
frequent patterns. The PSO generates the initial population using the frequent pattern growth method toimprove its performance.
Beyond single objective, multi-objective optimization is also considered in fuzzy association rule mining [11]. These studies take more than one objective
into account at the optimization of membership functions. Qodmanan et al. [28] considered both the support and confidence, and Meng and Pei [22] included
a linguistic quantifier and truth in the fitness function. Minaei-Bidgoli et al. [23] considered more objectives, including support, confidence, comprehensibility,
and interestingness. They used the Michigan approachfor the multi-objective evolutionary algorithm, where
each chromosome represents a single association rule.
By contrast, Rudziński [29] adopted the Pittsburgh approach for representation of the association rules considering two objectives, i.e., the root mean square error and interpretability. Antonelli et al. [3] presented amulti-objective evolutionary learning scheme to simultaneously optimize the association rules and the membership function parameters.
Memetic algorithms have achieved considerable success in data mining, such as classification [30], clustering [27], feature selection [25], and data processing [21].
Some research applies MA to fuzzy data mining. Gál etal. [13] proposed an MA based on bacterial evolutionary algorithm (BEA) for extracting the fuzzy rules oftrapezoidal membership functions. The local search operator relies on bacterial mutation and the LevenbergMarquardt method. Balázs and Kóczy [4] devised a bac-4

Algorithm 1 Memetic Algorithm
1: P ← Initialize()
2: Evaluate(all x ∈ P )3: while not terminated do
4:P0 ← ∅
5:
repeat6:
x1 , x2 ← Select(P )7:y 1 , y 2 ← Crossover(x1 , x2 )8:y i ← Mutate(y i ), i ∈ {1, 2}
9:
Evaluate(y i ), i ∈ {1, 2}
10:
P 0 ← P 0 ∪ {y 1 , y 2 }11:until P 0 is full12:
P 0 ← LocalSearch(P 0 )13:
P ← Survive(P, P 0 )14: end while

terial memetic programming for building a hierarchicalinterpolative fuzzy system. The bacterial memetic programming combines bacterial genetic programming witha gradient based local search operator. Ho and Garibaldi[14] mined Takagi-Sugeno-Kang (TSK) fuzzy models
by a memetic parallel GA, which integrates a parallel GA for the premise of fuzzy rules with a QR Householder least square method for the consequence of fuzzy
rules. The premises and consequences of fuzzy rules
are evolved by different search mechanisms. Tsakonas[32] considered memetic genetic programming (GP) for
constructing a Takagi-Sugeno fuzzy system. The MA
hybridizes GP with the least square and the gradientdescent methods. The above studies show that local
search can improve the convergence of evolutionary algorithms. Therefore, this paper considers an MA basedon GA with local search on the structure types for improving the convergence speed and solution quality infuzzy association rules mining.

3 The Proposed Memetic Algorithm
This study designs a memetic algorithm (MA) to optimize the membership functions. The proposed MA isbased on the evolutionary scheme of GA and a local
search operator. The MA adopts a novel chromosome
representation considering the structures, in addition
to the parameters, of the membership functions. The
genetic operators are further developed to adapt to the
new representation. Moreover, we devise a local search
operator that utilizes the structure information for the
MA. Algorithm 1 presents the framework of the proposed MA. More details are described below.

3.1 Representation
A membership function is composed of parameters to
be optimized in fuzzy association rule mining. These

Chuan-Kang Ting et al.
1

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

0

Fig. 2: Example of inappropriate membership functions

parameters are encoded as genes of a chromosome inevolutionary algorithms. The structure of membershipfunctions, however, is essential yet neglected in the conventional chromosome representation.
This study proposes a novel chromosome representation considering the parameters plus the structure ofmembership functions. Restated, a chromosome comprises two parts: 1) parameters, and 2) structure type.
Given an item using ` linguistic terms to describe its
quantity, the first part of a chromosome is represented
by 3` real-valued genes to determine the parameters of `membership functions. This part is conventionally used
for chromosome representation. In addition, this study
introduces the structure information to chromosomes.
The structure type is indexed according to the deployment of membership functions. For example, the first3` real-valued genes in Figure 3 represent the parameters of ` membership functions, and the last integervalued gene indicates the structure type. When forming
the membership functions, the 3` parameters are firstsorted and then arranged according to the structureindex. Algorithm 2 presents the pseudocode of converting a chromosome into membership functions. As
illustrated in Fig. 3, according to the structure type
ST (τ = 11) = (1, 2, 4, 3, 7, 5, 6, 8, 9), the lowest value
0.7 corresponds to the first parameter, the third lowest
value 4.5 corresponds to the fourth parameter, and soforth.
Legality and suitability are two key factors needed
to be considered in the parameter setting of member-

Mining Fuzzy Association Rules Using a Memetic Algorithm Based on Structure Representation

Algorithm 2 Conversion
1: procedure Convert(x)2:x0 ← Sort(x)
3:
k←1
4:
for i ← 1 to ` do5:
for j ← 1 to 3 do
6:ci,j ← x0ST (τ,k)
7:k ←k+18:
end for9:
end for
10: end procedure

2.20. x = (x1 , . . . , x3` , τ ). Sort x1 , . . . , x3`

6.10

9.10

4.50

12.00

0.70

Sorting
0.70

7.50

8.40

11

Structure
2.20

4.50

5.60

6.10

7.50

8.40

9.10

12.00

1 2 4 3 7 5 6 8 9. ST (τ, k): k-th element of. τ -th structure

ship functions. The former regulates that the parameters should comply with the form of membership function, while the latter is concerned with the expressiveness and interpretability of fuzzy sets.
Legality. Given a triangular membership function1 andlet ci,j denote the j-th parameter of i-th membershipfunction for a given item. A chromosome 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 andthe second constraint regulates the order of linguistic
terms. Figure 1 illustrates a legal membership functionthat satisfies the above constraints.
Suitability. In addition to legality, the suitability must
be considered in the optimization of membership functions. Hong et al. [15] defined the suitability by coverage and overlap of membership functions. The coverage represents the range covered by all the membershipfunctions for an item; the overlap is measured by thearea covered by two membership functions. Figure 2
illustrates inappropriate membership functions, where
the overlap of the left two membership functions is too
high, and the coverage is incomplete, due to the gap
between the right two membership functions.
The following inequalities secure the full coverageand moderate overlap:– Coverage:
ci−1,1 ≤ ci,1 ≤ ci−1,3(12a)ci+1,1 ≤ ci,3 ≤ ci+1,3(12b)– Overlap:
ci,3 ≤ ci+2,1

5.60

5

(13)

1 This study uses triangular membership functions; however,other shapes such as trapezoidal and bell functions are also applicable.

Fig. 3: Example of chromosome representation

The proposed representation, consisting of parametersand structure, can help refine the chromosomes for theappropriate membership functions. For fuzzy association rules using three triangular membership functions,the nine vertices account for 9! = 362880 permutations.
Among them, the proposed chromosome representationconsiders only 93 legal structure types that satisfy constraints (10) and (11) on shape and order, which substantially filters out the illegal membership functions
and reduces the search space. Furthermore, in the lightof suitability, 12 structures types are selected as per(12) and (13). These 12 structure types have an appropriate arrangement of membership functions, i.e., fullcoverage and moderate overlap.

3.2 Fitness Evaluation
In mining fuzzy association rules, the fuzzy support ofthe largest itemset is usually used to evaluate the fitnessof chromosomes. This evaluation is time-consuming due
to the time complexity O (2m ) for garnering the largest
itemset. To address this issue, Hong et al. [15] presented
the divide-and-conquer strategy for fitness evaluation infuzzy data mining. More specifically, the fitness function adopts the fuzzy support of the large 1-itemset L1
in place of the largest itemset to decrease the computational cost. The fitness function further considers thesuitability based on the coverage and overlap of membership functions. In light of these advantages, we use
this fitness function for the MA.
The fitness function evaluates a chromosome according to the fuzzy support and suitability. The fuzzy support is calculated using (7); the suitability is composedof the coverage and overlap of the membership functions defined in the chromosome.

6

Chuan-Kang Ting et al.

example, the k-tournament selection chooses the bestof the k chromosomes as a parent.
The reproduction process includes two operators,i.e., crossover and mutation. The crossover operator
i<jgenerates the offspring by recombining the genetic information of the parents. This study adopts the uniwith
form crossover that is widely used for GA. The uniform
The area covered by both Ri and Rj crossover assigns each gene randomly from either parent
ovlratio (Ri , Rj ) =.
min (ci,3 − ci,2 , cj,2 − cj,1 )to produce offspring. Next, the MA performs mutation(15)
for small changes on the offspring. Here we use the creep
mutation and random resetting to randomly alter the
The ratio of overlap ovlratio (Ri , Rj ) accounts for theparameters and structure type, respectively.
proportion of the area covered by both the membership
Noteworthily, the crossover and mutation operations
functions to the smaller of (ci,3 − ci,2 ) and (cj,2 − cj,1 ),may result in illegal offspring violating constraints (10)which are the right half of the left membership funcand (11). In the conventional chromosome represention and the left half of the right membership function,tation without structure information, these illegal offrespectively. The overlap factor is nonnegative with aspring need to be fixed by rearranging the sequence ofbest value of 0. Note that the zero overlap factor imgenes. By contrast, the proposed structure-based repplies a moderate overlap, rather than non-overlap, of
resentation is capable of preventing illegal offspring, inall pairs of the membership functions.
that the shape and order have been considered and stipulated in the structure type.
Definition 7 (Coverage Factor) The coverage facThe survival selection implements the principle “surtor of a chromosome x is defined byvival of the fittest” to pick the chromosomes and formmax (I)
the population for the next generation. In the wellCoverage (x) =.
(16)
range (R1 , . . . , Rl )known (µ + λ) survival selection, parents and offspring
all compete for survival.
The coverage factor is in inverse proportion to the range
Definition 6 (Overlap Factor) The overlap factor
of a chromosome x is defined by
X
Overlap (x) =(max (ovlratio (Ri , Rj ) , 1) − 1) (14)covered by all membership functions. The factor has aminimum (best) value of 1, indicating full coverage ofthe item’s quantity.
The suitability is defined as the sum of the overlap
and coverage factors. Accordingly, the fitness value of achromosome x is computed by
P
R∈L1 FuzzySupport (R)f (x) =.
(17)
Overlap (x) + Coverage (x)3.4 Local Search

The fitness function considers large 1-itemset L1 obtained from the membership functions converted fromx. The use of L1 instead of the largest itemset reduces
the computational cost at the calculation of fuzzy support. In addition, the suitability prevents the MA frompursuing the membership functions with high fuzzy support but serious overlap or narrow coverage.

This study proposes a local search operator to improve
the search capability of the MA. The local search acts
upon the structure types in that the chromosome representation facilitates exploring the structures of membership functions. As Algorithm 3 shows, the local search
operator scans the neighborhood of a given chromosome
for a better solution, where the neighbors are defined as
the chromosomes having the same parameters but different structure types. For example, there are 92 neighbors for a chromosome using three triangular membership functions. Compared to the neighborhood definedin the parameter domain, the neighborhood based on

3.3 Genetic Operators

Algorithm 3 Local Search

The proposed MA is based on the scheme of GA, inwhich the genetic operators include parent selection,
crossover, mutation, and survival selection. The parent
selection operator selects two chromosomes out of the
population to serve as the parents for subsequent reproduction. The probability for a chromosome to be
selected is ordinarily in proportion to its fitness. For

1: procedure LocalSearch(x, h). chromosome x, size h
2:
for i ← 1 to h do3:y i ← (x1 , . . . , x3` , rand(|ST |)). randomize type4:
end for5:y ∗ ← BestOf(y i∈{1,...,h} )6:
if f (y ∗ ) > f (x) then7:x ← y∗
8:
end if
9: end procedureMining Fuzzy Association Rules Using a Memetic Algorithm Based on Structure Representation

structures has a small size and can enhance the efficiency of local search.
Two strategies are developed for choosing the target chromosomes of local search: best and random. The
former chooses the best k chromosomes, whereas thelatter randomly picks k chromosomes from the population. Additionally, we limit the local search to check hneighbors to control the number of extra fitness evaluations. Hence, the local search requires kh additional
fitness evaluations at each generation.

7

Table 1: Parameter setting
Parameter

Value

Representation

Parameter (real number) +Structure (integer)
2-tournament
Uniform
pc = 0.8
Creep (ε = 3)pm = 0.01µ+λParent selection
Crossover
Crossover rate
Mutation
Mutation rate
Survival selection
Population size
#Evaluations

50
25000

4 Experimental Results
This study carries out a series of experiments to examine the performance of the proposed MA on the optimization of membership functions for mining fuzzy
association rules. In addition, we investigate the influences of the proposed chromosome representation andthe local search operator upon the fitness as well as its
components, to wit, overlap, coverage, and fuzzy support. The experiments include five algorithms: GA [15],GA93 (GA using the novel representation), GA12 (GA93refined by the suitability constraints), MA93 and MA12
(GA93 and GA12 applying the local search operator, respectively). The subscripts 93 and 12 account for thenumbers of structure types encoded in the chromosome
representation. Table 1 summarizes the parameter setting for the five test algorithms. The minimum support
is set to 0.04. Different data sizes are tested in the experiments, including 10, 30, 50, 70, and 90k transactions, each consisting of 64 items [15]. Moreover, we examine the performance of test algorithms on a datasetwith one million transactions (1000k) to simulate big
data. Each experiment includes 30 independent runs ofeach algorithm.

4.1 Local Search Strategy and SizeFirst, we investigate the effects of the best and random strategies on the MA. Figure 4 plots the progressof the mean best fitness (MBF) for MA93 and MA12using the best and random strategies performed on different number of chromosomes at each generation. Dueto space limitation, only the experimental results on
the 90k transactions are presented. The figures showthat MA93 benefits from the increase of individuals
for both the best and random strategies. In particular, MA93 using either the best or random strategy
on the whole population, i.e., 50 chromosomes, outperforms that with other sizes in terms of fitness. On theother hand, the enhancement on MA12 depends upon
the strategy adopted for the local search: The increaseof individuals leads to better fitness for the best strategy, but worse for the random strategy. Furthermore,
we look into the influences over the overlap, coverage,
suitability, and fuzzy support of MA93 and MA12 . According to Table 2, MA12 gains better overlap, coverage, and therefore better suitability than MA93 does.
Nonetheless, the constraints on the structure types ofMA12 hinder its pursuit of fuzzy support and result in
the fitness inferior to MA93 .
Second, we compare the performance of MA using
different local search sizes. The results in Fig. 5 showthat MA93 and MA12 with h = 1 perform best andtheir solution quality and convergence speed deteriorate
as the local search size increases. Table 3 lists the overlap, coverage, suitability, fuzzy support, and fitness values of the membership functions obtained from MA93
and MA12 with different sizes of h. The performancetrends with respect to h are similar among the twodatasets and two MAs: The increase in size h worsens
the overlap, coverage, suitability, fuzzy support, and fitness, suggesting the advantage of using h = 1, i.e., local
search checking only one neighbor.
In view of the generally good performance, the following experiments use the strategy of local search on
all chromosomes (k = 50) with only one neighbor (h =1) for MA93 and MA12 .

4.2 Performance Comparison
This study examines the performances of MA93 andMA12 in comparison to GA, GA93 , and GA12 . First,
we investigate the performances on the medium sizeof datasets (10–90k transactions). As Figure 6 shows,
GA using the structure-based representation, i.e., GA93
and GA12 , achieves higher fitness than the original GA
does, which verifies the advantages of using structure
types in the representation. The results further indicate the effectiveness of the proposed local search operator on improving the solution quality: MA93 andChuan-Kang Ting et al.
9.4

9.4

9.3

9.3

9.2

9.2

9.1

9.1
Fitness

Fitness

8

9.0
8.9

9.0
8.9

8.8

MA93 random 1
MA93 random 2
MA93 random 5
MA93 random 10
MA93 random 50

8.7
8.6
0

5000

10000
15000
#Evaluations

20000

8.8

MA93 best 1
MA93 best 2
MA93 best 5
MA93 best 10
MA93 best 50

8.7
8.6
25000

0

5000

(a) MA93 -random

10000
15000
#Evaluations

20000

25000

(b) MA93 -best
9.2

9.2
9.1
9.1
9.0
Fitness

Fitness

9.0
8.9

8.9
8.8

8.8
MA12 random 1
MA12 random 2
MA12 random 5
MA12 random 10
MA12 random 50

8.7
8.6
0

5000

10000
15000
#Evaluations

20000

MA12 best 1
MA12 best 2
MA12 best 5
MA12 best 10
MA12 best 50

8.7
8.6
25000

0

5000

(c) MA12 -random

10000
15000
#Evaluations

20000

25000

(d) MA12 -best

Fig. 4: Progress of MBF for MA93 and MA12 using local search on different numbers of random (left) and best(right) chromosomes on the dataset of 90k transactions
Table 2: Fitness, overlap, coverage, suitability, and fuzzy support of the membership functions obtained from
MA93 and MA12 using local search on different numbers of random and best chromosomes on the dataset of 90k
transactions.
MA

Strategy#Chroms

Overlap

Coverage

Suitability

Fuzzy Support

Fitness

MA93

Random

1
2
5
10
50

0.00860.00850.01030.00590.0032

1.00201.0022
1.00241.00281.00381.01061.01071.01271.0087
1.00709.29339.30429.35199.35059.38029.20099.21149.24159.2741
9.3176

Best

1
2
5
10
50

0.01350.01400.00980.01000.00321.00161.00171.00181.00211.00381.0152
1.01561.01161.01211.00709.13969.17289.20069.25519.38029.00989.0362
9.09949.14959.3176

Random

1
2
5
10
50

0.00000.00000.00000.00000.00001.00161.00161.00181.00191.00261.00161.00161.00181.00191.0026

9.1882
9.18879.18579.15749.15469.17319.17379.16939.14029.1306

Best

1
2
5
10
50

0.00000.00000.00000.00000.00001.00161.00161.00171.00191.00261.00161.00161.00171.00191.00269.03739.05019.07059.08569.15469.02319.03539.05509.06849.1306

MA12

Mining Fuzzy Association Rules Using a Memetic Algorithm Based on Structure Representation
9.0

8.8

8.8

8.6
8.4

8.4

Fitness

Fitness

8.6

9

8.2

8.2
8.0

8.0
7.8

7.8
MA93 h=1
MA93 h=5MA93 h=10

7.6
0

5000

10000
15000
#Evaluations

20000

MA12 h=1MA12 h=5MA12 h=10

7.6
25000

0

5000

(a) MA93 (10k)

20000

25000

(b) MA12 (10k)

9.4

9.2

9.2

9.0

9.0

8.8

8.8

8.6

8.6

Fitness

Fitness

10000
15000
#Evaluations

8.4
8.2

8.4
8.2
8.0

8.0
7.8

7.8

MA93 h=1
MA93 h=5MA93 h=10

7.6
0

5000

10000
15000
#Evaluations

20000

MA12 h=1MA12 h=5MA12 h=10

7.6
25000

0

5000

(c) MA93 (90k)

10000
15000
#Evaluations

20000

25000

(d) MA12 (90k)

Fig. 5: Progress of MBF for MA93 and MA12 using local search with different size h on the datasets of 10k and
90k transactions
Table 3: Fitness, overlap, coverage, suitability, and fuzzy support of the membership functions obtained from MA93
and MA12 using local search with different size h on the datasets of 10k and 90k transactions
Data

MA

Size

Overlap

Coverage

Suitability

Fuzzy Support

Fitness

10k

MA93

1
5
10

0.00500.00660.0082

1.00391.01101.01671.00891.01761.02499.05018.93498.81998.97388.78528.6107

MA12

1
5
10

0.00000.00000.00001.0027
1.00751.01201.0027
1.00751.01218.77098.65888.62358.74738.59438.5214

MA93

1
5
10

0.00320.00600.00531.00381.01111.0167

1.00701.01701.02199.38029.30089.1951

9.3176
9.14939.0013

MA12

1
5
10

0.00000.00000.00011.0026
1.00781.01181.0026
1.00781.01199.15469.06499.03819.13068.99518.932690k

10Chuan-Kang Ting et al.
9.4
9.2

8.8

9.0

8.6

8.8

8.4

8.6

Fitness

Fitness

9.0

8.2

8.4
8.2

8.0
8.0

GA
GA93
GA12
MA93
MA12

7.8
7.6
0

5000

10000
15000
#Evaluations

20000

GA
GA93
GA12
MA93
MA12

7.8
7.6
25000

0

(a) 10k transactions

5000

10000
15000
#Evaluations

20000

25000

(b) 30k transactions
9.4

9.5

9.2
9.0
8.8
Fitness

Fitness

9.0

8.5

8.6
8.4
8.2
8.0

GA
GA93
GA12
MA93
MA12

8.0

7.5
0

5000

10000
15000
#Evaluations

20000

GA
GA93
GA12
MA93
MA12

7.8
7.6
25000

(c) 50k transactions

0

5000

10000
15000
#Evaluations

20000

25000

(d) 90k transactions

Fig. 6: Progress of MBF against the number of fitness evaluations for GA, GA93 , GA12 , MA93 , and MA12 on
different datasets
MA12 gain higher fitness than GA93 and GA12 , respectively. When comparing the two MAs, MA93 outperforms MA12 in terms of fitness. As aforementioned, thetwo constraints on MA12 help to guarantee the suitability but impairs the fuzzy support; consequently, MA12
gains lower fitness than MA93 does. Table 4 presents
the MBF obtained and the p-values of one-tailed t-teston the MBF. With confidence level α = 0.01, the t-test
results indicate that MA93 and MA12 achieve significantly better fitness than GA93 and GA12 , respectively.
In addition, MA93 significantly outperforms MA12 on
all datasets. The superior outcomes validate the benefits of the structure representation and local search.
Table 5 compares the overlap, coverage, suitability, and fuzzy support of the membership functions obtained from the five test algorithms. The results indicate that GA12 and MA12 benefit from the two constraints in coverage and overlap; nevertheless; their fuzzy
support values are relatively low due to the limitation on the structure types. By contrast, GA attains
the highest fuzzy support at the cost of suitability; especially, it suffers from excessive overlap of member-ship functions. Compared to the above methods, MA93
maintains a balance between fuzzy support and suitability: By virtue of the structure representation andlocal search, MA93 achieves the best fitness with suitability better than GA and fuzzy support higher than
GA12 and MA12 .
This study further investigates the performance ofthe proposed MA on a large dataset, consisting of 1000ktransactions, to simulate mining fuzzy association ruleson big data. The experimental results on Table 6 showthat the proposed MA93 and MA12 achieve a satisfactory performance on optimizing the membership functions for large datasets. With confidence level α = 0.01,
the t-test results indicate that both MA93 and MA12
obtain significantly higher fitness than GA, GA93 , andGA12 . Although MA93 and MA12 have a slightly worse
coverage, they gain better overlap and fuzzy support
than GA93 and GA12 , respectively. Figure 7 plots theanytime behaviors of the five test algorithms in fitness,overlap, coverage, and fuzzy support. The figure shows
the advantage of local search: The two MAs progressbeyond the GAs in overlap, fuzzy support, and fitness.

Mining Fuzzy Association Rules Using a Memetic Algorithm Based on Structure Representation

11

Table 4: MBF and p-values for the five test algorithms on the datasets of different sizes. 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 five algorithms; boldfaced
p-values denote the statistical significance with confidence level α = 0.01
p-value

MBF
#Tr.

GA

GA93

GA12

MA93

MA12

GA93 :MA93

GA12 :MA12

MA12 :MA93

10k
30k
50k
70k
90k

8.60108.58458.58658.59708.58428.48158.92299.18038.83058.90578.64679.03989.2911
8.95509.02408.97389.31209.65999.23049.3176

8.74739.14919.4012
9.05799.1306

2.60E-45
2.45E-41
2.46E-42
6.87E-46
3.45E-45

1.25E-21
1.75E-25
5.96E-21
1.38E-21
4.34E-24

1.19E-37
8.50E-30
7.74E-41
2.62E-29
2.64E-34

Table 5: Overlap, coverage, suitability, and fuzzy support of the membership functions obtained from the five test
algorithms on the data of different sizes. Boldface marks the best result among the five algorithms#Tr.

Algorithm

Overlap

Coverage

Suitability

Fuzzy Support

Fitness

10k

GA
GA93
GA12
MA93
MA12

0.19280.04700.00100.00500.00001.00191.00161.00141.00391.0027

1.1946
1.04851.00241.00891.0027

10.18218.86568.66739.05018.77098.60108.48158.64678.97388.7473

30k

GA
GA93
GA12
MA93
MA12

0.1886
0.03310.00070.00460.00001.00181.00161.00141.00401.00261.19041.03461.00211.00861.0026

10.1259
9.2157
9.05969.3887
9.17268.58458.92299.03989.31209.1491

50k

GA
GA93
GA12
MA93
MA12

0.20120.03370.00100.00380.00001.00191.00151.00141.00411.00281.20301.0352
1.0024
1.00791.002810.22899.48149.31349.73299.42718.58659.18039.29119.65999.4012

70k

GA
GA93
GA12
MA93
MA12

0.19920.03620.00090.00370.00001.00191.00151.00141.00391.00281.20111.03771.0023
1.00761.002810.2227
9.14798.97549.29839.08298.59708.83058.95509.23049.0579

90k

GA
GA93
GA12
MA93
MA12

0.20190.03780.00100.00320.00001.00191.00161.00141.00381.00261.20381.03931.0024
1.00701.0026

10.23869.23229.04579.3802
9.15468.58428.90579.02409.31769.1306

Table 6: Fitness, overlap, coverage, suitability, and fuzzy support of the membership functions obtained from thefive test algorithms on the dataset of 1000k transactions. Boldface marks the best result among the five algorithms#Tr.

Algorithm

Overlap

Coverage

Suitability

Fuzzy Support

Fitness

1000k

GA
GA93
GA12
MA93
MA12

0.23870.05230.00060.00740.00001.00201.00161.00141.00391.00271.24071.05391.00201.01141.0027

10.3389.14108.84319.28278.96488.39198.69918.8251
9.18318.9403

12

Chuan-Kang Ting et al.
9.5

0.35

GA
GA93
GA12
MA93
MA12

0.30
0.25
Overlap

Fitness

9.0

8.5

8.0

0

5000

10000
15000
#Evaluations

20000

0.15
0.10

GA
GA93
GA12
MA93
MA12

7.5

0.20

0.05
0.00
25000

0

5000

(a) Fitness
1.030

10.0
Fuzzy Support

Coverage

1.015
1.010

9.5

9.0
GA
GA93
GA12
MA93
MA12

8.5

1.005
1.000

8.0
5000

10000
15000
#Evaluations

25000

10.5

1.020

0

20000

(b) Overlap

GA
GA93
GA12
MA93
MA12

1.025

10000
15000
#Evaluations

20000

25000

(c) Coverage

0

5000

10000
15000
#Evaluations

20000

25000

(d) Fuzzy support

Fig. 7: Variation of fitness, overlap, coverage, and fuzzy support against the number of evaluations for the five test
algorithms on 1000k transactions
They also address the issue that GA tends to sacrifice
overlap for fuzzy support. These outcomes confirm the
proposed MA is capable of improving GA in fuzzy data
mining on large datasets. They also validate the benefits of the chromosome representation and the local
search operator for the MA.

4.3 Comparison of Membership Functions
The shape of membership functions is key to the interpretability of fuzzy sets and exerts significant influence
on coverage, overlap, and fuzzy support. This section
compares the membership functions obtained from GA,
MA93 and MA12 on the data of 10k, 90k, and 1000ktransactions. According to Fig. 8, GA achieves membership functions with highest fuzzy support but lowest suitability. In particular, the membership functions
generated by GA have serious overlap, making the fuzzy
regions turn out to be trivial. That is, GA tends to sacrifice suitability for fuzzy support. On the other hand,
the results show that MA93 and MA12 can maintainproper overlap and coverage while pursuing fuzzy support. Hence, the membership functions obtained from
MA93 and MA12 have higher fitness values and reasonable shapes than that from GA. In addition, MA12
imposes constraints (12) and (13) to secure suitable coverage and overlap; nevertheless, these constraints also
hinder MA12 attaining high fuzzy support because thelimited fuzzy regions bring about lower fuzzy support,
which is reflected in the resultant membership functionsin Fig. 8.
5 Conclusions
This study proposes an MA to optimize the membership functions for fuzzy association rule mining. The
MA uses a chromosome representation consisting of theparameters and structure type of membership functions.
The consideration of structure in the representation
gains three advantages. First, the structure type helps
to filter out the illegal membership functions, thereby
reducing the search space. Second, it facilitates the design of heuristics and constraints for appropriate cover-Mining Fuzzy Association Rules Using a Memetic Algorithm Based on Structure Representation
1

1

0

1

0
0

2

4

6

8

10

12

0
0

(a) GA (10k transactions)

2

4

6

8

10

12

0
4

6

8

10

12

2

4

6

8

10

12

4

6

8

10

(g) MA12 (10k transactions)

12

10

12

2

4

6

8

10

12

1

0
2

8

(f) MA93 (1000k transactions)

1

0

0

(e) MA93 (90k transactions)

0

6

0
0

(d) MA93 (10k transactions)
1

4

1

0
2

2

(c) GA (1000k transactions)

1

0

0

(b) GA (90k transactions)

1

13

0
0

2

4

6

8

10

(h) MA12 (90k transactions)

12

0

2

4

6

8

10

12

(i) MA12 (1000k transactions)Fig. 8: Comparison of membership functions obtained from GA, MA93 and MA12 on the datasets of 10k (left),
90k (center), and 1000k (right) transactions
age and overlap. Third, local search can be performedon the structure types; accordingly; we develop a local
search operator to improve the search efficiency of theMA.
This study conducts a series of experiments to examine the performance of the proposed MA. Two instances of the MA, namely MA93 and MA12 , are investigated to consider different constraints on the structures.
The experimental results show that the MAs achievesignificantly higher fitness than GA and GA using thestructure representation. In exploring the influences on
the membership functions, the results show that theMA can attain a high fuzzy support and maintain suitability, i.e., appropriate overlap and coverage. The improvement of the proposed MAs upon the GAs becomeseven greater as the dataset grows to one million transactions. These outcomes indicate the advantages of thechromosome representation and local search operator
for the MA. In addition, they validate the effectivenessof the proposed MAs on the optimization of membership functions for fuzzy association rule mining.

Future work includes some directions: Advanced design of heuristics and constraints based on structure
types can be considered for enhancing the MA. Additionally, applying the proposed MA to optimize themembership functions for other fuzzy systems is promising. Extending the performance comparison with more
evolutionary algorithms would also help to validate theadvantages of the proposed MA.

Acknowledgment
The authors would like to thank the editor and reviewers for their valuable comments and suggestions.
This work was supported by the Ministry of Scienceand Technology of Taiwan, under contract MOST 1042221-E-194-015-MY3.

14

Compliance with Ethical Standards
Conflict of interest: The authors declare that they
have no conflict of interest.
Ethical approval: This article does not contain any
studies with human participants or animals performedby any of the authors.

References
1. R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In Procddings of the International Conference
on Very Large Data Bases, pages 487–499, 1994.
2. J. Alcalá-Fdez, R. Alcalá, and F. Herrera. A fuzzy association rule-based classification model for high-dimensional
problems with genetic rule selection and lateral tuning. IEEE
Transactions on Fuzzy Systems, 19(5):857–872, 2011.
3. M. Antonelli, P. Ducange, and F. Marcelloni. A fast and efficient multi-objective evolutionary learning scheme for fuzzy
rule-based classifiers. Information Sciences, 283(1):36–54,
2014.
4. K. Balázs and L. T. Kóczy. Genetic and bacterial memetic
programming approaches in hierarchical-interpolative fuzzy
system construction. In Proceedings of IEEE International
Conference on Fuzzy Systems, pages 1–8, 2012.
5. G.-R. Cai, S.-Z. Li, and S.-L. Chen. Mining fuzzy association rules by using nonlinear particle swarm optimization.
Quantitative Logic and Soft Computing, 82:621–630, 2010.
6. K. Chan and W. H. Au. Mining fuzzy association rules. In
Proceedings of the International Conference on Information
and Knowledge Management, pages 209–215, 1997.
7. C.-H. Chen, A.-F. Li, and Y.-C. Lee. A fuzzy coherent rulemining algorithm. Applied Soft Computing, 13(7):3422–3428,
2013.
8. C.-H. Chen, V.-S. Tseng, and T.-P. Hong. Cluster-based evaluation in fuzzy-genetic data mining. IEEE Transactions on
Fuzzy Systems, 16(1):249–262, 2008.
9. M.-S. Chen, J. Han, and P. S. Yu. Data mining: An overview
from a database perspective. IEEE Transactions on Knowledge and data Engineering, 8(6):866–883, 1996.
10. U. M. Fayyad, G. Piatetsky-Shapiro, and P. Smyth. Fromdata mining to knowledge discovery in databases. AI Magazine, 17:37–54, 1996.
11. M. Fazzolari, R. Alcala, Y. Nojima, H. Ishibuchi, and F. Herrera. A review of the application of multiobjective evolutionary fuzzy systems: Current status and further directions.
IEEE Transactions on Fuzzy Systems, 21(1):45–65, 2013.
12. L. Feng, Y. S. Ong, A. H. Tan, and I. W. Tsang. Memes asbuilding blocks: a case study on evolutionary optimization +transfer learning for routing problems. Memetic Computing,7(3):159–180, 2015.
13. L. Gál, J. Botzheim, L. T. Kóczy, and A. E. Ruano. Fuzzy
rule base extraction by the improved bacterial memetic algorithm. In Proceedings of International Symposium on Applied Machine Intelligence and Informatics, pages 49–53,
2008.
14. D.-T. Ho and J. M. Garibaldi. An improved optimisation
framework for fuzzy time-series prediction. In Proceedingsof IEEE International Conference on Fuzzy Systems, pages
1–8, 2013.
15. T.-P. Hong, C.-H. Chen, Y.-C. Lee, and Y.-L. Wu. Geneticfuzzy data mining with divide-and-conquer strategy. IEEE
Transaction on Evolutionary Computation, 12(2):252–265,
2008.

Chuan-Kang Ting et al.
16. T.-P. Hong, C.-S. Kuo, and S.-C. Chi. Mining association rules from quantitative data. Intelligent Data Analysis,3(5):363–376, 1999.
17. T.-P. Hong and C.-Y. Lee. Induction of fuzzy rules and membership functions from training examples. Fuzzy Sets andSystems, 84(1):33–47, 1996.
18. X.-P. Ji, X.-B. Cao, and K. Tang. Sequence searching andevaluation: A unified approach for aircraft arrival sequencing
and scheduling problems. Memetic Computing, 8(2):109–123,
2016.
19. C. M. Kuok, A. Fu, and M. H. Wong. Mining fuzzy association rules in databases. ACM SIGMOD Record, 27(1):41–46,
1998.
20. C. K.-H. Lee, K.-L. Choy, G. T.-S. Ho, and C. H.-Y. Lam. A
slippery genetic algorithm-based process mining system forachieving better quality assurance in the garment industry.
Expert Systems with Applications, 46:236–248, 2016.
21. M. A. El Majdouli, I. Rbouh, S. Bougrine, B. El Benani, and
A. A. El Imrani. Fireworks algorithm framework for big data
optimization. Memetic Computing, pages 1–15, 2016.
22. D. Meng and Z. Pei. Extracting linguistic rules from data setsusing fuzzy logic and genetic algorithms. Neurocomputing,78(1):45–54, 2012.
23. B. Minaei-Bidgoli, R. Barmaki, and M. Nasiri. Mining numerical association rules via multi-objective genetic algorithms. Information Sciences, 233(1):15–24, 2013.
24. S. Mishra, D. Mishra, and S. K. Satapathy. Particle swarm
optimization based fuzzy frequent pattern mining from gene
expression data. In Proceedings of the International Conference on Computer & Communication Technology, pages
15–20, 2011.
25. M. Nekkaa and D. Boughaci. A memetic algorithm with support vector machine for feature selection and classification.
Memetic Computing, 7(1):59–73, 2015.
26. Y. S. Ong, M. H. Lim, and X. S. Chen. Research frontier:
Memetic computation — past, present & future. IEEE Computational Intelligence Magazine, 5(2):24–36, 2010.
27. J. Prakash and P. K. Singh. An effective multiobjective approach for hard partitional clustering. Memetic Computing,7(2):93–104, 2015.
28. H. R. Qodmanan, M. Nasiri, and B. Minaei-Bidgoli. Multi
objective association rule mining with genetic algorithm
without specifying minimum support and minimum confidence. Expert Systems with Applications, 38(1):288–298,
2011.
29. F. Rudziǹski. A multi-objective genetic optimization ofinterpretability-oriented fuzzy rule-based classifiers. Applied
Soft Computing, 38:118–133, 2016.
30. H. Samma, C. P. Lim, J. M. Saleh, and S. A. Suandi. A
memetic-based fuzzy support vector machine model and its
application to license plate recognition. Memetic Computing,8(3):235–251, 2016.
31. R. Srikant and R. Agrawal. Mining quantitative association rules in large relational tables. ACM SIGMOD Record,25(2):1–12, 1996.
32. A. Tsakonas. Local and global optimization for takagi-sugeno
fuzzy system by memetic genetic programming. Expert Systems with Applications, 40(8):3282–3298, 2013.
33. Y. Zhang, J. Liu, M. X. Zhou, and Z. Z. Jiang. A multiobjective memetic algorithm based on decomposition for big
optimization problems. Memetic Computing, 8(1):45–61,
2016.