← Back to branch summary

~ubuntu-branches/ubuntu/trusty/weka/trusty-proposed

« back to all changes in this revision

Viewing changes to weka/classifiers/bayes/net/search/global/K2.java

  • Committer: Bazaar Package Importer
  • Author(s): Soeren Sonnenburg
  • Date: 2008-02-24 09:18:45 UTC
  • Revision ID: james.westby@ubuntu.com-20080224091845-1l8zy6fm6xipbzsr
Tags: upstream-3.5.7+tut1
Import upstream version 3.5.7+tut1

Show diffs side-by-side

added added

removed removed

Lines of Context:
weka/classifiers/bayes/net/search/global/K2.java
 
1
/*
 
2
 * This program is free software; you can redistribute it and/or modify
 
3
 * it under the terms of the GNU General Public License as published by
 
4
 * the Free Software Foundation; either version 2 of the License, or
 
5
 * (at your option) any later version.
 
6
 * 
 
7
 * This program is distributed in the hope that it will be useful,
 
8
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
 * GNU General Public License for more details.
 
11
 * 
 
12
 * You should have received a copy of the GNU General Public License
 
13
 * along with this program; if not, write to the Free Software
 
14
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 
15
 */
 
16
 
 
17
/*
 
18
 * K2.java
 
19
 * Copyright (C) 2001 University of Waikato, Hamilton, New Zealand
 
20
 * 
 
21
 */
 
22
package weka.classifiers.bayes.net.search.global;
 
23
 
 
24
import java.util.Enumeration;
 
25
import java.util.Vector;
 
26
import java.util.Random;
 
27
 
 
28
import weka.classifiers.bayes.BayesNet;
 
29
import weka.core.Instances;
 
30
import weka.core.Option;
 
31
import weka.core.TechnicalInformation;
 
32
import weka.core.TechnicalInformation.Type;
 
33
import weka.core.TechnicalInformation.Field;
 
34
import weka.core.TechnicalInformationHandler;
 
35
import weka.core.Utils;
 
36
 
 
37
/**
 
38
 <!-- globalinfo-start -->
 
39
 * This Bayes Network learning algorithm uses a hill climbing algorithm restricted by an order on the variables.<br/>
 
40
 * <br/>
 
41
 * For more information see:<br/>
 
42
 * <br/>
 
43
 * G.F. Cooper, E. Herskovits (1990). A Bayesian method for constructing Bayesian belief networks from databases.<br/>
 
44
 * <br/>
 
45
 * G. Cooper, E. Herskovits (1992). A Bayesian method for the induction of probabilistic networks from data. Machine Learning. 9(4):309-347.<br/>
 
46
 * <br/>
 
47
 * Works with nominal variables and no missing values only.
 
48
 * <p/>
 
49
 <!-- globalinfo-end -->
 
50
 *
 
51
 <!-- technical-bibtex-start -->
 
52
 * BibTeX:
 
53
 * <pre>
 
54
 * &#64;proceedings{Cooper1990,
 
55
 *    author = {G.F. Cooper and E. Herskovits},
 
56
 *    booktitle = {Proceedings of the Conference on Uncertainty in AI},
 
57
 *    pages = {86-94},
 
58
 *    title = {A Bayesian method for constructing Bayesian belief networks from databases},
 
59
 *    year = {1990}
 
60
 * }
 
61
 * 
 
62
 * &#64;article{Cooper1992,
 
63
 *    author = {G. Cooper and E. Herskovits},
 
64
 *    journal = {Machine Learning},
 
65
 *    number = {4},
 
66
 *    pages = {309-347},
 
67
 *    title = {A Bayesian method for the induction of probabilistic networks from data},
 
68
 *    volume = {9},
 
69
 *    year = {1992}
 
70
 * }
 
71
 * </pre>
 
72
 * <p/>
 
73
 <!-- technical-bibtex-end -->
 
74
 *
 
75
 <!-- options-start -->
 
76
 * Valid options are: <p/>
 
77
 * 
 
78
 * <pre> -N
 
79
 *  Initial structure is empty (instead of Naive Bayes)</pre>
 
80
 * 
 
81
 * <pre> -P &lt;nr of parents&gt;
 
82
 *  Maximum number of parents</pre>
 
83
 * 
 
84
 * <pre> -R
 
85
 *  Random order.
 
86
 *  (default false)</pre>
 
87
 * 
 
88
 * <pre> -mbc
 
89
 *  Applies a Markov Blanket correction to the network structure, 
 
90
 *  after a network structure is learned. This ensures that all 
 
91
 *  nodes in the network are part of the Markov blanket of the 
 
92
 *  classifier node.</pre>
 
93
 * 
 
94
 * <pre> -S [LOO-CV|k-Fold-CV|Cumulative-CV]
 
95
 *  Score type (LOO-CV,k-Fold-CV,Cumulative-CV)</pre>
 
96
 * 
 
97
 * <pre> -Q
 
98
 *  Use probabilistic or 0/1 scoring.
 
99
 *  (default probabilistic scoring)</pre>
 
100
 * 
 
101
 <!-- options-end -->
 
102
 *
 
103
 * @author Remco Bouckaert (rrb@xm.co.nz)
 
104
 * @version $Revision: 1.7 $
 
105
 */
 
