sequential.java

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

        int iStart = -1;
        for (int j = isp[0]+1; j < i_size; j++)
          if (titems[0] == items[j]) {
            iStart = j;
            isp[0] = j;
            break;
          };

        // No start item found => return:
        if (iStart == -1)
          break;

        // Search remaining items:
        boolean found = false;
        for (int j = 1; j < t_size; j++) {
          isp[j] = isp[j-1];
          int iS = -1;
          for (int k = isp[j]+1; k < i_size; k++)  {

            // Check for previous items which may not occur:
            boolean prev = false;
            for (int l = 0; l < j; l++)
              if (titems[l] == items[k])
                prev = true;

            if (prev)
              break;

            // Check for current item:
            if (titems[j] == items[k]) {
              iS     = k;
              isp[j] = k;
              break;
            };
          };

          // No following item found:
          if (iS == -1)
            break;

          if (j == t_size - 1)
            found = true;
        };

        // Remaining items not found => continue searching:
        if (!found && t_size > 1)
          continue;

        // Found:
        match = true;
        break;
      };

      if (debug) {
        if (match)
          System.out.println("Match trans nr = " + tnr.IntegerAt(i));
        else
          System.out.println("No match!");
      };

      // Transaction supports item set => add to count:
      if (match)
        nsupp = nsupp + 1;
    };

    return nsupp;
  };

  /**
   * Get numbers of all transactions which include the given items.
   *
   * @param items items to be looked for.
   * @param largeItems hash table of large (single) items, points to iTrans
   * @param itemTrans numbers of transactions including the single litem
   * @return numbers of all transactions
   */
  private static IntVector getTransactNumbers(int[] items, IntHashtable largeItems, IntVector[] itemTrans) {

    IntVector transVec = new IntVector();

    IntHashtable itemHash = new IntHashtable();

    int nitems = items.length;

    // Construct hashtable with transaction numbers as keys and number of items
    // as value:
    for (int i = 0; i < nitems; i++) {
      Integer iTem = largeItems.get(items[i]);
      for (int j = 0; j < itemTrans[iTem.intValue()].size(); j++) {
        int it = itemTrans[iTem.intValue()].IntegerAt(j);
        Integer iTrans = itemHash.get(it);
        if (iTrans == null)
          itemHash.put(it, 1);
        else
          itemHash.put(it, iTrans.intValue()+1);
      };
    };

    // Now check all keys and only use those values are equal to nitems,
    // i.e. those transactions which include all given items:
    java.util.Enumeration em = itemHash.keys();
    while (em.hasMoreElements()) {
      Integer Item = (Integer) em.nextElement();
      Integer Numb = (Integer) itemHash.get(Item);
      if (Numb.intValue() == nitems)
        transVec.addElement(Item);
    };

    return transVec;
  }

  /**
   * Finds all permutations for a given item set (as integers).
   * Example: 2 5 1 => 1 2 5, 1 5 2, 2 1 5, 2 5 1, 5 1 2, 5 2 1.
   *
   * @param item as simple array of integers
   * @return all itemsets obtained by permutation as ItemSetSeq
   */
  private static ItemSetSeq[] getISSbyPermut(int[] item) {

    // New sequential item set array:
    int len      = item.length;
    int n_sets   = 1;
    for (int i = 1; i <= len; i++)
      n_sets = i*n_sets;
    ItemSetSeq[] reArr = new ItemSetSeq[n_sets];

    // Start all permutations:
    int[] i_d    = new int[len];
    for (int i = 0; i < len; i++)
      i_d[i] = 0;

    int n_is      = 0;
    while (true) {

        // Check for validity:
        boolean[] rv = new boolean[len];
        for (int i = 0; i < len; i++)
          rv[i] = false;
        for (int i = 0; i < len; i++)
          rv[i_d[i]] = true;

        boolean valid = true;
        for (int i = 0; i < len; i++)
          if (! rv[i])
            valid = false;

        // If valid add to element list:
        if (valid) {
          reArr[n_is] = new ItemSetSeq();
          for (int i = 0; i < len; i++)
            reArr[n_is].addItem(item[ i_d[i] ]);
            n_is = n_is + 1;
        };

        // Set new position:
        if (i_d[0] < len-1) {
          i_d[0] = i_d[0] + 1;
        }
        else {
          int ip = -1;
          for (int i = 0; i < len; i++) {
            if (i_d[i] < len-1) {
              ip = i;
              break;
            };
            i_d[i] = 0;
          };
          if (ip == -1)
            break;
          i_d[ip] = i_d[ip] + 1;
        };
    };

    return reArr;
  }

