apriori.java

粗糙集遗传算法例程

import java.util.Vector;
import java.lang.*;
import Row;
import RowSet;
import ItemSet;
import RuleSet;
import Rule;

public class Apriori
{

  private Vector l; // set of large item sets (RowSets)
  private Vector c; // set of candidate large item sets (RowSets)

  //
  // Constructor
  //
  Apriori()
  {
    l = new Vector();
    c = new Vector();
  }

  //
  // Make a Set of Sets where each element set is
  // of size 1 and includes all elemets from the input set
  //
  private final ItemSet generateOneItemItemSets( ItemSet s )
  {
    ItemSet d = new ItemSet();
    Object o[] = s.toArray();
    for(int i=0; i<o.length; i++)
      if( o[i] instanceof ItemSet )
        d.unionWith( generateOneItemItemSets( (ItemSet)o[i] ) );
      else
      {
        ItemSet s1 = new ItemSet();
        s1.add( o[i] );
        d.add( s1 );
      }

   return d;
  }

  //
  // Same as aprioriGen but using D as input
  //
  private final RowSet genL1(ItemSet d, int minSup)
  {

    // Generate 1 item itemSet
    ItemSet oneItemSet = generateOneItemItemSets(d);

    // Generate C1 (which is a set of Rows)
    RowSet c1 = new RowSet( oneItemSet );

    // support C1
    c1.updateSupportA(d);  

    // Remove itemsets without minimum support
    c1.pruneForMinimumSupport(minSup);

  return c1;
  }

  //
  // Generate an ItemSet out of the sets in the RowSet
  //
  public static ItemSet makeItemSet(RowSet s)
  {
    ItemSet set = new ItemSet();
    //
    // collect all itemsets from each row
    // and add them to collector
    //
    Object o[] = s.toArray();
    for(int i=0; i<o.length; i++)
    {
      set.add( ((Row)o[i]).getSet() );
    }
  return set;
  }
  
  // 
  // Generate all super sets of rank +1 from L
  // that are supported by k items in L
  // 
  private final ItemSet aprioriGen( RowSet L, int k )
  {
//System.err.println("AprioriGen");
    ItemSet itemSet = new ItemSet();

    ItemSet l = makeItemSet(L);

    Object o[] = l.toArray();
    int end=o.length-1;
    for(int i=0; i<end; i++)
    {
      ItemSet s1 = (ItemSet)o[i];
      for(int j=i+1; j<o.length; j++)
      {
	ItemSet s2 = (ItemSet)o[j];
        if( s2.intersection(s1).size() == k-2 )
          itemSet.add( s2.union(s1) );
      }
    }

    //
    // Remove itemsets that are not supported by at least
    // k itemsets in L
    //
    RowSet ck = new RowSet( itemSet );
    ck.updateSupport( l );
    ck.pruneForMinimumSupport( k );

  return makeItemSet(ck);
  }

  //
  //
  //
  private final RuleSet generateRules(ItemSet d, float minConf)
  {
    RuleSet rules = new RuleSet();

    Object o[] = l.toArray();
    for(int i=0; i<o.length; i++)
    {
      RowSet s = (RowSet)o[i];

      Object p[] = s.toArray();
      for(int j=0; j<p.length; j++)
      {
        ItemSet largeItemSet = ( (Row)p[j] ).getSet();
        ItemSet largeItemSetSubSets = generateSubSets(largeItemSet);

        Object q[] = largeItemSetSubSets.toArray();
        for(int x=0; x<q.length; x++)
        {
          ItemSet lhs = (ItemSet)q[x];
          ItemSet rhs = largeItemSet.difference(lhs);

          int supportRHS = ((Row)p[j]).getSupport();
          int supportLHS = support(lhs, d);

          float confidence = (float) supportRHS / supportLHS;

          if( confidence >= minConf && !rhs.isEmpty() )
            rules.add( new Rule(lhs, rhs, supportRHS, confidence) );
//            System.out.println("RULE: "+translateRule(lhs,rhs)+"(confidence="+confidence+" support="+supportRHS+")");
        }
      }
    }                        

  return rules;
  }


  //
  // Calculate the support for s in d
  //
  public static int support(ItemSet s, ItemSet d)
  {
    int support=0;
    Object o[] = d.toArray();
    for(int i=0; i<o.length; i++)
      if( s.subsetOf( (ItemSet)o[i] ) )
        ++support;
  return support;
  }

  //
  // Generate all possible subsets of s
  //
  public static ItemSet generateSubSets(ItemSet s)
  {
    ItemSet subSets = itemizeSet(s);

    int rank = s.size()-1;
    for( int k = 0; k<rank; k++)
    {
      ItemSet currSet = (ItemSet)subSets.clone();

      Object o[] = currSet.toArray();
      int end=o.length-1;
      for(int i=0; i<end; i++)
      {
        ItemSet s1 = (ItemSet)o[i];
        for(int j=i+1; j<o.length; j++)
        {
          ItemSet s2 = (ItemSet)o[j];
          if( s1.intersection(s2).size() == k )
            subSets.add( s1.union(s2) );
        }
      }
    }
      
  return subSets;          
  }

  //
  // return a set of set of the elements 
  //
  public static ItemSet itemizeSet(ItemSet s)
  {
    ItemSet set = new ItemSet();

    Object o[] = s.toArray();
    for(int i=0; i<o.length; i++)
    {
      ItemSet s1 = new ItemSet();
      s1.add( o[i] );
      set.add(s1);
    }
  return set;
  }

  //
  // Apply the Apriori algorithm to set
  //
  public final RuleSet go( ItemSet d, int minSup, float minConf )
  {
    //
    // check to make sure d has elements
    //
    if ( d.isEmpty() )
      return( new RuleSet() );

    //
    // Generate L1
    //
    l.add( this.genL1(d, minSup) );
//System.out.println("L1 is "+l.lastElement());
    //
    // Calculate all Lx and Cx until Lx is empty
    //
    int k=1;

    RowSet lastL = (RowSet) l.lastElement();
    while( lastL.isEmpty() == false )
    {
      ++k;  // try to generate k rank item sets
      //System.out.println("Generating L"+k);
      System.err.println("Generating L"+k);
      // generate c[k]
      ItemSet ck = aprioriGen( lastL, k );

      c.add( ck );
//System.out.println("We got this bac"+c.lastElement());
      RowSet ckr = new RowSet( ck );
      ckr.updateSupportA( d );
//System.out.println("ckr now is"+ckr);
      ckr.pruneForMinimumSupport( minSup );
//System.out.println("ckr now is"+ckr);
      l.add( ckr );
      lastL = ckr;
//System.out.println("Lk is "+lastL);
    }

    
   return( generateRules(d, minConf) );   
   }                
  }