closedseqtree.cpp

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

  NodeVector::iterator Itrtr;
  NodeVector::iterator tmpItrtr;
	int NumOfItemSets;
	int * ItemPtr;

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

	NumOfItemSets = (*aSeq).NumOfItemSets();

	// for each itemset in the sequence.
	for( ItemPtr=(*aSeq).StartPtr+(*aSeq).Len-1; ItemPtr>=(*aSeq).StartPtr; ItemPtr-- )
	{
		// for each item in an itemset.
		for( ; *ItemPtr!=-1 && ItemPtr>=(*aSeq).StartPtr; ItemPtr-- )
		{

			if( Header[*ItemPtr].size() > 0 )
			{
				Itrtr = Header[*ItemPtr].end() - 1;
				while( Itrtr >= Header[*ItemPtr].begin()  )
				{
					//try 
					{
						if( (*(*Itrtr)).ItemsetNumber > NumOfItemSets || !(*(*Itrtr)).LastItemOfSequence() ) 
						{
							Itrtr--;
							continue;
						}
						
						if( IsClosedSupersetOfBranch( aSeq, (*Itrtr) ) )
						{
							tmpItrtr = Itrtr;
							tmpItrtr--;

							NumOfDels++;
							DeleteSequence( (*Itrtr) );
							Itrtr = tmpItrtr;
						} else 
							Itrtr--;
					} /*catch(...)	{
						Itrtr--;
						printf( " Error in Delete Subsets in SequenceList.\n" );
					}*/
				}
			}

		}
	}

}

