apriorit.html

apriori algorithm using datasets implementation

2 4 (2)
2 5 (1)
2 6 (1)
3 4 (1)
</PRE>
</TD><TD><PRE> </PRE></TD><TD>
<PRE>
4 5 (1)
4 6 (1)
1 3 4 (1)
2 4 5 (1)
2 4 6 (1)
</PRE>
</TD></TABLE>
</CENTER>

<P>These can be presented in a T-tree of the form given in Figure 1 (note the
reverse nature of the tree).
The internal representation of this "reverse" T-tree founded on arrays of
T-tree nodes that can be
conceptualised as shown in Figure 2. The storage required for each node
(representing a frequent set) in the T-tree is then 12 Bytes:</P>

<OL>
<LI> Reference to T-tree node structure (4 Bytes)
<LI> Support count field in T-tree node structure (4 Bytes)
<LI> Reference to child array field in T-tree node structure (4 Bytes)
</OL>

<P>Thus house keeping requirements are still 8 Bytes, however storage gains
are obtained because it is not necessary  to explicitly store individual
attribute labels (i.e. column numbers representing instantiated elements) as
these are implied by the indexing. Of course this approach must also require
storage for "stubs" (4 Bytes) where nodes are missing (unsupported). Overall
the storage advantages for this technique is thus, in part, dependent on the
number of missing combinations contained in the data set.</P>

<BR>
<CENTER>
<IMG
	SRC = "reverseTtree.gif"
	BORDER = 0
	ALT = "REVERSE T-TREE">
<P><B>Figure 1</B>: <I>Conceptual example of the T-tree data structure</I></P>
</CENTER>
<CENTER>
<IMG
	SRC = "t-treeStruct3.gif"
	BORDER = 0
	ALT = "VERSION 3 OF T-TREE">
<P><B>Figure 2</B>: <I>Internal representation of T-tree presented in Figure 1</I></P>
</CENTER>
<br><hr><br>

<a NAME = "aprioriT">
<table BORDER-=0 WIDTH="100%" CELLPADDING=5 BGCOLOR="006699">
<tr><td><h2><font color =" white">6. THE APRIOR-T ALGORITHM</font></h2></td>
</table><BR>

<P>The T-tree described above is built in an apriori manner, as first proposed
by Agrawal and Srikant (1994), starting with
the one item sets and continuing until there are no more candidate N-itemsets.
Thus, at a high level, a standard apriori algorithm is used.</P>

<PRE>
K <-- 1
nextlevelFlag=true;

generate candidate K-itemsets
Loop
    count support values for candidate K-itemsets
    prune unsupported K-itemsets
    K <-- 2
    generate candidate K2 itemsets from previous level
    if no K2 itemsets break
end Loop
</PRE>

<P>In more detail the Apriori-T algorithm commences with a method
<TT>createTotalSupportTree</TT> which is presented
in Table 1. The method commences by generating the top level of the T-tree
(<TT>createTtreeTopLevel</TT>) and then generating the next level
(<TT>generateLevel2</TT>) from the  supported sets in level 1 --- remember that
if a 1-itemset is not supported none of its super sets will be supported.
Once we have generated level 2 further levels can be generated
(<TT>createTtreeLevelN</TT>).</P>

<CENTER>
<TABLE BORDER=1 CELLPADDING=5><TR><TD>
<ALIGN=LEFT><PRE>
Method: createTotalSupportTree
Arguments: none
Return: none
Fields: NA
------------------------------
createTtreeTopLevel()
generateLevel2()
createTtreeLevelN()
------------------------------
</PRE></ALIGN>
</TD></TABLE>
<P><B>Table 1</B>: <I>The</I> <TT>createTotalSupportTree</TT> <I>method</I></P>
</CENTER>

<P>The method to generate the top level of a T-tree is as presented in Table 2.
Note that the method includes a
call to a general T-tree utility method <TT>pruneLevelN</TT> described later.</P>

<CENTER>
<TABLE BORDER=1 CELLPADDING=5><TR><TD>
<ALIGN=LEFT><PRE>
Method: createTtreeTopLevel
Arguments: none
Return: none
Fields: D number of attributes
        startTtreeRef start of T-tree
	dataArray 2D array holding input sets
--------------------------------------
Dimension and initialise top level of T-tree (length = D)

