linearforwardselection.java

这是关于数据挖掘的一些算法

  /**
   * Get the termination criterion (number of non-improving nodes).
   *
   * @return the number of non-improving nodes
   */
  public int getSearchTermination() {
    return m_maxStale;
  }

  /**
   * Returns the tip text for this property
   *
   * @return tip text for this property suitable for displaying in the
   *         explorer/experimenter gui
   */
  public String performRankingTipText() {
    return "Perform initial ranking to select top-ranked attributes.";
  }

  /**
   * Perform initial ranking to select top-ranked attributes.
   *
   * @param b
   *            true if initial ranking should be performed
   */
  public void setPerformRanking(boolean b) {
    m_performRanking = b;
  }

  /**
   * Get boolean if initial ranking should be performed to select the
   * top-ranked attributes
   *
   * @return true if initial ranking should be performed
   */
  public boolean getPerformRanking() {
    return m_performRanking;
  }

  /**
   * Returns the tip text for this property
   *
   * @return tip text for this property suitable for displaying in the
   *         explorer/experimenter gui
   */
  public String numUsedAttributesTipText() {
    return "Set the amount of top-ranked attributes that are taken into account by the search process.";
  }

  /**
   * Set the number of top-ranked attributes that taken into account by the
   * search process.
   *
   * @param k
   *            the number of attributes
   * @exception Exception
   *                if k is less than 2
   */
  public void setNumUsedAttributes(int k) throws Exception {
    if (k < 2) {
      throw new Exception("Value of -K must be >= 2.");
    }

    m_numUsedAttributes = k;
  }

  /**
   * Get the number of top-ranked attributes that taken into account by the
   * search process.
   *
   * @return the number of top-ranked attributes that taken into account
   */
  public int getNumUsedAttributes() {
    return m_numUsedAttributes;
  }

  /**
   * Returns the tip text for this property
   *
   * @return tip text for this property suitable for displaying in the
   *         explorer/experimenter gui
   */
  public String forwardSelectionMethodTipText() {
    return "Set the direction of the search.";
  }

  /**
   * Set the search direction
   *
   * @param d
   *            the direction of the search
   */
  public void setForwardSelectionMethod(SelectedTag d) {
    if (d.getTags() == TAGS_SEARCH_METHOD) {
      m_forwardSearchMethod = d.getSelectedTag().getID();
    }
  }

  /**
   * Get the search direction
   *
   * @return the direction of the search
   */
  public SelectedTag getForwardSelectionMethod() {
    return new SelectedTag(m_forwardSearchMethod, TAGS_SEARCH_METHOD);
  }

  /**
   * Returns the tip text for this property
   *
   * @return tip text for this property suitable for displaying in the
   *         explorer/experimenter gui
   */
  public String typeTipText() {
    return "Set the type of the search.";
  }

  /**
   * Set the type
   *
   * @param t
   *            the Linear Forward Selection type
   */
  public void setType(SelectedTag t) {
    if (t.getTags() == TAGS_TYPE) {
      m_linearSelectionType = t.getSelectedTag().getID();
    }
  }

  /**
   * Get the type
   *
   * @return the Linear Forward Selection type
   */
  public SelectedTag getType() {
    return new SelectedTag(m_linearSelectionType, TAGS_TYPE);
  }

  /**
   * Returns the tip text for this property
   *
   * @return tip text for this property suitable for displaying in the
   *         explorer/experimenter gui
   */
  public String verboseTipText() {
    return "Turn on verbose output for monitoring the search's progress.";
  }

  /**
   * Set whether verbose output should be generated.
   *
   * @param d
   *            true if output is to be verbose.
   */
  public void setVerbose(boolean b) {
    m_verbose = b;
  }

  /**
   * Get whether output is to be verbose
   *
   * @return true if output will be verbose
   */
  public boolean getVerbose() {
    return m_verbose;
  }

  /**
   * Gets the current settings of LinearForwardSelection.
   *
   * @return an array of strings suitable for passing to setOptions()
   */
  public String[] getOptions() {
    String[] options = new String[13];
    int current = 0;

    if (!(getStartSet().equals(""))) {
      options[current++] = "-P";
      options[current++] = "" + startSetToString();
    }

    options[current++] = "-D";
    options[current++] = "" + m_forwardSearchMethod;
    options[current++] = "-N";
    options[current++] = "" + m_maxStale;

    if (m_performRanking) {
      options[current++] = "-I";
    }

    options[current++] = "-K";
    options[current++] = "" + m_numUsedAttributes;
    options[current++] = "-T";
    options[current++] = "" + m_linearSelectionType;

    options[current++] = "-Z";
    options[current++] = "" + m_verbose;

    while (current < options.length) {
      options[current++] = "";
    }

    return options;
  }

  /**
   * converts the array of starting attributes to a string. This is used by
   * getOptions to return the actual attributes specified as the starting set.
   * This is better than using m_startRanges.getRanges() as the same start set
   * can be specified in different ways from the command line---eg 1,2,3 ==
   * 1-3. This is to ensure that stuff that is stored in a database is
   * comparable.
   *
   * @return a comma seperated list of individual attribute numbers as a
   *         String
   */
  private String startSetToString() {
    StringBuffer FString = new StringBuffer();
    boolean didPrint;

    if (m_starting == null) {
      return getStartSet();
    }

    for (int i = 0; i < m_starting.length; i++) {
      didPrint = false;

      if ((m_hasClass == false) ||
          ((m_hasClass == true) && (i != m_classIndex))) {
        FString.append((m_starting[i] + 1));
        didPrint = true;
      }

      if (i == (m_starting.length - 1)) {
        FString.append("");
      } else {
        if (didPrint) {
          FString.append(",");
        }
      }
    }

    return FString.toString();
  }

  /**
   * returns a description of the search as a String
   *
   * @return a description of the search
   */
  public String toString() {
    StringBuffer LFSString = new StringBuffer();

    LFSString.append("\tLinear Forward Selection.\n\tStart set: ");

    if (m_starting == null) {
      LFSString.append("no attributes\n");
    } else {
      LFSString.append(startSetToString() + "\n");
    }

    LFSString.append("\tForward selection method: ");

    if (m_forwardSearchMethod == SEARCH_METHOD_FORWARD) {
      LFSString.append("forward selection\n");
    } else {
      LFSString.append("floating forward selection\n");
    }

    LFSString.append("\tStale search after " + m_maxStale +
                     " node expansions\n");

    LFSString.append("\tLinear Forward Selection Type: ");

    if (m_linearSelectionType == TYPE_FIXED_SET) {
      LFSString.append("fixed-set\n");
    } else {
      LFSString.append("fixed-width\n");
    }

    LFSString.append("\tNumber of top-ranked attributes that are used: " +
                     m_numUsedAttributes + "\n");

    LFSString.append("\tTotal number of subsets evaluated: " + m_totalEvals +
                     "\n");
    LFSString.append("\tMerit of best subset found: " +
                     Utils.doubleToString(Math.abs(m_bestMerit), 8, 3) + "\n");

    return LFSString.toString();
  }

  /**
   * Searches the attribute subset space by linear forward selection
   *
   * @param ASEvaluator
   *            the attribute evaluator to guide the search
   * @param data
   *            the training instances.
   * @return an array (not necessarily ordered) of selected attribute indexes
   * @exception Exception
   *                if the search can't be completed
   */
  public int[] search(ASEvaluation ASEval, Instances data)
    throws Exception {
    m_totalEvals = 0;

    if (!(ASEval instanceof SubsetEvaluator)) {
      throw new Exception(ASEval.getClass().getName() + " is not a " +
                          "Subset evaluator!");
    }

    if (ASEval instanceof UnsupervisedSubsetEvaluator) {
      m_hasClass = false;
    } else {
      m_hasClass = true;
      m_classIndex = data.classIndex();
    }

    ((SubsetEvaluator) ASEval).buildEvaluator(data);

    m_numAttribs = data.numAttributes();

    if (m_numUsedAttributes > m_numAttribs) {
      System.out.println(
                         "Decreasing number of top-ranked attributes to total number of attributes: " +
                         data.numAttributes());
      m_numUsedAttributes = m_numAttribs;
    }

    BitSet start_group = new BitSet(m_numAttribs);
    m_startRange.setUpper(m_numAttribs - 1);

    if (!(getStartSet().equals(""))) {
      m_starting = m_startRange.getSelection();
    }

    // If a starting subset has been supplied, then initialise the bitset
    if (m_starting != null) {
      for (int i = 0; i < m_starting.length; i++) {
        if ((m_starting[i]) != m_classIndex) {
          start_group.set(m_starting[i]);
        }
      }
    }

    LFSMethods LFS = new LFSMethods();

    int[] ranking;

    if (m_performRanking) {
      ranking = LFS.rankAttributes(data, (SubsetEvaluator) ASEval, m_verbose);
    } else {
      ranking = new int[m_numAttribs];

      for (int i = 0; i < ranking.length; i++) {
        ranking[i] = i;
      }
    }

    if (m_forwardSearchMethod == SEARCH_METHOD_FORWARD) {
      LFS.forwardSearch(m_cacheSize, start_group, ranking, m_numUsedAttributes,
                        m_linearSelectionType == TYPE_FIXED_WIDTH, m_maxStale, -1, data,
                        (SubsetEvaluator) ASEval, m_verbose);
    } else if (m_forwardSearchMethod == SEARCH_METHOD_FLOATING) {
      LFS.floatingForwardSearch(m_cacheSize, start_group, ranking,
                                m_numUsedAttributes, m_linearSelectionType == TYPE_FIXED_WIDTH,
                                m_maxStale, data, (SubsetEvaluator) ASEval, m_verbose);
    }

    m_totalEvals = LFS.getNumEvalsTotal();
    m_bestMerit = LFS.getBestMerit();

    return attributeList(LFS.getBestGroup());
  }

  /**
   * Reset options to default values
   */
  protected void resetOptions() {
    m_maxStale = 5;
    m_forwardSearchMethod = SEARCH_METHOD_FORWARD;
    m_performRanking = true;
    m_numUsedAttributes = 50;
    m_linearSelectionType = TYPE_FIXED_SET;
    m_starting = null;
    m_startRange = new Range();
    m_classIndex = -1;
    m_totalEvals = 0;
    m_cacheSize = 1;
    m_verbose = false;
  }

  /**
   * converts a BitSet into a list of attribute indexes
   *
   * @param group
   *            the BitSet to convert
   * @return an array of attribute indexes
   */
  protected int[] attributeList(BitSet group) {
    int count = 0;

    // count how many were selected
    for (int i = 0; i < m_numAttribs; i++) {
      if (group.get(i)) {
        count++;
      }
    }

    int[] list = new int[count];
    count = 0;

    for (int i = 0; i < m_numAttribs; i++) {
      if (group.get(i)) {
        list[count++] = i;
      }
    }

    return list;
  }
}