apriori.cpp

Apriori算法的VC++实现,数据挖掘关联算法

#include <iostream>//标准I/O头文件
#include <windows.h>//windows库
#include <vector>//vector容器
#include <set>//set容器
#include <algorithm>//容器算法头文件
#pragma warning(disable : 4996)//去掉4996警告错误
using namespace std ;//命名空间
#define BUFLENGTH 10//缓冲区长度
#define MAXELEMENT 100//元素最大个数
typedef vector<int> Vector_int;
typedef vector<Vector_int> DoubleVector_int;
typedef set<int>    Set_int;

int MINSUPPORT;//支持度
int MINCONFIDENCE;//置信度

class CStructItem//定义CStructItem类
{
public:
	Vector_int  vItem;//项
	int  iSupport;//支持度
	CStructItem()//构造函数
	{
		vItem.clear();
		iSupport=0;
		
	}
};
typedef vector<CStructItem>        Vector_CStructItem;
typedef vector<Vector_CStructItem> DoubleVector_CStructItem;


DoubleVector_CStructItem All_L;

/////函数声明
Vector_CStructItem InitDataBase(Vector_CStructItem DataBase);//初始化文本数据库
DoubleVector_int AnalyzeAllSubSet(Vector_int V,int k);//分析集合中的所有子集
int CountSupport(Vector_CStructItem DataBase,CStructItem sItem,int k);//计算支持度
Vector_CStructItem Apriori_gen(Vector_CStructItem DataBase,Vector_CStructItem L,int k);//主体算法
void ShowAndSaveDataBase(Vector_CStructItem DataBase);//显示和保存数据库
void ShowAndSaveL(Vector_CStructItem L,int k);//显示和保存L集合
int CountItem(const char * Str);//计算字符串单词项数
char* TakeItemCommand(char *Str,int n);////////从多节命令中获得某节命令
int CountChar(const char *Str);/////////////////////////////计算字符串字数


