l maxpattern2.cpp

最大频繁项集挖掘算法。运行前需将release中的data和result数据拷贝到上一级目录下。

					pMemory->pMBlock=pBlock;
					nNodeCount=0;
				}
				pInsert=pBlock+nNodeCount;
				nNodeCount++;
				nCount1++;
				pInsert->fFrequency=1;
				pInsert->nNumber=nN;

				// Link it to brother link
				pInsert->pHorizon=pQuery;
				pPre->pHorizon=pInsert;

				// Set ancestor node
				pAnces=pInsert;

				// Go to next item
				arrnTick[i]=0;
				i++;

				while(i<=nCount)
				{
					// Get the head-node
					nN=arrnTick[i];

					// Create a new fpnode and initialize it
					if(nNodeCount==MINNODECOUNT)
					{
						pTempMemory=pMemory;
						pMemory=new MEMORYBLOCK;
						pMemory->pNext=pTempMemory;
						pBlock=new FPTREENODE[MINNODECOUNT];
						pMemory->pMBlock=pBlock;
						nNodeCount=0;
					}
					pQuery=pBlock+nNodeCount;
					nNodeCount++;
					nCount1++;
  					pQuery->nNumber=nN+nItemCount;
					pQuery->fFrequency=1;
					pQuery->pHorizon=pQuery;

					// Set ancestor-node
					pAnces->pVertical=pQuery;
					pAnces=pQuery;

					// Inspect next item
					arrnTick[i]=0;
					i++;
				}

				// End vertical link
				pAnces->pVertical=0;

				break;
			}

			// Have finded it
			pQuery->fFrequency++;
			pAnces=pQuery;

			// Inspect next item
			arrnTick[i]=0;
			i++;
		}while(i<=nCount);
	}

	// Close the opened file
	fclose(fileData);

	// Print the number of nodes in fptree
	printf("%d nodes, %d frequent items ... ",nCount1,nItemCount);
	fprintf(fileResult,"Count of frequent item: %d\n\n",nItemCount);

	// Free allocated memory
	delete[]arrnTick;

	// Reverse ancestor-link and create horizontal link
	ReverseLink();
}

// Reverse ancestor-link and create horizontal link
void ReverseLink()
{
	FPTREENODE **arrpNode,*pNode,*pRear;
	int nP;

	// Check tree is void
	if(!pRoot->pVertical) return;

	// Create used type and initialize it
	arrpNode=new FPTREENODE *[nPatternLength+1];
	pNode=pRoot;
	nP=0;

	// Reversing process
	while(1)
	{
		// Brother-link not end
		if(pNode)
		{
			pRear=pNode->pVertical;
			while(pRear)
			{
				arrpNode[nP]=pNode;

				pNode=pRear->pHorizon;
				pRear->pHorizon=0;
				pRear->nNumber-=nItemCount;
				nP++;

				pRear=pNode->pVertical;
			}
		}

		// Brother-link end
		else{
			nP--;
			if(!nP) break;
			pNode=arrpNode[nP];
		}

		// Link it to horizontal link
		pRear=pNode->pHorizon;
		pNode->pHorizon=arrpFpHorizon[pNode->nNumber];
		arrpFpHorizon[pNode->nNumber]=pNode;

		// Set ancestor
		pNode->pVertical=arrpNode[nP-1];

		// Deal with next brother-branch
		pNode=pRear;
	}

	// Free allocated memory
	delete[]arrpNode;
}

