nextendf5.c

关联规则中的频繁项集生成算法genmax

 	 }
         //seconds(t8);
         //tid_difference_time += t8 - t7;

         if (Xtem ->size()< 2){ 
                   if (Xtem ->size()== 1)  tail_list ->addatfront(Xtem ->head()->getdata()->itemset()->head()->getdata()); 
                  cptr = I -> itemset() ->head();
                  for (; cptr; cptr = cptr ->getnext()){
                          tail_list -> addatfront(cptr -> getdata());
                  }
                  if (has_sup(tail_list, Y))  delete tail_list;
                  else {
                       Y -> addatback(tail_list); 
		  }
         }
         else {
           temptr = Xtem ->head();
           for (; temptr; temptr = temptr->getnext()){
               if (Y -> size() > 0 ){
                  //seconds(t40);
                            G = new List<int>; 
                            ptr = temptr;
                            while (ptr){
                                 G ->addatback(ptr -> getdata() -> itemset()->head()->getdata());
                                 ptr = ptr ->getnext();
	                    }
                            cptr = tail_list ->head();
                            while (cptr){
                                     G -> addatback(cptr->getdata());
                                     cptr = cptr -> getnext();
	                    }
                            if (has_sup(G, Y)){
                                          delete G;        
                                          break;
	                    }
                            delete G;  
                            //seconds(t50);
                            //super_set_time += t50 - t40;
               }
               j = temptr -> getdata()->itemset()-> head() -> getdata();
               NewI = new Itemset(temptr -> getdata()->tidtotsize());
               for(int h=0; h < temptr->getdata()->tidsize(); h++){
                              NewI->add_tid(temptr ->getdata()->tid(h));
               }
               NewI->set_support(temptr -> getdata()->support());
               cptr = I -> itemset() ->head();
               for (; cptr; cptr = cptr ->getnext()){
                          NewI -> add_item(cptr -> getdata());
               }
               NewI ->add_item(j);
               NewY = new List<List<int> *>;
               //seconds(t40); 
               find_sets(NewY, Y, j);
               //seconds(t50);
               //find_time += (t50-t40);
               size_old = NewY->size();
               NewX = new List<Itemset *>; 
               xxptr = temptr -> getnext();
               while(xxptr){
                      NewX -> addatback(xxptr  -> getdata());
                      xxptr = xxptr -> getnext(); 
               }

               Extend (NewI, NewX, NewY, tail_list);

               ttptr = NewY->head();
               f = 1;
               while (ttptr){
                    if (f > size_old){
                                 Y -> addatback(ttptr -> getdata());
	            }
                    f +=1;
                    ttptr = ttptr -> getnext();
               }
               delete NewY; 
               delete NewX;
               delete NewI; 
           }
           delete tail_list;
         }
         if (Xtem->size() == 0) delete Xtem; 
         else clear_list_itemset(Xtem);
    
}