Loop from i = 0 to i = number of records in dataArray
    Loop from j = 0 to j = number of attributes in dataArray[i]
    	startTtreeRef[i][j]++
    End loop
End Loop

pruneLevelN(startTtreeRef,1)
--------------------------------------
</PRE></ALIGN>
</TD></TABLE>
<P><B>Table 2</B>: <I>The</I> <TT>createTtreeTopLevel</TT> <I>method</I></P>
</CENTER>

<P>The <TT>generateLevel2</TT> methods loops through the top level of the
T-tree creating new T-tree arrays where appropriate (i.e. where the immediate
parent nodes is supported). The method is outlined in Table 3. Note that the
method includes a call to a general T-tree utility method <TT>generateNextLevel</TT>
(also described later).</P>

<CENTER>
<TABLE BORDER=1 CELLPADDING=5><TR><TD>
<ALIGN=LEFT><PRE>
Method: generateLevel2
Arguments: none
Return: none
Fields: startTtreeRef start of T-tree
	nextlevelFlag set to true if next level exists
--------------------------------------
nextlevelFlag <-- false

loop from i = 0 to i = number of nodes in T-tree top level
    if startTtreeRef[i] != null
    		generateNextLevel(startTtreeRef,i,{i})
End Loop
--------------------------------------
</PRE></ALIGN>
</TD></TABLE>
<P><B>Table 3</B>: <I>The</I> <TT>createTtreeTopLevel</TT> <I>method</I></P>
</CENTER>

<P>Once we have a top level T-tree and a set of candidate second levels
(arrays) we can proceed with generating the rest of the T-tree using an
iterative process --- the <TT>createTtreeLevelN</TT> method presented in Table
4. The <TT>createTtreeLevelN</TT> method calls a number of
other methods <TT>addSupportToTtreeLevelN</TT>, <TT>pruneLevelN</TT> (also
called by the <TT>createTtreeTopLevel</TT> method) and
<TT>generateLevelN</TT> which are
presented in Tables 5, 6 and 7 respectively.</P>

<CENTER>
<TABLE BORDER=1 CELLPADDING=5><TR><TD>
<ALIGN=LEFT><PRE>
Method: createTtreeLevelN
Arguments: none
Return: none
Fields: startTtreeRef start of T-tree
	nextlevelFlag set to true if next level exists
--------------------------------------
K <-- 2

while (nextlevelFlag)
    addSupportToTtreeLevelN(K)
    pruneLevelN(startTtreeRef,K)
    nextlevelFlag <-- false
    generateLevelN(startTtreeRef,K,{})
    K <-- K+1
End loop
--------------------------------------
</PRE></ALIGN>
</TD></TABLE>
<P><B>Table 4</B>: <I>The</I> <TT>createTtreeLevelN</TT> <I>method</I></P>
</CENTER>

<CENTER>
<TABLE BORDER=1 CELLPADDING=5><TR><TD>
<ALIGN=LEFT><PRE>
Method: addSupportToTtreeLevelN
Arguments: K the current level
Return: none
Fields: startTtreeRef start of T-tree
	dataArray 2D array holding input sets
