closedtree.cpp

数据挖掘中的序列模式挖掘算法clospan的C++实现

#include <assert.h>
#include "../Global.h"
#include "../ProjDB.h"

#if defined(_ANOTHER_CLOSED_APPROACH)
#include "ClosedTree.h"

ItemSet supSet;
ItemSet subSet;

int zzz=0;

bool TreeNodeLess( TreeNode * a, TreeNode * b )
{
	if( (*a).ItemIsIntra == (*b).ItemIsIntra )
		return (*a).Item < (*b).Item; 
	else if( (*a).ItemIsIntra && !(*b).ItemIsIntra )
		return true;
	else
		return false;
}

int TreeNodeCompare( TreeNode ** a, TreeNode ** b )
{
	if( (*(*a)).ItemIsIntra == (*(*b)).ItemIsIntra )
		if( (*(*a)).Item == (*(*b)).Item )
			return 0;
		else if( (*(*a)).Item < (*(*b)).Item )
			return -1;
		else
			return 1;
	else if( (*(*a)).ItemIsIntra && !(*(*b)).ItemIsIntra )
		return -1;
	else
		return 1;
}


inline TreeNode * GetLastItemSet(TreeNode * treeNode, ItemSet *itemSet)
{
	int *itemArray=itemSet->ItemArray;
	int i=0;

	itemSet->reset();
	do {
		itemArray[i++]=treeNode->Item;
		if (!treeNode->ItemIsIntra)
			break;
		else
			treeNode=treeNode->Parent;
	} while (treeNode->Items > 0);
	
	itemSet->Count=i;
	return (treeNode->Parent);
}

inline int isContained_DBSizeEqual(struct PROJ_DB *pDB, TreeNode *currentLevel, TreeNode *candidate) 
{
	
	int		myItem = pDB->Item;
	bool	myItemIsIntra = pDB->ItemIsIntra;
	int		dir;
	bool	isContained;


	TreeNode *supNode;
	TreeNode *subNode;

	if ((myItem != candidate->Item) || (candidate->Items == (currentLevel->Items+1))) 
		return 0;

	if ( candidate->Items > (currentLevel->Items + 1))
		dir=1;
	else
		dir=-1;

	if (candidate->ItemIsIntra) {
		if (myItemIsIntra) {
			candidate=candidate->Parent;
		}
		else {
			//in this case, supNode must be candidate, subNode must be currentLevel
			while (candidate->ItemIsIntra && candidate->Items >0)
				candidate = candidate ->Parent;

			candidate=candidate->Parent;
			if ((candidate->Items < currentLevel->Items) || (candidate->ItemsetNumber < currentLevel->ItemsetNumber))
				return 0;
			
		}
	}
	else {
		if (myItemIsIntra) {
			//in this case, supNode must be currentLevel, subNode must be candidate
			while (currentLevel->ItemIsIntra && currentLevel->Items >0)
				currentLevel = currentLevel ->Parent;

			currentLevel=currentLevel->Parent;
			if ((candidate->Items > currentLevel->Items) || (candidate->ItemsetNumber > currentLevel->ItemsetNumber))
				return 0;

			
		}
		else {
			candidate=candidate->Parent;
		}
	}

	
	if (currentLevel->Items == 0) {
		return 1;
	}

	if (candidate->Items == 0) {
		return -1;
	}

	if ( dir == 1) {
		supNode=candidate;
		subNode=currentLevel;	
	}
	else {
		supNode=currentLevel;
		subNode=candidate;
	}

	isContained=false;
	supNode=GetLastItemSet(supNode, &supSet);
	subNode=GetLastItemSet(subNode, &subSet);

	while (1) {
		if (subSet.IsSubsetOf(&supSet)) {
			if (subNode->Items == 0) {
				isContained=true;
				break;
			}
			if ((supNode->Items >= subNode->Items) && (supNode->ItemsetNumber >= subNode->ItemsetNumber)) {
				supNode=GetLastItemSet(supNode, &supSet);
				subNode=GetLastItemSet(subNode, &subSet);
			}
			else
				break;
		}
		else {
			if (supNode->Items == 0) // unnecessary to check any more.
				break;

			if ((supNode->Items >= subNode->Items) && (supNode->ItemsetNumber >= subNode->ItemsetNumber)) {
				supNode=GetLastItemSet(supNode, &supSet);
			}
			else
				break;
		}

	}
	if (isContained)
		return dir;
	else
		return 0;


}

void updateNodeInfo(TreeNode *treeNode, int extraItems, int extraItemsetNumber)
{
	NodeVector::iterator it, endit;

	treeNode->Items += extraItems;
	treeNode->ItemsetNumber += extraItemsetNumber;
	for (it=treeNode->Children->begin(), endit=treeNode->Children->end(); it != endit; it++) {
		if ((*it)->Parent == treeNode)
				updateNodeInfo((*it), extraItems, extraItemsetNumber);
	}
}

void updateOldNodeInfo(TreeNode* parent, TreeNode *pNode, TreeNode *qNode)
{
	TreeNode **Res;
	Res = (TreeNode **) bsearch( &pNode, &(*(parent->Children))[0], (*(parent->Children)).size(), sizeof( TreeNode *), (int (*)(const void*, const void*))TreeNodeCompare );
	*Res=qNode;
}

