arset.java

数据挖掘中

/*----------------------------------------------------------------------
  File    : ARSet.java
  Contents: association rule management for visualization
  Author  : Christian Borgelt
  History : 06.07.2004 file created
            09.12.2004 adapted to changed additional evaluation output
            24.01.2005 incomplete adaptation completed
            21.02.2005 adapted to scanner utility functions
----------------------------------------------------------------------*/
package arview;

import java.io.InputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Hashtable;
import util.Arrays;
import util.Scanner;

/*--------------------------------------------------------------------*/
class ItemSet {
/*--------------------------------------------------------------------*/

  private static final int BLKSIZE = 64;

  /*------------------------------------------------------------------*/

  private Hashtable htab;       /* hash table for access by name */
  private String[]  items;      /* vector or item names */
  private int       cnt;        /* current number of items */

  /*------------------------------------------------------------------*/

  public ItemSet ()
  {                             /* --- create an item set */
    this.htab  = new Hashtable(63);
    this.items = new String[BLKSIZE];
    this.cnt   = 0;             /* create an empty item set */
  }  /* ItemSet() */

  /*------------------------------------------------------------------*/

  public int add (String name)
  {                             /* --- add an item */
    String[] vec;               /* buffer for reallocation */
    int      vsz;               /* new vector size */

    vsz = this.items.length;    /* get the size of the item vector */
    if (this.cnt >= vsz) {      /* if the item vector is full */
      vsz += (vsz > BLKSIZE) ? vsz >> 1 : BLKSIZE;
      vec = new String[vsz];    /* create a new item vector */
      System.arraycopy(this.items, 0, vec, 0, this.cnt);
      this.items = vec;         /* copy the vector contents */
    }                           /* and set the new vector */
    this.items[this.cnt] = name;/* add the new item to the set */
    this.htab.put(name, new Integer(this.cnt));
    return this.cnt++;          /* return the item identifier */
  }  /* add() */

  /*------------------------------------------------------------------*/

  public String get (int id) { return this.items[id]; }
  
  /*------------------------------------------------------------------*/

  public int get (String name)
  {                             /* --- get an item identifier */
    Object val = this.htab.get(name);
    if (val != null) return ((Integer)val).intValue();
    return -1;                  /* return the item identifier */
  }  /* get() */

  /*------------------------------------------------------------------*/

  public int getx (String name)
  {                             /* --- get an item identifier */
    Object val = this.htab.get(name);
    if (val != null) return ((Integer)val).intValue();
    return this.add(name);      /* return the item identifier */
  }  /* getx() */

}  /* class ItemSet */

/*--------------------------------------------------------------------*/
class ARule implements Arrays.CompareTo2 {
/*--------------------------------------------------------------------*/

  public  static final int SIZE    = 0;
  public  static final int CONF    = 1;
  public  static final int SUPP    = 2;
  public  static final int LIFT    = 3;
  public  static final int AREM    = 4;
  public  static final int HEAD    = 5;

  /*------------------------------------------------------------------*/

  private static final int BLKSIZE = 8;
  private static final Integer ISIZE = new Integer(SIZE);

  /*------------------------------------------------------------------*/

  private ItemSet iset;         /* underlying item set */
  private int     head;         /* consequent of the association rule */
  private int[]   body;         /* antecedent of the association rule */
  private int     cnt;          /* number of items in antecedent */
  private int     sabs;         /* absolute support */
  private float   supp;         /* relative support */
  private float   conf;         /* confidence */
  private float   lift;         /* lift value */
  private float   arem;         /* additional rule evaluation measure */

  /*------------------------------------------------------------------*/

  public String getHead ()
  { return (this.head >= 0) ? this.iset.get(this.head) : ""; }

  public String getBody (int i)
  { return (i < this.cnt) ? this.iset.get(this.body[i]) : ""; }

  public int    getSize () { return this.cnt;  }
  public float  getSupp () { return this.supp; }
  public int    getSAbs () { return this.sabs; }
  public float  getConf () { return this.conf; }
  public float  getLift () { return this.lift; }
  public float  getAREM () { return this.arem; }

  /*------------------------------------------------------------------*/

