111.txt

FP算法 由韩家炜教授发明 用于挖掘频繁项集

/****fp增长算法：****************
(1)计算各个项的支持度，按降序排列
(2)把各个事务的项按(1)的顺序排列
(3)改变各个共根项的计数
(4)以各个单项为尾计算各个频繁项集
 **************************************/

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using  namespace  std;

vector<vector<char> > VVCHAR;//存放一个集合的所有子集
vector<int> IS_NOT; //记录各个元素的选与未选
const SUPPORT=3; //支持度
/********返回一个序列中最大元素的索引号******/
int  max_index(const vector<int> & ivec)
{
 int max_num=-100;
 int index;
 for(int i=0;i<ivec.size();++i)
 {
  if(ivec[i]>max_num)
  {
   max_num=ivec[i];
   index=i;
  }
 }
 return  index;
}

//从各个事务的项集中得到数据库的所有单个项并按支持度排成降序
vector<char>  reverse_unique_item(const vector<vector<char> > & vvchar )
{
 vector<char> cvec;
 vector<int> count;
 vector<char> reverse_cvec;
 for(int i=0;i<vvchar.size();++i)
 {
  for(int j=0;j<vvchar[i].size();++j)
  {
   vector<char>::iterator iter;
   //找不到说明前面没有重复的单项
   if((iter=find(cvec.begin(),cvec.end(),vvchar[i][j]))==cvec.end())
   {
    cvec.push_back(vvchar[i][j]);
    count.push_back(1);
   }
   else
   {
    count[iter-cvec.begin()]+=1;//在重复元素对应的计数位置加1
   }    
  }
 }
 /******每次从序列中选出支持度最大的项加入倒序序列(不断删除最大元素)*****/
    while(count.size()>0)
 {
  int index=max_index(count);
  reverse_cvec.push_back(cvec[index]);
  cvec.erase(cvec.begin()+index);
  count.erase(count.begin()+index);
 }
 return  reverse_cvec;
}

/*******排列各个事务中的项集，参见单项的降序序列*****/
void sort_transaction(const vector<char> &reverse_cvec,
       vector<vector<char> > &vvchar)
{
 for(int i=0;i<vvchar.size();++i)
 {
  vector<int> count;
  for(int j=0;j<vvchar[i].size();++j)
  {   
   vector<char>::const_iterator iter;
   iter=find(reverse_cvec.begin(),reverse_cvec.end(),vvchar[i][j]);
   count.push_back(iter-reverse_cvec.begin());//得到该事务各个项在倒序序列的序号
  }
  vector<char> tmp=vvchar[i];//该事务的副本
  vector<char> reverse_tmp;//该事务的倒序序列
  while(count.size()>0)
  {
   int index=max_index(count);
   reverse_tmp.push_back(tmp[index]);
   tmp.erase(tmp.begin()+index);
   count.erase(count.begin()+index);
  }
  reverse(reverse_tmp.begin(),reverse_tmp.end());
  vvchar[i]=reverse_tmp;//得到倒序序列中的顺序
 }
}

/********两个分支进行比较，检查2个分支开头有多少项相同******/
int  root_location(const vector<char> & vchar1, const vector<char> & vchar2)
{
 for(int i=0;i<vchar1.size();++i)
 {
  if(vchar1[i]!=vchar2[i])
  {
   break;
  }
 }
 return i;
}

/*********改变各个共根项的计数，形成逻辑上的fp树********/
void count_root(const vector<vector<char> > & vvchar, 
    vector<vector<int> > & vvint)
{
 //初始化，分支上各个单项的计数都为1
 for(int i=0;i<vvchar.size();++i)
 {
  vector<int> ivec;
  for(int j=0;j<vvchar[i].size();++j)
  {
   ivec.push_back(1);
  }
  vvint.push_back(ivec);
 }
 for(int k=0;k<vvchar.size();++k)
 {
  for(int j=k+1;j<vvchar.size();++j)
  {
   int index=root_location(vvchar[k],vvchar[j]);
   if(index!=0)
   {
    for(int i=0;i<index;++i)
    {
     vvint[k][i]+=1;
     vvint[j][i]+=1;
    }
   }
  }
 }
}

/*******对规回溯产生所有一个集合的所有子集************/
void  backtrack(int m, vector<char> cvec)
{
 //本次深度搜索完毕
 if(m>=cvec.size())
 {
  vector<char> vchar;
  for(int i=0;i<cvec.size();++i)
  {
   if(IS_NOT[i]==1)
   {
    vchar.push_back(cvec[i]);
   }
  }
  if(vchar.size()!=0)
  {
   VVCHAR.push_back(vchar);//保留该子集
  }
  return;
 }
 for(int i=0;i<=1;++i)
 {
  //首先记录本次的选择
  if(IS_NOT.size()<cvec.size())
  {
   IS_NOT.push_back(i);
  }
  else
  {
   IS_NOT[m]=i;
  }
  backtrack(m+1,cvec);//深度递归
 }
}

