Research
Frontier

Chuan-Kang Ting, Wei-Ming Zeng, andTzu-Chieh Lin, National Chung Cheng
University, TAIWAN

Linkage Discovery Through Data MiningG

1. Introduction

enetic algor ithms (GAs) areextensively adopted in various
aspects of data mining, e.g., association rules, clustering, and classification [1, 2, 3]. Instead of applying GAs
for data mining, this study addresses
linkage discovery, an essential topic inGAs, by using data mining methods.
Inspired by natural evolution, GAs utilize selection, crossover, and mutation
operations to evolve candidate solutions
into global optima [4]. This evolutionary scheme can effectively resolve many
search and optimization problems. As
the most salient feature of GAs, crossover enables the recombination of goodparts of two selected chromosomes, yet,in doing so, may disrupt the collected
promising segments.
Linkage discovery (or linkage identification) attempts to identify the tightly
linked genes and bind them together toform building blocks, which can beused to avoid the disruptiveness induced
by crossover operation [4, 5]. Identifying
linkage is based on methods classified as
estimation of distribution algorithms(EDAs), perturbation-based methods(PMs), and mixed methods. Rather thanmanipulating linked genes deterministically, EDAs attempt to derive probability
models from selected chromosomes.
Related methods include Bayesian optimization algorithm (BOA) [6], factorized distribution algorithm (FDA) [7],and extended compact genetic algorithm (ECGA) [8]. While considering

Digital Object Identifier 10.1109/MCI.2009.935310

10

linkage in a statistical manner, EDAs
generally tend to neglect buildingblocks with a relatively low fitness contribution. Alternatively, PMs perturb
certain genes of each chromosome in
the population and,then, identify thelinkage relationshipby using the influenceof perturbation. Related methods include
linkage identification
by nonlinearity check(LINC) [9, 10], linkage identification by
non-monotonicitydetection (LIMD) [11], linkage identification based on epistasis measures(LIEM) [12], and their var iants.
Although capable of detecting the linkage with low-contribution building
blocks, PMs require additional fitness
evaluations in perturbation. As anotheralternative, a representative of mixed
methods is the dependency detection
for distribution derived from fitness differences (D5) [13]. This method extracts
information from subsequently perturbing genes to estimate the linkage relationship. Tsuji and Munetomo [14]indicated that D5 possesses the advantages of EDAs in terms of efficiency andof PMs in terms of detecting low-contribution building blocks. A moredetailed survey of linkage discovery
methods can be found in [14, 15].
Rather than deriving the linkage
relationship, this study proposes mining the interactions between genes forlinkage. Figure 1 illustrates the meta-IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | FEBRUARY 2010

phor that connects linkage discovery
to data mining. Learning association
rules involves finding the implicitly
associated items from transactions,which is analogous to discover ing
t h e l i n ke d g e n e sfrom chromosomesor re lated information. There fore, byregarding each linkage between genes as
an association rule,
this study adopts data
mining to learn theserules. The rest of this© PHOTODISC
paper is organized asfollows. Section 2 introduces the proposed linkage mining approach. Section 3 summarizes the experimentalresults. Conclusions are finally drawn
in Section 4, along with recommendations for future research.
2. Linkage Mining

As an implementation of data mining
for linkage discovery, this study adopts
the well-known Apriori algorithm tomine the data generated by D5 for association rules. The set of items in anassociation rule corresponds to the setof loci in a building block. The disruptiveness caused by crossover can beresolved using information on building
blocks. The major components for mining linkage are described below.
2.1 D5 Algorithm

The D5 algorithm [13] integrates theadvantages of PMs and EDAs. For eachlocus, D5 takes three steps:

1556-603X/10/$26.00©2010IEEE

1) Perturb genes at that locus forfitness difference.
2) Cluster the population according to fitness difference.
3) Estimate the linkage from eachcluster.
In the first step, D5 perturbs (i.e.
0 S 1 or 1 S 0) all genes at
locus i in the population and calculates the resulting difference infitness, that is,

