fp增长算法.txt

关于FP增长树的算法

FP增长树2007-07-12 19:41/********fp增长算法求出频繁项集*******/
/********作者：xiaocui************/
/********时间：2006.10.12*********/
/********版本：v1.0**********/

/****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);
}