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: * LAGDHillClimber.java
019: * Copyright (C) 2005 Manuel Neubach
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.Option;
028: import weka.core.Utils;
029:
030: import java.util.Enumeration;
031: import java.util.Vector;
032:
033: /**
034: <!-- globalinfo-start -->
035: * This Bayes Network learning algorithm uses a Look Ahead Hill Climbing algorithm called LAGD Hill Climbing. Unlike Greedy Hill Climbing it doesn't calculate a best greedy operation (adding, deleting or reversing an arc) but a sequence of nrOfLookAheadSteps operations, which leads to a network structure whose score is most likely higher in comparison to the network obtained by performing a sequence of nrOfLookAheadSteps greedy operations. The search is not restricted by an order on the variables (unlike K2). The difference with B and B2 is that this hill climber also considers arrows part of the naive Bayes structure for deletion.
036: * <p/>
037: <!-- globalinfo-end -->
038: *
039: <!-- options-start -->
040: * Valid options are: <p/>
041: *
042: * <pre> -L <nr of look ahead steps>
043: * Look Ahead Depth</pre>
044: *
045: * <pre> -G <nr of good operations>
046: * Nr of Good Operations</pre>
047: *
048: * <pre> -P <nr of parents>
049: * Maximum number of parents</pre>
050: *
051: * <pre> -R
052: * Use arc reversal operation.
053: * (default false)</pre>
054: *
055: * <pre> -N
056: * Initial structure is empty (instead of Naive Bayes)</pre>
057: *
058: * <pre> -mbc
059: * Applies a Markov Blanket correction to the network structure,
060: * after a network structure is learned. This ensures that all
061: * nodes in the network are part of the Markov blanket of the
062: * classifier node.</pre>
063: *
064: * <pre> -S [BAYES|MDL|ENTROPY|AIC|CROSS_CLASSIC|CROSS_BAYES]
065: * Score type (BAYES, BDeu, MDL, ENTROPY and AIC)</pre>
066: *
067: <!-- options-end -->
068: *
069: * @author Manuel Neubach
070: * @version $Revision: 1.6 $
071: */
072: public class LAGDHillClimber extends HillClimber {
073:
074: /** for serialization */
075: static final long serialVersionUID = 7217437499439184344L;
076:
077: /** Number of Look Ahead Steps **/
078: int m_nNrOfLookAheadSteps = 2;
079:
080: /** Number of Good Operations per Step **/
081: int m_nNrOfGoodOperations = 5;
082:
083: /**
084: * search determines the network structure/graph of the network
085: *
086: * @param bayesNet the network
087: * @param instances the data to use
088: * @throws Exception if something goes wrong
089: */
090: protected void search(BayesNet bayesNet, Instances instances)
091: throws Exception {
092: int k = m_nNrOfLookAheadSteps; // Number of Look Ahead Steps
093: int l = m_nNrOfGoodOperations; // Number of Good Operations per step
094: lookAheadInGoodDirectionsSearch(bayesNet, instances, k, l);
095: } // search
096:
097: /**
098: * lookAheadInGoodDirectionsSearch determines the network structure/graph of the network
099: * with best score according to LAGD Hill Climbing
100: *
101: * @param bayesNet the network
102: * @param instances the data to use
103: * @param nrOfLookAheadSteps
104: * @param nrOfGoodOperations
105: * @throws Exception if something goes wrong
106: */
107: protected void lookAheadInGoodDirectionsSearch(BayesNet bayesNet,
108: Instances instances, int nrOfLookAheadSteps,
109: int nrOfGoodOperations) throws Exception {
110: System.out.println("Initializing Cache");
111: initCache(bayesNet, instances);
112:
113: while (nrOfLookAheadSteps > 1) {
114: System.out.println("Look Ahead Depth: "
115: + nrOfLookAheadSteps);
116: boolean legalSequence = true;
117: double sequenceDeltaScore = 0;
118: Operation[] bestOperation = new Operation[nrOfLookAheadSteps];
119:
120: bestOperation = getOptimalOperations(bayesNet, instances,
121: nrOfLookAheadSteps, nrOfGoodOperations);
122: for (int i = 0; i < nrOfLookAheadSteps; i++) {
123: if (bestOperation[i] == null) {
124: legalSequence = false;
125: } else {
126: sequenceDeltaScore += bestOperation[i].m_fDeltaScore;
127: }
128: }
129: while (legalSequence && sequenceDeltaScore > 0) {
130: System.out
131: .println("Next Iteration..........................");
132: for (int i = 0; i < nrOfLookAheadSteps; i++) {
133: performOperation(bayesNet, instances,
134: bestOperation[i]);
135: }
136: bestOperation = getOptimalOperations(bayesNet,
137: instances, nrOfLookAheadSteps,
138: nrOfGoodOperations);
139: sequenceDeltaScore = 0;
140: for (int i = 0; i < nrOfLookAheadSteps; i++) {
141: if (bestOperation[i] != null) {
142: System.out
143: .println(bestOperation[i].m_nOperation
144: + " "
145: + bestOperation[i].m_nHead
146: + " "
147: + bestOperation[i].m_nTail);
148: sequenceDeltaScore += bestOperation[i].m_fDeltaScore;
149: } else {
150: legalSequence = false;
151:
152: }
153: System.out.println("DeltaScore: "
154: + sequenceDeltaScore);
155: }
156: }
157: --nrOfLookAheadSteps;
158: }
159:
160: /** last steps with greedy HC **/
161: Operation oOperation = getOptimalOperation(bayesNet, instances);
162: while ((oOperation != null) && (oOperation.m_fDeltaScore > 0)) {
163: performOperation(bayesNet, instances, oOperation);
164: System.out.println("Performing last greedy steps");
165: oOperation = getOptimalOperation(bayesNet, instances);
166: }
167: // free up memory
168: m_Cache = null;
169: } // lookAheadInGoodDirectionsSearch
170:
171: /**
172: * getAntiOperation determines the Operation, which is needed to cancel oOperation
173: *
174: * @param oOperation Operation to cancel
175: * @return antiOperation to oOperation
176: * @throws Exception if something goes wrong
177: */
178: protected Operation getAntiOperation(Operation oOperation)
179: throws Exception {
180: if (oOperation.m_nOperation == Operation.OPERATION_ADD)
181: return (new Operation(oOperation.m_nTail,
182: oOperation.m_nHead, Operation.OPERATION_DEL));
183: else {
184: if (oOperation.m_nOperation == Operation.OPERATION_DEL)
185: return (new Operation(oOperation.m_nTail,
186: oOperation.m_nHead, Operation.OPERATION_ADD));
187: else {
188: return (new Operation(oOperation.m_nHead,
189: oOperation.m_nTail, Operation.OPERATION_REVERSE));
190: }
191: }
192: } // getAntiOperation
193:
194: /**
195: * getGoodOperations determines the nrOfGoodOperations best Operations, which are considered for
196: * the calculation of an optimal operationsequence
197: * @param bayesNet Bayes network to apply operation on
198: * @param instances data set to learn from
199: * @param nrOfGoodOperations number of good operations to consider
200: * @return good operations to consider
201: * @throws Exception if something goes wrong
202: **/
203: protected Operation[] getGoodOperations(BayesNet bayesNet,
204: Instances instances, int nrOfGoodOperations)
205: throws Exception {
206: Operation[] goodOperations = new Operation[nrOfGoodOperations];
207: for (int i = 0; i < nrOfGoodOperations; i++) {
208: goodOperations[i] = getOptimalOperation(bayesNet, instances);
209: if (goodOperations[i] != null) {
210: m_Cache.put(goodOperations[i], -1E100);
211: } else
212: i = nrOfGoodOperations;
213: }
214: for (int i = 0; i < nrOfGoodOperations; i++) {
215: if (goodOperations[i] != null) {
216: if (goodOperations[i].m_nOperation != Operation.OPERATION_REVERSE) {
217: m_Cache.put(goodOperations[i],
218: goodOperations[i].m_fDeltaScore);
219: } else {
220: m_Cache
221: .put(
222: goodOperations[i],
223: goodOperations[i].m_fDeltaScore
224: - m_Cache.m_fDeltaScoreAdd[goodOperations[i].m_nHead][goodOperations[i].m_nTail]);
225: }
226: } else
227: i = nrOfGoodOperations;
228: }
229: return goodOperations;
230: } // getGoodOperations
231:
232: /**
233: * getOptimalOperations determines an optimal operationsequence in respect of the parameters
234: * nrOfLookAheadSteps and nrOfGoodOperations
235: * @param bayesNet Bayes network to apply operation on
236: * @param instances data set to learn from
237: * @param nrOfLookAheadSteps number of lood ahead steps to use
238: * @param nrOfGoodOperations number of good operations to consider
239: * @return optimal sequence of operations in respect to nrOfLookAheadSteps and nrOfGoodOperations
240: * @throws Exception if something goes wrong
241: **/
242: protected Operation[] getOptimalOperations(BayesNet bayesNet,
243: Instances instances, int nrOfLookAheadSteps,
244: int nrOfGoodOperations) throws Exception {
245: if (nrOfLookAheadSteps == 1) { // Abbruch der Rekursion
246: Operation[] bestOperation = new Operation[1];
247: bestOperation[0] = getOptimalOperation(bayesNet, instances);
248: return (bestOperation); // Abbruch der Rekursion
249: } else {
250: double bestDeltaScore = 0;
251: double currentDeltaScore = 0;
252: Operation[] bestOperation = new Operation[nrOfLookAheadSteps];
253: Operation[] goodOperations = new Operation[nrOfGoodOperations];
254: Operation[] tempOperation = new Operation[nrOfLookAheadSteps - 1];
255: goodOperations = getGoodOperations(bayesNet, instances,
256: nrOfGoodOperations);
257: for (int i = 0; i < nrOfGoodOperations; i++) {
258: if (goodOperations[i] != null) {
259: performOperation(bayesNet, instances,
260: goodOperations[i]);
261: tempOperation = getOptimalOperations(bayesNet,
262: instances, nrOfLookAheadSteps - 1,
263: nrOfGoodOperations); // rekursiver Abstieg
264: currentDeltaScore = goodOperations[i].m_fDeltaScore;
265: for (int j = 0; j < nrOfLookAheadSteps - 1; j++) {
266: if (tempOperation[j] != null) {
267: currentDeltaScore += tempOperation[j].m_fDeltaScore;
268: }
269: }
270: performOperation(bayesNet, instances,
271: getAntiOperation(goodOperations[i]));
272: if (currentDeltaScore > bestDeltaScore) {
273: bestDeltaScore = currentDeltaScore;
274: bestOperation[0] = goodOperations[i];
275: for (int j = 1; j < nrOfLookAheadSteps; j++) {
276: bestOperation[j] = tempOperation[j - 1];
277: }
278: }
279: } else
280: i = nrOfGoodOperations;
281: }
282: return (bestOperation);
283: }
284: } // getOptimalOperations
285:
286: /**
287: * Sets the max number of parents
288: *
289: * @param nMaxNrOfParents the max number of parents
290: */
291: public void setMaxNrOfParents(int nMaxNrOfParents) {
292: m_nMaxNrOfParents = nMaxNrOfParents;
293: }
294:
295: /**
296: * Gets the max number of parents.
297: *
298: * @return the max number of parents
299: */
300: public int getMaxNrOfParents() {
301: return m_nMaxNrOfParents;
302: }
303:
304: /**
305: * Sets the number of look-ahead steps
306: *
307: * @param nNrOfLookAheadSteps the number of look-ahead steps
308: */
309: public void setNrOfLookAheadSteps(int nNrOfLookAheadSteps) {
310: m_nNrOfLookAheadSteps = nNrOfLookAheadSteps;
311: }
312:
313: /**
314: * Gets the number of look-ahead steps
315: *
316: * @return the number of look-ahead step
317: */
318: public int getNrOfLookAheadSteps() {
319: return m_nNrOfLookAheadSteps;
320: }
321:
322: /**
323: * Sets the number of "good operations"
324: *
325: * @param nNrOfGoodOperations the number of "good operations"
326: */
327: public void setNrOfGoodOperations(int nNrOfGoodOperations) {
328: m_nNrOfGoodOperations = nNrOfGoodOperations;
329: }
330:
331: /**
332: * Gets the number of "good operations"
333: *
334: * @return the number of "good operations"
335: */
336: public int getNrOfGoodOperations() {
337: return m_nNrOfGoodOperations;
338: }
339:
340: /**
341: * Returns an enumeration describing the available options.
342: *
343: * @return an enumeration of all the available options.
344: */
345: public Enumeration listOptions() {
346: Vector newVector = new Vector();
347:
348: newVector.addElement(new Option("\tLook Ahead Depth", "L", 2,
349: "-L <nr of look ahead steps>"));
350: newVector.addElement(new Option("\tNr of Good Operations", "G",
351: 5, "-G <nr of good operations>"));
352:
353: Enumeration enm = super .listOptions();
354: while (enm.hasMoreElements()) {
355: newVector.addElement(enm.nextElement());
356: }
357: return newVector.elements();
358: } // listOptions
359:
360: /**
361: * Parses a given list of options. Valid options are:<p>
362: *
363: <!-- options-start -->
364: * Valid options are: <p/>
365: *
366: * <pre> -L <nr of look ahead steps>
367: * Look Ahead Depth</pre>
368: *
369: * <pre> -G <nr of good operations>
370: * Nr of Good Operations</pre>
371: *
372: * <pre> -P <nr of parents>
373: * Maximum number of parents</pre>
374: *
375: * <pre> -R
376: * Use arc reversal operation.
377: * (default false)</pre>
378: *
379: * <pre> -N
380: * Initial structure is empty (instead of Naive Bayes)</pre>
381: *
382: * <pre> -mbc
383: * Applies a Markov Blanket correction to the network structure,
384: * after a network structure is learned. This ensures that all
385: * nodes in the network are part of the Markov blanket of the
386: * classifier node.</pre>
387: *
388: * <pre> -S [BAYES|MDL|ENTROPY|AIC|CROSS_CLASSIC|CROSS_BAYES]
389: * Score type (BAYES, BDeu, MDL, ENTROPY and AIC)</pre>
390: *
391: <!-- options-end -->
392: *
393: * @param options the list of options as an array of strings
394: * @throws Exception if an option is not supported
395: */
396: public void setOptions(String[] options) throws Exception {
397: String sNrOfLookAheadSteps = Utils.getOption('L', options);
398: if (sNrOfLookAheadSteps.length() != 0) {
399: setNrOfLookAheadSteps(Integer.parseInt(sNrOfLookAheadSteps));
400: } else {
401: setNrOfLookAheadSteps(2);
402: }
403:
404: String sNrOfGoodOperations = Utils.getOption('G', options);
405: if (sNrOfGoodOperations.length() != 0) {
406: setNrOfGoodOperations(Integer.parseInt(sNrOfGoodOperations));
407: } else {
408: setNrOfGoodOperations(5);
409: }
410:
411: super .setOptions(options);
412: } // setOptions
413:
414: /**
415: * Gets the current settings of the search algorithm.
416: *
417: * @return an array of strings suitable for passing to setOptions
418: */
419: public String[] getOptions() {
420: String[] super Options = super .getOptions();
421: String[] options = new String[9 + super Options.length];
422: int current = 0;
423:
424: options[current++] = "-L";
425: options[current++] = "" + m_nNrOfLookAheadSteps;
426:
427: options[current++] = "-G";
428: options[current++] = "" + m_nNrOfGoodOperations;
429:
430: // insert options from parent class
431: for (int iOption = 0; iOption < super Options.length; iOption++) {
432: options[current++] = super Options[iOption];
433: }
434:
435: // Fill up rest with empty strings, not nulls!
436: while (current < options.length) {
437: options[current++] = "";
438: }
439: return options;
440: } // getOptions
441:
442: /**
443: * This will return a string describing the search algorithm.
444: * @return The string.
445: */
446: public String globalInfo() {
447: return "This Bayes Network learning algorithm uses a Look Ahead Hill Climbing algorithm called LAGD Hill Climbing."
448: + " Unlike Greedy Hill Climbing it doesn't calculate a best greedy operation (adding, deleting or reversing an arc) "
449: + "but a sequence of nrOfLookAheadSteps operations, which leads to a network structure whose score is most likely "
450: + "higher in comparison to the network obtained by performing a sequence of nrOfLookAheadSteps greedy operations. "
451: + "The search is not restricted by an order "
452: + "on the variables (unlike K2). The difference with B and B2 is that this hill "
453: + "climber also considers arrows part of the naive Bayes structure for deletion.";
454: } // globalInfo
455:
456: /**
457: * @return a string to describe the Number of Look Ahead Steps option.
458: */
459: public String nrOfLookAheadStepsTipText() {
460: return "Sets the Number of Look Ahead Steps. 'nrOfLookAheadSteps = 2' means that all network structures in a "
461: + "distance of 2 (from the current network structure) are taken into account for the decision which arcs to add, "
462: + "remove or reverse. 'nrOfLookAheadSteps = 1' results in Greedy Hill Climbing.";
463: } // nrOfLookAheadStepsTipText
464:
465: /**
466: * @return a string to describe the Number of Good Operations option.
467: */
468: public String nrOfGoodOperationsTipText() {
469: return "Sets the Number of Good Operations per Look Ahead Step. 'nrOfGoodOperations = 5' means that for the next "
470: + "Look Ahead Step only the 5 best Operations (adding, deleting or reversing an arc) are taken into account for the "
471: + "calculation of the best sequence consisting of nrOfLookAheadSteps operations.";
472: } // nrOfGoodOperationsTipText
473:
474: } // LAGDHillClimber
|