/*  Searching remark:
		The next level's nodes' frequencys based on larger numbers
	are zeroed by us before being searched. While all nodes' frequencys
	and	horizontal links oughtn't to be changed, we do it in two steps.
	First, adding frequency to array according to every number in nodes
	when searching ; Second, while searching the nodes, change information
	of every needed changing node of deeper level by checking its frequency
	in frequency array according to every item's number in nodes
*/
// Searching algorithm
void FpGrowth()
{
	int nP,nDepth,*arrnStart,nStart;
	FPTREENODE *pS_Node,*pS_Horizon,**arrpPattern;
	FPTREENODE *pM_Node,*pV_Ances,*pM_Insert;
	MEMORYBLOCK *pTempMemory;
	FREQ_TYPE fH_Frequency;

	// Allocate pattern nodes and initialize
	arrpPattern=new FPTREENODE *[nPatternLength+1];
	arrnStart=new int[nPatternLength+1];
	arrnStart[0]=1;
	pNodeRecycle=0;
	arrpPattern[0]=pM_Root;
	arrfFreq[nItemCount+1]=fSupport;
	nDepth=0;
	nP=1;

	// Initialize max-pattern tree node count
	nCount2=1;
	pHeaders=new FPTREENODE[nPatternLength];

	// Searching process
	while(1)
	{
		// Find an item number whose frequency isn't less
		// fSupport in frequency array from the top down.
		while(arrfFreq[nP]<fSupport)
		{
			arrpFpHorizon[nP]=0;
			arrfFreq[nP++]=0;
		}

		// If the found number is current depth number, return to
		// upper level, and mine from the number next to it , for current
		// searching level is created based on current depth number.
		if(nP==(pV_Ances=arrpPattern[nDepth])->nNumber)
		{
			// Mining process completes
			if(!nDepth) break;

			arrfFreq[nP]=0;
			arrpFpHorizon[nP++]=0;

			// Compare two trees and eliminate same branches
			EliminateBranches(pV_Ances,arrpPattern[nDepth-1]);
			nDepth--;
			continue;
		}

		// Calculate total number of frequent patterns
		nTotal++;
		nTotal2++;

		// Create the node for a pattern
		if(pNodeRecycle)
		{
			pM_Insert=pNodeRecycle;
			pNodeRecycle=pNodeRecycle->pVertical;
		}
		else{
			if(nNodeCount==MINNODECOUNT)
			{
				pTempMemory=pMemory;
				pMemory=new MEMORYBLOCK;
				pMemory->pNext=pTempMemory;
				pBlock=new FPTREENODE[MINNODECOUNT];
				pMemory->pMBlock=pBlock;
				nNodeCount=0;
			}
			pM_Insert=pBlock+nNodeCount;
			nNodeCount++;
		}
		nCount2++;
		pM_Insert->nNumber=nP;
		pM_Insert->pHorizon=pV_Ances->pVertical;
		pV_Ances->pVertical=pM_Insert;

		// Get next searching information. Search every branch marked
		// by every node of horizontal link, and add frequency to
		// frequency array.

		// Change node information while searching the nodes
		// Get first horizontal node
		// Find a number, create deeper searching level
		nStart=arrnStart[nDepth];
		pS_Horizon=arrpFpHorizon[nP];
		while(pS_Horizon)
		{
			// Get information in horizontal node
			fH_Frequency=pS_Horizon->fFrequency;
			pS_Node=pS_Horizon->pVertical;

			// Change information of every node
			while(pS_Node->nNumber>=nStart)
			{
				// Check if the node's frequency isn't less than
				if(pS_Node!=arrpFpHorizon[pS_Node->nNumber])
				{
					// Link it to horizontal link
					pS_Node->pHorizon=arrpFpHorizon[pS_Node->nNumber];
					arrpFpHorizon[pS_Node->nNumber]=pS_Node;

					// Add frequency to sub-tree node
					pS_Node->fFrequency=fH_Frequency;

					arrfFreq[pS_Node->nNumber]+=fH_Frequency;

					// Go to next node
					pS_Node=pS_Node->pVertical;

					continue;
				}

				// Add frequency to sub-tree node
				pS_Node->fFrequency+=fH_Frequency;
				arrfFreq[pS_Node->nNumber]+=fH_Frequency;

				pS_Node=pS_Node->pVertical;

				// Continue the process
				while(pS_Node->nNumber>=nStart)
				{
					// Add frequency to sub-tree node
					pS_Node->fFrequency+=fH_Frequency;

					arrfFreq[pS_Node->nNumber]+=fH_Frequency;

					// Go to next node
					pS_Node=pS_Node->pVertical;
				}

				break;
			}

			// Go to next horizontal node
			pS_Horizon=pS_Horizon->pHorizon;
		}

		// Find current level start point
		while(arrfFreq[nStart]<fSupport)
		{
			arrpFpHorizon[nStart]=0;
			arrfFreq[nStart++]=0;
		}

		// Make current depth horizontal link to zero for linking
		// deeper level's multiple searching branchs' head nodes
		// based larger numbers

		// Deal with the result
		if(nStart==nP)
		{
			pM_Insert->pVertical=0;
			pM_Insert->fFrequency=arrfFreq[nP];
			arrfFreq[nP]=0;
			arrpFpHorizon[nP++]=0;
			continue;
		}

		// Set current level start point
		arrnStart[++nDepth]=nStart;

		// Record current node
		arrpPattern[nDepth]=pM_Insert;

		// Calculate total number of frequent patterns
		nTotal++;

		// Create the node for a pattern
		if(pNodeRecycle)
		{
			pM_Node=pNodeRecycle;
			pNodeRecycle=pNodeRecycle->pVertical;
		}
		else{
			if(nNodeCount==MINNODECOUNT)
			{
				pTempMemory=pMemory;
				pMemory=new MEMORYBLOCK;
				pMemory->pNext=pTempMemory;
				pBlock=new FPTREENODE[MINNODECOUNT];
				pMemory->pMBlock=pBlock;
				nNodeCount=0;
			}
			pM_Node=pBlock+nNodeCount;
			nNodeCount++;
		}
		nCount2++;
		pM_Node->nNumber=nStart;
		pM_Insert->pVertical=pM_Node;
		pM_Node->pHorizon=pRoot;
		pM_Node->pVertical=0;

		// Clear current item information
		pM_Node->fFrequency=arrfFreq[nStart];
		arrfFreq[nStart]=0;
		arrpFpHorizon[nStart]=0;

		// Set number for checking every number from the top down
		// in frequency array
		nP=nStart+1;
	}

	// Contract last block
	realloc(pBlock,nNodeCount*sizeof(FPTREENODE));

	// Print max-patterns
	PrintMaxpatterns();

	// Print node count max-pattern tree
	printf("%d max-pattern tree nodes ... ",nCount2);

	// Free pattern array
	delete[]arrpPattern;
	delete[]pHeaders;
	delete[]arrnStart;
	delete[]arrfFreq;
}

