TELKOM
NIKA
, Vol. 11, No. 8, August 2013, pp. 44
7
7
~4
483
e-ISSN: 2087
-278X
4477
Re
cei
v
ed
Jan
uary 24, 201
3
;
Revi
sed
Ma
y 14, 201
3; Accepted Ma
y
24, 2013
An Algorithm on Generating Lattice based on Layered
Concept Lattice
Zhang Ch
an
g-sh
eng
1,2,3
, Ruan
Jing
4
, Huan
g
Hai-l
ong*
3
, Li long-ch
ang
3
, Yang Bing
-ru
1,
2
1
School of Co
mputer an
d Co
mmunicati
on E
ngi
neer
in
g,
Uni
v
ersit
y
of Sci
e
n
c
e and T
e
chno
log
y
Be
iji
ng,
Beiji
ng, 10
00
8
3
, Chin
a
2
Beijin
g Ke
y L
a
borator
y of Kn
o
w
le
dg
e Eng
i
n
eeri
ng for Mate
rials Scie
nce,
Beiji
ng 1
0
0
083
, China
3
Colle
ge of Ph
ysics & Electr
o
n
ic Informatio
n
Engin
eeri
ng,
W
enzho
u Univ
ersit
y
, Z
hej
ia
ng
, 32503
5, Chi
n
a
4
W
enzhou Voc
a
tion
al & T
e
chnical C
o
l
l
eg
e, Z
heji
ang, 3
250
35, Chi
n
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
:jsj_zcs@
12
6.com, ruanj
ing
1
979
@12
6
.com, 1567
32
998
@
qq.com*,
jsj_l
l
c@
w
z
u.ed
u.cn, br
yang
_k
d@1
26.com
A
b
st
r
a
ct
Conc
ept
lattic
e
is
an
effectiv
e too
l
for
data
an
alysis
an
d r
u
le
extractio
n
,
a b
o
ttleneck
fa
ctor on
impacti
ng th
e a
pplic
atio
ns of c
once
p
t lattice
i
s
how
to g
e
nerate latti
ce efficiently. In this
pa
per, a
n
al
gor
ith
m
LCLG on
gen
eratin
g lattice
in batch
proc
essin
g
bas
ed
on lay
e
re
d co
ncept lattic
e
i
s
devel
op
ed, this
alg
o
rith
m
is b
a
s
ed
on
lay
e
re
d co
ncept
latti
ce, the
lattice
is g
ener
ated
d
o
w
n
w
a
rd lay
e
r
by l
a
yer
throu
g
h
conce
p
t nod
e
s
and prov
isi
ona
l nod
es in
current
layer
;
the concept
nodes ar
e foun
d par
ent-c
hil
d
relati
onsh
i
ps
u
p
w
a
rd lay
e
r by
layer, th
en th
e
Hasse
di
agra
m
of inter-l
ayer
conn
ectio
n
is
gen
erate
d
; in t
h
e
gen
erate
d
pr
oc
ess of th
e
latti
ce n
o
d
e
s i
n
ea
ch l
a
yer, w
e
d
o
the
pr
uni
ng
oper
ations
dy
n
a
mical
l
y
accor
d
in
g
to rel
e
vant
pro
perties,
and
d
e
l
ete s
o
me
un
n
e
cessary
no
de
s, such th
at th
e g
ener
atin
g s
pee
d is
i
m
pr
ov
ed
greatly; the ex
peri
m
e
n
tal res
u
lts de
mo
nstra
t
e t
hat the prop
osed a
l
g
o
rith
m has goo
d perf
o
rmanc
e.
Ke
y
w
ords
: co
ncept lattice
ba
tch processi
ng,
layeri
ng, hass
e
dia
g
ra
m, CONCEPT
LAT
t
ice
Copy
right
©
2013 Un
ive
r
sita
s Ah
mad
Dah
l
an
. All rig
h
t
s r
ese
rved
.
1. Introduc
tion
In the appli
c
ations
of the
con
c
e
p
t lattice, the
first
solutio
n
is to
con
s
truct th
e lattice.
Therefore,
it i
s
im
porta
nt to stu
d
y the
g
enerati
ng l
a
ttice
algo
rithm
s
of con
c
ept l
a
ttice. The
r
e
a
r
e
many literatu
r
es
on the
construc
tio
n
al
gorithm
s of concept lattice
. The gene
ra
ting method
s of
con
c
e
p
t lattice can b
e
divi
ded int
o
two
categ
o
rie
s
: b
a
tch
pro
c
e
s
si
ng alg
o
rithm
s
and i
n
crem
e
n
tal
con
s
tru
c
tion
algorith
m
. M
any cl
assi
cal
algo
rith
ms
o
n
ba
tc
h pr
oc
es
s
i
n
g
,
s
u
ch
as
: Bo
rd
a
t
[1
]
,
Osh
a
m [2], Chein [3], Gan
t
er [4], Nou
r
i
ne [5] and
other b
a
tch
pro
c
e
ssi
ng alg
o
rithms. Sch
o
la
rs
have don
e so
me improvem
ents of
the a
bove algo
rith
ms an
d don
e
a wide rang
e
of applicatio
ns,
su
ch
as in t
he literature
[6-10], the
r
e
are
some i
m
provem
ents on
cla
s
sical
algo
rithm
s
,
the
authors i
n
th
e literatu
r
e
s
[11-13]
have
pro
p
o
s
ed
th
e a
s
soci
ation
rule
s
algo
rit
h
ms
ba
sed
on
con
c
e
p
t lattice, som
e
cla
ssifi
cation
an
d clu
s
te
ring
algorith
m
s
b
a
se
d on
con
c
ept lattice
are
prop
osed in t
he literatu
r
e
s
[14-15], and
the links bet
wee
n
the con
c
ept lattice
a
nd ro
ugh
set
are
studie
d
in the
literature
s
[1
6-17].
Algorithm Bo
rdat is a typi
cal effective
algor
ith
m
on
batch p
r
o
c
e
s
sing, in this
a
l
gorithm,
con
c
e
p
t lattice L is
co
nst
r
ucted f
r
om th
e top no
de,
whi
c
h i
s
ge
n
e
rated
all of i
t
s chil
d no
de
s for
each no
de, a
nd complete
the conn
ectio
n
between
th
e chil
d no
de
s to the pa
rent
node, the
n
call
for the re
cursive process o
f
each child
node. The
b
a
s
ic id
ea of the algorith
m
is: if the curre
n
t
node is
(O
1
, D
1
), D is a se
t of attributes. We need
to find the sub
s
e
t
of attributes D
2
D-
D
1
,
su
ch
that D
2
i
s
a
b
le to
maint
a
in the
cha
r
acteri
stics of
the
com
p
let
e
bin
a
ry
gro
up, i.e. it i
s
the
maximum ex
pan
sion. Th
e
n
D
1
∪
D
2
con
s
titutes the
connotatio
n of
a child n
ode
for the cu
rre
n
t
node. The al
gorithm i
s
si
mple, intuitive, and ea
sy
to paralleli
ze. Its disadv
antage i
s
that it
repe
atedly g
e
nerate
s
the
same
node.
It can
be
ob
se
rved that e
a
ch
nod
e i
s
g
ene
rated
hi
s fath
er
s
o
many times
.
From th
e
co
nstru
c
tion
proce
s
s of Bo
rdat al
go
rithm
,
it can
se
e
that althoug
h
Bordat
algorith
m
is
also
relate
s t
o
the hie
r
archy of
con
c
e
p
t, Bordat alg
o
rithm d
o
e
s
not have a
cl
ear
hiera
r
chi
c
al
division, it j
u
st con
s
tru
c
ts the
co
ncept
lattice
in
a
top-do
wn
p
r
o
c
e
ss,
usi
n
g
the
manne
r of generating chil
d node
s to build lattice. In
Bordat algo
rithm, it can not confirm th
at
Evaluation Warning : The document was created with Spire.PDF for Python.
e-ISSN: 2
087-278X
TELKOM
NIKA
Vol. 11, No
. 8, August 2013: 4477 –
4483
4478
what level
of the co
ncept, whi
c
h
con
c
ept belo
n
g
s
to the same l
e
vel, and it j
u
st rely on t
h
e
pare
n
t-child
relation
ship
b
e
twee
n the
n
ode
s to
confi
r
m the
u
ppe
r-lower relatio
n
shi
p
s bet
we
en
some
pa
rticul
ar no
de
s. In
Algorithm Bo
rdat, the
gen
e
r
ated
seq
uen
ce of
con
c
e
p
t is si
milar to t
he
depth-t
r
aversal ord
e
r of th
e tree, su
ch t
hat it
can onl
y determine t
he direct pre
c
urso
r-su
cce
s
sor
relation
shi
p
b
e
twee
n the n
ode
s in level. Therefore, its level is locali
zed.
But in the
pra
c
tical a
p
p
lication
s
, the
spat
ial and
temporal complexities
of many
gene
rating
lat
t
ice alg
o
rithm
s
b
a
sed o
n
concept lattice
need
to b
e
i
m
prove
d
, in t
h
is
pape
r, o
n
the
basi
s
of Algo
rithm Bordat, an alg
o
rithm
LCL
G
on
ge
neratin
g lattice in bat
ch p
r
oce
s
sing
ba
sed
on laye
red
co
nce
p
t lattice
i
s
d
e
velop
ed,
this al
gor
ithm
is
generating lattice
i
n
bat
ch processin
g
,
on the
layer ba
sis of th
e cardi
nalitie
s of th
e attri
butes in
co
n
c
ept l
a
ttice,
do the
pai
rwise
operation
s
be
tween the
co
nce
p
t node
s i
n
cu
rre
nt la
yer or the
con
c
ept node
s an
d the provi
s
io
nal
node
s to gen
erate the n
o
d
e
s in next layer, and d
o
the pruni
ng op
e
r
ation
s
dyna
mically acco
rding
to relevant p
r
opertie
s
, an
d
delete some
unne
ce
ss
ary
node
s, su
ch
that the gen
erating time i
s
redu
ce
d g
r
e
a
tly. The ex
perim
ental
re
sults dem
on
strate th
at th
e efficien
cy
of the p
r
opo
sed
algorith
m
is p
r
ior to Algo
rithm Bordat.
2. Relate
d Definitions
Defini
tion 1
. A formal c
ont
ext is
a triple K =
(
G ,M ,
I
), whe
r
e G is a
set of obje
c
ts, M is a
set of attribut
es, I is a bina
ry relation b
e
twee
n the G a
nd M, i.e.
I
G×M, g
I
m denotes it exists a
relation
shi
p
I
.
Defini
tion 2
.
In the form
al co
ntext K, a bina
ry g
r
oup
(A,B) from G
×
M exi
s
ts the
followin
g
two
prop
ertie
s
:
(1) B =
ƒ
(A),
whe
r
e ƒ
(
A) =
{
m:(m
∈∧
M )
(
g
∈
A
G, g
I
m)};
(2) A
=
g
(B
), where
g
(B)=
{g :(g
∈∧
G )
(
m
∈
B
M, g
I
m)}.
In the formal context K, (A, B) is calle
d as
a con
c
ept,
where B is referred to as
intent of
the con
c
ept (Intent), and A is called th
e extensi
on
of the conce
p
t (Extent
). Each
con
c
ept i
s
a
node of
con
c
ept lattice, the maximum
element of
la
ttice is (G,f(G)), the mini
mum elem
en
t of
lattic
e
is
(g(M),M).
Defini
tion 3
. A partial ord
e
r rel
a
tion be
tween the
co
nce
p
t node
s i
s
esta
blished
. Given
C
1
=(
A
1
, B
1
) and C
2
=(A
2
,B
2
),then C
1
>C
2
B
1
B
2
A
1
A
2
, th
e leadin
g
ord
e
r mea
n
s
C
1
is
the pare
n
t no
de of C
2
or th
e gene
rali
zati
on. If conce
p
ts C
1
=(
A
1
, B
1
) and C
2
=(A
2
, B
2
) sat
i
sf
y
A
2
A
1
, and there
does
not ex
ist the co
nce
p
ts (A,B)
such that A
2
A
A
1
; then C
1
is
called the
dire
ct sup
e
r-concept of C
2
, C
2
is a dire
ct sub con
c
ept
of C
1
, referre
d to as (A
1
, B
1
)>(A
2
, B
2
). The
linear
diag
ra
m of con
c
ept
lattice is g
ene
rated b
a
s
ed o
n
the partial
o
r
de
r rel
a
tion, whi
c
h is
Ha
sse
diagram.
Defini
tion 4
.
In the form
c
ontext K=(G,M,
I
), the rel
a
tionship b
e
twee
n the o
b
j
e
ct g
∈
G
and the prop
erty m
∈
M is (
g
,m)
∈
I
or (g,m)
I
.
A
limited
form backg
ro
und can be repre
s
e
n
ted b
y
a matrix, i
f
(
g
,m)
∈
I
, we use digita 1 to repre
s
ent in
the matrix; if (g,m)
I
, we use digita 1
to
repres
ent in the matrix, this
ma
trix is
said to be a trans
a
c
t
ion
matrix T in formal c
ontext K.
Defini
tion 5
.
Let K =
(G, M,
I
) be a form
context, for a
n
attribute y
∈
M, in the matrix of K,
if y corre
spo
n
d
ing to the co
lumns h
a
s n
u
m
bers of n eq
ual to 1, we call the ran
k
of the attribute is
n, denoted a
s
r(y)=n. De
not
ed by m=max
{
r(y
)|y
∈
M}, m is
the rank
of
form c
ontext.
Defini
tion 6
.
In the
con
c
e
p
t lattice, if B
in the
co
nce
p
t (A, B)
con
t
ains th
e nu
mber of
attributes i
s
K, called
(A, B) is the l
a
ttice n
ode
s
of t
he K-th laye
r, the layer i
s
referred to a
s
the
L
k
.
Defini
tion 7
. Redu
ndant
node: supp
ose there exist
s
the nod
e C in the L-th layer, the
set of
obje
c
ts i
s
A, an
d t
he
set of att
r
ibute
s
i
s
B.
If there exi
s
ts the
nod
e
C’=(A’,B’) in
the
gene
rated p
r
oce
s
s from the L layer to the L+1 laye
r node, such
that C
C’, and A=
A’or B=
B’,
then the nod
e
C is the re
du
ndant no
de in
the L-th layer.
Defini
tion 8
.
Contai
ned
no
de: su
ppo
se t
here
exists th
e nod
e C i
n
the L-t
h
layer,
the set
of obje
c
ts i
s
A, and the
se
t of attributes is B.
If there
exists the
no
de C’
=(A’,B’)
in the ge
nera
t
ed
pro
c
e
ss from
the L layer
to the L+1 l
a
yer no
de, such that B’
B, then the no
de C i
s
the
contai
ned n
o
de in the L-th
layer.
The followi
ng
prope
rtie
s ca
n be obtain
e
d
from the abo
ve definitions.
Property
1
.
Any one lattice nod
es i
n
th
e N-th l
a
yer,
whi
c
h at le
ast
is covere
d b
y
one of
the lattice no
des in the
N-1-th layer.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
e-ISSN:
2087
-278X
An Algorithm
on Gen
e
ratin
g
Lattice ba
sed on La
ye
re
d Con
c
e
p
t La
ttice (Zha
ng
Cha
ng-sh
eng
)
4479
Property
2
. The
con
c
e
p
t n
ode
s in
L
k
l
a
yer
and
othe
r
con
c
e
p
t no
de
s o
r
te
mpo
r
ary node
s
intersect in pair, and ge
nerate L
k+1
layer nod
es, whe
r
e the n
on-con
c
e
p
t node
s are cal
l
ed
temporary no
des.
Property
3
. For
C
1
=(a,b
)
and C
2
=(a’,b’), if it s
a
tis
f
ies
a’
a, b’
b, then directly di
scard
C
2
.
Property
4
. For
C
1
=(a,b) and
C
2
=
(
a’,b’), if it s
a
tis
f
ies
a’=
a
, b’
b, then di
rectly d
i
scard
C
2
after C
1
=(a, b
b’).
Property
5
. For
C
1
=(a,b
)
and C
2
=(a’,b’), if it satis
f
ies
a’
a, b’
=b, t
hen
dire
ctly d
i
scard
C
2
after C
1
=(a
a’,b).
3. LCLG
Algori
t
hm
3.1. The Idea
of Algorith
m
LCLG
In this pap
e
r
, the
de
sig
ned
algo
rith
m L
C
LG
d
r
aws the
cha
r
acte
ri
stics o
f
Bordat
algorith
m
, it is sim
p
le, intu
itive and easy-to-pa
r
a
llel
computing, an
d the co
re d
e
sig
ned id
ea
of
this alg
o
rithm
is a
s
follows.
For the
con
c
ept nod
es in
curre
n
t k laye
r and
other
concept nod
es or
the temporary nodes in
k layer, do the o
peratio
ns
a
s
follows: co
nstruct the intersection o
peration
of the extensi
on an
d the combinatio
n o
peratio
n of th
e co
nnotation
for every two
node
s, and t
h
e
results a
r
e ta
ken a
s
the e
x
tension a
n
d
the
conn
otation of the ne
wly gene
rate
d node fo
r k+1
layer; for a n
e
w
gene
rate
d no
de, we d
o
the
pru
n
ing
ope
ration
a
c
cording
to Property 3
~
5
a
n
d
mark the no
n
-
co
ncept no
d
e
s a
s
provisi
onal
no
de
s C*; and for ea
ch ne
wly gen
erated
node,
we
con
n
e
c
t the new g
ene
rat
ed nod
es to t
he upp
er
con
c
ept p
a
re
nt n
ode
s to gen
e
r
ate the p
a
re
nt-
child
rel
a
tionship, in thi
s
ste
p
, if the pa
ren
t
node
i
s
a
te
mporary n
o
d
e
, we
co
ntinu
e
to loo
k
fo
r t
he
pare
n
t con
c
e
p
t of conce
p
t nodes a
nd d
o
the conn
ect
i
ons; after ge
neratin
g all the node
s in k+1
layer, we del
ete all tempo
r
ary no
de in k layer to fre
e
the spa
c
e
up, until finish gene
rating
k+1
layer a
nd e
s
t
ablish a fath
e
r
an
d son
co
nne
ction b
e
twee
n no
de
s.
Rep
eat the
a
bove ste
p
s u
n
til it
doe
s not to
b
u
ild a
ne
w la
yer, the
com
p
lete
con
c
ept
lattice i
s
g
e
n
e
rated,
at the
sam
e
time, t
he
method
s of
seeki
ng the
pa
rent-chil
d
rel
a
tionshi
p of
co
nce
p
t nod
es
up to laye
r by
layer, such that
this algo
rithm
can ge
nerate
the Hasse
di
agra
m
of inter-laye
r
co
nne
ction.
3.2. LCLG Al
gorithm
Input
: A formal context K
Outpu
t
: A co
rre
sp
ondi
ng
Ha
sse diag
ra
m of the con
c
ept lattice L
Step 1
: Let formal co
ntext K be chang
e
d
into trans
action matrix T’, s
o
rt in a desc
e
nding
orde
r a
c
cordi
ng to r(m)=n,
and g
ene
rat
e
matrix T(th
e ro
ws
den
ote tran
sa
ction
records, a
nd
the
c
o
lumns
denote attributes)
，
and let maximum eleme
n
t
C
ma
x
=(G,
)
；
Step 2
: Ge
n
e
rate
all th
e
node
s i
n
L
k=0
layer
：∈
for eac
h
attribute
m
M
, to generate the
node
s C
m
=(g
(
m),m
), dire
ct
ly marked a
s
provisi
onal
n
ode
s C
m
*
，
th
e
provi
s
ion
a
l node
s C
m
*
a
nd
C
max
are com
posed of L
k=0
layer
；
Step 3
: Gen
e
rate all the
node
s in L
k=1
layer after the ope
ration
s of the nod
es in L
k=0
layer: do th
e
pairwise op
erations
betwe
en the
co
nce
p
t node
s
(not
e that the o
n
l
y
con
c
ept
no
de
in k=0 layer i
s
C
max
) and
other provisio
nal n
ode
s i
n
k=0 la
ye
r. T
h
e op
erations
are
a
s
follo
ws:
con
s
tru
c
t th
e
interse
c
tion
ope
ratio
n
of
the
extensi
on a
n
d
the
combi
nation
operation
of the
con
notation f
o
r every two
node
s, and th
e re
sults
ar
e t
a
ke
n as th
e e
x
tension a
nd
the con
notati
o
n
of the newly
gene
rated
no
de for the
ne
xt layer;
for a new g
ene
rat
ed nod
e at e
a
ch
ope
ration
, we
do the prunin
g
operation
s
and del
et
e the repe
at nod
es an
d the containe
d nod
es in the p
r
o
c
e
s
s
of com
b
inati
on; mark th
e non
-con
ce
pt node
s
as provi
s
ion
a
l
node
s
C*; a
nd con
s
tru
c
t
the
con
n
e
c
tion
s f
o
r th
e n
ode
s to C
max
; to judge
the
ne
wly ge
nerate
d
no
de
s in
L
k=1
layer
whe
t
her
there
exists
a no
de
C’
an
d if it satisfie
s |C
’.Extent|=|G|, if it exists, then
del
ete C
max
and the
con
n
e
c
tion
s, and let C’ b
e
a maximum
element, del
e
t
e all the pro
v
isional n
ode
s and
releva
nt
con
n
e
c
tion
s in k=0 layer, the k=1 layer i
s
co
mpleted.
Step 4
: Conti
nue to ge
ne
rate all the no
des i
n
k=k+1
layer
：
do th
e pairwi
s
e op
eration
s
for the con
c
e
p
t node
s in
k=k+1 l
a
yer o
r
betwe
en the
con
c
e
p
t nod
es a
nd the
provision
a
l nod
es
in curre
n
t layer to gene
rat
e
the extensi
on and t
he connotatio
n of the node
s
in k+1 laye
r; at the
same
time, fo
r a n
e
w gen
erated no
de
we
do the
prunin
g
ope
ratio
n
s
and d
e
lete th
e re
peat n
o
d
e
s
and th
e cont
ained
nod
es
in the p
r
o
c
e
s
s of
com
b
in
a
t
ion; mark th
e non
-con
ce
pt nod
es
or the
node
s
with th
e cardi
nality
of the
con
not
ations |C
.Inte
nt|>k+1
as provision
a
l no
d
e
s;
we
co
nne
ct
the ne
w
gen
erated
no
de
s to the
up
pe
r
con
c
e
p
t pa
rent
node
s to ge
nerate t
he p
a
re
nt-chi
ld
Evaluation Warning : The document was created with Spire.PDF for Python.
TEL
K
4480
relati
o
for t
h
the n
until
t
gene
3.3. I
D as
Exa
m
Input
Outp
u
orde
r
gene
{C
01
*
=
the p
layer
cur
r
e
com
b
each
the
n
provi
s
follo
w
(8,e)
}
the r
e
K
OM
NIKA
V
o
n
s
hi
p, i
n
t
h
h
e pare
n
t
no
od
es
in
k
+
1
t
he k+1 laye
r
Step 5
:
k
Step 6
:
R
rate mini
mu
m
Step 7
:
O
nstanc
e
of
V
The fo
rm
sho
w
n i
n
T
a
m
ple:
: the formal
c
u
t: the corre
s
Step 1:
L
r
acco
rdi
ng
t
rate C*
=(g
(
=
(12
345
678
rovisi
on
al n
o
Step 2:
G
as
follows
:
e
nt layer L
k
=
b
i
nation ope
r
ne
w
l
y ge
n
e
r
n
ode wh
eth
e
s
i
onal no
d
w
s:
{C
11
=(12
3
}
, be
cau
s
e
C
e
levant conn
ol. 11, No
. 8
h
is step, if th
de of con
c
e
layer, del
e
t
e
r
is
compl
e
t
e
k
=k
+
1
;
R
ep
e
a
t Step
m
eleme
n
t a
O
utp
u
t the c
o
V
erificati
on
al context
K
a
ble 1, the
fi
x
c
ontext K sh
s
pon
ding H
a
L
et formal
c
o
t
o r(
m)=
n
,
a
(
m)
,m
)
,
w
e
,a),
C
02
*=(24
5
o
de
s C
m
* an
d
Figur
e
G
en
erate
all
for the
con
=
0,
construct
r
ation of the
r
ated nod
e,
w
e
r is
con
c
e
d
es
. In t
h
3
4
5678,
a),
C
C
11
sat
i
sf
i
e
s
|
ec
tions
in L
k
, August 20
1
e p
a
re
nt n
o
d
pt nod
es i
n
e
all the pro
v
e
d and the
p
a
4-5, until
it
nd co
nstruc
t
o
rre
s
p
ondin
g
is determin
e
x
ed number
o
Table
a
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
o
w
n in Ta
bl
e
a
sse diag
ra
m
o
ntext
K be
a
nd
ge
ne
rat
e
c
a
n
get
5
67
,b
)
,
C
03
*=
d
C
max
are c
o
e
1. The
Tra
n
th
e node
s
cept no
de
s
the inters
e
co
nnotatio
n
w
e
do
the
p
r
pt nod
e a
f
t
h
is step,
12
*=(2456
7
,
b
|
g(a)|
=
|G|, t
h
k
=0
layer.
1
3: 4477 –
4
d
e i
n
k laye
r
k-1 lay
e
r a
n
v
isional nod
e
a
re
nt-child c
o
doe
s not
t
o
t
the parent-
c
g
Ha
sse
diag
e
d by
the fr
o
o
f attributes
1. Fo
rmal
C
b c d
0 1
1
1 1
1
0 1
0
1 0
0
1 0
0
1 1
0
1 0
1
0 1
1
e
1
m
of con
c
ept
chang
ed int
o
e
matrix
T
；
D
the set
(1
236
8,c),
C
o
mp
osed of
t
n
sa
ct
ion Ma
t
in
L
k=1
laye
r
C
max
and o
t
e
ction op
er
a
m, and
r
uni
ng ope
r
a
er prunin
g
,
the set
b
), C
13
*=(12
3
h
us C
max
=C
1
1
4
483
r
is
a te
m
p
o
r
n
d do the co
e
s and
the
r
o
nne
ction
s
a
o
ge
nerate
a
c
hild co
nne
c
t
ra
m of the c
o
o
nt eigh
t
thin
g
is
6
.
C
ontext
e
f
0
1
0
1
0
0
0
0
0
0
0
0
0
1
1
0
lattic
e
L.
o
transac
t
io
n
D
=8;C
max
=(1
o
f the ge
n
C
04
*= (127
8,
d
t
he node
s in
t
rix
T after O
r
after the o
p
t
her temp
or
a
a
tion of the
ge
nerate
n
e
tion a
c
cordi
n
the non-co
of the
g
3
68,c), C
14
*
=
1
; and delet
e
e
-
r
ary no
de,
w
nne
ction
s
;
a
r
ele
v
a
n
t co
n
n
a
re
c
o
ns
tr
uc
t
a
ne
w
no
d
e
t
ions
.
o
nc
ept lattic
e
g
s
in the tra
n
n
mat
r
ix, so
r
2
3456
78,
)
n
erated
n
o
d
), C
05
*=
(
1
2
L
k=0
layer.
r
de
ring
p
er
a
t
io
ns
o
f
a
ry
nod
e
s
C
extension
G
e
w n
o
de
s in
n
g to P
r
op
er
t
nce
p
t node
s
g
ene
rated
=
(127
8,d), C
e
all the pro
v
-
ISSN: 2087
e
co
ntinue
t
o
a
fter gen
erat
n
ec
tio
n
s
in
k
t
ed
.
in L
K
lay
e
r
e
L.
n
sa
ct
ion d
a
t
a
r
t in a de
sc
e
)
; For each
o
de
s a
s
f
o
2
7,f), C
06
*=
the nod
es
i
C
*
=
(g
(m
),m)
G
g(m
)
a
n
L
k=1
layer,
a
t
y 3~5;
an
d
s
are mark
e
node
s ar
e
15
*=
(127,f),
v
i
s
ional no
d
e
-278X
o
l
ook
ing a
l
l
k
layer
, then
a
ba
se
e
ndi
ng
m
∈
M,
o
ll
ows:
(8,e)};
n L
k=0
in the
n
d the
a
nd fo
r
ju
dge
e
d a
s
e
as
C
16
*=
e
s a
n
d
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
e-ISSN:
2087
-278X
An Algorithm
on Gen
e
ratin
g
Lattice ba
sed on La
ye
re
d Con
c
e
p
t La
ttice (Zha
ng
Cha
ng-sh
eng
)
4481
Step 3: G
e
n
e
rate
all th
e
node
s i
n
L
k=2
layer after the o
p
e
r
ation
s
of
the
nod
es i
n
L
k=1
layer
as follo
ws: f
r
om
the
uniqu
e
con
c
e
p
t nod
e
and
other provisio
nal n
ode
s i
n
L
k=1
layer, we
can
get that {
C
21
=(2
4567,a
b
),
C
22
=(123
68
,ac), C
23
= (1278,a
d
),
C
24
*= (1
27,af),
C
25
*= (8,a
e)}.
Becau
s
e it d
oes n
o
t need
to prune no
d
e
s in this
ste
p
, con
s
tru
c
t the parent-chil
d
con
n
e
c
tion
s to
C
11
; and delet
e all the provi
s
ion
a
l node
s
and the rel
e
vant con
n
e
c
tio
n
s in k=1
la
ye
r
.
Step 4: G
e
n
e
rate
all th
e
node
s i
n
L
k=3
layer after the o
p
e
r
ation
s
of
the
nod
es i
n
L
k=2
layer as
follows
: from the
c
o
nc
ept nodes
in L
k=2
laye
r and
othe
r concept no
de
s or p
r
ovisi
o
n
a
l
node
s, we
ca
n get the
set of the no
de
s
and the
pa
re
nt-chil
d
con
n
e
ction
s
, whe
r
e the
set of t
h
e
gene
rated
no
des a
r
e a
s
f
o
llows: {C
31
=(26,ab
c),C
32
*
=
(2
7,abd
), C
33
*= (2
7,abf),
C
34
= (128,a
c
d)
,
C
35
*=
(12,ac
f), C
36
*= (8,a
ce),
C
37
=
(
127
,a
d
f
)
,
C
38
*= (8,ade
)}; a
c
cording to th
e pro
pertie
s
,
we
combi
ne C
32
* and
C
33
* be
C
32
*=(27,ab
df), thoug
h C
32
* is a
con
c
ep
t node,
while
|C
32
*.Intent|>3,
thus it i
s
not t
he con
c
ept n
ode in
cu
rren
t layer
，
the m
a
rk it as provision
a
l no
de;
Similarly, C
36
*=
(8,acde
)
; finally, the set of the nodes in L
k=2
layer is {C
31
=(26,ab
c),C
32
*
=
(27,ab
df), C
34
=
(128,a
c
d
)
, C
35
*= (1
2,acf),
C
36
*=
(8,acde), C
37
= (127,
adf)}
；
a
nd d
e
l
ete all the provision
a
l nod
es
and the rel
e
vant con
n
e
c
tio
n
s in k=2
la
ye
r
.
Step 5: G
e
n
e
rate
all th
e
node
s i
n
L
k=4
layer after the o
p
e
r
ation
s
of
the
nod
es i
n
L
k=3
layer as follo
ws. From the
con
c
ept no
d
e
s in L
k=3
layer and
other
con
c
e
p
t node
s or p
r
ovisi
o
n
a
l
node
s, we
ca
n get the
set of the no
de
s
and the
pa
re
nt-chil
d
con
n
e
ction
s
, whe
r
e the
set of t
h
e
gene
rated
no
des
are a
s
follows: {
C
41
=(12,a
c
df),
C
42
=
(
8
,
ac
de
)
,
C
43
= (2
7,abdf),
C
44
*= (2,ab
c
df)};
delete all the
provisi
onal n
ode
s and the
relevant con
nectio
n
s in
k=3
layer.In this
s
t
ep, from the
c
o
nc
ep
t n
o
de C
37
=(127,a
d
f) and th
e p
r
o
v
isional
node
C
32
*=(27,ab
d
f
)*, we g
ene
rate the con
c
e
p
t
node C
43
= (2
7,abdf), wh
en
C
43
is conn
e
c
ted with two pare
n
t node
s,
we find that the parent no
de
C
32
* is a
pro
v
isional
nod
e
,
then
contin
ue to fi
n
d
th
e pa
rent
co
n
c
ept
nod
e from the
abov
e
layer
，
C
21
=(2
4567,a
b
) is
constructe
d the pare
n
t-child
conn
ectio
n
s,
which is sho
w
n a
s
Figu
re
2.
Step 6: G
e
n
e
rate
all th
e
node
s i
n
L
k=5
layer after the o
p
e
r
ation
s
of
the
nod
es i
n
L
k=4
layer as follo
ws. From the
con
c
ept no
d
e
s in L
k=4
layer and
other
con
c
e
p
t node
s or p
r
ovisi
o
n
a
l
node
s, we
ca
n get that {
C
51
= (2,ab
c
df
)}
; and d
e
lete
all the p
r
ovisi
onal n
ode
s a
nd the
releva
nt
con
n
e
c
t
i
on
s in k=
4
layer.
Step 7: Beca
use it is im
po
ssi
ble to ge
n
e
rate the
nod
es for th
e ne
xt layer from
the L
k=5
layer, thus th
e pro
c
e
ss
of gene
rating lat
t
ice is
compl
e
ted, con
s
tru
c
t
the minimum
element C
min
=(
, abcdef
), and
con
s
tru
c
t the
conn
ectio
n
s;
Step 8: Output the corre
s
p
ondin
g
Ha
sse
diagra
m
of the con
c
e
p
t lattice L.
The co
rrespo
nding
Ha
sse diagram
of the obtaine
d co
nce
p
t lattice is sh
own in Figure 3.
Figure 2. Find the Upp
e
r
Parent Con
c
e
p
t
Nod
e
s
Figure 3. The
Corre
s
po
ndi
ng Ha
sse Di
a
g
ram
of the Conc
ept Lattic
e
L
4. Experimental An
aly
s
is
To test th
e p
e
rform
a
n
c
e
o
f
the propo
se
d algo
rithm, we do
th
ree grou
ps
expe
ri
ments
to
make a
co
mparative analysi
s
for the algo
ri
thm
s
Bord
at an
d LCL
G
. The experim
en
tal
environ
ment i
s
a Pc
machi
ne of a
Wind
ows Serve
r
2
003 o
perating
system, I7 2.
0G 64
-bit qu
a
d
-
core ei
ght lin
es
with th
e p
r
ocesso
r, 4
G
memo
ry, an
d the
pro
g
ra
m ru
ns on
th
e environm
e
n
t of
JAVA SDK1.4.2. In this
experiment, we use
“attribute-attribut
e
wi
th no relevance probability” to
descri
be the relevan
c
y extent betwee
n
attributes a
nd a
ttributes.
Evaluation Warning : The document was created with Spire.PDF for Python.
e-ISSN: 2
087-278X
TELKOM
NIKA
Vol. 11, No
. 8, August 2013: 4477 –
4483
4482
The first exp
e
rime
nt: set
10 formal
co
ntexts
，
the n
u
mbe
r
s of att
r
ibute
s
a
nd
o
b
ject
s a
r
e
both fixed as
20, the attribute-attribute
wi
th no
relevance probability increases from 40% to 85%,
the re
sults
are sh
own in
Figure 4.
We
can fin
d
tha
t
the attribut
e-attrib
ute wi
th no rel
e
van
c
e
prob
ability ha
s n
o
im
pa
ct o
n
Bordat th
ro
ugh
expe
ri
me
ntal comp
ari
s
ons, i
n
co
ntra
st to Alg
o
rith
m
LCL
G
; the runnin
g
effici
ency ha
s o
b
v
ious adva
n
tage
s wh
en t
he attribute
-
attribute with
no
relevance probability is low.
The
se
con
d
e
x
perime
n
t: se
t 10 form
al
co
ntexts
, the att
r
ibute
-
attribut
e with
no
rele
vance
probability is
fixed as 80%
, the nu
mbers of
objects i
s
fixed
as 20
in each formal
context,
the
numbe
rs of attributes in
cre
a
se
s from 5
grad
ually
to 50, and the result
s are sh
own in Fi
gure 4.
From the t
r
en
d of the figure, whe
n
the n
u
mbe
r
s
of
attribute
s
is m
o
re than 25, th
e time increa
se
s
quickly for Algorithm Bo
rd
at
，
while the t
i
me slo
w
s fo
r Algorithm L
C
LG.
The third
exp
e
rime
nt: set 10 formal
co
ntexts
, the attribute-attribu
t
e with no rel
e
vance
probability is fixed as 80%
, the numbers of attribut
es is fixed as
20 in each formal context, the
numbe
rs of object
s
increa
se
s from 5 g
r
adually to
50,
and the re
su
lts are
sho
w
n
in Figure 6.
We
can
find th
at Algorithm
LCLG
ke
ep
stable
advantag
es in
contrast to Algorit
hm
Bordat
，
e
s
p
e
c
ially as th
e i
n
crea
se of th
e numb
e
rs of
object
s
, the runnin
g
sp
eed
has
rema
rka
b
le
advantag
es. From
the exp
e
rime
nts,
we
kno
w
that Algorithm L
C
L
G
gre
a
tly red
u
ce
s the imp
a
ct
on the
in
cre
a
se
of attri
b
utes
and
obj
ect affe
cted
to the time
compl
e
xity of the al
gorith
m
.
Comp
ared wi
th
Algorithm Bordat,
it
is more ada
pte
d
to the mo
re
obje
c
ts in th
e formal
co
ntext,
and
wh
en t
h
e attrib
ute-att
r
ibute
with
n
o
relevan
c
e
prob
ability is low,
the
ad
vantage
s of
this
algorith
m
is relatively more appa
rent.
0
1
2
3
4
5
6
40
45
50
55
60
6
5
7
0
75
80
85
a
t
t
r
i
but
e
-
a
t
t
r
i
but
e
no
a
s
s
o
c
i
a
t
e
d
pr
oba
bi
l
i
t
y
/
%
r
unni
ng t
i
m
e
/
s
Bor
dat
LCL
G
Figure 4. The
Trend of the
Efficiency of the
Algorithm wit
h
the Increase of attribute-
attribute with
No Relevance Probability
0
10
20
30
40
5
1
01
52
0
2
53
03
5
4
0
4
55
0
N
o
.
o
f
a
ttr
i
b
u
t
e
runni
ng t
i
m
e
/
s
B
orda
t
L
CLG
Figure 5. The
Trend of the
Efficiency of the
Algorithm wit
h
the Increase of Attributes
0
10
20
30
40
5
1
01
5
2
02
53
03
5
4
0
4
5
5
0
N
o
.
o
f
obj
e
c
t
r
u
nn
i
n
g t
i
e
m
/
s
Bo
rdat
LC
LG
Figure 6. The
Trend of the
Efficiency of the
Algorithm
with the Incre
a
se of Obj
e
ct
s
5. Conclusio
n
In this pap
er,
the algorith
m
LCL
G
on
gene
rating l
a
ttice in batch
pro
c
e
ssi
ng
based on
layered
con
c
ept lattice
i
s
develop
ed. T
he n
ode
s
l
a
yered
in
the
concept lattice
are int
r
odu
ced,
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
e-ISSN:
2087
-278X
An Algorithm
on Gen
e
ratin
g
Lattice ba
sed on La
ye
re
d Con
c
e
p
t La
ttice (Zha
ng
Cha
ng-sh
eng
)
4483
the lattice i
s
gene
rated
by widt
h-pri
o
r
method, do t
he pai
rwi
s
e
o
peratio
ns
bet
wee
n
the
con
c
ept
node
s in
ea
ch layer
or th
e
con
c
e
p
t nod
es a
nd the
provision
a
l no
d
e
s to
gene
rat
e
the no
de
s i
n
next layer, an
d do the prun
ing ope
ration
s dynami
c
ally
to delete so
me unne
ce
ssary node
s, su
ch
that the
gen
e
r
ating
speed
is im
prove
d
greatly,
the
concept n
ode
s are
con
s
tructed the
pa
ren
t
-
child
con
n
e
c
tions u
p
ward
layer by layer, then
the Hasse dia
g
ra
m of inter-lay
er conne
ctio
n is
gene
rated.
From the
comp
arative a
naly
s
is with
Al
go
rithm Bordat i
n
the
expe
ri
ments,
we
kn
ow
that Algorith
m
LCLG
grea
tly redu
ce
s th
e impa
ct o
n
t
he in
crea
se
o
f
attribute
s
a
n
d
obj
ect
affected
to the time
complexity of
the alg
o
rithm
.
And it
i
s
m
o
re
ada
pted
to the
situati
on that th
e
more
objects are i
n
the form
al
context, when the attr
ibut
e-attribute wi
th no rel
e
vance probability is
low, the adva
n
tage
s of Algorithm L
C
LG
is relatively m
o
re ap
pa
rent.
Ackn
o
w
l
e
dg
ements
This
work
wa
s su
ppo
rted i
n
part by the
National
Nat
u
ral Sci
e
n
c
e
Found
ation o
f
China
(No.6
087
502
9, No.61
175
0
48); Th
e Proj
ect of Beijing
Key Labo
rato
ry of Knowl
e
d
ge Engin
e
e
r
i
n
g
for Material
s
Scien
c
e
(
No.Z1211
0100
281
2005
).
Referen
ces
[1]
Bordat JP. Ca
l
c
ul prati
q
u
e
du
tr
eillis
de Gal
o
is d'un
e corres
pon
de
nce.
Mat
c
h. Sci. Hu
m.
199
6; 96: 3
1
-
47.
[2]
Ho T
B
. An approach to
c
onc
e
p
t
formatio
n
ba
sed on
formal
conce
p
t
a
nal
ys
is.
IEICE Trans Inform
atio
n
and Syste
m
s
. 199
5; 78(5): 55
3-55
9.
[3]
M Chein. Alg
o
r
i
thm de rech
er
che des so
us-
m
atrices premi
e
res du
ne matr
ices.
Bull. Math. Soc. Sci. R
.
S. Roma
in
e
. 1996; 13(
61): 21
-25.
[4]
Ganter RE. Bow
m
an
C M.
D
i
g
ital
Li
brari
e
s,
Conc
eptu
a
l K
n
ow
l
edg
e Syste
m
s
an
d the
N
e
bul
a Interfac
e
.
Univers
i
t
y
of Arkansas. 19
95;
125-
131.
[5] Nouri
n
e
L,
Ra
ynau
d.
A fast
al
gorith
m
for b
u
i
l
d
in
g l
a
ttices
. W
o
rkshop
on
Comp
utation
a
l
Graph
T
heor
y
and C
o
mbi
nato
r
ics(CGT
C
). Victoria. Can
a
d
a
. 1999; 7
6
-84.
[6]
R Godin, R Missao
u
i. Incrementa
l
conc
ept
formation
for learnin
g
from Databas
es.
T
heoretic
a
l
Co
mp
uter Scie
nce
. 199
4; (13
3
): 387-4
19.
[7]
Z
h
i Hui-l
a
i, Z
h
i Do
ng-j
i
e, Li
u Z
ong-tia
n
. T
heor
y
an
d A
l
gorit
hm of Conce
p
t Lattice
Unio
n.
Acta
Electron
ica Sin
i
ca
. 201
0; 38(2
)
: 455-45
9.
[8]
Shen J
i
n-b
i
a
o
, Liu Y
ue-j
i
n. A
nove
l
bu
ild
in
g
alg
o
rithm of co
ncept l
a
ttice.
Journ
a
l of H
e
fei
Univers
i
ty of
T
e
chno
logy (N
atural Sci
ence)
. 2010; 33(
2):3
01-3
07.
[9]
Gu Ch
un-sh
en
g. F
u
ll
y
Homo
morphic
Encr
yp
tion, A
ppro
x
i
m
ate L
a
ttice Pr
obl
em a
nd
LW
E.
Internatio
na
l
Journ
a
l of Clo
u
d
Co
mp
uting
a
nd Servic
es Scienc
e
. 201
3; 2(1): 1-15.
[10]
Qu W
en-j
i
an,
T
an Guang-
xin
g
, Qiu T
ao-ro
n
g
. Ne
w
Al
gor
ithm of Ge
ner
ating
Co
nce
p
t L
a
ttice Us
in
g
Univers
a
l Matri
x
. J
our
nal of C
h
in
ese Co
mput
er Systems
. 20
12; 33(3): 5
58-
564.
[11]
W
ang Hu
i, W
ang Jin
g
. Non-r
edu
nd
ant asso
ciatio
n rules e
x
tractio
n
of freque
nt conce
p
t lattice bas
e
d
on F
P
-tree.
Co
mp
uter Eng
i
n
e
e
rin
g
and A
ppl
i
c
ations
. 20
12;
48(1
5
): 12-1
4
.
[12]
Che
n
Xia
ng, W
u
Yue.
Asso
ci
atio
n Ru
le M
i
nin
g
Al
gorithm
Based
on Ba
se Set an
d Co
ncept L
a
ttice
.
Co
mp
uter Engi
neer
ing
. 2
010;
36(1
9
): 34-3
6
.
[13]
Yang
Kai, J
i
n
Yong-
lon
g
, H
e
Z
h
i-jun, M
a
Y
u
an. An
Appr
oa
ch for Bri
e
fest
Rules
E
x
tractio
n
Bas
ed O
n
Comp
act De
p
end
enci
e
s.
T
E
LKOMNIKA In
don
esia
n J
our
nal
of El
ectric
al E
ngi
ne
erin
g
. 201
3; 11(
2):
941-
947.
[14]
Hu
Xue-Gan
g
,
Ch
en
Hui, M
a
F
eng.
T
h
e Mi
nin
g
of
Cl
assifi
cation
Ru
les
B
a
sed
on
Mu
ltip
le Exte
nd
ed
Conc
ept Lattic
e
s
. Procee
din
g
s of the F
o
u
r
th Internati
o
n
a
l Co
nfere
n
ce
on Mach
ine
Lear
nin
g
an
d
C
y
ber
netics(M
L
C). Guangz
ho
u.
Chin
a. 200
5; 2063-
20
66.
[15]
Z
hao
Xu-
j
un,
Z
hang J
i
-fu, Ma Yan
g
, Cai J
i
ang-
hui.
N
o
ve
l
Classific
a
tio
n
Rule Acqu
isitio
n
Alg
o
rithm.
Journ
a
l of Chi
n
ese Co
mputer
Systems
. 20
12
; 33(5): 112
6-1
130.
[16]
Lv Yu
e-ji
n, Li
u
Hon
g
-me
i. Improve
d
a
l
g
o
rith
m for attribut
e
red
u
ction
o
n
conce
p
t lattice
.
Co
mp
uter
Engi
neer
in
g an
d Appl
icatio
ns
. 201
1; 47(8): 14
6-14
8.
[17]
W
ang De-
x
i
ng,
Hu Xu
e-g
ang,
W
ang Ha
o. Alg
o
rithm
of minin
g
associ
ation r
u
les b
a
sed o
n
Quantitativ
e
Conc
ept Lattic
e
.
Journa
l of Hefei Un
iversity
of T
e
chnol
ogy
(Natural Sc
ien
c
e). 2002; 2
5
(5
): 678-68
2.
Evaluation Warning : The document was created with Spire.PDF for Python.