fim_all.cpp

频繁模式挖掘算法

		j=0;
		i=0;
		while (j<tran)
		{
			if (FindInHashTable[Trans.Items[j]] != -1)
			{
				TransactionArray[i].Element  = Trans.Items[j] ;
				TransactionArray[i].Index = FindInHashTable[Trans.Items[j]] ;
				++i;
			}
			++j;
		} // End while (j<TransactionSize)
		sizeofFrequent = i-1;
} // End void ScanForLocation()


void FreeCOFITree(COFITree* COFIRoot)
{

	// Recursive deletion of COFI tree
	if (COFIRoot->child != NULL)
			FreeCOFITree(COFIRoot->child);
	if (COFIRoot->brother != NULL)
			FreeCOFITree(COFIRoot->brother);
	free (COFIRoot);
}

void traverseFPtree(FPTTree* Root)

{

	// Recursive deletion of COFI tree
if (Root != NULL)
{
printf ("Item = %ld, counter = %ld ",Root->Element, Root->counter);
if (Root->child != NULL)
{
	printf ("Child Item = %ld\n",Root->child->Element);
}
else {printf ("No child\n");}
}
if (Root->child != NULL)
		traverseFPtree(Root->child );
	
if (Root->brother != NULL)
		traverseFPtree(Root->brother);


}
/*

void traverseFPtree(FPTTree* Root,long depth,long brothers)
{
	// Recursive deletion of COFI tree
	Root = Root->child ;
	long i = 0;
	while (Root->brother != NULL)
	{
		fprintf(fpout,"%ld,Item,%ld,localfrequany,%ld,Global frequancy,%ld\n",i,Root->Element,Root->counter,F1_Items[FindInHashTable[Root->Element]].Frequency); 
		Root = Root->brother ;
		++i;
	}
}

*/

void FreeFrequentTree(FrequentTree* Root)
{
	// Recursive deletion of COFI tree
	
	if (Root->child != NULL)
			FreeFrequentTree(Root->child);
	if (Root->brother != NULL)
			FreeFrequentTree(Root->brother);
	
	if (Root->counter >= support)
	{
		++DepthArray[Root->depth];
		if (printingflag == 1)
		{
			fprintf(fpout, "%s ", Root->text);
			fprintf(fpout, "(%ld)\n", Root->counter);
		}
	}	
	free (Root);
}



void Generate_frequents (long itemsize, long branchsupport)
{

			FatherF = RootF;
			CurrentF=RootF->child  ;
			NewCurrentF = RootF->child;
			LastBrotherF = RootF->child;
			bool Found;
			
			for (int i=1;i<=itemsize;i++)
				{
					Found = false;
					if (CurrentF != NULL)
					{
						NewCurrentF = CurrentF;
						LastBrotherF = CurrentF;
						Found = SearchFrequentBrother(FrequentPattern[i],NewCurrentF,LastBrotherF);
					}
					if (Found)
					{
						CurrentF = NewCurrentF;
						if (itemsize == i) // only for last item
						CurrentF->counter = CurrentF->counter + branchsupport ; 
					} else
					{

						AddToFrequentTree(FrequentPattern[i],CurrentF,LastBrotherF,FatherF,branchsupport,i+1);
					}

					FatherF=CurrentF;
					CurrentF=CurrentF->child;
				}

			
}

void candidate_generation(FrequentTree* RootNode, int startpoint ,int itemsize, long branchsupport)
{


			FrequentTree* TempNode;
			FatherF = RootNode;
			CurrentF=RootF->child  ;
			NewCurrentF = RootF->child;
			LastBrotherF = RootF->child;
			bool Found;
			TempNode = FatherF;

			for (int i=startpoint;i<itemsize;i++)
				{
					Found = false;
					FatherF = TempNode;
					CurrentF = FatherF->child ;

					if (CurrentF != NULL)
					{
						NewCurrentF = CurrentF;
						LastBrotherF = CurrentF;
						Found = SearchFrequentBrother(COFIPattern[i],NewCurrentF,LastBrotherF);
					}
					if (Found)
					{
						CurrentF = NewCurrentF;
						//if (itemsize == i) // only for last item
						CurrentF->counter = CurrentF->counter + branchsupport ; 
					} else
					{
						
						AddToFrequentTree(COFIPattern[i],CurrentF,LastBrotherF,FatherF,branchsupport,FatherF->depth+1);
					}
					if (i+1 != itemsize)
						candidate_generation(CurrentF,i+1,itemsize,branchsupport);
					
				}

}


