Monday, March 30, 2009

/* TWO DECIMAL PLACES */

/* TWO DECIMAL PLACES */
/** Converts given real number to real number rounded up to two decimal
places.
@param number the given number.
@return the number to two decimal places. */

protected double twoDecPlaces(double number) {
int numInt = (int) ((number+0.005)*100.0);
number = ((double) numInt)/100.0;
return(number);
}


}


FPtree1.java

import java.io.*;
public class FPtree1 extends TotalSuppTree {

/** FP-tree node structure comprising a FPgrowthItemPrefixSubtreeNode in
which to store counts and a reference to a child branch. */
protected class FPtreeNode {
/** The FP tree node. */
private FPgrowthItemPrefixSubtreeNode node = null;
/** The reference to the child branch (levels in FP-tree branches are
stored as a arrays of FPtreeNode structures. */
private FPtreeNode[] childRefs = null;

/** Default constructor. */
protected FPtreeNode() {
}

/** Single argument constructor.
@param newNode the reference to a new node to be included in the

FP-tree.*/
protected FPtreeNode(FPgrowthItemPrefixSubtreeNode newNode) {
node = newNode;
}
}

/** Prefix subtree structure. A set enumeration tree in which to store
itemsets together with support values. */

private class FPgrowthItemPrefixSubtreeNode {
/** The attribute identifier. */
private short itemName;
/** The support count. */
private int itemCount;
/** The backward link to the parent node in FP tree. */
private FPgrowthItemPrefixSubtreeNode parentRef = null;
/** The forward link to the next node in a linked list of nodes with
same attribute identifier starting with an element in the header table
*/
private FPgrowthItemPrefixSubtreeNode nodeLink = null;

/** Default constructor. */
private FPgrowthItemPrefixSubtreeNode() {
}

/** Three argument constructor.
@param name the itemset identifier.
@param support the support value for the itemset.
@param backRef the backward link to the parent node. */

private FPgrowthItemPrefixSubtreeNode(short name, int support,
FPgrowthItemPrefixSubtreeNode backRef) {
itemName = name;
itemCount = support;
parentRef = backRef;
}
}

/** Header table. */

protected class FPgrowthHeaderTable {
/** The 1-itemset (attribute) identifier. */
protected short itemName;
/** The forward link to the next node in the link list of nodes. */
protected FPgrowthItemPrefixSubtreeNode nodeLink = null;

// Constructors
protected FPgrowthHeaderTable (short columnNum) {
itemName = columnNum;
}
}

/** Structure in which to store ancestor itemSets, i.e. nodes in an FP-tree
that preceed the nodes identified by following a trail of links from a
particular item in the header table. */

private class FPgrowthSupportedSets {
/** The itemSet label. */
private short[] itemSet = null;
/** The associated support value for the given itemset. */
private int support;
/** The reference to the next node in a linked list. */
private FPgrowthSupportedSets nodeLink = null;

/** Three argument constructor.
@param newitemSet the given itemSet label.
@param newSupport the associated support value for the given itemset.
@param newNodeLink the reference to the next node in a linked list. */

private FPgrowthSupportedSets(short[] newitemSet, int newSupport,
FPgrowthSupportedSets newNodeLink) {
itemSet = newitemSet;
support = newSupport;
nodeLink = newNodeLink;
}
}

/** Structure in which to store counts. */
private class FPgrowthColumnCounts {
/** The column/attribute ID number. */
private short columnNum;
/** The associated support value. */
private int support=0;

/** One argument constructor.
@param column the column/attribute ID number. */

private FPgrowthColumnCounts(int column) {
columnNum = (short) column;
}

/** Two argument constructor.
@param column the column/attribute ID number.
@param sup the associatec support value. */

private FPgrowthColumnCounts(int column, int sup) {
columnNum = (short) column;
support = sup;
}
}

/** Start reference for FP-tree. */
protected FPtreeNode rootNode = null;
/** Start reference for header table. */
protected FPgrowthHeaderTable[] headerTable;
/** Start reference for supportedSets linked list (temporary storage
only).*/
private static FPgrowthSupportedSets startTempSets = null;


/** Temporary storage for an index into an array of FP-tree nodes.
Used when reassigning child reference arrays. */
private int tempIndex = 0;

/** Number of nodes created. */
private int numberOfNodes;

/** Constructor to process command line argument.
@param args the command line arguments. */

public FPtree1(String[] args) {
super(args);

// Initialise root node
rootNode = new FPtreeNode();

// Create header table
headerTable = new FPgrowthHeaderTable[numOneItemSets+1];

// Populate header table
for (int index=1;index headerTable[index] = new FPgrowthHeaderTable((short) index);
}
}

/** Top level method to commence the construction of the FP-Tree. */

public void createFPtree() {
// Create header table
headerTable = new FPgrowthHeaderTable[numOneItemSets+1];

// Populate header table
for (int index=1;index headerTable[index] = new FPgrowthHeaderTable((short) index);
}

// Process datatable, loop through data table (stored in data array)
// For each entry add the entry to the FP-tree.
for (int index=0;index // Non null record (if initial data set has been reordered and
// pruned some records may be empty
if (dataArray[index] != null)
addToFPtree(rootNode,0,dataArray[index],1,headerTable);
}
}

/** Searches through current list of child refs looking for given item set.
If reference for current itemset found increments support count and
proceed down branch, otherwise adds to current level.
@param ref the current location in the FP-tree ( rootNode at start).
@param place the current index in the given itemset.
@param itemSet the given itemset.
@param support the associated support value for the given itemset.
@param headerRef the link to the appropriate place in the header table. */

private void addToFPtree(FPtreeNode ref, int place, short[] itemSet,
int support, FPgrowthHeaderTable[] headerRef) {

if (place < itemSet.length) {
if (!addToFPtree1(ref,place,itemSet,support,headerRef))
addToFPtree2(ref,place,itemSet,support,headerRef);
}
}

/** Searches through existing branch and if itemset found updates the
support count and returns true, otherwise return false.
@param ref the current FP-tree node reference.
@param place the current index in the given itemset.
@param itemSet the given itemset.
@param support the associated support value for the given itemset.
@param headerRef the link to the appropriate place in the header table.
@return true if given itemset exists in FP-tree, and false otherwise. */

private boolean addToFPtree1(FPtreeNode ref, int place, short[] itemSet,
int support, FPgrowthHeaderTable[] headerRef) {

// Loop
if (ref.childRefs != null) {
for (int index=0;index // If item is already in list of child refs
// increment count and proceed down branch.
if (itemSet[place] == ref.childRefs[index].node.itemName) {
ref.childRefs[index].node.itemCount =ref.childRefs[index].node.itemCount + support;
addToFPtree(ref.childRefs[index],place+1,itemSet,support,
headerRef);
return(true);
}
// Child refs ordered so break when passed
// point where item should be
if (itemSet[place] < ref.childRefs[index].node.itemName)
return(false);
}
}

// Default

return(false);
}


/** Adds new node to FP-tree. Adds first attribute in itemSet and then
rest of sequence.
@param ref the current FP-tree node reference.
@param place the current index in the given itemset.
@param itemSet the given itemset.
@param support the associated support value for the given itemset.
@param headerRef the link to the appropriate place in the header table. */

private void addToFPtree2(FPtreeNode ref, int place, short[] itemSet,
int support, FPgrowthHeaderTable[] headerRef) {

// Create new Item Prefix Subtree Node
FPgrowthItemPrefixSubtreeNode newPrefixNode = new
FPgrowthItemPrefixSubtreeNode(itemSet[place],support,ref.node);
// Create new FP tree node incorporating new Item Prefix Subtree Node
FPtreeNode newFPtreeNode = new FPtreeNode(newPrefixNode);
// Add link from header table
addRefToFPgrowthHeaderTable(itemSet[place],newPrefixNode,headerRef);
// Add into FP tree
ref.childRefs = reallocFPtreeChildRefs(ref.childRefs,newFPtreeNode);
// Proceed down branch with rest of itemSet
addRestOfitemSet(ref.childRefs[tempIndex],newPrefixNode,place+1,itemSet,
support,headerRef);
}


/** Continues adding attributes in current itemset to FP-tree.
@param ref the current FP-tree node reference.
@param backRef the backwards link to the previous node.
@param place the current index in the given itemset.
@param itemSet the given itemset.
@param support the associated support value for the given itemset.
@param headerRef the link to the appropriate place in the header table. */

private void addRestOfitemSet(FPtreeNode ref, FPgrowthItemPrefixSubtreeNode backRef,
int place, short[] itemSet, int support,
FPgrowthHeaderTable[] headerRef) {

// Process if more items in item set.
if (place // Create new Item Prefix Subtree Node
FPgrowthItemPrefixSubtreeNode newPrefixNode = new
FPgrowthItemPrefixSubtreeNode(itemSet[place],support,backRef);
// Create new FP tree node incorporating new Item Prefix Subtree
// Node
FPtreeNode newFPtreeNode = new FPtreeNode(newPrefixNode);
// Add link from header table
addRefToFPgrowthHeaderTable(itemSet[place],newPrefixNode,headerRef);
ref.childRefs = reallocFPtreeChildRefs(ref.childRefs,newFPtreeNode);
// Add into FP tree
addRestOfitemSet(ref.childRefs[tempIndex],newPrefixNode,place+1,
itemSet,support,headerRef);
}
}

/* Add reference to header table*/

/** Adds reference to new FP-tree node to header table moving old reference
so that it becomes a link from the new FP-tree node.
@param columnNumber the given attribute.
@param newNode the newly created FP-tree node.
@param headerRef the reference to the header table . */

private void addRefToFPgrowthHeaderTable(short columnNumber,
FPgrowthItemPrefixSubtreeNode newNode,
FPgrowthHeaderTable[] headerRef) {
FPgrowthItemPrefixSubtreeNode tempRef;

// Loop through header table
for (int index=1;index // Found right attribute in table?
if (columnNumber == headerRef[index].itemName) {
tempRef = headerRef[index].nodeLink;
headerRef[index].nodeLink = newNode;
newNode.nodeLink = tempRef;
break;
}
}
}




/* Start mining */

/** Top level "FP-growth method" to mine the FP tree. */

public void startMining() {

System.out.println("Mining FP-tree");

startMining(headerTable,null);

}

/** Commences process of mining the FP tree. Commence with the bottom
of the header table and work upwards. Working upwards from the bottom of
the header table if there is a link to an FP tree node :

@param tableRef the reference to the current location in the header table
(commencing with the last item).
@param itemSetSofar the label fot the current item sets as generated to
date (null at start). */

private void startMining(FPgrowthHeaderTable[] tableRef,
short[] itemSetSofar) {
int headerTableEnd = tableRef.length-1;
FPgrowthColumnCounts[] countArray = null;
FPgrowthHeaderTable[] localHeaderTable = null;
FPtreeNode localRoot;
int support;
short[] newCodeSofar;

// Loop through header table from end to start, item by item

for (int index=headerTableEnd;index>=1;index--) {
// Check for null link
if (tableRef[index].nodeLink != null) {
// process trail of links from header table element
startMining(tableRef[index].nodeLink,tableRef[index].itemName,
itemSetSofar);
}
}
}

/** Commence process of mining FP tree with respect to a single element in
the header table.
@param nodeLink the firsty link from the header table pointing to an FP-tree
node.
@param itemName the label associated with the element of interest in the
header table.
@param itemSetSofar the item set represented by the current FP-tree. */

protected void startMining(FPgrowthItemPrefixSubtreeNode nodeLink,
short itemName, short[] itemSetSofar) {

// Count support for current item in header table and store a
// T-tree data structure
int support = genSupHeadTabItem(nodeLink);
short[] newCodeSofar = realloc2(itemSetSofar,itemName);
addToTtree(newCodeSofar,support);

// Collect ancestor itemSets and store in linked list structure
startTempSets=null;
generateAncestorCodes(nodeLink);

// Process Ancestor itemSets
if (startTempSets != null) {
// Count singles in linked list
FPgrowthColumnCounts[] countArray = countFPgrowthSingles();
// Create and populate local header table
FPgrowthHeaderTable[] localHeaderTable =
createLocalHeaderTable(countArray);
if (localHeaderTable != null) {
// Prune ancestor itemSets
pruneAncestorCodes(countArray);
// Create new local root for local FP tree
FPtreeNode localRoot = generateLocalFPtree(localHeaderTable);
// Mine new FP tree
startMining(localHeaderTable,newCodeSofar);
}
}
}

/* Generarte support for header table single item */

/** Counts support for single attributes in header table by following node
links.
@param nodeLink the start link from the header table.
@return the support valye for the item set indicated by the header table. */

private int genSupHeadTabItem(FPgrowthItemPrefixSubtreeNode nodeLink) {
int counter = 0;

// Loop

while(nodeLink != null) {
counter = counter+nodeLink.itemCount;
nodeLink = nodeLink.nodeLink;
}

// Return
return(counter);
}

/** Generates ancestor itemSets are made up of the parent nodes of a given
node. This method collects such itemSets and stores them in a linked list
pointed at by startTempSets.
@param ref the reference to the current node in the prefix tree containing
itemsets together with support values.*/

private void generateAncestorCodes(FPgrowthItemPrefixSubtreeNode ref) {
short[] ancestorCode = null;
int support;

// Loop

while(ref != null) {
support = ref.itemCount;
ancestorCode = getAncestorCode(ref.parentRef);
// Add to linked list with current support
if (ancestorCode != null) startTempSets =
new FPgrowthSupportedSets(ancestorCode,support,
startTempSets);
// Next ref
ref = ref.nodeLink;
}
}

/** Generate the ancestor itemSet from a given node.
@param ref the reference to the current node in the prefix tree containing
itemsets together with support values. */

private short[] getAncestorCode(FPgrowthItemPrefixSubtreeNode ref) {
short[] itemSet = null;
if (ref == null) return(null);
// Else process
while (ref != null) {
itemSet = realloc2(itemSet,ref.itemName);
ref = ref.parentRef;
}

// Return
return(itemSet);
}

/** Removes elements in ancestor itemSets (pointed at by
startTempSets ) which are not supported by referring to count
array (which contains all the current supported 1 itemsets).
@param countArray the array of FPgrowthColumnCounts structures
describing the single item sets (in terms of labels and associated
support), contained in a linked list of FPgrowthSupportedSets
which in turn describe the ancestor nodes in an FP-tree that preceed the
nodes identified by following a trail of links from a particular item in
the header table. */

private void pruneAncestorCodes(FPgrowthColumnCounts[] countArray) {
FPgrowthSupportedSets ref = startTempSets;

// Loop through linked list of ancestor paths

while(ref != null) {
for(int index=0;index if (countArray[ref.itemSet[index]].support < minSupport)
ref.itemSet = removeElementN(ref.itemSet,index);
}
ref = ref.nodeLink;
}
}


/** Counts frequent 1 item sets in ancestor itemSets linked list and place
into an array.
@return array of FPgrowthColumnCounts structures describing the
single item sets (in terms of labels and associated support), contained in
a linked list of FPgrowthSupportedSets which in turn describe the
ancestor nodes in an FP-tree that preceed the nodes identified by following
a trail of links from a particular item in the header table. */

private FPgrowthColumnCounts[] countFPgrowthSingles() {
int index, place=0;
FPgrowthSupportedSets nodeLink = startTempSets; // Start of linked list

// Dimension array, assume all attributes present, then it will
// be possible to index in to the array.

FPgrowthColumnCounts[] countArray = new
FPgrowthColumnCounts[numOneItemSets+1];
// Initialise array
for (index=1;index new FPgrowthColumnCounts(index);

// Loop through linked list of ancestor itemSets

while (nodeLink != null) {
// Loop through itemSet
for (index=0;index place = nodeLink.itemSet[index];
countArray[place].support = countArray[place].support +
nodeLink.support;
}
nodeLink = nodeLink.nodeLink;
}



// Return
return(countArray);
}

/* Create local header table */

/** Creates a local header table comprising those item that are supported
in the count array.
@param countArray the support for the 1 item sets.
@return a FPgrowth header table. */

private FPgrowthHeaderTable[]
createLocalHeaderTable(FPgrowthColumnCounts[] countArray) {
int index;
FPgrowthHeaderTable[] localHeaderTable;

localHeaderTable = localHeadTabUnordered(countArray);

// Order according single item support

//orderLocalHeaderTable(localHeaderTable,countArray);

// Return

return(localHeaderTable);
}

/* Create new local header table */

/** Create a new local header table, but unorderd.
@param countArray the csupport for the 1 item sets.
@return a FPgrpwth header table. */

private FPgrowthHeaderTable[]
localHeadTabUnordered(FPgrowthColumnCounts[] countArray) {
int counter = 1;

// Loop through array and count supported one item sets
for (int index=1;index if (countArray[index].support >= minSupport) counter++;
}

// Build new Header Table array containing only supported items

if (counter == 1) return(null);
FPgrowthHeaderTable[] localHeaderTable =
new FPgrowthHeaderTable[counter];

// Populate header table

int place=1;
for (int index=1;index if (countArray[index].support >= minSupport) {
localHeaderTable[place] = new
FPgrowthHeaderTable((short) countArray[index].columnNum);
place++;
}
}

// Return

return(localHeaderTable);
}

/* Order local header table */

/** Orders local header table (currently unused).
@param localHeaderTable the FPgrpwth header table to be ordered.
@param countArray the csupport for the 1 item sets. */

private void orderLocalHeaderTable(FPgrowthHeaderTable[] localHeaderTable,
FPgrowthColumnCounts[] countArray) {
boolean isOrdered;
FPgrowthHeaderTable temp;
int index, place1, place2;

//loop through table
do {
index = 1;
isOrdered=true;
while (index < (localHeaderTable.length-1)) {
place1 = localHeaderTable[index].itemName;
place2 = localHeaderTable[index+1].itemName;
if (countArray[place1].support > countArray[place2].support) {
isOrdered=false;
// Swap
temp = localHeaderTable[index];
localHeaderTable[index] = localHeaderTable[index+1];
localHeaderTable[index+1] = temp;
}
// increment index
index++;
}
} while (isOrdered==false);
}


/** Generates a local FP tree
@param tableRef reference to start of header table containing links to
an FP-tree produced during the FP-tree generation process.
@rerurn reference to the start of the generated FP-tree*/

private FPtreeNode generateLocalFPtree(FPgrowthHeaderTable[] tableRef) {
FPgrowthSupportedSets ref = startTempSets;
FPtreeNode localRoot = new FPtreeNode();

// Loop

while(ref != null) {
// Add to conditional FP tree
if (ref.itemSet != null) addToFPtree(localRoot,0,ref.itemSet,
ref.support,tableRef);
ref = ref.nodeLink;
}

// Return

return(localRoot);
}


/** Resizes the given array of FP-tree nodes so that its length is
increased by one element and new element inserted.
@param oldArray the given array of FP-tree nodes.
@param newNode the given node to be added to the FP-tree
@return The revised array of FP-tree nodes. */

private FPtreeNode[] reallocFPtreeChildRefs(FPtreeNode[] oldArray,
FPtreeNode newNode) {

// No old array

if (oldArray == null) {
FPtreeNode[] newArray = {newNode};
tempIndex = 0;
return(newArray);
}

// Otherwise create new array with length one greater than old array

int oldArrayLength = oldArray.length;
FPtreeNode[] newArray = new FPtreeNode[oldArrayLength+1];

// Insert new node in correct order.

for (int index1=0;index1 < oldArrayLength;index1++) {
if (newNode.node.itemName < oldArray[index1].node.itemName) {
newArray[index1] = newNode;
for (int index2=index1;index2 newArray[index2+1] = oldArray[index2];
tempIndex = index1;
return(newArray);
}
newArray[index1] = oldArray[index1];
}

// Default

newArray[oldArrayLength] = newNode;
tempIndex = oldArrayLength;
return(newArray);
}

/** Commences process of outputting the prefix sub tree to the screen,
starting at header table. */

public void outputItemPrefixSubtree() {
int flag;
System.out.println("PREFIX SUBTREE FROM HEADER TABLE");
for(int index=1;index System.out.println("Header = " +
reconvertItem(headerTable[index].itemName));
flag = outputItemPrefixTree(headerTable[index].nodeLink);
if (flag!=1) System.out.println();
}
System.out.println();
}

/** Commences process of outputting a local prefix sub tree to the screen.
@param tableRef the reference to the local header table. */

private void outputItemPrefixSubtree(FPgrowthHeaderTable[] tableRef) {
int flag;
System.out.println("PREFIX SUBTREE FROM LOCAL HEADER TABLE");
for(int index=1;index System.out.println("Header = " +
reconvertItem(tableRef[index].itemName));
flag = outputItemPrefixTree(tableRef[index].nodeLink);
if (flag!=1) System.out.println();
}
System.out.println();
}

/** Outputs the given prefix sub tree.
@param ref the reference to the given branch.
@return a counter representing the current "node number" (used in
output). */

private int outputItemPrefixTree(FPgrowthItemPrefixSubtreeNode ref) {
int counter = 1;

// Loop

while (ref != null) {
System.out.print("(" + counter + ") " +
(reconvertItem(ref.itemName)) + ":" + ref.itemCount + " ");
counter++;
ref = ref.nodeLink;
}

return(counter);
}



/** Commences process of outputting FP-tree to screen. */

public void outputFPtree() {
System.out.println("FP TREE");
outputFPtreeNode1();
System.out.println();
}

/** Commences process of outputting a given branch of an FP-tree to the
screen.
@param ref the reference to the given FP-tree branch. */

private void outputFPtreeNode(FPtreeNode ref) {
System.out.println("LOCAL FP TREE");
outputFPtreeNode2(ref.childRefs,"");
System.out.println();
}

/** Continues process of outputting FP-tree to screen. */

private void outputFPtreeNode1() {
outputFPtreeNode2(rootNode.childRefs,"");
}

/** Outputs a given level in an FP-tree to the screen.
@param ref the reference to the given FP-tree level.
@param nodeID the root string for the node ID. */

private void outputFPtreeNode2(FPtreeNode ref[],String nodeID) {
if (ref == null) return;

// Otherwise process

for (int index=0;index System.out.print("(" + nodeID + (index+1) + ") ");
outputItemPrefixSubtreeNode(ref[index].node);
outputFPtreeNode2(ref[index].childRefs,nodeID+(index+1)+".");
}
}
/** Outputs the given prefix sub tree node.
@param ref the reference to the given node. */

public void outputItemPrefixSubtreeNode(FPgrowthItemPrefixSubtreeNode ref) {
System.out.print((reconvertItem(ref.itemName)) + ":" + ref.itemCount);
if (ref.nodeLink != null) {
System.out.println(" (ref to " +
(reconvertItem(ref.nodeLink.itemName)) + ":" +
ref.nodeLink.itemCount + ")");
}
else System.out.println(" (ref to null)");
}
}

Ttreenode.java

import java.io.*;
import java.util.*;

/** Methods concerned with Ttree node structure. Arrays of these structures
are used to store nodes at the same level in any sub-branch of the T-tree. */

public class TtreeNode {

/** The support associate with the itemset represented by the node. */
public int support = 0;

/** A reference variable to the child (if any) of the node. */
public TtreeNode[] childRef = null;

/** The number of nodes in the T-tree. */
public static int numberOfNodes = 0;

public TtreeNode() {
numberOfNodes++;
}
/** One argument constructor.
@param sup the support value to be included in the structure. */
public TtreeNode(int sup) {
support = sup;
numberOfNodes++;
}

public static int getNumberOfNodes() {
return(numberOfNodes);
}
}

No comments:





my traffic rate




Hire Me Direct
 
ss_blog_claim=47b8cd0f86a684cfdfc7f370edf4619d