注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

长风明志的博客

不要也不能做下一个谁,应该且可以做第一个自己

 
 
 

日志

 
 

C++简单实现关联规则挖掘中的Apriori算法  

2012-10-16 18:51:52|  分类: 数据挖掘 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
使用C++简单实现Apriori算法,程序中应用到了一些常用的C++容器和泛型算法和简单的文件操作。
工具: VC++6.0
输入: 事务数据文件 data.txt
输出:关联规则

The program flow chart of my implementation are as follows:

C++简单实现关联规则挖掘中的Apriori算法 - changfengmingzhi - 长风明志的博客
 

               The program flow chart

Other work that needed to be done:

1.      we should set the minimum confidence and minimum support.

2.      Preprocess the string from the input file,such as trim out the blank space on the left or on the right.

3.      When we generate the next round’s candidate itemset, we should judge whether or not two itemsets can merge into one.

4.      Execute the pruning operation.

5.      Avoiding generate duplicate candidate itemset.

The input data(Refer to figure 10):

C++简单实现关联规则挖掘中的Apriori算法 - changfengmingzhi - 长风明志的博客
 

                           Figure-10

The result of running the program(Refer to figure 11):

C++简单实现关联规则挖掘中的Apriori算法 - changfengmingzhi - 长风明志的博客
 

C++简单实现关联规则挖掘中的Apriori算法 - changfengmingzhi - 长风明志的博客
 

                            Figure-11

From the result,we can see that there are 4 association rules meet the requirement of minimum support and minimum confidence. To some extent, this program can be extended,we can change the input data easily by altering the input file data.txt.While the shortcomings are that I use too many containers and the readability is not quite well,what’s more, I can’t ensure that this program will have good efficiency when inputing large scale data.


