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) 2004 Stijn Lievens
23
package weka.classifiers.misc;
25
import weka.classifiers.RandomizableClassifier;
26
import weka.classifiers.misc.monotone.Coordinates;
27
import weka.classifiers.misc.monotone.DiscreteDistribution;
28
import weka.classifiers.misc.monotone.EnumerationIterator;
29
import weka.classifiers.misc.monotone.InstancesComparator;
30
import weka.classifiers.misc.monotone.InstancesUtil;
31
import weka.classifiers.misc.monotone.MultiDimensionalSort;
32
import weka.core.Attribute;
33
import weka.core.Capabilities;
34
import weka.core.FastVector;
35
import weka.core.Instance;
36
import weka.core.Instances;
37
import weka.core.Option;
38
import weka.core.SelectedTag;
40
import weka.core.TechnicalInformation;
41
import weka.core.TechnicalInformationHandler;
42
import weka.core.Utils;
43
import weka.core.Capabilities.Capability;
44
import weka.core.TechnicalInformation.Field;
45
import weka.core.TechnicalInformation.Type;
46
import weka.estimators.DiscreteEstimator;
48
import java.util.ArrayList;
49
import java.util.Comparator;
50
import java.util.Enumeration;
51
import java.util.HashMap;
52
import java.util.Iterator;
54
import java.util.Random;
55
import java.util.Vector;
58
<!-- globalinfo-start -->
59
* This class is an implementation of the Ordinal Learning Method<br/>
60
* Further information regarding the algorithm and variants can be found in:<br/>
62
* Arie Ben-David (1992). Automatic Generation of Symbolic Multiattribute Ordinal Knowledge-Based DSSs: methodology and Applications. Decision Sciences. 23:1357-1372.<br/>
64
* Lievens, Stijn (2003-2004). Studie en implementatie van instantie-gebaseerde algoritmen voor gesuperviseerd rangschikken..
66
<!-- globalinfo-end -->
68
<!-- technical-bibtex-start -->
71
* @article{Ben-David1992,
72
* author = {Arie Ben-David},
73
* journal = {Decision Sciences},
74
* pages = {1357-1372},
75
* title = {Automatic Generation of Symbolic Multiattribute Ordinal Knowledge-Based DSSs: methodology and Applications},
80
* @mastersthesis{Lievens2003-2004,
81
* author = {Lievens, Stijn},
82
* school = {Ghent University},
83
* title = {Studie en implementatie van instantie-gebaseerde algoritmen voor gesuperviseerd rangschikken.},
88
<!-- technical-bibtex-end -->
90
<!-- options-start -->
91
* Valid options are: <p/>
93
* <pre> -S <num>
98
* If set, classifier is run in debug mode and
99
* may output additional info to the console</pre>
101
* <pre> -C <CL|REG>
102
* Sets the classification type to be used.
103
* (Default: REG)</pre>
105
* <pre> -A <MEAN|MED|MAX>
106
* Sets the averaging type used in phase 1 of the classifier.
107
* (Default: MEAN)</pre>
109
* <pre> -N <NONE|EUCL|HAM>
110
* If different from NONE, a nearest neighbour rule is fired when the
111
* rule base doesn't contain an example smaller than the instance
113
* (Default: NONE).</pre>
115
* <pre> -E <MIN|MAX|BOTH>
116
* Sets the extension type, i.e. the rule base to use.
117
* (Default: MIN)</pre>
120
* If set, the instances are also sorted within the same class
121
* before building the rule bases</pre>
125
* @author Stijn Lievens (stijn.lievens@ugent.be)
126
* @version $Revision: 1.1 $
129
extends RandomizableClassifier
130
implements TechnicalInformationHandler {
132
/** for serialization */
133
private static final long serialVersionUID = 3722951802290935192L;
136
* Round the real value that is returned by the original algorithm
137
* to the nearest label.
139
public static final int CT_ROUNDED = 0;
142
* No rounding is performed during classification, this is the
143
* classification is done in a regression like way.
145
public static final int CT_REAL = 1;
147
/** the classification types */
148
public static final Tag[] TAGS_CLASSIFICATIONTYPES = {
149
new Tag(CT_ROUNDED, "CL", "Round to nearest label"),
150
new Tag(CT_REAL, "REG", "Regression-like classification")
154
* Use the mean for averaging in phase 1. This is in fact a
155
* non ordinal procedure. The scores used for averaging are the internal
158
public static final int AT_MEAN = 0;
161
* Use the median for averaging in phase 1. The possible values
162
* are in the extended set of labels, this is labels in between the
163
* original labels are possible.
165
public static final int AT_MEDIAN = 1;
168
* Use the mode for averaging in phase 1. The label
169
* that has maximum frequency is used. If there is more
170
* than one label that has maximum frequency, the lowest
173
public static final int AT_MAXPROB = 2;
175
/** the averaging types */
176
public static final Tag[] TAGS_AVERAGINGTYPES = {
177
new Tag(AT_MEAN, "MEAN", "Mean"),
178
new Tag(AT_MEDIAN, "MED","Median"),
179
new Tag(AT_MAXPROB, "MAX", "Max probability")
183
* No nearest neighbour rule will be fired when
184
* classifying an instance for which there is no smaller rule
187
public static final int DT_NONE = -1;
190
* Use the Euclidian distance whenever a nearest neighbour
193
public static final int DT_EUCLID = 0;
196
* Use the Hamming distance, this is the number of
197
* positions in which the instances differ, whenever a
198
* nearest neighbour rule is fired
200
public static final int DT_HAMMING = 1;
202
/** the distance types */
203
public static final Tag[] TAGS_DISTANCETYPES = {
204
new Tag(DT_NONE, "NONE", "No nearest neighbor"),
205
new Tag(DT_EUCLID, "EUCL", "Euclidean"),
206
new Tag(DT_HAMMING, "HAM", "Hamming")
210
* Use only the minimal extension, as in the original algorithm
213
public static final int ET_MIN = 0;
216
* Use only the maximal extension. In this case an algorithm
217
* dual to the original one is performed.
219
public static final int ET_MAX = 1;
222
* Combine both the minimal and maximal extension, and use the
223
* midpoint of the resulting interval as prediction.
225
public static final int ET_BOTH = 2;
227
/** the mode types */
228
public static final Tag[] TAGS_EXTENSIONTYPES = {
229
new Tag(ET_MIN, "MIN", "Minimal extension"),
230
new Tag(ET_MAX, "MAX", "Maximal extension"),
231
new Tag(ET_BOTH, "BOTH", "Minimal and maximal extension")
235
* The training examples, used temporarily.
236
* m_train is cleared after the rule base is built.
238
private Instances m_train;
240
/** Number of classes in the original m_train */
241
private int m_numClasses;
244
* The rule base, should be consistent and contain no
245
* redundant rules. This is the rule base as in the original
246
* algorithm of Ben-David.
248
private Instances m_baseMin;
251
* This is a complentary rule base, using the maximal rather
252
* than the minimal extension.
254
private Instances m_baseMax;
257
* Map used in the method buildClassifier in order to quickly
258
* gather all info needed for phase 1. This is a map containing
259
* (Coordinates, DiscreteEstimator)-pairs.
261
private Map m_estimatedDistributions;
263
/** classification type */
264
private int m_ctype = CT_REAL;
266
/** averaging type */
267
private int m_atype = AT_MEAN;
270
private int m_dtype = DT_EUCLID;
273
private int m_etype = ET_MIN;
276
* Should the instances be sorted such that minimal (resp. maximal)
277
* elements (per class) are treated first when building m_baseMin
280
private boolean m_sort = false;
283
* Returns a string describing the classifier.
284
* @return a description suitable for displaying in the
285
* explorer/experimenter gui
287
public String globalInfo() {
288
return "This class is an implementation of the Ordinal Learning "
290
+ "Further information regarding the algorithm and variants "
291
+ "can be found in:\n\n"
292
+ getTechnicalInformation().toString();
296
* Returns default capabilities of the classifier.
298
* @return the capabilities of this classifier
300
public Capabilities getCapabilities() {
301
Capabilities result = super.getCapabilities();
304
result.enable(Capability.NOMINAL_ATTRIBUTES);
307
result.enable(Capability.NOMINAL_CLASS);
308
result.enable(Capability.MISSING_CLASS_VALUES);
311
result.setMinimumNumberInstances(0);
317
* Returns an instance of a TechnicalInformation object, containing
318
* detailed information about the technical background of this class,
319
* e.g., paper reference or book this class is based on.
321
* @return the technical information about this class
323
public TechnicalInformation getTechnicalInformation() {
324
TechnicalInformation result;
325
TechnicalInformation additional;
327
result = new TechnicalInformation(Type.ARTICLE);
328
result.setValue(Field.AUTHOR, "Arie Ben-David");
329
result.setValue(Field.YEAR, "1992");
330
result.setValue(Field.TITLE, "Automatic Generation of Symbolic Multiattribute Ordinal Knowledge-Based DSSs: methodology and Applications");
331
result.setValue(Field.JOURNAL, "Decision Sciences");
332
result.setValue(Field.PAGES, "1357-1372");
333
result.setValue(Field.VOLUME, "23");
335
additional = result.add(Type.MASTERSTHESIS);
336
additional.setValue(Field.AUTHOR, "Lievens, Stijn");
337
additional.setValue(Field.YEAR, "2003-2004");
338
additional.setValue(Field.TITLE, "Studie en implementatie van instantie-gebaseerde algoritmen voor gesuperviseerd rangschikken.");
339
additional.setValue(Field.SCHOOL, "Ghent University");
345
* Returns the tip text for this property.
347
* @return tip text for this property suitable for
348
* displaying in the explorer/experimenter gui
350
public String classificationTypeTipText() {
351
return "Sets the classification type.";
355
* Sets the classification type.
357
* @param value the classification type to be set.
359
public void setClassificationType(SelectedTag value) {
360
if (value.getTags() == TAGS_CLASSIFICATIONTYPES)
361
m_ctype = value.getSelectedTag().getID();
365
* Gets the classification type.
367
* @return the classification type
369
public SelectedTag getClassificationType() {
370
return new SelectedTag(m_ctype, TAGS_CLASSIFICATIONTYPES);
374
* Returns the tip text for this property.
376
* @return tip text for this property suitable for
377
* displaying in the explorer/experimenter gui
379
public String averagingTypeTipText() {
380
return "Choses the way in which the distributions are averaged in "
381
+ "the first phase of the algorithm.";
385
* Sets the averaging type to use in phase 1 of the algorithm.
387
* @param value the averaging type to use
389
public void setAveragingType(SelectedTag value) {
390
if (value.getTags() == TAGS_AVERAGINGTYPES)
391
m_atype = value.getSelectedTag().getID();
395
* Gets the averaging type.
397
* @return the averaging type
399
public SelectedTag getAveragingType() {
400
return new SelectedTag(m_atype, TAGS_AVERAGINGTYPES);
404
* Returns the tip text for this property.
406
* @return tip text for this property suitable for
407
* displaying in the explorer/experimenter gui
409
public String distanceTypeTipText() {
410
return "Sets the distance that is to be used by the nearest neighbour "
415
* Sets the distance type to be used by a nearest neighbour rule (if any).
417
* @param value the distance type to use
419
public void setDistanceType(SelectedTag value) {
420
if (value.getTags() == TAGS_DISTANCETYPES)
421
m_dtype = value.getSelectedTag().getID();
425
* Gets the distance type used by a nearest neighbour rule (if any).
427
* @return the distance type
429
public SelectedTag getDistanceType() {
430
return new SelectedTag(m_dtype, TAGS_DISTANCETYPES);
434
* Returns the tip text for this property.
436
* @return tip text for this property suitable for
437
* displaying in the explorer/experimenter gui
439
public String extensionTypeTipText() {
440
return "Sets the extension type to use.";
444
* Sets the extension type to use.
445
* The minimal extension is the one used by
446
* Ben-David in the original algorithm. The maximal extension is
447
* a completely dual variant of the minimal extension. When using
448
* both, then the midpoint of the interval determined by both
449
* extensions is returned.
451
* @param value the extension type to use
453
public void setExtensionType(SelectedTag value) {
454
if (value.getTags() == TAGS_EXTENSIONTYPES)
455
m_etype = value.getSelectedTag().getID();
459
* Gets the extension type.
461
* @return the extension type
463
public SelectedTag getExtensionType() {
464
return new SelectedTag(m_etype, TAGS_EXTENSIONTYPES);
468
* Returns the tip text for this property.
470
* @return tip text for this property suitable for
471
* displaying in the explorer/experimenter gui
473
public String sortTipText() {
474
return "If true, the instances are also sorted within the classes "
475
+ "prior to building the rule bases.";
479
* Sets if the instances are to be sorted prior to building the rule bases.
481
* @param sort if <code> true </code> the instances will be sorted
483
public void setSort(boolean sort) {
488
* Returns if the instances are sorted prior to building the rule bases.
490
* @return <code> true </code> if instances are sorted prior to building
491
* the rule bases, <code> false </code> otherwise.
493
public boolean getSort() {
498
* Returns the tip text for this property.
500
* @return tip text for this property suitable for
501
* displaying in the explorer/experimenter gui
503
public String seedTipText() {
504
return "Sets the seed that is used to randomize the instances prior "
505
+ "to building the rule bases";
509
* Return the number of examples in the minimal rule base.
510
* The minimal rule base is the one that corresponds to the
511
* rule base of Ben-David.
513
* @return the number of examples in the minimal rule base
515
public int getSizeRuleBaseMin() {
516
return m_baseMin.numInstances();
520
* Return the number of examples in the maximal rule base.
521
* The maximal rule base is built using an algorithm
522
* dual to that for building the minimal rule base.
524
* @return the number of examples in the maximal rule base
526
public int getSizeRuleBaseMax() {
527
return m_baseMax.numInstances();
531
* Classifies a given instance according to the current settings
534
* @param instance the instance to be classified
535
* @return a <code> double </code> that represents the classification,
536
* this could either be the internal value of a label, when rounding is
537
* on, or a real number.
539
public double classifyInstance(Instance instance) {
540
double classValueMin = -1;
541
double classValueMax = -1;
544
if (m_etype == ET_MIN || m_etype == ET_BOTH) {
545
classValueMin = classifyInstanceMin(instance);
548
if (m_etype == ET_MAX || m_etype == ET_BOTH) {
549
classValueMax = classifyInstanceMax(instance);
554
classValue = classValueMin;
557
classValue = classValueMax;
560
classValue = (classValueMin + classValueMax) / 2;
563
throw new IllegalStateException("Illegal mode type!");
566
// round if necessary and return
567
return (m_ctype == CT_ROUNDED ? Utils.round(classValue) : classValue);
571
* Classify <code> instance </code> using the minimal rule base.
572
* Rounding is never performed, this is the responsability
573
* of <code> classifyInstance </code>.
575
* @param instance the instance to be classified
576
* @return the classification according to the minimal rule base
578
private double classifyInstanceMin(Instance instance) {
579
double classValue = -1;
580
if (m_baseMin == null) {
581
throw new IllegalStateException
582
("Classifier has not yet been built");
585
Iterator it = new EnumerationIterator(m_baseMin.enumerateInstances());
586
while (it.hasNext()) {
587
Instance r = (Instance) it.next();
589
// we assume that rules are ordered in decreasing class value order
590
// so that the first one that we encounter is immediately the
591
// one with the biggest class value
592
if (InstancesUtil.smallerOrEqual(r, instance)) {
593
classValue = r.classValue();
598
// there is no smaller rule in the database
599
if (classValue == -1) {
600
if (m_dtype != DT_NONE) {
601
Instance[] nn = nearestRules(instance, m_baseMin);
603
// XXX for the moment we only use the mean to extract a
604
// classValue; other possibilities might be included later
605
for (int i = 0; i < nn.length; i++) {
606
classValue += nn[i].classValue();
608
classValue /= nn.length;
611
classValue = 0; // minimal class value
615
return classValue; // no rounding!
619
* Classify <code> instance </code> using the maximal rule base.
620
* Rounding is never performed, this is the responsability
621
* of <code> classifyInstance </code>.
623
* @param instance the instance to be classified
624
* @return the classification according to the maximal rule base
626
private double classifyInstanceMax(Instance instance) {
627
double classValue = -1;
628
if (m_baseMax == null) {
629
throw new IllegalStateException
630
("Classifier has not yet been built");
633
Iterator it = new EnumerationIterator(m_baseMax.enumerateInstances());
634
while (it.hasNext()) {
635
Instance r = (Instance) it.next();
637
// we assume that rules are ordered in increasing class value order
638
// so that the first bigger one we encounter will be the one
639
// with the smallest label
640
if (InstancesUtil.smallerOrEqual(instance, r)) {
641
classValue = r.classValue();
646
// there is no bigger rule in the database
647
if (classValue == -1) {
648
if (m_dtype != DT_NONE) {
649
// XXX see remark in classifyInstanceMin
650
Instance[] nn = nearestRules(instance, m_baseMax);
652
for (int i = 0; i < nn.length; i++) {
653
classValue += nn[i].classValue();
655
classValue /= nn.length;
658
classValue = m_numClasses - 1; // maximal label
666
* Find the instances in <code> base </code> that are,
667
* according to the current distance type, closest
668
* to <code> instance </code>.
670
* @param instance the instance around which one looks
671
* @param base the instances to choose from
672
* @return an array of <code> Instance </code> which contains
673
* the instances closest to <code> instance </code>
675
private Instance[] nearestRules(Instance instance, Instances base) {
676
double min = Double.POSITIVE_INFINITY;
678
double[] instanceDouble = InstancesUtil.toDataDouble(instance);
679
ArrayList nn = new ArrayList();
680
Iterator it = new EnumerationIterator(base.enumerateInstances());
681
while(it.hasNext()) {
682
Instance r = (Instance) it.next();
683
double[] rDouble = InstancesUtil.toDataDouble(r);
686
dist = euclidDistance(instanceDouble, rDouble);
689
dist = hammingDistance(instanceDouble, rDouble);
692
throw new IllegalArgumentException("distance type is not valid");
698
} else if (dist == min) {
704
return (Instance[]) nn.toArray(new Instance[0]);
708
* Build the OLM classifier, meaning that the rule bases
711
* @param instances the instances to use for building the rule base
712
* @throws Exception if <code> instances </code> cannot be handled by
715
public void buildClassifier(Instances instances) throws Exception {
716
getCapabilities().testWithFail(instances);
719
m_train = new Instances(instances);
720
m_numClasses = m_train.numClasses();
722
// new dataset in which examples with missing class value are removed
723
m_train.deleteWithMissingClass();
725
// build the Map for the estimatedDistributions
726
m_estimatedDistributions = new HashMap(m_train.numInstances() / 2);
728
// cycle through all instances
729
Iterator it = new EnumerationIterator(m_train.enumerateInstances());
730
while (it.hasNext() == true) {
731
Instance instance = (Instance) it.next();
732
Coordinates c = new Coordinates(instance);
734
// get DiscreteEstimator from the map
735
DiscreteEstimator df =
736
(DiscreteEstimator) m_estimatedDistributions.get(c);
738
// if no DiscreteEstimator is present in the map, create one
740
df = new DiscreteEstimator(instances.numClasses(), 0);
742
df.addValue(instance.classValue(), instance.weight()); // update
743
m_estimatedDistributions.put(c, df); // put back in map
746
// Create the attributes for m_baseMin and m_baseMax.
747
// These are identical to those of m_train, except that the
748
// class is set to 'numeric'
749
// The class attribute is moved to the back
750
FastVector newAtts = new FastVector(m_train.numAttributes());
751
Attribute classAttribute = null;
752
for (int i = 0; i < m_train.numAttributes(); i++) {
753
Attribute att = m_train.attribute(i);
754
if (i != m_train.classIndex()) {
755
newAtts.addElement(att.copy());
757
classAttribute = new Attribute(att.name()); //numeric attribute
760
newAtts.addElement(classAttribute);
762
// original training instances are replaced by an empty set
764
m_train = new Instances(m_train.relationName(), newAtts,
765
m_estimatedDistributions.size());
766
m_train.setClassIndex(m_train.numAttributes() - 1);
769
// We cycle through the map of estimatedDistributions and
770
// create one Instance for each entry in the map, with
771
// a class value that is calculated from the distribution of
773
it = m_estimatedDistributions.keySet().iterator();
774
while(it.hasNext()) {
775
// XXX attValues must be here, otherwise things go wrong
776
double[] attValues = new double[m_train.numAttributes()];
777
Coordinates cc = (Coordinates) it.next();
778
DiscreteEstimator df =
779
(DiscreteEstimator) m_estimatedDistributions.get(cc);
780
cc.getValues(attValues);
783
attValues[attValues.length - 1] = (new DiscreteDistribution(df)).mean();
786
attValues[attValues.length - 1] = (new DiscreteDistribution(df)).median();
789
attValues[attValues.length - 1] = (new DiscreteDistribution(df)).modes()[0];
792
throw new IllegalStateException("Not a valid averaging type");
795
// add the instance, we give it weight one
796
m_train.add(new Instance(1, attValues));
799
if (m_Debug == true) {
800
System.out.println("The dataset after phase 1 :");
801
System.out.println(m_train.toString());
804
/* Shuffle to training instances, to prevent the order dictated
805
* by the map to play an important role in how the rule bases
808
m_train.randomize(new Random(getSeed()));
810
if (m_sort == false) {
811
// sort the instances only in increasing class order
812
m_train.sort(m_train.classIndex());
814
// sort instances completely
815
Comparator[] cc = new Comparator[m_train.numAttributes()];
816
// sort the class, increasing
817
cc[0] = new InstancesComparator(m_train.classIndex());
818
// sort the attributes, decreasing
819
for (int i = 1; i < cc.length; i++) {
820
cc[i] = new InstancesComparator(i - 1, true);
823
// copy instances into an array
824
Instance[] tmp = new Instance[m_train.numInstances()];
825
for (int i = 0; i < tmp.length; i++) {
826
tmp[i] = m_train.instance(i);
828
MultiDimensionalSort.multiDimensionalSort(tmp, cc);
830
// copy sorted array back into Instances
832
for (int i = 0; i < tmp.length; i++) {
837
// phase 2: building the rule bases themselves
839
new Instances(m_train, m_estimatedDistributions.size() / 4);
842
new Instances(m_train, m_estimatedDistributions.size() / 4);
847
* This implements the second phase of the OLM algorithm.
848
* We build the rule base m_baseMin, according to the conflict
849
* resolution mechanism described in the thesis.
851
private void phaseTwoMin() {
853
// loop through instances backwards, this is biggest class labels first
854
for (int i = m_train.numInstances() - 1; i >=0; i--) {
855
Instance e = m_train.instance(i);
857
// if the example is redundant with m_base, we discard it
858
if (isRedundant(e) == false) {
859
// how many examples are redundant if we would add e
860
int[] redundancies = makesRedundant(e);
861
if (redundancies[0] == 1
862
&& causesReversedPreference(e) == false) {
863
// there is one example made redundant be e, and
864
// adding e doesn't cause reversed preferences
865
// so we replace the indicated rule by e
866
m_baseMin.delete(redundancies[1]);
871
if (redundancies[0] == 0) {
872
// adding e causes no redundancies, what about
873
// reversed preferences ?
874
int[] revPref = reversedPreferences(e);
875
if (revPref[0] == 1) {
876
// there would be one reversed preference, we
877
// prefer the example e because it has a lower label
878
m_baseMin.delete(revPref[1]);
883
if (revPref[0] == 0) {
884
// this means: e causes no redundancies and no
885
// reversed preferences. We can simply add it.
894
* This implements the second phase of the OLM algorithm.
895
* We build the rule base m_baseMax .
897
private void phaseTwoMax() {
899
// loop through instances, smallest class labels first
900
for (int i = 0; i < m_train.numInstances(); i++) {
901
Instance e = m_train.instance(i);
903
// if the example is redundant with m_base, we discard it
904
if (isRedundantMax(e) == false) {
905
// how many examples are redundant if we would add e
906
int[] redundancies = makesRedundantMax(e);
907
if (redundancies[0] == 1
908
&& causesReversedPreferenceMax(e) == false) {
909
// there is one example made redundant be e, and
910
// adding e doesn't cause reversed preferences
911
// so we replace the indicated rule by e
912
m_baseMax.delete(redundancies[1]);
917
if (redundancies[0] == 0) {
918
// adding e causes no redundancies, what about
919
// reversed preferences ?
920
int[] revPref = reversedPreferencesMax(e);
921
if (revPref[0] == 1) {
922
// there would be one reversed preference, we
923
// prefer the example e because it has a lower label
924
m_baseMax.delete(revPref[1]);
929
if (revPref[0] == 0) {
930
// this means: e causes no redundancies and no
931
// reversed preferences. We can simply add it.
940
* Returns a string description of the classifier. In debug
941
* mode, the rule bases are added to the string representation
942
* as well. This means that the description can become rather
945
* @return a <code> String </code> describing the classifier.
947
public String toString() {
948
StringBuffer sb = new StringBuffer();
949
sb.append("OLM\n===\n\n");
950
if (m_etype == ET_MIN || m_etype == ET_BOTH) {
951
if (m_baseMin != null) {
952
sb.append("Number of examples in the minimal rule base = "
953
+ m_baseMin.numInstances() + "\n");
955
sb.append("minimal rule base not yet created");
959
if (m_etype == ET_MAX || m_etype == ET_BOTH) {
960
if (m_baseMax != null) {
961
sb.append("Number of examples in the maximal rule base = "
962
+ m_baseMax.numInstances() + "\n");
964
sb.append("maximal rule base not yet created");
968
if (m_Debug == true) {
970
if (m_etype == ET_MIN || m_etype == ET_BOTH) {
971
sb.append("The minimal rule base is \n");
972
if (m_baseMin != null) {
973
sb.append(m_baseMin.toString());
975
sb.append(".... not yet created");
979
if (m_etype == ET_MAX || m_etype == ET_BOTH) {
980
sb.append("The second rule base is \n");
981
if (m_baseMax != null) {
982
sb.append(m_baseMax.toString());
984
sb.append(".... not yet created");
990
return sb.toString();
994
* Is <code> instance </code> redundant wrt the
995
* current <code> m_baseMin </code>.
996
* This mean we are looking if there is an element in
997
* <code> m_baseMin </code> smaller than <code> instance </code>
998
* and with the same class.
1000
* @param instance the instance of which the redundancy needs to be
1002
* @return <code> true </code> if <code> instance </code>
1003
* is redundant, <code> false </code> otherwise
1005
private boolean isRedundant(Instance instance) {
1006
Iterator it = new EnumerationIterator(m_baseMin.enumerateInstances());
1007
while(it.hasNext()) {
1008
Instance r = (Instance) it.next();
1009
if (instance.classValue() == r.classValue()
1010
&& InstancesUtil.smallerOrEqual(r, instance) ) {
1018
* Is <code> instance </code> redundant wrt the
1019
* current <code> m_baseMax </code>.
1020
* This is dual to the previous method, this means that
1021
* <code> instance </code> is redundant if there exists
1022
* and example greater of equal than <code> instance </code>
1023
* with the same class value.
1025
* @param instance the instance of which the redundancy needs to be
1027
* @return <code> true </code> if <code> instance </code>
1028
* is redundant, <code> false </code> otherwise
1030
private boolean isRedundantMax(Instance instance) {
1031
Iterator it = new EnumerationIterator(m_baseMax.enumerateInstances());
1032
while(it.hasNext()) {
1033
Instance r = (Instance) it.next();
1034
if (instance.classValue() == r.classValue()
1035
&& InstancesUtil.smallerOrEqual(instance, r) ) {
1043
* If we were to add <code> instance </code>, how many
1044
* and which elements from <code> m_baseMin </code> would
1045
* be made redundant by <code> instance </code>.
1047
* @param instance the instance of which the influence is to be determined
1048
* @return an array containing two components
1049
* [0] is 0 if instance makes no elements redundant;
1050
* is 1 if there is one rule that is made redundant by instance;
1051
* is 2 if there is more than one rule that is made redundant;
1052
* [1] if [0] == 1, this entry gives the element that is made redundant
1054
private int[] makesRedundant(Instance instance) {
1055
int[] ret = new int[2];
1056
for (int i = 0; i < m_baseMin.numInstances(); i++) {
1057
Instance r = m_baseMin.instance(i);
1058
if (r.classValue() == instance.classValue() &&
1059
InstancesUtil.smallerOrEqual(instance, r)) {
1063
} else { // this means ret[0] == 1
1073
* If we were to add <code> instance </code>, how many
1074
* and which elements from <code> m_baseMax </code> would
1075
* be made redundant by <code> instance </code>.
1076
* This method is simply dual to <code> makesRedundant </code>.
1078
* @param instance the instance to add
1079
* @return an array containing two components
1080
* [0] is 0 if instance makes no elements redundant;
1081
* is 1 if there is one rule that is made redundant by instance;
1082
* is 2 if there is more than one rule that is made redundant;
1083
* [1] if [0] == 1, this entry gives the element that is made redundant
1085
private int[] makesRedundantMax(Instance instance) {
1086
int[] ret = new int[2];
1087
for (int i = 0; i < m_baseMax.numInstances(); i++) {
1088
Instance r = m_baseMax.instance(i);
1089
if (r.classValue() == instance.classValue() &&
1090
InstancesUtil.smallerOrEqual(r, instance)) {
1094
} else { // this means ret[0] == 1
1104
* Checks if adding <code> instance </code> to <code> m_baseMin </code>
1105
* causes reversed preference amongst the elements of <code>
1106
* m_baseMin </code>.
1108
* @param instance the instance of which the influence needs to be
1110
* @return <code> true </code> if adding <code> instance </code>
1111
* to the rule base would cause reversed preference among the rules,
1112
* <code> false </code> otherwise.
1114
private boolean causesReversedPreference(Instance instance) {
1115
Iterator it = new EnumerationIterator(m_baseMin.enumerateInstances());
1116
while (it.hasNext()) {
1117
Instance r = (Instance) it.next();
1118
if (instance.classValue() > r.classValue() &&
1119
InstancesUtil.smallerOrEqual(instance, r)) {
1120
// in the original version of OLM this should not happen
1122
("Should not happen in the original OLM algorithm");
1124
} else if (r.classValue() > instance.classValue() &&
1125
InstancesUtil.smallerOrEqual(r, instance)) {
1133
* Checks if adding <code> instance </code> to <code> m_baseMax </code>
1134
* causes reversed preference amongst the elements of
1135
* <code> m_baseMax </code>.
1137
* @param instance the instance to add
1138
* @return true if adding <code> instance </code> to the rule
1139
* base would cause reversed preference among the rules,
1142
private boolean causesReversedPreferenceMax(Instance instance) {
1143
Iterator it = new EnumerationIterator(m_baseMax.enumerateInstances());
1144
while (it.hasNext()) {
1145
Instance r = (Instance) it.next();
1146
if (instance.classValue() > r.classValue() &&
1147
InstancesUtil.smallerOrEqual(instance, r)) {
1149
} else if (r.classValue() > instance.classValue() &&
1150
InstancesUtil.smallerOrEqual(r, instance)) {
1158
* Find indices of the elements from <code> m_baseMin </code>
1159
* that are inconsistent with instance.
1161
* @param instance the instance of which the influence needs to be
1163
* @return an array containing two components
1164
* [0] is 0 if instance is consistent with all present elements
1165
* is 1 if instance is inconsistent (reversed preference) with
1166
* exactly one element
1167
* is 2 if instance is inconsistent with more than one element
1168
* [1] if [0] == 1, this entry gives the index of the
1169
* element that has reversed preference wrt to
1170
* <code> instance </code>
1172
private int[] reversedPreferences(Instance instance) {
1173
int[] revPreferences = new int[2];
1174
for (int i = 0; i < m_baseMin.numInstances(); i++) {
1175
Instance r = m_baseMin.instance(i);
1176
if (instance.classValue() < r.classValue() &&
1177
InstancesUtil.smallerOrEqual(r, instance) ) {
1178
if (revPreferences[0] == 0) {
1179
revPreferences[0] = 1;
1180
revPreferences[1] = i;
1182
revPreferences[0] = 2;
1183
return revPreferences;
1187
return revPreferences;
1191
* Find indices of the elements from <code> m_baseMin </code>
1192
* that are inconsistent with instance.
1194
* @param instance the instance of which the influence needs to be
1196
* @return an array containing two components
1197
* [0] is 0 if instance is consistent with all present elements
1198
* is 1 if instance is inconsistent (reversed preference) with
1199
* exactly one element
1200
* is 2 if instance is inconsistent with more than one element
1201
* [1] if [0] == 1, this entry gives the index of the
1202
* element that has reversed preference wrt to
1203
* <code> instance </code>
1205
private int[] reversedPreferencesMax(Instance instance) {
1206
int[] revPreferences = new int[2];
1207
for (int i = 0; i < m_baseMax.numInstances(); i++) {
1208
Instance r = m_baseMax.instance(i);
1209
if (instance.classValue() > r.classValue() &&
1210
InstancesUtil.smallerOrEqual(instance, r) ) {
1211
if (revPreferences[0] == 0) {
1212
revPreferences[0] = 1;
1213
revPreferences[1] = i;
1215
revPreferences[0] = 2;
1216
return revPreferences;
1220
return revPreferences;
1224
* Calculates the square of the Euclidian distance between
1225
* two arrays of doubles. The arrays should have the same length.
1227
* @param a1 the first array
1228
* @param a2 the second array
1229
* @return the square of the Euclidian distance between the two
1230
* arrays <code> a1 </code> and <code> a2 </code>
1232
private double euclidDistance(double[] a1, double[] a2) {
1234
for (int i = 0; i < a1.length; i++) {
1235
dist += (a1[i] - a2[i]) * (a1[i] - a2[i]);
1241
* Calculates the Hamming distances between two arrays, this
1242
* means one counts the number of positions in which these
1243
* two array differ. The arrays should be of the same length.
1245
* @param a1 the first array
1246
* @param a2 the second array
1247
* @return the requested Hamming distance
1248
* The Hamming distance between a1 and a2, this is
1249
* the number of positions in which a1 and a2 differ
1251
private int hammingDistance(double[] a1, double[] a2) {
1253
for (int i = 0; i < a1.length; i++) {
1254
dist += (a1[i] == a2[i]) ? 0 : 1;
1260
* Get an enumeration of all available options for this classifier.
1262
* @return an enumeration of available options
1264
public Enumeration listOptions() {
1265
Vector options = new Vector();
1267
Enumeration enm = super.listOptions();
1268
while (enm.hasMoreElements())
1269
options.addElement(enm.nextElement());
1271
String description =
1272
"\tSets the classification type to be used.\n" +
1273
"\t(Default: " + new SelectedTag(CT_REAL, TAGS_CLASSIFICATIONTYPES) + ")";
1274
String synopsis = "-C " + Tag.toOptionList(TAGS_CLASSIFICATIONTYPES);
1276
options.addElement(new Option(description, name, 1, synopsis));
1279
"\tSets the averaging type used in phase 1 of the classifier.\n" +
1280
"\t(Default: " + new SelectedTag(AT_MEAN, TAGS_AVERAGINGTYPES) + ")";
1281
synopsis = "-A " + Tag.toOptionList(TAGS_AVERAGINGTYPES);
1283
options.addElement(new Option(description, name, 1, synopsis));
1286
"\tIf different from " + new SelectedTag(DT_NONE, TAGS_DISTANCETYPES) + ", a nearest neighbour rule is fired when the\n" +
1287
"\trule base doesn't contain an example smaller than the instance\n" +
1288
"\tto be classified\n" +
1289
"\t(Default: " + new SelectedTag(DT_NONE, TAGS_DISTANCETYPES) + ").";
1290
synopsis = "-N " + Tag.toOptionList(TAGS_DISTANCETYPES);
1292
options.addElement(new Option(description, name, 1, synopsis));
1294
description = "\tSets the extension type, i.e. the rule base to use."
1295
+ "\n\t(Default: " + new SelectedTag(ET_MIN, TAGS_EXTENSIONTYPES) + ")";
1296
synopsis = "-E " + Tag.toOptionList(TAGS_EXTENSIONTYPES);
1298
options.addElement(new Option(description, name, 1, synopsis));
1301
"\tIf set, the instances are also sorted within the same class\n"
1302
+ "\tbefore building the rule bases";
1305
options.addElement(new Option(description, name, 0, synopsis));
1307
return options.elements();
1311
* Parses the options for this object. <p/>
1313
<!-- options-start -->
1314
* Valid options are: <p/>
1316
* <pre> -S <num>
1317
* Random number seed.
1321
* If set, classifier is run in debug mode and
1322
* may output additional info to the console</pre>
1324
* <pre> -C <CL|REG>
1325
* Sets the classification type to be used.
1326
* (Default: REG)</pre>
1328
* <pre> -A <MEAN|MED|MAX>
1329
* Sets the averaging type used in phase 1 of the classifier.
1330
* (Default: MEAN)</pre>
1332
* <pre> -N <NONE|EUCL|HAM>
1333
* If different from NONE, a nearest neighbour rule is fired when the
1334
* rule base doesn't contain an example smaller than the instance
1336
* (Default: NONE).</pre>
1338
* <pre> -E <MIN|MAX|BOTH>
1339
* Sets the extension type, i.e. the rule base to use.
1340
* (Default: MIN)</pre>
1343
* If set, the instances are also sorted within the same class
1344
* before building the rule bases</pre>
1346
<!-- options-end -->
1348
* @param options an array of strings containing the options
1349
* @throws Exception if there are options that have invalid arguments.
1351
public void setOptions(String[] options) throws Exception {
1354
// classification type
1355
args = Utils.getOption('C', options);
1356
if (args.length() != 0)
1357
setClassificationType(new SelectedTag(args, TAGS_CLASSIFICATIONTYPES));
1359
setClassificationType(new SelectedTag(CT_REAL, TAGS_CLASSIFICATIONTYPES));
1362
args = Utils.getOption('A', options);
1363
if (args.length() != 0)
1364
setAveragingType(new SelectedTag(args, TAGS_AVERAGINGTYPES));
1366
setAveragingType(new SelectedTag(AT_MEAN, TAGS_AVERAGINGTYPES));
1369
args = Utils.getOption('N', options);
1370
if (args.length() != 0)
1371
setDistanceType(new SelectedTag(args, TAGS_DISTANCETYPES));
1373
setDistanceType(new SelectedTag(DT_NONE, TAGS_DISTANCETYPES));
1376
args = Utils.getOption('E', options);
1377
if (args.length() != 0)
1378
setExtensionType(new SelectedTag(args, TAGS_EXTENSIONTYPES));
1380
setExtensionType(new SelectedTag(ET_MIN, TAGS_EXTENSIONTYPES));
1383
setSort(Utils.getFlag("sort", options));
1385
super.setOptions(options);
1389
* Gets an array of string with the current options of the classifier.
1391
* @return an array suitable as argument for <code> setOptions </code>
1393
public String[] getOptions() {
1398
result = new Vector();
1400
options = super.getOptions();
1401
for (i = 0; i < options.length; i++)
1402
result.add(options[i]);
1404
// classification type
1406
result.add("" + getClassificationType());
1409
result.add("" + getAveragingType());
1412
result.add("" + getDistanceType());
1415
result.add("" + getExtensionType());
1418
result.add("-sort");
1420
return (String[]) result.toArray(new String[result.size()]);
1424
* Main method for testing this class.
1426
* @param args the command line arguments
1428
public static void main(String[] args) {
1429
runClassifier(new OLM(), args);
added
removed
weka/classifiers/misc/OLM.java
