flatrulesalgorithm.java

一个数据挖掘软件ALPHAMINERR的整个过程的JAVA版源代码

    }

    /**
     * Process new transaction by adding to to the product lists
     * together with possible product combinations.
     *
     * @param is item set which is contained in the transaction
     * @param transnr transaction number
     * @throws MiningException cannot process transaction
     */
    private void processTransaction(ItemSet is, int transnr)
      throws MiningException {

      // Init:
      int nsize = is.getSize();

      // Transaction must contain at least 2 items:
//      if (nsize < 2)
//        return;

      // Fill tables:
      for (int i = 0; i < nsize; i++) {
        // Get current item:
        int item     = is.getItemAt(i);

        int ip = 0;
        IntVector tv    = null;
        IntHashtable ni = null;

        // Get position in hashtable:
        Integer iTem = itemHash.get(item);

        // Add new item:
        if (iTem == null) {
          itemHash.put(item, nItems);
          ip = nItems;
          tv = new IntVector();
          ni = new IntHashtable();
          itemTrans.addElement(tv);
          itemNeighb.addElement(ni);
          itemSims.addElement(new Vector());
          nItems = nItems + 1;
        }
        else {
          ip = iTem.intValue();
          tv = (IntVector) itemTrans.elementAt(ip);
          ni = (IntHashtable) itemNeighb.elementAt(ip);
        }

        // Add new transaction vector:
        tv.addElement(transnr);

        // Add new neighbouring hashtable:
        for (int j = i+1; j < nsize; j++) {
          int item2 = is.getItemAt(j);
          if ( ni.get(item2) != null )
            continue;

          Integer iTN = itemHash.get(item2);
          if (iTN == null)
            ni.put(item2, 0);
          else {
            int ip2 = iTN.intValue();
            IntHashtable ni2 = (IntHashtable) itemNeighb.elementAt(ip2);
            if (ni2.get(item) == null)
              ni.put(item2, 0);
          };
        };
      };
    }

    /**
     * Prints for all products the containing transactions and
     * neighbouring elements.
     */
    private void printItemData() {

      Enumeration em = itemHash.keys();
      while ( em.hasMoreElements() ) {
        int item = ((Integer) em.nextElement()).intValue();
        int ip   = ((Integer) itemHash.get(item)).intValue();
        IntVector tv    = (IntVector) itemTrans.elementAt(ip);
        IntHashtable ni = (IntHashtable) itemNeighb.elementAt(ip);

        System.out.println("item = " + item + " ip = " + ip);
        System.out.print("--> TA:");
        for (int i = 0; i < tv.size(); i++)
          System.out.print(tv.IntegerAt(i) + " ");
        System.out.println();
        System.out.print("--> NB:");
        Enumeration it = ni.keys();
        while( it.hasMoreElements() ) {
          Integer Item2 = (Integer) it.nextElement();
          System.out.print(Item2.intValue() + " ");
        }
        System.out.println();
      };
    }

    /**
     * Calculate similarity between neighbouring items.
     *
     * @throws MiningException cannot calculate similarities.
     */
    private void calcItemSimilarities() throws MiningException {

      Enumeration em = itemHash.keys();
      while ( em.hasMoreElements() ) {
        int item = ((Integer) em.nextElement()).intValue();
        int ip   = ((Integer) itemHash.get(item)).intValue();
        IntVector tv    = (IntVector) itemTrans.elementAt(ip);
        IntHashtable ni = (IntHashtable) itemNeighb.elementAt(ip);
        Vector neighb   = (Vector) itemSims.elementAt(ip);

        // Calculate similarities to all neighbouring vectors:
        Enumeration it  = ni.keys();
        while( it.hasMoreElements() ) {
          int item2 = ((Integer) it.nextElement()).intValue();
          int ip2   = ((Integer) itemHash.get(item2)).intValue();
          IntVector tv2  = (IntVector) itemTrans.elementAt(ip2);
          Vector neighb2 = (Vector) itemSims.elementAt(ip2);

          // Calculate similarity between both vectors:
          double[] sims = calcItemSimilarity(item, item2, tv, tv2);

          // Minimum support condition violated => next:
          if (sims == null)
            continue;

          // Add to large itemsets, if desired:
          if (createLargeItemSets) {
            ItemSet is1 = new ItemSet();
            is1.addItem(item);
            if (lits.get(is1) == null) {
              is1.setSupportCount( tv.size() );
              lits.put(is1, 0);
            };
            ItemSet is2 = new ItemSet();
            is2.addItem(item2);
            if (lits.get(is2) == null) {
              is2.setSupportCount( tv2.size() );
              lits.put(is2, 0);
            };
            ItemSet is3 = new ItemSet(is1, item2);
            if (lits.get(is3) == null) {
              is3.setSupportCount( (int) sims[0] );
              lits.put(is3, 0);
            }
          }

          // Add item 2 to neighbour list of item 1:
          if (sims[1] >= minimumConfidence) {
            SortItem si = new SortItem();
            si.item = item2;
            si.supp = (int) sims[0];
            si.conf = (float) sims[1];
            si.lift = (float) sims[3];
            neighb.addElement(si);
          }

          // Add item 1 to neighbour list of item 2:
          if (sims[2] >= minimumConfidence) {
            SortItem si2 = new SortItem();
            si2.item = item;
            si2.supp = (int) sims[0];
            si2.conf = (float) sims[2];
            si2.lift = (float) sims[3];
            neighb2.addElement(si2);
          }
        };
      };

      // Clear previous hashtables:
      itemTrans.clear();
      itemNeighb.clear();
    }

    /**
     * Calculates similarity between two items.
     *
     * @param item1 item 1
     * @param item2 item 2
     * @param tv1 vector of transactions containing item 1
     * @param tv2 vector of transactions containing item 2
     * @return array [support(i1,i2), conf(i1->i2), conf(i2->i1), lift(i1,i2)],
     * null if minimum support count condition violated
     * @throws MiningException cannot calculate similarity
     */
    private double[] calcItemSimilarity(int item1, int item2, IntVector tv1, IntVector tv2)
     throws MiningException {

      // Similarity:
      double[] sim = new double[4];

      // Calculate support, i.e. number of identic transactions in tv1 and tv2:
      int nmatch = numberMatchingTransactions(tv1, tv2);

      // Minimum support count violated => return:
      if (nmatch < minimumSuppCount) return null;

      // Save support, confidences, and lift:
      int n1 = tv1.size();
      int n2 = tv2.size();
      sim[0] = nmatch;
      sim[1] = ((double) nmatch) / n1;
      sim[2] = ((double) nmatch) / n2;
      sim[3] = ((double) nmatch) / (n1*n2);  // to be multiplied with nTransact

      return sim;
    }

    /**
     * Calculates number of matching transactions in both vectors,
     * i.e. power of the intersection.
     *
     * @param tv1 vector 1
     * @param tv2 vector 2
     * @return number of matchig elements
     */
    private int numberMatchingTransactions(IntVector tv1, IntVector tv2) {

      int nmatch = 0;
      IntHashtable transHash = new IntHashtable();
      for (int i = 0; i < tv1.size(); i++) {
        int it1 = tv1.IntegerAt(i);
        transHash.put(it1, 1);
      }
      for (int i = 0; i < tv2.size(); i++) {
        int it2 = tv2.IntegerAt(i);
        Integer iTrans = transHash.get(it2);
        if (iTrans != null)
          nmatch = nmatch + 1;
      }

      return nmatch;
    }

    /**
     * Sort neighbouring items into descending order by similarity
     * and cut all neighbours that are more than maximumItemSize away.
     *
     * @throws MiningException cannot sort similar items
     */
    private void sortItemSimilarities() throws MiningException {

      Enumeration em = itemHash.keys();
      while ( em.hasMoreElements() ) {
        int item = ((Integer) em.nextElement()).intValue();
        int ip   = ((Integer) itemHash.get(item)).intValue();
        Vector neighb = (Vector) itemSims.elementAt(ip);

        // Sort neighbouring list into descending order:
        int nneighb = neighb.size();
        SortItem[] sItems = new SortItem[nneighb];
        for (int i = 0; i < nneighb; i++)
          sItems[i] = (SortItem) neighb.elementAt(i);
        Arrays.sort(sItems);

        // Copy back and cut all neigbours that are farer than maxItemSize:
        neighb.clear();
        for (int i = 0; i < nneighb; i++) {
          if (maximumItemSize > -1 && i >= maximumItemSize)
            break;
          neighb.addElement(sItems[i]);
        }
      }
    }

