The ascending part of recursivity contributes to the
production of concepts (nodes) while the descending part handles the partial order
in the resulting lattice. Function put(n') returns the node of the input lattice that
corresponds to node n' in the output lattice. Function get(n) conducts the opposite
operation by returning the node in the output lattice that corresponds to node n. The
function parent_pruning consists to check itemset inclusion to avoid the exploration
of useless parent nodes in the lattice.
Algorithm 1: Projection
Input:.Node n, P: a set of attributes
Output:.Node n'
if n is already processed then
. return get(n)
Successors ?†? ??… /* keep track of the successors of a given node */
i1 ?†? intent(n) ??© P
Parents ?†? sort(Parents(n)) /* in a decreasing order of |intent(p) ??© i1| where p ??? Parents */
for.each non visited parent p of Parents do
i2 ?†? intent(p) ??© i1
. if i2 ?‰ ??… and i1 ?‰ i2 then
Successors ?†? Successors ??? Projection(p, P)
else if i1 = i2 then
Projection(p, P)
Mark n as a processed node
n' ?†? (extent(n), i2)
Link n' to Successors
Return n'
2 0 Missaoui, Jatteau, Boujenoui, & Naouali
Copyright ?© 2007, Idea Group Inc. Copying or distributing in print or electronic forms without written permission of
Idea Group Inc. is prohibited.
Table 3 provides the trace of the projection algorithm applied to lattice L (depicted
in Figure 1) and shows that the infimum of the output lattice is rapidly reached and
the resulting lattice is quickly formed using heuristics for selecting the successors
(parents) to explore.
Pages:
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501