Biology Reference
In-Depth Information
That is, it will take
O
(
|
obj
(
XS
i
)
|
) time to check if
XS
i
is closed. The total time
it takes to check if all children are closed is
O
(
i
=1
|
obj
(
XS
i
)
|
).
Recall that a concept
C
=(
obj
(
X
)
,X
) is uniquely determined by its extent
obj
(
X
) or its intent
X
. Therefore, we can store either the object sets or the at-
tribute sets generated so far in a trie, and then test the existence of
C
by testing the
existence of
obj
(
X
) or
X
. Since searching the object sets are needed in testing
the closure of an attribute set as described above, the cost of testing the existence
obj
(
X
) comes for free.
Note that
a∈
obj(
X
)
|
nbr
(
a
)
>
i
=1
|
obj
(
XS
i
)
. Hence, the time
it takes to process a concept is dominated by the procedure S
PROUT
,in
O
(
a∈
obj(
X
)
|
nbr
(
a
)
|
|·|
S
i
|
|
) time.
If we can reduce the sizes of the adjacency lists
(
), we can reduce the running time of the algorithm. Note that this basic
algorithm is already as fast as any existing algorithm for constructing a concept
lattice (or computing all concepts only that takes
O
(∆
2
) time where ∆ is the
maximum size of adjacency lists).
In the following we describe how to dynamically update the adjacency lists
that will reduce the sizes of adjacent lists, and thus improve the running time of
the algorithm.
|
nbr
()
|
8.4.2.1.
Further Improvement: Dynamically Update Adjacency Lists
Consider a concept
C
=(
obj
(
X
)
,X
), the object sets of all descendants of
C
are
all subsets of
obj
(
X
). To compute the descendants of
C
,itsuffices to consider
the objects with restriction to
obj
(
X
).For
S
∈
AttrChild
(
X
),bydefinition, all
attributes in
S
have the same adjacency lists when restricting to
obj
(
X
).That
is, for all
i
=
j
∈
S
,
nbr
(
i
)
∩
obj
(
X
)=
nbr
(
j
)
∩
obj
(
X
)(=
obj
(
XS
)).In
other words, for all
a
S
,
i.e., the adjacent list of
a
either contains all elements in
S
or no element in
S
.
Therefore, we can reduce the sizes of adjacent lists of objects by representing
all attributes in
S
by a single element. For example in Fig. 8.2, we can use a
single element 16 to represent the two attributes 1 and 6,and35 to represent 3
and 5.
∈
obj
(
X
),
i
∈
nbr
(
a
)
⇔
j
∈
nbr
(
a
),forall
i,j
∈
In doing so, we reduce the size of adjacency list of
b
from 5 elements
{
1
,
3
,
4
,
5
,
6
}
{
16
,
35
,
4
}
. We call the reduced adjacency lists
the condensed adjacency lists. Denoted the condensed adjacent list by
cnbr
().
The set of condensed adjacency lists corresponds to a reduced cross-table. For
example, the reduced cross table of
Child
(
abcde,∅
) of the above example is shown
in Fig. 8.2.
In order to use the condensed adjacency lists in procedure S
PROUT
, we need
to process our concepts in BFS order and it requires one extra level, i.e. in a two-
to three elements
Search WWH ::
Custom Search