fptree.cpp

FP-growth算法的改进C++程序,具有较好的扩展性和应用性,本程序改成用行读取

	m_sysTime =
		((float) (myTime3.ru_stime.tv_sec  - myTime1.ru_stime.tv_sec)) +
		((float) (myTime3.ru_stime.tv_usec - myTime1.ru_stime.tv_usec)) * 1e-6;
	m_userTime = m_persum.GetUserTime();
	m_sysTime = m_persum.GetSysTime();
	printf("User time : %f seconds\n", m_userTime);
	printf("System time : %f seconds\n", m_sysTime);
	printf("Total time: %f seconds\n\n", m_userTime + m_sysTime);
#else
#if !SIM_TIME
	m_sysTime = m_tm3.m_ktime - m_tm1.m_ktime;
	printf("System time : %f seconds\n", m_sysTime);
#endif
	m_userTime = m_tm3.m_utime - m_tm1.m_utime;
	printf("Use time: %f seconds\n", m_userTime);
	printf("Total time: %f seconds\n\n", m_userTime + m_sysTime);
#endif

}

void Fptree::Destroy()
{
	LargeItemPtr aLargeItemset; 
	int i;
	
	for (i=0; i < realK; i++) {
		aLargeItemset = largeItemset[i];
		while (aLargeItemset != NULL) {
			largeItemset[i] = largeItemset[i]->next;
			free(aLargeItemset->itemset);
			free(aLargeItemset);
			aLargeItemset = largeItemset[i];
		}
	}
	free(largeItemset);
	
	free(numLarge);
	
	free(headerTableLink);
	
	destroyTree(root);
	
	return;
}

void Fptree::destroyTree(FPTreeNode node)
{
	childLink temp1, temp2;
	
	if (node == NULL) return;
	
	temp1 = node->children;
	while(temp1 != NULL) {
		temp2 = temp1->next;
		destroyTree(temp1->node);
		free(temp1);
		temp1 = temp2;
	}
	
	free(node);
	
	return;
}

/******************************************************************************************
 * Function: q_sortA
 *
 * Description:
 * 	Quick sort two arrays, indexList[] and the corresponding freqItemP[], 
 *	in ascending order of indexList[].
 *
 * Invoked from:	
 *	buildTree()
 *	buildConTree()
 *	q_sortA()
 * 
 * Functions to be invoked:
 *	swap()
 *	q_sortA()
 *
 * Input Parameters:
 *      low		-> lower bound index of the array to be sorted
 *      high		-> upper bound index of the array to be sorted
 *      size		-> size of the array
 *	length		-> length of an itemset
 *
 * In/Out Parameters:
 *      indexList[]	-> array to be sorted
 *      freqItemP[]	-> array to be sorted
 */
void Fptree::q_sortA(int *indexList, int *freqItemP, int low, int high, int size)
{
 int pass;
 int highptr=high++;     /* highptr records the last element */
 /* the first element in list is always served as the pivot */
 int pivot=low;

 if(low>=highptr) return;
 do {
        /* Find out, from the head of indexList[], 
	 * the 1st element value not smaller than the pivot's 
	 */
        pass=1;
        while(pass==1) {
                if(++low<size) {
                        if(indexList[low] < indexList[pivot])
                                pass=1;
                        else pass=0;
                } else pass=0;
        }

        /* Find out, from the tail of indexList[],
	 * 1st element value not larger than the pivot's 
	 */
        pass=1;
        while(pass==1) {
                if(high-->0) {
                        if(indexList[high] > indexList[pivot])
                                pass=1;
                        else pass=0;
                } else pass=0;
        }

        /* swap elements pointed by low pointer & high pointer */
        if(low<high)
                swap(indexList, freqItemP, low, high);
 } while(low<=high);

 swap(indexList, freqItemP, pivot, high);

 /* divide list into two for further sorting */
 q_sortA(indexList, freqItemP, pivot, high-1, size);
 q_sortA(indexList, freqItemP, high+1, highptr, size);

 return;
}


/******************************************************************************************
 * Function: addToLargeList
 *
 * Description:
 *	Add a large itemset, i.e. an itemset of support >= threshold,
 *	to the large itemsets list.
 *
 * Invoked from:	
 *	FPgrowth()
 *	combine()
 * 
 * Functions to be invoked: None
 *
 * Input parameters:
 *	pattern[]	-> The large itemset to be inserted
 *	patternSupport	-> Support of the itemset
 *	index		-> Number of items in the itemset - 1
 *
 * Global variables:
 *	numLarge[]	-> Increment this counter by 1 to represent
 *			   the current number of large (index+1)-itemsets found
 */
