← Back to branch summary

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

« back to all changes in this revision

Viewing changes to weka/attributeSelection/SubsetSizeForwardSelection.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/attributeSelection/SubsetSizeForwardSelection.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
 *    SubsetSizeForwardSelection.java
 
19
 *    Copyright (C) 2007 Martin Gütlein
 
20
 *
 
21
 */
 
22
package weka.attributeSelection;
 
23
 
 
24
import weka.core.Instances;
 
25
import weka.core.Option;
 
26
import weka.core.OptionHandler;
 
27
import weka.core.SelectedTag;
 
28
import weka.core.Tag;
 
29
import weka.core.Utils;
 
30
import weka.core.TechnicalInformation;
 
31
import weka.core.TechnicalInformationHandler;
 
32
import weka.core.TechnicalInformation.Field;
 
33
import weka.core.TechnicalInformation.Type;
 
34
 
 
35
import java.util.BitSet;
 
36
import java.util.Enumeration;
 
37
import java.util.Random;
 
38
import java.util.Vector;
 
39
 
 
40
 
 
41
/**
 
42
 <!-- globalinfo-start -->
 
43
 * SubsetSizeForwardSelection :<br/>
 
44
 * Class for performing a subset size forward selection
 
45
 * <p>
 
46
 <!-- globalinfo-end -->
 
47
 *
 
48
 <!-- options-start -->
 
49
 * Valid options are:
 
50
 * <p>
 
51
 *
 
52
 * <pre> -I
 
53
 * Perform initial ranking to select top-ranked attributes.</pre>
 
54
 *
 
55
 * <pre> -K &lt;num&gt;
 
56
 * Number of top-ranked attributes that are taken into account.</pre>
 
57
 *
 
58
 * <pre> -T &lt;0 = fixed-set | 1 = fixed-width&gt;
 
59
 * Type of Linear Forward Selection (default = 0).</pre>
 
60
 *
 
61
 * <pre> -S &lt;num&gt;
 
62
 * Size of lookup cache for evaluated subsets. Expressed as a multiple of the
 
63
 * number of attributes in the data set. (default = 1).</pre>
 
64
 *
 
65
 * <pre> -E &lt;string&gt;
 
66
 * class name of subset evaluator to use for subset size determination (default =
 
67
 * null, same subset evaluator as for ranking and final forward selection is
 
68
 * used). Place any evaluator options LAST on the command line following a "--".
 
69
 * eg. -A weka.attributeSelection.ClassifierSubsetEval ... -- -M<pre>
 
70
 *
 
71
 * <pre> -F &lt;num&gt;
 
72
 * Number of cross validation folds for subset size determination (default = 5).</pre>
 
73
 *
 
74
 * <pre> -R &lt;num&gt;
 
75
 * Seed for cross validation subset size determination. (default = 1)</pre>
 
76
 *
 
77
 * <pre> -Z
 
78
 * verbose on/off.</pre>
 
79
 *
 
80
 <!-- options-end -->
 
81
 *
 
82
 * @author Martin Guetlein (martin.guetlein@gmail.com)
 
83
 * @version $Revision: 1.1 $
 
84
 */
 
85
public class SubsetSizeForwardSelection extends ASSearch
 
