📄 apriori_k.c
字号:
/*基于可拓学的apriori,用于数据关联规则挖掘
开发者:Ever Jian(Email:yongjunjian@gmail.com,QQ:282543459)
版本:
v0.1 2009.2.20
参与文献:<<基于可拓理论的关联规则应用研究>>,郭志强
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#define MAX_ELEM_NUM 100000000
//可接受的最大元素数.可以手动修改
#define MAX_STR_NUM 100//元素名称中可接受的最大字符数.可以手动修改
#define MAX_LINE_NUM 10000//每一行可接受的最大数目
//#define DEBUG
void storeElem();
void apriori_k();
long compare (const void * a, const void * b);
void help();
char *elem[MAX_ELEM_NUM];//用于保存所有的元素名称
long elemNum=0;//实际元素的个数
long itemsNum=0;//总的记录数
char *conceptStr=NULL;//概念描述
char *concepts[MAX_ELEM_NUM];//用于记录所用的概念描述
long conceptsNum=0;//用于记录概念的数目
FILE *inputFile=NULL;//用于储存输入数据的文件名
FILE *outputFile=NULL;//用于保存输出结果的文件名
double support=0.2;//支持度．默认为0.2
double confidence=0.8;//置信度．默认为0.8
long *setsH=NULL;//指向由大征集相交生成的征集
long Hdegree=0;//表示Hdegree元征集
long Hnum=0;//表示征集的个数
double *Xnum;//征集中某一字句在记录中出现的次数
double *XYnum;//征集与概念描述组合在记录中出现的次数
long *setsL=NULL;//指向由征集运算经过删除运算后生成的大征集
long Lnum=0;//记录大征集的个数
long Ldegree=0;//表示Ldegree元大征集
long rulesCount=0;//记录得到的总的关联规则数
void storeElem(){//保存输入文件中的所有元素名
char str[MAX_STR_NUM];
long i=0;
long count=0;
elemNum=0;
#ifndef DEBUG
printf("\nReading all elements：\n");
#endif
rewind(inputFile);
while(!feof(inputFile)){
#ifndef DEBUG
printf("\r%d\t\t%d",count, elemNum);
#endif
fscanf(inputFile,"%s",str);
count++;
if(strcmp(str,conceptStr)){//排除概念元素
for(i=0;i<elemNum;i++){//判断该元素是否已经被保存
if(!strcmp(str,elem[i])){
break;
}
}
if(i==elemNum){
elem[elemNum]=(char*)malloc(strlen(str)+1);
strcpy(elem[elemNum],str);
elemNum++;
}
}
}
printf("\n");
/*for(i=0;i<elemNum;i++){
printf("%s\n",elem[i]);
}
**/
}
void storeConcepts(){//将所有的元素作为概念描述保存
char str[MAX_STR_NUM];
long i;
long count=0;
conceptsNum=0;
#ifndef DEBUG
printf("Reading all concepts from file.....\n");
#endif
rewind(inputFile);
while(!feof(inputFile)){
#ifndef DEBUG
printf("\r%d\t\t%d",count, conceptsNum);
#endif
fscanf(inputFile,"%s",str);
count++;
for(i=0;i<conceptsNum;i++){//判断该元素是否已经被保存
if(!strcmp(str,concepts[i])){
break;
}
}
if(i==conceptsNum){
concepts[conceptsNum]=(char*)malloc(strlen(str)+1);
strcpy(concepts[conceptsNum],str);
conceptsNum++;
}
}
printf("\n");
/*for(i=0;i<elemNum;i++){
printf("%s\n",elem[i]);
}
**/
}
void apriori_k(){
long i=0,j=0,k=0;
char line[MAX_LINE_NUM];//用于储存一行字串
long num=0;//一行字串中字符的个数
long capacity=0;//用于记录
itemsNum=0;
#ifndef DEBUG
printf("Start computing rules associated with the concept '%s'......\n",conceptStr);
printf("accociate degree:");
#endif
Hdegree=1;//一元征集
setsH=calloc(elemNum,sizeof(long));
for(i=0;i<elemNum;i++){//构造一元征集H1
setsH[i]=i;
}
Hnum=i;
Xnum=calloc(Hnum,sizeof(double));
XYnum=calloc(Hnum,sizeof(double));
rewind(inputFile);
#ifndef DEBUG
printf("1\40");
#endif
while(!feof(inputFile)){//统计数据，用于计算征集的支持度和置信度
fgets(line,MAX_LINE_NUM,inputFile);//读取一行记录
itemsNum++;
for(i=0;i<Hnum;i++){
if(strstr(line,elem[i])!=NULL){
Xnum[i]++;
if(strstr(line,conceptStr)!=NULL){
XYnum[i]++;
}
}
}
}
Lnum=0;
#ifdef DEBUG
printf("H1:\n");
#endif
for(i=0;i<Hnum;i++){//进行删除运算，准备构造大征集
#ifdef DEBUG
printf("%s%s\t",elem[setsH[i]],conceptStr);
printf("%f\t",XYnum[i]/itemsNum);
printf("%f\n",XYnum[i]/Xnum[i]);
#endif
if((XYnum[i]/itemsNum)<support){
Xnum[i]=-1;//置-1表示将对应的征集删除
}
else{
if(XYnum[i]/Xnum[i]>=confidence){//输出规则
rulesCount++;
fprintf(outputFile,"%s<--%s(%.2f,%.2f)\n",conceptStr,elem[i],XYnum[i]/itemsNum,XYnum[i]/Xnum[i]);//输出关联规则
Xnum[i]=-1;//将些征集删除是为了避免规则冗余
}else{
Lnum++;
}
}
}
if(Lnum>0){
Ldegree=1;
setsL=calloc(Lnum,sizeof(long));
j=0;
#ifdef DEBUG
printf("L1:\n");
#endif
for(i=0;i<Hnum;i++){//构造一元大征集,用于进行征集的交运算
if(Xnum[i]!=-1){
setsL[j]=setsH[i];
j++;
#ifdef DEBUG
printf("%s%s\t",elem[setsH[i]],conceptStr);
printf("%f\t",XYnum[i]/itemsNum);
printf("%f\n",XYnum[i]/Xnum[i]);
#endif
}
}
}
while(Lnum>1){//当大征集中元素个数大于1时，进行交运算
Hnum=0;
Hdegree++;
capacity=1000;
setsH=calloc(1000,sizeof(long)*Hdegree);//预分配容纳1000个Hdegree元征集的空间，以后不够用时，按100递增
for(i=0;i<Lnum-1;i++){//大征集的相交运算
for(j=i+1;j<Lnum;j++){
for(k=0;k<Ldegree;k++){//判断两个征集是否能够进行交运算（即除最后一个元素不同外，其它元素都相同）
if(setsL[i*Ldegree+k]!=setsL[j*Ldegree+k]){
break;
}
}
if(k==Ldegree-1){//满足相交的条件
if((Hnum+1)>capacity){//空间不够用
setsH=realloc(setsH,(capacity+100)*sizeof(long)*Hdegree);//增加100个单位的空间
capacity=capacity+100;
}
for(k=0;k<Ldegree-1;k++){//进行相交运算
setsH[Hnum*Hdegree+k]=setsL[i*Ldegree+k];
}
setsH[Hnum*Hdegree+Ldegree-1]=setsL[i*Ldegree+Ldegree-1];
setsH[Hnum*Hdegree+Ldegree]=setsL[j*Ldegree+Ldegree-1];
Hnum++;
}
}
}
if(Hnum>0){//对征集进行删除运算，构造大征集
Xnum=calloc(Hnum,sizeof(double));
XYnum=calloc(Hnum,sizeof(double));
rewind(inputFile);
#ifndef DEBUG
printf("%d\40",Hdegree);//输出计算的层次
#endif
while(!feof(inputFile)){//统计数据，用于计算征集的支持度和置信度
fgets(line,MAX_LINE_NUM,inputFile);//读取一行记录
for(i=0;i<Hnum;i++){
for(j=0;j<Hdegree;j++){
if(strstr(line,elem[setsH[i*Hdegree+j]])==NULL){
break;
}
}
if(j==Hdegree){//记录中包含该征集
Xnum[i]++;
if(strstr(line,conceptStr)!=NULL){
XYnum[i]++;
}
}
}
}
Lnum=0;
#ifdef DEBUG
printf("H%d:\n",Hdegree);
#endif
for(i=0;i<Hnum;i++){//进行删除运算，准备构造大征集
#ifdef DEBUG
for(j=0;j<Hdegree;j++){
printf("%s",elem[setsH[i*Hdegree+j]]);
}
printf("%s\t%f\t",conceptStr,XYnum[i]/itemsNum);
printf("%f\n",XYnum[i]/Xnum[i]);
#endif
if((XYnum[i]/itemsNum)<support){
Xnum[i]=-1;//置-1表示将其删除
}
else{
if(XYnum[i]/Xnum[i]>=confidence){//输出关联规则
rulesCount++;
fprintf(outputFile,"%s<--",conceptStr);//输出关联规则
for(j=0;j<Hdegree-1;j++){
fprintf(outputFile,"%s\40",elem[setsH[i*Hdegree+j]]);
}
fprintf(outputFile,"%s",elem[setsH[i*Hdegree+j]]);
fprintf(outputFile,"(%.2f,%.2f)\n",XYnum[i]/itemsNum,XYnum[i]/Xnum[i]);
Xnum[i]=-1;//将该征集删除,避免规则冗余
}else{
Lnum++;
}
}
}
if(Lnum>0){
Ldegree++;
setsL=calloc(Lnum,sizeof(long)*Ldegree);
j=0;
#ifdef DEBUG
printf("L%d:\n",Ldegree);
#endif
for(i=0;i<Hnum;i++){//构造大征集,用于进行征集的交运算
if(Xnum[i]!=-1){
#ifdef DEBUG
for(k=0;k<Hdegree;k++){
printf("%s",elem[setsH[i*Hdegree+k]]);
}
printf("%s\t%f\t",conceptStr,XYnum[i]/itemsNum);
printf("%f\n",XYnum[i]/Xnum[i]);
#endif
for(k=0;k<Ldegree;k++){
setsL[j*Ldegree+k]=setsH[i*Ldegree+k];
}
qsort(setsL+j*Ldegree,Ldegree,sizeof(long),compare);//对每一个大征集进行排序处理，接下来用于检验可否相关
j++;
}
}
}
}else{
Lnum=0;
}
}
}
long compare (const void * a, const void * b)//qsort()的辅助函数
{
return ( *(long*)a - *(long*)b );
}
void help(){//输出帮助信息
printf("useage:apriori_k inFile outFile [options]\n");
printf("-s\tminmum support\n");
printf("-c\tminmum confidence\n");
printf("-d\tconcepts list\n");
printf("--all\ttreat each element in the inFile as concept\n\n");
printf("Find associated rules based on apriori algorithm using extension theory.\n");
printf("\tversion 0.1(2009.2.20)\t(c)2009 Ever Jian(yongjunjian@gmail.com)\n");
printf("\t\t\t\t(:Have Fun:)\n");
}
void main(long argc,char*argv[]){
clock_t start,begin;
//long diff;
long i=0;
char *inputFileName=NULL;
char *outputFileName=NULL;
begin=clock();
if(argc<3){//当参数少于2个时,只输出帮助信息
help();
exit(0);
}
inputFileName=argv[1];//第一个参数为输入文件名
outputFileName=argv[2];//第二个参数为输出文件名
inputFile=fopen(inputFileName,"rt");
outputFile=fopen(outputFileName,"wt");
i=3;
conceptsNum=0;
while(i<argc){
if(!strcmp(argv[i],"-d")){//输入的为概念描述
i++;
while(i<argc){
if(strcmp(argv[i],"-d")&&strcmp(argv[i],"-c")&&strcmp(argv[i],"-s")&&strcmp(argv[i],"--all")){
concepts[conceptsNum]=argv[i];
conceptsNum++;
i++;
}else{
i--;
break;
}
}
}else if(!strcmp(argv[i],"-c")){//输入的为置信度
i++;
confidence=atof(argv[i]);
i++;
}else if(!strcmp(argv[i],"-s")){//输入的为置信度
i++;
support=atof(argv[i]);
i++;
}else if(!strcmp(argv[i],"--all")){//将每一个元素都作为一个概念描述
start=clock();
storeConcepts();
#ifndef DEBUG
printf("Time eclipsed:%.3fs\n",(double)(clock()-start)/CLOCKS_PER_SEC);
#endif
i++;
}else{
printf("参数无法识别！");
exit(-1);
}
}
if(conceptsNum==0){
storeConcepts();
}
for(i=0;i<conceptsNum;i++){//对每一个概念进行计算
conceptStr=concepts[i];
start=clock();
storeElem();//先将所有的元素保存起来,使得一个元素与一个数组下标对应起来
#ifndef DEBUG
printf("\nTime eclipsed:%.3fs\n",(double)(clock()-start)/CLOCKS_PER_SEC);
#endif
start=clock();
apriori_k();
#ifndef DEBUG
printf("\nTime eclipsed:%.3fs\n",(double)(clock()-start)/CLOCKS_PER_SEC);
#endif
}
#ifndef DEBUG
printf("\nFind %d rules in %s within %0.3f seconds.\n",rulesCount,outputFileName,(double)(clock()-begin)/CLOCKS_PER_SEC);
#endif
fclose(inputFile);
fclose(inputFile);
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -