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: * K2.java
019: * Copyright (C) 2001 University of Waikato, Hamilton, New Zealand
020: *
021: */
022: package weka.classifiers.bayes.net.search.local;
023:
024: import weka.classifiers.bayes.BayesNet;
025: import weka.core.Instances;
026: import weka.core.Option;
027: import weka.core.TechnicalInformation;
028: import weka.core.TechnicalInformation.Type;
029: import weka.core.TechnicalInformation.Field;
030: import weka.core.TechnicalInformationHandler;
031: import weka.core.Utils;
032:
033: import java.util.Enumeration;
034: import java.util.Random;
035: import java.util.Vector;
036:
037: /**
038: <!-- globalinfo-start -->
039: * This Bayes Network learning algorithm uses a hill climbing algorithm restricted by an order on the variables.<br/>
040: * <br/>
041: * For more information see:<br/>
042: * <br/>
043: * G.F. Cooper, E. Herskovits (1990). A Bayesian method for constructing Bayesian belief networks from databases.<br/>
044: * <br/>
045: * G. Cooper, E. Herskovits (1992). A Bayesian method for the induction of probabilistic networks from data. Machine Learning. 9(4):309-347.<br/>
046: * <br/>
047: * Works with nominal variables and no missing values only.
048: * <p/>
049: <!-- globalinfo-end -->
050: *
051: <!-- technical-bibtex-start -->
052: * BibTeX:
053: * <pre>
054: * @proceedings{Cooper1990,
055: * author = {G.F. Cooper and E. Herskovits},
056: * booktitle = {Proceedings of the Conference on Uncertainty in AI},
057: * pages = {86-94},
058: * title = {A Bayesian method for constructing Bayesian belief networks from databases},
059: * year = {1990}
060: * }
061: *
062: * @article{Cooper1992,
063: * author = {G. Cooper and E. Herskovits},
064: * journal = {Machine Learning},
065: * number = {4},
066: * pages = {309-347},
067: * title = {A Bayesian method for the induction of probabilistic networks from data},
068: * volume = {9},
069: * year = {1992}
070: * }
071: * </pre>
072: * <p/>
073: <!-- technical-bibtex-end -->
074: *
075: <!-- options-start -->
076: * Valid options are: <p/>
077: *
078: * <pre> -N
079: * Initial structure is empty (instead of Naive Bayes)</pre>
080: *
081: * <pre> -P <nr of parents>
082: * Maximum number of parents</pre>
083: *
084: * <pre> -R
085: * Random order.
086: * (default false)</pre>
087: *
088: * <pre> -mbc
089: * Applies a Markov Blanket correction to the network structure,
090: * after a network structure is learned. This ensures that all
091: * nodes in the network are part of the Markov blanket of the
092: * classifier node.</pre>
093: *
094: * <pre> -S [BAYES|MDL|ENTROPY|AIC|CROSS_CLASSIC|CROSS_BAYES]
095: * Score type (BAYES, BDeu, MDL, ENTROPY and AIC)</pre>
096: *
097: <!-- options-end -->
098: *
099: * @author Remco Bouckaert (rrb@xm.co.nz)
100: * @version $Revision: 1.6 $
101: */
102: public class K2 extends LocalScoreSearchAlgorithm implements
103: TechnicalInformationHandler {
104:
105: /** for serialization */
106: static final long serialVersionUID = 6176545934752116631L;
107:
108: /** Holds flag to indicate ordering should be random **/
109: boolean m_bRandomOrder = false;
110:
111: /**
112: * Returns an instance of a TechnicalInformation object, containing
113: * detailed information about the technical background of this class,
114: * e.g., paper reference or book this class is based on.
115: *
116: * @return the technical information about this class
117: */
118: public TechnicalInformation getTechnicalInformation() {
119: TechnicalInformation result;
120: TechnicalInformation additional;
121:
122: result = new TechnicalInformation(Type.PROCEEDINGS);
123: result.setValue(Field.AUTHOR, "G.F. Cooper and E. Herskovits");
124: result.setValue(Field.YEAR, "1990");
125: result
126: .setValue(Field.TITLE,
127: "A Bayesian method for constructing Bayesian belief networks from databases");
128: result.setValue(Field.BOOKTITLE,
129: "Proceedings of the Conference on Uncertainty in AI");
130: result.setValue(Field.PAGES, "86-94");
131:
132: additional = result.add(Type.ARTICLE);
133: additional
134: .setValue(Field.AUTHOR, "G. Cooper and E. Herskovits");
135: additional.setValue(Field.YEAR, "1992");
136: additional
137: .setValue(Field.TITLE,
138: "A Bayesian method for the induction of probabilistic networks from data");
139: additional.setValue(Field.JOURNAL, "Machine Learning");
140: additional.setValue(Field.VOLUME, "9");
141: additional.setValue(Field.NUMBER, "4");
142: additional.setValue(Field.PAGES, "309-347");
143:
144: return result;
145: }
146:
147: /**
148: * buildStructure determines the network structure/graph of the network
149: * with the K2 algorithm, restricted by its initial structure (which can
150: * be an empty graph, or a Naive Bayes graph.
151: *
152: * @param bayesNet the network
153: * @param instances the data to work with
154: * @throws Exception if something goes wrong
155: */
156: public void buildStructure(BayesNet bayesNet, Instances instances)
157: throws Exception {
158: super .buildStructure(bayesNet, instances);
159: int nOrder[] = new int[instances.numAttributes()];
160: nOrder[0] = instances.classIndex();
161:
162: int nAttribute = 0;
163:
164: for (int iOrder = 1; iOrder < instances.numAttributes(); iOrder++) {
165: if (nAttribute == instances.classIndex()) {
166: nAttribute++;
167: }
168: nOrder[iOrder] = nAttribute++;
169: }
170:
171: if (m_bRandomOrder) {
172: // generate random ordering (if required)
173: Random random = new Random();
174: int iClass;
175: if (getInitAsNaiveBayes()) {
176: iClass = 0;
177: } else {
178: iClass = -1;
179: }
180: for (int iOrder = 0; iOrder < instances.numAttributes(); iOrder++) {
181: int iOrder2 = Math.abs(random.nextInt())
182: % instances.numAttributes();
183: if (iOrder != iClass && iOrder2 != iClass) {
184: int nTmp = nOrder[iOrder];
185: nOrder[iOrder] = nOrder[iOrder2];
186: nOrder[iOrder2] = nTmp;
187: }
188: }
189: }
190:
191: // determine base scores
192: double[] fBaseScores = new double[instances.numAttributes()];
193: for (int iOrder = 0; iOrder < instances.numAttributes(); iOrder++) {
194: int iAttribute = nOrder[iOrder];
195: fBaseScores[iAttribute] = calcNodeScore(iAttribute);
196: }
197:
198: // K2 algorithm: greedy search restricted by ordering
199: for (int iOrder = 1; iOrder < instances.numAttributes(); iOrder++) {
200: int iAttribute = nOrder[iOrder];
201: double fBestScore = fBaseScores[iAttribute];
202:
203: boolean bProgress = (bayesNet.getParentSet(iAttribute)
204: .getNrOfParents() < getMaxNrOfParents());
205: while (bProgress) {
206: int nBestAttribute = -1;
207: for (int iOrder2 = 0; iOrder2 < iOrder; iOrder2++) {
208: int iAttribute2 = nOrder[iOrder2];
209: double fScore = calcScoreWithExtraParent(
210: iAttribute, iAttribute2);
211: if (fScore > fBestScore) {
212: fBestScore = fScore;
213: nBestAttribute = iAttribute2;
214: }
215: }
216: if (nBestAttribute != -1) {
217: bayesNet.getParentSet(iAttribute).addParent(
218: nBestAttribute, instances);
219: fBaseScores[iAttribute] = fBestScore;
220: bProgress = (bayesNet.getParentSet(iAttribute)
221: .getNrOfParents() < getMaxNrOfParents());
222: } else {
223: bProgress = false;
224: }
225: }
226: }
227: } // buildStructure
228:
229: /**
230: * Sets the max number of parents
231: *
232: * @param nMaxNrOfParents the max number of parents
233: */
234: public void setMaxNrOfParents(int nMaxNrOfParents) {
235: m_nMaxNrOfParents = nMaxNrOfParents;
236: }
237:
238: /**
239: * Gets the max number of parents.
240: *
241: * @return the max number of parents
242: */
243: public int getMaxNrOfParents() {
244: return m_nMaxNrOfParents;
245: }
246:
247: /**
248: * Sets whether to init as naive bayes
249: *
250: * @param bInitAsNaiveBayes whether to init as naive bayes
251: */
252: public void setInitAsNaiveBayes(boolean bInitAsNaiveBayes) {
253: m_bInitAsNaiveBayes = bInitAsNaiveBayes;
254: }
255:
256: /**
257: * Gets whether to init as naive bayes
258: *
259: * @return whether to init as naive bayes
260: */
261: public boolean getInitAsNaiveBayes() {
262: return m_bInitAsNaiveBayes;
263: }
264:
265: /**
266: * Set random order flag
267: *
268: * @param bRandomOrder the random order flag
269: */
270: public void setRandomOrder(boolean bRandomOrder) {
271: m_bRandomOrder = bRandomOrder;
272: } // SetRandomOrder
273:
274: /**
275: * Get random order flag
276: *
277: * @return the random order flag
278: */
279: public boolean getRandomOrder() {
280: return m_bRandomOrder;
281: } // getRandomOrder
282:
283: /**
284: * Returns an enumeration describing the available options.
285: *
286: * @return an enumeration of all the available options.
287: */
288: public Enumeration listOptions() {
289: Vector newVector = new Vector(0);
290:
291: newVector
292: .addElement(new Option(
293: "\tInitial structure is empty (instead of Naive Bayes)",
294: "N", 0, "-N"));
295:
296: newVector.addElement(new Option("\tMaximum number of parents",
297: "P", 1, "-P <nr of parents>"));
298:
299: newVector.addElement(new Option("\tRandom order.\n"
300: + "\t(default false)", "R", 0, "-R"));
301:
302: Enumeration enu = super .listOptions();
303: while (enu.hasMoreElements()) {
304: newVector.addElement(enu.nextElement());
305: }
306: return newVector.elements();
307: }
308:
309: /**
310: * Parses a given list of options. <p/>
311: *
312: <!-- options-start -->
313: * Valid options are: <p/>
314: *
315: * <pre> -N
316: * Initial structure is empty (instead of Naive Bayes)</pre>
317: *
318: * <pre> -P <nr of parents>
319: * Maximum number of parents</pre>
320: *
321: * <pre> -R
322: * Random order.
323: * (default false)</pre>
324: *
325: * <pre> -mbc
326: * Applies a Markov Blanket correction to the network structure,
327: * after a network structure is learned. This ensures that all
328: * nodes in the network are part of the Markov blanket of the
329: * classifier node.</pre>
330: *
331: * <pre> -S [BAYES|MDL|ENTROPY|AIC|CROSS_CLASSIC|CROSS_BAYES]
332: * Score type (BAYES, BDeu, MDL, ENTROPY and AIC)</pre>
333: *
334: <!-- options-end -->
335: *
336: * @param options the list of options as an array of strings
337: * @throws Exception if an option is not supported
338: */
339: public void setOptions(String[] options) throws Exception {
340:
341: setRandomOrder(Utils.getFlag('R', options));
342:
343: m_bInitAsNaiveBayes = !(Utils.getFlag('N', options));
344:
345: String sMaxNrOfParents = Utils.getOption('P', options);
346:
347: if (sMaxNrOfParents.length() != 0) {
348: setMaxNrOfParents(Integer.parseInt(sMaxNrOfParents));
349: } else {
350: setMaxNrOfParents(100000);
351: }
352: super .setOptions(options);
353: }
354:
355: /**
356: * Gets the current settings of the search algorithm.
357: *
358: * @return an array of strings suitable for passing to setOptions
359: */
360: public String[] getOptions() {
361: String[] super Options = super .getOptions();
362: String[] options = new String[4 + super Options.length];
363: int current = 0;
364: options[current++] = "-P";
365: options[current++] = "" + m_nMaxNrOfParents;
366: if (!m_bInitAsNaiveBayes) {
367: options[current++] = "-N";
368: }
369: if (getRandomOrder()) {
370: options[current++] = "-R";
371: }
372:
373: // insert options from parent class
374: for (int iOption = 0; iOption < super Options.length; iOption++) {
375: options[current++] = super Options[iOption];
376: }
377:
378: while (current < options.length) {
379: options[current++] = "";
380: }
381: // Fill up rest with empty strings, not nulls!
382: return options;
383: }
384:
385: /**
386: * This will return a string describing the search algorithm.
387: * @return The string.
388: */
389: public String globalInfo() {
390: return "This Bayes Network learning algorithm uses a hill climbing algorithm "
391: + "restricted by an order on the variables.\n\n"
392: + "For more information see:\n\n"
393: + getTechnicalInformation().toString()
394: + "\n\n"
395: + "Works with nominal variables and no missing values only.";
396: }
397:
398: /**
399: * @return a string to describe the RandomOrder option.
400: */
401: public String randomOrderTipText() {
402: return "When set to true, the order of the nodes in the network is random."
403: + " Default random order is false and the order"
404: + " of the nodes in the dataset is used."
405: + " In any case, when the network was initialized as Naive Bayes Network, the"
406: + " class variable is first in the ordering though.";
407: } // randomOrderTipText
408: }
|