l maxfpminer.cpp

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

						pBlock=new FPTREENODE[MINNODECOUNT];
						pMemory->pMBlock=pBlock;
						nNodeCount=0;
					}
					pQuery=pBlock+nNodeCount;
					nNodeCount++;
					nFptreeNodeCount++;
  					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("%u nodes, %u frequent items ... ",nFptreeNodeCount,nItemCount);
	fprintf(fileResult,"Count of frequent item: %u\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;
	unsigned nP;

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

	// Create used type and initialize it
	arrpNode=new FPTREENODE *[nFPMaxlength+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 MiningMaxfp()
{
	unsigned i,nP,nDepth,*arrnStart,nStart,nEnd,nMiddle;
	unsigned _int64 arr2Powers[64];
	unsigned *arrnFreqOrders,nFreqCount;
	FPTREENODE *pS_Node,*pS_Horizon,**arrpPattern;
	FPTREENODE *pM_Node,*pV_Ances,*pM_Insert;
	MEMORYBLOCK *pTempMemory;
	FREQ_TYPE fH_Frequency,fS_Support;

	// Cuculate 2' powers
	arr2Powers[0]=1;
	for(i=1;i<64;i++) arr2Powers[i]=arr2Powers[i-1]+arr2Powers[i-1];

	// Allocate pattern nodes and initialize
	nTotalMined=1;
	nMaxfpCount=1;
	arrpPattern=new FPTREENODE *[nFPMaxlength+1];
	arrnStart=new unsigned[nFPMaxlength+1];
	arrnFreqOrders=new unsigned[nFPMaxlength+2];
	arrnFreqOrders[0]=nItemCount+1;
	arrnStart[0]=1;
	pNodeRecycle=0;
	arrpPattern[0]=pM_Root;
	arrfFreq[nItemCount+1]=fSupport;
	nDepth=0;
	nP=nItemCount+1;
	nStart=1;

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

	// Initialize insert pointer
	pM_Insert=pM_Root;

	// Searching process
	while(1)
	{
		// Initialize frequent orders
		nFreqCount=0;
		fS_Support=arrfFreq[nStart];
		while(nStart<=nP)
		{
			if(arrfFreq[nStart]>=fSupport)
			{
				arrnFreqOrders[++nFreqCount]=nStart;
				if(nFreqCount>nFPMaxlength) break;
			}
			nStart++;
		}

		// Find the possible long continuous frequent order set,
		// and insert it into max-pattern tree
		nStart=2;
		nEnd=nFreqCount-1;
		nP=1;
		while(nStart<=nEnd)
		{
			nMiddle=(nStart+nEnd)/2;
			pS_Horizon=arrpFpHorizon[arrnFreqOrders[nMiddle]];
			fH_Frequency=0;
			while(pS_Horizon)
			{
				// Get information in horizontal node
				pS_Node=pS_Horizon->pVertical;
				i=nMiddle-1;

				// Change information of every node
				while(1)
				{
					if(pS_Node->nNumber<arrnFreqOrders[i]) break;

					if(pS_Node->nNumber==arrnFreqOrders[i]) i--;

					pS_Node=pS_Node->pVertical;
				}

				// Caculate support
				if(!i) fH_Frequency+=pS_Horizon->fFrequency;

				// Go to next path
				pS_Horizon=pS_Horizon->pHorizon;
			}

			// Deal with the result
			if(fH_Frequency>=fSupport)
			{
				nP=nMiddle;
				fS_Support=fH_Frequency;
				nStart=nMiddle+1;
			}
			else nEnd=nMiddle-1;
		}

		// Insert the pattern into max-pattern tree
		for(i=nP;i>0;i--)
		{
			// 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++;
			}
			nMptreeNodeCount++;
			pM_Node->nNumber=arrnFreqOrders[i];
			pM_Node->pHorizon=pRoot;

			pM_Insert->pVertical=pM_Node;
			pM_Insert=pM_Node;
		}

		// pattern information
		pM_Insert->pVertical=0;
		pM_Insert->fFrequency=arrfFreq[arrnFreqOrders[nP]];

		// Caculate pattern count
		nTotal+=arr2Powers[nP];

		// Initialize next frequent order
		nP=arrnFreqOrders[nP+1];

		while(1)
		{
			if(nP==(pV_Ances=arrpPattern[nDepth])->nNumber)
			{
				// Mining process completes
				if(!nDepth) break;

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

				// Find next frequent order
				while(arrfFreq[++nP]<fSupport);

				nDepth--;

				continue;
			}

			// Calculate total number of frequent patterns
			nTotalMined++;
			nMaxfpCount++;

			// Clear information in head talbes before building subtree
			nStart=arrnStart[nDepth];
			for(;nStart<nP;nStart++)
			{
				arrfFreq[nStart]=0;
				arrpFpHorizon[nStart]=0;
			}

			// Build subtree
			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
			// and clear useless information
			while(arrfFreq[nStart]<fSupport)
			{
				arrpFpHorizon[nStart]=0;
				arrfFreq[nStart++]=0;
			}

			// Insert pattern ended with nP
			// 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++;
			}
			nMptreeNodeCount++;
			pM_Insert->nNumber=nP;
			pM_Insert->pHorizon=pV_Ances->pVertical;
			pV_Ances->pVertical=pM_Insert;

			// Deal with the result

			// The pattern can be longered
			if(nStart!=nP)
			{
				arrpPattern[++nDepth]=pM_Insert;
				arrnStart[nDepth]=nStart;

				break;
			}

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

			// Current pattern end
			pM_Insert->pVertical=0;
			pM_Insert->fFrequency=arrfFreq[nP];

			// Check orders in upper level
			while(arrfFreq[++nP]<fSupport);
		}

		// Mining process end
		if(!nDepth) break;
	}

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

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

	// Print max-patterns
	PrintMaxpatterns();

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

// 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)
	{
		nMaxfpCount--;
		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;
				nMptreeNodeCount--;
			}
			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;
				nMptreeNodeCount--;
			}
			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;
	unsigned i,nS;

	// Initialization
	arrpM_Stack=new FPTREENODE *[nFPMaxlength+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,"%u\t",arrNumberToItem[arrpM_Stack[i]->nNumber]);
			for(i=1;i<nS;i++) fprintf(fileResult,"%u\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 FreeMemory()
{
	MEMORYBLOCK *pTempMemory;
	FPTREENODE *pBlock;

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

	// 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()			MiningMaxfp()
arrPattern		int[]		  MiningMaxfp()	MiningMaxfp()		MiningMaxfp()

*/