long FindNextLocal(long COFIItemlocation, long Originallocation)
{
	long location = Originallocation;
	
	bool found;
	found = false;

	while ((location > COFIItemlocation) && (!found))		
		{
			if ((F1_Items[location].firstCOFI != NULL) && (F1_Items[location].COFIFrequency >= support) && (F1_Items[location].COFIFrequency > F1_Items[location].COFIFrequency1))
				found = true;
			else
				-- location;
		}		
	return location;
}

void MineCOFITree(COFITree* COFIRoot, long itemlocation, long c)
{
	
	long SizeOfFrequent = F1_Size - itemlocation;
	long LocationOfCurrentlocalF = FindNextLocal(itemlocation,F1_Size);
	CurrentF = new FrequentTree;
	FatherF = new FrequentTree;
	NewCurrentF = new FrequentTree;
	LastBrotherF = new FrequentTree;
	RootOrignal = new FrequentTree;

	RootF = (FrequentTree* )malloc(sizeof(FrequentTree));

    RootF->Element = COFIRoot->Element ;
	RootF->depth = 1;
	sprintf(RootF->text, "%ld",COFIRoot->Element);
	RootF->counter = COFIRoot->counter ;
 	RootF->brother = NULL;		
//	RootF->brotherR = NULL;		
	RootF->father   = NULL;
	RootF->next   = NULL;
	RootF->child = NULL;
	RootOrignal = RootF;

	if (LocationOfCurrentlocalF != itemlocation)
	{
	long patternsize;
	
	COFIPattern = (long *)malloc((SizeOfFrequent+1)*sizeof(long));
	COFITree* COFInode;
	COFITree* traverse;
	int counter = 0;
	while (LocationOfCurrentlocalF != itemlocation)
	{
	COFInode = F1_Items[LocationOfCurrentlocalF].firstCOFI;
	while (COFInode != NULL)
			{			
			traverse = COFInode;
			long branchsupport = traverse->counter - traverse->participation  ;
			//COFIPattern[0] = COFIRoot->Element ;
			patternsize = 0;
			while ((traverse  != COFIRoot) && (branchsupport > 0))
				{
				// Item prunning
					COFIPattern[patternsize] = traverse->Element ;				
					traverse->participation = traverse->participation + branchsupport;
					++patternsize;
					F1_Items[FindInHashTable[traverse->Element]].COFIFrequency1 = F1_Items[FindInHashTable[traverse->Element]].COFIFrequency1 + branchsupport;
					traverse = traverse->father ;
				} // end while (traverse->FatherCOFI != root)
			
			COFInode = COFInode->next ;
			if (patternsize > 0)
			{
		
			++GeneralCounter;
			candidate_generation (RootF,0,patternsize,branchsupport);
			RootF = RootOrignal ;

			}
		}  // End (while (COFInode != F1_Items[j].last)
	LocationOfCurrentlocalF = FindNextLocal(itemlocation,LocationOfCurrentlocalF-1);
	++ counter;
	} // end loop (LocationOfCurrentlocalF != itemlocation)
	} // end if (LocationOfCurrentlocalF != itemlocation)
}



