fptn20.c

关联规则的频繁项集算法bomo的源代码

/* fptN20.c (release mode) */
/* Mining N-most interesting large itemsets */
/* array of linked lists for support[], largeItemset[][][] and numLarge[] */
/* redo mining if there is not enough k-itemsets */
/* modifications: 1, 6, 7, 8, 4, 9, 13, 14 */
/* N21.c + N16.c */

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <sys/resource.h>
#include <sys/times.h>
#include <unistd.h>


/***** Data Structure *****/
typedef struct FPnode *FPTreeNode;

typedef struct Childnode *childLink;
typedef struct Childnode {
	FPTreeNode node;
	childLink next;
} ChildNode;

typedef struct FPnode {
        /* int leaf; */
        int item;
        int count;
	int numPath; 
	FPTreeNode parent;
        childLink children;
        FPTreeNode hlink;
} FPNode;


typedef struct Itemsetnode *LargeItemPtr;
typedef struct Itemsetnode {
	int support;
	int *itemset;
	LargeItemPtr next;
} ItemsetNode;
		

/***** Global Variables *****/
int startHeader;
int round=0;

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

int *limit;
int *thresholdK;

FPTreeNode root=NULL;
FPTreeNode *headerTableLink;
int headerTableSize;

int N;
int expectedK;
int realK;
int threshold;
int oldThreshold;
int numItem;
int numTrans;
float decreaseRate;
char dataFile[50];
char treeFile[50];
char outFile[50];

int *arrThresholdK;


void destroyTree(FPTreeNode node, int level)
{
 childLink temp1, temp2;

 if (node == NULL) return;

 temp1 = node->children;
 while(temp1 != NULL) {
	temp2 = temp1->next;
	destroyTree(temp1->node, level+1);
	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(support1);
 free(largeItem1);
 free(limit);
 destroyTree(root, 1);
 free(headerTableLink);
 free(thresholdK);

 return;
}


/* swap x th element and i th element */
void swap2(int *support, int x, int i)
{ 
 int temp; 

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

/* Quick sort support[] and the corresponding itemset[] in descending order.
 * Parameters:
 *      support[]	-> array to be sorted
 *      itemset[]	-> array to be sorted
 *      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
 */
void q_sort2(int *support, 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 1st element value larger than the pivot's */
	pass=1;
	while(pass==1) {
		if(++low<size) {
			if(support[low] > support[pivot])
				pass=1;
			else pass=0;
		} else pass=0;
	} 

	/* find out 1st element value 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)
		swap2(support, low, high);
 } while(low<=high);

 swap2(support, pivot, high);

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

void visitTree(FPTreeNode T, int level)
{
 childLink child;

 if (level == realK-1) {
 	child = T->children; 
 	while (child != NULL) {
		arrThresholdK[N] = child->node->count;		
		q_sort2(arrThresholdK, 0, N, N+1);

		child = child->next;
	}

	return;
 }

 child = T->children;
 while (child != NULL) {
	visitTree(child->node, level+1);
	child = child->next;
 }

 return;
}


void initThresholdK()
{
 int i;
 int level=0;

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

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

 threshold = 1;
 for (i=0; i <= N; i++) {
	arrThresholdK[i] = threshold;
 }

 visitTree(root, level);

 for (i=1; i < realK; i++) {
	thresholdK[i] = arrThresholdK[N-1];
 }

 free(arrThresholdK);
 
 threshold = thresholdK[realK-1];

 return;
}


/* swap x th element and i th element */
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;
}

/* Quick sort support[] and the corresponding itemset[] in descending order.
 * Parameters:
 *      support[]	-> array to be sorted
 *      itemset[]	-> array to be sorted
 *      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
 */
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 {
	/* find out 1st element value larger than the pivot's */
	pass=1;
	while(pass==1) {
		if(++low<size) {
			if(support[low] > support[pivot])
				pass=1;
			else pass=0;
		} else pass=0;
	} 

	/* find out 1st element value 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;
}


/* Quick sort indexList[] and freqItemP[] in ascending order.
 * Parameters:
 *      indexList[]     -> array to be sorted
 *      freqItemP[]     -> array to be sorted
 *      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
 */
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 {
        /* find out 1st element value 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 1st element value 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;

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

 aLargeItemset->support = patternSupport;

 for (i=0; i <= index; i++) {
	aLargeItemset->itemset[i] = pattern[i];
 }

 aLargeItemset->next = NULL;

 aNode = largeItemset[index];
 if (aNode == NULL) {
	largeItemset[index] = aLargeItemset;
 } else {
 	while ((aNode != NULL) && (aNode->support > patternSupport)) {
		previous = aNode;
		aNode = aNode->next;
 	}

 	if (previous != NULL) {
		previous->next = aLargeItemset;
		aLargeItemset->next = aNode;
	} else {
		aLargeItemset->next = largeItemset[index];
		largeItemset[index] = aLargeItemset;
	}
 }

 (numLarge[index])++;

 if (numLarge[index] >= limit[index]) {
        aNode = largeItemset[index];
        for (i=1; i < limit[index]; i++)
                aNode = aNode->next;

        if (thresholdK[index] < aNode->support) {
                thresholdK[index] = aNode->support;

		threshold = thresholdK[realK-1];
		for (i = realK-2; i > 0; i--)
			if (thresholdK[i] < threshold)
				threshold = thresholdK[i];
	}
 }
 
 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;

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

 for (j=0; j < baseSize; j++)
	pattern[j+1] = base[j];

 for (i=start; i < itemListSize; i++) {
	pattern[0] = itemList[i];

	if ((baseSize > 0) && (support[i] < oldThreshold)
		&& (support[i] >= thresholdK[baseSize]))
		addToLargeList(pattern , support[i], baseSize);

	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 (ptr == length) return;

 if (T->children == NULL) {
	/* T has no children */

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

	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;

	hNode = headerTableLink[indexList[ptr]];
	if (hNode == NULL) {
		headerTableLink[indexList[ptr]] = newNode->node;
	} else {
		while (hNode != NULL) {
			hPrevious = hNode;
			hNode = hNode->hlink;
		}

		hPrevious->hlink = newNode->node;
	}

	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) {
		/* 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);
		}

		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;
		
		hNode = headerTableLink[indexList[ptr]];
		if (hNode == NULL)
			headerTableLink[indexList[ptr]] = newNode->node;
		else {
			while (hNode != NULL) {
				hPrevious = hNode;
				hNode = hNode->hlink;
			}
			hPrevious->hlink = newNode->node;
		}

		insert_tree(freqItemP, indexList, count, ptr+1, length, 
					newNode->node, headerTableLink, path);
		(*path)++;
		
		T->numPath += *path;

	} else {
		/* match an existing child of T */

		aNode->node->count += count;

		insert_tree(freqItemP, indexList, count, ptr+1, length, 
				aNode->node, headerTableLink, path);
		T->numPath += *path; 
	}
 }


 return;
}


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

 /* build 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 FP-tree */
 (*conRoot) = (FPTreeNode) malloc (sizeof(FPNode));
 if (*conRoot == NULL) {
        printf("out of memory\n");
        exit(1);
 }

 (*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);
 }