fp_tree.cpp

关联规则挖掘算法FPtree的源代码

/*
   Author:  Jianfei Zhu  
            Concordia University
   Date:    Feb. 10, 2004

Copyright (c) 2004, Concordia University, Montreal, Canada
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

   - Redistributions of source code must retain the above copyright notice,
       this list of conditions and the following disclaimer.
   - Redistributions in binary form must reproduce the above copyright
       notice, this list of conditions and the following disclaimer in the
       documentation and/or other materials provided with the distribution.
   - Neither the name of Concordia University nor the names of its
       contributors may be used to endorse or promote products derived from
       this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
THE POSSIBILITY OF SUCH DAMAGE.

*/

#include <stdlib.h>
#include <assert.h>
#include <math.h>
#include "buffer.h"
#include "common.h"

template <class T> void swap(T* k, T* j)
{
	T temp;
	temp = *j;
	*j = *k;
	*k = temp;
}

int findpivot(const int& i, const int& j) {return (i+j)/2;}

int partition(int* array, int* temp, int l, int r, int pivot)
{
	do {
		while (array[++l] > pivot);
		while (r && array[--r] < pivot);
		swap(array+l, array+r);
		swap(temp+l, temp+r);
	}while (l < r);
	swap(array + l, array + r);
	swap(temp + l, temp + r);
	return l;
}

//Bug! Dec. 4, 2003
void inssort(int* array, int* temp, int i, int j)
{
	for (int k=i+1; k<=j; k++)
		for (int m=k; (m>i) && (array[m] > array[m-1]); m--)
		{
			swap(array+m, array+m-1);
		    swap(temp+m, temp+m-1);
		}
}

void sort(int *array, int* temp, int i, int j)
{
	if(j-i < SORTHRESH) inssort(array, temp, i, j);
	else
	{
		int pivotindex = findpivot(i, j);
		swap(array+pivotindex, array+j);
		swap(temp+pivotindex, temp+j);
		int k = partition(array, temp, i-1, j, array[j]);
		swap(array+k, array+j);
		swap(temp+k, temp+j);
		if((k-i)>1) sort(array, temp, i, k-1);
		if((j-k)>1) sort(array, temp, k+1, j);
	}
}

void update_mfi_trees(int treeno)
{
	int i, j;
	for(i=0; i<treeno; i++)
	{
		for(j = list->top-1; j >mfitrees[i]->posi+1; j--)
			current_fi[mfitrees[i]->order[list->FS[j]]] = true;

		mfitrees[i]->insert(current_fi, list->top-1-mfitrees[i]->posi-1);
	}
}

void update_cfi_trees(int treeno, int Count)
{
	int i, j;
	for(i=0; i<treeno; i++)
	{
		for(j = list->top-1; j >cfitrees[i]->posi+1; j--)
			current_fi[cfitrees[i]->order[list->FS[j]]] = true;

		if(list->top-1-cfitrees[i]->posi-1>0)
                    cfitrees[i]->insert(current_fi, Count, list->top-1-cfitrees[i]->posi-1);
	}
}

stack::stack(int length, bool close)
{
	top= 0; 
	FS = new int[length];
	if(close)
		counts = new int[length];
	else
		counts = NULL;
}

stack::~stack()
{
	delete []FS;
}

void stack::insert(FI_tree* fptree)
{
	for(Fnode* node=fptree->Root->leftchild; node!=NULL; node=node->leftchild)
	{
		FS[top]=node->itemname; 
		top++;
	}
}

void CFI_tree::init(memory* close_buf, FI_tree* fp_tree, CFI_tree* old_LClose, Cnode* node, int Posi)
{	
	int i;

	CloseNo=0;

	order = fp_tree->order;
	table = fp_tree->table;
	itemno = fp_tree->itemno;
	posi = Posi;
	Close_buf = close_buf;
	Root = (Cnode*)Close_buf->newbuf(1, sizeof(Cnode));
	Root->init(NULL, -1, 0, 0);
	head = (Cnode**)Close_buf->newbuf(itemno, sizeof(Cnode*));
	for(i=0; i<itemno; i++)
		head[i] = NULL;
	if(old_LClose && node)		
	{
		int has, current;
		bool* origin;
		Cnode* link, *parent;
		int* old_order;

		old_order = old_LClose->order;
		current = old_order[node->itemname];

		origin = new bool[current];
		assert(origin!=NULL);

		for(i=0; i<current; i++) origin[i]=false;
		
		for(link=node; link!=NULL; link=link->next)
		{	
			has=0;
			for(parent=link->par; parent->itemname!=-1; parent=parent->par)
				if(order[parent->itemname]!=-1)
				{
					origin[order[parent->itemname]]=true;
					has++;
				}

			if(has)
				insert(origin, link->count, has);
		}

		delete []origin;
	}
}

