apriori.cpp

本算法是基于数据挖掘与关联规则

// apriori.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <iostream>       //标准输入输出流定义
#include <fstream>        //文件流类定义
#include <vector>
#include <algorithm>
#include <Windows.h>
using namespace std;

bool   mysort(int*  m,int*   n) //一项集排序
{ 
	return m[0]<n[0] ;  
} 

int gen_oneFreqItemSet(int min_sup,vector<int* > &v)   //生成频繁一项集
{
	
	FILE *stream; //文件指针
    int temp;  
	int *tempItem1;
	bool judge;
	stream=fopen("2.txt","r"); //打开文件
	int judgeEOF;
	
	while(!feof(stream)) //到文件末尾就返回非零
		
	{  
		judge=true;
		judgeEOF=fscanf(stream,"%d",&temp); //每次扫描一个整形数字
		if(judgeEOF==EOF)
		{break;}
		if(v.empty())     //VECTOR为空，则添加项目
		{
			
			int* a=new int[2];
			a[0]=temp;
			a[1]=1;
			v.push_back(a);
		}else{                           //如果VECTOR里已经有了该项目，则只需增加记数统计，如果没有则添加到VECTOR队尾
			
			for(int i=0;i<v.size();i++)
			{
				tempItem1=v.at(i);
				if(temp==tempItem1[0])
				{
					tempItem1[1]++;
					judge=false;
					break;
				}
			}
			if(judge)
			{
				int *item=new int[2];
				item[0]=temp;
				item[1]=1;		 
				v.push_back(item);
			}
		}		  
	}
	
	
	int *  tempItem2;
	vector<int*>::iterator itr;    
	for(int t=0;t<v.size();t++)   //删除支持度低的项，得到频繁一项集
	{
		
		tempItem2=v.at(t);
		if(tempItem2[1]<min_sup)      //删除一项后，循环变量不要增加，故有t--；         
		{
			itr=v.begin();
			v.erase(itr+t);
			t--;                   
			
		}		
	}
	
	sort(v.begin(),v.end(),mysort); //需要<algorithm>头
	//oneFreqSize=v.size();
		for(int j=0;j<v.size();j++)  //测试输出VECTOR
		{
		int* t=v.at(j);
		cout<<t[0]<<"   "<<t[1]<<"\n";
		
		  }
		
	cout << "1 itmes done"<< endl;
	return 0;
}

int gen_apriori(int k,vector<int* > vSource,vector<int* >& vCandi) //由k-1项频繁集生成k项候选集
{ 
	cout<<"aaa"<<endl;
	bool judge=true;
	int vSourceSize=vSource.size();
	for(int i=0;i<vSourceSize;i++)
	{
		for(int j=i+1;j<vSourceSize;j++)
		{
			judge=true;
			for(int m=0;m<k-2;m++)
			{
				if(vSource.at(i)[m]!=vSource.at(j)[m])
				{
					judge=false;
					break;
				}
				
			}
			if(judge)  //如果前k-2项都相等，那么可以合并成K项
			{     //合并
				int * item=new int[k+1];
				item[k]=0; //第k+1个元素是用来记录支持度的
				for(int n=0;n<k-2;n++)
				{
                    item[n]=vSource.at(i)[n];
				}
				if(vSource.at(i)[k-2]<vSource.at(j)[k-2])
				{
					item[k-2]=vSource.at(i)[k-2];
					item[k-1]=vSource.at(j)[k-2];
				}else{
					item[k-2]=vSource.at(j)[k-2];
					item[k-1]=vSource.at(i)[k-2];					 
				}
				
				
				if(k==2)
					
				{
					
					vCandi.push_back(item);
					
				}else
					
				{
					
					//剪枝,当候选k项的k-1子集（一定包含k-2和k-1项的子集）在频繁k-1项集中出现次数
					
					//少于k-2时，就将候选该k项剪去。
					
					int count=0;
					
					int h=0;
					
					int flag1=true;
					
					for(int l1=0;l1<k;l1++)
					{
						int* subSet=new int[k];
						h=0;
						//取一个K-1子集
						for(int l2=0;l2<k;l2++)
						{    
							
							if(l1!=l2)
							{
								subSet[h]=item[l2];
								h++;
							}
							
							
							
						}
						//flag1=true;
						for(int t1=0;t1<vSourceSize;t1++)
						{
							flag1=true;
							for(int t2=0;t2<k-1;t2++)
							{  // cout<<vSource.at(t1)[t2]<<endl;
								if(subSet[t2]!=vSource.at(t1)[t2])
								{
									flag1=false;
									break;
								}
								
								
							}
							if(flag1)
							{
								
								count++;
								break;
							}
							
						}
					}
						if(count==k)
						{
							vCandi.push_back(item);
						}
								
					
					
				}
				
				
				
			}
		//	judge=true;
		}
	}
	
	
			 /*
			 for(int s=0;s<vCandi.size();s++)  //测试输出VECTOR
			 {
			 for(int h=0;h<k;h++)
			 {
			 cout<<vCandi.at(s)[h]<<"  ";
			 }
			 
			   cout<<endl;
			   
						 }*/
						 
						 
	return 0;
}


