closedseqtree.cpp

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

}

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;
}

TreeNode::TreeNode( int anItem, bool IsIntra, int Sup, TreeNode * aParent )
{
	Children = NULL;
	Parent = aParent;
	ItemsetNumber = 0;
	Item = anItem;
	ItemIsIntra = IsIntra;
	Support = Sup;
}

inline TreeNode * TreeNode::FindChild( int anItem, bool Intra )
{
	TreeNode ** Res;
	TreeNode * tmp = new TreeNode( anItem, Intra );

	Res = (TreeNode **) bsearch( &tmp, (*Children).begin(), (*Children).size(), sizeof( TreeNode *), (int (*)(const void*, const void*))TreeNodeCompare );

	delete tmp;

	if( Res )
		return (*Res);
	else
		return NULL;
}

inline TreeNode * TreeNode::FindChild( TreeNode * Child )
{
	TreeNode ** Res;

	Res = (TreeNode **) bsearch( &Child, (*Children).begin(), (*Children).size(), sizeof( TreeNode *), (int (*)(const void*, const void*))TreeNodeCompare );

	if( Res )
		return (*Res);
	else
		return NULL;
}

inline void TreeNode::DelChild( TreeNode * Child )
{
	TreeNode ** Res;

	if( Children==NULL )
		return;

	if( (*Children).size() == 1 )
	{
		Res = (*Children).begin();
	} else {
		Res = (TreeNode **) bsearch( &Child, (*Children).begin(), (*Children).size(), sizeof( TreeNode *), (int (*)(const void*, const void*))TreeNodeCompare );
	}

	if( Res )
	{
		(*Children).erase( (Res) );
	}

}

TreeNode * TreeNode::AddChild( TreeNode * Child ) 
{ 
	TreeNode * Result = NULL;

	if( Children == NULL )
	{
		Children = new NodeVector();
		(*Children).push_back( Child );
		Result = Child;
		(*Child).Parent = this;
		if( (*Child).ItemIsIntra )
			(*Child).ItemsetNumber = ItemsetNumber;
		else
			(*Child).ItemsetNumber = ItemsetNumber + 1;
	} else {
		Result = FindChild( Child );
		if( Result == NULL )
		{
			Result = Child;
			(*Children).push_back( Child ); 
			// To keep the children vector sorted.
			inplace_merge( (*Children).begin(), (*Children).end()-1, (*Children).end(), TreeNodeLess );
			(*Child).Parent = this;
			if( (*Child).ItemIsIntra )
				(*Child).ItemsetNumber = ItemsetNumber;
			else
				(*Child).ItemsetNumber = ItemsetNumber + 1;
		} else {
			if( (*Child).Support > (*Result).Support )
				(*Result).Support = (*Child).Support;

			delete Child;

		}
	}

	return Result;
}

inline int TreeNode::NumOfChildren()
{
	if( Children==NULL )
		return 0;
	else
		return (*Children).size();
}

inline int TreeNode::MaxChildSupport()
{
	int MaxChildSup = 0;
  NodeVector::iterator Itrtr;

	if( Children==NULL )
		return 0;

	for( Itrtr = (*Children).begin(); Itrtr != (*Children).end(); Itrtr++ )
		if( (*(*Itrtr)).Support > MaxChildSup )
			MaxChildSup = (*(*Itrtr)).Support;

	return MaxChildSup;
}

bool TreeNode::LastItemOfSequence()
{
	if( Children==NULL )
		return true;

	if( MaxChildSupport() < Support )
		return true;

	return false;
}

void TreeNode::PrintRules( FILE * aFile, int * SeqBuf, int SeqLen, SequenceList * aSeqTree, SeqList * aSeqList, int NumOfItems )
{
	Sequence * aSeq;
	int MaxChildSupport = 0;
  NodeVector::iterator Itrtr;

	SeqBuf[ SeqLen ] = Item;

	if( Children != NULL )
	{
		for( Itrtr = (*Children).begin(); Itrtr != (*Children).end(); Itrtr++ )
		{
			if( !(*(*Itrtr)).ItemIsIntra )
			{
				SeqBuf[ SeqLen + 1 ] = -1;
				(*(*Itrtr)).PrintRules( aFile, SeqBuf, SeqLen + 2, aSeqTree, aSeqList, NumOfItems + 1 );
			} else {
				(*(*Itrtr)).PrintRules( aFile, SeqBuf, SeqLen + 1, aSeqTree, aSeqList, NumOfItems + 1 );
			}
			if( (*(*Itrtr)).Support > MaxChildSupport )
			{
				MaxChildSupport = (*(*Itrtr)).Support;
			} 
		}
		if( MaxChildSupport < Support )
		{
			aSeq = new Sequence( SeqBuf, SeqLen + 1, Support );
			gnResSizeCount[NumOfItems]++;

			if( aSeqList==NULL )
			{
				(*aSeq).Print( aFile );
				delete aSeq;
			} else {
				(*aSeqList).push_back( aSeq );
				// To keep the List vector sorted.
				inplace_merge( (*aSeqList).begin(), (*aSeqList).end()-1, (*aSeqList).end(), SeqGreater );
			}
			(*aSeqTree).Size++;
		}
	} else {
		aSeq = new Sequence( SeqBuf, SeqLen + 1, Support );
		gnResSizeCount[NumOfItems]++;

		if( aSeqList==NULL )
		{
			(*aSeq).Print( aFile );
			delete aSeq;
		} else {
			(*aSeqList).push_back( aSeq );
			// To keep the List vector sorted.
			inplace_merge( (*aSeqList).begin(), (*aSeqList).end()-1, (*aSeqList).end(), SeqGreater );
		}
		(*aSeqTree).Size++;
	}
}