Vector_CStructItem InitDataBase(Vector_CStructItem DataBase)//初始化文本数据库
{
	Vector_CStructItem L;
	CStructItem sItem;
	Set_int sTemp;
	set <int>::iterator pIter;
	int ArrayElement[MAXELEMENT+1];
	memset(ArrayElement,0,MAXELEMENT);//把ArrayElement的数组置０

	int DataBaseSize=DataBase.size();//获取数据大小
	int n;
	for(int i=0;i<DataBaseSize;i++)
		sort(DataBase.at(i).vItem.begin(),DataBase.at(i).vItem.end());//排序

	///////把数据放到set,排除重复的,同时计算各元素的支持度
	for(int i=0;i<DataBaseSize;i++)
	{
		n=DataBase.at(i).vItem.size();
		for(int j=0;j<n;j++)
		{
			sTemp.insert(DataBase.at(i).vItem.at(j));
			ArrayElement[DataBase.at(i).vItem.at(j)]++;
		}
	}
	
	//////测试set集合元素
	for (pIter =sTemp.begin( ); pIter != sTemp.end( ); pIter++ )
	{
		if(ArrayElement[*pIter]>=MINSUPPORT)
		{
			sItem.vItem.push_back(*pIter);
			sItem.iSupport=ArrayElement[*pIter];
			L.push_back(sItem);
			sItem.vItem.clear();
		}
	}
	return L;
}
/////////////////////////////////////分析所有子集
DoubleVector_int AnalyzeAllSubSet(Vector_int V,int k)
{
	DoubleVector_int AllSubSet;//定义一个用来容纳所有子集的集合
	Vector_int Vtemp;
	int size=V.size();
	for(int i=1;i<(1<<size);i++)
	{
		for(int j=0;j<size;j++)
		{
			if   (i   &   (1   <<   j))
				Vtemp.push_back(V.at(j));
		}
		if(Vtemp.size()==k)
		{
			AllSubSet.push_back(Vtemp);//把所有该子集丢进AllSubSet里面去
		}
		Vtemp.clear();
	}
	return AllSubSet;//返回它
}
////////////////////////////////////////////计算a支持度
int CountSupport(Vector_CStructItem DataBase,int a)
{
	int DataBaseSize=DataBase.size();
	int DVtempSize;
	int count=0;//支持度记数

	for(int i=0;i<DataBaseSize;i++)
	{
		DVtempSize=DataBase.at(i).vItem.size();
		for(int j=0;j<DVtempSize;j++)
		{
			if(DataBase.at(i).vItem.at(j)==a)
				count++;
		}
	}
	return count;//返回记数个数
}
////////////////////////////////////////////重载 计算l支持度
int CountSupport(Vector_CStructItem DataBase,CStructItem sItem,int k)
{
	int DataBaseSize=DataBase.size();
	DoubleVector_int DVtemp;
	int DVtempSize;
	int count=0;//支持度记数
	for(int i=0;i<DataBaseSize;i++)
	{
		DVtemp=AnalyzeAllSubSet(DataBase.at(i).vItem,k+1);
		DVtempSize=DVtemp.size();
		for(int j=0;j<DVtempSize;j++)
		{
			if(DVtemp.at(j)==sItem.vItem)
				count++;
		}
		DVtemp.clear();
	}
	return count;//返回记数个数
}
Vector_CStructItem Apriori_gen(Vector_CStructItem DataBase,Vector_CStructItem L,int k)
{
	Vector_CStructItem C;
	int iSize = L.size();
	int iTheLastSame=k-1;
	CStructItem sItem;
	/////////////////////////合并工作
	for( int i=0;i<iSize;i++)
	{
		for(int j=i+1;j<iSize;j++)
		{
			sItem.vItem.clear();//清空sItem项集合
			for(int n=0;n<=k;n++)
			{
				if(n==iTheLastSame)
				{
					if(L.at(i).vItem.at(n)<L.at(j).vItem.at(n))
					{
						sItem.vItem.push_back(L.at(i).vItem.at(n));
						sItem.vItem.push_back(L.at(j).vItem.at(n));
						sItem.iSupport=CountSupport(DataBase,sItem,k);//计算各项支持度，并赋值
						/////////////////Prune
						if(sItem.iSupport>=MINSUPPORT)//假如大于预设置的最小支持度
						{
							C.push_back(sItem);//就丢到C集合里面
						}
						break;
					}
				}
				else
				{
					if(L.at(i).vItem.at(n) == L.at(j).vItem.at(n))
						sItem.vItem.push_back(L.at(i).vItem.at(n));
					else
						break;
				}
			}
		}
	}
	return C;
}
void ShowAndSaveDataBase(Vector_CStructItem DataBase)
{
	FILE *pFile=NULL;
	char buf[BUFLENGTH]={0};
	int DataBaseSize=DataBase.size();
	int ItemSize;
	if( fopen_s( &pFile, "Result.txt", "w" ) == 0 )//打开或创建Result.txt来写入
	{
		cout<<"数据库的数据为："<<endl;
		fwrite("数据库的数据为：\r\n",1,sizeof("数据库的数据为：\r\n"),pFile);
		for(int i=0;i<DataBaseSize;i++)
		{
			memset(buf,0,BUFLENGTH);//把buf数组置0
			ItemSize=DataBase.at(i).vItem.size();
			cout<<endl<<"TID\t";
			fwrite("\r\nTID\t",1,sizeof("\r\nTID\t"),pFile);//写入回车换行
			for(int j=0;j<ItemSize;j++)
			{
				memset(buf,0,BUFLENGTH);//把buf数组置0
				cout<<DataBase.at(i).vItem.at(j)<<'\t';//屏幕输出
				sprintf(buf,"%d\t",DataBase.at(i).vItem.at(j));//字符格式化
				fwrite(buf,1,sizeof(buf),pFile);//把缓冲区写入
			}
		}
		memset(buf,0,BUFLENGTH);//把buf数组置0
		fwrite("\r\n\r\n",1,sizeof("\r\n\r\n"),pFile);//写入回车换行
		fclose(pFile);//关闭文件
	}
	return;
}
void ShowAndSaveL(Vector_CStructItem L,int k)//显示和保存L集合
{
	FILE *pFile=NULL;
	char buf[BUFLENGTH]={0};
	int LSize=L.size();
	int ItemSize;
	if( fopen_s( &pFile, "Result.txt", "a" ) == 0 )//打开文件
	{
		cout<<"L"<<k<<": "<<endl;
		sprintf(buf,"\r\nL%d :\r\n",k);//格式化回车换行到缓冲区
		fwrite(buf,1,sizeof(buf),pFile);//把缓冲区写入
		for(int i=0;i<LSize;i++)
		{
			memset(buf,0,BUFLENGTH);//把buf置０
			ItemSize=L.at(i).vItem.size();
			cout<<"TID\t";
			fwrite("\tTID\t",1,sizeof("\tTID\t"),pFile);//写入
			for(int j=0;j<ItemSize;j++)
			{
				memset(buf,0,BUFLENGTH);//把buf置０
				cout<<L.at(i).vItem.at(j)<<'\t';
				sprintf(buf,"%d\t",L.at(i).vItem.at(j));
				fwrite(buf,1,sizeof(buf),pFile);
			}
			memset(buf,0,BUFLENGTH);
			cout<<":"<<L.at(i).iSupport<<endl;
			sprintf(buf,":%d\r\n",L.at(i).iSupport);
			fwrite(buf,1,sizeof(buf),pFile);
		}
		memset(buf,0,BUFLENGTH);
		fwrite("\r\n\r\n",1,sizeof("\r\n\r\n"),pFile);
		fclose(pFile);//关闭文件
	}
	return;
}
/////////////////////////////计算字符串字数
int CountChar(const char *Str)
{
	int i;
	for(i=0;Str[i]!='\0';i++);
	return i;
}