  public int compareTo (Object obj, Object data)
  {                             /* --- compare two rules */
    ARule rule = (ARule)obj;    /* get the rule to compare to */
    int   r;                    /* result of comparison */

    switch (((Integer)data).intValue()) {
      case CONF: if (this.conf < rule.conf) return  1;
                 if (this.conf > rule.conf) return -1; break;
      case SUPP: if (this.supp < rule.supp) return  1;
                 if (this.supp > rule.supp) return -1;
                 if (this.sabs < rule.sabs) return  1;
                 if (this.sabs > rule.sabs) return -1; break;
      case LIFT: if (this.lift < rule.lift) return  1;
                 if (this.lift > rule.lift) return -1; break;
      case AREM: if (this.arem < rule.arem) return  1;
                 if (this.arem > rule.arem) return -1; break;
      case SIZE: if (this.cnt  > rule.cnt)  return  1;
                 if (this.cnt  < rule.cnt)  return -1;
      case HEAD: r = this.getHead().compareTo(rule.getHead());
                 if (r != 0) return r;
    }                           /* compare the two rules */
    if (this.conf < rule.conf) return  1;
    if (this.conf > rule.conf) return -1;
    if (this.supp < rule.supp) return  1;
    if (this.supp > rule.supp) return -1;
    if (this.sabs < rule.sabs) return  1;
    if (this.sabs > rule.sabs) return -1;
    if (this.lift < rule.lift) return  1;
    if (this.lift > rule.lift) return -1;
    if (this.arem < rule.arem) return  1;
    if (this.arem > rule.arem) return -1;
    if (this.cnt  > rule.cnt)  return  1;
    if (this.cnt  < rule.cnt)  return -1;
    return this.getHead().compareTo(rule.getHead());
  }  /* compareTo() */          /* compare additional fields */

  /*------------------------------------------------------------------*/

  public void pack ()
  {                             /* --- pack an association rule */
    int[] vec;                  /* buffer for reallocation */
    int   vsz;                  /* size of the body vector */

    vsz = (this.body != null) ? this.body.length : 0;
    if (vsz <= this.cnt) return;
    vec = new int[vsz];         /* if the body vector is too large */
    System.arraycopy(this.body, 0, vec, 0, this.cnt);
    this.body = vec;            /* shrink the body vector */
  }  /* pack() */

  /*------------------------------------------------------------------*/

  public ARule (ItemSet iset, Scanner s) throws IOException
  {                             /* --- parse an association rule */    
    int[] vec;                  /* buffer for reallocation */
    int   vsz;                  /* size of the antecedent vector */

    this.iset = iset;           /* note the underlying item set */
    s.getID();                  /* get the consequent item */
    this.head = iset.getx(s.value);
    if (s.nextToken() != Scanner.T_LFT)
      throw new IOException("'<-' expected " +s.lno());
    this.body = new int[vsz = BLKSIZE];
    while ((s.nextToken() == Scanner.T_ID)
    ||     (s.ttype       == Scanner.T_NUM)) {
      if (this.cnt >= vsz) {    /* if the antecedent vector is full */
        vsz += (vsz > BLKSIZE) ? vsz >> 1 : BLKSIZE;
        vec = new int[vsz];     /* create a new antecedent vector */
        System.arraycopy(this.body, 0, vec, 0, this.cnt);
        this.body = vec;        /* copy the vector contents */
      }                         /* and set the new vector */
      this.body[this.cnt++] = this.iset.getx(s.value);
    }                           /* store the antecedent items */
    s.pushBack();               /* unget last token */
    s.getChar('(');             /* check for a '(' */
    s.getNumber();              /* get the relative support */
    this.supp = Float.parseFloat(s.value);
    s.getChar('/');             /* check for a '/' */
    s.getNumber();              /* get the absolute support */
    this.sabs = Integer.parseInt(s.value);
    s.getChar(',');             /* check for a ',' */
    s.getNumber();              /* get the confidence */
    this.conf = Float.parseFloat(s.value);
    s.getChar(',');             /* check for a ',' */
    s.getNumber();              /* get the lift value */
    this.lift = Float.parseFloat(s.value);
    if (s.nextToken() != ',') { /* if no further number follows */
      this.arem = -Float.MAX_VALUE;
      s.pushBack(); }           /* invalidate the add. evaluation */
    else {                      /* otherwise consume the number */
      s.getNumber();            /* get the additional evaluation */
      this.arem = Float.parseFloat(s.value);
    }
    s.getChar(')');             /* check for a ')' */
    this.pack();                /* pack the parsed association rule */
  }  /* ARule() */

  /*------------------------------------------------------------------*/