void TreeNode::Print( char * PrefixString, FILE * aFile )
{
  NodeVector::iterator Itrtr;

	if( ItemIsIntra )
		fprintf( aFile, "%sNode = _%d   Support = %d   ItemsetNumber = %d\n", PrefixString, Item, Support, ItemsetNumber );
	else
		fprintf( aFile, "%sNode =  %d   Support = %d   ItemsetNumber = %d\n", PrefixString, Item, Support, ItemsetNumber );

	if( Children != NULL && NumOfChildren() > 0 )
	{
		char tmpString[256] = "   ";

		fprintf( aFile, "  %sChildren\n", PrefixString );

		strncat( tmpString, PrefixString, 250 );
		//strcat( tmpString, "  " );

		for( Itrtr = (*Children).begin(); Itrtr != (*Children).end(); Itrtr++ )
		{
			//fprintf( aFile, "    " );
			(*(*Itrtr)).Print( tmpString, aFile );
		}
	}

	//fprintf( aFile, "\n" );
}

TreeNode::~TreeNode()
{
	NodeVector::iterator Itrtr;

	if( Children )
		for( Itrtr = (*Children).begin(); Itrtr != (*Children).end(); Itrtr++)
			delete *Itrtr;
}

//************************
//************************

//************************
//************************


bool HdrTreeNodeLess( TreeNode * a, TreeNode * b )
{
	return a > b;
}

int HdrTreeNodeCompare( TreeNode ** a, TreeNode ** b )
{
	if( *a < *b )
		return 1;
	else if( *a > *b )
		return -1;
	else   
		return 0;
}


SequenceList::SequenceList( int ItemsCount )
{
	PeakNumOfTreeNodes = 0;
	NumOfTreeNodes = 0;

	Root = new TreeNode();
	IncNumOfTreeNodes();

	NumOfItems = ItemsCount;
	Header = new NodeVector[ NumOfItems ];

	NumOfAdds = 0;
	NumOfDels = 0;
	NumOfAddIfClosed = 0;
	NumIsClosedSubsetOfBranch = 0;
	NumIsClosedSupersetOfBranch = 0;
}


inline void SequenceList::IncNumOfTreeNodes()
{
	NumOfTreeNodes++;
	if( NumOfTreeNodes > PeakNumOfTreeNodes )
		PeakNumOfTreeNodes = NumOfTreeNodes;
}

inline void SequenceList::DecNumOfTreeNodes()
{
	NumOfTreeNodes--;
}

// Returns the item in the last itemset of aSeq, with shortest header list.
int SequenceList::LeastFreqInHeader( Sequence * aSeq )
{
	int * ItemPtr;
	int Res = -1;
	int Min = 10000000;
	int HeaderSize;

	for( ItemPtr=(*aSeq).StartPtr+(*aSeq).Len-1; *ItemPtr!=-1 && ItemPtr>=(*aSeq).StartPtr; ItemPtr-- )
	{
		HeaderSize = Header[*ItemPtr].size();
		if( HeaderSize < Min )
		{
			Min = HeaderSize;
			Res = *ItemPtr;
		}
		if( Min==0 ) break;
	}

	return Res;
}

// Returns true, if aSeq is a subset of the sequence in the tree with aNode as its last Item.
bool SequenceList::IsClosedSubsetOfBranch( Sequence * aSeq, TreeNode * aNode )
{
	int * ItemPtr;
	int * EndOfItemset;
	int NumOfRemItemsets;
	TreeNode * CurNode = aNode;


	NumIsClosedSubsetOfBranch++;

	NumOfRemItemsets = (*aSeq).NumOfItemSets();

	if( (*CurNode).ItemsetNumber < NumOfRemItemsets || (*aSeq).Support > (*CurNode).Support )
		return false;

	ItemPtr = (*aSeq).StartPtr+(*aSeq).Len-1;
	EndOfItemset = ItemPtr;

	// For all itemsets in the sequence.
	while( ItemPtr >= (*aSeq).StartPtr )
	{

		// For this itemset.
		while( true )
		{
			if( (*CurNode).Item == *ItemPtr )
			{
				ItemPtr--;

				if( ItemPtr < (*aSeq).StartPtr )
					return true;

				// Check previous itemset in the sequence.
				if( *ItemPtr == -1 )
				{
					ItemPtr--;
					break;
				}

			}

			if( !(*CurNode).ItemIsIntra )
			{
				if( (*CurNode).ItemsetNumber <= NumOfRemItemsets )
					return false;

				ItemPtr = EndOfItemset;
			}

			CurNode = (*CurNode).Parent;
		}

		NumOfRemItemsets--;
		//Move to the end of the previous itemset.
		while( (*CurNode).ItemIsIntra && (*CurNode).Parent!=NULL )
			CurNode = (*CurNode).Parent;
		CurNode = (*CurNode).Parent;


		EndOfItemset = ItemPtr;

	}
	return false;
}