void Fptree::addToLargeList(int *pattern, int patternSupport, int index)
{
 LargeItemPtr aLargeItemset;
 LargeItemPtr aNode, previous=NULL;
 int i;

 /* Create a node to store the itemset */
 aLargeItemset = (LargeItemPtr) malloc (sizeof(ItemsetNode));
 if (aLargeItemset == NULL) {
	printf("out of memory\n");
	exit(1);
 }
 aLargeItemset->itemset = (int *) malloc (sizeof(int) * (index+1));
 if (aLargeItemset->itemset == NULL) {
	printf("out of memory\n");
	exit(1);
 }

 /* Store the support of the itemset */
 aLargeItemset->support = patternSupport;

 /* Store the items of the itemset */
 for (i=0; i <= index; i++) {
	aLargeItemset->itemset[i] = pattern[i];
 }

 aLargeItemset->next = NULL;

 /* Assign aNode to point to the head of the resulting list */
 aNode = largeItemset[index];

 /* Insert the itemset to the (index+1)-itemset resulting list. 
  * There are 3 cases for the insertion:
  *	1. The resulting list is empty
  *		-- insert the itemset to the head of the list
  *	2. The itemset should be inserted somewhere between 
  *	   the head and tail of the list
  *		-- locate the suitable position of the list according to its support
  *		-- insert the itemset
  *	3. The itemset's support is less than the supports of all the itemsets in the list
  *		-- append the itemset at the end of the list
  */
 if (aNode == NULL) {
	/* Case 1: The resulting list is empty */	
	largeItemset[index] = aLargeItemset;
 } else {
 	while ((aNode != NULL) && (aNode->support > patternSupport)) {
		previous = aNode;
		aNode = aNode->next;
 	}

	/* Case 2: Insert between head and tail of the list */
 	if (previous != NULL) {
		previous->next = aLargeItemset;
		aLargeItemset->next = aNode;
	} else {

		/* Case 3: Append to the end of the list */
		aLargeItemset->next = largeItemset[index];
		largeItemset[index] = aLargeItemset;
	}
 }

 /* Update the counter for the number of large (index+1)-itemsets in the list */
 (numLarge[index])++;
 
 return;
}


/******************************************************************************************
 * Function: combine
 *
 * Description:
 *	Make all possible combinations of itemsets for a single path FP-tree.	
 *	Any of the combinations is a large itemset.
 *
 * Invoked from:	
 *	FPgrowth()
 *	combine()
 * 
 * Functions to be invoked:
 *	addToLargeList()
 *	combine()
 *
 * Input parameters:
 *  	*itemList	-> Array to hold all items in the FP-tree path
 *  	*support	-> Counts of the items in the path (in *itemList)
 *  	*base		-> A large itemset discovered which will be used to combine
 *			   with additional items in *itemList to form more large itemsets 
 *  	start		-> Position in *itemList where the base is formed
 *              	   from subset of the set of items in the prefix to this position,
 *			   and new large pattern will combine the base with
 *			   one additional element from the suffix to this position.
 *  	baseSize	-> Size of the base, i.e. number of items in base
 *    
 */
void Fptree::combine(int *itemList, int *support, int start, int itemListSize, int *base, int baseSize)
{
 int *pattern;
 int i, j; 

 if (baseSize >= realK) return;

 if (start == itemListSize) return;

 /* Create an array of size (baseSize+1) to store any itemset formed from
  * the union of *base and 
  * any item of *itemsetListSize from the position of start to the end
  */
 pattern = (int *) malloc (sizeof(int) * (baseSize+1));
 if (pattern == NULL) {
	printf("out of memory\n");
	exit(1);
 }

 /* Insert all the items in base[] to pattern[] 
  */
 for (j=0; j < baseSize; j++)
	pattern[j] = base[j];

 for (i=start; i < itemListSize; i++) {

	/* Append an item, itemList[i], to pattern[] 
	 */
	pattern[baseSize] = itemList[i];

	/* Insert pattern[] to the result list of large (baseSizes+1)-itemsets.
	 * Support of this itemset = support[i] 
	 */
	addToLargeList(pattern , support[i], baseSize);

	/* Form pattern[] with 
	 * any item in *itemListSize from position (i+1) to the end of itemListSize
	 */
	combine(itemList, support, i+1, itemListSize, pattern, baseSize+1);	
 }

 free(pattern);
 
 return;
}


