fcbfsearch.java

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

   *  Specify a starting set of attributes.
   *   Eg. 1,3,5-7.
   *  Any starting attributes specified are
   *  ignored during the ranking.</pre>
   * 
   * <pre> -T &lt;threshold&gt;
   *  Specify a theshold by which attributes
   *  may be discarded from the ranking.</pre>
   * 
   * <pre> -N &lt;num to select&gt;
   *  Specify number of attributes to select</pre>
   * 
   <!-- options-end -->
   *
   * @param options the list of options as an array of strings
   * @throws Exception if an option is not supported
   *
   **/
  public void setOptions (String[] options)
    throws Exception {
    String optionString;
    resetOptions();

    optionString = Utils.getOption('D', options);
    if (optionString.length() != 0) {
      setGenerateDataOutput(Boolean.getBoolean(optionString));
    }

    optionString = Utils.getOption('P', options);
    if (optionString.length() != 0) {
      setStartSet(optionString);
    }

    optionString = Utils.getOption('T', options);
    if (optionString.length() != 0) {
      Double temp;
      temp = Double.valueOf(optionString);
      setThreshold(temp.doubleValue());
    }

    optionString = Utils.getOption('N', options);
    if (optionString.length() != 0) {
      setNumToSelect(Integer.parseInt(optionString));
    }
  }

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

      options[current++] = "-D";
      options[current++] = ""+getGenerateDataOutput();

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

    options[current++] = "-T";
    options[current++] = "" + getThreshold();

    options[current++] = "-N";
    options[current++] = ""+getNumToSelect();

    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();
  }

  /**
   * Kind of a dummy search algorithm. Calls a Attribute evaluator to
   * evaluate each attribute not included in the startSet and then sorts
   * them to produce a ranked list of attributes.
   *
   * @param ASEval the attribute evaluator to guide the search
   * @param data the training instances.
   * @return an array (not necessarily ordered) of selected attribute indexes
   * @throws Exception if the search can't be completed
   */
  public int[] search (ASEvaluation ASEval, Instances data)
    throws Exception {
    int i, j;

    if (!(ASEval instanceof AttributeSetEvaluator)) {
      throw  new Exception(ASEval.getClass().getName()
                           + " is not an "
                           + "Attribute Set evaluator!");
    }

    m_numAttribs = data.numAttributes();

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

    // get the transformed data and check to see if the transformer
    // preserves a class index
    if (ASEval instanceof AttributeTransformer) {
      data = ((AttributeTransformer)ASEval).transformedHeader();
      if (m_classIndex >= 0 && data.classIndex() >= 0) {
        m_classIndex = data.classIndex();
        m_hasClass = true;
      }
    }


    m_startRange.setUpper(m_numAttribs - 1);
    if (!(getStartSet().equals(""))) {
      m_starting = m_startRange.getSelection();
    }

    int sl=0;
    if (m_starting != null) {
      sl = m_starting.length;
    }
    if ((m_starting != null) && (m_hasClass == true)) {
      // see if the supplied list contains the class index
      boolean ok = false;
      for (i = 0; i < sl; i++) {
        if (m_starting[i] == m_classIndex) {
          ok = true;
          break;
        }
      }

      if (ok == false) {
        sl++;
      }
    }
    else {
      if (m_hasClass == true) {
        sl++;
      }
    }


    m_attributeList = new int[m_numAttribs - sl];
    m_attributeMerit = new double[m_numAttribs - sl];

    // add in those attributes not in the starting (omit list)
    for (i = 0, j = 0; i < m_numAttribs; i++) {
      if (!inStarting(i)) {
        m_attributeList[j++] = i;
      }
    }

    this.m_asEval = ASEval;
    AttributeSetEvaluator ASEvaluator = (AttributeSetEvaluator)ASEval;

    for (i = 0; i < m_attributeList.length; i++) {
      m_attributeMerit[i] = ASEvaluator.evaluateAttribute(m_attributeList[i]);
    }

    double[][] tempRanked = rankedAttributes();
    int[] rankedAttributes = new int[m_selectedFeatures.length];

    for (i = 0; i < m_selectedFeatures.length; i++) {
      rankedAttributes[i] = (int)tempRanked[i][0];
    }
    return  rankedAttributes;
  }



  /**
   * Sorts the evaluated attribute list
   *
   * @return an array of sorted (highest eval to lowest) attribute indexes
   * @throws Exception of sorting can't be done.
   */
  public double[][] rankedAttributes ()
    throws Exception {
    int i, j;

    if (m_attributeList == null || m_attributeMerit == null) {
      throw  new Exception("Search must be performed before a ranked "
                           + "attribute list can be obtained");
    }

    int[] ranked = Utils.sort(m_attributeMerit);
    // reverse the order of the ranked indexes
    double[][] bestToWorst = new double[ranked.length][2];

    for (i = ranked.length - 1, j = 0; i >= 0; i--) {
      bestToWorst[j++][0] = ranked[i];
    //alan: means in the arrary ranked, varialbe is from ranked as from small to large
    }

    // convert the indexes to attribute indexes
    for (i = 0; i < bestToWorst.length; i++) {
      int temp = ((int)bestToWorst[i][0]);
      bestToWorst[i][0] = m_attributeList[temp];     //for the index
      bestToWorst[i][1] = m_attributeMerit[temp];    //for the value of the index
    }

    if (m_numToSelect > bestToWorst.length) {
      throw new Exception("More attributes requested than exist in the data");
    }

    this.FCBFElimination(bestToWorst);

    if (m_numToSelect <= 0) {
      if (m_threshold == -Double.MAX_VALUE) {
        m_calculatedNumToSelect = m_selectedFeatures.length;
      } else {
        determineNumToSelectFromThreshold(m_selectedFeatures);
      }
    }
    /*    if (m_numToSelect > 0) {
      determineThreshFromNumToSelect(bestToWorst);
      } */

    return  m_selectedFeatures;
  }

  private void determineNumToSelectFromThreshold(double [][] ranking) {
    int count = 0;
    for (int i = 0; i < ranking.length; i++) {
      if (ranking[i][1] > m_threshold) {
        count++;
      }
    }
    m_calculatedNumToSelect = count;
  }

  private void determineThreshFromNumToSelect(double [][] ranking)
    throws Exception {
    if (m_numToSelect > ranking.length) {
      throw new Exception("More attributes requested than exist in the data");
    }

    if (m_numToSelect == ranking.length) {
      return;
    }

    m_threshold = (ranking[m_numToSelect-1][1] +
                   ranking[m_numToSelect][1]) / 2.0;
  }

  /**
   * returns a description of the search as a String
   * @return a description of the search
   */
  public String toString () {
    StringBuffer BfString = new StringBuffer();
    BfString.append("\tAttribute ranking.\n");

    if (m_starting != null) {
      BfString.append("\tIgnored attributes: ");

      BfString.append(startSetToString());
      BfString.append("\n");
    }

    if (m_threshold != -Double.MAX_VALUE) {
      BfString.append("\tThreshold for discarding attributes: "
                      + Utils.doubleToString(m_threshold,8,4)+"\n");
    }

    BfString.append("\n\n");

    BfString.append("     J || SU(j,Class) ||    I || SU(i,j). \n");

    for (int i=0; i<m_rankedFCBF.length; i++)
    {
      BfString.append(Utils.doubleToString(m_rankedFCBF[i][0]+1,6,0)+" ; "
                      +Utils.doubleToString(m_rankedFCBF[i][1],12,7)+" ; ");
      if (m_rankedFCBF[i][2] == m_rankedFCBF[i][0])
      {
        BfString.append("    *\n");
      }
      else
      {
        BfString.append(Utils.doubleToString(m_rankedFCBF[i][2] + 1,5,0) + " ; "
                     + m_rankedFCBF[i][3] + "\n");
      }
    }

    return BfString.toString();
  }


  /**
   * Resets stuff to default values
   */
  protected void resetOptions () {
    m_starting = null;
    m_startRange = new Range();
    m_attributeList = null;
    m_attributeMerit = null;
    m_threshold = -Double.MAX_VALUE;
  }


  private boolean inStarting (int feat) {
    // omit the class from the evaluation
    if ((m_hasClass == true) && (feat == m_classIndex)) {
      return  true;
    }

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

    for (int i = 0; i < m_starting.length; i++) {
      if (m_starting[i] == feat) {
        return  true;
      }
    }

    return  false;
  }

  private void FCBFElimination(double[][]rankedFeatures)
  throws Exception {

    int i,j;

    m_rankedFCBF = new double[m_attributeList.length][4];
    int[] attributes = new int[1];
    int[] classAtrributes = new int[1];

    int numSelectedAttributes = 0;

    int startPoint = 0;
    double tempSUIJ = 0;

    AttributeSetEvaluator ASEvaluator = (AttributeSetEvaluator)m_asEval;

    for (i = 0; i < rankedFeatures.length; i++) {
      m_rankedFCBF[i][0] = rankedFeatures[i][0];
      m_rankedFCBF[i][1] = rankedFeatures[i][1];
      m_rankedFCBF[i][2] = -1;
    }

    while (startPoint < rankedFeatures.length)
    {
      if (m_rankedFCBF[startPoint][2] != -1)
      {
        startPoint++;
        continue;
      }

      m_rankedFCBF[startPoint][2] = m_rankedFCBF[startPoint][0];
      numSelectedAttributes++;

      for (i = startPoint + 1; i < m_attributeList.length; i++)
      {
        if (m_rankedFCBF[i][2] != -1)
        {
          continue;
        }
        attributes[0] = (int) m_rankedFCBF[startPoint][0];
        classAtrributes[0] = (int) m_rankedFCBF[i][0];
        tempSUIJ = ASEvaluator.evaluateAttribute(attributes, classAtrributes);
        if (m_rankedFCBF[i][1] < tempSUIJ || Math.abs(tempSUIJ-m_rankedFCBF[i][1])<1E-8)
        {
          m_rankedFCBF[i][2] = m_rankedFCBF[startPoint][0];
          m_rankedFCBF[i][3] = tempSUIJ;
        }
      }
      startPoint++;
    }

    m_selectedFeatures = new double[numSelectedAttributes][2];

    for (i = 0, j = 0; i < m_attributeList.length; i++)
    {
      if (m_rankedFCBF[i][2] == m_rankedFCBF[i][0])
      {
        m_selectedFeatures[j][0] = m_rankedFCBF[i][0];
        m_selectedFeatures[j][1] = m_rankedFCBF[i][1];
        j++;
      }
    }
  }
}