apriori_simple.cpp

Aprioir算法的的Vc++的简单实现。所采用的数据集在程序中的到体现

#include <iostream>
#include <list>
#include <string>
using namespace std;
list<string> transcation;      //链表记录交易数据集
list<string> frequentSet[5];  //链表记录频繁集合
list<int *> count[5];  //频度
float frentNum=2;      //支持度，默认为2






void main()
{
  
	void InitialTranscationSet();  //初始化事务数据集合
 	void OutPut();
  	void Find1_FrequentSet();  //找出频繁1项集
 	void FunctionMain();      //主程序
	void AprioriGen(int k);  //由k-1频繁项集产生k项集合
 	void Prune(int k);  //    删除不是k频繁项集的元素

//定义
//--------------------------------------------------------


    cout<<"Apriori算法实现，本程序采用固定的交易数据："<<endl;
start:cout<<"输入支持度：(0-1,一般为0.2)";
	cin>>frentNum;
    if(frentNum>=1||frentNum<=0)
	{	
		cout<<"输入错误，重新输入"<<endl;
		goto start;
	}
	
	frentNum=frentNum*9;
	InitialTranscationSet();
	Find1_FrequentSet();
	FunctionMain();
	OutPut();
	char f;
	cout<<"任意键退出:";
	cin>>f;

}
Prune(int k)    //删除不是频繁的项
{
	int * temp=new int [frequentSet[k].size()];
	for(int j=0;j<frequentSet[k].size();j++)
	{
	   temp[j]=0;
	} 
	int i=0;          //查找频度。
	for(list<string>::iterator iter1=frequentSet[k].begin();iter1!=frequentSet[k].end();iter1++)
	{
		for(list<string>::iterator iter=transcation.begin();iter!=transcation.end();iter++)
		{   
			string::size_type pos=0;
			string strtemp=*iter1;
			int icout=strtemp.size()-1;
			while(icout>=0)   //分解字符串，寻找每个子串是否在事务数据中
			{
				string substemp=strtemp.substr(icout-1,2);
				pos=(*iter).find(substemp);
				if(pos!= (string::npos)) icout=icout-3;
				else break;
			}
			if(icout<0)  temp[i]++;
		}
		i++;
	}

	list<string>::iterator iter2=frequentSet[k].begin();
    //删除不频繁的
    int Isrerase=0;
	int sizeTemp=frequentSet[k].size();
	for(int t=0;t<sizeTemp-Isrerase;t++)   //这里一定要注意
	{   
		if(temp[t]<frentNum)   
		{
	    
			iter2= frequentSet[k].erase(iter2);
			if(t!=sizeTemp-1-Isrerase)  
			{ 
				for(int l=t;l<sizeTemp-1-Isrerase;l++  ) 
					temp[l]=temp[l+1]; 
				//temp[l]=0;
				t=t-1;
			}
			Isrerase++;
		} 
     	else iter2++;
	}
    cout<<endl;
	count[k].push_back(temp);
}
AprioriGen(int k)   //由k-1产生k项集
{
	int sizeTemp=frequentSet[k].size();
	list<string>::iterator iterFirstTmep=frequentSet[k].begin(); //变量iterFirstTmep为合并的前一个数据
	int mark=0;
	for(int i=0;i<sizeTemp-1;i++,iterFirstTmep++)
	{
		int temp=i;
		list<string>::iterator iterTailTmep=frequentSet[k].begin();//变量iterTailTmep为合并的后一个数据
		iterTailTmep++;
		while(temp)
		{
			iterTailTmep++;
			temp--;
		}
		for(int j=i+1;j<sizeTemp;j++,iterTailTmep++)
		{
			string strTmpFirest=*iterFirstTmep;   
			string strTempTail=*iterTailTmep;
		
	/*		for(int h=0;h<strTmpFirest.size();h++)
	          {			cout<<strTmpFirest[h]<<""<<strTempTail<<"  "<<endl;*/
                       
			int position=strTmpFirest.size()-1;
			while(position>=0)            //分解字符串，比较。
			{
				if(position==strTmpFirest.size()-1)   //strTmpFirest[k-1]<strTempTail[k]
				{
					char ctemp1=strTmpFirest[position];
     				char ctemp2=strTempTail[position]; 
					if(ctemp1<ctemp2) mark=1;
					else  mark=0;
    
				}
    			else 
				{
					if(mark==1)     //strTmpFirest和strTempTail 其他的部分要相同
					{
     					char ctemp3=strTmpFirest[position];
 						char ctemp4=strTempTail[position];  
						if(ctemp3==ctemp4) mark=1;
						else 
						{ 
    						mark=0; 
     						continue; 
						}
 					}   
 				}
    			position=position-3;
			}
    		if(position<0&&mark==1)     //如果满足合并的条件，就把两个字符串合并成新的字符串
			{
				string str=strTmpFirest+","+strTempTail.substr(strTempTail.size()-2);    
				frequentSet[k+1].push_back(str);
			}
		}
	}
}
void FunctionMain()    //产生频繁项集
{
	for(int frenSetNum=1;frequentSet[frenSetNum-1].size()!=0;frenSetNum++)
	{
		AprioriGen(frenSetNum-1);    //由k-1到k
		Prune(frenSetNum);       //删除不是频繁的项
	}
}
void InitialTranscationSet()   //初始化事务数据集合
{
	 string s0="I1,I2,I3";   
	 string s1="I2,I4";
	 string s2="I2,I3";
	 string s3="I1,I2,I4";
	 string s4="I1,I3";
	 string s5="I2,I3";
	 string s6="I1,I3";
	 string s7="I1,I2,I3,I5";
	 string s8="I1,I2,I3";
	 transcation.push_back(s0);
	 transcation.push_back(s1);
	 transcation.push_back(s2);
	 transcation.push_back(s3);
	 transcation.push_back(s4);
	 transcation.push_back(s5);
	 transcation.push_back(s6);
	 transcation.push_back(s7);
	 transcation.push_back(s8);
  
}
void Find1_FrequentSet()     //首先查找频繁1项集
{
	
	frequentSet[0].push_back("I1");
	frequentSet[0].push_back("I2");
	frequentSet[0].push_back("I3");
	frequentSet[0].push_back("I4");
	frequentSet[0].push_back("I5");
    static int * temp=new int [5];
	for(int j=0;j<5;j++)
	{
	   temp[j]=0;
	}
	int i=0;
	//产找每个的频繁度
	for(list<string>::iterator iter1=frequentSet[0].begin();iter1!=frequentSet[0].end();iter1++)
	{
		for(list<string>::iterator iter=transcation.begin();iter!=transcation.end();iter++)
		{   
			string::size_type pos=0;
			pos=(*iter).find((*iter1));
			if( pos!= (string::npos) ) temp[i]++;
		
		}

	
	i++;
	}
	//删除不是频繁的项
	list<string>::iterator iter2=frequentSet[0].begin();
    int Isrerase=0;
	for(int k=0;k<5-Isrerase;k++)
	{
		if((float)temp[k]<frentNum)   
		{
			   
	    	iter2= frequentSet[0].erase(iter2);
			if(k!=5-Isrerase-1)  
			{ 
				for(int l=k;l<5-Isrerase-1;l++  ) 
					temp[l]=temp[l+1]; 
				temp[l]=0;
				k--;
			}
			Isrerase++;
		} 
     	else iter2++;
	}

	count[0].push_back(temp);  //把频繁度数组加入到链表中
}
void OutPut()    //输出所有的频繁项集合
 {  
	cout<<endl;
	cout<<endl;
	cout<<endl;
	cout<<endl;
	cout<<"交易事务数据集为："<<"共9个交易数据,5个项I1-I5"<<endl;
    cout<<"--------------------------------------------------"<<endl;
	 for(list<string>::iterator iter=transcation.begin();iter!=transcation.end();iter++ )
	 {
		 string temp=*iter;
		 for(int i=0;i<temp.size();i++)
		 {
		 
			 cout<< temp[i];
		 }
		 cout<<endl;
		 
	 }
		 cout<<"--------------------------------------------------"<<endl;
		 
		 cout<<"产生的频繁集为："<<endl;
	 
	 int Num=0;
	 while(frequentSet[Num].size()!=0)
	 {
		 cout<<"--------------------------------------------------"<<endl;
		 cout<<"频繁"<<Num+1<<"项集为:"<<endl;
		 list<int *>::iterator iter2=count[Num].begin();
		 int * itemp=*iter2;
		 int t=0;
		 for(list<string>::iterator iter1=frequentSet[Num].begin();iter1!=frequentSet[Num].end();iter1++,t++)
		 {
			 string temp1=*iter1;
			 for(int j=0;j<temp1.size();j++)
			 {
				 cout<<temp1[j];
			 }
			 cout<<"   频度: "<<itemp[t];
			 cout<<endl;
			 
		 }
		 Num++;
	 }
	 cout<<"--------------------------------------------------"<<endl;
	 
 }