C++源代码:
/*
实现Apriori算法 
原始数据(数据以空格为分隔符):
I1 I2 I5
I1 I2
I2 I4
I1 I2 I4
I1 I3
I1 I2 I3 I5
I1 I2 I3
I2 I5
I2 I3 I4
I3 I4
*/
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <bitset>
#include <algorithm>
#include <iomanip>
using namespace std;
//#define minsup 0.2
//#define minconf 0.8
const double minsup=0.2,minconf=0.7;  //设置最小支持度和最小置信度
vector<string> confidencevec;     //用于存放满足最低置信度要求的关联规则
map<string,int> items_count;   //统计各个项集的数目
vector<string> mergeItem(vector<string> vect1,vector<string> vect2,int round);     //合并生成新的候选项集
int isExist(vector<string> item,vector<vector<string> >items);         //判断项集item是否已经存在候选项集集合items中,存在则返回1
void computeConfidence(vector<string> vec,int round);         //计算并输出置信度
int main()
{
  vector<vector<string> > datavec;        //原始数据项集
  vector<vector<string> > candidatevec;   //候选项集
  vector<vector<string> > frequentvec;   //频繁项集
  vector<string> AssociationRulevec;   //关联规则项集
  vector<map<string,int> > bitmap;     //判断某个项目在某一个事务中是否存在,存在则值为1,反之为0
  long trancount=0;   //原始事务总数
  ifstream file("F:\\Software\\source code\\data.txt");   //打开数据文件
  ofstream outfile("F:\\Software\\source code\\output.txt");   //输出规则到该文件
  if(!file)        //检查文件是否打开成功
  {
     cout<<"Fail to open data file!"<<endl;
     return 1;
  }
  else
  {
     string temp;
     vector<string> item;   //项集的临时vector 
     cout<<"The original data:"<<endl;
     int begin,end;
     while(getline(file,temp))     //一行一行读入数据
     {
        trancount++;
        begin=0;
        temp.erase(0,temp.find_first_not_of("\r\t\n "));   //去除字符串首部的空格
        temp.erase(temp.find_last_not_of("\r\t\n")+1);        //去除字符串尾部的空格
        
        while((end=temp.find(' ',begin))!=string::npos)    //每一个事务中的项是以空格为分隔符的
        {
           item.push_back(temp.substr(begin,end-begin));   //将每一个项插入item中
           begin=end+1;
        }
        item.push_back(temp.substr(begin));     //一个事务中的最后一项
        datavec.push_back(item);       //将一个事务中的所有项当成一个整体插入另一个大的vector中
        item.clear();   //清空item
        cout<<temp<<endl;
     }
     cout<<"Press Enter to continue the processing";  //pause
     getchar();
     map<string,int> item_map; 
     for(vector<vector<string> >::size_type ix=0;ix!=datavec.size();++ix)
     {
        for(vector<string>::size_type iy=0;iy!=datavec[ix].size();++iy)
        {
         items_count[datavec[ix].at(iy)]++;    //该项集的计数加1
         item_map[datavec[ix].at(iy)]=1;       //表示该项目在该事务中存在,值为1,否则默认为0
        }
        bitmap.push_back(item_map);
        item_map.clear();      //这里一定要清空一下
     }
     map<string,int>::const_iterator map_it=items_count.begin();
     cout<<"候选1项集:"<<endl;
     while(map_it!=items_count.end())      //输出候选1项集
     {
        cout<<"{"<<map_it->first<<"}"<<endl;
        map_it++;
     }
     cout<<"Press Enter to continue the processing";  //pause
     getchar();
     map_it=items_count.begin();
     cout<<"频繁1项集(minsup=0.2,minconf=0.8):"<<endl;
     while(map_it!=items_count.end())          //频繁1项集
     {
        if(((float)map_it->second/(float)trancount)>minsup||fabs(((float)map_it->second/(float)trancount)-minsup)<1.0e-7)    //支持度大于0.2
        {
            cout.setf(ios::fixed);
            cout<<"{"<<map_it->first<<"}"<<" 支持度:"<<setprecision(6)<<(float)map_it->second/(float)trancount<<endl;
            item.push_back(map_it->first);
            frequentvec.push_back(item);   //插入候选1项集的vector中
            item.clear();    
        }
        map_it++;
     }
     if(!frequentvec.empty())   //判断频繁1项集是否为空,为空则退出
     {
         cout<<"Press Enter to continue the processing";  //pause
         getchar();
         int round=1;     //生成候选项集轮次
         int found;    //是否包含有非频繁的子集,为1表示含有,有的话进行剪枝,如假设I1I4为非频繁项集,则I1I2I4要剪枝掉
         string tempstr;
         vector<string> tempvec;
         do
         {
            //生成下一轮的候选项集
            vector<vector<string> >::size_type st=frequentvec.size();
            candidatevec.clear();         //清除上一轮的候选项集
            for(vector<vector<string> >::size_type st1=0;st1<st;st1++)
            {
                for(vector<vector<string> >::size_type st2=st1+1;st2<st;st2++)
                {
                    found=0;
                    item=mergeItem(frequentvec[st1],frequentvec[st2],round);    //调用函数合并生成下一轮的候选项集
                    if(!item.empty()&&!isExist(item,candidatevec))   //若经过判断处理后返回的vector不为空且还不存在该项集,则作为候选项集加入候选vector中
                    {
                        ////////实现剪枝//////////////////////////
                        string teststr;
                        int testint;
                        tempvec=item;
                        sort(tempvec.begin(),tempvec.end());
                        while(next_permutation(tempvec.begin(),tempvec.end()))   //遍历所有的组合I1I2I4,要变成I1I4I2或其他如I2I1I4才能判断它包含I1I4这个非频繁项集
                        {
                           for(vector<string>::size_type tempst=0;tempst!=tempvec.size();tempst++) //拼接出该字符串组合
                           {
                                tempstr+=tempvec[tempst];                                
                           }
                           for(map<string,int>::const_iterator tempit=items_count.begin();tempit!=items_count.end();tempit++)
                           {
                                if(((float)(tempit->second)/(float)trancount)<minsup)  //非频繁项集
                                {
                                    if(tempstr.find(tempit->first)!=string::npos)   //表示包含有非频繁子项集
                                   {
                                       found=1;
                                       teststr=tempit->first;
                                       testint=tempit->second;
                                       break;
                                   }
                                }
                           }
                           tempstr.erase();
                           if(found)   //包含非频繁子项集
                           {
                              break;
                           }
                           
                        }
                        if(!found)     //只有不包含有非频繁子项集才加入候选项集中,否则剪枝掉
                           candidatevec.push_back(item);
                        else
                        {
                           cout<<"剪去项集:";
                           for(vector<string>::size_type st2=0;st2!=item.size();st2++)
                               cout<<item[st2];
                           cout<<" 含有非频繁子项集:"<<teststr<<" "<<testint<<"/"<<trancount<<"="<<((float)(testint)/(float)trancount);
                           cout<<endl;
                        }
                        found=0;   //重置
                    }
                    
                }
            }
            frequentvec.clear();         //清除上一轮的频繁项集
            round++;
            cout<<"候选"<<round<<"项集:"<<endl;
            for(vector<vector<string> >::size_type ix=0;ix!=candidatevec.size();++ix)      //输出候选项集
            {
               cout<<"{";
               for(vector<string>::size_type iy=0;iy!=candidatevec[ix].size();++iy)
               {
                cout<<candidatevec[ix].at(iy);
               }
               cout<<"}"<<endl;
            }
            if(candidatevec.empty())  //候选项集为空
            {
               cout<<"候选"<<round<<"项集为空!"<<endl;
            }
            int flag;    //标记某个项集在某条事务中是否出现,出现为1,不出现为0,如:{I1I2}
            int count;   //统计某个想集在整个交易的事务集中出现的次数
            string tempstr;   //临时string,用于串接各个项成一个字符串: 如: I1 I2  I3  串接为"I1I2I3"
            int mark;    //为避免执行多余的字符串串接工作
            for(vector<vector<string> >::size_type sx=0;sx!=candidatevec.size();++sx)      //构造下一轮的频繁项集
            {
                mark=1;
                count=0;
                for(vector<map<string,int> >::size_type sy=0;sy!=bitmap.size();++sy)
                {
                    flag=1;       //初始化为1,表出现
                    for(vector<string>::size_type sz=0;sz!=candidatevec[sx].size();++sz)
                    {
                       if(bitmap[sy][candidatevec[sx].at(sz)]==0)   //存在某一个子项不存在,则没出现项集
                       {
                           flag=0;
                       }
                       if(mark==1)   //只串接一次,如I1I2    否则为10个I1I2的串接
                       {
                           tempstr+=candidatevec[sx].at(sz);  //串接字符串
                       }
                    }
                    
                    if(flag)  //flag仍然为1,表示该项集在该条事务中出现了,计数加1
                    {
                       count++;
                    }
                    mark++;
                }
                
                if(((float)count/(float)trancount)>minsup||fabs(((float)count/(float)trancount)-minsup)<1.0e-7)   //支持度大于0.2
                {
                    frequentvec.push_back(candidatevec[sx]);        //插入频繁项集
                }
                items_count[tempstr]=count;       //对应该项集的计数值
                /////////假设此时生成的tempstr为I1I2I3,为便于后面的求置信度的计算,这里需要产生I2I1I3,I1I3I2等组合,并
                //在items_count中给它们赋予和I1I2I3相同的值
                sort(candidatevec[sx].begin(),candidatevec[sx].end());    //排序
                string tempstr2;
                while(next_permutation(candidatevec[sx].begin(),candidatevec[sx].end()))  //取下一排列组合
                {
                     for(vector<string>::size_type tempst=0;tempst!=candidatevec[sx].size();tempst++) //拼接出该字符串组合
                     {
                         tempstr2+=candidatevec[sx][tempst];
                     }
                     items_count[tempstr2]=count;  //对应该项集的计数值
                     tempstr2.erase();
                }               
                tempstr.erase();
            }
            cout<<"Press Enter to continue the processing";  //pause
            getchar();
            if(!frequentvec.empty())     //频繁项集不为空
            {
                 
                 cout<<"频繁"<<round<<"项集(minsup=0.2,minconf=0.8):"<<endl;
                 for(sx=0;sx!=frequentvec.size();++sx)      //输出频繁项集
                 {
                     cout.setf(ios::fixed);
                     cout<<"{"; 
                     for(vector<string>::size_type sz=0;sz!=frequentvec[sx].size();++sz)
                     {
                        cout<<frequentvec[sx].at(sz);
                        tempstr+=frequentvec[sx].at(sz);  //串接字符串
                     }
                     cout<<"}";
                     cout<<" 支持度:"<<setprecision(6)<<(float)items_count[tempstr]/(float)trancount<<" 置信度:";
                     //////////计算并输出置信度/////////
                     computeConfidence(frequentvec[sx],round);
                     cout<<endl;
                     tempstr.erase();
                 }
                 cout<<"Press Enter to continue the processing";  //pause
                 getchar();
             }
             else
             {
                 cout<<"没有"<<round<<"-频繁项集,Apriori算法结束!"<<endl;
             }
         }while(!frequentvec.empty());   //频繁项集不为空,则循环继续
         
         cout<<"得出的关联规则如下:"<<endl;
         for(vector<string>::size_type st=0;st!=confidencevec.size();st++)
         {
             cout<<confidencevec[st]<<endl;
         }
         outfile<<"输出的关联规则如下:"<<endl;
         for(vector<string>::iterator tempit=confidencevec.begin();tempit!=confidencevec.end();tempit++)
         {
            outfile<<*tempit<<endl;
         }
         file.close();
         outfile.close();
         return 0;
     }
     else
     {         
         return 0;
     }    //end of if(!frequentvec.empty())
     
  }//end of if(!file)
}
vector<string> mergeItem(vector<string> vect1,vector<string> vect2,int round)            //判断两个项集是否可以合并(要求只有一项不同)成一个新的项集(做为候选集)
{

   ////////////////////////////////////////////剪枝工作////
   int count=0;     //统计两个vector中相同的项的数目
   vector<string> vect;
   map<string,int> tempMap;   //辅助判断两个vector中重复的项
   for(vector<string>::size_type st=0;st<vect1.size();st++)
   {
      tempMap[vect1[st]]++;
      vect.push_back(vect1[st]);
   }
   for(st=0;st<vect2.size();st++)
   {
      tempMap[vect2[st]]++;
      if(tempMap[vect2[st]]==2)  //表示这两项相同
      {
         count++;
      }
      else
      {
         vect.push_back(vect2[st]);
      }
   }
   if((count+1)!=round)       //要求两个项目集只有一个项目不相同,其他都相同,如:I1 I2 I4 和I1 I2 I3
   {
      vect.clear();
   }
   return vect;
}


