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.
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.
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.
19
* Copyright (C) 2001 University of Waikato, Hamilton, New Zealand
22
package weka.classifiers.bayes.net.search.global;
24
import java.util.Enumeration;
25
import java.util.Vector;
26
import java.util.Random;
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;
38
<!-- globalinfo-start -->
39
* This Bayes Network learning algorithm uses a hill climbing algorithm restricted by an order on the variables.<br/>
41
* For more information see:<br/>
43
* G.F. Cooper, E. Herskovits (1990). A Bayesian method for constructing Bayesian belief networks from databases.<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/>
47
* Works with nominal variables and no missing values only.
49
<!-- globalinfo-end -->
51
<!-- technical-bibtex-start -->
54
* @proceedings{Cooper1990,
55
* author = {G.F. Cooper and E. Herskovits},
56
* booktitle = {Proceedings of the Conference on Uncertainty in AI},
58
* title = {A Bayesian method for constructing Bayesian belief networks from databases},
62
* @article{Cooper1992,
63
* author = {G. Cooper and E. Herskovits},
64
* journal = {Machine Learning},
67
* title = {A Bayesian method for the induction of probabilistic networks from data},
73
<!-- technical-bibtex-end -->
75
<!-- options-start -->
76
* Valid options are: <p/>
79
* Initial structure is empty (instead of Naive Bayes)</pre>
81
* <pre> -P <nr of parents>
82
* Maximum number of parents</pre>
86
* (default false)</pre>
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>
94
* <pre> -S [LOO-CV|k-Fold-CV|Cumulative-CV]
95
* Score type (LOO-CV,k-Fold-CV,Cumulative-CV)</pre>
98
* Use probabilistic or 0/1 scoring.
99
* (default probabilistic scoring)</pre>
103
* @author Remco Bouckaert (rrb@xm.co.nz)
104
* @version $Revision: 1.7 $
107
extends GlobalScoreSearchAlgorithm
108
implements TechnicalInformationHandler {
110
/** for serialization */
111
static final long serialVersionUID = -6626871067466338256L;
113
/** Holds flag to indicate ordering should be random **/
114
boolean m_bRandomOrder = false;
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.
121
* @return the technical information about this class
123
public TechnicalInformation getTechnicalInformation() {
124
TechnicalInformation result;
125
TechnicalInformation additional;
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");
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");
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.
151
* @param bayesNet the network
152
* @param instances the data to work with
153
* @throws Exception if something goes wrong
155
public void search (BayesNet bayesNet, Instances instances) throws Exception {
156
int nOrder[] = new int [instances.numAttributes()];
157
nOrder[0] = instances.classIndex();
161
for (int iOrder = 1; iOrder < instances.numAttributes(); iOrder++) {
162
if (nAttribute == instances.classIndex()) {
165
nOrder[iOrder] = nAttribute++;
168
if (m_bRandomOrder) {
169
// generate random ordering (if required)
170
Random random = new Random();
172
if (getInitAsNaiveBayes()) {
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;
187
// determine base scores
188
double fBaseScore = calcScore(bayesNet);
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;
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) {
203
nBestAttribute = iAttribute2;
206
if (nBestAttribute != -1) {
207
bayesNet.getParentSet(iAttribute).addParent(nBestAttribute, instances);
208
fBaseScore = fBestScore;
218
* Sets the max number of parents
220
* @param nMaxNrOfParents the max number of parents
222
public void setMaxNrOfParents(int nMaxNrOfParents) {
223
m_nMaxNrOfParents = nMaxNrOfParents;
227
* Gets the max number of parents.
229
* @return the max number of parents
231
public int getMaxNrOfParents() {
232
return m_nMaxNrOfParents;
236
* Sets whether to init as naive bayes
238
* @param bInitAsNaiveBayes whether to init as naive bayes
240
public void setInitAsNaiveBayes(boolean bInitAsNaiveBayes) {
241
m_bInitAsNaiveBayes = bInitAsNaiveBayes;
245
* Gets whether to init as naive bayes
247
* @return whether to init as naive bayes
249
public boolean getInitAsNaiveBayes() {
250
return m_bInitAsNaiveBayes;
254
* Set random order flag
256
* @param bRandomOrder the random order flag
258
public void setRandomOrder(boolean bRandomOrder) {
259
m_bRandomOrder = bRandomOrder;
263
* Get random order flag
265
* @return the random order flag
267
public boolean getRandomOrder() {
268
return m_bRandomOrder;
272
* Returns an enumeration describing the available options.
274
* @return an enumeration of all the available options.
276
public Enumeration listOptions() {
277
Vector newVector = new Vector(0);
279
newVector.addElement(new Option("\tInitial structure is empty (instead of Naive Bayes)",
282
newVector.addElement(new Option("\tMaximum number of parents", "P", 1,
283
"-P <nr of parents>"));
285
newVector.addElement(new Option(
287
+ "\t(default false)",
290
Enumeration enu = super.listOptions();
291
while (enu.hasMoreElements()) {
292
newVector.addElement(enu.nextElement());
294
return newVector.elements();
298
* Parses a given list of options. <p/>
300
<!-- options-start -->
301
* Valid options are: <p/>
304
* Initial structure is empty (instead of Naive Bayes)</pre>
306
* <pre> -P <nr of parents>
307
* Maximum number of parents</pre>
311
* (default false)</pre>
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>
319
* <pre> -S [LOO-CV|k-Fold-CV|Cumulative-CV]
320
* Score type (LOO-CV,k-Fold-CV,Cumulative-CV)</pre>
323
* Use probabilistic or 0/1 scoring.
324
* (default probabilistic scoring)</pre>
328
* @param options the list of options as an array of strings
329
* @throws Exception if an option is not supported
331
public void setOptions(String[] options) throws Exception {
333
setRandomOrder(Utils.getFlag('R', options));
335
m_bInitAsNaiveBayes = !(Utils.getFlag('N', options));
337
String sMaxNrOfParents = Utils.getOption('P', options);
339
if (sMaxNrOfParents.length() != 0) {
340
setMaxNrOfParents(Integer.parseInt(sMaxNrOfParents));
342
setMaxNrOfParents(100000);
344
super.setOptions(options);
348
* Gets the current settings of the search algorithm.
350
* @return an array of strings suitable for passing to setOptions
352
public String [] getOptions() {
353
String[] superOptions = super.getOptions();
354
String[] options = new String[4 + superOptions.length];
356
options[current++] = "-P";
357
options[current++] = "" + m_nMaxNrOfParents;
358
if (!m_bInitAsNaiveBayes) {
359
options[current++] = "-N";
361
if (getRandomOrder()) {
362
options[current++] = "-R";
364
// insert options from parent class
365
for (int iOption = 0; iOption < superOptions.length; iOption++) {
366
options[current++] = superOptions[iOption];
368
// Fill up rest with empty strings, not nulls!
369
while (current < options.length) {
370
options[current++] = "";
372
// Fill up rest with empty strings, not nulls!
377
* @return a string to describe the RandomOrder option.
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
388
* This will return a string describing the search algorithm.
389
* @return The string.
391
public String globalInfo() {
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.";