数据挖掘中关联规则中求频繁项集的aprior算法[cser]

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int SUPPORT=2;//最小支持度

//从各个事务的项集中得到数据库的所有单个项并对单项排序
vector<char> unique_item(const vector<vector<char> > & vvchar )
{
vector<char> cvec;
for(int i=0;i<vvchar.size();++i)
{
for(int j=0;j<vvchar[i].size();++j)
{
//找不到说明前面没有重复的单项
if(find(cvec.begin(),cvec.end(),vvchar[i][j])==cvec.end())
{
cvec.push_back(vvchar[i][j]);
}
}
}
sort(cvec.begin(),cvec.end());
return cvec;
}

//算出项集中每个项(包括单项)在总的事务集合中出现的次数(支持度)
vector<int> count_itemcollection(const vector<vector<char> > & vvchar,
const vector<vector<char> > & transction)
{
vector<int> ivec;
int count=0;
for(int i=0;i<vvchar.size();++i)//对每一个项集
{
for(int j=0;j<transction.size();++j)
{
for(int k=0;k<vvchar[i].size();++k)
{
//如果一个项在当前事务中找不到，其它的项也就不用再在当前事务中找
//直接在下一个事务中找
if(find(transction[j].begin(),transction[j].end(),vvchar[i][k])==transction[j].end())
{
break;
}
}

//当前项集的所有项都在当前事务中出现，计数加1
if(k==vvchar[i].size())
{
count++;
}
}
ivec.push_back(count);
count=0;
}
return ivec;
}

//从剪枝后的候选项选出频繁项集
vector<vector<char> > choose_freq(vector<vector<char> > & candidate_cut,
const vector<vector<char> > & transaction)
{
vector<vector<char> > freq;
vector<int> count=count_itemcollection(candidate_cut,transaction);
for(int i=0;i<count.size();++i)
{
if(count[i]>=SUPPORT)
{
freq.push_back(candidate_cut[i]);
}
}
return freq;
}

//把前一代的频繁项集连接生成下一代的候选项集
vector<vector<char> > connect_freq(const vector<vector<char> > & freq1,
const vector<vector<char> > & freq2)
{
vector<vector<char> > candidate;
for(int i=0;i<freq1.size();++i)
{
for(int j=0;j<freq2.size();++j)
{
for(int k=0;k<freq1[i].size()-1;++k)
{
if(freq1[i][k]!=freq2[j][k])
{
break;
}
}
//第一个项集的前n－1位都等于第二个项集的前n－1位
if (k==freq1[i].size()-1)
{
//同时，第一个项集的最后一项小于第二个项集的最后一项
if(freq1[i][k]<freq2[j][k])
{
vector<char> cvec;
//把第一个项集的全部项移入候选项
for(int m=0;m<freq1[i].size();++m)
{
cvec.push_back(freq1[i][m]);
}
//把第二个项集的最后一个项移入候选项
cvec.push_back(freq2[j][freq2[j].size()-1]);
//把候选项加入候选项集中
candidate.push_back(cvec);
}
}
}
}
return candidate;
}
void main()
{
//从事务文件中把各个事务写到vvchar中
ifstream input=ifstream("transction.txt");
vector< vector<char> > transaction;
if (input==0) //文件打开失败
{
cout<<"存放事务的文件transction不存在，请先手工建立"<<endl;
}
else
{
while(input)
{
string str;
getline(input,str,'\n'); //得到一行事务项集
if(str!="")//最后有一空行，所以在此用if消除
{
vector<char> cvec;
for(int i=0;i<str.size();++i)
{
cvec.push_back(str[i]);
}
transaction.push_back(cvec);
}
}
}
//对各个事务项集进行排序
for(int i=0;i<transaction.size();++i)
{
sort(transaction[i].begin(),transaction[i].end());
}
//取得各个单项并对单项排序
vector<char> cvec =unique_item(transaction);
vector<vector< vector<char> > >freq_results;//保存最后的频繁项集结果
vector< vector<char> > candidate;//各个代的候选项集
//候选项集开始初始化为单项集合
for(int j=0;j<cvec.size();++j)
{
vector<char> cvec_tmp;
cvec_tmp.push_back(cvec[j]);
candidate.push_back(cvec_tmp);
}
//开始迭代求频繁项集，直到候选项集为空为止
while(candidate.size()>0)
{
vector<vector<char> > freq_tmp=choose_freq(candidate,transaction);
freq_results.push_back(freq_tmp);//这一代的频繁项集加入结果集合中
candidate=connect_freq(freq_tmp,freq_tmp);
}
//输出所有的频繁项集
for(int l=0;l<freq_results.size();++l)
{
cout<<"含"<<l+1<<"个元素的频繁项集为:"<<endl;
for(int m=0;m<freq_results[l].size();++m)
{
for(int n=0;n<freq_results[l][m].size();++n)
{
cout<<freq_results[l][m][n]<<" ";
}
cout<<endl;
}
}
}