int isExist(vector<string> item,vector<vector<string> >items)  //判断项集item是否已经存在候选项集集合items中,存在则返回1
{
   ////////////////重复的比如:I1I2I3和I2I3I1
    int count;   //统计相同的项的数目
    if(!items.empty())
    {
       for(vector<vector<string> >::size_type ix=0;ix!=items.size();ix++)
       {
           count=0;
           for(vector<string>::size_type iy=0;iy!=items[ix].size();iy++)
           {
               for(vector<string>::size_type iz=0;iz!=item.size();iz++)
               {
                   if(item[iz]==items[ix].at(iy))
                   {
                      count++;
                   }
               }
           }
           if(count==item.size())     //表示存在
           {
              return 1;
           }
       }
     }
    return 0;
}
void computeConfidence(vector<string> vec,int round)            //计算并输出置信度
{
    int i=1;
    unsigned long u=1;
    int j;
    string tempstr;
    vector<string> realsubset;   //存放vec的非空真子集  
    int upper=(int)pow(2,round)-1;   //循环的上限
    char str[100];
    vector<string>::size_type st;
    while(i<upper)
    {
        bitset<10> bitvec(u);         //bitset容器,用于辅助求关联规则模式置信度时的项集真子集
        for(j=0;j<round;j++)
        {
            if(bitvec[j])    //该位为1
            {
               tempstr+=vec[j];   //串接字符串形成一个子集
            }
        }
        //cout<<"  "<<tempstr<<" round="<<round;
        realsubset.push_back(tempstr);   //插入非空真子集集合中
        tempstr.erase();
        u++;
        i++;
    }
    //////计算非空真子集中各个子集直接关联规则的置信度,如I1=>I2I3
    
    for(i=0;i<realsubset.size();i++)
    {
       for(j=0;j<realsubset.size();j++)
       {
          if(i!=j&&realsubset[i].find(realsubset[j])==string::npos&&realsubset[j].find(realsubset[i])==string::npos)
          ///不能计算自己跟自己的,如I1与I1, 也不能计算包含自己的情况,如: I1=>I1I3或I1I3=>I1
          ////!!!!!!I1I3=>I2I3如何排除????
          {
             if((float)(items_count[realsubset[i]+realsubset[j]])/(float)(items_count[realsubset[i]])>minconf||fabs((float)(items_count[realsubset[i]+realsubset[j]])/(float)(items_count[realsubset[i]])-minconf)<1.0e-7)   //A=>B 置信度大于0.8
             {
                 cout.setf(ios::fixed);
                 cout<<realsubset[i]<<"=>"<<realsubset[j]<<"<"<<setprecision(6)<<(float)(items_count[realsubset[i]+realsubset[j]])/(float)(items_count[realsubset[i]])<<"> ";
                 tempstr="{"+realsubset[i]+"}=>{"+realsubset[j]+"} 置信度:";
                 sprintf(str,"%f",(float)(items_count[realsubset[i]+realsubset[j]])/(float)(items_count[realsubset[i]]));
                 string tempstr2(str);
                 tempstr+=tempstr2;
                 for(st=0;st<confidencevec.size();st++)      //检查是否已经有该关联规则存进去了,以防止重复
                 {
                     if(confidencevec[st]==tempstr)
                        break;
                 }
                 if(st==confidencevec.size())     //没有发生重复,则加入关联规则集合
                 {
                    confidencevec.push_back(tempstr);      
                 }
                 tempstr.erase();            
             }

          }
       }
    }
    cout<<endl;
}
  评论这张
 
阅读(3298)| 评论(9)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017