fim_all.cpp

频繁模式挖掘算法

/*
 
   Copyright (C) 2003 Mohammad El-Hajj and Osmar R. Zaiane 
                      (University of Alberta, Canada)
                         ALL RIGHTS RESERVED.


  The enclosed software and documentation includes copyrighted works.
  It is submitted exclusively for the Workshop of Frequent Itemset Mining 
  Implementations (FIMI'03) to be held in Melbourne, FL, USA in 
  conjunction with ICDM 2003 on November 19, 2003.

  This code is not to be distributed until further explicit notice by the 
  authors. 

  This code shall not be modified or distributed and the copyright notices 
  should not be deleted from the code or documentation.

  COFI Algorithm Implementation

  Date 26-09-2003  
*/


#include <stdio.h>
#include <fstream.h> 
#include <iostream>
#include <time.h>
#include <malloc.h>
#include <vector>

long Maxtransactionsize;
long DimentionSize;
long ProblemSize;
long support;
long GeneralCounter;
int printingflag;
long mxtransaction;


FILE *fp;
FILE *fpout;

// data structr for a node of the FP-tree
 struct FPTTree
{
  long  Element;
  long   counter;
  FPTTree* child;  
  FPTTree* brother;
  FPTTree* father;
  FPTTree* next;
};

struct COFITree
{
  long  Element;
  long  counter;
  long  participation;
  COFITree* child;
  COFITree* brother;
  COFITree* father;
  COFITree* next;
};

struct FrequentTree
{
  long  Element;
  long  counter;
  char  text[100];
  int depth;
  FrequentTree* child;
  FrequentTree* brother;
  FrequentTree* father;
  FrequentTree* next;
};

FrequentTree* RootOrignal;
struct FrequentStruc
{
  long  Item;
  long   Frequency;  
  long   COFIFrequency;  
  long   COFIFrequency1; 
  FPTTree* first;
  COFITree* firstCOFI;
 };
 


class Transaction
{ 
public : 
       long ID; 
	   long* Items; 	   
}; 
 


struct TransactionRecord
{
  long  Element;
  long  Index;
};

struct ItemsStructure
{
	long Item;
	long Frequency;

};

struct CandidateStructures
{
	ItemsStructure *ArrayOfCandidates;
};


 long* COFIPattern;
 long* FrequentPattern;
 long DepthArray[500];

 CandidateStructures *Candidate_Items;
 FrequentStruc *F1_Items; 
 long No_Of_Frequent1_Items,F1_Size; 
 TransactionRecord *TransactionArray; 
 long* FindInHashTable;
 int Transaction_Frequent_size;
 fstream outfile;
 Transaction Trans;
 int Index_FrequentStruc,New_Index_FrequentStruc;
 FPTTree* First;
 long tran;
 FrequentTree* CurrentF ;
 FrequentTree* FatherF;
 FrequentTree* RootF;
 FrequentTree* NewCurrentF;
 FrequentTree* LastBrotherF;
 


 
//clock_t start1, finish1,start2, finish2,start3, finish3,start4, finish4,start5, finish5,startf, finishf;
//double  duration1,duration2,duration3,duration4,duration5,duration6,duration7,durationp,durationpt;
long LineRead;

//void InitializeItems(long offset, long candidateindex)
void InitializeItems()
{
int i,k;	

	for (i=0;i<=500;++i)
	{
	Candidate_Items[i].ArrayOfCandidates  = (ItemsStructure *)malloc((1000+1)*sizeof(ItemsStructure));
		for (k=0;k<1000;++k)
	{
		
		Candidate_Items[i].ArrayOfCandidates[k].Item =k+(i*1000);
		Candidate_Items[i].ArrayOfCandidates[k].Frequency = 0;
		
				
	}
	}

} // end Initialise Items


long ElementLocation(long element)
{
	long location;
	location = FindInHashTable[element];
	return location;
}

void traverseCOFI(COFITree* Root,int i)

{

	// Recursive deletion of COFI tree
if (Root != NULL)
{
printf ("Item = %ld, depth = %d, counter = %ld ",Root->Element,i,Root->counter);
if (Root->child != NULL)
{
	printf ("Child Item = %ld\n",Root->child->Element);
}
else
{
	printf ("\n");
}
if (Root->brother  != NULL)
{
	printf ("Brother Item = %ld\n",Root->brother->Element);
}
else
{
	printf ("\n");
}
}
if (Root->child != NULL)
		traverseCOFI(Root->child ,i+1);
	
if (Root->brother != NULL)
		traverseCOFI(Root->brother,i);


}