bool CFI_tree::is_subset(int Count)const
{
	int i, *FS;
	Cnode* temp;

	FS = list->FS;
	if(list->top==posi+2&&head[order[FS[posi+1]]])
	{
		for(temp=head[order[FS[posi+1]]];temp!=NULL; temp=temp->next)
			if(temp->count >= Count)return true;
		return false;
	}

	Cnode* temp2;
	for(temp=head[order[FS[posi+1]]];temp!=NULL; temp=temp->next)
	{
		if(temp->level<list->top-1-posi || temp->count<Count)continue;
		temp2=temp->par;
		for(i=list->top-1; i>=posi+2; i--)
		{
            for(; temp2->itemname!=-1 && order[temp2->itemname]>order[FS[i]]&&temp2->level>=i-posi-1; temp2=temp2->par);
      		if(temp2->itemname!=FS[i])break;
			if(i==posi+2)return true;
		}
	}

	return false;
}

void CFI_tree::insert(bool* origin, int Count, int has)
{
	int i=0, j=1, k=0;
	Cnode* root=Root, *temp=NULL;

	if(posi==-1)CloseNo++;

	while(k<has)
	{
		if(origin[i])
		{
			origin[i]=false;
			k++;
			temp = root->leftchild;
			if(temp == NULL)break;
			for(; temp->rightsibling!=NULL; temp=temp->rightsibling)
				if(temp->itemname==table[i])break;
			if(temp->itemname==table[i])	    
			{
				if(temp->count <Count)temp->count = Count;
				root=temp; 
			}else break;          //temp->rightsibling == NULL
		}
		i++;
	}

	if(k==has && root==temp)return;

	origin[i] = true;
	for(j=i; k<=has; j++)
		if(origin[j])
		{
			origin[j] = false;
			root=root->append(this, temp, table[j], k, Count);
			k++;
		}
}

void CFI_tree::insert(int* mfi, int start, int end, int Count)  //compact info
{
	int i, j=1, k=0;
	Cnode* root=Root, *temp=NULL;

	if(posi==-1)CloseNo++;

	if(start==end || start+1==end)
		return;
//Modified on Feb. 10, 2004
	
	i = start+1;

	while(i<end)
	{
		k++;
		temp = root->leftchild;
		if(temp == NULL)break;
		for(; temp->rightsibling!=NULL; temp=temp->rightsibling)
			if(temp->itemname==mfi[i])break;
		if(temp->itemname==mfi[i])		    //temp->rightsibling == NULL
		{
			if(temp->count <Count)temp->count = Count;
			root=temp; 
		}else break;
		i++;
	}

//Modified on Feb. 10, 2004
	if(i!=end)
		for(j=i; j<end; j++)
		{
			root=root->append(this, temp, mfi[j], k, Count);
			k++;
		}
}
//Patch  Dec. 4

void CFI_tree::order_FS(int* FS, int start, int end)
{     
        int i;
                
	for(i = start; i<end; i++)
		if(order[FS[i]]>order[FS[i+1]])break;
	if(i==end)return;

	for (int k=start+1; k<=end; k++)
		for (int m=k; (m>start) && (order[FS[m]] < order[FS[m-1]]); m--)
			swap(FS+m, FS+m-1);
}

