apriori.cpp

实现Apriori算法基本功能,获取测试数据集的关联规则

#include <math.h>
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
#include<malloc.h>

struct Database{
	char array[20];
	int supportcount;                //支持度计数
	int count;                       //项集大小 
	int pos;                         //项集个数
};
Database database[100];         //数据集
Database ck[100];               //候选集
Database lk[100];               //频繁集
int minsup=9,G;
double minconf=1;
FILE  *fp;

bool canjoin(char a[],char b[],int x)
{
	int i,s=0;
	   for(i=0;i<x-1;i++)
	   {
		if(a[i]==b[i])
			s++;
	   }
	   if(s==(x-1))
		return true;
	else return false;
}

bool isin(char a[],char b[],int m,int n)
{
	int i,j,sum=0;
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
		{
			if(a[i]==b[j])
				sum++;
		}
	}
	if(sum==m)
		return true;
	else return false;
}
void join(char p[],char q[],int x,int y)                //连接
{
	int i,s=0;
	if(x==1 && y==1)
	{
       p[1]=q[0];
	   x=2;
	}
	if(x>1 && y>1)
	{
	   for(i=0;i<x-1;i++)
	   {
		if(p[i]==q[i])
			s++;
	   }
	   if(s==(x-1))
	   {
		p[x]=q[y-1];
	    x=x+1;
	   }
	}
}

void xiqu(char a[],char b[],char c[],int m,int n)
{
	int i,j,s=0;
	G=0;
    for(i=0;i<n;i++)
	{
		s=0;
		for(j=0;j<m;j++)
		{
			if(b[i]==a[j])
				s++;
		}
		if(s==0)
		{
			c[G]=b[i];
			G++;
		}
	}
}
void main()
{
	int i,j,k,alfa=0,belta=0,tch=0;
	char cc[10];
	Database fset[100];                               //频繁集
	fp=fopen("data5.txt","r");
	rewind(fp);
	while(fgetc(fp)!=EOF)
	{
		while(fgetc(fp)!='\n')
		{
		  fscanf(fp," %c",&database[alfa].array[belta]);            //从文件中读入数据
		  belta++;
		}
		database[alfa].count=belta;
		alfa++;
		belta=0;
	}
	database->pos=alfa;
	fclose(fp);	
	for(i=0;i<alfa;i++)
	{
		for(j=0;j<database[i].count;j++)
			printf("%c ",database[i].array[j]);
		printf("\n");
	}
	ck[0].array[0]=database[0].array[0];
	ck->pos=1;
	ck[0].supportcount=0;
	for(i=0;i<alfa;i++)
	{
		for(j=0;j<database[i].count;j++)
		{
			for(k=0;k<ck->pos;k++)
			{
				if(database[i].array[j]==ck[k].array[0])
					tch++;
			}
			if(tch==0)
			{
				ck[ck->pos].array[0]=database[i].array[j];
				ck[ck->pos].supportcount=0;
				ck->pos++;
			}
			tch=0;
		}
	}
	ck->count=1;
	lk->pos=0;
	lk->count=1;
	for(i=0;i<ck->pos;i++)
	{
		for(j=0;j<database->pos;j++)
		{
			if(isin(ck[i].array,database[j].array,ck->count,database[j].count))
				ck[i].supportcount++;
		}
		if(ck[i].supportcount>=minsup)
		{
			lk[lk->pos].array[0]=ck[i].array[0];
			lk[lk->pos].supportcount=ck[i].supportcount;
			lk->pos++;
		}
	}
	for(i=0;i<lk->pos;i++)
		printf("%c :%d\n",lk[i].array[0],lk[i].supportcount);     //频繁一项集
	fset->pos=lk->pos;
	for(i=0;i<lk->pos;i++)
	{
		fset[i].array[0]=lk[i].array[0];
		fset[i].count=lk->count;
		fset[i].supportcount=lk[i].supportcount;
	}
	do{
		ck->pos=0;
		for(i=0;i<lk->pos-1;i++)
		{
			for(j=i+1;j<lk->pos;j++)
			{
				if(canjoin(lk[i].array,lk[j].array,lk->count))
				{
					join(lk[i].array,lk[j].array,lk->count,lk->count);
					for(k=0;k<lk->count+1;k++)
						ck[ck->pos].array[k]=lk[i].array[k];
					ck->pos++;
				}
			}
		}
		ck->count=lk->count+1;
		for(i=0;i<ck->pos;i++)
		{
			for(j=0;j<ck->count;j++)
				printf("%c",ck[i].array[j]);
			printf("\n");
		}
		lk->count=ck->count;
		lk->pos=0;
		for(i=0;i<ck->pos;i++)
		{
			ck[i].supportcount=0;
			for(j=0;j<database->pos;j++)
			{
				if(isin(ck[i].array,database[j].array,ck->count,database[j].count))
					ck[i].supportcount++;
			}
			if(ck[i].supportcount>=minsup)
			{
				for(k=0;k<lk->count;k++)
				{
					lk[lk->pos].array[k]=ck[i].array[k];
					lk[lk->pos].supportcount=ck[i].supportcount;
				}
				lk->pos++;
			}
		}
		for(i=0;i<lk->pos;i++)
		{
			for(j=0;j<lk->count;j++)
				printf("%c",lk[i].array[j]);
		printf(" :%d\n",lk[i].supportcount); 
		}
		for(i=0;i<lk->pos;i++)
		{
			for(j=0;j<lk->count;j++)
		        fset[fset->pos].array[j]=lk[i].array[j];
		    fset[fset->pos].count=lk->count;
		    fset[fset->pos].supportcount=lk[i].supportcount;
		    fset->pos++;
		}
	}while(lk->pos>0);
	printf("\n*******************************************************\n");
	for(i=0;i<fset->pos;i++)
	{
		for(j=0;j<fset[i].count;j++)
			printf("%c",fset[i].array[j]);
		printf(":%d\n",fset[i].supportcount);
	}
	printf("\n*********************关联规则****************************\n");
	for(i=0;i<fset->pos;i++)
	{
		for(j=0;j<fset->pos;j++)
		{
			if(isin(fset[i].array,fset[j].array,fset[i].count,fset[j].count) && fset[j].count>fset[i].count && (double)(fset[j].supportcount)/(double)(fset[i].supportcount)>=minconf)
			{				
			//printf("%f\n",(double)(fset[j].supportcount)/(double)(fset[i].supportcount));
					xiqu(fset[i].array,fset[j].array,cc,fset[i].count,fset[j].count);
					for(k=0;k<fset[i].count;k++)
					printf("%c",fset[i].array[k]);
					printf("=>");
					for(k=0;k<G;k++)
						printf("%c",cc[k]);
					printf("\n");				
			}
		}
	}
	getchar();
}