void traverseFrequent(FrequentTree* Root,int i)

{

	// Recursive deletion of COFI tree
if (Root != NULL)
{
printf ("Item = %ld, depth = %d, items = %s, counter = %ld ",Root->Element,i,Root->text ,Root->counter);
if (Root->child != NULL)
{
	printf ("Child Item = %ld\n",Root->child->Element);
}
else {printf ("No child\n");}
}
if (Root->child != NULL)
		traverseFrequent(Root->child ,i+1);
	
if (Root->brother != NULL)
		traverseFrequent(Root->brother,i);


}


long SizeOf1Frequent ()
{
	
	long i,j,k;
	j=0;
	for (i=0;i<=500;++i)
	{
		for (k=0;k<=1000;++k)
			{
				if (Candidate_Items[i].ArrayOfCandidates[k].Frequency >= support)
				{
				++j;					
				}				
			}
	}
	return j;
	
}


void sortfrequent( long lo, long up )
     {
	 int i, j;
     FrequentStruc  tempr;
     while ( up>lo ) {
          i = lo;
          j = up;
          tempr = F1_Items[lo];
          /*** Split file in two ***/
          while ( i<j ) {
               for ( ; F1_Items[j].Frequency > tempr.Frequency; j-- );
               for ( F1_Items[i]=F1_Items[j]; i<j && F1_Items[i].Frequency<=tempr.Frequency; i++ );
               F1_Items[j] = F1_Items[i];
               }
          F1_Items[i] = tempr;
          /*** Sort recursively, the smallest first ***/
          if ( i-lo < up-i ) { sortfrequent(lo,i-1);  lo = i+1; }
               else    { sortfrequent(i+1,up);  up = i-1; }
          }
     }


void Sort_Transaction( long lo, long up )
     {
	 int i, j;
     TransactionRecord  tempr;
     while ( up>lo ) {
          i = lo;
          j = up;
          tempr = TransactionArray[lo];
          /*** Split file in two ***/
          while ( i<j ) 
				{
               for ( ; TransactionArray[j].Index > tempr.Index; j-- );
               for ( TransactionArray[i]=TransactionArray[j]; i<j && TransactionArray[i].Index<=tempr.Index; i++ );
               TransactionArray[j] = TransactionArray[i];
				}
          TransactionArray[i] = tempr;
          /*** Sort recursively, the smallest first ***/
          if ( i-lo < up-i ) { Sort_Transaction(lo,i-1);  lo = i+1; }
               else    { Sort_Transaction(i+1,up);  up = i-1; }
          }
     }


void SortFrequent()
{
		long  i , j,k,d;

	
		j = 0;
		i=0;
		k=0;
		for (d=0;d<=DimentionSize;d++)
		{
		
				if (Candidate_Items[i].ArrayOfCandidates [k].Frequency >= support)
				{
					F1_Items[j].Item = Candidate_Items[i].ArrayOfCandidates[k].Item ;
					F1_Items[j].Frequency  = Candidate_Items[i].ArrayOfCandidates[k].Frequency ;
					F1_Items[j].first = NULL;
					F1_Items[j].firstCOFI = NULL;
					F1_Items[j].COFIFrequency = 0;
					F1_Items[j].COFIFrequency1 = 0;
					++j		;							
				}
				++k;
				if (k%1000 == 0)
				{
					++i;
					k=0;
				}
		}
		sortfrequent(0,j-1);
}

void BuildHashTable()
{
long i;
for (i=0; i<=F1_Size; ++i)
{
	// search for the location of that item	 
	FindInHashTable[F1_Items[i].Item] = i;
} // end for

}


void ReadingFromText()
{
	
char c;
int i;
i=0;

 do {
    int item=0, pos=0;
    c = getc(fp);
    while((c >= '0') && (c <= '9')) {
      item *=10;
      item += int(c)-int('0');
      c = getc(fp);
      pos++;
    }
    if(pos) {
		Trans.Items[i] = item;
		++i;
		}
  }while(c != '\n' && !feof(fp));
 tran = i;
 if (tran > mxtransaction)
	 mxtransaction = tran;

}