/*******************************************************************************/
/************************* BEGIN OF SHOWING RESULTS ****************************/
  /**
   * Show large itemsets.
   *
   * @param largeItemSetList list of large itemsets
   * @param nTransact number of transactions
   */
  private static void showLITS(ItemSetList largeItemSetList, int nTransact) {

      int nLITS = largeItemSetList.getSize();

      // LARGE ITEM SETS:
      System.out.println();
      System.out.println("Number of large item sets found: " + nLITS);
      for (int i = 0; i < nLITS; i++) {
        System.out.print(i + ": ");
        ItemSet is   = (ItemSet) largeItemSetList.getItemSetAtNew(i);
        int itemSize = is.getSize();
        for (int j = 0; j < itemSize; j++) {
          int pN                            = is.getIntegerAt(j);
          String pNumb                      = String.valueOf(pN);
          System.out.print(pNumb + " ");
        }
        double Support = 100.0 * ((double) is.getSupportCount()) /
                                 ((double) nTransact);
        System.out.println(" Supp = " + Math.round(Support*100)/100.0);
      }
  }

  /**
   * Shows hash table of large items.
   *
   * The keys of the table are the large items wheras the values
   * point to the vectors of transactions where they occur.
   *
   * @param largeItems integer hashtable of large item sets
   * @param itemTrans array of integer vectors with transaction numbers
   */
//  private static void showLargeItemHash(IntHashtable largeItems, IntVector[] itemTrans) {
private static void showLargeItemHash(IntHashtable largeItems, IntVector[] itemTrans) {
    System.out.println("Large items:");

    java.util.Enumeration em = largeItems.keys();
    while (em.hasMoreElements()) {
      Integer Item = (Integer) em.nextElement();
      System.out.print(Item.intValue() + ": ");
      Integer iTrans = largeItems.get(Item.intValue());
      for (int i = 0; i < itemTrans[iTrans.intValue()].size(); i++)
        System.out.print(itemTrans[iTrans.intValue()].IntegerAt(i) + "\t");
      System.out.println();
    };

  }
/************************** END OF SHOWING RESULTS *****************************/
/*******************************************************************************/