int main(int argc, char *argv[])
{
  
  
 char *stopstring;
 printf("COFI-Tree: Mining Frequent patterns using COFI-Tree algorithm\nUniversity of Alberta - Computing Science department\n\n Mining in Process Please wait \n");
 printingflag = 0;
 char inputfilename[81];
 char outputfilename[81];
 DimentionSize = 0;
 Maxtransactionsize = 500;
 sprintf(inputfilename, "%s",argv[1]);
 support = strtol( argv[2], &stopstring, 10 );
 if (argc == 4)
	{
	printingflag = 1;
	sprintf(outputfilename, "%s",argv[3]);
	}
	


 //sprintf(inputfilename, "%s","chess.dat");
 //support = 1000;
	FPTTree* Current = new FPTTree;
	FPTTree* Father = new FPTTree;
	FPTTree* Root = new FPTTree;

	FPTTree* NewCurrent = new FPTTree;
	FPTTree* LastBrother = new FPTTree;
	

	
	for (int i=1;i<500;i++)
		DepthArray[i]=0;


  Candidate_Items = (CandidateStructures *)malloc((500+1)*sizeof(CandidateStructures));
  Trans.Items = (long *)malloc((Maxtransactionsize+1)*sizeof(long));
  TransactionArray = (TransactionRecord *)malloc((Maxtransactionsize+1)*sizeof(TransactionRecord));


  
  
  
  bool Found;
if (printingflag == 1)
{
		if( (fpout  = fopen( outputfilename, "w" )) == NULL )
			printf( "The file 'output' was not opened\n" );
}

	
	if( (fp  = fopen( inputfilename,"r" )) == NULL )
		   
			printf( "The file %s was not opened\n",inputfilename );
	   //else
		//	printf( "The file 'data' was opened\n" );

	  
	   // Initialise the Candidate item list;
	   InitializeItems();
//	   start1 = clock();
	   

	   int j;
	   // Building Candidate 1 Item-Set
       LineRead = 1;
	   ReadingFromText();
	   long index,offset;
	   while( !feof( fp ) )
	   {
		 
		   for (j=0;j<tran;++j)
		   {
			    index = Trans.Items[j]/1000;
				offset = Trans.Items[j]%1000;
				if (Trans.Items[j] > DimentionSize)
					DimentionSize = Trans.Items[j];
				++Candidate_Items[index].ArrayOfCandidates[offset].Frequency;			
	
		   }
		   ReadingFromText();
		   ++LineRead;
		   
		   
	   }
//	   finish1 = clock();
//	   start2 = clock();

//	   duration1 = (double)(finish1 - start1) / CLOCKS_PER_SEC;	   
	   //printf( " Actual Transactions = %ld s \n", LineRead ); 	
	   //printf( " Total run time pass1 %2.1f s \n", duration1 ); 
	   //printf( " Max transactionsize = %ld s \n", mxtransaction ); 
	   //printf( " Dimension = %ld s \n", DimentionSize ); 
	   

	 fclose (fp);
	 No_Of_Frequent1_Items = SizeOf1Frequent();
	 FindInHashTable= (long *)malloc((DimentionSize+1)*sizeof(long));
	// FindInHashTable= (long *)malloc((No_Of_Frequent1_Items+1)*sizeof(long));
	 
	for (int i1=0;i1<=DimentionSize;++i1)
	 {
		FindInHashTable[i1] = -1;
	 }
	 
	if (No_Of_Frequent1_Items > 0)
			 
	{
	 F1_Size = No_Of_Frequent1_Items -1 ;
	 F1_Items = (FrequentStruc *)malloc((No_Of_Frequent1_Items+1)*sizeof(FrequentStruc));
//	 finish1 = clock();
//	 start2 = clock();
	 SortFrequent();
//	 finish2 = clock();
  	 BuildHashTable();
	 Root->brother = NULL;		
	 Root->father = NULL;
	 Root->next = NULL;
	 Root->child = NULL;
long t;

    	free(Candidate_Items);
	 // End Order Items		
		
		// Start Pass II

		if( (fp  = fopen( inputfilename,"r" )) == NULL )
				printf( "The file 'data' was not opened\n" );
	   else
		//	printf+( "The file 'data' was opened for pass II\n" );
	  
	   LineRead = 1;
	   
	   ReadingFromText();
	    while( !feof( fp ) )
	  {
//			startf = clock();	 
			ScanForLocation(New_Index_FrequentStruc);
			t = New_Index_FrequentStruc;
			Sort_Transaction(0,New_Index_FrequentStruc);
			New_Index_FrequentStruc = t;
//			finishf = clock();
//			durationp = (double)(finishf - startf) / CLOCKS_PER_SEC;
//			durationpt = durationp + durationpt;
				Father = Root;
				Current=Root->child  ;
				NewCurrent = Root->child;
				LastBrother = Root->child;
			
			for (int i=New_Index_FrequentStruc;i>=0;i--)
				{
					Found = false;
					
					if (Current != NULL)
					{
						NewCurrent = Current;
						LastBrother = Current;
						
						Found = SearchFTPBrother(TransactionArray[i],NewCurrent,LastBrother);
					}
					if (Found)
					{
						Current = NewCurrent;
						++Current->counter; 
						
					} else
						AddToFTPTree(TransactionArray[i],Current,LastBrother,Father);
					
					Father=Current;
					Current=Current->child;
				}

			ReadingFromText();
			
			
			++LineRead;
				
		}  // End (ReadingIndex < InputSize) Pase II
		fclose (fp);

//traverseFPtree(Root);
//traverseFPtree(Root,0,0);

//finish2 = clock();
//duration1 = (double)(finish2 - start2) / CLOCKS_PER_SEC;	   
//printf( " Total run time Building FP-Tree %2.1f s \n", duration1 ); 	
	COFITree* CurrentCOFI;
	COFITree* FatherCOFI ;
	COFITree* NewCurrentCOFI;
	COFITree* LastBrotherCOFI;

	CurrentCOFI = (COFITree* )malloc(sizeof(COFITree));
	FatherCOFI = (COFITree* )malloc(sizeof(COFITree));
	NewCurrentCOFI = (COFITree* )malloc(sizeof(COFITree));
	LastBrotherCOFI = (COFITree* )malloc(sizeof(COFITree));

	long locationCOFI,c;
	c = 0;

		// Build and Mine COFI trees

		j = 0;
		long COFIItem,loc;
		
		long branchsupport = 0;
		FPTTree* COFInode = F1_Items[j].first;
		FPTTree* traverse;		
		COFITree* COFIRoot ;
		bool foundone;

		while (j < F1_Size)
		{

			COFIItem =	F1_Items[j].Item ;		
			COFInode = F1_Items[j].first;		
			COFIRoot = (COFITree* )malloc(sizeof(COFITree));
			COFIRoot->Element = F1_Items[j].Item;
			COFIRoot->counter = F1_Items[j].Frequency;
			COFIRoot->brother = NULL;		
			COFIRoot->father   = NULL;
			COFIRoot->next   = NULL;
			COFIRoot->child = NULL;
			COFIRoot->participation = 0;
			foundone = false;
	
			//printf(" building %d, in %ld COFI-Tree for item %ld\n",j,F1_Size, COFIRoot->Element);
			while (COFInode != NULL)
			{
				traverse = COFInode;			
				branchsupport = traverse->counter ;
				traverse = COFInode->father;
				while (traverse  != Root)
				{
					locationCOFI = FindInHashTable[traverse->Element];
					F1_Items[locationCOFI].COFIFrequency = F1_Items[locationCOFI].COFIFrequency + branchsupport;										
					if (F1_Items[locationCOFI].COFIFrequency >= support)
						foundone = true;
					traverse = traverse->father ;
				} // end while (traverse->FatherCOFI != root)
				COFInode = COFInode->next ;				
			}  // End (while (COFInode != F1_Items[j].last)
			
			COFIItem =	F1_Items[j].Item ;		
			COFInode = F1_Items[j].first;		

			if (foundone == true)
			{
			while (COFInode != NULL)
			{
			traverse = COFInode;			
			branchsupport = traverse->counter ;
			traverse = COFInode->father;			
			FatherCOFI = COFIRoot;			
			CurrentCOFI= COFIRoot->child  ;
			NewCurrentCOFI = COFIRoot->child ;
			LastBrotherCOFI = COFIRoot->child ;
			
	
			while (traverse  != Root)
				{
				loc = FindInHashTable[traverse->Element];
				if (F1_Items[loc].COFIFrequency >= support)
				{
					Found = false;
					if (CurrentCOFI != NULL)
					{
						NewCurrentCOFI = CurrentCOFI;
						LastBrotherCOFI = CurrentCOFI;
						Found = SearchCOFIBrother(traverse->Element ,NewCurrentCOFI,LastBrotherCOFI);
					}
					if (Found)
					{
						CurrentCOFI = NewCurrentCOFI;
						CurrentCOFI->counter = branchsupport + CurrentCOFI->counter; 
					} else
						AddToCOFITree(traverse->Element ,CurrentCOFI,LastBrotherCOFI,FatherCOFI,branchsupport);

					FatherCOFI=CurrentCOFI;
					CurrentCOFI=CurrentCOFI->child;
				} // end if

					traverse = traverse->father ;
			} // end while (traverse->FatherCOFI != root)

			COFInode = COFInode->next ;
				
		}  // End (while (COFInode != F1_Items[j].last)
			} // end if foundone = true;

			if (COFIRoot->child != NULL)
			{
				++c;
					//printf(" Mining %d, in %ld COFI-Tree for item %ld\n",j,F1_Size, COFIRoot->Element);
				MineCOFITree(COFIRoot,j,c);
				//	traverseCOFI(COFIRoot,0);
				//	traverseFrequent(RootF,0);
				FreeFrequentTree(RootF);
			}
			else
			{
				++DepthArray[1];		
				if (printingflag == 1)
					{
						fprintf(fpout, "%ld ", COFIRoot->Element );
						fprintf(fpout, "(%ld)\n", COFIRoot->counter);
					}
			}
			FreeCOFITree(COFIRoot);		 
			
		 ++j;

		 for (int i=j;i<=F1_Size;++i)
			{
					F1_Items[i].firstCOFI = NULL;
					F1_Items[i].COFIFrequency = 0;		
					F1_Items[i].COFIFrequency1 = 0;	
			}
			

		}// end While (j > 1)

	
	  // printf("--------------------------------------------------------------\n");	   
	  // printf("Total Number of Items = %ld\n", DimentionSize ); 		
	  // printf("Actual Total Number of Transactions = %ld\n", LineRead - 1 ); 			   
	  // printf("Maximum Numbers in one transaction = %ld\n", Maxtransactionsize ); 		
	  // printf("Support threshold = %ld\n", support ); 
	  // printf("--------------------------------------------------------------\n");

	long total = F1_Size+1;	
	int i1 = 1;
	printf ("Number of Frequent %d-patterns: %ld\n", i1,F1_Size+1);
		for (i1=2;i1<500;i1++)
		{
			if (DepthArray[i1] > 0)
			{
				printf ("Number of Frequent %d-patterns: %ld\n", i1,DepthArray[i1]);
				total = total + DepthArray[i1];
			}
		}
	
	
	printf ("Total number of frequent patterns: %ld\n", total);

} // not 1 frequent

//	   finish4 = clock();	   	   		
	  
	   //duration1 = (double)(finish1 - start1) / CLOCKS_PER_SEC;
	   //duration2 = (double)(finish2 - start2) / CLOCKS_PER_SEC;
	  // duration3 = (double)(finish3 - start3) / CLOCKS_PER_SEC;
	  // duration4 = (double)(finish4 - start4) / CLOCKS_PER_SEC;	   	   
//	   duration7 = (double)(finish4 - start1) / CLOCKS_PER_SEC;	   	   

//	   printf( " Total run time %2.1f s \n", duration7 ); 	


	   //fclose (fp); 
	   if (printingflag == 1)
	   {
			fclose (fpout); 
	   }

return 0;

}