106
public class K2 
 
107
        extends GlobalScoreSearchAlgorithm
 
108
        implements TechnicalInformationHandler {
 
109
  
 
110
        /** for serialization */
 
111
        static final long serialVersionUID = -6626871067466338256L;
 
112
        
 
113
        /** Holds flag to indicate ordering should be random **/
 
114
        boolean m_bRandomOrder = false;
 
115
 
 
116
        /**
 
117
         * Returns an instance of a TechnicalInformation object, containing 
 
118
         * detailed information about the technical background of this class,
 
119
         * e.g., paper reference or book this class is based on.
 
120
         * 
 
121
         * @return the technical information about this class
 
122
         */
 
123
        public TechnicalInformation getTechnicalInformation() {
 
124
          TechnicalInformation  result;
 
125
          TechnicalInformation  additional;
 
126
          
 
127
          result = new TechnicalInformation(Type.PROCEEDINGS);
 
128
          result.setValue(Field.AUTHOR, "G.F. Cooper and E. Herskovits");
 
129
          result.setValue(Field.YEAR, "1990");
 
130
          result.setValue(Field.TITLE, "A Bayesian method for constructing Bayesian belief networks from databases");
 
131
          result.setValue(Field.BOOKTITLE, "Proceedings of the Conference on Uncertainty in AI");
 
132
          result.setValue(Field.PAGES, "86-94");
 
133
          
 
134
          additional = result.add(Type.ARTICLE);
 
135
          additional.setValue(Field.AUTHOR, "G. Cooper and E. Herskovits");
 
136
          additional.setValue(Field.YEAR, "1992");
 
137
          additional.setValue(Field.TITLE, "A Bayesian method for the induction of probabilistic networks from data");
 
138
          additional.setValue(Field.JOURNAL, "Machine Learning");
 
139
          additional.setValue(Field.VOLUME, "9");
 
140
          additional.setValue(Field.NUMBER, "4");
 
141
          additional.setValue(Field.PAGES, "309-347");
 
142
          
 
143
          return result;
 
144
        }
 
145
 
 
146
        /**
 
147
         * search determines the network structure/graph of the network
 
148
         * with the K2 algorithm, restricted by its initial structure (which can
 
149
         * be an empty graph, or a Naive Bayes graph.
 
150
         * 
 
151
         * @param bayesNet the network
 
152
         * @param instances the data to work with
 
153
         * @throws Exception if something goes wrong
 
154
         */
 
155
        public void search (BayesNet bayesNet, Instances instances) throws Exception {
 
156
                int nOrder[] = new int [instances.numAttributes()];
 
157
                nOrder[0] = instances.classIndex();
 
158
 
 
159
                int nAttribute = 0;
 
160
 
 
161
                for (int iOrder = 1; iOrder < instances.numAttributes(); iOrder++) {
 
162
                  if (nAttribute == instances.classIndex()) {
 
163
                    nAttribute++;
 
164
                  } 
 
165
                  nOrder[iOrder] = nAttribute++;
 
166
                } 
 
167
 
 
168
                if (m_bRandomOrder) {
 
169
                        // generate random ordering (if required)
 
170
                        Random random = new Random();
 
171
                                        int iClass;
 
172
                                        if (getInitAsNaiveBayes()) {
 
173
                                                iClass = 0; 
 
174
                                        } else {
 
175
                                                iClass = -1;
 
176
                                        }
 
177
                        for (int iOrder = 0; iOrder < instances.numAttributes(); iOrder++) {
 
178
                        int iOrder2 = Math.abs(random.nextInt()) % instances.numAttributes();
 
179
                                                if (iOrder != iClass && iOrder2 != iClass) {
 
180
                                                        int nTmp = nOrder[iOrder];
 
181
                                                        nOrder[iOrder] = nOrder[iOrder2];
 
182
                                                        nOrder[iOrder2] = nTmp;
 
183
                                                }
 
184
                        }
 
185
                }
 
186
 
 
187
                // determine base scores
 
188
                double fBaseScore = calcScore(bayesNet);
 
189
 
 
190
                // K2 algorithm: greedy search restricted by ordering 
 
191
                for (int iOrder = 1; iOrder < instances.numAttributes(); iOrder++) {
 
192
                        int iAttribute = nOrder[iOrder];
 
193
                        double fBestScore = fBaseScore;
 
194
 
 
195
                        boolean bProgress = (bayesNet.getParentSet(iAttribute).getNrOfParents() < getMaxNrOfParents());
 
196
                        while (bProgress && (bayesNet.getParentSet(iAttribute).getNrOfParents() < getMaxNrOfParents())) {
 
197
                                int nBestAttribute = -1;
 
198
                                for (int iOrder2 = 0; iOrder2 < iOrder; iOrder2++) {
 
199
                                        int iAttribute2 = nOrder[iOrder2];
 
200
                                        double fScore = calcScoreWithExtraParent(iAttribute, iAttribute2);
 
201
                                        if (fScore > fBestScore) {
 
202
                                                fBestScore = fScore;
 
203
                                                nBestAttribute = iAttribute2;
 
204
                                        }
 
205
                                }
 
206
                                if (nBestAttribute != -1) {
 
207
                                        bayesNet.getParentSet(iAttribute).addParent(nBestAttribute, instances);
 
208
                                        fBaseScore = fBestScore;
 
209
                                        bProgress = true;
 
210
                                } else {
 
211
                                        bProgress = false;
 
212
                                }
 
213
                        }
 
214
                }
 
215
        } // search 
 
216
 
 
217
        /**
 
218
         * Sets the max number of parents
 
219
         *
 
220
         * @param nMaxNrOfParents the max number of parents
 
221
         */
 
222
        public void setMaxNrOfParents(int nMaxNrOfParents) {
 
223
          m_nMaxNrOfParents = nMaxNrOfParents;
 
224
        } 
 
225
 
 
226
        /**
 
227
         * Gets the max number of parents.
 
228
         *
 
229
         * @return the max number of parents
 
230
         */
 
231
        public int getMaxNrOfParents() {
 
232
          return m_nMaxNrOfParents;
 
233
        } 
 
234
 
 
235
        /**
 
236
         * Sets whether to init as naive bayes
 
237
         *
 
238
         * @param bInitAsNaiveBayes whether to init as naive bayes
 
239
         */
 
240
        public void setInitAsNaiveBayes(boolean bInitAsNaiveBayes) {
 
241
          m_bInitAsNaiveBayes = bInitAsNaiveBayes;
 
242
        } 
 
243
 
 
244
        /**
 
245
         * Gets whether to init as naive bayes
 
246
         *
 
247
         * @return whether to init as naive bayes
 
248
         */
 
249
        public boolean getInitAsNaiveBayes() {
 
250
          return m_bInitAsNaiveBayes;
 
251
        } 
 
252
 
 
253
        /** 
 
254
         * Set random order flag 
 
255
         *
 
256
         * @param bRandomOrder the random order flag
 
257
         */
 
258
        public void setRandomOrder(boolean bRandomOrder) {
 
259
                m_bRandomOrder = bRandomOrder;
 
260
        } // SetRandomOrder
 
261
 
 
262
        /** 
 
263
         * Get random order flag 
 
264
         *
 
265
         * @return the random order flag
 
266
         */
 
267
        public boolean getRandomOrder() {
 
268
                return m_bRandomOrder;
 
269
        } // getRandomOrder
 
270
  
 
271
        /**
 
272
         * Returns an enumeration describing the available options.
 
273
         *
 
274
         * @return an enumeration of all the available options.
 
275
         */
 
276
        public Enumeration listOptions() {
 
277
          Vector newVector = new Vector(0);
 
278
 
 
279
          newVector.addElement(new Option("\tInitial structure is empty (instead of Naive Bayes)", 
 
280
                                         "N", 0, "-N"));
 
281
 
 
282
          newVector.addElement(new Option("\tMaximum number of parents", "P", 1, 
 
283
                                                "-P <nr of parents>"));
 
284
 
 
285
          newVector.addElement(new Option(
 
286
                        "\tRandom order.\n"
 
287
                        + "\t(default false)",
 
288
                        "R", 0, "-R"));
 
289
 
 
290
                Enumeration enu = super.listOptions();
 
291
                while (enu.hasMoreElements()) {
 
292
          newVector.addElement(enu.nextElement());
 
293
                }
 
294
          return newVector.elements();
 
295
        }
 
296
 
 
297
        /**
 
298
         * Parses a given list of options. <p/>
 
299
         *
 
300
         <!-- options-start -->
 
301
         * Valid options are: <p/>
 
302
         * 
 
303
         * <pre> -N
 
304
         *  Initial structure is empty (instead of Naive Bayes)</pre>
 
305
         * 
 
306
         * <pre> -P &lt;nr of parents&gt;
 
307
         *  Maximum number of parents</pre>
 
308
         * 
 
309
         * <pre> -R
 
310
         *  Random order.
 
311
         *  (default false)</pre>
 
312
         * 
 
313
         * <pre> -mbc
 
314
         *  Applies a Markov Blanket correction to the network structure, 
 
315
         *  after a network structure is learned. This ensures that all 
 
316
         *  nodes in the network are part of the Markov blanket of the 
 
317
         *  classifier node.</pre>
 
318
         * 
 
319
         * <pre> -S [LOO-CV|k-Fold-CV|Cumulative-CV]
 
320
         *  Score type (LOO-CV,k-Fold-CV,Cumulative-CV)</pre>
 
321
         * 
 
322
         * <pre> -Q
 
323
         *  Use probabilistic or 0/1 scoring.
 
324
         *  (default probabilistic scoring)</pre>
 
325
         * 
 
326
         <!-- options-end -->
 
327
         *
 
328
         * @param options the list of options as an array of strings
 
329
         * @throws Exception if an option is not supported
 
330
         */
 
331
        public void setOptions(String[] options) throws Exception {
 
332
    
 
333
          setRandomOrder(Utils.getFlag('R', options));
 
334
 
 
335
          m_bInitAsNaiveBayes = !(Utils.getFlag('N', options));
 
336
 
 
337
          String sMaxNrOfParents = Utils.getOption('P', options);
 
338
 
 
339
          if (sMaxNrOfParents.length() != 0) {
 
340
                setMaxNrOfParents(Integer.parseInt(sMaxNrOfParents));
 
341
          } else {
 
342
                setMaxNrOfParents(100000);
 
343
          } 
 
344
          super.setOptions(options);      
 
345
        }
 
346
 
 
347
        /**
 
348
         * Gets the current settings of the search algorithm.
 
349
         *
 
350
         * @return an array of strings suitable for passing to setOptions
 
351
         */
 
352
        public String [] getOptions() {
 
353
                String[] superOptions = super.getOptions();
 
354
                String[] options = new String[4 + superOptions.length];
 
355
                int current = 0;
 
356
                  options[current++] = "-P";
 
357
                  options[current++] = "" + m_nMaxNrOfParents;
 
358
            if (!m_bInitAsNaiveBayes) {
 
359
                  options[current++] = "-N";
 
360
            } 
 
361
            if (getRandomOrder()) {
 
362
                  options[current++] = "-R";
 
363
            }
 
364
            // insert options from parent class
 
365
            for (int iOption = 0; iOption < superOptions.length; iOption++) {
 
366
                  options[current++] = superOptions[iOption];
 
367
            }
 
368
            // Fill up rest with empty strings, not nulls!
 
369
            while (current < options.length) {
 
370
                  options[current++] = "";
 
371
            }
 
372
            // Fill up rest with empty strings, not nulls!
 
373
            return options;
 
374
        }
 
375
 
 
376
        /**
 
377
         * @return a string to describe the RandomOrder option.
 
378
         */
 
379
        public String randomOrderTipText() {
 
380
          return "When set to true, the order of the nodes in the network is random." +
 
381
          " Default random order is false and the order" +
 
382
          " of the nodes in the dataset is used." +
 
383
          " In any case, when the network was initialized as Naive Bayes Network, the" +
 
384
          " class variable is first in the ordering though.";
 
385
        } // randomOrderTipText
 
386
 
 
387
        /**
 
388
         * This will return a string describing the search algorithm.
 
389
         * @return The string.
 
390
         */
 
391
        public String globalInfo() {
 
392
          return 
 
393
              "This Bayes Network learning algorithm uses a hill climbing algorithm "
 
394
            + "restricted by an order on the variables.\n\n"
 
395
            + "For more information see:\n\n"
 
396
            + getTechnicalInformation().toString() + "\n\n"
 
397
            + "Works with nominal variables and no missing values only.";
 
398
        }
 
399
}