FP-TREE算法 C++实现

//FP增长树2007-07-12 19:41/******fp增长算法求出频繁项集

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

#include 
#include 
#include 
#include 
#include 
using   namespace   std;

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

//从各个事务的项集中得到数据库的所有单个项并按支持度排成降序
vector   reverse_unique_item（const vector > & vvchar ）
{
vector cvec;
vector count;
vector reverse_cvec;
for（int i=0;i{
   for（int j=0;j   {
    vector::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 &reverse_cvec
        vector > &vvchar）
{
for（int i=0;i{
   vector count;
   for（int j=0;j   {
    vector::const_iterator iter;
    iter=find（reverse_cvec.begin（）reverse_cvec.end（）vvchar[i][j]）;
    count.push_back（iter-reverse_cvec.begin（））;//得到该事务各个项在倒序序列的序号
   }
   vector tmp=vvchar[i];//该事务的副本
   vector 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 & vchar1 const vector & vchar2）
{
int i;
for（i=0;i{
//	cout<<“++++++++++++++++++++“;
//	cout<//	cout<   if（vchar1[i]!=vchar2[i]）
   {
    break;
   }
}
return i;
}

/*********改变各个共根项的计数，形成逻辑上的fp树********/
void count_root（const vector > & vvchar
     vector > & vvint）
{
//初始化，分支上各个单项的计数都为1
for（int i=0;i{
   vector ivec;
   for（int j=0;j   {
	   //cout<    ivec.push_back（1）;
   }
   vvint.push_back（ivec）;
}

for（int k=0;k{
   for（int j=k+1;j   {

    int index=root_location（vvchar[k]vvchar[j]）;
    if（index!=0）
    {
     for（