void checkNodeInfo(TreeNode *treeNode)
{	
	int items;
	int itemset_number;
	TreeNode *parent = treeNode->Parent;
	NodeVector::iterator it, endit;


	if( treeNode->ItemIsIntra ) {
		itemset_number = parent->ItemsetNumber;
		items = parent->Items + 1;
	}
	else {
		itemset_number = parent->ItemsetNumber + 1;
		items = parent->Items + 1;
	}

	if ((items != treeNode->Items) || (itemset_number != treeNode->ItemsetNumber))
		printf("Node Info: Items or ItemsetNumber Error");

	for (it=treeNode->Children->begin(), endit=treeNode->Children->end(); it != endit; it++) {
		if ((*it)->Parent == treeNode)
			checkNodeInfo((*it));
	}
	

	
}

//int qqq;
int addSequence(struct PROJ_DB *pDB, TreeNode **currentLevelp, ReverseHashTable *reverseTable)
{
	TreeNode   *pNode, *qNode;
	TreeNode *currentLevel=*currentLevelp;

	ReverseMap pMap;
	ReverseHashTable::iterator it, endit;


	int ret, myNumOfItems;

	
	/*printf("SSN: %d Item: %d\n", ++qqq, pDB->Item);

	if (qqq == 20496) {
		printf("hello\n");
	}*/

	

	//myNumOfItems=pDB->NumOfItems + pDB->m_nMaxSup - pDB->m_nSup;
	myNumOfItems=pDB->NumOfItems + pDB->m_nMaxSup;
	//myNumOfItems=pDB->NumOfItems;

	/*if (myNumOfItems == 3378012)
			printf("GUGU\n");
	*/


	pMap=(*reverseTable).equal_range(myNumOfItems);
	for (it=pMap.first, endit=pMap.second; it != endit; it++) {
		pNode=(*it).second;
		if (pNode->Support != pDB->m_nMaxSup)
			continue;
		ret=isContained_DBSizeEqual(pDB, currentLevel, pNode);
		switch (ret) {
			case 0:
				continue;
			case 1:  //Backward SubPattern
				//(*(currentLevel->Children)).push_back(pNode);
				//(*(currentLevel->IntraChildren))[pDB->Item]=pNode;
				//qNode is a mirror of pNode, but has slight different
				//the major goal is to let closed_maxPruning much easier
				qNode= new TreeNode();
				qNode= currentLevel->AddChildWithoutChecking( pDB->Item, pDB->ItemIsIntra, pDB->m_nMaxSup);
				qNode->SetProjDBSize(myNumOfItems);
				qNode->Children=pNode->Children;
				return EQUAL_PROJECT_DB_SIZE;

			case -1: //Backward SuperPattern

				qNode= new TreeNode(pNode);
				updateOldNodeInfo(pNode->Parent, pNode, qNode);

				if (pDB->ItemIsIntra) {
					updateNodeInfo(pNode, 
								   currentLevel->Items - pNode->Parent->Items,
								   currentLevel->ItemsetNumber - pNode->Parent->ItemsetNumber);
					//checkNodeInfo(currentLevel);
					pNode->ItemIsIntra=true;
					pNode->Parent=currentLevel;
					(*(currentLevel->Children)).push_back(pNode);
					inplace_merge((*(currentLevel->Children)).begin(), (*(currentLevel->Children)).end()-1, 
								  (*(currentLevel->Children)).end(), TreeNodeLess );
				}
				else {
					updateNodeInfo(pNode, 
								   currentLevel->Items - pNode->Parent->Items,
								   currentLevel->ItemsetNumber - pNode->Parent->ItemsetNumber);
					//checkNodeInfo(currentLevel);
					//pNode->Parent->Children->erase(pNode);
					pNode->ItemIsIntra=false;
					pNode->Parent=currentLevel;
					(*(currentLevel->Children)).push_back(pNode);
					inplace_merge((*(currentLevel->Children)).begin(), (*(currentLevel->Children)).end()-1, 
								  (*(currentLevel->Children)).end(), TreeNodeLess );

				}
				
				//reverseTable->erase(it);
				//reverseTable->insert(ReverseHashTable::value_type(myNumOfItems, qNode));
					
				return EQUAL_PROJECT_DB_SIZE;
			default:
				break;
		}
	}
	
	zzz++;
	pNode= new TreeNode();
	pNode= currentLevel->AddChildWithoutChecking( pDB->Item, pDB->ItemIsIntra, pDB->m_nMaxSup);
	pNode->SetProjDBSize(myNumOfItems);
	(*currentLevelp)=pNode;
	reverseTable->insert(ReverseHashTable::value_type(myNumOfItems, pNode));

	return INEQUAL_PROJECT_DB_SIZE;

}


void closed_maxChecking(TreeNode *pNode, TreeNode *pNode_parent, TreeNode *qNode)
{
	NodeVector::iterator it, endit;

	if (pNode == NULL)
		return;

	if (pNode->Parent != pNode_parent)
		return;

#if defined (_ANOTHER_MAX_APPROACH)
		pNode->max=false;
#else
	if (pNode->Support == qNode->Support)
		pNode->closed = false;
#endif

	for (it=qNode->Children->begin(), endit=qNode->Children->end(); it != endit; it++) 
		closed_maxChecking (pNode->FindChild((*it)->Item, (*it)->ItemIsIntra), pNode, (*it));

}

void closed_maxPruning(TreeNode *treeNode, TreeNode *parent)
{
	NodeVector::iterator it, endit, ti;
	bool myItemIsIntra=treeNode->ItemIsIntra;
	TreeNode *pNode;

#if defined (_ANOTHER_MAX_APPROACH)