this study applies the Apriorialgor ithm, a well-establishedmethod for mining association
rules, to mine the estimatedInformation
Data
dependency sets generated by D5
for building blocks in GAs.
Some related terms in data
mining are defined before
introducing the Apriori algoInvestigation
Miningrithm. The support of an itemset
X represents the number oftransactions in which the memDfi 1 c 2 5 f 1 cr 2 2 f 1 c 2 ,bers of X all exist. Additionally,
Ck denotes the collection ofwhere f 1 c 2 and f 1 cr 2 denotecandidate itemsets of size k,Building
the fitness values before and afterand Lk represents the collection
AssociationBlocks
Rulesof large itemsets of size k,perturbing the gene at locus i,
R1 … … …
R2 … … …
which have a support exceedrespectively.
R3 … … …
ing the predefined minimum
Based on fitness difference, D5partitions the population into
support minsup.
several sub-populations Ci1,
The Apriori algorithm was
Ci2, c, CiNi. For a sub-populaproposed by Agrawal et al. [17,tion Cij larger than a predefined FIGURE 1 Metaphor connecting linkage discovery to data18]. Starting with k 5 1, Apriorisize, D5 constructs the largest set mining.
incrementally generates candidateof loci, denoted by Vij, that conitemsets Ck and finds out large
tains locus i and holds the minimum
itemsets Lk from Ck, until Lk is empty.
transaction. With respect to the metaThis algorithm can effectively reduce
entropy for the genes at these loci. The
phor in Fig. 1, the elements (loci) of an
the computational effort in checking
set Vij serves as an estimated dependency
estimated dependency set are regarded
set for further deriving linkage sets, i.e.
various combinations of itemsets foras the items of a transaction. Moreover,building blocks. The derivation of linklarge itemsets.
association rules refer to the strong
age sets in D5 depends on the following
Figure 2 illustrates use of the Aprioconnections of certain items, which isproblem types: For non-overlapping
ri algorithm to mine for linkage. The
analogous to the linkage relationship offunctions, linkage set Vi for locus i is thedatabase consists of four transactions,particular genes. Based on this analogy,estimated dependency set Vij* with thesmallest entropy, i.e. j* 5 argminj E 1 Vij 2 ,where E 1 2 refers to the entropy. As for
C1 Itemset
Database
L1Itemset
SupportSupportoverlapping functions, the enhanced D5Tran. ID Items
{1}
2{1}
2
[16] investigates the mutual dependency
1{1, 3, 4, 5}
{2}
2{2}
2Sup
≥
2
Scan
relationship among the unions of esti{3}2{2, 4, 5}
2{3}
2|{4}
4{4}
4
mated dependency sets V i 5 d jVij for
3{4, 5}{5}4{5}44{1, 3, 4}
all locus i to determine the linkage sets.
5{2, 5}This study examines the feasibility
C2 Itemset
L2Itemset
SupportSupport
minsup = 0.4
of using the Apriori algorithm to mine
{1, 2}
0{1, 3}2
the estimated dependency sets for{1, 3}
2{1, 4}2
Sup ≥ 2
Scan{1, 4}
2{2, 5}2
building blocks. This mining approach{1, 5}
1{3, 4}2
can identify building blocks precisely{2, 3}
0{4, 5}3and improve the performance of GAs{2, 4}
1{2, 5}2on both the non-overlapping and over{3, 4}
2lapping functions.
2.2 Apriori Algorithm

Association rules are commonly expressed in the form of X S Y, representing
whenever itemset (i.e. set of items) X isin a transaction, itemset Y is also in theC3
Scan{3, 5}{4, 5}

13Itemset{1, 3, 4}Support
2L3Sup ≥ 2Itemset{1,3, 4}

Support2

FIGURE 2 Generation of candidate itemsets and large itemsets.

FEBRUARY 2010 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE

11Instead of applying GAs for data mining, this studyaddresses linkage discovery, an essential topic in GAs,
by using data mining methods.
where the first transaction represents anestimated dependency set, including
loci 5 1, 3, 4, 5 6 . Apriori first scans forcandidate itemsets C1 and then determines large itemsets L1 from them. In
the example, given (number of transactions) 3 minsup 5 2, only the itemsets
in C1 that appear at least twice among
all transactions in the database areplaced into L1. The candidate itemsets

C2 are formed by joining and pruning
the itemsets in L1. Apriori continues
with this procedure to generate C2,L2, C3, and L3. We posit that each large
itemset is a building block, except forthe subsets of higher-order itemsets.
Hence, the large itemsets 5 2, 5 6 ,5 4, 5 6 , and 5 1, 3, 4 6 are obtained asbuilding blocks.
3. ExperimentalResults

TABLE 1 Success rate (SR) and the number of evaluations(NES) to achieve the optimal solutions for D5 and theproposed mining approach on the trap5 function withchromosome length l and population size p. Boldface
signifies a superior SR or a significantly lower NES.
SR (%)

This study conducts
exper iments on thenon-overlapping trap5
function and the function with stochastic
circularly overlapping
sub-functions (SCOS)[16]. Performance ofthe proposed mining
approach based onNESlp

D5MINING

D5MINING

200
400
600
800
1,000

400
400
600
800
1,000

50.0
10.0
60.0
50.0
70.0

100.0
80.0
100.0
100.0
100.0

132,840
235,880
447,240
770,400
1,157,500

