ranksearch.java

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

  /**
   * Parses a given list of options. <p/>
   *
   <!-- options-start -->
   * Valid options are: <p/>
   * 
   * <pre> -A &lt;attribute evaluator&gt;
   *  class name of attribute evaluator to use for ranking. Place any
   *  evaluator options LAST on the command line following a "--".
   *  eg.:
   *   -A weka.attributeSelection.GainRatioAttributeEval ... -- -M
   *  (default: weka.attributeSelection.GainRatioAttributeEval)</pre>
   * 
   * <pre> -S &lt;step size&gt;
   *  number of attributes to be added from the
   *  ranking in each iteration (default = 1).</pre>
   * 
   * <pre> -R &lt;start point&gt;
   *  point in the ranking to start evaluating from. 
   *  (default = 0, ie. the head of the ranking).</pre>
   * 
   * <pre> 
   * Options specific to evaluator weka.attributeSelection.GainRatioAttributeEval:
   * </pre>
   * 
   * <pre> -M
   *  treat missing values as a seperate value.</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('S', options);
    if (optionString.length() != 0) {
      setStepSize(Integer.parseInt(optionString));
    }

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

    optionString = Utils.getOption('A', options);
    if (optionString.length() == 0)
      optionString = GainRatioAttributeEval.class.getName();
    setAttributeEvaluator(ASEvaluation.forName(optionString, 
                                     Utils.partitionOptions(options)));
  }

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

    if ((m_ASEval != null) && 
        (m_ASEval instanceof OptionHandler)) {
      evaluatorOptions = ((OptionHandler)m_ASEval).getOptions();
    }

    String[] options = new String[8 + evaluatorOptions.length];
    int current = 0;

    options[current++] = "-S"; options[current++] = ""+getStepSize();

    options[current++] = "-R"; options[current++] = ""+getStartPoint();

    if (getAttributeEvaluator() != null) {
      options[current++] = "-A";
      options[current++] = getAttributeEvaluator().getClass().getName();
    }

    if (evaluatorOptions.length > 0) {
      options[current++] = "--";
      System.arraycopy(evaluatorOptions, 0, options, current, 
          evaluatorOptions.length);
      current += evaluatorOptions.length;
    }

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

    return  options;
  }

  /**
   * Reset the search method.
   */
  protected void resetOptions () {
    m_ASEval = new GainRatioAttributeEval();
    m_Ranking = null;
  }

  /**
   * Ranks attributes using the specified attribute evaluator and then
   * searches the ranking using the supplied subset evaluator.
   *
   * @param ASEval the subset 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 {
    
    double best_merit = -Double.MAX_VALUE;
    double temp_merit;
    BitSet temp_group, best_group=null;
    
    if (!(ASEval instanceof SubsetEvaluator)) {
      throw  new Exception(ASEval.getClass().getName() 
                           + " is not a " 
                           + "Subset evaluator!");
    }

    m_SubsetEval = ASEval;
    m_Instances = data;
    m_numAttribs = m_Instances.numAttributes();

    /*    if (m_ASEval instanceof AttributeTransformer) {
      throw new Exception("Can't use an attribute transformer "
                          +"with RankSearch");
                          } */
    if (m_ASEval instanceof UnsupervisedAttributeEvaluator || 
        m_ASEval instanceof UnsupervisedSubsetEvaluator) {
      m_hasClass = false;
      /*      if (!(m_SubsetEval instanceof UnsupervisedSubsetEvaluator)) {
        throw new Exception("Must use an unsupervised subset evaluator.");
        } */
    }
    else {
      m_hasClass = true;
      m_classIndex = m_Instances.classIndex();
    }

    if (m_ASEval instanceof AttributeEvaluator) {
      // generate the attribute ranking first
      Ranker ranker = new Ranker();
      ((AttributeEvaluator)m_ASEval).buildEvaluator(m_Instances);
      if (m_ASEval instanceof AttributeTransformer) {
        // get the transformed data a rebuild the subset evaluator
        m_Instances = ((AttributeTransformer)m_ASEval).
          transformedData();
        ((SubsetEvaluator)m_SubsetEval).buildEvaluator(m_Instances);
      }
      m_Ranking = ranker.search((AttributeEvaluator)m_ASEval, m_Instances);
    } else {
      GreedyStepwise fs = new GreedyStepwise();
      double [][]rankres; 
      fs.setGenerateRanking(true);
      ((SubsetEvaluator)m_ASEval).buildEvaluator(m_Instances);
      fs.search(m_ASEval, m_Instances);
      rankres = fs.rankedAttributes();
      m_Ranking = new int[rankres.length];
      for (int i=0;i<rankres.length;i++) {
        m_Ranking[i] = (int)rankres[i][0];
      }
    }

    // now evaluate the attribute ranking
    for (int i=m_startPoint;i<m_Ranking.length;i+=m_add) {
      temp_group = new BitSet(m_numAttribs);
      for (int j=0;j<=i;j++) {
        temp_group.set(m_Ranking[j]);
      }
      temp_merit = ((SubsetEvaluator)m_SubsetEval).evaluateSubset(temp_group);

      if (temp_merit > best_merit) {
        best_merit = temp_merit;;
        best_group = temp_group;
      }
    }
    m_bestMerit = best_merit;
    return attributeList(best_group);
  }
    
  /**
   * converts a BitSet into a list of attribute indexes 
   * @param group the BitSet to convert
   * @return an array of attribute indexes
   **/
  private 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;
  }

   /**
   * returns a description of the search as a String
   * @return a description of the search
   */
  public String toString () {
    StringBuffer text = new StringBuffer();
    text.append("\tRankSearch :\n");
    text.append("\tAttribute evaluator : "
                + getAttributeEvaluator().getClass().getName() +" ");
    if (m_ASEval instanceof OptionHandler) {
      String[] evaluatorOptions = new String[0];
      evaluatorOptions = ((OptionHandler)m_ASEval).getOptions();
      for (int i=0;i<evaluatorOptions.length;i++) {
        text.append(evaluatorOptions[i]+' ');
      }
    }
    text.append("\n");
    text.append("\tAttribute ranking : \n");
    int rlength = (int)(Math.log(m_Ranking.length) / Math.log(10) + 1);
    for (int i=0;i<m_Ranking.length;i++) {
      text.append("\t "+Utils.doubleToString((double)(m_Ranking[i]+1),
                                             rlength,0)
                  +" "+m_Instances.attribute(m_Ranking[i]).name()+'\n');
    }
    text.append("\tMerit of best subset found : ");
    int fieldwidth = 3;
    double precision = (m_bestMerit - (int)m_bestMerit);
    if (Math.abs(m_bestMerit) > 0) {
      fieldwidth = (int)Math.abs((Math.log(Math.abs(m_bestMerit)) / Math.log(10)))+2;
    }
    if (Math.abs(precision) > 0) {
      precision = Math.abs((Math.log(Math.abs(precision)) / Math.log(10)))+3;
    } else {
      precision = 2;
    }

    text.append(Utils.doubleToString(Math.abs(m_bestMerit),
                                     fieldwidth+(int)precision,
                                     (int)precision)+"\n");
    return text.toString();
  }
}