bool CFI_tree::generate_close(int new_item_no, int Count, FSout* fout)
{
	int i, whole, temp = Count;
	
	if(list->top>1)
		temp=list->counts[list->top-2];
	
	whole = list->top+new_item_no;
	for(i=list->top; i<whole && list->counts[i]==Count; i++);
	list->top = i;

	ITlen[i-1]++;
	if(fout)
		fout->printSet(i, list->FS, Count);

//	insert(list->FS, posi+1, i, Count);
//	update_cfi_trees(posi+1, Count);
	update_cfi_trees(posi+2, Count);  //Modified on Oct. 10, 2003

	if(i==whole && temp == Count)
		return true;	

	while(i<whole)
	{
		Count = list->counts[i];
		for(; i<whole && list->counts[i]==Count; i++);
		list->top = i;

//Patch Dec. 4
		order_FS(list->FS, posi+2, i-1);
		if(!is_subset(Count))
		{
			ITlen[i-1]++;
			if(fout)
				fout->printSet(i, list->FS, Count);
//			insert(list->FS, posi+1, i, Count);
//			update_cfi_trees(posi+1, Count);
			update_cfi_trees(posi+2, Count);   //Modified on Oct. 10, 2003
		}else{
		}
	}

	return false;
}

void MFI_tree::init(memory* max_buf, FI_tree* fp_tree, MFI_tree* old_LMFI, Mnode* node, int Posi)
{	
	int i;

	MFSNo=0;

	order = fp_tree->order;
	table = fp_tree->table;
	itemno = fp_tree->itemno;
	posi = Posi;
	Max_buf = max_buf;
	Root = (Mnode*)Max_buf->newbuf(1, sizeof(Mnode));
	Root->init(NULL, -1, 0);
	head = (Mnode**)Max_buf->newbuf(itemno, sizeof(Mnode*));
	for(i=0; i<itemno; i++)
		head[i] = NULL;

	if(old_LMFI && node)
	{
		int has, current;
		bool* origin;
		Mnode* link, *parent;
		int* old_order;

		old_order = old_LMFI->order;
		current = old_order[node->itemname];

		origin = new bool[current];
		assert(origin!=NULL);

		for(i=0; i<current; i++) origin[i]=false;
		
		for(link=node; link!=NULL; link=link->next)
		{	
			has=0;
			for(parent=link->par; parent->itemname!=-1; parent=parent->par)
				if(order[parent->itemname]!=-1)
				{
					origin[order[parent->itemname]]=true;
					has++;
				}

			if(has)
				insert(origin, has);
		}

		delete []origin;
	}
}

bool MFI_tree::is_subset()
{
	int i;
	int *FS;

	FS = list->FS;
	if(list->top==posi+2&&head[order[FS[posi+1]]])return true;

	Mnode* temp, *temp2;
	for(temp=head[order[FS[posi+1]]];temp!=NULL; temp=temp->next)
	{
		if(temp->level<list->top-1-posi)continue;
		temp2=temp->par;
		for(i=list->top-1; i>=posi+2; i--)
		{
            for(; temp2->itemname!=-1 && order[temp2->itemname]>order[FS[i]]&&temp2->level>=i-posi-1; temp2=temp2->par);
      		if(temp2->itemname!=FS[i])break;
			if(i==posi+2)return true;
		}
	}

	return false;
}

void MFI_tree::insert(bool* origin, int has)
{
	int i=1, j=1, k=0;
	
	if(posi==-1)MFSNo++;

	Mnode* root=Root;
	Mnode* temp=NULL;
	i=0;
	while(k<has)
	{
		if(origin[i])
		{
			origin[i]=false;
			k++;
			temp = root->leftchild;
			if(temp == NULL)break;
			for(; temp->rightsibling!=NULL; temp=temp->rightsibling)
				if(temp->itemname==table[i])break;
			if(temp->itemname==table[i])root=temp;    //temp->rightsibling == NULL
			else break;
//			if(k==has)return;
		}
		i++;
	}
	if(k==has && root==temp)return;

	origin[i] = true;
	for(j=i; k<=has; j++)
		if(origin[j])
		{
			origin[j] = false;
			root=root->append(this, temp, table[j], k);
			k++;
		}
}

void MFI_tree::insert(int* mfi, int start, int end)  //compact info
{
	int i, j=1, k=0;
	Mnode* root=Root, *temp=NULL;

	if(posi==-1)MFSNo++;

//Modified on Feb. 10, 2004
	if(start==end) return;

	i = start+1;
	while(i<end)
	{
		k++;
		temp = root->leftchild;
		if(temp == NULL)break;
		for(; temp->rightsibling!=NULL; temp=temp->rightsibling)
			if(temp->itemname==mfi[i])break;
		if(temp->itemname==mfi[i])root=temp;    //temp->rightsibling == NULL
		else break;
		i++;
	}

//Modified on Feb. 10, 2004
	if(i!=end)
	{ 
		for(j=i; j<end; j++)
		{
			root=root->append(this, temp, mfi[j], k);
			k++;
		}
	}
}