// Returns true, if aSeq is a superset of the sequence in the tree with aNode as its last element.
bool SequenceList::IsClosedSupersetOfBranch( Sequence * aSeq, TreeNode * aNode )
{
	int * ItemPtr;
	TreeNode * EndOfItemset;
	int NumOfRemItemsets;
	TreeNode * CurNode = aNode;

	NumIsClosedSupersetOfBranch++;

	NumOfRemItemsets = (*aSeq).NumOfItemSets();

	if( (*CurNode).ItemsetNumber > NumOfRemItemsets || (*CurNode).Support > (*aSeq).Support )
		return false;

	ItemPtr = (*aSeq).StartPtr+(*aSeq).Len-1;
	EndOfItemset = aNode;

	while( ItemPtr >= (*aSeq).StartPtr )
	{
		// For this itemset.
		//while( true )
		while( ItemPtr >= (*aSeq).StartPtr )
		{
			if( (*CurNode).Item == *ItemPtr )
			{
				//if( (*(*CurNode).Parent).ItemsetNumber == 0 )
				if( (*(*CurNode).Parent).ItemsetNumber <= 0 )
					return true;

				// Check previous itemset in the sequence.
				if( !(*CurNode).ItemIsIntra )
				{
					CurNode = (*CurNode).Parent;
					break;
				}
				CurNode = (*CurNode).Parent;
			}

			if( *ItemPtr == -1 )
			{
				NumOfRemItemsets--;
				if( (*CurNode).ItemsetNumber > NumOfRemItemsets )
					return false;

				CurNode = EndOfItemset;
			}
			ItemPtr--;
		}

		//Move to the end of the previous itemset.
		while( *ItemPtr!=-1 && ItemPtr >= (*aSeq).StartPtr )
			ItemPtr--;
		ItemPtr--;


		EndOfItemset = CurNode;

	}
	return false;
}

bool SequenceList::IsContained( Sequence * aSeq )
{
	int NumOfItemSets;
	int anItem;
  NodeVector::iterator Itrtr;

	if( (*aSeq).Len == 0 )
		return true;


	// Just check for the item in the item list with shortest header list.
	//anItem = LeastFreqInHeader( aSeq );
	anItem = *((*aSeq).StartPtr+(*aSeq).Len-1); // Last Item of the sequence.

	if( Header[anItem].size() == 0 )
		return false; 

	NumOfItemSets = (*aSeq).NumOfItemSets();

	for( Itrtr = Header[anItem].begin(); Itrtr != Header[anItem].end(); Itrtr++ )
	{

		if( (*(*Itrtr)).ItemsetNumber < NumOfItemSets || (*(*Itrtr)).Support < (*aSeq).Support )
			continue;
		
		if( IsClosedSubsetOfBranch( aSeq, (*Itrtr) ) )
			return true;
	}

	return false;
}

void SequenceList::RemoveFromHeaderList( TreeNode * aNode )
{
  NodeVector::iterator Itrtr;

	Itrtr = FindInHeaderList( aNode ) ;
	while( Itrtr!=NULL )
	{
		Header[(*aNode).Item].erase( Itrtr );
		Itrtr = FindInHeaderList( aNode ) ;
	}

/*
	for( Itrtr = Header[(*aNode).Item].begin(); Itrtr<Header[(*aNode).Item].end(); Itrtr++ )
	{
		if( (*Itrtr) == aNode )
			Itrtr = Header[(*aNode).Item].erase( Itrtr );
	}
*/
}

void SequenceList::DeleteSequence( TreeNode * aNode )
{
	TreeNode * tmpNode;
	TreeNode * tmpChildNode;
	int aSup;
	int NewSup;

	aSup = (*aNode).Support;
	tmpNode = aNode;

	while( (*tmpNode).Support==aSup && (*tmpNode).Parent!=NULL && (*tmpNode).NumOfChildren() == 0 )
	{
		RemoveFromHeaderList( tmpNode );

		tmpChildNode = tmpNode;
		tmpNode = (*tmpNode).Parent;
		(*tmpNode).DelChild( tmpChildNode );

		delete tmpChildNode;
		DecNumOfTreeNodes();
	}

	if( (*tmpNode).Support==aSup && (*tmpNode).Parent!=NULL )
	{
		NewSup = (*tmpNode).MaxChildSupport();
		(*tmpNode).Support = NewSup;
		tmpNode = (*tmpNode).Parent;
	}

	while( (*tmpNode).Support==aSup && (*tmpNode).Parent!=NULL )
	{
		if( (*tmpNode).Support > (*tmpNode).MaxChildSupport() )
			(*tmpNode).Support = NewSup;
		tmpNode = (*tmpNode).Parent;
	}

}


void SequenceList::DeleteClosedSubsets( Sequence * aSeq )
{