// Compare two tree and eliminate same branches
bool EliminateBranches(FPTREENODE *pV_Root, FPTREENODE *pH_Root)
{
	static FPTREENODE *pHeader=pHeaders;
	FPTREENODE *pV_Horizon,*pH_Horizon,*pEndNode;

	// Initialization

	// Ensure a unempty tree
	pH_Horizon=pH_Root->pVertical;
	if(!pH_Horizon)
	{
		nTotal2--;
		return true;
	}

	pV_Horizon=pV_Root->pVertical;
	if(!pV_Horizon) return false;

	// Create header node
	pHeader++;
	pEndNode=pHeader;

	// Nodes matching in the two horizontal links
	while(1)
	{
		// Matching in right branches
		while(pV_Horizon->nNumber<pH_Horizon->nNumber)
		{
			pEndNode->pHorizon=pH_Horizon;
			pEndNode=pH_Horizon;

			pH_Horizon=pH_Horizon->pHorizon;
		}

		// No matching nodes
		if(pH_Horizon==pRoot) break;

		// Nodes matching
		if(pV_Horizon->nNumber==pH_Horizon->nNumber)
		{
			if(EliminateBranches(pV_Horizon,pH_Horizon))
			{
				pH_Horizon->pVertical=pNodeRecycle;
				pNodeRecycle=pH_Horizon;
				nCount2--;
			}
			else{
				pEndNode->pHorizon=pH_Horizon;
				pEndNode=pH_Horizon;
			}

			// Go to next nodes
			pV_Horizon=pV_Horizon->pHorizon;
			pH_Horizon=pH_Horizon->pHorizon;
		}

		while(pV_Horizon->nNumber>pH_Horizon->nNumber)
			pV_Horizon=pV_Horizon->pHorizon;

		// No matching nodes
		if(pV_Horizon==pRoot) break;

		// Nodes matching
		if(pV_Horizon->nNumber==pH_Horizon->nNumber)
		{
			if(EliminateBranches(pV_Horizon,pH_Horizon))
			{
				pH_Horizon->pVertical=pNodeRecycle;
				pNodeRecycle=pH_Horizon;
				nCount2--;
			}
			else{
				pEndNode->pHorizon=pH_Horizon;
				pEndNode=pH_Horizon;
			}

			// Go to next nodes
			pV_Horizon=pV_Horizon->pHorizon;
			pH_Horizon=pH_Horizon->pHorizon;
		}
	}

	// End horizontal link
	pEndNode->pHorizon=pH_Horizon;

	// Deal with the result
	if(pHeader->pHorizon==pRoot)
	{
		pHeader--;
		return true;
	}

	pH_Root->pVertical=pHeader->pHorizon;
	pHeader--;

	return false;
}

// Print out max-patterns
void PrintMaxpatterns()
{
	FPTREENODE *pM_Node,**arrpM_Stack;
	int i,nS;

	// Initialization
	arrpM_Stack=new FPTREENODE *[nPatternLength+1];
	pM_Node=pM_Root;
	nS=0;
	while(1)
	{
		// Go to branch leaves
		if(pM_Node->nNumber)
		{
			do{
				arrpM_Stack[nS++]=pM_Node;
				pM_Node=pM_Node->pVertical;
			}while(pM_Node);

			// Print a max-pattern
//			for(i=1;i<nS;i++) fprintf(fileResult,"%d\t",arrNumberToItem[arrpM_Stack[i]->nNumber]);
			for(i=1;i<nS;i++) fprintf(fileResult,"%d\t",arrpM_Stack[i]->nNumber);
			fprintf(fileResult,":: %d\n",arrpM_Stack[nS-1]->fFrequency);
		}

		// Return to upper level
		nS--;
		if(!nS) break;
		pM_Node=arrpM_Stack[nS]->pHorizon;
	}

	// Free memory
	delete[]arrpM_Stack;
}

// Free allocated memory
void DeleteFptree()
{
	MEMORYBLOCK *pTempMemory;
	FPTREENODE *pBlock;

	// Free allocated memory
    delete[]arrfItemInfo;
	delete[]arrNumberToItem;
	delete[]arrpFpHorizon;

	// Free fptree nodes
	do
	{
		pTempMemory=pMemory;
		pMemory=pTempMemory->pNext;
		pBlock=pTempMemory->pMBlock;
		delete[]pBlock;
		delete pTempMemory;
	}while(pMemory!=0);
}

/*  Used variables in searching:
Variable		Type		Creation		Initialization	Deletion

arrfItemInfo	ITEMINFO[]	Initialize()	Initialize()	DeletFptree()
arrNumberToItem	ITEM_TYPE[]	 Sort()			Sort()			DeletFptree()
arrpFpHorizon	FPTREENODE*[] Sort()		Sort()			DeletFptree()
arrfFreq		FREQ_TYPE[]	  Sort()		Sort()			FpGrowth()
arrPattern		int[]		  FpGrowth()	FpGrowth()		FpGrowth()

*/