void FI_tree::init(int old_itemno, int new_itemno)
{
	int i;

	Root = (Fnode*)fp_buf->newbuf(1, sizeof(Fnode));
	Root->init(NULL, -1, 0);
//	Root = new Fnode(-1, 0, NULL);
	if(old_itemno!=-1)
	{
		order = (int*)fp_buf->newbuf(ITEM_NO, sizeof(int));
		count = (int*)fp_buf->newbuf(old_itemno, sizeof(int));
		table = (int*)fp_buf->newbuf(old_itemno, sizeof(int));
		for (i=0; i<old_itemno; i++)
		{
			order[i]=-1;
			count[i] = 0;
			table[i] = i;
		}
		for (; i<ITEM_NO; i++)
			order[i]=-1;
	}

	itemno = new_itemno;
	if(new_itemno!=0)
		head = (Fnode**)fp_buf->newbuf(itemno, sizeof(Fnode*));
}

void FI_tree::scan1_DB(Data* fdat)
{
	int i,j;
	int net_itemno=0;
	int *counts;

	counts= new int[ITEM_NO];
	assert(counts!=NULL);

	for(i=0; i<ITEM_NO; i++)
		counts[i] = 0;

	Transaction *Tran = new Transaction;
	assert(Tran!=NULL);

	while(Tran = fdat->getNextTransaction(Tran))
	{	
		for(int i=0; i<Tran->length; i++) 
		{
			if(Tran->t[i]>=ITEM_NO)
			{
				ITEM_NO = 2*Tran->t[i];
				int* temp = new int[2*Tran->t[i]];
				for(j=0; j<=net_itemno; j++)
					temp[j] = counts[j];
				for(; j<ITEM_NO; j++)
					temp[j] = 0;
				delete []counts;
				counts=temp;
				net_itemno=Tran->t[i];
			}else
				if(net_itemno<Tran->t[i])
					net_itemno = Tran->t[i];
			counts[Tran->t[i]]++;
		}
		TRANSACTION_NO++;
	}

	ITEM_NO = net_itemno+1;

//	cout << "The dataset contains " << TRANSACTION_NO << " transactions and "
//       << "the largest item is " << net_itemno << endl;

//	THRESHOLD = ceil (TRANSACTION_NO/100000.0 * THRESHOLD);
//	cout << "The minimum support is "<<THRESHOLD<<endl;

	order = (int*)fp_buf->newbuf(ITEM_NO, sizeof(int));
	table = (int*)fp_buf->newbuf(ITEM_NO, sizeof(int));
	count = (int*)fp_buf->newbuf(ITEM_NO, sizeof(int));
	for (i=0; i<ITEM_NO; i++)
	{
		order[i]=-1;
		count[i] = counts[i];
		table[i] = i;
	}

	sort(count, table, 0, ITEM_NO-1);
	
	for (i =0; i<ITEM_NO&&count[i] >= THRESHOLD; i++);

	itemno = i;

	for (j=0; j<itemno; j++)
	{
		count[j]=counts[table[j]];  
		order[table[j]]=j;
	}

//	for(int k=0; k<ITEM_NO; k++)cout<<order[k]<<"  "; cout<<endl;
//	for( k=0; k<itemno; k++)cout<<table[k]<<"  "; cout<<endl;

	head = (Fnode**)fp_buf->newbuf(itemno, sizeof(Fnode*));

	if(itemno>SUDDEN+5)
	{
		array = new int*[itemno-1-SUDDEN];
		for(i=0; i<itemno-1-SUDDEN; i++)
		{
			array[i] = new int[itemno-1-i];
			for(j=0; j<itemno-1-i; j++)
				array[i][j] = 0;
		}
	}else array = NULL;

// The following is for the case when ITEM_NO is very big and fptree->itemno is very small
	order_item = new int[itemno];
	item_order = new int[ITEM_NO];
	for(i=0; i<itemno; i++)
	{
		head[i] = (Fnode*)fp_buf->newbuf(1, sizeof(Fnode));
		head[i]->init(NULL, i, count[i]);		

		order_item[i]=table[i];
		table[i]=i;
		item_order[i] = order[i];
		order[i]=i;
	}
	for(;i<ITEM_NO; i++)