001: /*
002: * This program is free software; you can redistribute it and/or modify
003: * it under the terms of the GNU General Public License as published by
004: * the Free Software Foundation; either version 2 of the License, or
005: * (at your option) any later version.
006: *
007: * This program is distributed in the hope that it will be useful,
008: * but WITHOUT ANY WARRANTY; without even the implied warranty of
009: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
010: * GNU General Public License for more details.
011: *
012: * You should have received a copy of the GNU General Public License
013: * along with this program; if not, write to the Free Software
014: * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
015: */
016:
017: /*
018: * CISearchAlgorithm.java
019: * Copyright (C) 2004 University of Waikato, Hamilton, New Zealand
020: *
021: */
022:
023: package weka.classifiers.bayes.net.search.ci;
024:
025: import weka.classifiers.bayes.BayesNet;
026: import weka.classifiers.bayes.net.ParentSet;
027: import weka.classifiers.bayes.net.search.local.LocalScoreSearchAlgorithm;
028: import weka.core.Instances;
029:
030: /**
031: <!-- globalinfo-start -->
032: * 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).
033: * <p/>
034: <!-- globalinfo-end -->
035: *
036: <!-- options-start -->
037: * Valid options are: <p/>
038: *
039: * <pre> -mbc
040: * Applies a Markov Blanket correction to the network structure,
041: * after a network structure is learned. This ensures that all
042: * nodes in the network are part of the Markov blanket of the
043: * classifier node.</pre>
044: *
045: * <pre> -S [BAYES|MDL|ENTROPY|AIC|CROSS_CLASSIC|CROSS_BAYES]
046: * Score type (BAYES, BDeu, MDL, ENTROPY and AIC)</pre>
047: *
048: <!-- options-end -->
049: *
050: * @author Remco Bouckaert (rrb@xm.co.nz)
051: * @version $Revision: 1.6 $
052: */
053: public class CISearchAlgorithm extends LocalScoreSearchAlgorithm {
054:
055: /** for serialization */
056: static final long serialVersionUID = 3165802334119704560L;
057:
058: BayesNet m_BayesNet;
059: Instances m_instances;
060:
061: /**
062: * Returns a string describing this object
063: * @return a description of the classifier suitable for
064: * displaying in the explorer/experimenter gui
065: */
066: public String globalInfo() {
067: return "The CISearchAlgorithm class supports Bayes net structure "
068: + "search algorithms that are based on conditional independence "
069: + "test (as opposed to for example score based of cross validation "
070: + "based search algorithms).";
071: }
072:
073: /** IsConditionalIndependent tests whether two nodes X and Y are independent
074: * given a set of variables Z. The test compares the score of the Bayes network
075: * with and without arrow Y->X where all nodes in Z are parents of X.
076: * @param iAttributeX - index of attribute representing variable X
077: * @param iAttributeY - index of attribute representing variable Y
078: * @param iAttributesZ - array of integers representing indices of attributes in set Z
079: * @param nAttributesZ - cardinality of Z
080: * @return true if X and Y conditionally independent given Z
081: */
082: protected boolean isConditionalIndependent(int iAttributeX,
083: int iAttributeY, int[] iAttributesZ, int nAttributesZ) {
084: ParentSet oParentSetX = m_BayesNet.getParentSet(iAttributeX);
085: // clear parent set of AttributeX
086: while (oParentSetX.getNrOfParents() > 0) {
087: oParentSetX.deleteLastParent(m_instances);
088: }
089:
090: // insert parents in iAttributeZ
091: for (int iAttributeZ = 0; iAttributeZ < nAttributesZ; iAttributeZ++) {
092: oParentSetX.addParent(iAttributesZ[iAttributeZ],
093: m_instances);
094: }
095:
096: double fScoreZ = calcNodeScore(iAttributeX);
097: double fScoreZY = calcScoreWithExtraParent(iAttributeX,
098: iAttributeY);
099: if (fScoreZY <= fScoreZ) {
100: // the score does not improve by adding Y to the parent set of X
101: // so we conclude that nodes X and Y are conditionally independent
102: // given the set of variables Z
103: return true;
104: }
105: return false;
106: } // IsConditionalIndependent
107:
108: } // class CISearchAlgorithm
|