/******************************************************************************************
 * Function: insert_tree
 *
 * Description:
 *  	This function is to insert a frequent pattern
 *  	of a transaction to the FP-tree (or conditional FP-tree).
 *  	The frequent pattern consists of a list of the frequent 1-items
 *  	of a transaction, and is sorted according to the sorted order of the
 *  		1. frequent 1-items in function pass1(), if it is the initial FP-tree;
 *		2. frequent 1-items in the conditional pattern base, if it is a conditional FP-tree.
 *  	This function is recursively invoked and insert the (ptr+1)th item of the
 *  	frequent pattern in the (ptr+1)th round of recursion.
 *
 *	There are 3 cases to handle the insertion of an item:
 *	1. The tree or subtree being visited has no children.
 *		Create the first child and store the info of the item
 *		to this first child.
 *	2. The tree or subtree has no children that match the current item.
 *		Add a new child node to store the item.
 *	3. There is a match between the item and a child of the tree.
 *		Increment the count of the child, and visit the subtree of this child.
 *
 * Invoked from:	
 *	buildTree()
 *	buildConTree()
 *	insertTree()
 *
 * Functions to be invoked:
 *	insertTree()
 *
 * Parameters:
 *  - freqItemP : The list of frequent items of the transaction.
 *                They are sorted according to the order of frequent 1-items.
 *  - indexList : 'indexList[i]' is the corresponding index of the header table 
 *                that represents the item 'freqItemP[i]'.
 *  - count     : The initial value for the 'count' of the FP-tree node for the current
 *                freqItemP[i].
 *		  It is equal to 1 if the FP-tree is the initial one,
 *		  otherwiese it is equal to the support of the base of 
 *		  this conditional FP-tree.
 *  - ptr       : Number of items in the frequent pattern inserted so far.
 *  - length    : Number of items in the frequent pattern.
 *  - T         : The current FP-tree/subtree being visited so far.
 *  - headerTableLink : Header table of the FP-tree.
 *  - path      : Number of new tree path (i.e. new leaf nodes) created so far for the insertions.
 */
void Fptree::insert_tree(int *freqItemP, int *indexList, int count, int ptr, int length, 
			FPTreeNode T, FPTreeNode *headerTableLink, int *path)  
{
 childLink newNode;
 FPTreeNode hNode;
 FPTreeNode hPrevious;
 childLink previous;
 childLink aNode;

 /* If all the items have been inserted */
 if (ptr == length) return;

 /* Case 1 : If the current subtree has no children */
 if (T->children == NULL) {
	/* T has no children */

	/* Create child nodes for this node */
	newNode = (childLink) malloc (sizeof(ChildNode));
	if (newNode == NULL) {
		printf("out of memory\n");
		exit(1);
	}

	/* Create a first child to store the item */
	newNode->node = (FPTreeNode) malloc (sizeof(FPNode));
	if (newNode->node == NULL) {
		printf("out of memory\n");
		exit(1);
	}

	/* Store information of the item */
	newNode->node->item = freqItemP[ptr];
	newNode->node->count = count;
	newNode->node->numPath = 1;
	newNode->node->parent = T;
	newNode->node->children = NULL;
	newNode->node->hlink = NULL;
	newNode->next = NULL;
	T->children = newNode;

	/* Link the node to the header table */
	hNode = headerTableLink[indexList[ptr]];
	if (hNode == NULL) {
		/* Place the node at the front of the horizontal link for the item */
		headerTableLink[indexList[ptr]] = newNode->node;
	} else {
		/* Place the node at the end using the horizontal link */
		while (hNode != NULL) {
			hPrevious = hNode;
			hNode = hNode->hlink;
		}

		hPrevious->hlink = newNode->node;
	}

	/* Insert next item, freqItemP[ptr+1], to the tree */
	insert_tree(freqItemP, indexList, count, ptr+1, length, T->children->node, headerTableLink, path);
	T->numPath += *path;

 } else {
	aNode = T->children;
	while ((aNode != NULL) && (aNode->node->item != freqItemP[ptr])) {
		previous = aNode;
		aNode = aNode->next;
	}

	if (aNode == NULL) {
		/* Case 2: Create a new child for T */ 

		newNode = (childLink) malloc (sizeof(ChildNode));
		if (newNode == NULL) {
			printf("out of memory\n");
			exit(1);
		}
		newNode->node = (FPTreeNode) malloc (sizeof(FPNode));
		if (newNode->node == NULL) {
			printf("out of memory\n");
			exit(1);
		}

		/* Store information of the item */
		newNode->node->item = freqItemP[ptr];
		newNode->node->count = count;
		newNode->node->numPath = 1;
		newNode->node->parent = T;
		newNode->node->children = NULL;
		newNode->node->hlink = NULL;
		newNode->next = NULL;
		previous->next = newNode;

		/* Link the node to the header table */
		hNode = headerTableLink[indexList[ptr]];
		if (hNode == NULL) {
			/* Place the node at the front of the horizontal link for the item */
			headerTableLink[indexList[ptr]] = newNode->node;
		} else {
			/* Place the node at the end using the horizontal link */
			while (hNode != NULL) {
				hPrevious = hNode;
				hNode = hNode->hlink;
			}
			hPrevious->hlink = newNode->node;
		}

		/* Insert next item, freqItemP[ptr+1], to the tree */
		insert_tree(freqItemP, indexList, count, ptr+1, length, newNode->node, headerTableLink, path);

		(*path)++;
		T->numPath += *path;

	} else {
		/* Case 3: Match an existing child of T */

		/* Increment the count */
		aNode->node->count += count;

		/* Insert next item, freqItemP[ptr+1], to the tree */
		insert_tree(freqItemP, indexList, count, ptr+1, length, aNode->node, headerTableLink, path);

		T->numPath += *path; 
	}
 }