inline NodeVector::iterator SequenceList::FindInHeaderList( TreeNode * aNode )
{

  NodeVector::iterator Itrtr;

	Itrtr = (TreeNode **) bsearch( &aNode, Header[(*aNode).Item].begin(), Header[(*aNode).Item].size(), sizeof( TreeNode *), (int (*)(const void*, const void*))HdrTreeNodeCompare );

	return Itrtr;

/*
  NodeVector::iterator Itrtr;
  NodeVector::iterator ResultItrtr = NULL;

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

// Updates the Header list for the sequences ending with LastNode.
inline void SequenceList::UpdateHeaderList( TreeNode * LastNode )
{
  NodeVector::iterator Itrtr;
	TreeNode * CurNode;
	int LastSup = 0;


	// Add the last instance of each item in the sequence to the header list.
	for( CurNode=LastNode; (*CurNode).Parent!=NULL; CurNode=(*CurNode).Parent )
	{

		if( LastSup != (*CurNode).Support )
		{
			// inter_freq_idx is used to avoid adding duplicated items to the header list.
			memset( inter_freq_idx, 0, sizeof(int)*gN_ITEMS );

			LastSup = (*CurNode).Support;
		}

		if( inter_freq_idx[ (*CurNode).Item ] == 0 )
		{
			Itrtr = FindInHeaderList( CurNode );

			if( Itrtr == NULL )
			{
				Header[(*CurNode).Item].push_back( CurNode );

				// To keep the Header lists sorted based on the ItemsetNumber.
				inplace_merge( Header[(*CurNode).Item].begin(), Header[(*CurNode).Item].end()-1, Header[(*CurNode).Item].end(), HdrTreeNodeLess ); 
			}
	
			inter_freq_idx[ (*CurNode).Item ] = 1;

		}
	}
}

int SequenceList::AddIfClosedSeq( Sequence * aSeq )
{
	TreeNode * tmpNode;
	TreeNode * CurNode;
	TreeNode * LastOldNode = NULL;
	int * CurItem;
	bool Intra = false;

	NumOfAddIfClosed ++;


	// aSeq was not added.
	if( IsContained( aSeq ) ) 
	{
		delete aSeq;
		return 1;
	}

	DeleteClosedSubsets( aSeq );

	
	CurNode = Root;

	// Add the sequence to the tree.
	for( CurItem = (*aSeq).StartPtr; !(*aSeq).EndOfSequence( CurItem ); CurItem++ )
	{
		for( ; !(*aSeq).EndOfItemSet( CurItem ); CurItem++ )
		{
			tmpNode = new TreeNode( *CurItem, Intra, (*aSeq).Support );
			CurNode = (*CurNode).AddChild( tmpNode );
			if( CurNode == tmpNode ) 
				IncNumOfTreeNodes();


			// Keep the parent of the first new added node to the tree.
			if( LastOldNode==NULL && CurNode==tmpNode )
				LastOldNode = (*CurNode).Parent;

			Intra = true;
		}
		Intra = false;
	}


	UpdateHeaderList( CurNode );
	
	NumOfAdds++;

	delete aSeq;
	
	// aSeq was added.
	return 0;
}

void SequenceList::InternalPrintRules( FILE * aFile )
{

  NodeVector::iterator Itrtr;
	SeqList * SortedSeqList = NULL;

	#if defined( _SORT_RESULTS )
		SeqList::iterator ListItrtr;
		SortedSeqList = new SeqList;
	#endif

	if( Root )
		if( (*Root).Children != NULL )
		{
			for( Itrtr = (*(*Root).Children).begin(); Itrtr != (*(*Root).Children).end(); Itrtr++ )
			{
				(*(*Itrtr)).PrintRules( aFile, buf_idx, 0, this, SortedSeqList, 1 ); // buf_idx is a buffer defined globaly.
			}
		}

	#if defined( _SORT_RESULTS )
		fprintf( aFile, "\n" );
		for( ListItrtr=(*SortedSeqList).begin(); ListItrtr<(*SortedSeqList).end(); ListItrtr++ )
		{
			(*(*ListItrtr)).Print( aFile );
			delete (*ListItrtr);
		}
		delete SortedSeqList;
	#endif
}

void SequenceList::Print( FILE * aFile )
{
	Size = 0;
	InternalPrintRules( aFile );

	fprintf( aFile, "\n" );
	fprintf( aFile, "# of elements added %d\n", NumOfAdds );
	fprintf( aFile, "# of elements deleteded %d\n", NumOfDels );
	fprintf( aFile, "# of times AddIfClosedSeq called %d\n", NumOfAddIfClosed );
	fprintf( aFile, "# of times IsClosedSubsetOf called %d\n", NumIsClosedSubsetOfBranch + NumIsClosedSupersetOfBranch );
	fprintf( aFile, "# of elements in the list %d\n", Size );
	fprintf( aFile, "# of nodes in the final tree %d\n", NumOfTreeNodes );
	fprintf( aFile, "Peak # of nodes used in tree %d\n", PeakNumOfTreeNodes );

//	fprintf( aFile, "\n\n**************************************\n\n", Size );
//	PrintTree( aFile );
}

void SequenceList::PrintTree( FILE * aFile )
{
  NodeVector::iterator Itrtr;

	if( Root )
		(*Root).Print( "", aFile );

	fprintf( aFile, "\n Header Table:\n" );

	for( int i=0; i<NumOfItems; i++ )
	{

		fprintf( aFile, "  List for %d (Len=%d) => ", i, Header[i].size() );
		for( Itrtr = Header[i].begin(); Itrtr != Header[i].end(); Itrtr++)
		{
			fprintf( aFile, "  %d(%d)",  (*(*Itrtr)).Item, (*(*Itrtr)).Support );
		}
		fprintf( aFile, " \n" );
	}

}


SequenceList::~SequenceList()
{
	delete[] Header;
	delete Root;
}
//************************************
//************************************
//************************************

//************************
//************************
#endif // _NEW_SEQUENCE_LIST < 20
//************************
//************************
#else // defined( _NEW_SEQUENCE_LIST )
//************************
//************************

SequenceList::SequenceList()
{
	NumOfAdds = 0;
	NumOfDels = 0;
	NumOfAddIfClosed = 0;
	NumIsClosedSubsetOf = 0;
}

inline void SequenceList::AddSeq( Sequence * aSeq )
{
			//List.push_back( aSeq );
			// To keep the List vector sorted.
			//inplace_merge( List.begin(), List.end()-1, List.end(), SeqGreater );
	List.insert( List.end(), aSeq );
	NumOfAdds++;
}

inline SeqList::iterator SequenceList::Del( SeqList::iterator anItr )
{
	NumOfDels++;
	return List.erase( anItr );
}

// Tries to add aSeq to the list if non of the list elements
// is a closed superset of aSeq.
// Sequences in the list that are closed subset of aSeq
// will be deleted from the list.
// Returns true if aSeq is added.
bool SequenceList::AddIfClosedSeq( Sequence * aSeq )
{
	SeqList::iterator Itrtr;
	bool IsSuper = false;


	NumOfAddIfClosed++;
	for( Itrtr = List.begin(); Itrtr != List.end(); )
	{
		if( !IsSuper )
		{
			NumIsClosedSubsetOf++;
			if( (*aSeq).IsClosedSubsetOf( (*Itrtr) ) )
				return false;
		}

		NumIsClosedSubsetOf++;
		if( (*(*Itrtr)).IsClosedSubsetOf( aSeq ) )
		{

			delete (*Itrtr) ;

			IsSuper = true;
			Itrtr = Del( Itrtr );
		} else
			Itrtr++;
	}

	AddSeq( aSeq );
	return true;
} 

void SequenceList::Print( FILE *aFile )
{

	SeqList::iterator Itrtr;

#if defined( _SORT_RESULTS )
  SeqList::iterator ListItrtr;
	SeqList * SortedSeqList = NULL;
	SortedSeqList = new SeqList;
#endif

	fprintf( aFile, "\n" );

	for( Itrtr = List.begin(); Itrtr != List.end(); Itrtr++)
	{
		#if defined( _SORT_RESULTS )
			(*SortedSeqList).push_back( (*Itrtr) );
			// To keep the List vector sorted.
			inplace_merge( (*SortedSeqList).begin(), (*SortedSeqList).end()-1, (*SortedSeqList).end(), SeqGreater );
		#else
			(*(*Itrtr)).Print( aFile );
		#endif
	}

#if defined( _SORT_RESULTS )
	fprintf( aFile, "\n" );
	for( ListItrtr=(*SortedSeqList).begin(); ListItrtr<(*SortedSeqList).end(); ListItrtr++ )
	{
		(*(*ListItrtr)).Print( aFile );
	}
	delete SortedSeqList;
#endif

	fprintf( aFile, "\n" );
	fprintf( aFile, "# of elements added %d\n", NumOfAdds );
	fprintf( aFile, "# of elements deleteded %d\n", NumOfDels );
	fprintf( aFile, "# of times AddIfClosedSeq called %d\n", NumOfAddIfClosed );
	fprintf( aFile, "# of times IsClosedSubsetOf called %d\n", NumIsClosedSubsetOf );
	fprintf( aFile, "# of elements in the list %d\n", List.size() );

}

SequenceList::~SequenceList()
{
	SeqList::iterator Itrtr;

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

#endif // defined( _NEW_SEQUENCE_LIST )
//************************
//************************

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

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

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


void RTATest( const struct PROJ_DB * pDB )
{
/*
	int tmp = 0;
	int aMat[10];
	SequenceList * aSeqTree;
	Sequence * aSeq;


	aSeqTree = new SequenceList( 10 );


	aMat[0] = 1;
	aMat[1] = -1;
	aMat[2] = 2;
	aMat[3] = 3;
	aSeq = new Sequence( aMat, 4, 4 );
	(*aSeq).Print();
	printf( " NumOfItemSets = %d\n", (*aSeq).NumOfItemSets() );
	if( (*aSeqTree).AddIfClosedSeq( aSeq ) == 0 )
	{
		printf( "was added to the tree.\n\n" );
	} else {
		printf( "was NOT added to the tree.\n\n" );
	}

	aMat[0] = 1;
	aMat[1] = -1;
	aMat[2] = 2;
	aSeq = new Sequence( aMat, 3, 6 );
	(*aSeq).Print();
	printf( " NumOfItemSets = %d\n", (*aSeq).NumOfItemSets() );
	if( (*aSeqTree).AddIfClosedSeq( aSeq ) == 0 )
	{
		printf( "was added to the tree.\n\n" );
	} else {
		printf( "was NOT added to the tree.\n\n" );
	}

	aMat[0] = 1;
	aMat[1] = -1;
	aMat[2] = 2;
	aMat[3] = 4;
	aSeq = new Sequence( aMat, 4, 4 );
	(*aSeq).Print();
	printf( " NumOfItemSets = %d\n", (*aSeq).NumOfItemSets() );
	if( (*aSeqTree).AddIfClosedSeq( aSeq ) == 0 )
	{
		printf( "was added to the tree.\n\n" );
	} else {
		printf( "was NOT added to the tree.\n\n" );
	}

	aMat[0] = 1;
	aMat[1] = -1;
	aMat[2] = 2;
	aMat[3] = 4;
	aMat[4] = 5;
	aSeq = new Sequence( aMat, 5, 2 );
	(*aSeq).Print();
	printf( " NumOfItemSets = %d\n", (*aSeq).NumOfItemSets() );
	if( (*aSeqTree).AddIfClosedSeq( aSeq ) == 0 )
	{
		printf( "was added to the tree.\n\n" );
	} else {
		printf( "was NOT added to the tree.\n\n" );
	}

	aMat[0] = 1;
	aMat[1] = -1;
	aMat[2] = 2;
	aMat[3] = 4;
	aMat[4] = 6;
	aSeq = new Sequence( aMat, 5, 2 );
	(*aSeq).Print();
	printf( " NumOfItemSets = %d\n", (*aSeq).NumOfItemSets() );
	if( (*aSeqTree).AddIfClosedSeq( aSeq ) == 0 )
	{
		printf( "was added to the tree.\n\n" );
	} else {
		printf( "was NOT added to the tree.\n\n" );
	}

	aMat[0] = 1;
	aMat[1] = -1;
	aMat[2] = 2;
	aMat[3] = 4;
	aMat[4] = 7;
	aSeq = new Sequence( aMat, 5, 5 );
	(*aSeq).Print();
	printf( " NumOfItemSets = %d\n", (*aSeq).NumOfItemSets() );
	if( (*aSeqTree).AddIfClosedSeq( aSeq ) == 0 )
	{
		printf( "was added to the tree.\n\n" );
	} else {
		printf( "was NOT added to the tree.\n\n" );
	}

	aMat[0] = 1;
	aMat[1] = -1;
	aMat[2] = 2;
	aMat[3] = 4;
	aMat[4] = 6;
	aMat[5] = 8;
	aSeq = new Sequence( aMat, 6, 6 );
	(*aSeq).Print();
	printf( " NumOfItemSets = %d\n", (*aSeq).NumOfItemSets() );
	if( (*aSeqTree).AddIfClosedSeq( aSeq ) == 0 )
	{
		printf( "was added to the tree.\n\n" );
	} else {
		printf( "was NOT added to the tree.\n\n" );
	}
	buf_idx=(int*)malloc(sizeof(int)*1000);


	//(*aSeqTree).PrintTree();
	(*aSeqTree).Print();

	free( buf_idx );
	delete aSeqTree;
	exit( 0 );

*/

/*	int * RecStart;
	//SeqWrap * aWrap;
	Prefix * aWrap;
	Sequence * aSeq;
	FILE *File1 = NULL;
	FILE *File2 = NULL;

  File1 = file_open( "PrjDBNewStruc.txt", "w" ); 
  File2 = file_open( "PrjDBOldStruc.txt", "w" ); 

	for( int i=0; i<(*pDB).m_nSup; i++ )
	{
		RecStart = GetStartPtr( pDB, i );
		//aWrap = new SeqWrap( RecStart );
		aWrap = new Prefix( RecStart, GetEndPtr( RecStart ) );
		(*aWrap).GetFirst();
		(*aWrap).Print( File1 );
		delete aWrap;

		aSeq = new Sequence( RecStart, true );
		(*aSeq).Print( File2 );
		delete aSeq;
	}

  fclose( File1 );
  fclose( File2 );
*/
}

#endif // !defined( _FIND_MAX_SEQS ) && !defined( _FIND_FREQUENT_SEQS )