main.cpp

Apriori算法是一种找频繁项目集的基本算法。其基本原理是逐层搜索的迭代

#include <afxdb.h>
#include <vector>
#include <iostream>
#include <CString>

#define MIN_SUP 0.7//最小支持度

long MAX_T_SUM=0;	//事物总数

typedef struct
{
	std::vector<CString> tname;
	long sup;
}lnote;

typedef std::vector<lnote> L;

int Find_Tlist_In_DBTlist(std::vector<CString> tlist,std::vector<CString> *s)
{
	int flag;
	for(unsigned int i=0;i<tlist.size();i++)
	{
		flag=0;
		for(unsigned int j=0;j<s->size();j++)
			if((*s)[j].Compare(tlist[i])==0)
			{
				flag=1;		break;
			}
		if(flag==0)
			goto end;
	}
end:
	return flag;
}

bool Find_TName_In_L_Or_C(int &i,CString tname,L c)
{
	unsigned int j;
	for(j=0;j<c.size();j++)
		if(tname.Compare(c[j].tname[0])==0)
				goto Find;
	return false;
Find:
	i=j;
	return true;
}

bool Find_TList_In_L(std::vector<CString> tlist,L &l)
{
	unsigned int j,k;
	for(unsigned int i=0;i<l.size();i++)
	{
		for(j=0,k=0;j<tlist.size();j++)
		{
			for(;k<l[i].tname.size();k++)
			{
				if(tlist[j].Compare(l[i].tname[k])<0)
					goto next;
				if(tlist[j].Compare(l[i].tname[k])==0)
					break;
			}
			if(k==l[i].tname.size())
				break;
		}
next:
		if(j==tlist.size())
			return true;
	}
	return false;
}

void Find_L1(CRecordset *tt,L &l1)
{
	L c1;
	//get C1
	for(int i;!tt->IsEOF();MAX_T_SUM++)
	{
		CString tname;
		for(long j=1;j<tt->GetODBCFieldCount();j++)
		{
			tt->GetFieldValue(j,tname);
			tname.TrimLeft();
			tname.TrimRight();//Trim();
			if(Find_TName_In_L_Or_C(i,tname,c1))
				c1[i].sup++;
			else
			{
				lnote ln;
				ln.sup=1;
				ln.tname.push_back(tname);
				c1.push_back(ln);
			}
		}
		tt->MoveNext();
		//std::cout<<MAX_T_SUM<<'\n';
	}
	//get L1 from C1
	for(unsigned int i1=0;i1<c1.size();i1++)
		if(c1[i1].sup*1.0/MAX_T_SUM>=MIN_SUP)
			l1.push_back(c1[i1]);
}

bool Join_Li_And_Lj(std::vector<CString> tname1,std::vector<CString> tname2,lnote &cnote)
{
	cnote.tname.clear();
	for(unsigned int i=0;i<tname1.size();i++)
		if(i==tname1.size()-1)
			if(tname1[i].Compare(tname2[i])<0)
			{
				cnote.tname.push_back(tname1[i]);
				cnote.tname.push_back(tname2[i]);
				cnote.sup=0;
				return true;
			}
			else
			{
				cnote.tname.push_back(tname2[i]);
				cnote.tname.push_back(tname1[i]);
				cnote.sup=0;
				return true;
			}
		else
			if(tname1[i].Compare(tname2[i])!=0)
				break;
			else
				cnote.tname.push_back(tname1[i]);
	return false;
}

bool Has_Infrequent_Subset(std::vector<CString> tlist,L &l)
{
	unsigned int len=tlist.size()-2;
	std::vector<CString> tl;
	for(unsigned int i=0;i<len;i++)
	{
		tl.clear();
		for(unsigned int j=0;j<tlist.size();j++)
			if(j!=i)
				tl.push_back(tlist[j]);
		if(!Find_TList_In_L(tl,l))		//find return true
			return true;				//has infrequent subset
	}
	return false;
}

void aproiri_gen(L &l,L &c)
{
	lnote cnote;
	c.clear();
	for(unsigned int i=0;i<l.size();i++)
		for(unsigned int j=i+1;j<l.size();j++)
		{
			if(Join_Li_And_Lj(l[i].tname,l[j].tname,cnote))		//true is can join
				if(!Has_Infrequent_Subset(cnote.tname,l))				//true means has infrequent subset
					c.push_back(cnote);
		}
}

void Print_L(L &l)
{
	lnote ll;
	for(unsigned int i=0;i<l.size();i++)
	{
		ll=l[i];
		for(unsigned int j=0;j<ll.tname.size();j++)
		{
			CString cc;
			cc=ll.tname[j];
			for(unsigned int t=0;t<cc.GetLength();t++)
				std::cout<<cc.GetAt(t)<<",";
		}
		std::cout<<"\t\t"<<ll.sup*1.0/MAX_T_SUM<<'\n';
	}
}

void Apriori(CRecordset *tt,std::vector<L> &lt)
{
	tt->Open(CRecordset::forwardOnly,"select * from mushroom",CRecordset::readOnly);
	
	L l,c;
	Find_L1(tt,l);	
	while(l.size()!=0)
	{
		lt.push_back(l);
	//	Print_L(l);std::cout<<'\n';
		aproiri_gen(l,c);
	//	Print_L(c);std::cout<<'\n';
		tt->Close();
		tt->Open(CRecordset::forwardOnly,"select * from mushroom",CRecordset::readOnly);
		//tt->MoveFirst();
		while(!tt->IsEOF())
		{
			CString tname;
			std::vector<CString> s;
			for(long j=1;j<tt->GetODBCFieldCount();j++)
			{
				tt->GetFieldValue(j,tname);
				tname.TrimLeft();
				tname.TrimRight();//Trim();
				s.push_back(tname);
			}
			for(unsigned int i=0;i<c.size();i++)
				c[i].sup+=Find_Tlist_In_DBTlist(c[i].tname,&s);	//find return 1
			tt->MoveNext();
			s.clear();
		}
	//	Print_L(c);std::cout<<'\n';
		l.clear();
		for(unsigned int i=0;i<c.size();i++)
			if(c[i].sup*1.0/MAX_T_SUM>=MIN_SUP)
				l.push_back(c[i]);
	}
	
	tt->Close();
}

void Print_Lt(std::vector<L> &lt)
{
	for(unsigned int i=0;i<lt.size();i++)
	{
		std::cout<<'L'<<i+1<<':'<<'\n';
		Print_L(lt[i]);
	}
}

void main()
{
	CDatabase db;
	db.Open("db_mg");
	CRecordset tt(&db);
	SYSTEMTIME beginT,endT;
	std::vector<L> lt;

	GetSystemTime(&beginT);
	Apriori(&tt,lt);
	GetSystemTime(&endT);
	
	int m,s;
	m=endT.wMinute - beginT.wMinute;
	s=endT.wSecond - beginT.wSecond;
	if(s < 0)
	{
		s=60+s;
		m--;
	}

	Print_Lt(lt);
	std::cout << m << "M "
		      << s << "S \n";

 	db.Close();
}