THE LUCS-KDD TFP (TOTAL FROM PARTIAL) ASSOCIATION RULE MINING ALGORITHM

1. INTRODUCTION

2. DOWNLOADING THE SOFTWARE

3. RUNNING THE SOFTWARE

4. MORE DETAIL ON APPLICATION CLASSES

5. THE P-TREE DATA STRUCTURE

A P-tree is a set enumeration tree structure in which to store partial counts for item sets. The top, single attribute, level comprises an array of references to structures of the form shown to the right, one for each column.

Each of these top level structures is then the root of a sub-tree of the overall P-tree. The nodes in each of these sub-tress are represented as structures of the form:

Assuming a sample data set as shown below:

where D=6 (number of columns/attributes) and N=3 (number of records). Prior to commencement of the generation process the P-tree will comprise a 6 element array as shown in Figure 1(a). The first row will be stored in the P-tree as shown in Figure 1(b).

(a): Prior to start

(b): Addition of first row ({1, 3, 4}).

(c): Addition of second row ({1, 4, 5}).

(d): Addition of third row ({2, 4, 6}).

Figure 1: P-tree Generation

Note the support for the parent node is incremented by one. The second row is then included as shown in Figure 1(c), and the third as shown in Figure 20(d). Note that because this last row shares a common leading substring with an existing node in the P-tree a dummy node is created to ensure that the tree does not become "flat".

Inspection of the final P-tree as shown in Figure 2(d) indicates that nothing is lost if we do not store that part of any particular "node code" which is duplicated in the parent code (Figure 2).

Figure 2: P-tree in its final form.

The internal representation of the P-tree presented in Figure 2 is then as shown in Figure 3.

Figure 3: Internal representation of P-tree presented in Figure 2.

On completion of the generation process the P-tree itself is "thrown away" and the contents of the tree stored in a P-tree table --- an array of arrays each element of which is a pointer to a structure of the form:

The node code is the set of column numbers represented by any individual node (not the complete itemset represented by the node). The parent code is the union of all the node codes of the current node's "ancestor nodes" (parent node, grandparent node, etc.). The union of the parent code and the node code for any individual node is the itemset represented by the node. The first index of the array represents the size of the union of the parent and node codes in that array of the array of arrays, i.e. the size (cardinality) of the itemset represented by the node. Thus all singletons are stored at index 1, doubles at index 2 and so on.

The advantages offered by the P-tree table are:

1. Reduced storage requirements (particularly where the data set contained duplicate rows).
2. Faster run times because the desired total support counts had already been partially calculated.

Internally the P-tree presented in Figure 3 will be stored in tabular form as shown in Figure 4.

Figure 4: P-tree table.

6. THE TFP ALGORITHM

The TFP algorithm is used to determine ARs by first creating a T-tree from the P-tree. This process can best be explained by considering the P-tree table given in Figure 4. The T-tree is generated in an Apriori manner. There are a number of features of the P-tree Table that enhance the efficiency of this process:

1. The first pass of the P-tree will be to calculate supports for singletons and thus the entire P-tree must be traversed. However, on the second pass when calculating the support for "doubles" we can ignore the top level in the P tree, i.e. we can start processing from index 2. Further, at the end of the previous pass we can delete the top level (cardinality = 1) part of the table. Consequently as the T-tree grows in size the P-tree table shrinks.

2. To prevent double counting, on the first pass of the P-tree, we update only those elements in the top level array of the T-tree that correspond to the column numbers in node codes (not parent codes). On the second pass, for each P-tree table record found, we consider only those branches in the T-tree that emanate from a top level element corresponding to a column number represented by the node code (not the parent code). Once the appropriate branch has been located we proceed down to level 2 and update those elements that correspond to the column numbers in the union of the parent and node codes. We then repeat this process for all subsequent levels until there are no more levels in the T-tree to consider.

Thus returning to the P-tree table presented in Figure 4 we proceed as follows:

1. Commence with an empty top-level T-tree Figure 5(a).

