lagdhillclimber.java

数据挖掘中聚类的算法

          double bestDeltaScore = 0;
          double currentDeltaScore = 0;
          Operation [] bestOperation = new Operation [nrOfLookAheadSteps];
          Operation [] goodOperations = new Operation [nrOfGoodOperations];
          Operation [] tempOperation = new Operation [nrOfLookAheadSteps-1];
          goodOperations = getGoodOperations(bayesNet, instances, nrOfGoodOperations);
          for (int i = 0; i < nrOfGoodOperations; i++) {
           if (goodOperations[i] != null) {
             performOperation(bayesNet, instances, goodOperations [i]);
             tempOperation = getOptimalOperations(bayesNet, instances, nrOfLookAheadSteps-1, nrOfGoodOperations); // rekursiver Abstieg
             currentDeltaScore = goodOperations [i].m_fDeltaScore;
             for (int j = 0; j < nrOfLookAheadSteps-1; j++) {
                if (tempOperation [j] != null) {
                   currentDeltaScore += tempOperation [j].m_fDeltaScore;
                }
             }
             performOperation(bayesNet, instances, getAntiOperation(goodOperations [i]));
                      if (currentDeltaScore > bestDeltaScore) {
                        bestDeltaScore = currentDeltaScore;
                        bestOperation [0] = goodOperations [i];
                        for (int j = 1; j < nrOfLookAheadSteps; j++) {
                          bestOperation [j] = tempOperation [j-1];
                        }
                    }
            } else i=nrOfGoodOperations;
           }
           return(bestOperation);
       }
    } // getOptimalOperations


	/**
	 * Sets the max number of parents
	 *
	 * @param nMaxNrOfParents the max number of parents
	 */
	public void setMaxNrOfParents(int nMaxNrOfParents) {
	  m_nMaxNrOfParents = nMaxNrOfParents;
	} 

	/**
	 * Gets the max number of parents.
	 *
	 * @return the max number of parents
	 */
	public int getMaxNrOfParents() {
	  return m_nMaxNrOfParents;
	} 

	/**
	 * Sets the number of look-ahead steps
	 *
	 * @param nNrOfLookAheadSteps the number of look-ahead steps
	 */
	public void setNrOfLookAheadSteps(int nNrOfLookAheadSteps) {
	  m_nNrOfLookAheadSteps = nNrOfLookAheadSteps;
	} 

	/**
	 * Gets the number of look-ahead steps
	 *
	 * @return the number of look-ahead step
	 */
	public int getNrOfLookAheadSteps() {
	  return m_nNrOfLookAheadSteps;
	} 

	/**
	 * Sets the number of "good operations"
	 *
	 * @param nNrOfGoodOperations the number of "good operations"
	 */
	public void setNrOfGoodOperations(int nNrOfGoodOperations) {
	  m_nNrOfGoodOperations = nNrOfGoodOperations;
	} 

	/**
	 * Gets the number of "good operations"
	 *
	 * @return the number of "good operations"
	 */
	public int getNrOfGoodOperations() {
	  return m_nNrOfGoodOperations;
	} 


	/**
	 * Returns an enumeration describing the available options.
	 *
	 * @return an enumeration of all the available options.
	 */
	public Enumeration listOptions() {
		Vector newVector = new Vector();

		newVector.addElement(new Option("\tLook Ahead Depth", "L", 2, "-L <nr of look ahead steps>"));
		newVector.addElement(new Option("\tNr of Good Operations", "G", 5, "-G <nr of good operations>"));

		Enumeration enm = super.listOptions();
		while (enm.hasMoreElements()) {
			newVector.addElement(enm.nextElement());
		}
		return newVector.elements();
	} // listOptions

	/**
	 * Parses a given list of options. Valid options are:<p>
	 *
	 <!-- options-start -->
	 * Valid options are: <p/>
	 * 
	 * <pre> -L &lt;nr of look ahead steps&gt;
	 *  Look Ahead Depth</pre>
	 * 
	 * <pre> -G &lt;nr of good operations&gt;
	 *  Nr of Good Operations</pre>
	 * 
	 * <pre> -P &lt;nr of parents&gt;
	 *  Maximum number of parents</pre>
	 * 
	 * <pre> -R
	 *  Use arc reversal operation.
	 *  (default false)</pre>
	 * 
	 * <pre> -N
	 *  Initial structure is empty (instead of Naive Bayes)</pre>
	 * 
	 * <pre> -mbc
	 *  Applies a Markov Blanket correction to the network structure, 
	 *  after a network structure is learned. This ensures that all 
	 *  nodes in the network are part of the Markov blanket of the 
	 *  classifier node.</pre>
	 * 
	 * <pre> -S [BAYES|MDL|ENTROPY|AIC|CROSS_CLASSIC|CROSS_BAYES]
	 *  Score type (BAYES, BDeu, MDL, ENTROPY and AIC)</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 sNrOfLookAheadSteps = Utils.getOption('L', options);
		if (sNrOfLookAheadSteps.length() != 0) {
		  setNrOfLookAheadSteps(Integer.parseInt(sNrOfLookAheadSteps));
		} else {
		  setNrOfLookAheadSteps(2);
		}

                String sNrOfGoodOperations = Utils.getOption('G', options);
		if (sNrOfGoodOperations.length() != 0) {
		  setNrOfGoodOperations(Integer.parseInt(sNrOfGoodOperations));
		} else {
		  setNrOfGoodOperations(5);
		}
		
		super.setOptions(options);
	} // setOptions

	/**
	 * Gets the current settings of the search algorithm.
	 *
	 * @return an array of strings suitable for passing to setOptions
	 */
	public String[] getOptions() {
		String[] superOptions = super.getOptions();
		String[] options = new String[9 + superOptions.length];
		int current = 0;

		options[current++] = "-L";
		options[current++] = "" + m_nNrOfLookAheadSteps;
		
		options[current++] = "-G";
		options[current++] = "" + m_nNrOfGoodOperations;

		// insert options from parent class
		for (int iOption = 0; iOption < superOptions.length; iOption++) {
			options[current++] = superOptions[iOption];
		}

		// Fill up rest with empty strings, not nulls!
		while (current < options.length) {
			options[current++] = "";
		}
		return options;
	} // getOptions


	/**
	 * This will return a string describing the search algorithm.
	 * @return The string.
	 */
	public String globalInfo() {
	  return "This Bayes Network learning algorithm uses a Look Ahead Hill Climbing algorithm called LAGD Hill Climbing." +
	  " Unlike Greedy Hill Climbing it doesn't calculate a best greedy operation (adding, deleting or reversing an arc) " + 
	  "but a sequence of nrOfLookAheadSteps operations, which leads to a network structure whose score is most likely " +
	  "higher in comparison to the network obtained by performing a sequence of nrOfLookAheadSteps greedy operations. " +
	  "The search is not restricted by an order " +
	  "on the variables (unlike K2). The difference with B and B2 is that this hill " +
          "climber also considers arrows part of the naive Bayes structure for deletion.";
	} // globalInfo

	/**
	 * @return a string to describe the Number of Look Ahead Steps option.
	 */
	public String nrOfLookAheadStepsTipText() {
	  return "Sets the Number of Look Ahead Steps. 'nrOfLookAheadSteps = 2' means that all network structures in a " +
	  "distance of 2 (from the current network structure) are taken into account for the decision which arcs to add, " +
	  "remove or reverse. 'nrOfLookAheadSteps = 1' results in Greedy Hill Climbing." ;
	} // nrOfLookAheadStepsTipText

	/**
	 * @return a string to describe the Number of Good Operations option.
	 */
	public String nrOfGoodOperationsTipText() {
	  return "Sets the Number of Good Operations per Look Ahead Step. 'nrOfGoodOperations = 5' means that for the next " +
	  "Look Ahead Step only the 5 best Operations (adding, deleting or reversing an arc) are taken into account for the " +
	  "calculation of the best sequence consisting of nrOfLookAheadSteps operations." ;
	} // nrOfGoodOperationsTipText


} // LAGDHillClimber