content: /*
   * This program is free software; you can redistribute it and/or modify
   * it under the terms of the GNU General Public License as published by
   * the Free Software Foundation; either version 2 of the License, or
   * (at your option) any later version.
   * 
   * This program is distributed in the hope that it will be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   * GNU General Public License for more details.
   * 
   * You should have received a copy of the GNU General Public License
   * along with this program; if not, write to the Free Software
   * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
   */
  
  /*
   * CISearchAlgorithm.java
   * Copyright (C) 2004 University of Waikato, Hamilton, New Zealand
   * 
   */
  
  package weka.classifiers.bayes.net.search.ci;
  
  import weka.classifiers.bayes.BayesNet;
  import weka.classifiers.bayes.net.ParentSet;
  import weka.classifiers.bayes.net.search.local.LocalScoreSearchAlgorithm;
  import weka.core.Instances;
  import weka.core.RevisionUtils;
  
  /** 
   <!-- globalinfo-start -->
   * The CISearchAlgorithm class supports Bayes net structure search algorithms that are based on conditional independence test (as opposed to for example score based of cross validation based search algorithms).
   * <p/>
   <!-- globalinfo-end -->
   *
   <!-- 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 -->
   *
   * @author Remco Bouckaert (rrb@xm.co.nz)
   * @version $Revision: 1.7 $
   */
  public class CISearchAlgorithm 
  	extends LocalScoreSearchAlgorithm {
    	
    	/** for serialization */
    	static final long serialVersionUID = 3165802334119704560L;
    	
  	BayesNet  m_BayesNet;
  	Instances m_instances;
  	    
  	/**
  	 * Returns a string describing this object
  	 * @return a description of the classifier suitable for
  	 * displaying in the explorer/experimenter gui
  	 */
  	public String globalInfo() {
  	  return 
  	      "The CISearchAlgorithm class supports Bayes net structure "
  	    + "search algorithms that are based on conditional independence "
  	    + "test (as opposed to for example score based of cross validation "
  	    + "based search algorithms).";
  	}
  
  	/** IsConditionalIndependent tests whether two nodes X and Y are independent
  	 *  given a set of variables Z. The test compares the score of the Bayes network
  	 * with and without arrow Y->X where all nodes in Z are parents of X.
  	 * @param iAttributeX - index of attribute representing variable X
  	 * @param iAttributeY - index of attribute representing variable Y
   	 * @param iAttributesZ - array of integers representing indices of attributes in set Z
   	 * @param nAttributesZ - cardinality of Z
   	 * @return true if X and Y conditionally independent given Z 
  	 */
  	protected boolean isConditionalIndependent(
  		int iAttributeX, 
  		int iAttributeY, 
  		int [] iAttributesZ, 
  		int nAttributesZ) {
  		ParentSet oParentSetX = m_BayesNet.getParentSet(iAttributeX);
  		// clear parent set of AttributeX
  		while (oParentSetX.getNrOfParents() > 0) {
  			oParentSetX.deleteLastParent(m_instances);
  		}
  		
  		// insert parents in iAttributeZ
  		for (int iAttributeZ = 0; iAttributeZ < nAttributesZ; iAttributeZ++) {
  			oParentSetX.addParent( iAttributesZ[iAttributeZ], m_instances);
  		}
  		
  		double fScoreZ = calcNodeScore(iAttributeX);
  		double fScoreZY = calcScoreWithExtraParent(iAttributeX, iAttributeY);
  		if (fScoreZY <= fScoreZ) {
  			// the score does not improve by adding Y to the parent set of X
  			// so we conclude that nodes X and Y are conditionally independent
  			// given the set of variables Z
  			return true;
  		}
  		return false;
  	} // IsConditionalIndependent
  
  	/**
  	 * Returns the revision string.
  	 * 
  	 * @return		the revision
  	 */
  	public String getRevision() {
  	  return RevisionUtils.extract("$Revision: 1.7 $");
  	}
  } // class CISearchAlgorithm
  