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: * TAN.java
019: * Copyright (C) 2004 University of Waikato, Hamilton, New Zealand
020: *
021: */
022:
023: package weka.classifiers.bayes.net.search.local;
024:
025: import weka.classifiers.bayes.BayesNet;
026: import weka.core.Instances;
027: import weka.core.TechnicalInformation;
028: import weka.core.TechnicalInformation.Type;
029: import weka.core.TechnicalInformation.Field;
030: import weka.core.TechnicalInformationHandler;
031:
032: import java.util.Enumeration;
033:
034: /**
035: <!-- globalinfo-start -->
036: * This Bayes Network learning algorithm determines the maximum weight spanning tree and returns a Naive Bayes network augmented with a tree.<br/>
037: * <br/>
038: * For more information see:<br/>
039: * <br/>
040: * N. Friedman, D. Geiger, M. Goldszmidt (1997). Bayesian network classifiers. Machine Learning. 29(2-3):131-163.
041: * <p/>
042: <!-- globalinfo-end -->
043: *
044: <!-- technical-bibtex-start -->
045: * BibTeX:
046: * <pre>
047: * @article{Friedman1997,
048: * author = {N. Friedman and D. Geiger and M. Goldszmidt},
049: * journal = {Machine Learning},
050: * number = {2-3},
051: * pages = {131-163},
052: * title = {Bayesian network classifiers},
053: * volume = {29},
054: * year = {1997}
055: * }
056: * </pre>
057: * <p/>
058: <!-- technical-bibtex-end -->
059: *
060: <!-- options-start -->
061: * Valid options are: <p/>
062: *
063: * <pre> -mbc
064: * Applies a Markov Blanket correction to the network structure,
065: * after a network structure is learned. This ensures that all
066: * nodes in the network are part of the Markov blanket of the
067: * classifier node.</pre>
068: *
069: * <pre> -S [BAYES|MDL|ENTROPY|AIC|CROSS_CLASSIC|CROSS_BAYES]
070: * Score type (BAYES, BDeu, MDL, ENTROPY and AIC)</pre>
071: *
072: <!-- options-end -->
073: *
074: * @author Remco Bouckaert
075: * @version $Revision: 1.6 $
076: */
077: public class TAN extends LocalScoreSearchAlgorithm implements
078: TechnicalInformationHandler {
079:
080: /** for serialization */
081: static final long serialVersionUID = 965182127977228690L;
082:
083: /**
084: * Returns an instance of a TechnicalInformation object, containing
085: * detailed information about the technical background of this class,
086: * e.g., paper reference or book this class is based on.
087: *
088: * @return the technical information about this class
089: */
090: public TechnicalInformation getTechnicalInformation() {
091: TechnicalInformation result;
092:
093: result = new TechnicalInformation(Type.ARTICLE);
094: result.setValue(Field.AUTHOR,
095: "N. Friedman and D. Geiger and M. Goldszmidt");
096: result.setValue(Field.YEAR, "1997");
097: result.setValue(Field.TITLE, "Bayesian network classifiers");
098: result.setValue(Field.JOURNAL, "Machine Learning");
099: result.setValue(Field.VOLUME, "29");
100: result.setValue(Field.NUMBER, "2-3");
101: result.setValue(Field.PAGES, "131-163");
102:
103: return result;
104: }
105:
106: /**
107: * buildStructure determines the network structure/graph of the network
108: * using the maximimum weight spanning tree algorithm of Chow and Liu
109: *
110: * @param bayesNet the network
111: * @param instances the data to use
112: * @throws Exception if something goes wrong
113: */
114: public void buildStructure(BayesNet bayesNet, Instances instances)
115: throws Exception {
116:
117: m_bInitAsNaiveBayes = true;
118: m_nMaxNrOfParents = 2;
119: super .buildStructure(bayesNet, instances);
120: int nNrOfAtts = instances.numAttributes();
121:
122: // determine base scores
123: double[] fBaseScores = new double[instances.numAttributes()];
124:
125: for (int iAttribute = 0; iAttribute < nNrOfAtts; iAttribute++) {
126: fBaseScores[iAttribute] = calcNodeScore(iAttribute);
127: }
128:
129: // // cache scores & whether adding an arc makes sense
130: double[][] fScore = new double[nNrOfAtts][nNrOfAtts];
131:
132: for (int iAttributeHead = 0; iAttributeHead < nNrOfAtts; iAttributeHead++) {
133: for (int iAttributeTail = 0; iAttributeTail < nNrOfAtts; iAttributeTail++) {
134: if (iAttributeHead != iAttributeTail) {
135: fScore[iAttributeHead][iAttributeTail] = calcScoreWithExtraParent(
136: iAttributeHead, iAttributeTail);
137: }
138: }
139: }
140:
141: // TAN greedy search (not restricted by ordering like K2)
142: // 1. find strongest link
143: // 2. find remaining links by adding strongest link to already
144: // connected nodes
145: // 3. assign direction to links
146: int nClassNode = instances.classIndex();
147: int[] link1 = new int[nNrOfAtts - 1];
148: int[] link2 = new int[nNrOfAtts - 1];
149: boolean[] linked = new boolean[nNrOfAtts];
150:
151: // 1. find strongest link
152: int nBestLinkNode1 = -1;
153: int nBestLinkNode2 = -1;
154: double fBestDeltaScore = 0.0;
155: int iLinkNode1;
156: for (iLinkNode1 = 0; iLinkNode1 < nNrOfAtts; iLinkNode1++) {
157: if (iLinkNode1 != nClassNode) {
158: for (int iLinkNode2 = 0; iLinkNode2 < nNrOfAtts; iLinkNode2++) {
159: if ((iLinkNode1 != iLinkNode2)
160: && (iLinkNode2 != nClassNode)
161: && ((nBestLinkNode1 == -1) || (fScore[iLinkNode1][iLinkNode2]
162: - fBaseScores[iLinkNode1] > fBestDeltaScore))) {
163: fBestDeltaScore = fScore[iLinkNode1][iLinkNode2]
164: - fBaseScores[iLinkNode1];
165: nBestLinkNode1 = iLinkNode2;
166: nBestLinkNode2 = iLinkNode1;
167: }
168: }
169: }
170: }
171: link1[0] = nBestLinkNode1;
172: link2[0] = nBestLinkNode2;
173: linked[nBestLinkNode1] = true;
174: linked[nBestLinkNode2] = true;
175:
176: // 2. find remaining links by adding strongest link to already
177: // connected nodes
178: for (int iLink = 1; iLink < nNrOfAtts - 2; iLink++) {
179: nBestLinkNode1 = -1;
180: for (iLinkNode1 = 0; iLinkNode1 < nNrOfAtts; iLinkNode1++) {
181: if (iLinkNode1 != nClassNode) {
182: for (int iLinkNode2 = 0; iLinkNode2 < nNrOfAtts; iLinkNode2++) {
183: if ((iLinkNode1 != iLinkNode2)
184: && (iLinkNode2 != nClassNode)
185: && (linked[iLinkNode1] || linked[iLinkNode2])
186: && (!linked[iLinkNode1] || !linked[iLinkNode2])
187: && ((nBestLinkNode1 == -1) || (fScore[iLinkNode1][iLinkNode2]
188: - fBaseScores[iLinkNode1] > fBestDeltaScore))) {
189: fBestDeltaScore = fScore[iLinkNode1][iLinkNode2]
190: - fBaseScores[iLinkNode1];
191: nBestLinkNode1 = iLinkNode2;
192: nBestLinkNode2 = iLinkNode1;
193: }
194: }
195: }
196: }
197:
198: link1[iLink] = nBestLinkNode1;
199: link2[iLink] = nBestLinkNode2;
200: linked[nBestLinkNode1] = true;
201: linked[nBestLinkNode2] = true;
202: }
203:
204: // 3. assign direction to links
205: boolean[] hasParent = new boolean[nNrOfAtts];
206: for (int iLink = 0; iLink < nNrOfAtts - 2; iLink++) {
207: if (!hasParent[link1[iLink]]) {
208: bayesNet.getParentSet(link1[iLink]).addParent(
209: link2[iLink], instances);
210: hasParent[link1[iLink]] = true;
211: } else {
212: if (hasParent[link2[iLink]]) {
213: throw new Exception(
214: "Bug condition found: too many arrows");
215: }
216: bayesNet.getParentSet(link2[iLink]).addParent(
217: link1[iLink], instances);
218: hasParent[link2[iLink]] = true;
219: }
220: }
221:
222: } // buildStructure
223:
224: /**
225: * Returns an enumeration describing the available options.
226: *
227: * @return an enumeration of all the available options.
228: */
229: public Enumeration listOptions() {
230: return super .listOptions();
231: } // listOption
232:
233: /**
234: * Parses a given list of options. <p/>
235: *
236: <!-- options-start -->
237: * Valid options are: <p/>
238: *
239: * <pre> -mbc
240: * Applies a Markov Blanket correction to the network structure,
241: * after a network structure is learned. This ensures that all
242: * nodes in the network are part of the Markov blanket of the
243: * classifier node.</pre>
244: *
245: * <pre> -S [BAYES|MDL|ENTROPY|AIC|CROSS_CLASSIC|CROSS_BAYES]
246: * Score type (BAYES, BDeu, MDL, ENTROPY and AIC)</pre>
247: *
248: <!-- options-end -->
249: *
250: * @param options the list of options as an array of strings
251: * @throws Exception if an option is not supported
252: */
253: public void setOptions(String[] options) throws Exception {
254: super .setOptions(options);
255: } // setOptions
256:
257: /**
258: * Gets the current settings of the Classifier.
259: *
260: * @return an array of strings suitable for passing to setOptions
261: */
262: public String[] getOptions() {
263: return super .getOptions();
264: } // getOptions
265:
266: /**
267: * This will return a string describing the classifier.
268: * @return The string.
269: */
270: public String globalInfo() {
271: return "This Bayes Network learning algorithm determines the maximum weight spanning tree "
272: + " and returns a Naive Bayes network augmented with a tree.\n\n"
273: + "For more information see:\n\n"
274: + getTechnicalInformation().toString();
275: } // globalInfo
276:
277: } // TAN
|