apriori.c

FAST apriori.cpp 基于数组和为运算的apriori算法实现,采用为运算来测试子集的存在性

#include<stdio.h>
typedef  struct
{
int item[10];  //数据项
} D_Node;      //数据库D
typedef  struct
{
int item[10];  //数据项,用item[0]保存支持度
} C_Node; //候选集
typedef  struct
{
int item[10];  //数据项,用item[0]保存支持度
} L_Node;//频繁集
C_Node C[20][10];
L_Node L[20][10];
D_Node D[20];
int min_supp;  //最小支持度
void  InPut()
{
 int i,j,n,n1;
 printf("请输入最小支持度计数min_count:");
 scanf("%d",&min_supp);
  printf("请输入交易集的大小");
  scanf("%d",&D[0].item[0]);
  n=D[0].item[0];
   printf("输入各个记录时请直接输入数字\n\n");
     for(i=1;i<=n;i++)  //for1
     {
        printf("请输入交易[%d]中记录的个数(n)",i);
         scanf("%d",&n1);
         D[i].item[0]=n1;
           for(j=1;j<=n1;j++)  //for2
           {
              printf("请输入交易[%d]的记录项[%d]:",i,j);
             scanf("%d",&D[i].item[j]);
           }//for2
           }  //for1
     }//end of InPut
void  C1()
{
	//功能：扫描数据集D生成1项候选集C1
	//输入：数据集D
	//输出1项候选集C1
	//初始条件 数据集D 非空
   int i,j,k;
   int no=1,temp=0;
   C[1][0].item[0]=0;  //1 项集的个数，在本算法中，用C[n][k].item[0]来保存候选集Cn的第k项的支持度
   if(D[0].item[0]!=0)
   {
      C[1][1].item[1]=D[1].item[1];
   }
    for(i=1;i<=D[0].item[0];i++)  //for1
    {
         for(j=1;j<=D[i].item[0];j++)  //for2
    	 {
               temp=1;
               for(k=1;k<=no;k++)  //for3
			   {
                  if(C[1][k].item[1]==D[i].item[j])
        		  {
                     C[1][k].item[0]++;  //支持度加1
	                     temp=0;  //
                  }   //if
               }//end for3
              if(temp)//生成新的项集
        	  {
                    C[1][++no].item[1]=D[i].item[j];
                    C[1][no].item[0]=1;
        	  }
         }//end for2
    } // end  for1
    C[1][0].item[0]=no;//数据项的个数
}  //end of  C1()
void Cn( int n)
{
	//用频繁集Ln-1为基础，通过连接得到n项候选集Cn
 int i,j,k,p,q,s,t,num;
 int no=0,temp=0,count;
 C[n][0].item[0]=0;  //初始化

num=L[n-1][0].item[0];  //num是Ln-1项集的数据个数
   for(i=1;i<=num;i++)
      for(j=i+1;j<=num;j++)   //for2
         {
		    temp=1;  //测试是否满足联结条件
              if(n>2)//if 1
              {
                  for(k=1;k<n-1;k++)    	//for3
              	  {
					 if(L[n-1][i].item[k]!=L[n-1][j].item[k])
                   {  temp=0;
                     break; }//if 1
                    }//end for3
                 }//end if1
                      if(temp==1)//满足联结条件
                     {
                          // printf("in if 2  no=%d\n",no);
                     no++;
                    for(p=1;p<=n-1;p++)
                    C[n][no].item[p]=L[n-1][i].item[p];
                    C[n][no].item[p]=L[n-1][j].item[p-1];
                    C[n][no].item[0]=0;
                         for(q=1;q<=D[0].item[0];q++)  //for5  测试其支持度
						 {
							 count=0; //count用来记数,当所测试的项存在时,count加1,当count=n时，则子集存在
                               for(s=1;C[n][no].item[s]!=0;s++)  //for6
                	     	   {
                                      for(t=1;t<=D[q].item[0];t++)  //for7
									  {
                                             if(C[n][no].item[s]==D[q].item[t])
											 {   count+=1;
									             break;
											 }
									  }//end for7
							   }//end for 6
                           if(count==n) C[n][no].item[0]+=1;//子集存在,第no项的支持度加1
						 }//end for5
                      C[n][0].item[0]+=1;
					  }//end if2
           }//end for2
     
}//end of Cn()
void L1()
{
    int i,j,k;
	j=0;
   L[1][0].item[0]=0;
   //printf("C[1][0].item[0]=%d\n",C[1][0].item[0]);
   for(i=1;i<=C[1][0].item[0];i++)
   {
       if(C[1][i].item[0]>=min_supp)
       {
       j+=1;
        for(k=1;k<=1;k++)
         L[1][j].item[k]=C[1][i].item[k];
        L[1][j].item[0]=C[1][i].item[0];
	//	printf("L[1][%d].item[1]=%d   ",j,L[1][j].item[1]);  测试功能时加的
	//	printf("  -------------%d\n",L[1][j].item[0]);
       }
   }//end for1
   L[1][0].item[0]=j;
}//end of L1()
void Ln(int n)
{
    int i,j,k;
	Cn(n);
    j=0;
    L[n][0].item[0]=0;
	  // printf("in Ln(%d) C[%d][0].item[0]=%d\n",n,n,C[n][0].item[0]);
   for(i=1;i<=C[n][0].item[0];i++)  //for 1
   {
       if(C[n][i].item[0]>=min_supp)
       {
         j+=1;
        for(k=1;k<=n;k++)
         L[n][j].item[k]=C[n][i].item[k];
        L[n][j].item[0]=C[n][i].item[0];
       }  //end if
   }//end for1
   /*  for(i=1;i<=j;i++)
       for(k=0;k<=n;k++)
	 {printf("L[%d][%d].item[%d]=%d \n",n,i,k,L[n][i].item[k]);
	 }   */
L[n][0].item[0]=j; //保存数据的个数
}//end of Ln(int n)
  void  OutPut(int n)
  {
     int i,j,k;
     printf("\n频繁项目集L%d如下:\n",n);
     k=L[n][0].item[0];
         if(k!=0)
         {
             for(i=1;i<=k;i++)
        	 {
                printf("{");
               for(j=1;j<=n;j++)
			     printf("  I%d ",L[n][i].item[j]);
			     printf("}        支持度:%d\n",L[n][i].item[0]);
             }//for
          }
         else                printf("项目集为空\n");
  }
  void main()
  {
	int i;
	int n=1;
    InPut();
	C1();//初始化,生成1项候选集C1
	L1();//得到1项频繁集L1
    while(L[n][0].item[0]!=0)
	{
		n+=1;
        Ln(n);
	}
    for(i=1;i<=n;i++)
        OutPut(i);
  }