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

/********数据挖掘中关联规则求法的第一步：**/
/********求频繁项集的aprior算法******/
/********作者：xiaocui******/
/********时间：2006年9月15日***/
/********版本：v1.0*******/
#include
#include
#include
#include
#include
using  namespace  std;
const  int  SUPPORT=2;//最小支持度

//从各个事务的项集中得到数据库的所有单个项并对单项排序
vector  unique_item(const vector > & vvchar )
{
 vector cvec;
 for(int i=0;i {
  for(int j=0;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 count_itemcollection(const vector > & vvchar,
         const vector > & transction)
{
 vector ivec;
 int count=0;
 for(int i=0;i {
  for(int j=0;j  {
   for(int k=0;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 >  choose_freq(vector > & candidate_cut,
                       const vector > & transaction)
{
 vector > freq;
 vector count=count_itemcollection(candidate_cut,transaction);
 for(int i=0;i {
  if(count[i]>=SUPPORT)
  {
   freq.push_back(candidate_cut[i]);   
  }
 }
 return  freq;
}

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