Apriori算法的C++实现-白红宇

Apriori算法的C++实现

阅读量：4969 次

发布时间：2019-06-12

本文共 3763 字，大约阅读时间需要 12 分钟。

Apriori是经典的购物篮分析算法。该算法用SQL实现难度较大，所以考虑用C++实现。

花了两天，代码例如以下。原创转载请注明出处

//Apriori.c #include
     
      #include
      
       #include
       #include
        
         #include
         
          using namespace std;typedef map
          
           
            ,int> map_s;map_s Ck ;//候选集Ckmap_s Lk ; //频繁项集Lkvector
            
             
               > data; //原始数据vector
              
               
                 > L; //频繁项集合vector
                
                  data2; //切割后的原始数据int n,m;int minSup = 2;int minConf = 0.2;set
                 
                   s;string in;void Delete(map_s &Ck){ for( map_s::iterator l_it=Ck.begin();l_it!=Ck.end();l_it++ ) { if( l_it->second< minSup) { Ck.erase(l_it); } }}int compset(set
                  
                    s1,set
                   
                     s2){ int flag=0; //推断集合s1是不是s2的子集 for( set
                    
                     ::iterator it=s1.begin(); it!=s1.end();it++ ) { //s1有元素不在s2中 if( s2.find(*it)==s2.end() ) { flag=10; break; } } for( set
                     
                      ::iterator it=s2.begin(); it!=s2.end();it++ ) { //s2有元素不在s1中 if( s1.find(*it)==s1.end() ) { flag+=1; break; } } /*当flag==0,s1元素所有在s2中，s2元素也所有在s1中，s1==s2 当flag==10,s1有元素不在s2中，s2所有元素都在s1中。s1包括了s2 当flag==1,s1所有元素在s2中，s2有元素不在s1中。s2包括了s1 当flag==11,s1 s2集合互不包括 */ return flag;}map_s apriori_gen(map_s &Ck,int k){ //生成子集 map_s Ck_temp; set
                      
                        s_temp; for( map_s::iterator l_it1=Ck.begin();l_it1!=Ck.end();l_it1++ ) { for( map_s::iterator l_it2=Ck.begin();l_it2!=Ck.end();l_it2++ ) { //假设两个set一样，则说明是同一个KEY。跳过 if(!((l_it1->first > l_it2->first)||(l_it1->first < l_it2->first))) continue; //否则開始组装,遍历整个Ck for( set
                       
                        ::iterator s_it=l_it2->first.begin();s_it!=l_it2->first.end();s_it++ ) { //假设该值在l_it1 set里面能够找到，不能组装 if( l_it1->first.find(*s_it)!=l_it1->first.end()) continue; //否则进行组装,先把l_it1的set复制进去 s_temp = l_it1->first; //再把l_it2的值放进去 s_temp.insert(*s_it); //推断该组装的set是否已在生成集合中。假设之前已生成。则不须要往下运算 if(Ck_temp.find(s_temp)!=Ck_temp.end()) continue; else //否则放到生成的子集中 { Ck_temp.insert(pair
                        
                         
                          ,int >(s_temp,0)); } } } } //对于k=2的情况。须要扫描原始数据得出计数值 if( 2 == k ) { for( map_s::iterator l_it=Ck_temp.begin();l_it!=Ck_temp.end();l_it++ ) for(int i=0;i
                          
                           first)) || (0 == compset(data[i],l_it->first)) ) Ck_temp[l_it->first]++; //扫描完之后排除 非频繁项 for( map_s::iterator l_it=Ck_temp.begin();l_it!=Ck_temp.end();l_it++ ) if( Ck_temp[l_it->first] < minSup ) Ck_temp.erase(l_it); } //假设是大于2的情况，扫描k-1的频繁项子集 if( 2 < k ) { //每次都循环获取每一个Ck的k-1子集元素 //如{I1,I2,I3}C3的子集是{I1,I2} {I2,I3} {I3,I4} //假设Ck的子集不在k-1的频繁项子集中，则去掉该Ck项 for( map_s::iterator l_it=Ck_temp.begin();l_it!=Ck_temp.end();l_it++ ) { int flag; for( set
                           
                            ::iterator s_it=l_it->first.begin();s_it!=l_it->first.end();s_it++ ) { //開始求子集 //首先把当前Ck项的集合保存 s_temp=l_it->first; //去掉一个元素。即是它的k-1子集 s_temp.erase(*s_it); //遍历频繁项集合L。看看是不是在频繁集中 flag=1; for( int i=0;i
                            
                             ::iterator s_it=l_it->first.begin();s_it!=l_it->first.end();s_it++ ) cout<<*s_it<<" "; cout<
                             
                              second<
                              
                               >n; for(int i=0;i
                               
                                >m; for(int j=0;j
                                
                                 >in; s.insert(in); data2.push_back(in); } data.push_back(s); } //扫描数据集D。生成C1 //对于每一个候选集里面的元素 for( int j=0; j
                                 
                                  first).find(data2[j]) != (l_it->first).end() ) { Ck[l_it->first]++; flag=0; break; } } //不存在，插入到C1集合中 if(flag) { s.clear(); s.insert(data2[j]); Ck.insert(pair
                                  
                                   
                                    ,int>(s,1)); } } //去掉支持度不足的 for( map_s::iterator l_it=Ck.begin();l_it!=Ck.end();l_it++ ) { if( l_it->second< minSup) Ck.erase(l_it); } cout<<"C1候选集:"<
                                    
                                     ::iterator s_it=(l_it->first).begin(); s_it!=(l_it->first).end(); s_it++) cout<<*s_it<<" "<
                                     
                                      second<
                                      
                                       first); //获取Ck集，已清除掉小于支持度的候选集 Ck=apriori_gen(Ck,f_count); if( Ck.empty() ) { break; }else{ f_count++; } } cout<<"终于的频繁集集合"<
                                       
                                        ::iterator s_it=L[i].begin(); s_it!=L[i].end(); s_it++) cout<<*s_it<<" "; cout<

眼下仅仅实现到产生频繁集合，支持度默认计数2。在g++环境下编译 g++ -g Apriori.c -o apr

測试数据例如以下：

3 I1 I2 I6

4 I1 I2 I3 I5

3 I2 I3 I7

5 I1 I3 I5 I6 I2

输出例如以下：

用ORACLE格式化数据导出成文件，C++处理后返回文件给ORACLE，传到推荐数据库中就可以完毕这个算法的全流程。

当然眼下还仅仅是儿童玩具，由于全部的数据都是放在内存里的，数据量一大这个代码就不有用了。

C++牛逼的地方在于能够直接调用linux底层的接口处理这一类问题。比方当内存不足时数据存到磁盘。我们这边内存有几十G。订单总量不超过1G。所以这个代码应该够用了，不够用时能够再扩展

转载于:https://www.cnblogs.com/zsychanpin/p/7079379.html

你可能感兴趣的文章