2. Pass through the P-tree table level by level, starting with level 1, updating the top-level of the T-tree according to the nature of each record in the P-tree table. Thus:
   1. The first record encountered represents the node {1}. and thus we update the support for element 1 of the top-level of the T-tree (Figure 5(b)).
   2. The second record in the P-tree table to be considered is the node {2} and consequently we update the support element 2 in the top-level of the T-tree (Figure 5(c)) --- note that the support for node {2} is 2.
   3. We now pass to the second level in the P-tree table (index 2) which represents doubles (set cardinality = 2). There is only one record at this level with parent code {2} and node code 4 (the record in its entirety represents the P-tree node {2,4}). The contribution of this node to element 2 (the parent code) in the T-tree has already been considered thus, as before, we only consider the node code and increment the support for element 4 in the T-tree (Figure 5(d)).
   4. We now pass down to the third level in the P-tree table. There are three nodes here. We only consider the node codes and thus first increment the supports for elements 3 and 4 in the T-tree (Figure 5(e), then element 5 (Figure 5(f)), and then element 6 (Figure 5(g)).
   We have now completed one pass of the P-tree and we can remove the singles from the P-tree table (Figure 6), prune the T-tree of those nodes that are not adequately supported (Figure 5(h)), and generate the next T-tree level (Figure 5(i)).

(a): Prior to start

(b): P-tree Table, Level 1, Node 1.

(c): P-tree Table, Level 1, Node 2.

(d): P-tree Table, Level 2, Node 1..

3. Continuing on to level two of the T-tree we commence with the cardinality 2 sets in the P-tree table:
   1. There is only one cardinality 2 node in the table, this has parent code {2} and node code {4}. Therefore we search the T-tree branch emanating from element 4 only (the node code), and do not consider the branch emanating from element 1 (the parent code). Thus we pass down branch 4 to the second level and attempt to update elements 4 and 2 (the union of the node and parent codes). However, there is no element 4 in this part of the T-tree so we only update the support associated with element 2 (Figure 7(a)).
   2. We then move to the cardinality 3 nodes in the P-tree Table. The first we encounter has a parent code of {1} and a node code of {3,4} thus we search only the T-tree branch emanating from elements 3 and 4. There is no element 3 so we only consider element 4 and pass down this branch to level 2 in the T-tree and update the elements {1,3,4} (the union of the node and parent P-tree codes) if they are present in this part of the T-tree (Figure 7(b)).
   3. We repeat this process for the other two nodes. The first of these has node code {5} which does not appear in the top level of the T-tree (as pruned so far) and consequently we can ignore this node. The same applies to the last level 3 P-tree Table node.

This completes the second pass of the P-tree table; we set the size 2 reference in the P-tree Table to null (Figure 8), prune the T-tree so far (Figure 7(c)), and generate the the third level on the T-tree (Figure 7(d)).

(a): P-tree Table, Level 2, Node 1.

(b): P-tree Table, Level 3, Node 1.

4. On subsequent level (level three and beyond) We now repeat the process starting with the cardinality 3 nodes in the P-tree table:
   1. The first node has node code {3,4} thus we search only those T-tree branches emanating from elements 3 and 4 in the T-tree --- there is no element 3 so we only consider element 4. We we get down to the right level (level 3) we update the elements {1,3,4} if present (Figure 9(a)),
   2. The second node has node code 5 which is not in the top level of the T-tree so can be ignored.
   3. The last node has node code 6 and this is also not in the T-tree.

This then completes the third pass of the P-tree table and consequently we prune level 3 of the T-tree (Figure 9(b)), and attempt to generate the next level in the the T-tree, however, in this case there are no more levels to generate and thus we have come to the end of the T-tree generation process (Figure 9(c)). The generation process is also ended because, after removing level 3 in the P-tree Table (Figure 10) there are no more nodes in the table to consider.

(a): P-tree Table, Level 3, Node 1.

7. CONCLUSIONS

REFERENCES