apriori.cpp

可以运行的apriori算法实现

# include <iostream.h>
# include <stdlib.h>
# include <fstream.h>

void sum(int t[30][20]);
int get(int t[30][20],int a[100][20],int b[100][20],int k0,int k,int h);
int  jield(int t[30][20],int l[100][20],int k,int h,int qian[50][10],int hou[50][10],int y,double credit[50]);
int n,m;     //n表示事务数，m表示项数
double s,d;  //s表示支持度，d表示置信度
void main()
{
    int i,j,k,k1,k2,k5,h2,h3,pan;
	int t[50][20]={{4,1,2,3},{5,1,2,3,4,5,8},{3,1,3,4,6},{4,2,1,4,5},{5,3,2,4,6,7,9},
	{2,5,3,1,7},{2,5,3,1,8},{2,5,3,1,8,9}};
	//每个行数组中的第一个用来计数 如：t[1][0]=3;表示第二行有三个元素。
	//int t[50][20];
	h2=0;  h3=0;   i=0;
    for(i=0;i<20;i++)  cout<<"*";
    cout<<""<<"  apriori算法：  ***";
	for(i=0;i<20;i++)  cout<<"*";  
	cout<<endl<<endl;
	for(i=0;i<20;i++)  cout<<" ";
	cout<<"请选择操作："<<endl;
    for(i=0;i<15;i++)  cout<<"-";
	cout<<"选1.使用原有数据进行操作"<<endl;
    for(i=0;i<15;i++)  cout<<"-";
	cout<<"选2.则读入文件中的数据进行操作"<<endl;
	for(i=0;i<15;i++)  cout<<"-";
	cout<<"选3.可自由输入数据，进行测试"<<endl;
	for(i=0;i<15;i++)  cout<<"-";
	cout<<"选4.则退出"<<endl<<endl;
	for(i=0;i<60;i++)  cout<<"*";
	cout<<endl<<endl<<"请选择操作：（输入1、2、3或4）";
	cin>>pan;

	if(pan==2)
	{ for(i=0;i<50;i++) 
		for(j=0;j<20;j++)
			t[i][j]=0;
       	ifstream f2("wr1.dat",ios::in|ios::nocreate);
	  if(!f2)
	  {	cerr<<"wr1.dat file not open!"<<endl;
	        exit(1);
	  }
    	int x;  i=0;  j=1;
     	while(f2>>x)
		{ if(x>0)  { t[i][j]=x;j++;}
	      else if(x==0) {i=i+1;j=1;}
	      else if(x<0)  break;
		}
	f2.close();
	}

	if(pan==3)
	{
	for(i=0;i<50;i++) 
		for(j=0;j<20;j++)
			t[i][j]=0;
    cout<<endl<<endl<<"一项事务结束请输入'0',全部事务结束则请输入负数："<<endl;
	cout<<"例如：一个事务为{1,2,5},则请输入：1 2 5 0,再按enter键。"<<endl;
	cout<<"      如果输入结束则输入负数，如：－2，再按enter键。"<<endl<<endl;
	i=0;
 	while(1)
	{	cout<<"输入第"<<i+1<<"个事务在的项： ";
		for(j=1;1;j++)
		{
			cin>>h3;
			if(h3==0)  break;
			if(h3<0)   { h2=1;break;}
			t[i][j]=h3;
		}
		if(h2==1)   break;
		i++;
	}
	}

	if(pan==4)  exit(1);
	sum(t);
	int bi,b1[30];    k5=1;
	for (i=0;i<30;i++)  b1[i]=0;
	for(i=0;i<n;i++)
		for(j=1;j<=t[i][0];j++)
		{  int ij=t[i][j]; bi=0;
		   for(k=1;b1[k]>0;k++)
			   if (ij==b1[k]) { bi=1;break;}
			if(bi==0) 
			{  b1[k5]=ij;   k5++;}
		}
		   
	double s1,d1;
	cout<<endl<<"输入支持度：   ";
	cin>>s1;
	cout<<"输入置信度：   ";
	cin>>d1;
    s=int(n*s1); d=d1;
	cout<<endl<<"总事务数 n= "<<n<<"总项数  m= "<<m<<"支持数  s= "<<s<<"置信度  d= "<<d<<endl;
	int c[20],ck[20],l[100][20],count[20];
	//ck[i]用于记录一个集中有多少个频繁项集
	int qian[50][10],hou[50][10];
	double credit[50];
	
	cout<<" 面包 ：1  果冻 ：2   花生酱 ：3   牛奶：4   啤酒：5 "<<endl;

	k1=0;     //k1用于记录L1中项数
	
	//输出事务数组T中内容
	cout<<endl<<"输出初始的事务内容"<<endl;
	cout<<"项数  各项值"<<endl;
	for (i=0;i<n;i++)
	{for (j=0;t[i][j]>0;j++)
	   cout<<t[i][j]<<"     ";
	    cout<<endl;
	}
 
	for(i=0;i<20;i++)
	{	c[i]=0; ck[i]=0;count[i]=0; }
   //求初始的L1；
    for (i=1;i<=m;i++)
	{
		for (j=0;j<n;j++)
		{
			for (k=1;k<=t[j][0];k++)
            {
				if(b1[i]==t[j][k])
				{c[i]++; break;
				}
			}
		}
	}
 
	//l[k][0]第一项存出现次数，
	//输出结果
	
	for (i=1;i<=m;i++)
		if(c[i]>=s)
		{l[k1][0]=c[i]; l[k1][1]=b1[i]; k1++;
		}
    ck[1]=k1;
   cout<<endl<<"输出求得的L1"<<endl;
	cout<<"次数  值"<<endl;
    for (i=0;i<k1;i++)
	{	for(j=0;j<2;j++)
		{
			cout<<l[i][j]<<"      ";
		}
		cout<<endl;
	}
  
	//调用子函数，循环扫描连接。
	k=k1; int x=0;  
    int total=k1; //total为频繁项集的总计数
   for(i=2;k>=2;i++) 
   {
	  ck[i]=get(t,l,l,x,ck[i-1],i);
      k=ck[i];
	  x=x+ck[i-1];
      total=total+ck[i];
	  cout<<"输出求得的L"<<i<<endl;
	 cout<<"次数  值"<<endl;
     for (k2=x;k2<total;k2++)
	 {	for(j=0;j<i+1;j++)
		{
			cout<<l[k2][j]<<"      ";
		}
		cout<<endl;
	 }
	
   }

 //  cout<<endl<<total-k1<<endl;
   cout<<endl<<"输出所有的频繁项集："<<endl;
   cout<<"次数  值"<<endl;
   for (k2=k1;k2<total;k2++)
	 {	
	   if(k2<total)
	   {
		   if(k2>=ck[1]&&k2<ck[2]+ck[1])
	        i=3;
           else 	if(k2>=ck[2]+ck[1]&&k2<ck[3]+ck[2]+ck[1])
	                 i=4;
	               else 	if(k2>=ck[3]+ck[2]+ck[1]&&k2<ck[4]+ck[3]+ck[2]+ck[1])
	                  i=5;
				   else 	if(k2>=ck[3]+ck[2]+ck[1]+ck[4]&&k2<ck[5]+ck[4]+ck[3]+ck[2]+ck[1])
	                  i=6;
	   }
	   for(j=0;j<i;j++)
		{
			cout<<l[k2][j]<<"      ";
		}
		cout<<endl;
	 }
 
   int y,y1=0;
   y=0;
   cout<<"一共有频繁项集：  "<<total-k1<<endl<<endl;
  // y1=jield(t,l,22,4,qian,hou,y,credit);
    //生成所有的规则
   cout<<"所有规则如下：  "<<endl;
   for(i=k1;i<total;i++)
 {
	 j=2; 
	 if(i>k1&&i<ck[1]+ck[2])   j=2;
	 else  if(i>=ck[1]+ck[2]&&i<ck[1]+ck[2]+ck[3])   j=3;
	 	 else  if(i>=ck[1]+ck[2]+ck[3]&&i<ck[1]+ck[2]+ck[3]+ck[4])   j=4;
	 y1=jield(t,l,i,j,qian,hou,y,credit);
	 y=y+y1;

 }

   //输出所有的规则
/*   int p;
	cout<<endl<<"输出所有的满足条件的规则："<<endl;
	for(i=0;i<y;i++)
	{
    	for (j=1;qian[i][j]>0;j++)
		{
			cout<<qian[i][j]<<"  ";
		}
		cout<<"     推出的结果为：   ";
       for (p=1;hou[i][p]>0;p++)
		{
			cout<<hou[i][p]<<"  ";
		}
        cout<<"置信度为："<<credit[i]<<endl;
	  
	}*/
   cout<<endl<<"请随便输入一个数以用于退出：";
   cin>>i;
}

