apriori.cpp

Apriori算法实现

// Apriori.cpp: implementation of the Apriori class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Apriori_MB.h"
#include "Apriori.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Apriori::Apriori()
{

}

Apriori::~Apriori()
{

}

vector<char> Apriori::unique_item(const vector<vector<char> > & vvchar )
{
	vector<char> cvec;
	for(int i=0;i<vvchar.size();++i)
	{
		for(int j=0;j<vvchar[i].size();++j)
		{
			//找不到说明前面没有重复的单项
			if(find(cvec.begin(),cvec.end(),vvchar[i][j])==cvec.end())
			{
				cvec.push_back(vvchar[i][j]);
			}
		}
	}
	sort(cvec.begin(),cvec.end());
 return  cvec;
}

vector<int> Apriori::count_itemcollection(const vector<vector<char> > & vvchar,const vector<vector<char> > & transction)
{
	vector<int> ivec;
	int count=0;
	for(int i=0;i<vvchar.size();++i)//对每一个项集
	{
		for(int j=0;j<transction.size();++j)
		{
			for(int k=0;k<vvchar[i].size();++k)
			{
				//如果一个项在当前事务中找不到，其它的项也就不用再在当前事务中找
				//直接在下一个事务中找
				if(find(transction[j].begin(),transction[j].end(),vvchar[i][k])==transction[j].end())
				{
					break;
				}
			}
			
			//当前项集的所有项都在当前事务中出现，计数加1
			if(k==vvchar[i].size())
			{
				count++;
			}
		}
		ivec.push_back(count);
		count=0;
	}
 return  ivec;
}

vector< vector<char> > Apriori::choose_freq(vector<vector<char> > & candidate_cut,const vector<vector<char> > & transaction)
{
	vector<vector<char> > freq;
	vector<int> count=count_itemcollection(candidate_cut,transaction);
	for(int i=0;i<count.size();++i)
	{
		if(count[i]>=SUPPORT)
		{
			freq.push_back(candidate_cut[i]);   
		}
	}
 return  freq;
}

vector< vector<char> > Apriori::connect_freq(const vector<vector<char> > & freq1, const vector<vector<char> > & freq2)
{
	vector<vector<char> > candidate;
	for(int i=0;i<freq1.size();++i)
	{
		for(int j=0;j<freq2.size();++j)
		{
			for(int k=0;k<freq1[i].size()-1;++k)
			{
				if(freq1[i][k]!=freq2[j][k])
				{
					break;
				}
			}
			//第一个项集的前n－1位都等于第二个项集的前n－1位
			if (k==freq1[i].size()-1)
			{
				//同时，第一个项集的最后一项小于第二个项集的最后一项
				if(freq1[i][k]<freq2[j][k])
				{
					vector<char> cvec;
					//把第一个项集的全部项移入候选项
					for(int m=0;m<freq1[i].size();++m)
					{
						cvec.push_back(freq1[i][m]);
					}
					//把第二个项集的最后一个项移入候选项
					cvec.push_back(freq2[j][freq2[j].size()-1]);
					//把候选项加入候选项集中
					candidate.push_back(cvec);
				}
			}
		}
	}
 return  candidate;
}

void Apriori::FindItemSet(vector< vector<char> > transaction)
{
	//对各个事务项集进行排序
	for(int i=0;i<transaction.size();++i)
	{
		sort(transaction[i].begin(),transaction[i].end());
	}    
	//取得各个单项并对单项排序
	vector<char> cvec =unique_item(transaction);
//	vector<vector< vector<char> > >freq_results;//保存最后的频繁项集结果
	vector< vector<char> > candidate;//各个代的候选项集
	//候选项集开始初始化为单项集合
	for(int j=0;j<cvec.size();++j)
	{
		vector<char> cvec_tmp;
		cvec_tmp.push_back(cvec[j]);
		candidate.push_back(cvec_tmp);
	}
	//开始迭代求频繁项集，直到候选项集为空为止
	while(candidate.size()>0)
	{
		vector<vector<char> > freq_tmp=choose_freq(candidate,transaction);
		m_freqresults.push_back(freq_tmp);//这一代的频繁项集加入结果集合中
		candidate=connect_freq(freq_tmp,freq_tmp);
 }
}