bool SearchFrequentBrother(long Item,FrequentTree*& NewCurrent,FrequentTree*& LastBrother)
{

bool found,over;
found = false;
over = false;
LastBrother = NULL;

	while ((NewCurrent != NULL) && (!found) && (!over))
	{
		if (NewCurrent->Element == Item)
		found = true;
		else if (F1_Items[FindInHashTable[Item]].COFIFrequency > F1_Items[FindInHashTable[NewCurrent->Element]].COFIFrequency)
		over = true;
		else 
		{
			LastBrother = NewCurrent;
			NewCurrent  = NewCurrent->brother;
		}
	} // End while ((Current != NULL) && (!found))
return found;

} // End bool SearchFTPBrother(NewTransactionArray[i],Current,NewCurrent)



bool SearchCOFIBrother(long Item,COFITree*& NewCurrent,COFITree*& LastBrother)
{
bool found,over;
found = false;
over = false;
LastBrother = NULL;

	while ((NewCurrent != NULL) && (!found) && (!over))
	{
		if (NewCurrent->Element == Item)
		found = true;
		else if (F1_Items[FindInHashTable[Item]].COFIFrequency > F1_Items[FindInHashTable[NewCurrent->Element]].COFIFrequency)
		over = true;
		else 
		{
			LastBrother = NewCurrent;
			NewCurrent  = NewCurrent->brother;
		}
	} // End while ((Current != NULL) && (!found))
return found;
} // End bool SearchFTPBrother(NewTransactionArray[i],Current,NewCurrent)


bool SearchFTPBrother(struct TransactionRecord Item,FPTTree*& NewCurrent,FPTTree*& LastBrother)
{
bool found,over;
found = false;
over = false;
LastBrother = NULL;

	while ((NewCurrent != NULL) && (!found) && (!over))
	{
		if (NewCurrent->Element == Item.Element)
		found = true;
		else if (F1_Items[FindInHashTable[Item.Element]].COFIFrequency > F1_Items[FindInHashTable[NewCurrent->Element]].Frequency)
		over = true;
		else 
		{
			LastBrother = NewCurrent;
			NewCurrent  = NewCurrent->brother;
		}
	} // End while ((Current != NULL) && (!found))


return found;
} // End bool SearchFTPBrother(NewTransactionArray[i],Current,NewCurrent)

void AddNewChildWithBrother(struct TransactionRecord item,FPTTree* FatherNode,FPTTree* LastBrother,FPTTree*& NewCurrent)
{

	FPTTree* node = new FPTTree;
	node->Element = item.Element;
	node->child = NULL;
	node->next = NULL;
	node->counter = 1;
	node->father = FatherNode;
	
	if (LastBrother == NULL)
	{
	node->brother = FatherNode->child;		
	FatherNode->child = node;
	}
	else
	{
		node->brother = LastBrother->brother;	
		LastBrother->brother = node;
	}
	NewCurrent = node;

}

void AddNewChildNoBrother(struct TransactionRecord item,FPTTree* FatherNode,FPTTree*& NewCurrent)
{
	FPTTree* node = new FPTTree;
	node->Element = item.Element;
	node->brother = NULL;	
	node->child = NULL;		
	node->next = NULL;
	node->counter = 1;
	node->father = FatherNode;
	FatherNode->child = node;
	NewCurrent = node;
}

void AddCOFINewChildWithBrother(long item,COFITree* FatherNode,COFITree* LastBrother,COFITree*& NewCurrent, long branchsupport)
{

	NewCurrent = (COFITree* )malloc(sizeof(COFITree));
	NewCurrent->Element = item;
	NewCurrent->child = NULL;	
	NewCurrent->next = NULL;
	NewCurrent->counter = branchsupport;
	NewCurrent->father = FatherNode;	
	NewCurrent->participation = 0;
	if (LastBrother == NULL)
	{
	NewCurrent->brother = FatherNode->child;		
	FatherNode->child = NewCurrent;
	}
	else
	{
		NewCurrent->brother = LastBrother->brother;	
		LastBrother->brother = NewCurrent;
	}
}