//生成频繁项集函数
int get(int t[30][20],int a[100][20],int b[100][20],int k0,int k,int h)
{
	//ko表示L中前K-2一共有多少项，表起点；K表示K-1上一次有多少项，H表示L中有几位数有用
	if (k==0) return(0);
	int ab[100][20];
    int i,j,p,q,m1,x,y,k1,z,z1;   
	y=0; //用于记数产生了多少条项集
	z=0;  //用于记录有用的项集
	int c[100];  //计数
    int dch[100];
	int biao[100];

	for(i=0;i<100;i++)
	{	c[i]=0;  	dch[i]=0; biao[i]=0;}
//	cout<<"输出K0与K、h "<<"k0="<<k0<<"        k="<<k<<"   h="<<h<<endl;
//	cout<<endl<<"输出K0与K、h "<<"k0="<<k0<<"        k="<<k<<"   h="<<h<<endl<<endl;		

	//连接 k表示前一个有多少个项集
	for(i=k0;i<k0+k;i++)
		for(j=i+1;j<k0+k;j++)
		{
        	for(k1=0;k1<100;k1++)     {	c[k1]=0;  }
			
			  m1=0;
			for(p=1;p<h;p++)
			{
				for(q=1;q<h;q++)
				{
					if(a[i][p]==a[j][q])
					{
						m1++;  c[q]=1;
					}
				}
			}

			if(m1==h-2)
			{  //第一项存出现次数
				for(x=1;x<h;x++)
					ab[y][x]=a[i][x];
				for(x=1;x<h;x++)
					if(c[x]==0)  ab[y][h]=a[j][x];
                 y++;
			}
  
		}
//	cout<<endl<<"输出K0与K、h、Y "<<"k0="<<k0<<"        k="<<k<<"   h="<<h<<" y="<<y<<endl;		 
//删除
		for(k1=0;k1<y;k1++)
		{
			z1=0;
			for(i=0;i<n;i++)
			{   
				z=0;
				for (j=1;j<=h;j++)
				{
					for(x=1;x<=t[i][0];x++)
					{
						if(ab[k1][j]==t[i][x])  
						{  z++;  break;} 
					}
				}
				if(z==h)   z1++;
			}
			if(z1>=s)   {dch[k1]=1; }  ab[k1][0]=z1;
		}

		//除去重复项
      for(i=0;i<y;i++)
	  {
		  for(j=i+1;j<y;j++)
		  {
           
		    	m1=0;
			   for(p=1;p<=h;p++)
			   {
				for(q=1;q<=h;q++)
				{
					if(ab[i][p]==ab[j][q])
					{
						m1++; 
					}
				}
			   }
             if(m1==h)
			 {
				 biao[j]=1;
			 }
		  }
	  }

        
/*
		//输出
    cout<<"输出初始的L"<<h<<endl;
	cout<<"次数  值"<<endl;
   for(i=0;i<y;i++)
    if(biao[i]==0)
	{  for(j=0;j<=h;j++)
		{
			cout<<ab[i][j]<<"      ";
		}
		cout<<endl;
	}
*/
	//赋值
	x=k+k0; z=0;
	for(i=0;i<y;i++)
	  if(dch[i]==1&&biao[i]==0)
	  {
		  for(j=0;j<=h;j++)
		  {   b[x][j]=ab[i][j];
		  }
		  z++;  x++;
	  }
    return z;
}

