fpgrowth.cpp

本人收集了一些关于关联规则算法的小程序,供大家参考,不足之处,请大家提出宝贵意见,谢谢

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<fstream.h>
#include<time.h>

typedef struct FPnode *FPTreeNode;	/* Pointer to a FP-tree node */

typedef struct Childnode *childLink;	/* Pointer to children of a FP-tree node */


typedef struct Childnode {
	FPTreeNode node;	/* A child node of an item */
	childLink next;		/* Next child */
} ChildNode;


typedef struct FPnode {
        int item;		
        int count;		
	int numPath;  		
	FPTreeNode parent;	/* Pointer to parent node */
        childLink children;	/* Pointer to children */
        FPTreeNode hlink;	/* Horizontal link to next node with same item */
} FPNode;


typedef struct Itemsetnode *LargeItemPtr;
typedef struct Itemsetnode {
	int support;
	float corr;
	int *itemset;
	LargeItemPtr next;
} ItemsetNode;
		
void FPgrowth(FPTreeNode T, FPTreeNode *headerTableLink, int headerSize, int *baseItems, int baseSize);


LargeItemPtr *largeItemset;	
int *numLarge;			
int *support1;			
int *largeItem1;	

FPTreeNode root=NULL;		/* Initial FP-tree */
FPTreeNode *headerTableLink;	/* Corresponding header table */

int expectedK;			/* User input upper limit of itemset size to be mined */
int realK;			/* Actual upper limit of itemset size can be mined */
int threshold;			
int numItem;			/* Number of items in the database */
int numTrans;			/* Number of transactions in the database */

float correlate;
char *dataFile;		
char *outFile;	
time_t start,finish;
float used_time;

int findsup(int inputnum)
{
	int i;
	int j;
	i=0;
	j=0;
 for (i=0; i < numItem; i++)
	if (largeItem1[i]==inputnum)
	{
		
	
	j=support1[i];
		break;

	}
 /*	support1[i] = 0;
	largeItem1[i] = i;
*/	
 
 return j;
}

void 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;
}


void 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 swap(int *support, int *itemset, int x, int i)
{ 
 int temp; 

 temp = support[x];
 support[x] = support[i];
 support[i] = temp;
 temp = itemset[x];
 itemset[x] = itemset[i];
 itemset[i] = temp;
 
 return;
}

void q_sortD(int *support, int *itemset, 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 {

	pass=1;
	while(pass==1) {
		if(++low<size) {
			if(support[low] > support[pivot])
				pass=1;
			else pass=0;
		} else pass=0;
	} 

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

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

 swap(support, itemset, pivot, high);

 /* divide list into two for further sorting */ 
 q_sortD(support, itemset, pivot, high-1, size); 
 q_sortD(support, itemset, high+1, highptr, size);
 
 return;
}


void 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 {

        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;
}


void addToLargeList(int *pattern, int patternSupport, int index)
{
 LargeItemPtr aLargeItemset;
 LargeItemPtr aNode, previous=NULL;
 int i,c1,c2;
 int temp=0;
 float cor;
 


 /* Judge whether to add the itemset */
 //printf("%d\n",pattern[0]);
// printf("%d\n",pattern[index]);
 
// printf("%d\n",temp);
// temp=temp*correlate;

 //printf("%d\n",temp);
	c1=findsup(pattern[0]);
	for (i=0;i<=index;i++)
	{
		c2=findsup(pattern[i]);
		if (c2>c1) c1=c2;	
	}
	temp=c1*correlate;
 if (patternSupport<=temp ) return;
	cor=float(patternSupport)/float(c1);

	

 


 /* 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;
 aLargeItemset->corr=cor;

 /* 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];

 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;
	}
 }

 (numLarge[index])++;
 
 return;
}


void 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;
}



void 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 {
		aNode->node->count += count;

		insert_tree(freqItemP, indexList, count, ptr+1, length, aNode->node, headerTableLink, path);

		T->numPath += *path; 
	}
 }

 return;
}


void buildtemptree(FPTreeNode *conRoot, FPTreeNode **conHeader, int conHeaderSize, int *conLargeItem,
		int *conLargeItemSupport, FPTreeNode T, FPTreeNode *headerTable, int baseIndex, int headerSize)
{
 FPTreeNode aNode;
 FPTreeNode ancestorNode;
 int *freqItemP;	
 int *indexList;	
 int path;
 int count;
 int i;

 /* create temp header table 
  */
 *conHeader = (FPTreeNode *) malloc (sizeof(FPTreeNode) * conHeaderSize);
 if (*conHeader == NULL) {
        printf("out of memory\n");
        exit(1);
 }
 for (i=0; i < conHeaderSize; i++)
        (*conHeader)[i] = NULL;

 /* create root of the temp FP-tree 
  */
 (*conRoot) = (FPTreeNode) malloc (sizeof(FPNode));
 if (*conRoot == NULL) {
        printf("out of memory\n");
        exit(1);
 }

 /* Initialize the root of the temp FP-tree 
  */
 (*conRoot)->numPath = 1;
 (*conRoot)->parent = NULL;
 (*conRoot)->children = NULL;
 (*conRoot)->hlink = NULL;

 freqItemP = (int *) malloc (sizeof(int) * conHeaderSize);
 if (freqItemP == NULL) {
        printf("out of memory\n");
        exit(1);
 }

 indexList = (int *) malloc (sizeof(int) * conHeaderSize);
 if (indexList == NULL) {
        printf("out of memory\n");
        exit(1);
 }

 aNode = headerTable[baseIndex];

 while (aNode != NULL) {
	ancestorNode = aNode->parent;
	count = 0;

	while (ancestorNode != T) {
		for (i=0; i < conHeaderSize; i++) {