aprioriset.cpp

Apriori算法源码（C++） 看了以前在这里发的apriori源码

#include "stdAfx.h"
#include ".\aprioriset.h"

using namespace win32::gui;


CAprioriSet::CAprioriSet(int _itemCount, double _itemSupp)
{

	itemCount = _itemCount;
	freq  = _itemSupp * itemCount;

	//initialization database access
	con.connect ( DB_NAME, HOST, USER, PASSWD );

	Query query = con.query();
	query<<"select * from AprioriDB";

	res = query.store();

}

CAprioriSet::~CAprioriSet(void)
{
	con.close();
}

//************************************************************
//*
//* 功能：	查找1-频繁项集				    
//*							    
//************************************************************
void CAprioriSet::FindlargeItem(void)
{
	int count = 0;

	string strInit;
	string strValue;

	// 初始化候选项目集——从I1到I9	
	for( int initCount = 0; initCount < itemCount ; initCount++ )
	{   
		strInit = "I" + boost::lexical_cast<std::string>( initCount+1 );
		candlargeItem[0][initCount] = strInit;
	}

	// 遍历访问数据，获取项集
	Result::iterator it;
	for ( it = res.begin() ; it != res.end(); ++it )
	{
		
		// 获取当前列的值
		Row row(*it);
		strValue = row[1];
		//strValue = it->lookup_by_name( res.field_name(i).c_str() );   //效率较低,似乎无法获得正确的值
		
		// 统计1-频繁项集的值
		for(int j = 0; j < itemCount; j++)
			if ( npos != strValue.find( candlargeItem[0][j]) )
				candFreqCount[0][j]++;

	}

	// 生成1-频繁项集
	for ( int i = 0; i < itemCount; i++)
	{
		if ( candFreqCount[0][i] > freq )
		{
			freqGroup.push_back( make_tuple( 0, candlargeItem[0][i], candFreqCount[0][i] ) );
			largeItem[0][count] = candlargeItem[0][i];
			freqCount[0][count] = candFreqCount[0][i];
			count++;
		}
	}

	candlargeItemCount.push_back(count);

	largeItemCount.push_back(count);

}

//************************************************************
//*
//* 功能：	生成k(k>1)-频繁项集				    
//*							    
//************************************************************
void CAprioriSet::GenfreqItem(int level)
{
	string	strValue;
	int	count = 0;

	// 以下为求频繁项目集
	int k = level;
	
	for(int i = 0; i < candlargeItemCount[k]; i++)
	{
		if ( candFreqCount[k][i] > freq )
		{
			freqGroup.push_back ( make_tuple( k, candlargeItem[k][i], candFreqCount[k][i] ) );
			largeItem[k][count] = candlargeItem[k][i];
			freqCount[k][count] = candFreqCount[k][i];
			count++;
		}
	}

	// 复制频繁项目个数
	largeItemCount.push_back(count);
}

//********************************************************************
//*
//* 功能：	剪枝函数, 对已生成的候选项集检测其所有k-1组合是否存在				    
//*							    
//********************************************************************

bool CAprioriSet::Prune( int level, string& strCandFreqItem, vector<bool> itemFlag )
{
	int pos;
	vector<string> strFreqItem;	
	string strSubTemp;

	// 以，为间隔符取得字符串中的各项
	tokenItem ( strFreqItem, strCandFreqItem );

	pos = strFreqItem.size() - 2;
	while( pos-- >= 0 )
	{
		strSubTemp.clear();

		strSubTemp = next_combination( strFreqItem, pos );

		// 如果下一个k-1组合存在于C(k-1)中，则返回true
		for( int i = 0; i < largeItemCount[level-1]; i++ )
		{
			if ( npos == largeItem[level-1][i].find( strSubTemp ) ) 
			{
				return false;
			}
			else {
				itemFlag[i] = true;
			}
		}
	}

	return true;
}


//************************************************************
//*
//* 功能：	由L(k-1)生成C(k)				    
//*							    
//************************************************************