int jield(int t[30][20],int l[100][20],int k,int h,int qian[50][10],int hou[50][10],
		     int y,double credit[50])
{
	//h表示有多少个项，K表示是第几个频繁项集,y表示前有多少项规则
	//qian存前件，hou存后件，credit存置信度
	int i,j,p,q,r,z,z1,a[10];  int t1;
	int k1=0; 	
	int biao[10];
	int ab[100][20],dc[100][20];
 
	for(i=0;i<10;i++)
	{ a[i]=0; biao[i]=0;}
	//求非空子集
	i=1;
	if(i<h)
	{ 
		for(j=1;j<=h;j++)
        {	
			ab[k1][0]=i;
			ab[k1][1]=l[k][j];
			k1++;
		}
	}

    i=2;    t1=1;
	if(i<h)
	{ 
		for(a[1]=1;a[1]<=h;a[1]++)
           for(a[2]=a[1]+1;a[2]<=h;a[2]++)
		   {
		    	ab[k1][0]=i;
			    ab[k1][1]=l[k][a[1]];
				ab[k1][2]=l[k][a[2]];
				k1++;
			
		     }
	}
 
	i=3;    t1=1;
	if(i<h)
	{ 
		for(a[1]=1;a[1]<=h;a[1]++)
           for(a[2]=a[1]+1;a[2]<=h;a[2]++)
             for(a[3]=a[2]+1;a[3]<=h;a[3]++)
		   {
		    	ab[k1][0]=i;
			    ab[k1][1]=l[k][a[1]];
				ab[k1][2]=l[k][a[2]];
                ab[k1][3]=l[k][a[3]];
				k1++;
			
		     }
	}
	i=4;    t1=1;
	if(i<h)
	{ 
		for(a[1]=1;a[1]<=h;a[1]++)
           for(a[2]=a[1]+1;a[2]<=h;a[2]++)
             for(a[3]=a[2]+1;a[3]<=h;a[3]++)
              for(a[4]=a[3]+1;a[4]<=h;a[4]++)
		   {
		    	ab[k1][0]=i;
			    ab[k1][1]=l[k][a[1]];
				ab[k1][2]=l[k][a[2]];
                ab[k1][3]=l[k][a[3]];
				ab[k1][4]=l[k][a[4]];
				k1++;
			    
		     }
	}

	i=5;    t1=1;
	if(i<h)
	{ 
		for(a[1]=1;a[1]<=h;a[1]++)
           for(a[2]=a[1]+1;a[2]<=h;a[2]++)
             for(a[3]=a[2]+1;a[3]<=h;a[3]++)
              for(a[4]=a[3]+1;a[4]<=h;a[4]++)
				  for(a[5]=a[4]+1;a[5]<=h;a[5]++)
		   {
		    	ab[k1][0]=i;
			    ab[k1][1]=l[k][a[1]];
				ab[k1][2]=l[k][a[2]];
                ab[k1][3]=l[k][a[3]];
				ab[k1][4]=l[k][a[4]];
                ab[k1][5]=l[k][a[5]];
				k1++;
			    
		     }
	}
	//产生与AB对应的数组DC

	for(i=0;i<k1;i++)
	{
		for(t1=0;t1<10;t1++)   	{   biao[t1]=0;}
		for(j=1;ab[i][j]>0;j++)
		{
			for (p=1;p<=h;p++)
				if(ab[i][j]==l[k][p])
				{
					biao[p]=1;
					break;
				}
		}	
		r=1;
		for(q=1;q<=h;q++)
		{
			if(biao[q]==0)
			{	dc[i][r]=l[k][q];
			      r++;
			}
		}
	}



	//统计出现的次数
	int k2,x;
		for(k2=0;k2<k1;k2++)
		{
			z1=0;
			for(i=0;i<n;i++)
			{   
				z=0;
				for (j=1;ab[k2][j]>0;j++)
				{
					for(x=1;x<=t[i][0];x++)
					{
						if(ab[k2][j]==t[i][x])  
						{  z++;  break;} 
					}
				}
				if(z==ab[k2][0])   z1++;
			}
		  ab[k2][0]=z1;
		}
	
	//推规则
     double c ;
	 double cre[20],dch[20];
	 for(i=0;i<20;i++)
	 { 
		 cre[i]=0;  dch[i]=0;
	 }
	
	 for(i=0;i<k1;i++)
	 {
		 c=0;
		 c=((double)l[k][0])/ab[i][0];
		 if(c>=d)
		 {
			 dch[i]=1;
		 }
         cre[i]=c*100;
	 }

	//输出
/*	cout<<endl;
    cout<<"分子的次数为： "<<l[k][0]<<endl;
	for(i=0;i<k1;i++)
	{
		for (j=1;ab[i][j]>0;j++)
		{
			cout<<ab[i][j]<<"  ";
		}
		cout<<" 结果为：   ";
      for (p=1;dc[i][p]>0;p++)
		{
			cout<<dc[i][p]<<"  ";
		}
        cout<<"置信度为："<<cre[i]<<endl;
	}
*/

//	cout<<"除去置信度少于d的项："<<endl;
	for(i=0;i<k1;i++)
	{
      if(dch[i]==1)
	  {
    	for (j=1;ab[i][j]>0;j++)
		{
			cout<<ab[i][j]<<"  ";
		}
		cout<<"      结论为：     ";
       for (p=1;dc[i][p]>0;p++)
		{
			cout<<dc[i][p]<<"  ";
		}
	   double zhi=l[k][0]*100/n;
	   cout<<"    置信度为： "<<cre[i]<<"    支持度为："<<zhi<<endl;
	  }
	}

	//将有效的规则保存
	x=0;
	for(i=0;i<k1;i++)
	{
		if(dch[i]==1)
	  {
    	for (j=1;ab[i][j]>0;j++)
		{
		   qian[y][j]=ab[i][j];
		}
       for (p=1;dc[i][p]>0;p++)
		{
		   hou[y][p]=dc[i][p];
		}
	   credit[y]=cre[i];
       y++;
	   x++;
	  }
	}
	
    return x;

}

//统计N与M的值
void sum(int t[30][20])
{
	int x,y,z,i,j,k;
	int c[20];
	for(j=0;j<20;j++)  c[j]=0;
	y=0;
	for(k=0;t[k][1]>0;k++)
	{
		for(i=1;t[k][i]>0;i++)
		{
			x=0;
			for(z=0;c[z]>0;z++)
			{
				if(t[k][i]==c[z])
					 x=1;
			}
			if(x==0) 
			{
				c[y]=t[k][i];
				y++;
			}
		}
       t[k][0]=i-1;
	}
	n=k;
	m=y;
}