  public ARule (ItemSet iset, String desc)    throws IOException
  { this(iset, new Scanner(desc)); }

  public ARule (ItemSet iset, InputStream in) throws IOException
  { this(iset, new Scanner(in)); }

  /*------------------------------------------------------------------*/

  public String toString ()
  {                             /* --- create a string representation */
    int          i;             /* loop variable */
    StringBuffer b;             /* created string representation */
    String       s;             /* buffer for a string */
    
    s = (this.head < 0) ? "" : this.iset.get(this.head);
    b = new StringBuffer(s);    /* start with the consequent */
    b.append(" <-");            /* add implication sign */
    for (i = 0; i < this.cnt; i++) {
      b.append(" "); b.append(this.iset.get(this.body[i])); }
    b.append("  (");            /* add the antecedent items */
    b.append(supp); b.append("/");    /* add evaluation */
    b.append(sabs); b.append(", ");   /* information */
    b.append(conf); b.append(", ");
    b.append(lift); b.append(", ");
    b.append(arem); b.append(")");
    return b.toString();        /* return the string representation */
  }  /* toString() */

}  /* class ARule */

/*--------------------------------------------------------------------*/
public class ARSet {
/*--------------------------------------------------------------------*/

  private static final int BLKSIZE = 64;

  /*------------------------------------------------------------------*/

  ItemSet iset;                 /* underlying item set */
  ARule[] rules;                /* list of association rules */
  int     cnt;                  /* current number of rules */
  int     max;                  /* maximal number of items in body */

  /*------------------------------------------------------------------*/

  public ARSet ()
  {                             /* --- create an association rule set */
    this.iset  = new ItemSet();
    this.rules = new ARule[BLKSIZE];
    this.cnt   = this.max = 0;  /* initialize the fields */
  }  /* ARSet() */

  /*------------------------------------------------------------------*/

  public ItemSet getItemSet    () { return this.iset; }
  public int     getCount      () { return this.cnt; }
  public int     getSize       () { return this.max; }
  public ARule   getRule (int id) { return this.rules[id]; }

  /*------------------------------------------------------------------*/

  public int add (ARule rule)
  {                             /* --- add an association rule */
    ARule[] vec;                /* buffer for reallocation */
    int     vsz;                /* new vector size */

    vsz = this.rules.length;    /* get the size of the rule vector */
    if (this.cnt >= vsz) {      /* if the rule vector is full */
      vsz += (vsz > BLKSIZE) ? vsz >> 1 : BLKSIZE;
      vec = new ARule[vsz];     /* create a new rule vector */
      System.arraycopy(this.rules, 0, vec, 0, this.cnt);
      this.rules = vec;         /* copy the vector contents */
    }                           /* and set the new vector */
    this.rules[this.cnt] = rule;/* add the new rule to the set */
    vsz = rule.getSize();       /* adapt the maximal rule size */
    if (vsz > this.max) this.max = vsz;
    return this.cnt++;          /* return the rule identifier */
  }  /* add() */

  /*------------------------------------------------------------------*/

  public void sort (int field)
  {                             /* --- sort association rules */
    Arrays.sort(this.rules, 0, this.cnt, new Integer(field));
  }  /* sort() */

  /*------------------------------------------------------------------*/

  public ARSet (Scanner s) throws IOException
  {                             /* --- parse an association rule set */
    this();                     /* initialize the ass. rule set */
    while (s.nextToken() != Scanner.T_EOF) {
      s.pushBack(); this.add(new ARule(this.iset, s)); }
  }  /* ARSet() */              /* parse the association rules */

  /*------------------------------------------------------------------*/

  public ARSet (String desc)    throws IOException
  { this(new Scanner(desc)); }

  public ARSet (InputStream in) throws IOException
  { this(new Scanner(in)); }

  /*------------------------------------------------------------------*/

  public static void main (String args[])
  {                             /* --- main function for testing */
    int   i;                    /* loop variable */
    ARSet s;                    /* created association rule set */

    try {                       /* create an association rule set */
      if (args.length <= 0)     /* if no arguments given */
        s = new ARSet("a <- b c (1/3, 20, 80, 150)");
      else                      /* if a file argument is given */
        s = new ARSet(new FileInputStream(args[0])); }
    catch (IOException ioe) {
      System.err.println(ioe.getMessage()); return; }
    for (i = 0; i < s.getCount(); i++)
      System.out.println(s.getRule(i));
  }  /* main() */

}  /* class ARSet */