/////////////////////////////// 计算字符串单词项数
int CountItem(const char * Str)
{           
	int count = 0;
	for(int i=0,j=1;Str[i]!='\0';i++,j++)
	{                                   
		if( Str[i]!=' '&& (Str[j]==' '|| Str[j]=='\0') )
            count++;
	}
return count;
}

////////从多节命令中获得某节命令
char* TakeItemCommand(char *Str,int n)
{
	if(n>CountItem(Str))
		return 0;
	int N=n-1;
	int count = 0;
	char *p;
	p=new char[CountChar(Str)];
	int m=0;
	if(n==1)
	{
		for(int i=0,j=1;Str[i]!='\0';i++,j++)
		{                                   
			if( Str[i]!=' '&& (Str[j]==' '|| Str[j]=='\0') )
				count++;
			if(count==N)
			{
				if(Str[i]==' ')continue;
				p[m]=Str[i];
				m++;
			}
			if(count>N)
			{
				p[m]=Str[i];
				m++;
				p[m]='\0';
				return p;
			}
		}
	}
	else
	{
		for(int i=0,j=1;Str[i]!='\0';i++,j++)
		{                                   
			if( Str[i]!=' '&& (Str[j]==' '|| Str[j]=='\0') )
				count++;
			if(count==N)
			{
				if(Str[j]==' ')continue;
				p[m]=Str[j];
				m++;
			}
			if(count>N)
			{
				p[m]='\0';
				return p;
			}
		}
	}
	return 0;
}

int main()//主函数，进入口
{
	CStructItem StructItem;
	Vector_CStructItem DataBase;
	FILE *pFile=NULL;
	char *DataArray;
	if( fopen_s( &pFile, "DataBase.txt", "r" ) == 0 )//打开数据文件
	{
		fseek(pFile,0,SEEK_END);//定位最后光标
		int iLength=ftell(pFile);
		fseek(pFile,0,SEEK_SET);//设置光标
		DataArray=new char[iLength+1];//动态申请空间
		memset(DataArray,0,iLength);//把DataArray置０
		fread( DataArray,1, iLength, pFile);//把数据读到缓冲区

	

		int count=CountItem(DataArray);//字符命令个数
		for(int i=1;i<=count;i++)
		{
			char *str=TakeItemCommand(DataArray,i);//提取数据
			if(strcmp(str,"TID")==0)
			{
				if(i>1)
				{
					DataBase.push_back(StructItem);
					StructItem.vItem.clear();//清空StructItem
				}
			}
			else
			{
				int num=atoi(str);//把str转为整型数据
				StructItem.vItem.push_back(num);
			}
		}
		DataBase.push_back(StructItem);

		cout<<endl;
		if(DataArray)
			delete [] DataArray;//释放内存

		ShowAndSaveDataBase(DataBase);//显示并保存数据库


		cout<<endl<<"请输入最小支持度的值：";
		cin>>MINSUPPORT;/////////设置最小支持度的值
		cout<<"请输入最小置信度的值：";
		cin>>MINCONFIDENCE;
		cout<<endl;/////////设置最小置信度的值


		Vector_CStructItem L=InitDataBase(DataBase);
		int k=0;
		while(L.size()>=1)
		{
			All_L.push_back(L);
			ShowAndSaveL(L,++k);//显示和保存L集合数据
			L=Apriori_gen(DataBase,L,k);//分析L集合，进入主体算法
		}

		int iSupportl=0;
		int iSupporta=0;
		float conf=0.0;
		////////格式化并赋值
		for(int i=0;i<All_L.size();i++)
		{
			cout<<endl<<endl<<"L"<<i+1<<": ";
			for(int j=0;j<All_L.at(i).size();j++)
			{
				cout<<endl<<"\tl"<<j+1<<": ";
				for(int k=0;k<All_L.at(i).at(j).vItem.size();k++)
					cout<<All_L.at(i).at(j).vItem.at(k)<<'\t';
				cout<<":"<<All_L.at(i).at(j).iSupport;
				for(int k=0;k<All_L.at(i).at(j).vItem.size();k++)
				{
					iSupportl=All_L.at(i).at(j).iSupport;
					iSupporta=CountSupport(DataBase,All_L.at(i).at(j).vItem.at(k));
					////////把结果输出到屏幕
					cout<<endl<<"\t\ta = "<<All_L.at(i).at(j).vItem.at(k)<<'\t';
					cout<<"support(l"<<j+1<<") /support(a) =";
					cout<<iSupportl;
					cout<<" / ";
					cout<<iSupporta;
					conf=float(iSupportl)/float(iSupporta);
					cout<<" = "<<conf;
					if(conf >= MINCONFIDENCE )
						cout<<" 强关联";
				}
			}
		}
		fclose(pFile);//关闭文件
	}
	else
	{
		cout<<"无法找到数据源"<<endl;
		system("pause");
		return -1;
	}
	cout<<endl;
	return 0;//返回，程序结束
}