/**
 * Class for sorting neighbouring items with given order function.
 * Compare operator is defined for descending ordering by order measure.
 */
private class SortItem implements java.lang.Comparable
{
    int item;
    int supp;
    float conf;
    float lift;

    public int compareTo(Object o) {

      SortItem y = (SortItem) o;
      if (rulesOrderType == ORDER_SUPP) {
        if (supp < y.supp) return +1;
        else return -1;
      }
      else if (rulesOrderType == ORDER_CONF) {
        if (conf < y.conf) return +1;
        else return -1;
      }
      else if (rulesOrderType == ORDER_SUPP_CONF) {
        if (supp*conf < y.supp*y.conf) return +1;
        else return -1;
      }
      else if (rulesOrderType == ORDER_LIFT) {
        if (lift < y.lift) return +1;
        else return -1;
      }

      return -1;
    }

    public String toString() {
      String s = "item = " + item + " supp = " + supp + " conf = " + conf +
                 " lift = " + lift;
      return s;
    }
};

    /**
     * Save results in rules and large itemsets.
     *
     * @throws MiningException cannot save results
     */
    private void saveResults() throws MiningException {

      // Rules:
      int nitems = 0;
      int nrecs  = 0;
      Enumeration em = itemHash.keys();
      while (em.hasMoreElements()) {
        int item = ((Integer) em.nextElement()).intValue();
        int ip   = ((Integer) itemHash.get(item)).intValue();
        Vector neighb = (Vector) itemSims.elementAt(ip);

        // Premise itemset:
        ItemSet is1 = new ItemSet();
        is1.addItem(item);
        int nneighb = neighb.size();
        for (int i = 0; i < nneighb; i++) {
          // Neighbour item:
          SortItem si = (SortItem) neighb.elementAt(i);
          int item2   = si.item;
          int suppct  = si.supp;
          double conf = si.conf;
          double lift = si.lift*nTransact;
          double supp = 0.0;
          if (nTransact > 0) supp = ((double)suppct) / nTransact;

          // Conclusion itemset:
          ItemSet is2 = new ItemSet();
          is2.addItem(item2);

          // Association rule:
          RuleSet rs  = new RuleSet(is1, is2, supp, conf);
          rs.setLift(lift);
          associationRules.addElement(rs);
        }
        nitems++;
        if (nneighb > 0) nrecs++;
      }
//      if (debug > 0) System.out.println("#nItems = " + categoryItemId.getCategoriesNumber() );
      if (debug > 0) System.out.println("#nItems = " + nitems);
      if (debug > 0) System.out.println("#recItems = " + nrecs);
      
      fireMiningEvent(new AlgorithmStatusMessage(getAlgorithmLevel(), "RulesGenerationFinished", new Object[]{new Integer(associationRules.size())}));

      // Large itemsets:
      if (!createLargeItemSets)
        return;
      
      fireMiningEvent(new AlgorithmStatusMessage(getAlgorithmLevel(), "LargeItemSetsGenerationStarted", null));
      
      em = lits.keys();
      while (em.hasMoreElements()) {
        ItemSet is = (ItemSet) em.nextElement();
        largeItemSets.addElement(is);
      }
      
      fireMiningEvent(new AlgorithmStatusMessage(getAlgorithmLevel(), "LargeItemSetsFound", new Object[]{new Integer(largeItemSets.size())}));
    }

    /**
     * Returns string representation of algorithm.
     *
     * @return string representation of algorithm
     */
    public String toString()
    {
        return "FlatRulesAlgorithm";
    }
}