lfsmethods.java

来自「这是关于数据挖掘的一些算法」· Java 代码 · 共 692 行 · 第 1/2 页

    double tempMerit = 0;
    Link2 link;
    LinkedList2 list = new LinkedList2(maxStale);
    Hashtable alreadyExpanded = new Hashtable(cacheSize * data.numAttributes());
    int insertCount = 0;
    int backtrackingSteps = 0;
    boolean improvement;
    boolean backward;
    int thisK = k;
    int evalsTotal = 0;
    int evalsCached = 0;

    bestGroup = (BitSet) startGroup.clone();

    String hashKey = bestGroup.toString();
    bestMerit = evaluator.evaluateSubset(bestGroup);

    if (verbose) {
      System.out.print("Group: ");
      printGroup(bestGroup, data.numAttributes());
      System.out.println("Merit: " + tempMerit);
      System.out.println("----------");
    }

    alreadyExpanded.put(hashKey, new Double(bestMerit));
    insertCount++;
    bestSize = bestGroup.cardinality();

    if (maxStale > 1) {
      Object[] best = new Object[1];
      best[0] = bestGroup.clone();
      list.addToList(best, bestMerit);
    }

    backward = improvement = true;

    while (true) {
      // we are search in backward direction -> 
      // continue backward search as long as a new best set is found
      if (backward) {
        if (!improvement) {
          backward = false;
        }
      }
      // we are searching forward ->  
      // stop search or start backward step
      else {
        if (!improvement && (backtrackingSteps >= maxStale)) {
          break;
        }

        backward = true;
      }

      improvement = false;

      // best-first: take first elem from list
      if (maxStale > 1) {
        if (list.size() == 0) {
          backtrackingSteps = maxStale;

          break;
        }

        link = list.getLinkAt(0);
        tempGroup = (BitSet) (link.getData()[0]);
        tempGroup = (BitSet) tempGroup.clone();
        list.removeLinkAt(0);

        tempSize = 0;

        for (int i = 0; i < data.numAttributes(); i++) {
          if (tempGroup.get(i)) {
            tempSize++;
          }
        }
      } else //hill-climbing
        {
          tempGroup = (BitSet) bestGroup.clone();
          tempSize = bestSize;
        }

      //backward search only makes sense for set-size bigger than 2
      if (backward && (tempSize <= 2)) {
        backward = false;
      }

      //set number of top k attributes that are taken into account
      if (incrementK) {
        thisK = Math.max(thisK,
                         Math.min(Math.max(thisK, k + tempSize), data.numAttributes()));
      } else {
        thisK = k;
      }

      //temporarilly add/remove attributes to/from current set
      for (int i = 0; i < thisK; i++) {
        if (ranking[i] == data.classIndex()) {
          continue;
        }

        if (backward) {
          if (!tempGroup.get(ranking[i])) {
            continue;
          }

          tempGroup.clear(ranking[i]);
          tempSize--;
        } else {
          if ((ranking[i] == data.classIndex()) || tempGroup.get(ranking[i])) {
            continue;
          }

          tempGroup.set(ranking[i]);
          tempSize++;
        }

        hashKey = tempGroup.toString();

        if (!alreadyExpanded.containsKey(hashKey)) {
          evalsTotal++;
          tempMerit = evaluator.evaluateSubset(tempGroup);

          if (insertCount > (cacheSize * data.numAttributes())) {
            alreadyExpanded = new Hashtable(cacheSize * data.numAttributes());
            insertCount = 0;
          }

          alreadyExpanded.put(hashKey, new Double(tempMerit));
          insertCount++;
        } else {
          evalsCached++;
          tempMerit = ((Double) alreadyExpanded.get(hashKey)).doubleValue();
        }

        if (verbose) {
          System.out.print("Group: ");
          printGroup(tempGroup, data.numAttributes());
          System.out.println("Merit: " + tempMerit);
        }

        if ((tempMerit - bestMerit) > 0.00001) {
          improvement = true;
          backtrackingSteps = 0;
          bestMerit = tempMerit;
          bestSize = tempSize;
          bestGroup = (BitSet) (tempGroup.clone());
        }

        if (maxStale > 1) {
          Object[] add = new Object[1];
          add[0] = tempGroup.clone();
          list.addToList(add, tempMerit);
        }

        if (backward) {
          tempGroup.set(ranking[i]);
          tempSize++;
        } else {
          tempGroup.clear(ranking[i]);
          tempSize--;
        }
      }

      if (verbose) {
        System.out.println("----------");
      }

      if ((maxStale > 1) && backward && !improvement) {
        Object[] add = new Object[1];
        add[0] = tempGroup.clone();
        list.addToList(add, Double.MAX_VALUE);
      }

      if (!backward && !improvement) {
        backtrackingSteps++;
      }
    }

    if (verbose) {
      System.out.println("Best Group: ");
      printGroup(bestGroup, data.numAttributes());
      System.out.println();
    }

    m_bestGroup = bestGroup;
    m_bestMerit = bestMerit;
    m_evalsTotal += evalsTotal;
    m_evalsCached += evalsCached;

    return bestGroup;
  }

  /**
   * Debug-out
   */
  protected static void printGroup(BitSet tt, int numAttribs) {
    System.out.print("{ ");

    for (int i = 0; i < numAttribs; i++) {
      if (tt.get(i) == true) {
        System.out.print((i + 1) + " ");
      }
    }

    System.out.println("}");
  }

  // Inner classes
  /**
   * Class for a node in a linked list. Used in best first search.
   * Copied from BestFirstSearch
   *
   * @author Mark Hall ([e-mail])
   */
  public class Link2 implements Serializable {
    /* BitSet group; */
    Object[] m_data;
    double m_merit;

    // Constructor
    public Link2(Object[] data, double mer) {
      // group = (BitSet)gr.clone();
      m_data = data;
      m_merit = mer;
    }

    /** Get a group */
    public Object[] getData() {
      return m_data;
    }

    public String toString() {
      return ("Node: " + m_data.toString() + "  " + m_merit);
    }
  }

  /**
   * Class for handling a linked list. Used in best first search. Extends the
   * Vector class.
   *
   * @author Mark Hall ([e-mail])
   */
  public class LinkedList2 extends FastVector {
    // Max number of elements in the list
    int m_MaxSize;

    // ================
    // Public methods
    // ================
    public LinkedList2(int sz) {
      super();
      m_MaxSize = sz;
    }

    /**
     * removes an element (Link) at a specific index from the list.
     *
     * @param index
     *            the index of the element to be removed.
     */
    public void removeLinkAt(int index) throws Exception {
      if ((index >= 0) && (index < size())) {
        removeElementAt(index);
      } else {
        throw new Exception("index out of range (removeLinkAt)");
      }
    }

    /**
     * returns the element (Link) at a specific index from the list.
     *
     * @param index
     *            the index of the element to be returned.
     */
    public Link2 getLinkAt(int index) throws Exception {
      if (size() == 0) {
        throw new Exception("List is empty (getLinkAt)");
      } else {
        if ((index >= 0) && (index < size())) {
          return ((Link2) (elementAt(index)));
        } else {
          throw new Exception("index out of range (getLinkAt)");
        }
      }
    }

    /**
     * adds an element (Link) to the list.
     *
     * @param gr
     *            the attribute set specification
     * @param mer
     *            the "merit" of this attribute set
     */
    public void addToList(Object[] data, double mer) throws Exception {
      Link2 newL = new Link2(data, mer);

      if (size() == 0) {
        addElement(newL);
      } else {
        if (mer > ((Link2) (firstElement())).m_merit) {
          if (size() == m_MaxSize) {
            removeLinkAt(m_MaxSize - 1);
          }

          // ----------
          insertElementAt(newL, 0);
        } else {
          int i = 0;
          int size = size();
          boolean done = false;

          // ------------
          // don't insert if list contains max elements an this
          // is worst than the last
          if ((size == m_MaxSize) &&
              (mer <= ((Link2) (lastElement())).m_merit)) {
          }
          // ---------------
          else {
            while ((!done) && (i < size)) {
              if (mer > ((Link2) (elementAt(i))).m_merit) {
                if (size == m_MaxSize) {
                  removeLinkAt(m_MaxSize - 1);
                }

                // ---------------------
                insertElementAt(newL, i);
                done = true;
              } else {
                if (i == (size - 1)) {
                  addElement(newL);
                  done = true;
                } else {
                  i++;
                }
              }
            }
          }
        }
      }
    }
  }
}