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.
18
* VotedPerceptron.java
19
* Copyright (C) 1999 University of Waikato, Hamilton, New Zealand
24
package weka.classifiers.functions;
26
import weka.classifiers.Classifier;
27
import weka.core.Capabilities;
28
import weka.core.Instance;
29
import weka.core.Instances;
30
import weka.core.Option;
31
import weka.core.OptionHandler;
32
import weka.core.TechnicalInformation;
33
import weka.core.TechnicalInformationHandler;
34
import weka.core.Utils;
35
import weka.core.Capabilities.Capability;
36
import weka.core.TechnicalInformation.Field;
37
import weka.core.TechnicalInformation.Type;
38
import weka.filters.Filter;
39
import weka.filters.unsupervised.attribute.NominalToBinary;
40
import weka.filters.unsupervised.attribute.ReplaceMissingValues;
42
import java.util.Enumeration;
43
import java.util.Random;
44
import java.util.Vector;
47
<!-- globalinfo-start -->
48
* Implementation of the voted perceptron algorithm by Freund and Schapire. Globally replaces all missing values, and transforms nominal attributes into binary ones.<br/>
50
* For more information, see:<br/>
52
* Y. Freund, R. E. Schapire: Large margin classification using the perceptron algorithm. In: 11th Annual Conference on Computational Learning Theory, New York, NY, 209-217, 1998.
54
<!-- globalinfo-end -->
56
<!-- technical-bibtex-start -->
59
* @inproceedings{Freund1998,
60
* address = {New York, NY},
61
* author = {Y. Freund and R. E. Schapire},
62
* booktitle = {11th Annual Conference on Computational Learning Theory},
64
* publisher = {ACM Press},
65
* title = {Large margin classification using the perceptron algorithm},
70
<!-- technical-bibtex-end -->
72
<!-- options-start -->
73
* Valid options are: <p/>
75
* <pre> -I <int>
76
* The number of iterations to be performed.
79
* <pre> -E <double>
80
* The exponent for the polynomial kernel.
83
* <pre> -S <int>
84
* The seed for the random number generation.
87
* <pre> -M <int>
88
* The maximum number of alterations allowed.
89
* (default 10000)</pre>
93
* @author Eibe Frank (eibe@cs.waikato.ac.nz)
94
* @version $Revision: 1.22 $
96
public class VotedPerceptron
98
implements OptionHandler, TechnicalInformationHandler {
100
/** for serialization */
101
static final long serialVersionUID = -1072429260104568698L;
103
/** The maximum number of alterations to the perceptron */
104
private int m_MaxK = 10000;
106
/** The number of iterations */
107
private int m_NumIterations = 1;
110
private double m_Exponent = 1.0;
112
/** The actual number of alterations */
115
/** The training instances added to the perceptron */
116
private int[] m_Additions = null;
118
/** Addition or subtraction? */
119
private boolean[] m_IsAddition = null;
121
/** The weights for each perceptron */
122
private int[] m_Weights = null;
124
/** The training instances */
125
private Instances m_Train = null;
127
/** Seed used for shuffling the dataset */
128
private int m_Seed = 1;
130
/** The filter used to make attributes numeric. */
131
private NominalToBinary m_NominalToBinary;
133
/** The filter used to get rid of missing values. */
134
private ReplaceMissingValues m_ReplaceMissingValues;
137
* Returns a string describing this classifier
138
* @return a description of the classifier suitable for
139
* displaying in the explorer/experimenter gui
141
public String globalInfo() {
143
"Implementation of the voted perceptron algorithm by Freund and "
144
+ "Schapire. Globally replaces all missing values, and transforms "
145
+ "nominal attributes into binary ones.\n\n"
146
+ "For more information, see:\n\n"
147
+ getTechnicalInformation().toString();
151
* Returns an instance of a TechnicalInformation object, containing
152
* detailed information about the technical background of this class,
153
* e.g., paper reference or book this class is based on.
155
* @return the technical information about this class
157
public TechnicalInformation getTechnicalInformation() {
158
TechnicalInformation result;
160
result = new TechnicalInformation(Type.INPROCEEDINGS);
161
result.setValue(Field.AUTHOR, "Y. Freund and R. E. Schapire");
162
result.setValue(Field.TITLE, "Large margin classification using the perceptron algorithm");
163
result.setValue(Field.BOOKTITLE, "11th Annual Conference on Computational Learning Theory");
164
result.setValue(Field.YEAR, "1998");
165
result.setValue(Field.PAGES, "209-217");
166
result.setValue(Field.PUBLISHER, "ACM Press");
167
result.setValue(Field.ADDRESS, "New York, NY");
173
* Returns an enumeration describing the available options.
175
* @return an enumeration of all the available options.
177
public Enumeration listOptions() {
179
Vector newVector = new Vector(4);
181
newVector.addElement(new Option("\tThe number of iterations to be performed.\n"
183
"I", 1, "-I <int>"));
184
newVector.addElement(new Option("\tThe exponent for the polynomial kernel.\n"
186
"E", 1, "-E <double>"));
187
newVector.addElement(new Option("\tThe seed for the random number generation.\n"
189
"S", 1, "-S <int>"));
190
newVector.addElement(new Option("\tThe maximum number of alterations allowed.\n"
191
+ "\t(default 10000)",
192
"M", 1, "-M <int>"));
194
return newVector.elements();
198
* Parses a given list of options. <p/>
200
<!-- options-start -->
201
* Valid options are: <p/>
203
* <pre> -I <int>
204
* The number of iterations to be performed.
207
* <pre> -E <double>
208
* The exponent for the polynomial kernel.
211
* <pre> -S <int>
212
* The seed for the random number generation.
215
* <pre> -M <int>
216
* The maximum number of alterations allowed.
217
* (default 10000)</pre>
221
* @param options the list of options as an array of strings
222
* @throws Exception if an option is not supported
224
public void setOptions(String[] options) throws Exception {
226
String iterationsString = Utils.getOption('I', options);
227
if (iterationsString.length() != 0) {
228
m_NumIterations = Integer.parseInt(iterationsString);
232
String exponentsString = Utils.getOption('E', options);
233
if (exponentsString.length() != 0) {
234
m_Exponent = (new Double(exponentsString)).doubleValue();
238
String seedString = Utils.getOption('S', options);
239
if (seedString.length() != 0) {
240
m_Seed = Integer.parseInt(seedString);
244
String alterationsString = Utils.getOption('M', options);
245
if (alterationsString.length() != 0) {
246
m_MaxK = Integer.parseInt(alterationsString);
253
* Gets the current settings of the classifier.
255
* @return an array of strings suitable for passing to setOptions
257
public String[] getOptions() {
259
String[] options = new String [8];
262
options[current++] = "-I"; options[current++] = "" + m_NumIterations;
263
options[current++] = "-E"; options[current++] = "" + m_Exponent;
264
options[current++] = "-S"; options[current++] = "" + m_Seed;
265
options[current++] = "-M"; options[current++] = "" + m_MaxK;
266
while (current < options.length) {
267
options[current++] = "";
273
* Returns default capabilities of the classifier.
275
* @return the capabilities of this classifier
277
public Capabilities getCapabilities() {
278
Capabilities result = super.getCapabilities();
281
result.enable(Capability.NOMINAL_ATTRIBUTES);
282
result.enable(Capability.NUMERIC_ATTRIBUTES);
283
result.enable(Capability.DATE_ATTRIBUTES);
284
result.enable(Capability.MISSING_VALUES);
287
result.enable(Capability.BINARY_CLASS);
288
result.enable(Capability.MISSING_CLASS_VALUES);
291
result.setMinimumNumberInstances(0);
297
* Builds the ensemble of perceptrons.
299
* @param insts the data to train the classifier with
300
* @throws Exception if something goes wrong during building
302
public void buildClassifier(Instances insts) throws Exception {
304
// can classifier handle the data?
305
getCapabilities().testWithFail(insts);
307
// remove instances with missing class
308
insts = new Instances(insts);
309
insts.deleteWithMissingClass();
312
m_Train = new Instances(insts);
313
m_ReplaceMissingValues = new ReplaceMissingValues();
314
m_ReplaceMissingValues.setInputFormat(m_Train);
315
m_Train = Filter.useFilter(m_Train, m_ReplaceMissingValues);
317
m_NominalToBinary = new NominalToBinary();
318
m_NominalToBinary.setInputFormat(m_Train);
319
m_Train = Filter.useFilter(m_Train, m_NominalToBinary);
321
/** Randomize training data */
322
m_Train.randomize(new Random(m_Seed));
324
/** Make space to store perceptrons */
325
m_Additions = new int[m_MaxK + 1];
326
m_IsAddition = new boolean[m_MaxK + 1];
327
m_Weights = new int[m_MaxK + 1];
329
/** Compute perceptrons */
332
for (int it = 0; it < m_NumIterations; it++) {
333
for (int i = 0; i < m_Train.numInstances(); i++) {
334
Instance inst = m_Train.instance(i);
335
if (!inst.classIsMissing()) {
336
int prediction = makePrediction(m_K, inst);
337
int classValue = (int) inst.classValue();
338
if (prediction == classValue) {
341
m_IsAddition[m_K] = (classValue == 1);
342
m_Additions[m_K] = i;
355
* Outputs the distribution for the given output.
357
* Pipes output of SVM through sigmoid function.
358
* @param inst the instance for which distribution is to be computed
359
* @return the distribution
360
* @throws Exception if something goes wrong
362
public double[] distributionForInstance(Instance inst) throws Exception {
365
m_ReplaceMissingValues.input(inst);
366
m_ReplaceMissingValues.batchFinished();
367
inst = m_ReplaceMissingValues.output();
369
m_NominalToBinary.input(inst);
370
m_NominalToBinary.batchFinished();
371
inst = m_NominalToBinary.output();
374
double output = 0, sumSoFar = 0;
376
for (int i = 0; i <= m_K; i++) {
378
output -= m_Weights[i];
380
output += m_Weights[i];
382
if (m_IsAddition[i]) {
383
sumSoFar += innerProduct(m_Train.instance(m_Additions[i]), inst);
385
sumSoFar -= innerProduct(m_Train.instance(m_Additions[i]), inst);
389
double[] result = new double[2];
390
result[1] = 1 / (1 + Math.exp(-output));
391
result[0] = 1 - result[1];
397
* Returns textual description of classifier.
399
* @return the model as string
401
public String toString() {
403
return "VotedPerceptron: Number of perceptrons=" + m_K;
407
* Returns the tip text for this property
408
* @return tip text for this property suitable for
409
* displaying in the explorer/experimenter gui
411
public String maxKTipText() {
412
return "The maximum number of alterations to the perceptron.";
416
* Get the value of maxK.
418
* @return Value of maxK.
420
public int getMaxK() {
426
* Set the value of maxK.
428
* @param v Value to assign to maxK.
430
public void setMaxK(int v) {
436
* Returns the tip text for this property
437
* @return tip text for this property suitable for
438
* displaying in the explorer/experimenter gui
440
public String numIterationsTipText() {
441
return "Number of iterations to be performed.";
445
* Get the value of NumIterations.
447
* @return Value of NumIterations.
449
public int getNumIterations() {
451
return m_NumIterations;
455
* Set the value of NumIterations.
457
* @param v Value to assign to NumIterations.
459
public void setNumIterations(int v) {
465
* Returns the tip text for this property
466
* @return tip text for this property suitable for
467
* displaying in the explorer/experimenter gui
469
public String exponentTipText() {
470
return "Exponent for the polynomial kernel.";
474
* Get the value of exponent.
476
* @return Value of exponent.
478
public double getExponent() {
484
* Set the value of exponent.
486
* @param v Value to assign to exponent.
488
public void setExponent(double v) {
494
* Returns the tip text for this property
495
* @return tip text for this property suitable for
496
* displaying in the explorer/experimenter gui
498
public String seedTipText() {
499
return "Seed for the random number generator.";
503
* Get the value of Seed.
505
* @return Value of Seed.
507
public int getSeed() {
513
* Set the value of Seed.
515
* @param v Value to assign to Seed.
517
public void setSeed(int v) {
523
* Computes the inner product of two instances
525
* @param i1 first instance
526
* @param i2 second instance
527
* @return the inner product
528
* @throws Exception if computation fails
530
private double innerProduct(Instance i1, Instance i2) throws Exception {
532
// we can do a fast dot product
534
int n1 = i1.numValues(); int n2 = i2.numValues();
535
int classIndex = m_Train.classIndex();
536
for (int p1 = 0, p2 = 0; p1 < n1 && p2 < n2;) {
537
int ind1 = i1.index(p1);
538
int ind2 = i2.index(p2);
540
if (ind1 != classIndex) {
541
result += i1.valueSparse(p1) *
545
} else if (ind1 > ind2) {
553
if (m_Exponent != 1) {
554
return Math.pow(result, m_Exponent);
561
* Compute a prediction from a perceptron
564
* @param inst the instance to make a prediction for
565
* @return the prediction
566
* @throws Exception if computation fails
568
private int makePrediction(int k, Instance inst) throws Exception {
571
for (int i = 0; i < k; i++) {
572
if (m_IsAddition[i]) {
573
result += innerProduct(m_Train.instance(m_Additions[i]), inst);
575
result -= innerProduct(m_Train.instance(m_Additions[i]), inst);
588
* @param argv the commandline options
590
public static void main(String[] argv) {
591
runClassifier(new VotedPerceptron(), argv);
added
removed
weka/classifiers/functions/VotedPerceptron.java