--------------------------------------
Loop from i = 0 to i = number of records in dataArray
    length = number of attributes in dataArray[i]
    addSupportToTtreeFindLevel(startTtreeRef,K,length,
    		dataArray[i]
End loop
--------------------------------------

Method: addSupportToTtreeFindLevel
Arguments: linkref reference to current array in T-tree
	K level marker
	length length of array at current branch in t-tree
	record input data record under consideration
Return: none
Fields: None
--------------------------------------
if (K=1)
    Loop from i = 0 to i = length
    	if (linkref[record[i]] != null)
		increment linkref[record[i]].support by 1
	End if
    End Loop
else
    Loop from i = K-1 to i = length
        if (linkref[record[i]] != null &&
			linkref[record[i]].childRef != null)
	    addSupportToTtreeFindLevel(linkref[record[i]].childRe,
	 		K-1,i,record)
	End if
    End loop
end if else   		   	
--------------------------------------
</PRE></ALIGN>
</TD></TABLE>
<P><B>Table 5</B>: <I>The</I> <TT>addSupportToTtreeLevelN</TT> <I>method</I>
and its related <TT>addSupportToTtreeFindLevel</TT> method</P>
</CENTER>

<CENTER>
<TABLE BORDER=1 CELLPADDING=5><TR><TD>
<ALIGN=LEFT><PRE>
Method: pruneLevelN
Arguments: linkref reference to current array in T-tree
	K level marker
Return: true if entire array pruned
Fields: minSupport the minimum support threshold
--------------------------------------
if (K=1)
    allUnsupported <-- true
    Loop from i = 1 to i = length of array
    	if (linkref[i] != null)
	    if (linkref[i].support < minSupport)
	    		linkref[i] <-- null
            else allUnsupported <-- false
	    End if else
	End if
    return allUnsupported
    End Loop
else
    Loop from i = K to i = length of array
        if (linkref[i] != null)
	    if (pruneLevelN(linkref[i].childRef,K-1)
	    	linkref[i].childRef <-- null
	    End if
	 End if
    End loop
End if else   		   	
--------------------------------------
</PRE></ALIGN>
</TD></TABLE>
<P><B>Table 6</B>: <I>The</I> <TT>pruneLevelN</TT></P>
</CENTER>

<CENTER>
<TABLE BORDER=1 CELLPADDING=5><TR><TD>
<ALIGN=LEFT><PRE>
Method: generateLevelN
Arguments: linkref reference to current array in T-tree
	K level marker
	I the item set represented by the parent node
Return: None
Fields: None
--------------------------------------
if (K=1)
    Loop from i = 2 to i = length of array
	if (linkref[i] != null)
	    generateNextLevel(linkref,i,I union i)
	End if
    End loop
else
    Loop from i = K to i = length of array
	if (linkref[i] != null && linkref[i].childRef != null)
	    generateLevelN(linkref[i].childRef,K-1,I union i
--------------------------------------

Method: generateNextLevel
Arguments: linkref reference to current array in T-tree
	i index to parent node in vurrent array
	I the item set represented by the parent node
Return: None
Fields: nextLevelExists flafg set to true or false
--------------------------------------
linkref[i].childRef <-- array of empty t-tree nodes of length i

Loop from j = 1 to j = i
     if (linkRef[j] != null)
         newI <-- I union j
	 if (all newI true subsets are all supported in the
	 		T-tree sofar)
	     linkRef[i].childRef[j] <-- new T-tree Node
	     nextLevelExists <-- true
	 else linkRef[i].childRef[j] <-- null
	 End if else
     End if
End loop
--------------------------------------
</PRE></ALIGN>
</TD></TABLE>
<P><B>Table 7</B>: <I>The</I> <TT>generateLevelN</TT> <I>method</I>
and its related <TT>generateNextLevel</TT> method</P>
</CENTER>

<br><hr><br>
<A name = "conclusions">
<table BORDER-=0 WIDTH="100%" CELLPADDING=5 BGCOLOR="006699">
<tr><td><h2><font color =" white">7. CONCLUSSIONS</font></h2></td>
</table> <BR>

<P>The Apriori-T ARM algorithm described here
have been use successfully by the LUCS-KDD reseach group to contrast and 
compare a variety of ARM algorithms and techniques. The software is available for
free, however the author 
would appreciate appropriate acknowledgement. The following reference format 
for referring to the Apriori-T implementation available here
is suggested:</P>

<OL>
<LI>Coenen, F. (2004), <I>The LUCS-KDD
Apriori-T Association Rule Mining Algorrithm</I>,
http://www.cxc.liv.ac.uk/~frans/KDD/Software/Apriori_T/aprioriT.html,
Department of Computer Science, The University of Liverpool, UK.
</OL>

<P>Should you discover any "bugs" or other problems within the software (or this 
documentation), do not hesitate to contact 
the author.</P>

<br><hr><br>
<table BORDER-=0 WIDTH="100%" CELLPADDING=5 BGCOLOR="006699">
<tr><td><h2><font color =" white">REFERENCES</font></h2></td>
</table> <BR>

<OL>
<LI>Agrawal, R. and Srikant, R. (1994),
<I>t algorithms for mining association rules</I>,
In proceedings of 20th VLDB Conference, Morgan Kaufman, pp487-499.
<LI>Coenen and Leng (2004).
<I>Data Structures for Association Rule Mining: 
T-trees and P-trees</I>
To appear in IEEE Transaction in Knowledge and Data Engineering. 
</OL>

<br><hr><br>
<p>Created and maintained by
<a HREF=http://www.csc.liv.ac.uk/~frans/>Frans Coenen</a>.
Last updated 17 March 2004
</body>
</html>