/******************************************************************************/
/*                                                                            */
/**************** BEGIN: OLD OPERATIONS ***************************************/
  /**
   * Sequential basket analysis algorithm of Michael Thess.
   *
   * @param transSet sequential transaction set
   * @param minsupp minimal support
   * @param minconf minimum confidence
   * @return result as list of sequential item sets
   */
  public static SequentialResult SequentialAlg(TransactionSetSeq transSet,
                                             double minsupp, double minconf) {

    return SequentialAlg(transSet, minsupp, minconf, 1, -1);
  }

  /**
   * Sequential basket analysis algorithm of Michael Thess.
   *
   * @param transSet sequantial transaction set
   * @param minsupp minimal support
   * @param minconf not used
   * @param minItemSize minimum size of sequences
   * @param maxItemSize maximum size of sequences, -1 for unbounded
   * @return result as list of sequential item sets
   */
  public static SequentialResult SequentialAlg(TransactionSetSeq transSet,
                                             double minsupp, double minconf,
                                             int minItemSize, int maxItemSize) {

/*******************************************************************************/
/************************* BEGIN OF APRIORI PHASE ******************************/

    // Copy to transaction set:
    TransactionSet ts;
    ts = new TransactionSet();   // First ts is used for usual transactions
    for (int i = 0; i < transSet.getSize(); i++) {
      ItemSet is     = new ItemSet();
      ItemSetSeq iss = (ItemSetSeq) transSet.getItemSetAt(i);
      for (int j = 0; j < iss.getSize(); j++)
        is.addItem( iss.getItemAt(j) );
      ts.addTransaction(is);
    }
    if (debug) {
      transSet.print();
      ts.print();
    };

    // Apply Apriori algorithm for large itemsets:
    ItemSetList largeItemSetList = Apriori.AprioriAlgLITS((TransactionSet) ts, 0, minsupp,
                                                          1, maxItemSize);
    if (debug)
      showLITS(largeItemSetList, ts.getSize());

/*************************** END OF APRIORI PAHSE ******************************/
/*******************************************************************************/

/*******************************************************************************/
/************************ BEGIN OF TRANSFORMATION PHASE ************************/

    // First find all items in large itemsets and write them into hash table:
    IntHashtable largeItems = new IntHashtable();

    int nLITS = largeItemSetList.getSize();  // number of large itemsets
    int nLit  = 0;                           // number of large items
    for (int i = 0; i < nLITS; i++) {
      ItemSet is   = (ItemSet) largeItemSetList.getItemSetAt(i);
      int itemSize = is.getSize();

      for (int j = 0; j < itemSize; j++) {
        int pN = is.getIntegerAt(j);
        if (largeItems.get(pN) == null) {
          largeItems.put(pN, nLit);
          nLit = nLit + 1;
        };
      };
    };

    // Vector containing all transactions for all itemsets:
    IntVector[] itemTrans = new IntVector[nLit];
    for (int i = 0; i < nLit; i++)
      itemTrans[i] = new IntVector();

    // Show large items:
    if (debug)
      showLargeItemHash(largeItems, itemTrans);

    // Now take all items from sequential transaction set which are
    // large items and copy to transaction list 'ts':
    TransactionSetSeq tss;
    tss = new TransactionSetSeq();   // Now ts is used for sequential transactions
    for (int i = 0; i < transSet.getSize(); i++) {

      ItemSetSeq iss   = (ItemSetSeq) transSet.getItemSetAt(i);
      ItemSetSeq isnew = new ItemSetSeq();

      // Copy iss => isnew:
      int prev_item = -1;
      for (int j = 0; j < iss.getSize(); j++) {
        int item      = iss.getItemAt(j);
        Integer Item  = largeItems.get(item);

        // Item is large item => remains part of transaction, if not doubled:
        if (Item != null && item != prev_item) {
          isnew.addItem(item);

          // Add to transaction vector if still not contained:
          int ind = Item.intValue();
          boolean cont = false;
          for (int k = 0; k < itemTrans[ind].size(); k++)
            if (itemTrans[ind].IntegerAt(k) == i)
              cont = true;
          if (!cont)
            itemTrans[ind].addElement(i);
        };

        prev_item = item;
      };

      // Add to transaction list:
      tss.addTransaction(isnew);
    };

    // Show transactions, large items with transactions:
    if (debug) {
      tss.print();
      showLargeItemHash(largeItems, itemTrans);
    };

/************************ END OF TRANSFORMATION PHASE **************************/
/*******************************************************************************/

/*******************************************************************************/
/************************** BEGIN OF SEQUENCE PHASE ****************************/

    // Calculate and get minimum support count:
    tss.setMinSuppCount(minsupp);
    int minSuppCount = tss.getMinSuppCount();
    if (debug)
      System.out.println("minSuppCount = " + minSuppCount);

    // Create list of sequential itemsets:
    ItemSetSeqList sequenceList = new ItemSetSeqList();

    // Check sequential items and add to list:
    for (int i = 0; i < nLITS; i++) {
      // Large itemset:
      ItemSet is   = (ItemSet) largeItemSetList.getItemSetAt(i);
      int itemSize = is.getSize();

      // Filter itemsets of appropriate size:
      if (itemSize < minItemSize)
        continue;

      // Items for testing:
      int[] getItems = new int[itemSize];
      for (int j = 0; j < itemSize; j++)
        getItems[j] = is.getIntegerAt(j);

      // Get all transactions including these numbers:
      IntVector transNr = getTransactNumbers(getItems, largeItems, itemTrans);

      if (debug) {
        System.out.print("\n L I T S: ");
        for (int j = 0; j < itemSize; j++)
          System.out.println(getItems[j] + " ");
        System.out.println();
        System.out.println("Numbers of transactions including this LITS: ");
        for (int j = 0; j < transNr.size(); j++)
          System.out.print(transNr.IntegerAt(j) + " ");
        System.out.println();
      };

      // Create all permutations:
      ItemSetSeq[] testItems = getISSbyPermut(getItems);

      // Get support count of testing itemset:
      for (int j = 0; j < testItems.length; j++) {

        // Show testing itemset:
        if (debug) {
          System.out.println("Candidate item order:");
          testItems[j].print();
        };

        // Get support count:
        int suppCount = getSupportCount(testItems[j], (TransactionSetSeq) tss, transNr);
        if (debug)
          System.out.println("suppCount = " + suppCount);

        // Support constraint if satisfied:
        if (suppCount >= minSuppCount) {
          testItems[j].setSupportCount(suppCount);
          sequenceList.addItemSetSeq(testItems[j]);
        };

      };
    };
/*************************** END OF SEQUENCE PHASE *****************************/
/*******************************************************************************/

    // Show result:
    if (debug) {
      System.out.println("\n R E S U L T:");
      sequenceList.print();
    };

    SequentialResult seqRes = new SequentialResult(sequenceList);

    return seqRes;
  }
/****************** END: OLD OPERATIONS ***************************************/
/*                                                                            */
/******************************************************************************/

}