exhaustivesearch.java

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

      text.append("no attributes\n");
    }
    else {
      text.append(startSetToString()+"\n");
    }
    text.append("\tNumber of evaluations: "+m_evaluations+"\n");
    text.append("\tMerit of best subset found: "
		+Utils.doubleToString(Math.abs(m_bestMerit),8,3)+"\n");

    return text.toString();
  }

  /**
   * Searches the attribute subset space using an exhaustive search.
   *
   * @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 {
     double best_merit;
     double tempMerit;
     int setSize;
     boolean done = false;
     int sizeOfBest;
     int tempSize;
     
     m_numAttribs = data.numAttributes();
     m_bestGroup = new BitSet(m_numAttribs);
     
     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 ASEvaluator = (SubsetEvaluator)ASEval;
     m_numAttribs = data.numAttributes();

     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) {
       m_stopAfterFirst = true;
       for (int i = 0; i < m_starting.length; i++) {
	 if ((m_starting[i]) != m_classIndex) {
	   m_bestGroup.set(m_starting[i]);
	 }
       }
     }
     best_merit = ASEvaluator.evaluateSubset(m_bestGroup);
     m_evaluations++;
     sizeOfBest = countFeatures(m_bestGroup);

     if (m_verbose) {
       if (m_stopAfterFirst) {
	 System.out.println("Initial subset ("
			    +Utils.doubleToString(Math.
						  abs(best_merit),8,5)
			    +"): "+printSubset(m_bestGroup));
       }
     }

     BitSet tempGroup = new BitSet(m_numAttribs);
     tempMerit = ASEvaluator.evaluateSubset(tempGroup);

     if (m_verbose) {
       System.out.println("Zero feature subset ("
			  +Utils.doubleToString(Math.
						abs(tempMerit),8,5)
			  +")");
     }

     if (tempMerit >= best_merit) {
       tempSize = countFeatures(tempGroup);
       if (tempMerit > best_merit || 
	   (tempSize < sizeOfBest)) {
	 best_merit = tempMerit;
	 m_bestGroup = (BitSet)(tempGroup.clone());
	 sizeOfBest = tempSize;
       }
       if (m_stopAfterFirst) {
	 done = true;
       }
     }

     int i,j;
     int subset;
     if (!done) {
       emerateSizes: for (setSize = 1;setSize<=m_numAttribs;setSize++) {
	 // set up and evaluate initial subset of this size
	 subset = 0;
	 tempGroup = new BitSet(m_numAttribs);
	 for (i=0;i<setSize;i++) {
	   subset = (subset ^ (1<<i));
	   tempGroup.set(i);
	   if (m_hasClass && i == m_classIndex) {
	     tempGroup.clear(i);
	   }
	 }
	 tempMerit = ASEvaluator.evaluateSubset(tempGroup);
	 m_evaluations++;
	 if (tempMerit >= best_merit) {
	   tempSize = countFeatures(tempGroup);
	   if (tempMerit > best_merit || 
	       (tempSize < sizeOfBest)) {
	     best_merit = tempMerit;
	     m_bestGroup = (BitSet)(tempGroup.clone());
	     sizeOfBest = tempSize;
	     if (m_verbose) {
	       System.out.println("New best subset ("
				+Utils.doubleToString(Math.
						      abs(best_merit),8,5)
				  +"): "+printSubset(m_bestGroup));
	     }
	   }
	   if (m_stopAfterFirst) {
	     done = true;
	     break emerateSizes;
	   }
	 }
	 // generate all the other subsets of this size
	 while (subset > 0) {
	   subset = generateNextSubset(subset, setSize, tempGroup);
	   if (subset > 0) {
	     tempMerit = ASEvaluator.evaluateSubset(tempGroup);
	     m_evaluations++;
	     if (tempMerit >= best_merit) {
	       tempSize = countFeatures(tempGroup);
	       if (tempMerit > best_merit || 
		   (tempSize < sizeOfBest)) {
		 best_merit = tempMerit;
		 m_bestGroup = (BitSet)(tempGroup.clone());
		 sizeOfBest = tempSize;
		 if (m_verbose) {
		   System.out.println("New best subset ("
				      +Utils.
				      doubleToString(Math.
						     abs(best_merit),8,5)
				      +"): "+printSubset(m_bestGroup));
		 }
	       }
	       if (m_stopAfterFirst) {
		 done = true;
		 break emerateSizes;
	       }
	     }
	   }
	 }
       }
     }   
     m_bestMerit = best_merit;
     
     return attributeList(m_bestGroup);
   }

  /**
   * counts the number of features in a subset
   * @param featureSet the feature set for which to count the features
   * @return the number of features in the subset
   */
  private int countFeatures(BitSet featureSet) {
    int count = 0;
    for (int i=0;i<m_numAttribs;i++) {
      if (featureSet.get(i)) {
	count++;
      }
    }
    return count;
  }   

  /**
   * prints a subset as a series of attribute numbers
   * @param temp the subset to print
   * @return a subset as a String of attribute numbers
   */
  private String printSubset(BitSet temp) {
    StringBuffer text = new StringBuffer();

    for (int j=0;j<m_numAttribs;j++) {
      if (temp.get(j)) {
        text.append((j+1)+" ");
      }
    }
    return text.toString();
  }

  /**
   * 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;
  }

  /**
   * generates the next subset of size "size" given the subset "set"
   * coded as an integer. The next subset is returned (as an Integer) 
   * and temp contains this subset as a BitSet.
   * @param set the current subset coded as an integer
   * @param size the size of the feature subset (eg. 2 means that the 
   * current subset contains two features and the next generated subset
   * should also contain 2 features).
   * @param temp will hold the generated subset as a BitSet
   */
  private int generateNextSubset(int set, int size, BitSet temp) {
    int i,j;
    int counter = 0;
    boolean done = false;

    for (i=0;i<m_numAttribs;i++) {
      temp.clear(i);
    }

    while ((!done) && (counter < size)) {
      for (i=m_numAttribs-1-counter;i>=0;i--) {
	if ((set & (1<<i)) !=0) {
	  // erase and move
	  set = (set ^ (1<<i));

	  if (i != (m_numAttribs-1-counter)) {
	    set = (set ^ (1<<i+1));
	    for (j=0;j<counter;j++) {
	      set = (set ^ (1<<(i+2+j)));
	    }
	    done = true;
	    break;
	  } else {
	    counter++;
	    break;
	  }
	}
      }
    }

    for (i=m_numAttribs-1;i>=0;i--) {
      if ((set & (1<<i)) != 0) {
	if (i != m_classIndex) {
	  temp.set(i);
	}
      }
    }
    return set;
  }
      
  /**
   * resets to defaults
   */
  private void resetOptions() {
    m_starting = null;
    m_startRange = new Range();
    m_stopAfterFirst = false;
    m_verbose = false;
    m_evaluations = 0;
  }
}