void read_files(List<int> *F1)
{

   int i,j,a,b;
   double te,ts;
   seconds(ts);
   
   maxitemsup = make_l1_pass(F1);
   
   seconds(te);
   
   iterstat *is = new iterstat(DBASE_MAXITEM, 0, te-ts);
   stats.add(is);
   
   ts = te;
   
   cout << "maxitemsup: " << maxitemsup <<endl;
   item1 = new Itemset(maxitemsup);
   item2 = new Itemset(maxitemsup);
 
   int l2cnt = make_l2_pass(ext_l2_pass, it2f);
   seconds(te);
   L2TIME = te-ts;
   cout << "\nL2TIME = " << te-ts << endl;
   
   is = new iterstat(DBASE_MAXITEM*(DBASE_MAXITEM-1)/2,0,te-ts);
   stats.add(is);
   
   ts = te;
 
   eqgraph2 = new List<int> *[DBASE_MAXITEM];
   bzero((char *)eqgraph2, DBASE_MAXITEM*sizeof(List<int> *));  

   for (i=0; i < DBASE_MAXITEM; i++){
      eqgraph2[i]= new List<int>;
   }

   cout << " MINSUPPORT is : " <<  MINSUPPORT;

   int idx;   
   int it1, it2;   
   int lcnt;   
   GrNode *grn;   
   for (i=0; i < Graph::numF1; i++){
      //cout << "\nITEM " << i;
      grn = (*F2Graph)[i];      
      it1 = grn->item();
      lcnt = grn->size();       
      if (lcnt > 0){
         for (j=0; j < grn->size(); j++){
            it2 = (*F2Graph)[(*grn)[j]->adj()]->item();            
            eqgraph2[it1]->addatback(it2);
            eqgraph2[it2]->addatback(it1);
         }
      }
   }
   //delete offsets;

   // To fill in the list F1 by comblnth(i) values and delete items with 
   // comblist values equal to 0, these items are maximal itemsets. 
   // Also compute the maximum and minimum levels.

   Listnode<int> *ptr = F1 ->head();
   Listnode<int> *temptr = NULL;
   min1 = F1 ->size();
   max1 = 0;
   while (ptr){
       a = ptr -> getdata();
       b = eqgraph2[a]->size();
       if (b > 0){
                  ptr -> set_comblnth(b);
                  if (b < min1)   min1 = b;
                  if (b > max1)   max1 = b;
                  temptr = ptr;
       }
       else {
             if (!temptr)  F1 -> set_head(ptr->getnext());
             else  temptr ->set_next(ptr -> getnext());
       }
       ptr = ptr ->getnext();
   }
   seconds(te);

   cout << "\nConstruction time for the combine lists = " << te-ts << endl;

    //cout << "The combine Lists before sorting are: " << endl;
   //for (i=0; i < DBASE_MAXITEM; i++){   
     //  if (eqgraph2[i]->size()>0) cout <<"Combine list of item ("<<i<<") is "
       //                     <<*eqgraph2[i]<< endl;
   //} 
}

void Max_itset_algo()
{
double t1,t2;
int i, j, f, m, zsize_old, ysize_old;
Listnode <List<int> *> *ttptr;
    List<int> *H, *tail_list;
    Listnode<int> *temptr, *temptr1;
    Itemset *I, *it1;
    List<Itemset *> *X1, *X2;
    Listnode <Itemset *> *xptr, *ptr1, *xxptr;
    List <List<int> *> *M, *Z, *Y;

    M = new List<List<int> *>;
    temptr = F1 -> head();
    for (; temptr; temptr = temptr -> getnext()){
             i = temptr -> getdata();
             Memman::read_from_disk(item1,i); 
             X1 = new List<Itemset *>; 
             //seconds(t5);
             temptr1 = eqgraph2[i] -> head();
             for (; temptr1; temptr1 = temptr1 -> getnext()){
                     m = temptr1 -> getdata();
                     Memman::read_from_disk(item2, m);
                     it1 = new Itemset(DBASE_NUM_TRANS - item2 -> support());
                     Diff1(it1, item1, item2);
                     //stats.incrcand(item1->itemsetsize());
                     it1 -> add_item(m);
                     X1-> sorted_descend(it1, it1->tidsize());
             }
             //seconds(t6);
             //read_dbase_time += t6 - t5;
             Z= new List<List<int> *>;
             //seconds(t40);
             find_sets(Z, M, i);
             //seconds(t50);
             //find_time += (t50-t40);
             zsize_old = Z->size();
             xptr = X1 -> head();
             for (; xptr; xptr = xptr -> getnext()){
                 if ( Z -> size() > 0){   
                       H = new List<int>; 
                       ptr1 = xptr;
                       while (ptr1){
                            H ->addatback(ptr1 ->getdata()->itemset()->head()->getdata());
                            ptr1 = ptr1 ->getnext();
	               }
                       if (has_sup(H, Z)){ 
                              delete H;        
                              break;               
	               }
                       delete H; 
	         }
                 j = xptr -> getdata()->itemset()->head()->getdata();
                 //cout << "j is " << j<<endl;
                 I = new Itemset(xptr -> getdata()->tidtotsize());
                 for(int h=0; h < xptr->getdata()->tidsize();h++){
                         I -> add_tid(xptr->getdata()->tid(h));
		  }
                  I->set_support(xptr -> getdata()->support());
                  I ->add_item(i);
                  I ->add_item(j);
                  Y = new List<List<int> *>;
                  //seconds(t40); 
                  find_sets(Y, Z, j);
                  //seconds(t50);
                  //find_time += (t50-t40);
                  ysize_old = Y->size();
                  tail_list = new List<int>;
                  X2 = new List<Itemset *>; 
                  xxptr = xptr -> getnext();
                  while(xxptr){
                      X2 -> addatback(xxptr  -> getdata());
                      xxptr = xxptr -> getnext();
	          }
                  //seconds(t1); 
                  Extend (I, X2, Y, tail_list);
                  //seconds(t2); 
                  //extend_time += (t2-t1);
                  //cout << "\nY after extend contains:" << endl;
                  ttptr = Y->head();
                  f = 1;
                  while (ttptr){
                        //cout <<*(ttptr->getdata()) << endl;
                        if (f >ysize_old){
                                 Z -> addatback(ttptr -> getdata());
			}
                        f +=1;
                        ttptr = ttptr -> getnext();
	          }
                  delete Y; 
                  delete X2;
                  delete tail_list;
                  if (I) delete I;
	     }
             Listnode <List<int> *> *zptr = Z -> head();
             f = 1;
             while (zptr){
                     if (f > zsize_old) M -> addatback(zptr -> getdata());
                     f += 1;
                     zptr = zptr -> getnext();
             }
             delete Z;
             clear_list_itemset(X1);
    }
 
    ttptr = M->head();
    if (print_output) cout << "\nM contains:" << endl;
    while (ttptr){
       if (print_output) cout <<*(ttptr->getdata()) << endl;
       Listnode <int> *mptr = ttptr->getdata()->head();
       int mcnt=0;
       while (mptr){
          mcnt++;
          mptr = mptr->getnext();
       }
       stats.incrlarge(mcnt-1);       
       ttptr = ttptr -> getnext();       
    }
    
    cout <<";Number of maximal frequent itemsets : "<< M->size()<< endl;  
}