void CAprioriSet::AprioriGen( int level )
{
	string strTemp;
	int levelCount = 0;

	vector<bool> candLargeItemFlag( largeItemCount[level-1], false );
	
	// 如果两个L(k-1)项，前k-2都相同，只是最后一项不同，且前一项小于后一项
	// 则生成C(k)，并剪枝
	for(int i = 0; i < largeItemCount[level-1]; i++)
	{
		string strTemp1 = largeItem[ level-1 ][i];		
		
		for(int j = i + 1; j < largeItemCount[level-1]; j++)
		{
			// 如果此项为前面某k项组合中的k-1子项，则必不符合下述条件
			if( candLargeItemFlag[j] ){ 
				candLargeItemFlag[j] = false;
				continue;
			}
			string strTemp2 = largeItem[ level-1 ][j];

			// 检查两个L(k-1)项，是否只有最后一项不同，且符合条件
			pair<string::iterator, string::iterator> result =
				mismatch( strTemp1.begin(), strTemp1.end(), strTemp2.begin());

			if ( result.first == strTemp1.end()-1 && *(result.first) < *(result.second) )
			{
				strTemp = strTemp1 + ",I" + *(result.second);

				if( level == 1 || Prune( level, strTemp, candLargeItemFlag ) )
				{
					candlargeItem[level][levelCount++] = strTemp;				
				}
			}
		}

	}

	candlargeItemCount.push_back(levelCount);
}

//************************************************************
//*
//* 功能：	获取频繁项集，返回给view				    
//*							    
//************************************************************

vector<ItemType>  CAprioriSet::getFreqItem()
{
	Result::iterator it;
	string strValue;
	vector<string> strVec;

        FindlargeItem();
	
	for( int k = 1; largeItemCount[k-1] > k-1; k++ )
	{    

		AprioriGen(k);

		// 统计各项集频繁度
		for ( it = res.begin(); it != res.end(); it++ )
		{
			Row row(*it);
			strValue = row[1];

			for ( int i = 0; i < candlargeItemCount[k]; i++)
			{
				tokenItem( strVec, candlargeItem[k][i] );
				if ( search( strVec, strValue) )
				{
					candFreqCount[k][i]++;
					
				}
			}
			

		} 
	
		// 生成频繁项集
		GenfreqItem(k);

	}

	return freqGroup;
}

//************************************************************
//*
//* 功能：	以','为间隔符抽取字符串中的单项目，返回矢量				    
//*							    
//************************************************************

vector<string>& CAprioriSet::tokenItem(vector<string>& strVec, string& text)
{
	strVec.clear();
        
	string::const_iterator begin = text.begin(), end = text.end();
	boost::regex re("\\s*,\\s*", regex::optimize);
	boost::sregex_token_iterator token( begin, end, re, -1 );
	boost::sregex_token_iterator seeker;

	while ( token != seeker )
		strVec.push_back( *token++ );

	return strVec;

}

//************************************************************
//*
//* 功能：	生成L(k-1)的下一个组合				    
//*							    
//************************************************************

string& CAprioriSet::next_combination( vector<string>& kItem, int vecPos )
{
	vector<string> next = kItem;
	string str;
	
	// 用排除法求k-1组合
	vector<string>::iterator it;
	vector<string>::iterator new_end = remove( next.begin(), next.end(), kItem[ vecPos - 1 ] );
	next.erase( new_end, next.end() );

	for( it = kItem.begin(); it != kItem.end()-1; it++ )
		str += *it + ",";
	str += *it;

	return str;
}

//************************************************************
//*
//* 功能：	查找候选项集在在数据集中的匹配				    
//*							    
//************************************************************
bool CAprioriSet::search(vector<string>& src, string& text)
{
	vector<string>::iterator it;
	for( it = src.begin(); it != src.end(); it++ )
	{
		if ( npos == text.find(*it) )
			return false;
	}

	return true;
}