localscoresearchalgorithm.java

数据挖掘中聚类的算法

					// it seems safe to assume that numInstances>0 here
				}

				break;

			case (Scoreable.AIC) :
				{
					fLogScore -= nCardinality * (numValues - 1);
				}

				break;
		}

		return fLogScore;
	} // CalcNodeScore

	protected double calcScoreOfCounts2(int[][] nCounts, int nCardinality, int numValues, Instances instances) {

		// calculate scores using the distributions
		double fLogScore = 0.0;

		for (int iParent = 0; iParent < nCardinality; iParent++) {
			switch (m_nScoreType) {

				case (Scoreable.BAYES) :
					{
						double nSumOfCounts = 0;

						for (int iSymbol = 0; iSymbol < numValues; iSymbol++) {
							if (m_fAlpha + nCounts[iParent][iSymbol] != 0) {
								fLogScore += Statistics.lnGamma(m_fAlpha + nCounts[iParent][iSymbol]);
								nSumOfCounts += m_fAlpha + nCounts[iParent][iSymbol];
							}
						}

						if (nSumOfCounts != 0) {
							fLogScore -= Statistics.lnGamma(nSumOfCounts);
						}

						if (m_fAlpha != 0) {
							fLogScore -= numValues * Statistics.lnGamma(m_fAlpha);
							fLogScore += Statistics.lnGamma(numValues * m_fAlpha);
						}
					}

					break;

				case (Scoreable.BDeu) :
				{
					double nSumOfCounts = 0;

					for (int iSymbol = 0; iSymbol < numValues; iSymbol++) {
						if (m_fAlpha + nCounts[iParent * numValues][iSymbol] != 0) {
							fLogScore += Statistics.lnGamma(1.0/(numValues * nCardinality) + nCounts[iParent * numValues][iSymbol]);
							nSumOfCounts += 1.0/(numValues * nCardinality) + nCounts[iParent * numValues][iSymbol];
						}
					}
					fLogScore -= Statistics.lnGamma(nSumOfCounts);

					fLogScore -= numValues * Statistics.lnGamma(1.0/(nCardinality * numValues));
					fLogScore += Statistics.lnGamma(1.0/ nCardinality);
				}
					break;

				case (Scoreable.MDL) :

				case (Scoreable.AIC) :

				case (Scoreable.ENTROPY) :
					{
						double nSumOfCounts = 0;

						for (int iSymbol = 0; iSymbol < numValues; iSymbol++) {
							nSumOfCounts += nCounts[iParent][iSymbol];
						}

						for (int iSymbol = 0; iSymbol < numValues; iSymbol++) {
							if (nCounts[iParent][iSymbol] > 0) {
								fLogScore += nCounts[iParent][iSymbol]
									* Math.log(nCounts[iParent][iSymbol] / nSumOfCounts);
							}
						}
					}

					break;

				default :
					{
					}
			}
		}

		switch (m_nScoreType) {

			case (Scoreable.MDL) :
				{
					fLogScore -= 0.5 * nCardinality * (numValues - 1) * Math.log(instances.numInstances());

					// it seems safe to assume that numInstances>0 here
				}

				break;

			case (Scoreable.AIC) :
				{
					fLogScore -= nCardinality * (numValues - 1);
				}

				break;
		}

		return fLogScore;
	} // CalcNodeScore


	/**
	 * Calc Node Score With AddedParent
	 * 
	 * @param nNode node for which the score is calculate
	 * @param nCandidateParent candidate parent to add to the existing parent set
	 * @return log score
	 */
	public double calcScoreWithExtraParent(int nNode, int nCandidateParent) {
		ParentSet oParentSet = m_BayesNet.getParentSet(nNode);

		// sanity check: nCandidateParent should not be in parent set already
		if (oParentSet.contains(nCandidateParent)) {
				return -1e100;
		}

		// set up candidate parent
		oParentSet.addParent(nCandidateParent, m_BayesNet.m_Instances);

		// calculate the score
		double logScore = calcNodeScore(nNode);

		// delete temporarily added parent
		oParentSet.deleteLastParent(m_BayesNet.m_Instances);

		return logScore;
	} // CalcScoreWithExtraParent


	/**
	 * Calc Node Score With Parent Deleted
	 * 
	 * @param nNode node for which the score is calculate
	 * @param nCandidateParent candidate parent to delete from the existing parent set
	 * @return log score
	 */
	public double calcScoreWithMissingParent(int nNode, int nCandidateParent) {
		ParentSet oParentSet = m_BayesNet.getParentSet(nNode);

		// sanity check: nCandidateParent should be in parent set already
		if (!oParentSet.contains( nCandidateParent)) {
				return -1e100;
		}

		// set up candidate parent
		int iParent = oParentSet.deleteParent(nCandidateParent, m_BayesNet.m_Instances);

		// calculate the score
		double logScore = calcNodeScore(nNode);

		// restore temporarily deleted parent
		oParentSet.addParent(nCandidateParent, iParent, m_BayesNet.m_Instances);

		return logScore;
	} // CalcScoreWithMissingParent

	/**
	 * set quality measure to be used in searching for networks.
	 * 
	 * @param newScoreType the new score type
	 */
	public void setScoreType(SelectedTag newScoreType) {
		if (newScoreType.getTags() == TAGS_SCORE_TYPE) {
			m_nScoreType = newScoreType.getSelectedTag().getID();
		}
	}

	/**
	 * get quality measure to be used in searching for networks.
	 * @return quality measure
	 */
	public SelectedTag getScoreType() {
		return new SelectedTag(m_nScoreType, TAGS_SCORE_TYPE);
	}

	/**
	 * 
	 * @param bMarkovBlanketClassifier
	 */
	public void setMarkovBlanketClassifier(boolean bMarkovBlanketClassifier) {
	  super.setMarkovBlanketClassifier(bMarkovBlanketClassifier);
	}
	
	/**
	 * 
	 * @return
	 */
	public boolean getMarkovBlanketClassifier() {
	  return super.getMarkovBlanketClassifier();
	}

	/**
	 * 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(
		    "\tApplies a Markov Blanket correction to the network structure, \n"
		  + "\tafter a network structure is learned. This ensures that all \n"
		  + "\tnodes in the network are part of the Markov blanket of the \n"
		  + "\tclassifier node.",
		  "mbc", 0, "-mbc"));
      
		newVector.addElement(
			new Option(
				"\tScore type (BAYES, BDeu, MDL, ENTROPY and AIC)",
				"S",
				1,
				"-S [BAYES|MDL|ENTROPY|AIC|CROSS_CLASSIC|CROSS_BAYES]"));

		return newVector.elements();
	} // listOptions

	/**
	 * Parses a given list of options. <p/>
	 *
	 <!-- options-start -->
	 * Valid options are: <p/>
	 * 
	 * <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 {

	  	setMarkovBlanketClassifier(Utils.getFlag("mbc", options));

		String sScore = Utils.getOption('S', options);

		if (sScore.compareTo("BAYES") == 0) {
			setScoreType(new SelectedTag(Scoreable.BAYES, TAGS_SCORE_TYPE));
		}
		if (sScore.compareTo("BDeu") == 0) {
			setScoreType(new SelectedTag(Scoreable.BDeu, TAGS_SCORE_TYPE));
		}
		if (sScore.compareTo("MDL") == 0) {
			setScoreType(new SelectedTag(Scoreable.MDL, TAGS_SCORE_TYPE));
		}
		if (sScore.compareTo("ENTROPY") == 0) {
			setScoreType(new SelectedTag(Scoreable.ENTROPY, TAGS_SCORE_TYPE));
		}
		if (sScore.compareTo("AIC") == 0) {
			setScoreType(new SelectedTag(Scoreable.AIC, TAGS_SCORE_TYPE));
		}
	} // 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[3 + superOptions.length];
		int current = 0;

		if (getMarkovBlanketClassifier())
		  options[current++] = "-mbc";

		options[current++] = "-S";

		switch (m_nScoreType) {

			case (Scoreable.BAYES) :
				options[current++] = "BAYES";
				break;

			case (Scoreable.BDeu) :
				options[current++] = "BDeu";
				break;

			case (Scoreable.MDL) :
				options[current++] = "MDL";
				break;

			case (Scoreable.ENTROPY) :
				options[current++] = "ENTROPY";

				break;

			case (Scoreable.AIC) :
				options[current++] = "AIC";
				break;
		}

                // 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

	/**
	 * @return a string to describe the ScoreType option.
	 */
	public String scoreTypeTipText() {
		return "The score type determines the measure used to judge the quality of a"
			+ " network structure. It can be one of Bayes, BDeu, Minimum Description Length (MDL),"
			+ " Akaike Information Criterion (AIC), and Entropy.";
	}
	
	/**
	 * @return a string to describe the MarkovBlanketClassifier option.
	 */
	public String markovBlanketClassifierTipText() {
	  return super.markovBlanketClassifierTipText();
	}

	/**
	 * This will return a string describing the search algorithm.
	 * @return The string.
	 */
	public String globalInfo() {
	  return 
	      "The ScoreBasedSearchAlgorithm class supports Bayes net "
	    + "structure search algorithms that are based on maximizing "
	    + "scores (as opposed to for example conditional independence "
	    + "based search algorithms).";
	} // globalInfo
}