Efficiently Identifying Exploratory Rules’ Significance - Data Mining: Theory, Methodology, Techniques, and Applications - page 72

Fig. 2. The circular intersection approach flow for ABCDE

Fig. 3. The circular intersection approach for ABCDE when current is ABCD

do intersections from the last condition E back to the second one B ,whichis

referred to as the backward stage . During the backward stage, the of

each direct parent of the current rule is found. By introducing the circular inter-
section approach, the number of intersection operations required for identifying
the significance of current rule is reduced to only 10.

coverset

Complexity. Using the parallel intersection approach, the number of intersec-
tion operations for iterating through all the subsets is:

( n − 2) × n +1 ,

where is the maximum number of conditions on the rule antecedent. The

complexity is

n

2 ).
After introducing the circular intersection approach, the intersection opera-
tions for iterating through all the subsets are:

O ( n

3 n − 5 .

The complexity is ). However, practically the difference in running time will

notbesodramatic,sincewehaveintroduced the triviality filter, which enables
the pruning of the search space. Both the parallel intersection procedure and the
circular intersection procedure will probably stop at anytime when it is identified
that the current rule is a trivial rule.
The two approaches (the difference set statistics derivation approach and the
circular intersection approach) mentioned above can combine with each other
so as to achieve higher eciency. We can save one more intersection operation
by introducing the difference set statistics derivation technique in section 5.1.
Suppose that we are deciding whether the rule

O ( n

A & B & C & D & E → target is

significant or not. Now that the statistics of one of its parent A & B & C & D →

target )

once again. Hereby, one intersection operation can also be saved by following
the procedure shown in figure 3 according to lemma 1. The number of necessary
intersection operations is reduced to

is known, thus we don't have to derive the statistics of coverset ( ABCD

3 n − 6 .