108,560
218,360
451,620
742,800
1,140,000

TABLE 2 Success rate (SR) and the number of evaluations (NES) to achieve theoptimal solutions for D5 and the proposed mining approach on the SCOS function
with variance s2, chromosome length l, and population size p. Boldface signifies asuperior SR or a significantly lower NES.
NESSR (%)

slp

D5MINING

D5MINING

2

60

500
1,000
500
1,000
500
1,000

100.0
100.0
76.7
100.0
63.3
100.0

100.0
100.0
93.3
100.0
83.3
100.0

51,61784,00093,483
122,400
126,017
161,700

46,867
83,40081,950122,200
112,333
161,833

500
1,000
500
1,000
500
1,000

13.3
100.0
0.0
70.0
0.0
46.7

90.0
100.0
60.0
96.7
23.3
93.3

125,317
108,600
145,500
204,133
160,500
276,800

68,25088,233113167145,267
148,650
183,967

1,000
2,000
1,000
2,000
2,000
3,000

46.7
100.0
0.0
86.7
16.7
63.3

96.7
100.0
50.0
90.0
60.0
86.7

216,633
213,467
291,000
386,933
622,267
801,400

122,367
199,000
249,267
360,667
550,800
741,600

1,000
2,000
1,000
2,000
2,000
3,000

46.7
100.0
0.0
70.0
23.3
70.0

100.0
100.0
53.3
83.3
60.0
83.3

211,933
199,133
291,000
428,000
619,133
817,600

104,467
195,533
238,500
374,200
534,867
756,000

21

90120226090120526090120102609012012IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | FEBRUARY 2010

Apriori is compared with that of D5.
The GA uses the context dependent
crossover (CDC) [16] and no mutation for both methods. Notably, thepopulation size is the same for boththe linkage discovery phase and evolution phase. The minimum support isempirically set in the range of 3 0, 0.1 4 .
Each experimental setting includes 30
independent runs of 200 generations
concerning the stochastic nature ofGAs. Performance measures include
success rate (SR) and the number ofevaluations (NES) to achieve the optimal solutions for all 30 runs.
Table 1 compares the performancesof D 5 and the proposed mining
approach on the trap function. The
mining approach yields 100% SR on all
test instances except for l 5 400 andoutperforms D 5 in SR on all testinstances. Additionally, the approachrequires significantly fewer evaluations
to achieve the optima solutions than D5
does, where the statistical significance is
examined by a one-tailed t-test with aconfidence level of 0.05. The preferable
experimental results demonstrate theadvantage of the proposed mining
approach over D5 in terms of solution
quality and efficiency.
Furthermore, Table 2 presents theSR and NES for D5 and the proposedmining approach on the SCOS function. Notably, a large var iance s2
incurs highly complex and overlapping interactions between building
blocks in the SCOS function. Experimental results indicate that the mining approach can achieve better SR
with a lower NES than D5 on most
test instances. Moreover, the mining
approach using a relatively small population is comparable with D5 using a
relatively large population in terms ofSR on several instances. Regarding
algor ithmic efficiency, the mining
approach uses a significantly lower
NES than D5 does. In addition to validating the capability of superior SR,
these outcomes indicate that the mining approach can substantially decrease
the required computational resourcesof D5 with respect to population size
and number of evaluations.

Learning association rules involves finding theimplicitly associated items from transactions, which
is analogous to discovering the linked genes fromchromosomes or related information.
4. Conclusions

Instead of applying GAs to data mining,
this study identifies the linkage relationship in GAs through data mining.
Based on the analogy between building
blocks and association rules, this study
utilizes the Apriori algorithm to minethe estimated dependency sets generated by D5 for the large itemsets as building blocks.
Experimental results of non-overlapping and complex overlapping functions
indicate that the proposed mining
approach can improve D5 in terms ofsolution quality and efficiency. Specifically, the mining approach achieves ahigher success rate with significantly
fewer evaluations to achieve the optimal
solutions than D5 does. With a smaller
population, the mining approach canalso yield a success rate comparable withD 5 using a larger population. These
superior outcomes validate the effectiveness and efficiency of the proposed
approach in linkage discovery.
In addition to enhancing D5, linkage
mining paves the way for a new field ofresearch. We recommend the following
directions for future research. First,
future studies should attempt to obtain
the data to be mined for building blocks
from methods other than D5. Second,
given the availability of a considerable
number of association rules learning
methods, more effective methods should
be adopted for linkage mining applications. Finally, as well as association rules,
other data mining tasks, such as classification and clustering, are highly promising for use in linkage discovery.
Acknowledgments