86
  implements OptionHandler {
 
87
  /** search directions */
 
88
  protected static final int TYPE_FIXED_SET = 0;
 
89
  protected static final int TYPE_FIXED_WIDTH = 1;
 
90
  public static final Tag[] TAGS_TYPE = {
 
91
    new Tag(TYPE_FIXED_SET, "Fixed-set"),
 
92
    new Tag(TYPE_FIXED_WIDTH, "Fixed-width"),
 
93
  };
 
94
 
 
95
  // member variables
 
96
  /** perform initial ranking to select top-ranked attributes */
 
97
  protected boolean m_performRanking;
 
98
 
 
99
  /**
 
100
   * number of top-ranked attributes that are taken into account for the
 
101
   * search
 
102
   */
 
103
  protected int m_numUsedAttributes;
 
104
 
 
105
  /** 0 == fixed-set, 1 == fixed-width */
 
106
  protected int m_linearSelectionType;
 
107
 
 
108
  /** the subset evaluator to use for subset size determination */
 
109
  private SubsetEvaluator m_setSizeEval;
 
110
 
 
111
  /**
 
112
   * Number of cross validation folds for subset size determination (default =
 
113
   * 5).
 
114
   */
 
115
  protected int m_numFolds;
 
116
 
 
117
  /** Seed for cross validation subset size determination. (default = 1) */
 
118
  protected int m_seed;
 
119
 
 
120
  /** number of attributes in the data */
 
121
  protected int m_numAttribs;
 
122
 
 
123
  /** total number of subsets evaluated during a search */
 
124
  protected int m_totalEvals;
 
125
 
 
126
  /** for debugging */
 
127
  protected boolean m_verbose;
 
128
 
 
129
  /** holds the merit of the best subset found */
 
130
  protected double m_bestMerit;
 
131
 
 
132
  /** holds the maximum size of the lookup cache for evaluated subsets */
 
133
  protected int m_cacheSize;
 
134
 
 
135
  /**
 
136
   * Constructor
 
137
   */
 
138
  public SubsetSizeForwardSelection() {
 
139
    resetOptions();
 
140
  }
 
141
 
 
142
  /**
 
143
   * Returns a string describing this search method
 
144
   *
 
145
   * @return a description of the search method suitable for displaying in the
 
146
   *         explorer/experimenter gui
 
147
   */
 
148
  public String globalInfo() {
 
149
    return "SubsetSizeForwardSelection:\n\n" +
 
150
      "Extension of LinearForwardSelection. The search performs an interior " +
 
151
      "cross-validation (seed and number of folds can be specified). A " +
 
152
      "LinearForwardSelection is performed on each foldto determine the optimal " +
 
153
      "subset-size (using the given SubsetSizeEvaluator). Finally, a " +
 
154
      "LinearForwardSelection up to the optimal subset-size is performed on " +
 
155
      "the whole data.\n\n"
 
156
      + "For more information see:\n\n"
 
157
      + getTechnicalInformation().toString();
 
158
  }
 
159
 
 
160
  /**
 
161
   * Returns an instance of a TechnicalInformation object, containing 
 
162
   * detailed information about the technical background of this class,
 
163
   * e.g., paper reference or book this class is based on.
 
164
   * 
 
165
   * @return the technical information about this class
 
166
   */
 
167
  public TechnicalInformation getTechnicalInformation() {
 
168
    TechnicalInformation        result;
 
169
    
 
170
    result = new TechnicalInformation(Type.MASTERSTHESIS);
 
171
    result.setValue(Field.AUTHOR, "Martin Guetlein");
 
172
    result.setValue(Field.YEAR, "2006");
 
173
    result.setValue(Field.TITLE, "Large Scale Attribute Selection Using Wrappers");
 
174
    result.setValue(Field.SCHOOL, "Albert-Ludwigs-Universitat");
 
175
    result.setValue(Field.ADDRESS, "Freiburg, Germany");
 
176
    
 
177
    return result;
 
178
  }
 
179
 
 
180
  /**
 
181
   * Returns an enumeration describing the available options.
 
182
   *
 
183
   * @return an enumeration of all the available options.
 
184
   *
 
185
   */
 
186
  public Enumeration listOptions() {
 
187
    Vector newVector = new Vector(9);
 
188
 
 
189
    newVector.addElement(new Option("\tPerform initial ranking to select the" +
 
190
                                    "\n\ttop-ranked attributes.", "I", 0, "-I"));
 
191
    newVector.addElement(new Option(
 
192
                                    "\tNumber of top-ranked attributes that are " +
 
193
                                    "\n\ttaken into account by the search.", "K", 1, "-K <num>"));
 
194
    newVector.addElement(new Option(
 
195
                                    "\tType of Linear Forward Selection (default = 0).", "T", 1,
 
196
                                    "-T <0 = fixed-set | 1 = fixed-width>"));
 
197
    newVector.addElement(new Option(
 
198
                                    "\tSize of lookup cache for evaluated subsets." +
 
199
                                    "\n\tExpressed as a multiple of the number of" +
 
200
                                    "\n\tattributes in the data set. (default = 1)", "S", 1, "-S <num>"));
 
201
    newVector.addElement(new Option(
 
202
                                    "\tSubset-evaluator used for subset-size determination." + "-- -M",
 
203
                                    "E", 1, "-E <subset evaluator>"));
 
204
    newVector.addElement(new Option("\tNumber of cross validation folds" +
 
205
                                    "\n\tfor subset size determination (default = 5).", "F", 1, "-F <num>"));
 
206
    newVector.addElement(new Option("\tSeed for cross validation" +
 
207
                                    "\n\tsubset size determination. (default = 1)", "R", 1, "-R <num>"));
 
208
    newVector.addElement(new Option("\tverbose on/off", "Z", 0, "-Z"));
 
209
 
 
210
    if ((m_setSizeEval != null) && (m_setSizeEval instanceof OptionHandler)) {
 
211
      newVector.addElement(new Option("", "", 0,
 
212
                                      "\nOptions specific to " + "evaluator " +
 
213
                                      m_setSizeEval.getClass().getName() + ":"));
 
214
 
 
215
      Enumeration enu = ((OptionHandler) m_setSizeEval).listOptions();
 
216
 
 
217
      while (enu.hasMoreElements()) {
 
218
        newVector.addElement(enu.nextElement());
 
219
      }
 
220
    }
 
221
 
 
222
    return newVector.elements();
 
223
  }
 
224
 
 
225
  /**
 
226
   * Parses a given list of options.
 
227
   *
 
228
   * Valid options are:
 
229
   * <p>
 
230
   *
 
231
   * -I <br>
 
232
   * Perform initial ranking to select top-ranked attributes.
 
233
   * <p>
 
234
   *
 
235
   * -K <num> <br>
 
236
   * Number of top-ranked attributes that are taken into account.
 
237
   * <p>
 
238
   *
 
239
   * -T <0 = fixed-set | 1 = fixed-width> <br>
 
240
   * Typ of Linear Forward Selection (default = 0).
 
241
   * <p>
 
242
   *
 
243
   * -S <num> <br>
 
244
   * Size of lookup cache for evaluated subsets. Expressed as a multiple of
 
245
   * the number of attributes in the data set. (default = 1).
 
246
   * <p>
 
247
   *
 
248
   * -E <string> <br>
 
249
   * class name of subset evaluator to use for subset size determination
 
250
   * (default = null, same subset evaluator as for ranking and final forward
 
251
   * selection is used). Place any evaluator options LAST on the command line
 
252
   * following a "--". eg. -A weka.attributeSelection.ClassifierSubsetEval ... --
 
253
   * -M
 
254
   *
 
255
   * </pre>
 
256
   *
 
257
   * -F <num> <br>
 
258
   * Number of cross validation folds for subset size determination (default =
 
259
   * 5).
 
260
   * <p>
 
261
   *
 
262
   * -R <num> <br>
 
263
   * Seed for cross validation subset size determination. (default = 1)
 
264
   * <p>
 
265
   *
 
266
   * -Z <br>
 
267
   * verbose on/off.
 
268
   * <p>
 
269
   *
 
270
   * @param options
 
271
   *            the list of options as an array of strings
 
272
   * @exception Exception
 
273
   *                if an option is not supported
 
274
   *
 
275
   */
 
276
  public void setOptions(String[] options) throws Exception {
 
277
    String optionString;
 
278
    resetOptions();
 
279
 
 
280
    setPerformRanking(Utils.getFlag('I', options));
 
281
 
 
282
    optionString = Utils.getOption('K', options);
 
283
 
 
284
    if (optionString.length() != 0) {
 
285
      setNumUsedAttributes(Integer.parseInt(optionString));
 
286
    }
 
287
 
 
288
    optionString = Utils.getOption('T', options);
 
289
 
 
290
    if (optionString.length() != 0) {
 
291
      setType(new SelectedTag(Integer.parseInt(optionString), TAGS_TYPE));
 
292
    } else {
 
293
      setType(new SelectedTag(TYPE_FIXED_SET, TAGS_TYPE));
 
294
    }
 
295
 
 
296
    optionString = Utils.getOption('S', options);
 
297
 
 
298
    if (optionString.length() != 0) {
 
299
      setLookupCacheSize(Integer.parseInt(optionString));
 
300
    }
 
301
 
 
302
    optionString = Utils.getOption('E', options);
 
303
 
 
304
    if (optionString.length() == 0) {
 
305
      System.out.println(
 
306
                         "No subset size evaluator given, using evaluator that is used for final search.");
 
307
      m_setSizeEval = null;
 
308
    } else {
 
309
      setSubsetSizeEvaluator(ASEvaluation.forName(optionString,
 
310
                                                  Utils.partitionOptions(options)));
 
311
    }
 
312
 
 
313
    optionString = Utils.getOption('F', options);
 
314
 
 
315
    if (optionString.length() != 0) {
 
316
      setNumSubsetSizeCVFolds(Integer.parseInt(optionString));
 
317
    }
 
318
 
 
319
    optionString = Utils.getOption('R', options);
 
320
 
 
321
    if (optionString.length() != 0) {
 
322
      setSeed(Integer.parseInt(optionString));
 
323
    }
 
324
 
 
325
    m_verbose = Utils.getFlag('Z', options);
 
326
  }
 
327
 
 
328
  /**
 
329
   * Set the maximum size of the evaluated subset cache (hashtable). This is
 
330
   * expressed as a multiplier for the number of attributes in the data set.
 
331
   * (default = 1).
 
332
   *
 
333
   * @param size
 
334
   *            the maximum size of the hashtable
 
335
   */
 
336
  public void setLookupCacheSize(int size) {
 
337
    if (size >= 0) {
 
338
      m_cacheSize = size;
 
339
    }
 
340
  }
 
341
 
 
342
  /**
 
343
   * Return the maximum size of the evaluated subset cache (expressed as a
 
344
   * multiplier for the number of attributes in a data set.
 
345
   *
 
346
   * @return the maximum size of the hashtable.
 
347
   */
 
348
  public int getLookupCacheSize() {
 
349
    return m_cacheSize;
 
350
  }
 
351
 
 
352
  /**
 
353
   * Returns the tip text for this property
 
354
   *
 
355
   * @return tip text for this property suitable for displaying in the
 
356
   *         explorer/experimenter gui
 
357
   */
 
358
  public String lookupCacheSizeTipText() {
 
359
    return "Set the maximum size of the lookup cache of evaluated subsets. This is " +
 
360
      "expressed as a multiplier of the number of attributes in the data set. " +
 
361
      "(default = 1).";
 
362
  }
 
363
 
 
364
  /**
 
365
   * Returns the tip text for this property
 
366
   *
 
367
   * @return tip text for this property suitable for displaying in the
 
368
   *         explorer/experimenter gui
 
369
   */
 
370
  public String performRankingTipText() {
 
371
    return "Perform initial ranking to select top-ranked attributes.";
 
372
  }
 
373
 
 
374
  /**
 
375
   * Perform initial ranking to select top-ranked attributes.
 
376
   *
 
377
   * @param b
 
378
   *            true if initial ranking should be performed
 
379
   */
 
380
  public void setPerformRanking(boolean b) {
 
381
    m_performRanking = b;
 
382
  }
 
383
 
 
384
  /**
 
385
   * Get boolean if initial ranking should be performed to select the
 
386
   * top-ranked attributes
 
387
   *
 
388
   * @return true if initial ranking should be performed
 
389
   */
 
390
  public boolean getPerformRanking() {
 
391
    return m_performRanking;
 
392
  }
 
393
 
 
394
  /**
 
395
   * Returns the tip text for this property
 
396
   *
 
397
   * @return tip text for this property suitable for displaying in the
 
398
   *         explorer/experimenter gui
 
399
   */
 
400
  public String numUsedAttributesTipText() {
 
401
    return "Set the amount of top-ranked attributes that are taken into account by the search process.";
 
402
  }
 
403
 
 
404
  /**
 
405
   * Set the number of top-ranked attributes that taken into account by the
 
406
   * search process.
 
407
   *
 
408
   * @param k
 
409
   *            the number of attributes
 
410
   * @exception Exception
 
411
   *                if k is less than 2
 
412
   */
 
413
  public void setNumUsedAttributes(int k) throws Exception {
 
414
    if (k < 2) {
 
415
      throw new Exception("Value of -K must be >= 2.");
 
416
    }
 
417
 
 
418
    m_numUsedAttributes = k;
 
419
  }
 
420
 
 
421
  /**
 
422
   * Get the number of top-ranked attributes that taken into account by the
 
423
   * search process.
 
424
   *
 
425
   * @return the number of top-ranked attributes that taken into account
 
426
   */
 
427
  public int getNumUsedAttributes() {
 
428
    return m_numUsedAttributes;
 
429
  }
 
430
 
 
431
  /**
 
432
   * Returns the tip text for this property
 
433
   *
 
434
   * @return tip text for this property suitable for displaying in the
 
435
   *         explorer/experimenter gui
 
436
   */
 
437
  public String typeTipText() {
 
438
    return "Set the type of the search.";
 
439
  }
 
440
 
 
441
  /**
 
442
   * Set the type
 
443
   *
 
444
   * @param t
 
445
   *            the Linear Forward Selection type
 
446
   */
 
447
  public void setType(SelectedTag t) {
 
448
    if (t.getTags() == TAGS_TYPE) {
 
449
      m_linearSelectionType = t.getSelectedTag().getID();
 
450
    }
 
451
  }
 
452
 
 
453
  /**
 
454
   * Get the type
 
455
   *
 
456
   * @return the Linear Forward Selection type
 
457
   */
 
458
  public SelectedTag getType() {
 
459
    return new SelectedTag(m_linearSelectionType, TAGS_TYPE);
 
460
  }
 
461
 
 
462
  /**
 
463
   * Returns the tip text for this property
 
464
   *
 
465
   * @return tip text for this property suitable for displaying in the
 
466
   *         explorer/experimenter gui
 
467
   */
 
468
  public String subsetSizeEvaluatorTipText() {
 
469
    return "Subset evaluator to use for subset size determination.";
 
470
  }
 
471
 
 
472
  /**
 
473
   * Set the subset evaluator to use for subset size determination.
 
474
   *
 
475
   * @param eval
 
476
   *            the subset evaluator to use for subset size determination.
 
477
   */
 
478
  public void setSubsetSizeEvaluator(ASEvaluation eval)
 
479
    throws Exception {
 
480
    if (!SubsetEvaluator.class.isInstance(eval)) {
 
481
      throw new Exception(eval.getClass().getName() +
 
482
                          " is no subset evaluator.");
 
483
    }
 
484
 
 
485
    m_setSizeEval = (SubsetEvaluator) eval;
 
486
  }
 
487
 
 
488
  /**
 
489
   * Get the subset evaluator used for subset size determination.
 
490
   *
 
491
   * @return the evaluator used for subset size determination.
 
492
   */
 
493
  public ASEvaluation getSubsetSizeEvaluator() {
 
494
    return m_setSizeEval;
 
495
  }
 
496
 
 
497
  /**
 
498
   * Returns the tip text for this property
 
499
   *
 
500
   * @return tip text for this property suitable for displaying in the
 
501
   *         explorer/experimenter gui
 
502
   */
 
503
  public String numSubsetSizeCVFoldsTipText() {
 
504
    return "Number of cross validation folds for subset size determination";
 
505
  }
 
506
 
 
507
  /**
 
508
   * Set the number of cross validation folds for subset size determination
 
509
   * (default = 5).
 
510
   *
 
511
   * @param f
 
512
   *            number of folds
 
513
   */
 
514
  public void setNumSubsetSizeCVFolds(int f) {
 
515
    m_numFolds = f;
 
516
  }
 
517
 
 
518
  /**
 
519
   * Get the number of cross validation folds for subset size determination
 
520
   * (default = 5).
 
521
   *
 
522
   * @return number of folds
 
523
   */
 
524
  public int getNumSubsetSizeCVFolds() {
 
525
    return m_numFolds;
 
526
  }
 
527
 
 
528
  /**
 
529
   * Returns the tip text for this property
 
530
   *
 
531
   * @return tip text for this property suitable for displaying in the
 
532
   *         explorer/experimenter gui
 
533
   */
 
534
  public String seedTipText() {
 
535
    return "Seed for cross validation subset size determination. (default = 1)";
 
536
  }
 
537
 
 
538
  /**
 
539
   * Seed for cross validation subset size determination. (default = 1)
 
540
   *
 
541
   * @param s
 
542
   *            seed
 
543
   */
 
544
  public void setSeed(int s) {
 
545
    m_seed = s;
 
546
  }
 
547
 
 
548
  /**
 
549
   * Seed for cross validation subset size determination. (default = 1)
 
550
   *
 
551
   * @return seed
 
552
   */
 
553
  public int getSeed() {
 
554
    return m_seed;
 
555
  }
 
556
 
 
557
  /**
 
558
   * Returns the tip text for this property
 
559
   *
 
560
   * @return tip text for this property suitable for displaying in the
 
561
   *         explorer/experimenter gui
 
562
   */
 
563
  public String verboseTipText() {
 
564
    return "Turn on verbose output for monitoring the search's progress.";
 
565
  }
 
566
 
 
567
  /**
 
568
   * Set whether verbose output should be generated.
 
569
   *
 
570
   * @param d
 
571
   *            true if output is to be verbose.
 
572
   */
 
573
  public void setVerbose(boolean b) {
 
574
    m_verbose = b;
 
575
  }
 
576
 
 
577
  /**
 
578
   * Get whether output is to be verbose
 
579
   *
 
580
   * @return true if output will be verbose
 
581
   */
 
582
  public boolean getVerbose() {
 
583
    return m_verbose;
 
584
  }
 
585
 
 
586
  /**
 
587
   * Gets the current settings of LinearForwardSelection.
 
588
   *
 
589
   * @return an array of strings suitable for passing to setOptions()
 
590
   */
 
591
  public String[] getOptions() {
 
592
    String[] evaluatorOptions = new String[0];
 
593
 
 
594
    if ((m_setSizeEval != null) && (m_setSizeEval instanceof OptionHandler)) {
 
595
      evaluatorOptions = ((OptionHandler) m_setSizeEval).getOptions();
 
596
    }
 
597
 
 
598
    String[] options = new String[15 + evaluatorOptions.length];
 
599
    int current = 0;
 
600
 
 
601
    if (m_performRanking) {
 
602
      options[current++] = "-I";
 
603
    }
 
604
 
 
605
    options[current++] = "-K";
 
606
    options[current++] = "" + m_numUsedAttributes;
 
607
    options[current++] = "-T";
 
608
    options[current++] = "" + m_linearSelectionType;
 
609
 
 
610
    options[current++] = "-F";
 
611
    options[current++] = "" + m_numFolds;
 
612
    options[current++] = "-S";
 
613
    options[current++] = "" + m_seed;
 
614
 
 
615
    options[current++] = "-Z";
 
616
    options[current++] = "" + m_verbose;
 
617
 
 
618
    if (m_setSizeEval != null) {
 
619
      options[current++] = "-E";
 
620
      options[current++] = m_setSizeEval.getClass().getName();
 
621
    }
 
622
 
 
623
    options[current++] = "--";
 
624
    System.arraycopy(evaluatorOptions, 0, options, current,
 
625
                     evaluatorOptions.length);
 
626
    current += evaluatorOptions.length;
 
627
 
 
628
    while (current < options.length) {
 
629
      options[current++] = "";
 
630
    }
 
631
 
 
632
    return options;
 
633
  }
 
634
 
 
635
  /**
 
636
   * returns a description of the search as a String
 
637
   *
 
638
   * @return a description of the search
 
639
   */
 
640
  public String toString() {
 
641
    StringBuffer LFSString = new StringBuffer();
 
642
 
 
643
    LFSString.append("\tSubset Size Forward Selection.\n");
 
644
 
 
645
    LFSString.append("\tLinear Forward Selection Type: ");
 
646
 
 
647
    if (m_linearSelectionType == TYPE_FIXED_SET) {
 
648
      LFSString.append("fixed-set\n");
 
649
    } else {
 
650
      LFSString.append("fixed-width\n");
 
651
    }
 
652
 
 
653
    LFSString.append("\tNumber of top-ranked attributes that are used: " +
 
654
                     m_numUsedAttributes + "\n");
 
655
 
 
656
    LFSString.append(
 
657
                     "\tNumber of cross validation folds for subset size determination: " +
 
658
                     m_numFolds + "\n");
 
659
    LFSString.append("\tSeed for cross validation subset size determination: " +
 
660
                     m_seed + "\n");
 
661
 
 
662
    LFSString.append("\tTotal number of subsets evaluated: " + m_totalEvals +
 
663
                     "\n");
 
664
    LFSString.append("\tMerit of best subset found: " +
 
665
                     Utils.doubleToString(Math.abs(m_bestMerit), 8, 3) + "\n");
 
666
 
 
667
    return LFSString.toString();
 
668
  }
 
669
 
 
670
  /**
 
671
   * Searches the attribute subset space by subset size forward selection
 
672
   *
 
673
   * @param ASEvaluator
 
674
   *            the attribute evaluator to guide the search
 
675
   * @param data
 
676
   *            the training instances.
 
677
   * @return an array (not necessarily ordered) of selected attribute indexes
 
678
   * @exception Exception
 
679
   *                if the search can't be completed
 
680
   */
 
681
  public int[] search(ASEvaluation ASEval, Instances data)
 
682
    throws Exception {
 
683
    m_totalEvals = 0;
 
684
 
 
685
    if (!(ASEval instanceof SubsetEvaluator)) {
 
686
      throw new Exception(ASEval.getClass().getName() + " is not a " +
 
687
                          "Subset evaluator!");
 
688
    }
 
689
 
 
690
    if (m_setSizeEval == null) {
 
691
      m_setSizeEval = (SubsetEvaluator) ASEval;
 
692
    }
 
693
 
 
694
    m_numAttribs = data.numAttributes();
 
695
 
 
696
    if (m_numUsedAttributes > m_numAttribs) {
 
697
      System.out.println(
 
698
                         "Decreasing number of top-ranked attributes to total number of attributes: " +
 
699
                         data.numAttributes());
 
700
      m_numUsedAttributes = m_numAttribs;
 
701
    }
 
702
 
 
703
    Instances[] trainData = new Instances[m_numFolds];
 
704
    Instances[] testData = new Instances[m_numFolds];
 
705
    LFSMethods[] searchResults = new LFSMethods[m_numFolds];
 
706
 
 
707
    Random random = new Random(m_seed);
 
708
    Instances dataCopy = new Instances(data);
 
709
    dataCopy.randomize(random);
 
710
 
 
711
    if (dataCopy.classAttribute().isNominal()) {
 
712
      dataCopy.stratify(m_numFolds);
 
713
    }
 
714
 
 
715
    for (int f = 0; f < m_numFolds; f++) {
 
716
      trainData[f] = dataCopy.trainCV(m_numFolds, f, random);
 
717
      testData[f] = dataCopy.testCV(m_numFolds, f);
 
718
    }
 
719
 
 
720
    LFSMethods LSF = new LFSMethods();
 
721
 
 
722
    int[] ranking;
 
723
 
 
724
    if (m_performRanking) {
 
725
      ((SubsetEvaluator) ASEval).buildEvaluator(data);
 
726
      ranking = LSF.rankAttributes(data, (SubsetEvaluator) ASEval, m_verbose);
 
727
    } else {
 
728
      ranking = new int[m_numAttribs];
 
729
 
 
730
      for (int i = 0; i < ranking.length; i++) {
 
731
        ranking[i] = i;
 
732
      }
 
733
    }
 
734
 
 
735
    int maxSubsetSize = 0;
 
736
 
 
737
    for (int f = 0; f < m_numFolds; f++) {
 
738
      if (m_verbose) {
 
739
        System.out.println("perform search on internal fold: " + (f + 1) + "/" +
 
740
                           m_numFolds);
 
741
      }
 
742
 
 
743
      m_setSizeEval.buildEvaluator(trainData[f]);
 
744
      searchResults[f] = new LFSMethods();
 
745
      searchResults[f].forwardSearch(m_cacheSize, new BitSet(m_numAttribs),
 
746
                                     ranking, m_numUsedAttributes,
 
747
                                     m_linearSelectionType == TYPE_FIXED_WIDTH, 1, -1, trainData[f],
 
748
                                     m_setSizeEval, m_verbose);
 
749
 
 
750
      maxSubsetSize = Math.max(maxSubsetSize,
 
751
                               searchResults[f].getBestGroup().cardinality());
 
752
    }
 
753
 
 
754
    if (m_verbose) {
 
755
      System.out.println(
 
756
                         "continue searches on internal folds to maxSubsetSize (" +
 
757
                         maxSubsetSize + ")");
 
758
    }
 
759
 
 
760
    for (int f = 0; f < m_numFolds; f++) {
 
761
      if (m_verbose) {
 
762
        System.out.print("perform search on internal fold: " + (f + 1) + "/" +
 
763
                         m_numFolds + " with starting set ");
 
764
        LFSMethods.printGroup(searchResults[f].getBestGroup(),
 
765
                              trainData[f].numAttributes());
 
766
      }
 
767
 
 
768
      if (searchResults[f].getBestGroup().cardinality() < maxSubsetSize) {
 
769
        m_setSizeEval.buildEvaluator(trainData[f]);
 
770
        searchResults[f].forwardSearch(m_cacheSize,
 
771
                                       searchResults[f].getBestGroup(), ranking, m_numUsedAttributes,
 
772
                                       m_linearSelectionType == TYPE_FIXED_WIDTH, 1, maxSubsetSize,
 
773
                                       trainData[f], m_setSizeEval, m_verbose);
 
774
      }
 
775
    }
 
776
 
 
777
    double[][] testMerit = new double[m_numFolds][maxSubsetSize + 1];
 
778
 
 
779
    for (int f = 0; f < m_numFolds; f++) {
 
780
      for (int s = 1; s <= maxSubsetSize; s++) {
 
781
        if (HoldOutSubsetEvaluator.class.isInstance(m_setSizeEval)) {
 
782
          m_setSizeEval.buildEvaluator(trainData[f]);
 
783
          testMerit[f][s] = ((HoldOutSubsetEvaluator) m_setSizeEval).evaluateSubset(searchResults[f].getBestGroupOfSize(
 
784
                                                                                                                        s), testData[f]);
 
785
        } else {
 
786
          m_setSizeEval.buildEvaluator(testData[f]);
 
787
          testMerit[f][s] = m_setSizeEval.evaluateSubset(searchResults[f].getBestGroupOfSize(
 
788
                                                                                             s));
 
789
        }
 
790
      }
 
791
    }
 
792
 
 
793
    double[] avgTestMerit = new double[maxSubsetSize + 1];
 
794
    int finalSubsetSize = -1;
 
795
 
 
796
    for (int s = 1; s <= maxSubsetSize; s++) {
 
797
      for (int f = 0; f < m_numFolds; f++) {
 
798
        avgTestMerit[s] = ((avgTestMerit[s] * f) + testMerit[f][s]) / (double) (f +
 
799
                                                                                1);
 
800
      }
 
801
 
 
802
      if ((finalSubsetSize == -1) ||
 
803
          (avgTestMerit[s] > avgTestMerit[finalSubsetSize])) {
 
804
        finalSubsetSize = s;
 
805
      }
 
806
 
 
807
      if (m_verbose) {
 
808
        System.out.println("average merit for subset-size " + s + ": " +
 
809
                           avgTestMerit[s]);
 
810
      }
 
811
    }
 
812
 
 
813
    if (m_verbose) {
 
814
      System.out.println("performing final forward selection to subset-size: " +
 
815
                         finalSubsetSize);
 
816
    }
 
817
 
 
818
    ((SubsetEvaluator) ASEval).buildEvaluator(data);
 
819
    LSF.forwardSearch(m_cacheSize, new BitSet(m_numAttribs), ranking,
 
820
                      m_numUsedAttributes, m_linearSelectionType == TYPE_FIXED_WIDTH, 1,
 
821
                      finalSubsetSize, data, (SubsetEvaluator) ASEval, m_verbose);
 
822
 
 
823
    m_totalEvals = LSF.getNumEvalsTotal();
 
824
    m_bestMerit = LSF.getBestMerit();
 
825
 
 
826
    return attributeList(LSF.getBestGroup());
 
827
  }
 
828
 
 
829
  /**
 
830
   * Reset options to default values
 
831
   */
 
832
  protected void resetOptions() {
 
833
    m_performRanking = true;
 
834
    m_numUsedAttributes = 50;
 
835
    m_linearSelectionType = TYPE_FIXED_SET;
 
836
    m_setSizeEval = new ClassifierSubsetEval();
 
837
    m_numFolds = 5;
 
838
    m_seed = 1;
 
839
    m_totalEvals = 0;
 
840
    m_cacheSize = 1;
 
841
    m_verbose = false;
 
842
  }
 
843
 
 
844
  /**
 
845
   * converts a BitSet into a list of attribute indexes
 
846
   *
 
847
   * @param group
 
848
   *            the BitSet to convert
 
849
   * @return an array of attribute indexes
 
850
   */
 
851
  protected int[] attributeList(BitSet group) {
 
852
    int count = 0;
 
853
 
 
854
    // count how many were selected
 
855
    for (int i = 0; i < m_numAttribs; i++) {
 
856
      if (group.get(i)) {
 
857
        count++;
 
858
      }
 
859
    }
 
860
 
 
861
    int[] list = new int[count];
 
862
    count = 0;
 
863
 
 
864
    for (int i = 0; i < m_numAttribs; i++) {
 
865
      if (group.get(i)) {
 
866
        list[count++] = i;
 
867
      }
 
868
    }
 
869
 
 
870
    return list;
 
871
  }
 
872
}