int gen_freqItemSet(int k,int min_sup,vector<int*>& FreqSet )
{
	//FILE f;
	ifstream inFile;//输入文件对象
	char buffer[10240]; //存储一个事务项
	int vectorSize=FreqSet.size();//用来统计FreqSet的size
	int* count=new int[vectorSize]; //用来统计项目出现次数
	int index=0,flag=0;
	string tempItem="";
	int  tempInt;
	memset(buffer,0,10240);
	
	inFile.open("2.txt",ios::out|ios::app);
	while(!inFile.eof())
	{   
		
		index=0;
		inFile.getline(buffer,10239);//读取一行，也就是读取一个事务
		tempItem="";
		
		//计数数组清零
		for(int l=0;l<vectorSize;l++)
		{
			count[l]=0;
		}
		
		//读取每一个item
		
		while((buffer[index]!='\0')||(flag==0))
		{
			if(buffer[index]!=' '&&buffer[index]!='\0')
			{
				tempItem+=buffer[index];
				flag=0;
				
			}else
			{
				if(!flag)
				{
					
					
					tempInt=atoi(tempItem.c_str());
					
					//统计一个事务项中所有item对于每一个候选频繁K项来说，出现的次数计数
					for(int i=0;i<vectorSize;i++)
					{
						for(int j=0;j<k;j++)
						{
							if(tempInt==FreqSet.at(i)[j])
							{
								count[i]++;
								break;
							}
						}
					} 
					
					tempItem="";
					flag=1;
				}
				
			}
			index++;
		}
		
		//看每一个候选K项是否在该事务项中出现，出现则支持度加1，不出现则不加
		for(int m=0;m<vectorSize;m++)
		{
			if(count[m]==k)
			{
				FreqSet.at(m)[k]++;
			}
			
		}
		memset(buffer,0,10240);
		
		
		
	}
	//删除支持度低的项，得到频繁K项集
	
	
	
	vector<int*>::iterator itr; 
	int* tempItem2;
	for(int t=0;t<FreqSet.size();t++)  
	{
		
		tempItem2=FreqSet.at(t);
		if(tempItem2[k]<min_sup)      //删除一项后，循环变量不要增加，故有t--；         
		{
			itr=FreqSet.begin();
			FreqSet.erase(itr+t);
			t--;                   
		}
		
	}
	
	
	
	//cout<<buffer<<endl
	
	
	
	for(int n=0;n<FreqSet.size();n++)  //测试输出VECTOR
	{   
		int* a=FreqSet.at(n);
		for(int r=0;r<k+1;r++)
		{ 
			cout<<a[r]<<"   ";
		}
		cout<<endl;
		
	}
	/*
    //读取文件流
    for()//循环读行
    {
	for()//依次读取每一行的项
	{
	if()//该项存在在freqSet的元素中
	a[i]++
	
	  }
	  for()// 对于每一个侯选项来循环
	  if(  [i]=k)
	  {
	  freqSet.at(i)[k]++//  前面应该先置0
	  }
	  } 
    // 统计支持度的数目*/
	
	
	return 0;
}



int main ()
{
	int start =GetTickCount();
	cout<<start<<endl;
	const int min_sup=45000; //最小支持度
	vector<int* > oneFreqSet;//记录频繁一项集
	vector<vector<int*>*> vResult; //存放指向频繁项集的指针
	gen_oneFreqItemSet(min_sup,oneFreqSet); //生成频繁一项集
	
	if(oneFreqSet.size()==1)
	{
		return 0;
	}
	
    // vector<int *>* ptr=&(oneFreqSet); 
	// cout<<(&(gen_oneFreqItemSet(min_sup)))->size()<<endl;
	//vector<int> resultSize;//每一个频繁项集包含的个数
	//int oneFreqSize;//频繁一项集包含的个数
	
    vResult.push_back(&oneFreqSet); //生成频繁一项集
	
	
	// 	cout<<vResult.at(0)->at(1)[1]<<endl;
	//  int	k=2;
	//  vector<int* >* FreqSet=new vector<int* >; //存放频繁K项集的vector
	// 	gen_apriori(k,*vResult.at(k-2),FreqSet); //由k-1项频繁集生成k项候选集
	//	if(FreqSet->size()==0)
	//			{
	//				return 0;
	//			}
	//  gen_freqItemSet(k,min_sup,FreqSet);
	
	for(int k=2;vResult.at(k-2)->size()!=0;k++)
	{
		cout << k << "itme set ..."<< endl;
		if(vResult.at(k-2)->size()==1)
		{
			return 0;
		}
		vector<int* >* FreqSet=new vector<int* >; //存放频繁K项集的vector
		gen_apriori(k,*(vResult.at(k-2)),*FreqSet); //由k-1项频繁集生成k项候选集
		// 	cout<<FreqSet->size()<<endl;//测试生成的vector的size
		
		if(FreqSet->size()==0)
		{
			int end=GetTickCount(); 
	     	cout<<end<<endl;
           - cout<<end-start;
			return 0;
		}
		cout <<FreqSet->size()<<endl;
		gen_freqItemSet(k,min_sup,*FreqSet);
		vResult.push_back(FreqSet);
		cout <<FreqSet->size()<<endl;
		cout << k << "itme set done."<<vResult.at(k-1)->size() <<endl;
		
	}
	
		
    return 0;
}