/********根据逻辑fp树，以各个单项为尾找出频繁项集*********/
vector<vector<char> > frequen_collection(const vector<vector<char> > & vvchar,
                                         const vector<vector<int> > & vvint,
           const vector<char> & item,
           int  support)
{
 vector<vector<char> > collection;  
 for(int i=item.size()-1;i>=0;--i)
 {
  //对每个单项，寻找到以它为尾的所有树枝
  vector<vector<char> > vvchar_tmp;
  for(int j=0;j<vvchar.size();++j)
  {
      if(find(vvchar[j].begin(),vvchar[j].end(),item[i])!=vvchar[j].end())
   {
    vector<char> vchar_tmp;
    for(int k=0;k<find(vvchar[j].begin(),vvchar[j].end(),item[i])-vvchar[j].begin();++k)
    {
     vchar_tmp.push_back(vvchar[j][k]);
    }
    if(vchar_tmp.size()>0)
    {
     vvchar_tmp.push_back(vchar_tmp);
    }
   }
  }
  /********如果该单项前面没有树枝，说明是树顶，单独考虑*****/
  if(vvchar_tmp.size()==0)
  {
   int item_count=0;
   for(int m=0;m<vvchar.size();++m)
   {
    for(int n=0;n<vvchar[m].size();++n)
    {
     if(vvchar[m][n]==item[i])
     {
      item_count=item_count+1;
     }
    }
   }
   if(item_count>=support)
   {
    vector<char> tmp;
    tmp.push_back(item[i]);
    collection.push_back(tmp);
   }
  }
  /**************找出以该单项为尾的频繁项集****************/
  if(vvchar_tmp.size()>=support) //如果以该单项为尾的树枝数大于等于支持度
  {
   /*******计算以该单项为尾的某个树枝中各项的出现次数******/
   vector<char> vchar_tmp2;
   vector<int> count;
   for(int i1=0;i1<vvchar_tmp.size();++i1)
   {
    for(int j=0;j<vvchar_tmp[i1].size();++j)
    {
     vector<char>::iterator iter;
     if((iter=find(vchar_tmp2.begin(),vchar_tmp2.end(),vvchar_tmp[i1][j]))==vchar_tmp2.end())
     {
      vchar_tmp2.push_back(vvchar_tmp[i1][j]);//第1次添加进去
      count.push_back(1);//第1次添加进去，计数初始化为1
     }
     else
     {
      count[iter-vchar_tmp2.begin()]+=1;
     }
    }
   }
   //首先删除单项重复次数小于support的项
   for(int k=0;k<count.size();++k)
   {
    if(count[k]<support)
    {
     count.erase(count.begin()+k);
     vchar_tmp2.erase(vchar_tmp2.begin()+k);
     k--;
    }
   }
   //从剩下的单项重复次数均大于支持度的树枝中生成频繁项集
   //等价于生成集合的子集
   backtrack(0,vchar_tmp2);//递归生成全部子集，保存在VVCHAR
   for(int index=0;index<VVCHAR.size();++index)
   {
    VVCHAR[index].push_back(item[i]);
    collection.push_back(VVCHAR[index]);
   }
      int item_count=0;
   for(int m=0;m<vvchar.size();++m)
   {
    for(int n=0;n<vvchar[m].size();++n)
    {
     if(vvchar[m][n]==item[i])
     {
      item_count=item_count+1;
     }
    }
   }
   if(item_count>=support)
   {
    vector<char> tmp;
    tmp.push_back(item[i]);
    collection.push_back(tmp);
   }
   VVCHAR.erase(VVCHAR.begin(),VVCHAR.end());
   IS_NOT.erase(IS_NOT.begin(),IS_NOT.end());
  }
 }
 return  collection;
}

/**********输出显示*********/
void  print(vector<vector<char> > vvchar)
{
 for(int i=0;i<vvchar.size();++i)
 {
  for(int j=0;j<vvchar[i].size();++j)
  {
   cout<<vvchar[i][j];
  }
  cout<<endl;
 }
}

void main()
{
 //从事务文件中把各个事务写到vvchar中
 ifstream  input=ifstream("transaction.txt");
 vector<vector<char> > transaction;//事务集合
 vector<vector<int> > count;//树枝上各点的计数
 vector<vector<char> > collection;//频繁项集
 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);
   }
  }
 }
    vector<char> reverse_cvec=reverse_unique_item(transaction);//得到按支持度降序的项集合
 sort_transaction(reverse_cvec,transaction);//把各个事务的项按降序项集和重排
 count_root(transaction,count);//改变同根计数，形成逻辑fp树
 collection=frequen_collection(transaction,count,reverse_cvec,SUPPORT);
 //输出频繁项集
 cout<<"经过fp增长算法得到的频繁项集为："<<endl;
 print(collection);
}