The authors would like to thank Miwako
Tsuji for the source code of D5 and CDC.
References[1] J. Han and M. Kamber, Data Mining: Concepts andTechniques. San Mateo, CA: Morgan Kaufmann, 2000.
[2] A. A. Freitas, Data Mining and Knowledge Discovery with
Evolutionary Algorithms. Berlin: Springer-Verlag, 2002.
[3] S. Mitra, S. K. Pal, and P. Mitra, “Data mining in soft
computing framework: A survey,” IEEE Trans. NeuralNetw., vol. 13, no. 1, pp. 3–14, 2002.
[4] J. Holland, Adaptation in Natural and Artificial Systems.
Univ. of Michigan Press, 1975.
[5] D. E. Goldberg, The Design of Innovation: Lessons Fromand For Competent Genetic Algorithms. Berlin: SpringerVerlag, 2002.

[6] M. Pelikan, D. E. Goldberg, and E. Cantú-Paz,“BOA: The Bayesian optimization algorithm,” in Proc.
1999 Genetic and Evolutionary Computation Conf., 1999, pp.
525–532.
[7] H. Mühlenbein and T. Mahnig, “FDA – A scalable
evolutionary algorithm for the optimization for the optimization of additively decomposed functions,” Evolution.
Computat., vol. 7, no. 4, pp. 353–376, 1999.
[8] G. R. Harik, “Linkage learning via probabilistic
modeling in the ECGA,” Univ. of Illinois at UrbanaChampaign, Illinois Genetic Algorithms Laboratory, Tech.
Rep., 1999.
[9] M. Munetomo and D. E. Goldberg, “Designing agenetic algorithm using the linkage identification bynonlinearity check,” Univ. of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Tech. Rep.,
1998.
[10] M. Munetomo and D. E. Goldberg, “Identifying
linkage by nonlinearity check,” Univ. of Illinois at UrbanaChampaign, Illinois Genetic Algorithms Laboratory, Tech. Rep.,
1998.
[11] M. Munetomo and D. E. Goldberg, “Linkage identification by non-monotonicity detection for overlapping
functions,” Evolution. Computat., vol. 7, no. 4, pp. 377–398,
1999.
[12] M. Munetomo, “Linkage identification based onepistasis measures to realize efficient genetic algorithms,”
in Proc. 2002 IEEE Congress on Evolutionary Computation,
2002, pp. 1332–1337.
[13] M. Tsuji, M. Munetomo, and K. Akama, “Modelingdependencies of loci with string classification accordingto fitness differences,” in Proc. 2004 Genetic and Evolutionary Computation Conf., 2004, pp. 246–257.
[14] M. Tsuji and M. Munetomo, “Linkage analysis in genetic algorithms,” in Computational Intelligence Paradigms.
Berlin: Springer-Verlag, 2008, pp. 251–279.
[15] Y. P. Chen, T. L. Yu, K. Sastry, and D. E. Goldberg,“A survey of genetic linkage learning techniques,” Univ.
of Illinois at Urbana-Champaign, Illinois Genetic Algorithms
Laboratory, Tech. Rep., 2007.
[16] M. Tsuji, M. Munetomo, and K. Akama, “A crossover for complex building blocks overlapping,” in Proc.
2006 Genetic and Evolutionary Computation Conf., 2006,
pp. 1337–1344.
[17] R. Agrawal, T. Imieliński, and A. Swami, “Miningassociation rules between sets of items in large databases,”in Proc. 1993 ACM SIGMOD Int. Conf. Management ofData, 1993, vol. 22, no. 2, pp. 207–216.
[18] R. Agrawal and R. Srikant, “Fast algorithms formining association rules,” in Proc. 20th Int. Conf. Very
Large Data Bases, 1994, vol. 1215, pp. 487–499.

Society Briefs (continued from page 4)
using the appropriate IEEE spreadsheet
available on the link above (budgetforms are not required for technical cosponsorship proposals). Proposals should
be submitted 18 months in advance ofthe desired conference dates, especiallywith regards to conferences withrequested financial support from IEEE
CIS. Both the IEEE CIS conferences
committee and the IEEE CIS adminis-trative committee must approve all budgets (and budget revisions).
AsVP Conferences, it is my goal to encourage continued growth in our IEEECIS sponsored conferences. This can beaccomplished through new special sessions at standard conference events, or byturning very popular special sessions into
their own symposia. Fostering additional
interaction between the IEEE CIS tech-nical committees and conferences will
help increase quality and attendance. I
also feel that it is very important thatstudents be attracted to these events andlook forward to IEEE CIS continuing
its assistance with student travel grants. If
you have any thoughts or questions about
the conference process please contact me
at gfogel@natural-selection.com.

FEBRUARY 2010 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE

13