TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol.12, No.4, April 201
4, pp. 2941 ~ 2
9
4
9
DOI: http://dx.doi.org/10.11591/telkomni
ka.v12i4.4810
2941
Re
cei
v
ed Se
ptem
ber 6, 2013; Re
vi
sed
No
vem
ber 1
0
,
2013; Accep
t
ed No
vem
b
e
r
23, 2013
A High Efficient Association Rule Mining Algorithm
Based on Intelligent Computation
Wu Feng
xia
ng
North Ch
ina C
a
reer Aca
dem
y of
w
a
te
r R
e
so
urces, Hen
anZ
hen
gzh
ou, Chi
n
a
E-mail: yanc
aif
eng
20
02@
163
.com
A
b
st
r
a
ct
Data
min
i
ng is
to use auto
m
ated d
a
ta an
al
ysis
techni
qu
e
s
to uncover
previ
ously u
n
d
e
tecte
d
relati
onsh
i
ps a
m
o
ng d
a
ta ite
m
s. In data mi
nin
g
, asso
ciati
on rul
e
mi
ni
ng
is a preval
ent
and w
e
ll res
e
a
r
ched
meth
od for d
i
s
c
overi
ng us
eful
relatio
n
s betw
een v
a
ria
b
le
s
i
n
larg
e dat
aba
ses. In this pap
er, w
e
investig
at
e
the pr
inci
ple
o
f
Apriori,
dir
e
c
t
hash
a
nd
pr
uni
ng
an
d a
l
s
o
study
the
d
r
aw
back of th
em. T
h
e first
is
constructin
g
h
a
sh ta
ble w
i
th
out co
nflictio
n
i
s
theoret
ic
al
ly
opti
m
a
l
, but it
nee
ds co
nsu
m
e a l
o
t of
me
mor
y
space
an
d sp
a
c
e util
i
z
a
t
io
n is
low
.
T
he seco
nd is t
hat
it d
o
e
s not
have
ha
sh tree
data str
u
cture l
e
a
d
in
g
to
too lon
g
ins
e
rt and se
arch ti
me. So w
e
pr
opos
e a
new
associ
ation r
u
l
e
mi
ni
ng a
l
gor
ithm
base
d
on
differenti
a
l evol
ution
a
ry
co
mp
utati
on. T
h
e ex
peri
m
e
n
t resu
lts show
that
ou
r prop
osed
al
g
o
rith
m h
a
s bett
e
r
executi
on ti
me
and acc
u
racy, w
h
ich can b
e
u
s
ed in e
l
ectro
n
i
c
commerc
e
system.
Ke
y
w
ords
:
ap
riori, associ
atio
n rule, dir
e
ct hash an
d pr
u
nni
ng, differenti
a
l
evol
ution
a
ry co
mp
utatio
n
Co
p
y
rig
h
t
©
2014 In
stitu
t
e o
f
Ad
van
ced
En
g
i
n
eerin
g and
Scien
ce. All
rig
h
t
s reser
ve
d
.
1. Introducti
on
No
wad
a
ys, with the rapid developm
ent
of in
formation technol
ogy, espe
cially the web
servi
c
e
-
ba
se
d appli
c
atio
n, se
rvice
-
o
r
iented a
r
ch
itecture a
nd
clou
d-com
put
ing, co
ntinu
a
lly
expandi
ng da
ta are inte
gra
t
ed to gen
era
t
e useful
i
n
fo
rmation. Th
ere are
many
databa
se
s a
n
d
data wa
re
ho
use
s
availa
bl
e all aro
und
the wo
rld. T
he co
re ta
sk is to make
good u
s
e
of the
informatio
n o
r
kno
w
le
dge
from these
databa
se
s. Implicit kno
w
ledge of the
databa
se
s can
provide
imp
o
r
tant p
a
ttern
s like
a
s
soci
ation
rule
s
whi
c
h
may l
ead
to de
ci
sion
sup
port
ma
ki
ng,
medical di
ag
nosi
s
and
m
any oth
e
r
a
pplication
s
.
Asso
ciatio
n
rule mini
ng i
s
task of fin
d
i
n
g
intere
sting asso
ciation or corr
elation
rel
a
tionship
s
a
m
ong l
a
rg
e d
a
taba
se
s [1]. Asso
ciatio
n rule
s
are tho
ught t
o
be interesti
ng as
well a
s
useful
if the
y
meet both a minimum
suppo
rt thre
sh
old
and
a mini
mu
m confiden
ce
threshold
[2
, 3]. A majo
r
con
c
e
r
n i
n
a
s
so
ciation
rul
e
s mi
ning
toda
y
is to contin
ue
to improve al
gorithm p
e
rfo
r
man
c
e.
Asso
ciatio
n rules can be
defined
by formal definitio
n as Let
12
{,
,
,
}
m
I
ii
i
be a set
of items. L
e
t
D
be a
set of d
a
taba
se tran
saction
s
whe
r
e ea
ch t
r
an
saction
T
is a
set of items
su
ch t
h
at
TI
. Each
tran
sa
cti
on mu
st h
a
ve an i
dentifie
r, call
ed
TI
D
. Let
A
be a
set o
f
items. A tran
sa
ction
T
is sa
id to contain
A
if and only if
A
T
. An asso
cia
t
ion rule i
s
of the
form
AB
, where
A
I
,
B
I
and
AB
.
Asso
ciatio
n rule minin
g
[8
-12] ha
s attra
c
ted
a l
o
t of intention in
re
sea
r
ch a
r
ea
of data
mining a
nd g
eneration of
asso
ciation
rules i
s
compl
e
tely depen
d
ent on findin
g
frequ
ent item
sets. M
any al
gorithm
s a
r
e
available fo
r t
h
is p
u
rpo
s
e.
In [1], an alg
o
rithm fo
r fre
quent item
set
gene
ration i
s
propo
se
d, which is the first algorit
hm
being availa
b
l
e to us for freque
nt item
set
discovery an
d is kn
own as AIS algorithm.
The Apri
ori
-
b
a
se
d algo
rith
ms find fre
q
u
ent
item set
s
based up
on
an iterative b
o
ttom-up
method to ge
nerate
can
d
id
ate item sets.
Since the
first pro
p
o
s
al of
associ
ation rules mini
ng b
y
R. Agrawal
[1
, 2], many re
searche
s
have
been
do
ne t
o
ma
ke frequ
ent item
sets
mining
scala
b
l
e
and effici
ent. But there
are still some
deficie
nci
e
s t
hat Aprio
r
i-ba
sed
algo
rithm
s
suffere
d fro
m
,
whi
c
h in
clud
e too many
scan
s of
the
transactio
n
d
a
taba
se
whe
n
se
eki
ng fre
quent item
sets,
large
am
ount
of ca
ndid
a
te i
t
em sets
gen
erated
u
nne
cessarily
and
so on.
In [4], a
n
alg
o
rithm
h
a
s
been
sugg
est
ed by using b
o
ttom up method along
wi
th using matrix and redu
ce
d transactio
n
s
.
In [5], a new algorith
m
ha
s be
en given
for re
du
cing
the ca
ndid
a
te item set
s
b
y
redu
cing t
h
e
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 4, April 2014: 2941 – 2
949
2942
con
n
e
c
ting it
em sets i.e.
For la
rg
e dat
aba
se, this o
p
timized
algo
rithm can
sav
e
co
st a
s
well
as
time and hen
ce in
cre
a
se the efficien
cy than the Apri
ori algo
rithm.
In [6], a method ha
s bee
n
prop
osed to improve the ef
ficien
cy of Apri
ori Algo
rith
m using tran
saction redu
cti
on.
In the next
se
ction,
we int
r
odu
ce p
r
in
cip
l
e of
Apri
ori,
dire
ct ha
sh
a
nd p
r
uni
ng. In Sectio
n
3 we p
r
op
ose a
efficient
algorith
m
b
a
s
ed
on
di
fferential evol
utionary
co
mpu
t
ation [19-22]
. In
Section 4, we
test the performa
n
ce of three al
gorith
m
s. In Sectio
n 5 we co
ncl
ude the pap
e
r
and
giv
e
some
re
mar
ks.
2. Principle
of As
socia
t
ion Rule Mining
The pro
c
e
s
s of commo
nly use
d
Aprio
r
i algorith
m
is a
s
follows:
input: Databas
e, D, of trans
a
c
t
ions
;
minimum su
ppo
rt threshold, mi
n_sup.
output: L, freuqent itemsets in D.
C
k
: Candi
dat
e itemset of size k
L
k
:freque
nt itemset of si
ze
k
L
1
= find_fre
q
uent_1
_itemsets(D);
for (k
= 2; L
k+1
!=
; k++) d
o
begin
{
C
k
= aprio
ri_gen
(L
k-1
, min_sup);
for each transactio
n
t in databa
se D
do{
scan D for count
s
Ct =
s
ubset(C
k
, t); get the subsets of t that ar
e candid
a
tes For e
a
ch can
d
idate
c
C
t
c.count++;
}
L
k
= candidates in
C
k
wi
th min_su
ppo
rt
}end
return L=
k
L
k
;
In every sca
nning
of finding a
s
sociati
on rul
e
s, fre
quent item
set
i
L
is ne
ede
d to
gene
rate ca
n
d
idate
item set
1
i
C
, meanin
g
com
b
ine t
w
o
i
L
freq
uent it
em sets(
11
LL
) with
1
i
numb
e
r of
common
items. Then
scan
databa
se
and
statisti
c
sup
port d
e
g
r
ee
o
f
each item
set
in
1
i
C
to determine
1
i
L
. Large
r
numb
e
r
of ite
m
set
in
i
C
re
sult
s i
n
hig
her
co
s
t
t
o
determi
ne
i
L
. In ord
e
r to u
n
derstand th
e prin
ciple
of Direct
Ha
sh an
d Prunin
g
, we give out an
example th
at
gene
rate
s a
candid
a
te 2
-
ite
m
set
by
mea
n
s
of DHP
al
gorithm. A
bu
cket is ma
de
up
of the foll
owi
ng th
ree
pa
rts. Bucket
n
u
mbe
r
i
s
co
rrespon
ding
value
of
Ha
sh fun
c
tion. T
he
se
con
d
pa
rt is elem
ent
sto
r
ed in th
e Ha
sh tabl
e. The
third pa
rt is t
he num
be
r of
cell el
ement
s in
the table.
Ha
sh ta
ble i
s
m
ade
up
of the
third
pa
rt
of
all the
bu
ckets. All the
bu
ckets con
s
ist
s
a bit
vector. Valu
e
of each bit i
n
the bit vect
or is
rel
e
vant
to the numb
e
r of ele
m
ent
in the bu
cke
t. If
the numbe
r is greate
r
than
or equ
al to
mi
n
s
u
p
, it is 1, otherwise it is 0.
Table 1. Tran
sa
ction Datab
a
se Exampl
e
TID
I
TE
M
S
100 ACD
200 BCE
300 ABCE
400 BE
For
datab
ase
in T
able
1, t
he p
r
emi
s
e
condition
of al
gorithm
is mi
nimal
sup
p
o
r
t deg
ree
i
s
2
and
hash functio
n
is (1).
{,
}
(
(
)
1
0
(
)
)
m
o
d
7
h
x
y
o
r
d
er
o
f
x
o
rd
er
o
f
y
.
(1)
order
o
f
x
is the seq
uen
ce num
b
e
r of
x
in all value sequ
ences. Such
as
transactio
n
it
em of the
dat
aba
se i
s
A, B
,
C, D
and
E
and o
r
d
e
r
of A is 1, o
r
d
e
r
of D i
s
4. Fi
rstly
gene
rate
ca
ndidate
1-ite
m
set, that i
s
1
{{
},
{
}
,
{
},
{
}
,
{
}}
CA
B
C
D
E
. Secon
d
l
y
scan
all
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A High Efficie
n
t Asso
ciatio
n Rule Mini
ng
Algorithm
Based o
n
Intelligent… (Wu F
eng
xian
g)
2943
transactio
n
s
in the datab
ase, stati
s
tic supp
or
t de
gree of all these ca
ndid
a
te 1-item
set
to
gene
rate
1
L
. At the same t
i
me
1
C
set
s
u
p
ha
sh t
a
ble
2
H
for fas
t
s
t
atis
tics
. In order to
c
o
ns
tr
uc
t c
a
nd
id
a
t
e
2-
ite
m
s
e
t
2
C
to s
e
t
up
2
H
, databa
se
is de
comp
osed
as sh
own in
Table
2.
For 2
-
itemset {A C}, sub
s
titute into hash function a
nd
obtain:
{{
}}
(
(
)
1
0
(
)
)
m
o
d
7
(1
1
0
3
)
m
o
d
7
6
h
A
C
o
r
d
er
of
A
o
r
d
e
r
of
C
(2)
D
i
r
e
c
t
ha
sh
an
d
pr
u
n
i
n
g
de
te
c
t
ea
ch
item to
dete
r
mi
ne
wheth
e
r it
is in
the
ha
sh
table. If
it is in
the
ha
sh ta
ble, valu
e of
cou
n
t of
this item
is in
cre
a
sed
by 1.
Othe
rwi
s
e
it
put this item i
n
the ha
sh ta
bl
e an
d value
o
f
cou
n
t is
set
to 1. Sch
e
ma
tic dia
g
ra
m of
ha
sh ta
ble
2
H
is
s
h
ow
n
in
Table 3.
Table 2. Data
base De
com
positio
n
100
{A C},
{
A D
}
,{C,D}
200
{B C},
{
B E},
{
C,E
}
300
{A B},
{
A C},
{
A E},{B C},
{
B
E}
,{
C E
}
400 {B
E}
Table 3. Data
base De
com
positio
n
Hash
value
0
1 2
3
4
5 6
el
ement
{CE
}
{CE
}{A
D
}
{A
E
}
{B
C}
{B
C
}
{B
E
}{B
E
}{B
E
}
{A
B
}
{A
C}
{CD
}{A
C}
Number
of
eleme
n
t
3
1 2
0
3
1 3
Becau
s
e
mi
nimum
su
pp
ort i
s
2,
bi
t vector is <1,
0, 1,
0, 1,
0,
1>
and
1
{{
}{
}{
}{
}}
LA
B
C
E
. Then do
11
LL
and obtain
11
{{
}{
}{
}{
}{
}{
}}
L
L
AB
AC
AE
BC
BE
C
E
.
Subs
titute 2-items
e
t in
11
LL
into hash fun
c
t
i
on to obtain
hash ad
dre
ss of ea
ch 2-
itemset. Fo
r
each tran
sa
ct
ion, wh
en all
1-item
sets
statistics
com
p
letely, all 2-i
t
emset
s
of this
transactio
n
g
enerate. The
n
acco
rdin
g to val
ue of bit vector, filter
2-item
sets fro
m
11
LL
and 2-
itemset
s
who
s
e bit vecto
r
is 0 are
delete
d
. At last we obtain
2
{{
},
{
}
,
{
},
{
}
}
CA
C
B
C
B
E
C
E
.
3. An Improv
ed Scheme
Bas
e
d on Differen
tial Ev
o
l
utionar
y
Alg
o
rithm
3.1. Principle of Differ
en
ti
al Ev
olutionar
y
Algorithm
In esse
nce, d
i
rect
ha
sh
an
d prunin
g
u
s
es
as
so
ciatio
n op
eratio
n t
hat is the
sa
me a
s
the
method th
at
Apriori
alg
o
rit
h
m u
s
e
s
to
determi
ne
ca
ndidate
item
sets [13-18]. The
r
e
are
two
probl
em
s. Th
e first p
r
obl
e
m
is that
co
nstru
c
ting
ha
sh tabl
e with
out co
nflictio
n
is the
o
retically
optimal, b
u
t it nee
ds
con
s
u
m
e a
lot
of m
e
mory
sp
ace
and
sp
ace uti
lization
is lo
w. The
se
co
nd
is
that it does n
o
t have hash tree
data
stru
cture le
adin
g
to too long in
sert an
d se
arch time.
Dire
ct ha
sh
a
nd prunin
g
o
w
n
s
fast exa
c
tion ti
me at
the co
st of calcul
ating ha
sh tabl
e
and sto
r
ag
e space of the d
a
taba
se
table
.
This re
quire
s that dat
aba
se can be
sto
r
ed in me
mory.
If the datab
a
s
e i
s
to
o la
rg
e, it ca
n n
o
t
be pl
aced
in
memory. It
will was
t
e
a lot
of time
reading
from the di
sk and
co
st of establi
s
hi
ng
hash table
i
s
expen
sive. Throu
gh the
a
nalysi
s
of de
gree
of databa
se
pruni
ng of di
rect h
a
sh pruning al
gorit
hm, we find
that pruni
ng
techn
o
logy can
further streng
then, so
that
we p
r
o
p
o
s
ed
an imp
r
ove
d
algo
rithm b
a
s
ed
on
dire
ct
hash p
r
uni
n
g
.
Dire
ct h
a
sh a
nd p
r
unin
g
i
m
prove
s
efficiency th
rou
g
h
pru
n
ing
of candid
a
te item
set. In o
r
de
r to
deal
with g
r
eat datab
ase, dire
ct h
a
s
h
and
pru
n
i
ng is combi
ned
with ra
ndom
sam
p
li
ng
techn
o
logy t
o
imp
r
ove
a
pplication
ra
nge
and
ex
e
c
ution
efficie
n
cy. Data i
n
the
datab
ase is
distrib
u
ted ra
ndomly, mea
n
ing ea
ch t
r
a
n
sa
ction
in t
he datab
ase
perh
a
p
s
ap
p
ears in the
a
n
y
record of databa
se. Beca
use in the b
e
g
innin
g
, t
here
are many da
ta items whi
c
h make an
other
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 4, April 2014: 2941 – 2
949
2944
item set from each transaction many. This in
creases the possi
bility
of confliction of
hash
function,
whi
c
h m
a
kes
pe
rforma
nce of
dire
ct ha
sh
and
p
r
u
n
ing worse. To re
duce
the co
st
of
establi
s
hi
ng
Ha
sh table, a
nd re
du
ce th
e execut
io
n time, databa
se
can be
dealt
with prin
cipl
e of
rand
om
sam
p
ling. In th
eo
ry, the meth
o
d
of di
sc
overi
ng a
s
so
ciatio
n rul
e
s from
sampl
e
s exist
s
a
probl
em an
d there i
s
a bal
ance betwee
n
time and a
c
curacy. Since
there is n
o
search ba
se
d
on
the whole d
a
ta, some i
n
formatio
n may be lost. From imple
m
entation re
sults of mult
iple
databa
se
s, a
s
long
as the
numbe
r of sample a
nd
selectio
n of re
laxation facto
r
is ap
propri
a
te
and get go
od
results.
Differential
evolutiona
ry comp
utatio
n is
on
e o
f
the curren
tly popular
intelligent
popul
ation ev
olutiona
ry alg
o
rithm. Its
sol
v
ing efficien
cy is hig
h
an
d
has a b
e
tter solutio
n
spa
c
e
sea
r
ch pe
rformance an
d strong
rob
u
stn
e
ss, so
us
i
n
g differential
evolutiona
ry comp
utation
to
solve the pro
b
lem of asso
ciation rule e
x
traction is fe
asibl
e
.
Differential
e
v
olution alg
o
rithm pro
d
u
c
e
d
in 1
995,
which i
s
pro
p
o
s
ed
by Rain
er Storn
and Ke
nneth
P
rice
in th
e
United
States o
n
the
ba
sis of
evolutio
nary id
ea
s
such
a
s
g
ene
tic
algorith
m
. This al
gorithm
is al
so a
kind of
bioni
c intelligent a
l
gorithm
stim
ulating natu
r
al
biologi
cal
ev
olution m
e
ch
anism.
It is the m
a
in
o
peratin
g tho
ught i
s
b
a
sed o
n
in
dividual
differen
c
e de
gree of the p
opulatio
n gen
erate
temp
orary individual
, and use o
n
e
-to-one g
r
ee
dy
sele
ction
co
mpetition m
e
ch
ani
sm to
reali
z
e po
pulation evo
l
ution thro
ug
h the ra
nd
om
rest
ru
cturin
g. The co
ncrete
process is a
s
follows:
Step 1. Population ran
dom
initialize.
(0
,1
)
rand
returns
ran
dom n
u
mbe
r
of
(0
,1
)
,
0
t
.
(0
)
{
(0
)
|
(
0
)
(
0
,
1
)
(
)
1
}
ii
j
j
j
j
PX
x
r
a
n
d
U
L
L
j
n
.
(
3
)
Step 2. It is the mutation pro
c
e
ss.
Cho
o
se thre
e individual
s
()
,
(
)
,
()
ab
c
XtX
t
X
t
rand
om i
n
po
pulation
()
Pt
. Three in
dividual
s a
r
e
differe
n
t
with
()
i
Xt
.Operat
e with
the foll
ow
expre
ssi
on.
12
(1
)
(
(1
)
,
(1
)
,
,
(
1
)
)
ii
i
i
n
Dt
d
t
d
t
d
t
.
(
4
)
(1
)
(
)
(
(
)
(
)
)
ij
aj
b
j
c
j
dt
x
t
F
x
t
x
t
.
(
5
)
1,
1
is
jn
.
Step 3. It is the cro
s
sover
pro
c
e
ss.
1
r
2
,
r
is ra
ndom valu
e o
f
betwee
n
0 a
nd 1. Calculat
e
temporary ind
i
vidual acco
rd
ing to (6) a
n
d
(7).
12
(1
)
(
(1
)
,
(
1
)
,
,
(
1
)
)
ii
i
i
n
Et
e
t
e
t
e
t
.
(
6
)
1
1
(1
)
,
(1
)
()
,
ij
ij
ij
dt
r
C
et
x
tr
C
.
(7)
Step 4. It is th
e sele
ction p
r
oce
s
s acco
rdi
ng to (8).
(1
)
,
(
(
1
)
)
(
(
)
)
(1
)
()
,
ii
i
i
i
E
tf
E
t
f
X
t
Xt
Xt
e
l
s
e
.
(8)
Step 5. Cal
c
ulate individu
al with the
smallest fitne
s
s
(1
)
b
Xt
in
(1
)
Pt
. If meet
the
terminatio
n condition, out
put
b
X
and
()
b
f
X
. Otherwise
1
tt
and
turn ba
ck
to step 2
to
contin
ue.
(0
,
2
)
F
is perturbation
scale factor a
n
d
(0
,
1
)
C
is cr
os
s f
a
ct
or.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A High Efficie
n
t Asso
ciatio
n Rule Mini
ng
Algorithm
Based o
n
Intelligent… (Wu F
eng
xian
g)
2945
3.2. An
Effic
i
ent
Ass
o
cia
t
ion
Rule Mi
ning Al
go
rithm Ba
sed
o
n
Differ
entia
l
Ev
olutionar
y
Com
p
u
t
atio
n
H
o
w
th
e or
ig
in
a
l
s
o
lu
tion
is r
e
p
r
es
en
te
d
b
y
d
i
ffere
ntial
evolution
alg
o
rithm
co
ding
form
is
the mo
st im
p
o
rtant li
nk. In
dividual
of th
e alg
o
ri
thm
i
s
set i
n
to a
binary
code
stru
cture, whi
c
h
rep
r
e
s
ent
s d
e
ci
sion attrib
ute and task attribute
stru
cture
co
ntaini
ng item set
s
and befo
r
e a
n
d
after part.
12
12
{,
,
,
,
,
,
}
nm
A
AA
B
B
B
,
i
A
is de
ci
sion
attribute
an
d
i
B
is task
attribut
e. The
individual coding
is
12
1
2
{,
,
,
,
,
,
}
nm
x
xx
b
b
b
.
12
,,
,
n
x
xx
is de
ci
sio
n
attribute
and
12
,,
m
bb
b
is task
attribute. Attribute pop
ulation
and
rule
pop
ulation i
s
ge
nerate
d
. Attribut
e
popul
ation i
s
used
to g
e
nerate
fre
q
u
ent item
set
s
a
n
d
rul
e
popul
ation i
s
used
to o
b
t
ain
asso
ciation
rule. Frequ
en
t item sets
are
gen
er
ate
d
by attri
but
e po
pulatio
n
and
the fitn
ess
function that
cho
o
se high
sup
port de
gree and a
ban
d
on low
sup
p
o
r
t degree is
shown in (9
).
1
(
)
s
upp(
)
(
s
up(
)
/
(
)
)
j
j
iX
Y
f
Rw
R
w
R
l
e
n
R
.
(
9
)
For rule po
pu
lation used to
gene
rate a
s
so
ciation
rule
, screeni
ng is done a
c
cordi
ng to credibili
ty
of generated
rule an
d the correspon
ding
fitness fun
c
tio
n
is (10
)
:
2
()
()
i
n
t
(
)
f
Rc
o
n
f
R
e
r
R
.
(
1
0
)
s
up(
)
()
s
up(
)
c
R
co
n
f
R
R
.
(11)
0
0
(
)
s
up(
)
in
t
(
)
m
a
x{
(
)
,
s
up(
)
}
co
n
f
R
R
er
R
c
onf
R
R
.
(
1
2
)
1,
1
.
R
represents rule an
d
()
len
R
represe
n
ts the
le
ngth of rule.
int
(
)
er
R
is
intere
stingn
e
s
s deg
re
e of
rule,
whi
c
h i
s
a num
be
r m
o
re th
an 0.
c
R
is
data set whi
c
h rep
r
e
s
ents
su
ccessful m
a
tchin
g
bet
ween rule
R
and
deci
s
io
n attri
bute in the
R
,
0
R
is data
set
whi
c
h
rep
r
e
s
ent
s su
ccessful m
a
tching b
e
twe
e
n
rule
R
and ta
sk
attribute in th
e
R
. The p
r
o
c
e
ss
of ou
r
prop
osed alg
o
rithm is a
s
follows:
Step 1. Initialize the po
pula
t
ion.
Step 2.
k
x
is tra
n
sformed to
[0
,1
]
k
cx
according to (13).
mi
n
,
ma
x
,
()
/
(
)
kk
k
jj
j
j
j
c
x
xx
xx
.
(
1
3
)
1,
2
,
,
0
jn
k
.
Step 3. Calcu
l
ate the next individual a
c
cordin
g to (14
)
and (15
)
.
1
4(
1
)
kk
k
jj
j
cx
cx
cx
.
(
1
4
)
11
mi
n
,
ma
x
,
mi
n
,
()
kk
jj
j
j
j
xx
c
x
x
x
.
(15
)
Step 4. If
1
0
()
(
)
k
j
f
xf
x
,
the prog
ram
stops. Othe
rwi
s
e it turns to
step 2 to
go
on
runni
ng.
Step 5. Keep
80% excell
e
n
t individual
s and ab
and
o
n
other i
ndivi
dual
s to gen
e
r
ate new
popul
ation.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 4, April 2014: 2941 – 2
949
2946
Step 6. For the new p
o
p
u
lation, rep
e
a
t step
2 to step 4. If it meets the termin
al
con
d
ition, record
cu
rrent b
e
st individ
ual
be
s
t
X
and
stop
th
e program. O
t
herwi
se
do
a
s
(16) an
d
(17
)
. Ran
dom
ly generate 5
0
% individua
ls in
mi
n
,
ma
x
,
[,
]
jj
xx
and tu
rn
to step 2 to go on.
mi
n,
mi
n
,
,
m
a
x
,
m
i
n
,
ma
x
{
,
(
)
}
jj
b
s
e
t
j
j
j
Xx
x
r
x
x
.
(
1
6
)
ma
x
,
ma
x
,
,
m
a
x
,
m
i
n
,
mi
n
{
,
(
)
}
jj
b
s
e
t
j
j
j
Xx
x
r
x
x
.
(
1
7
)
01
r
.
4. Experiment and Analy
s
is
In this exp
e
r
iment, ha
sh
table
k
H
with
k+1-ite
m
set is g
ene
ra
ted. Tra
n
saction
tA
B
C
D
E
F
. Hash tabl
e establi
s
h
ed b
y
2
C
contai
ns five numbe
r of 2-item set (A
C, AE, AF,
CD, EF). Accordin
g to our
prop
osed alg
o
rithm,
A, C, E and F are
kept and B an
d D are delet
ed.
t
is la
beled
a
s
'
t
. It can b
e
se
en that n
o
t all
the items in
t
can
be
used t
o
gen
erate item set. In
fac
t,
C
doe
s n
o
t belon
g to
any item set,
becau
se onl
y AC and
CD are 2
-
can
d
id
ate item set
s
.
So
C
is deleted
from
'
t
.
Execution ti
me comp
ari
s
on of th
ree
algorith
m
i
s
sho
w
n
in T
a
ble 4. Exe
c
u
t
ion time
comp
ari
s
o
n
of three algo
rithms u
nde
r the same suppo
rt and d
i
fferent datab
ase i
s
sho
w
n in
Figure 1. Exe
c
ution tim
e
compa
r
ison of
three
al
go
rithms
und
er di
fferent supp
o
r
t and th
e
sa
me
databa
se is
sho
w
n in Ta
ble 5. Execution time
com
pari
s
on of three algo
rithms under different
sup
port a
nd the sa
me data
base is
sho
w
n in Figu
re
2.
The blue lin
e
represents A
p
rio
r
i algo
rith
m,
the red line repre
s
e
n
ts direct ha
sh and
pruni
n
g
algo
rithm DHP, and the yello
w line rep
r
e
s
ents
our p
r
o
p
o
s
ed
algorith
m
ba
sed
on diffe
rential ev
oluti
onary IDE. It can
be
see
n
that execution
time of our
prop
osed al
g
o
rithm b
a
sed
on differ
enti
a
l evolution
a
r
y is
small.
Execution ti
me
comp
ari
s
o
n
o
f
gene
ratin
g
k frequ
ent
se
t of thre
e
alg
o
rithm
s
u
nde
r the
same
d
a
taba
se
and
the
same
mini
ma
l su
ppo
rt i
s
shown in
Ta
bl
e 6
and
Fig
u
r
e
3. Ta
kin
g
databa
se
of
5000
0 lin
e fo
r
example, exe
c
ution time o
f
IDE and DHP is mu
ch
smalle
r than
that of Apriori. But 1-frequ
ent
item set, exe
c
ution
time
of IDE a
nd
DHP is l
onge
r th
an that
of Ap
riori. B
e
ca
use Apri
ori
ha
s
the
best p
e
rfo
r
m
ance at the f
i
rst it
eration
and
DHP n
e
eds to
co
nstruct ha
sh ta
ble at the first
iteration.
Table 4. The
Execution Ti
me of the Three Algorithm
s
Data
size(
line)
Execution time(s
)
Apriori DHP
IDE
4000
73
37
28
5000
91
45
38
6000
114
55
46
8000
153
72
60
10000
192
94
72
15000
285
133
94
20000
324
185
124
30000
572
277
156
50000
955
472
206
100000
1833
954
264
150000
2765
1422
332
These th
ree
algorith
m
s a
r
e u
s
ed
in
the
ele
c
tro
n
ic co
mmerce
re
co
mmend
ation
system,
aiming to fin
d
the asso
ci
ation mod
e
a
nd k
nowl
edg
e betwe
en b
r
owsed
WEB page
s in trad
ing
things. It can
predi
ct user
intere
sting pa
ges a
nd an
al
ysis u
s
e
r
s' p
r
eferen
ce to
contribute to t
h
e
relatively larg
e si
ze
of pu
rcha
se. Expe
rimental
d
a
ta
com
e
s from
logs of
WEB se
rver
of an
enterp
r
i
s
e
WEB containi
n
g
726
WEB
page
s. Five
wee
k
s visit reco
rd
s a
r
e e
x
tracted
and
6200
use
r
tran
sa
cti
ons a
r
e obtai
ned after dat
a prep
ro
ce
ssi
ng. Relatio
n
betwe
en exe
c
ution time a
nd
minimum
su
p
port d
egree i
s
sho
w
n i
n
F
i
gure
4 a
nd
relation b
e
twe
en exe
c
ution
time an
d th
e
numbe
r of tra
n
sa
ction i
s
sh
own in Fig
u
re
5. In
Figure 4, the red line
represents A
p
rio
r
i algo
rith
m,
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A High Efficie
n
t Asso
ciatio
n Rule Mini
ng
Algorithm
Based o
n
Intelligent… (Wu F
eng
xian
g)
2947
and yell
ow li
ne rep
r
e
s
ent
s di
re
ct h
a
sh an
d p
r
uni
n
g
alg
o
rithm
and th
e bl
ue
line
rep
r
e
s
e
n
ts
prop
osed alg
o
rithm IDE. In Figure 5, the yello
w lin
e rep
r
e
s
ent
s Apriori
algo
rithm, and red
line
rep
r
e
s
ent
s di
rect h
a
sh an
d pruni
ng alg
o
rithm
an
d the blue line re
pre
s
ent
s pro
posed alg
o
rit
h
m
IDE. It can be see
n
that runnin
g
time of each
al
go
rithm become
s
sm
aller
wit
h
the increa
se of
minimum
sup
port. When t
he minim
u
m
sup
port i
s
th
e sa
me, ru
nn
ing time of A
p
rio
r
i is l
ong
est,
runni
ng
tim
e
of DHP
i
s
middle and
runnin
g
time
of
IDE
i
s
sh
ortest. Ru
nni
ng
time
of
e
a
ch
algorith
m
be
comes l
a
rg
er
with the in
crease of
num
ber of tra
n
sa
ction an
d ru
n
n
ing time of
our
prop
osed
al
gorithm
is shorte
st. Efficiency
of propo
sed
alg
o
r
ithm b
a
sed
on
differen
t
ial
evolutiona
ry comp
utation i
s
the be
st, which
can b
e
u
s
ed in el
ectro
n
ic comme
rce system.
Figure 1. Execution Tim
e
Comp
ari
s
o
n
of
Thre
e Algorit
hms un
de
r the Same Supp
ort
and Different Datab
a
se
Figure 2. Execution Tim
e
Comp
ari
s
o
n
of
Thre
e Algorit
hms un
de
r Di
fferent Suppo
rt and
the Same Dat
aba
se
Figure 3. Execution Tim
e
Comp
ari
s
o
n
of
Gene
rating
k Freq
uent Set of Three
Algorithm
s
Figure 4. Rel
a
tion betwee
n
Execution T
i
me
and Minim
u
m
Support
Figure 5. Rel
a
tion betwee
n
Execution
T
i
me and the
Numb
er of Transactio
n
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 4, April 2014: 2941 – 2
949
2948
Table 5. Execution Time Compa
r
ison of Thre
e Algorit
hms un
de
r Di
fferent Suppo
rt and the
Same Databas
e
Minimal
support
Execution time(s
)
Apriori DHP
IDE
0.5%
1643
704
272
1%
1408
632
248
1.5%
1296
598
236
2%
1205
576
234
3%
1148
532
218
5%
1024
486
210
6%
955
472
206
Table 6. Execution Time Compa
r
ison of Gene
rating
k Freq
uent Set
The numbe
r of f
r
equent item sets k
Execution time(s
)
Apriori DHP IDE
1 62
76
66
2 154
78
34
3 162
64
27
4 133
57
21
5 122
51
16
6 108
46
14
7 102
42
12
8 66
36
8
9 46
22
8
5. Conclusio
n
This pap
er in
vestigate
s
th
e p
r
inci
ple
of
Aprior
i,
direct
ha
sh
and
p
r
uning
an
d al
so stu
d
ie
s
their drawba
cks. The
n
we prop
ose a
n
improve
d
algorith
m
ba
s
ed o
n
differential evolutionary
algorith
m
. Th
e expe
riment
re
sults show that ou
r p
r
o
posed al
go
rithm ha
s b
e
tte
r exe
c
ution ti
me
and a
c
cu
ra
cy and
pro
p
o
s
e
d
algo
rithm b
a
se
d on
di
fferential
evolutionary
com
put
ation is ca
n b
e
use
d
in ele
c
tronic
comm
erce sy
stem.
Referen
ces
[1]
Rakes
h
Agr
a
w
a
l, T
o
masz Imielinsk
i, Aru
n
S
w
a
m
i.
Mi
nin
g
Associati
on
Ru
les b
e
tw
een S
e
ts of Items
i
n
Larg
e
Data
bas
es.
Proceed
in
g
s
of the 1993 A
C
M SIGMOD
Confer
ence W
a
shi
ngto
n
DC, USA. 1993.
[2]
Jia
w
e
i
Ha
n,
Michel
in
e Ka
mber.
Data
Minin
g
: Co
nc
epts an
d T
e
c
hni
ques
. Mor
gan K
aufma
n
n
Publ
ishers, Ch
ampa
ign: CS4
97JH, fall 2
0
0
1
.
[3]
Rakes
h
Agra
w
a
l, Ramakris
hn
an Srika
n
t.
F
a
st Algorith
m
s for Minin
g
Ass
o
ciati
on Ru
les.
Proceed
ing
s
of the 20th VL
DB Confer
enc
e Santia
go, Ch
ile. 19
94.
[4]
Suni
l Kumar, Sh
yam Kara
nth, Aksha
y
K, Anant
h Pra
b
h
u
, Bharathra
j
Kumar M. Improved Apr
i
o
r
i
Algorit
hm Base
d on bottom u
p
appr
oach
usin
g Proba
bil
i
t
y
a
nd Matri
x
.
201
2; 9(2): 169
4-0
814.
[5]
Jiao Y
a
b
i
ng.
Rese
arch
of an Improv
ed
Apriori
Alg
o
rit
h
m in
Data
Minin
g
Assoc
i
ation
Rul
e
s
.
Internatio
na
l Journ
a
l of Co
mputer
an
d Co
mmu
n
ic
ation En
gin
eeri
n
g
. 2013; 2(1).
[6]
Jaishr
ee Si
ng
h
,
Hari R
a
m, Dr
JS Sod
h
i. Improvi
ng Effici
e
n
c
y
of Apri
ori
Algorit
hm usi
n
g T
r
ansaction
Red
u
ction.
Inte
rnatio
nal Jo
urn
a
l of Scient
ific and
R
e
se
arch Publ
icatio
ns.
2
013; 3(1), ISSN 225
0-31
53.
[7]
Anurag Choubey
,
Rav
i
ndr
a P
a
tel,
JL Rana.
A Survey
of Ef
ficient
A
l
gor
ithms and Ne
w
A
pproach f
o
r
F
a
st Discover
y
of F
r
eqent itemset for Associatio
n Rul
e
Min
i
ng.
IJSCE
, ISSN: 2231-
23
07
, 2011; 1(2).
[8]
AMJ Md Z
ubai
r Rahma
n
, P Balas
ubram
ani
e
,
P Venk
ata Krihsn
a. A Hash base
d
Mini
ng
Algorit
hm for
Maximal F
r
e
q
u
ent Itemsets u
s
ing
Lin
ear Pr
o
b
in
g.
Infoco
mp
Journ
a
l of C
o
mp
uter Sci
enc
e
. 200
9; 8(1):
14-1
9
.
[9]
Y LIU, B YANG. Research o
f
an Improved
Ap
riori A
l
gor
ith
m
in Mini
ng A
ssociati
on Ru
l
e
s.
Journa
l of
Co
mp
uter Appl
icatio
ns
. 200
7; 27: 418-
42
0.
[10]
Lei J
i
, Bao
w
e
n
Z
han
g, Jia
nhu
a L
i
.
A N
e
w
Improv
e
m
ent o
n
Apri
ori
Algor
ith
m
.
C
o
mputati
o
n
a
l
Intelli
genc
e an
d Securit
y
, Internatio
nal C
onfe
r
ence. 20
06; 1:
840-8
44.
[11]
Sujn
i Pau
l
, V S
a
rava
nan.
H
a
s
h
Partitio
ne
d A
p
riori
in P
a
ral
l
e
l
an
d Distri
bute
d
Data M
i
ni
ng
Enviro
n
m
ent
w
i
th Dyna
mic
Data All
o
cati
on
Approac
h.
Co
mputer Scie
nc
e and Inform
ation T
e
chno
log
y
, ICCSIT
'
08.
Internatio
na
l C
onfere
n
ce. 20
0
8
: 481-4
85.
[12]
Bo W
u
, Defu Z
han
g, Qihu
a L
an, Jiemi
n
Z
h
e
ng.
An Efficie
n
t F
r
eque
nt Patterns Min
i
n
g
Al
gorith
m
b
a
se
d
on Apri
ori Al
g
o
rith
m an
d the
F
P
-tree Structure.
Conv
erge
nce an
d H
y
br
i
d
Informatio
n
T
e
chnolog
y,
ICCIT
'
08. T
h
ird
Internation
a
l
C
onfere
n
ce. 20
0
8
; 1: 1099-
110
2.
[13]
Sombo
on A
n
ekritmon
gkol,
Kultho
n Kas
e
ms
an. SQL
Mode
l in
La
ngu
ag
e Enca
psul
ation
an
d
Compress
io
n T
e
chn
i
qu
e for Associati
on Ru
le
s Minin
g
. IJIP
M
l. 2013; 4(1):
65-7
5
.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A High Efficie
n
t Asso
ciatio
n Rule Mini
ng
Algorithm
Based o
n
Intelligent… (Wu F
eng
xian
g)
2949
[14]
Nail
i Li
u, Lei
Ma. Impr
oved
algor
ithm for minin
g
frequ
e
n
t itemsets ba
sed on
bin
a
r
y
.
Internatio
na
l
Journ
a
l of Adv
ance
m
ents in
Co
mp
uting T
e
c
hno
logy
. 2
013;
5(9): 1077-
10
84.
[15]
Moham
ad F
a
r
han M
oham
ad
Mohsin, Mo
h
d
Helm
y
A
bd
W
ahab, Mo
hd
F
a
iruz Z
a
i
y
a
d
i, Cik F
a
zil
a
h
Hiba
d
u
lla
h. An
Investigati
on i
n
to Influe
nce F
a
ct
or of Stude
nt Programmi
n
g
Grade Us
in
g
Associatio
n
Rule
Mi
ni
ng. Advanc
es in Info
rmati
on Sci
enc
es and Serv
ice
Sciences
. 20
1
0
; 2(2): 19-27.
[16]
Yuan
W
ang,
L
an Z
h
eng. E
n
d
o
crin
e H
o
rmon
e
s Asso
c
i
atio
n
Rul
e
s Mi
ni
ng
Based
on
Impr
oved
Apri
or
i
Algorit
hm.
Jour
nal of Co
nver
g
ence Infor
m
ati
on T
e
chn
o
l
ogy
. 2012; 7(7): 72
-82.
[17]
YiJie C
h
e
n
. T
h
e Dev
e
lo
pment
of T
he Commodit
y
F
l
o
w
A
n
a
l
y
s
is S
y
stem B
a
sed On Ass
o
ciatio
n Ru
l
e
Mining.
Interna
t
iona
l Journ
a
l o
f
Advance
m
e
n
t
s
in Co
mp
uting
T
e
chnol
ogy.
2
012; 4(1
3
): 430
-436.
[18]
Cha
ngj
ian
g
L
i
,
Xi
anfe
ng Y
a
n
g
.
T
he Res
earc
h
of Rec
o
mme
ndati
on S
y
ste
m
s in E-C
o
mm
erce Bas
ed
on
Associati
on R
u
le Improv
ed-A
p
riori A
l
g
o
rith
ms.
Internation
a
l Jo
urna
l of
Advanc
e
m
e
n
ts in Co
mputi
n
g
T
e
chno
logy
. 2
012; 4(2
1
): 354
-361.
[19]
J Rönkk
öne
n,
S Kukkon
en,
KV Price.
Re
a
l
-para
m
eter o
p
t
imi
z
at
io
n w
i
th differenti
a
l ev
oluti
on.
Proc.
IEEE Congr. Evolut. Comput., Edinbu
rgh, Scotland.
2005: 506–513.
[20]
AK Qin, VL Huang, PN Su
ga
nthan.
Differe
n
t
ial evo
l
utio
n al
gorithm
w
i
t
h
strateg
y
ad
aptati
on for glo
b
a
l
numeric
al o
p
ti
mizatio
n
.
IEEE Trans. Evol. Comput.,
200
9; 13(2): 39
8-4
1
7
.
[21]
S Das, A Abraham, UK Ch
akrab
o
rt
y
,
A Konar.
Differe
nti
a
l evo
l
utio
n us
ing a n
e
ig
hb
or
hoo
d-bas
e
d
mutation o
per
a
t
or.
IEEE
Trans. Evol. Comput.,
2009; 13(3): 526
–5
53.
[22]
J Brest, S Gre
i
ner, B Boskovic, M Mernik, V Zume
r. Selfada
ptin
g contr
o
l par
ameters in
differe
ntia
l
evol
ution: A
co
mparat
iv
e
stud
y on num
erica
l
be
nchmark
pr
obl
ems.
IEEE
Trans. Evol. Comput.,
20
06
;
10(6): 64
6–
657
.
Evaluation Warning : The document was created with Spire.PDF for Python.