void AddCOFINewChildNoBrother(long item,COFITree* FatherNode,COFITree*& NewCurrent, long branchsupport)
{

	NewCurrent = (COFITree* )malloc(sizeof(COFITree));
	NewCurrent->Element = item;
	NewCurrent->child = NULL;	
	NewCurrent->brother = NULL;
	NewCurrent->next = NULL;
	NewCurrent->counter = branchsupport;
	NewCurrent->father = FatherNode;
	NewCurrent->participation = 0;
	FatherNode->child = NewCurrent;


}

void AddFrequentNewChildWithBrother(long item,FrequentTree* FatherNode,FrequentTree* LastBrother,FrequentTree*& NewCurrent, long branchsupport, long depth)
{

	NewCurrent = (FrequentTree* )malloc(sizeof(FrequentTree));
	sprintf(NewCurrent->text, "%s %ld",FatherNode->text,item);
	NewCurrent->Element = item;
	NewCurrent->child = NULL;
	NewCurrent->depth = depth;
	NewCurrent->next = NULL;
	NewCurrent->counter = branchsupport;
	NewCurrent->father = FatherNode;	

		if (LastBrother == NULL)
	{
	NewCurrent->brother = FatherNode->child;		
	FatherNode->child = NewCurrent;
	}
	else
	{
		NewCurrent->brother = LastBrother->brother;	
		LastBrother->brother = NewCurrent;
	}
}


void AddFrequentNewChildNoBrother(long item,FrequentTree* FatherNode,FrequentTree*& NewCurrent, long branchsupport,long depth)
{

	NewCurrent = (FrequentTree* )malloc(sizeof(FrequentTree));
	sprintf(NewCurrent->text, "%s %ld",FatherNode->text,item);
	NewCurrent->Element = item;
	NewCurrent->depth = depth;
	NewCurrent->brother = NULL;
	NewCurrent->child = NULL;		
	NewCurrent->next = NULL;
	NewCurrent->counter = branchsupport;
	NewCurrent->father = FatherNode;
	FatherNode->child = NewCurrent;
	
}

void UpdateTable(struct TransactionRecord item,FPTTree*& NewCurrent)
{
	int loc = item.Index;
	
		if (F1_Items[loc].first == NULL)
			F1_Items[loc].first = NewCurrent;
		 else
			{
				NewCurrent->next = F1_Items[loc].first;
				F1_Items[loc].first= NewCurrent;
			}

}

void UpdateCOFITable(long item,COFITree*& NewCurrent,long branchsupport)
{
	long loc = FindInHashTable[item];
	
		if (F1_Items[loc].firstCOFI  == NULL)
			F1_Items[loc].firstCOFI = NewCurrent;
		 else
			{
				NewCurrent->next = F1_Items[loc].firstCOFI ;
				F1_Items[loc].firstCOFI =NewCurrent;
			}
}

void AddToFTPTree(struct TransactionRecord Item,FPTTree*& Current,FPTTree* LastBrother,FPTTree* Fathernode)
{
	if (Fathernode->child == NULL)
			AddNewChildNoBrother(Item,Fathernode,Current);
	else
	{
			AddNewChildWithBrother(Item,Fathernode,LastBrother,Current);

	}
	 UpdateTable(Item,Current);
} // End AddToFTPTree(NewTransactionArray[i],FPTTree*& Current);

void AddToCOFITree(long Item,COFITree*& Current,COFITree* LastBrother,COFITree* Fathernode, long branchsupport)
{
	if (Fathernode->child == NULL)
			AddCOFINewChildNoBrother(Item,Fathernode,Current,branchsupport);
	else
	{
			AddCOFINewChildWithBrother(Item,Fathernode,LastBrother,Current,branchsupport);
	}
	 UpdateCOFITable(Item,Current,branchsupport);
} // End AddToFTPTree(NewTransactionArray[i],FPTTree*& Current);

void AddToFrequentTree(long Item,FrequentTree*& Current,FrequentTree* LastBrother,FrequentTree* Fathernode, long branchsupport, long depth)
{
	if (Fathernode->child == NULL)
			AddFrequentNewChildNoBrother(Item,Fathernode,Current,branchsupport,depth);
	else
				AddFrequentNewChildWithBrother(Item,Fathernode,LastBrother,Current,branchsupport,depth);
} // End AddToFTPTree(NewTransactionArray[i],FPTTree*& Current);


void ScanForLocation(int& sizeofFrequent)
{
		int i,j;