int main(int argc, char **argv)
{
  double t20,t30, Sorting_time;

  F1 = new List<int>;

  seconds(ts);

  parse_args(argc, argv);
  partition_alloc(dataf, idxf);
  read_files(F1);

  //cout << "F1 before sorting is : " << *F1 << endl;
  seconds(t20);
  sorting(F1);
  seconds(t30);
  Sorting_time = t30 -t20;

  //cout << "F1 after sorting is : " << *F1 << endl;
  cout << "F1 Size is : " << F1->size() << endl;
  //Listnode<int> *lptr = F1->head();
  //while (lptr){
            //cout << "sup("<< lptr->getdata() << ") = "<< lptr->sup()<<" ";
            //lptr = lptr->getnext();
  //}
  //cout << "F1 Sorting time is  : " << Sorting_time << endl;

  procces_comblists(F1);

  //cout << "The combine Lists are: " << endl;
  //Listnode<int> *fptr= F1 -> head();
  //for (;fptr; fptr = fptr->getnext()){    
   //    int b = fptr ->getdata(); 
     //  if (eqgraph2[b]->size()>0) cout <<"combine set of item ("<<b<<") is "
       //                     << *eqgraph2[b]<<endl;
   //} 

  Max_itset_algo();
   
  //close(it2_fd);
  //munmap((char *)it2_cnt, it2flen);
  
  partition_dealloc();
  
  summary << "GENMAX " << dataf << " " << MINSUP_PER << " "
          << DBASE_NUM_TRANS << " " << MINSUPPORT << " ";  

   seconds(te);

   cout << " Time used for extend: " << extend_time << endl;
   cout << " Time used for find operation: " << find_time << endl;
   cout << " Time used for Differences: " << tid_difference_time 
        << endl;
   cout << " Time used for supper set checking in extend:  "<< super_set_time 
        <<endl;
   cout << " Time used for reading external data base and" << endl 
        << "      Computing lower level Diferences:   " << read_dbase_time 
        << endl;
   cout << ";Total elapsed time " << te-ts 
        << ", NumIntersect " << num_intersect <<"\n";

   stats.tottime = te-ts;
   summary << stats << " " << num_intersect << endl;
   
  exit(0);
}