001: /*
002: * This program is free software; you can redistribute it and/or modify
003: * it under the terms of the GNU General Public License as published by
004: * the Free Software Foundation; either version 2 of the License, or
005: * (at your option) any later version.
006: *
007: * This program is distributed in the hope that it will be useful,
008: * but WITHOUT ANY WARRANTY; without even the implied warranty of
009: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
010: * GNU General Public License for more details.
011: *
012: * You should have received a copy of the GNU General Public License
013: * along with this program; if not, write to the Free Software
014: * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
015: */
016:
017: /*
018: * KStar.java
019: * Copyright (C) 1995-97 University of Waikato, Hamilton, New Zealand
020: *
021: */
022:
023: package weka.classifiers.lazy;
024:
025: import weka.classifiers.Classifier;
026: import weka.classifiers.UpdateableClassifier;
027: import weka.classifiers.lazy.kstar.KStarCache;
028: import weka.classifiers.lazy.kstar.KStarConstants;
029: import weka.classifiers.lazy.kstar.KStarNominalAttribute;
030: import weka.classifiers.lazy.kstar.KStarNumericAttribute;
031: import weka.core.Attribute;
032: import weka.core.Capabilities;
033: import weka.core.Instance;
034: import weka.core.Instances;
035: import weka.core.Option;
036: import weka.core.SelectedTag;
037: import weka.core.Tag;
038: import weka.core.TechnicalInformation;
039: import weka.core.TechnicalInformationHandler;
040: import weka.core.Utils;
041: import weka.core.Capabilities.Capability;
042: import weka.core.TechnicalInformation.Field;
043: import weka.core.TechnicalInformation.Type;
044:
045: import java.util.Enumeration;
046: import java.util.Random;
047: import java.util.Vector;
048:
049: /**
050: <!-- globalinfo-start -->
051: * K* is an instance-based classifier, that is the class of a test instance is based upon the class of those training instances similar to it, as determined by some similarity function. It differs from other instance-based learners in that it uses an entropy-based distance function.<br/>
052: * <br/>
053: * For more information on K*, see<br/>
054: * <br/>
055: * John G. Cleary, Leonard E. Trigg: K*: An Instance-based Learner Using an Entropic Distance Measure. In: 12th International Conference on Machine Learning, 108-114, 1995.
056: * <p/>
057: <!-- globalinfo-end -->
058: *
059: <!-- technical-bibtex-start -->
060: * BibTeX:
061: * <pre>
062: * @inproceedings{Cleary1995,
063: * author = {John G. Cleary and Leonard E. Trigg},
064: * booktitle = {12th International Conference on Machine Learning},
065: * pages = {108-114},
066: * title = {K*: An Instance-based Learner Using an Entropic Distance Measure},
067: * year = {1995}
068: * }
069: * </pre>
070: * <p/>
071: <!-- technical-bibtex-end -->
072: *
073: <!-- options-start -->
074: * Valid options are: <p/>
075: *
076: * <pre> -B <num>
077: * Manual blend setting (default 20%)
078: * </pre>
079: *
080: * <pre> -E
081: * Enable entropic auto-blend setting (symbolic class only)
082: * </pre>
083: *
084: * <pre> -M <char>
085: * Specify the missing value treatment mode (default a)
086: * Valid options are: a(verage), d(elete), m(axdiff), n(ormal)
087: * </pre>
088: *
089: <!-- options-end -->
090: *
091: * @author Len Trigg (len@reeltwo.com)
092: * @author Abdelaziz Mahoui (am14@cs.waikato.ac.nz) - Java port
093: * @version $Revision: 1.8 $
094: */
095: public class KStar extends Classifier implements KStarConstants,
096: UpdateableClassifier, TechnicalInformationHandler {
097:
098: /** for serialization */
099: static final long serialVersionUID = 332458330800479083L;
100:
101: /** The training instances used for classification. */
102: protected Instances m_Train;
103:
104: /** The number of instances in the dataset */
105: protected int m_NumInstances;
106:
107: /** The number of class values */
108: protected int m_NumClasses;
109:
110: /** The number of attributes */
111: protected int m_NumAttributes;
112:
113: /** The class attribute type */
114: protected int m_ClassType;
115:
116: /** Table of random class value colomns */
117: protected int[][] m_RandClassCols;
118:
119: /** Flag turning on and off the computation of random class colomns */
120: protected int m_ComputeRandomCols = ON;
121:
122: /** Flag turning on and off the initialisation of config variables */
123: protected int m_InitFlag = ON;
124:
125: /**
126: * A custom data structure for caching distinct attribute values
127: * and their scale factor or stop parameter.
128: */
129: protected KStarCache[] m_Cache;
130:
131: /** missing value treatment */
132: protected int m_MissingMode = M_AVERAGE;
133:
134: /** 0 = use specified blend, 1 = entropic blend setting */
135: protected int m_BlendMethod = B_SPHERE;
136:
137: /** default sphere of influence blend setting */
138: protected int m_GlobalBlend = 20;
139:
140: /** Define possible missing value handling methods */
141: public static final Tag[] TAGS_MISSING = {
142: new Tag(M_DELETE,
143: "Ignore the instances with missing values"),
144: new Tag(M_MAXDIFF,
145: "Treat missing values as maximally different"),
146: new Tag(M_NORMAL, "Normalize over the attributes"),
147: new Tag(M_AVERAGE, "Average column entropy curves") };
148:
149: /**
150: * Returns a string describing classifier
151: * @return a description suitable for
152: * displaying in the explorer/experimenter gui
153: */
154: public String globalInfo() {
155:
156: return "K* is an instance-based classifier, that is the class of a test "
157: + "instance is based upon the class of those training instances "
158: + "similar to it, as determined by some similarity function. It differs "
159: + "from other instance-based learners in that it uses an entropy-based "
160: + "distance function.\n\n"
161: + "For more information on K*, see\n\n"
162: + getTechnicalInformation().toString();
163: }
164:
165: /**
166: * Returns an instance of a TechnicalInformation object, containing
167: * detailed information about the technical background of this class,
168: * e.g., paper reference or book this class is based on.
169: *
170: * @return the technical information about this class
171: */
172: public TechnicalInformation getTechnicalInformation() {
173: TechnicalInformation result;
174:
175: result = new TechnicalInformation(Type.INPROCEEDINGS);
176: result.setValue(Field.AUTHOR,
177: "John G. Cleary and Leonard E. Trigg");
178: result
179: .setValue(Field.TITLE,
180: "K*: An Instance-based Learner Using an Entropic Distance Measure");
181: result.setValue(Field.BOOKTITLE,
182: "12th International Conference on Machine Learning");
183: result.setValue(Field.YEAR, "1995");
184: result.setValue(Field.PAGES, "108-114");
185:
186: return result;
187: }
188:
189: /**
190: * Returns default capabilities of the classifier.
191: *
192: * @return the capabilities of this classifier
193: */
194: public Capabilities getCapabilities() {
195: Capabilities result = super .getCapabilities();
196:
197: // attributes
198: result.enable(Capability.NOMINAL_ATTRIBUTES);
199: result.enable(Capability.NUMERIC_ATTRIBUTES);
200: result.enable(Capability.DATE_ATTRIBUTES);
201: result.enable(Capability.MISSING_VALUES);
202:
203: // class
204: result.enable(Capability.NOMINAL_CLASS);
205: result.enable(Capability.NUMERIC_CLASS);
206: result.enable(Capability.DATE_CLASS);
207: result.enable(Capability.MISSING_CLASS_VALUES);
208:
209: // instances
210: result.setMinimumNumberInstances(0);
211:
212: return result;
213: }
214:
215: /**
216: * Generates the classifier.
217: *
218: * @param instances set of instances serving as training data
219: * @throws Exception if the classifier has not been generated successfully
220: */
221: public void buildClassifier(Instances instances) throws Exception {
222: String debug = "(KStar.buildClassifier) ";
223:
224: // can classifier handle the data?
225: getCapabilities().testWithFail(instances);
226:
227: // remove instances with missing class
228: instances = new Instances(instances);
229: instances.deleteWithMissingClass();
230:
231: m_Train = new Instances(instances, 0, instances.numInstances());
232:
233: // initializes class attributes ** java-speaking! :-) **
234: init_m_Attributes();
235: }
236:
237: /**
238: * Adds the supplied instance to the training set
239: *
240: * @param instance the instance to add
241: * @throws Exception if instance could not be incorporated successfully
242: */
243: public void updateClassifier(Instance instance) throws Exception {
244: String debug = "(KStar.updateClassifier) ";
245:
246: if (m_Train.equalHeaders(instance.dataset()) == false)
247: throw new Exception("Incompatible instance types");
248: if (instance.classIsMissing())
249: return;
250: m_Train.add(instance);
251: // update relevant attributes ...
252: update_m_Attributes();
253: }
254:
255: /**
256: * Calculates the class membership probabilities for the given test instance.
257: *
258: * @param instance the instance to be classified
259: * @return predicted class probability distribution
260: * @throws Exception if an error occurred during the prediction
261: */
262: public double[] distributionForInstance(Instance instance)
263: throws Exception {
264:
265: String debug = "(KStar.distributionForInstance) ";
266: double transProb = 0.0, temp = 0.0;
267: double[] classProbability = new double[m_NumClasses];
268: double[] predictedValue = new double[1];
269:
270: // initialization ...
271: for (int i = 0; i < classProbability.length; i++) {
272: classProbability[i] = 0.0;
273: }
274: predictedValue[0] = 0.0;
275: if (m_InitFlag == ON) {
276: // need to compute them only once and will be used for all instances.
277: // We are doing this because the evaluation module controls the calls.
278: if (m_BlendMethod == B_ENTROPY) {
279: generateRandomClassColomns();
280: }
281: m_Cache = new KStarCache[m_NumAttributes];
282: for (int i = 0; i < m_NumAttributes; i++) {
283: m_Cache[i] = new KStarCache();
284: }
285: m_InitFlag = OFF;
286: // System.out.println("Computing...");
287: }
288: // init done.
289: Instance trainInstance;
290: Enumeration enu = m_Train.enumerateInstances();
291: while (enu.hasMoreElements()) {
292: trainInstance = (Instance) enu.nextElement();
293: transProb = instanceTransformationProbability(instance,
294: trainInstance);
295: switch (m_ClassType) {
296: case Attribute.NOMINAL:
297: classProbability[(int) trainInstance.classValue()] += transProb;
298: break;
299: case Attribute.NUMERIC:
300: predictedValue[0] += transProb
301: * trainInstance.classValue();
302: temp += transProb;
303: break;
304: }
305: }
306: if (m_ClassType == Attribute.NOMINAL) {
307: double sum = Utils.sum(classProbability);
308: if (sum <= 0.0)
309: for (int i = 0; i < classProbability.length; i++)
310: classProbability[i] = (double) 1
311: / (double) m_NumClasses;
312: else
313: Utils.normalize(classProbability, sum);
314: return classProbability;
315: } else {
316: predictedValue[0] = (temp != 0) ? predictedValue[0] / temp
317: : 0.0;
318: return predictedValue;
319: }
320: }
321:
322: /**
323: * Calculate the probability of the first instance transforming into the
324: * second instance:
325: * the probability is the product of the transformation probabilities of
326: * the attributes normilized over the number of instances used.
327: *
328: * @param first the test instance
329: * @param second the train instance
330: * @return transformation probability value
331: */
332: private double instanceTransformationProbability(Instance first,
333: Instance second) {
334: String debug = "(KStar.instanceTransformationProbability) ";
335: double transProb = 1.0;
336: int numMissAttr = 0;
337: for (int i = 0; i < m_NumAttributes; i++) {
338: if (i == m_Train.classIndex()) {
339: continue; // ignore class attribute
340: }
341: if (first.isMissing(i)) { // test instance attribute value is missing
342: numMissAttr++;
343: continue;
344: }
345: transProb *= attrTransProb(first, second, i);
346: // normilize for missing values
347: if (numMissAttr != m_NumAttributes) {
348: transProb = Math.pow(transProb,
349: (double) m_NumAttributes
350: / (m_NumAttributes - numMissAttr));
351: } else { // weird case!
352: transProb = 0.0;
353: }
354: }
355: // normilize for the train dataset
356: return transProb / m_NumInstances;
357: }
358:
359: /**
360: * Calculates the transformation probability of the indexed test attribute
361: * to the indexed train attribute.
362: *
363: * @param first the test instance.
364: * @param second the train instance.
365: * @param col the index of the attribute in the instance.
366: * @return the value of the transformation probability.
367: */
368: private double attrTransProb(Instance first, Instance second,
369: int col) {
370: String debug = "(KStar.attrTransProb)";
371: double transProb = 0.0;
372: KStarNominalAttribute ksNominalAttr;
373: KStarNumericAttribute ksNumericAttr;
374: switch (m_Train.attribute(col).type()) {
375: case Attribute.NOMINAL:
376: ksNominalAttr = new KStarNominalAttribute(first, second,
377: col, m_Train, m_RandClassCols, m_Cache[col]);
378: ksNominalAttr.setOptions(m_MissingMode, m_BlendMethod,
379: m_GlobalBlend);
380: transProb = ksNominalAttr.transProb();
381: ksNominalAttr = null;
382: break;
383:
384: case Attribute.NUMERIC:
385: ksNumericAttr = new KStarNumericAttribute(first, second,
386: col, m_Train, m_RandClassCols, m_Cache[col]);
387: ksNumericAttr.setOptions(m_MissingMode, m_BlendMethod,
388: m_GlobalBlend);
389: transProb = ksNumericAttr.transProb();
390: ksNumericAttr = null;
391: break;
392: }
393: return transProb;
394: }
395:
396: /**
397: * Returns the tip text for this property
398: * @return tip text for this property suitable for
399: * displaying in the explorer/experimenter gui
400: */
401: public String missingModeTipText() {
402: return "Determines how missing attribute values are treated.";
403: }
404:
405: /**
406: * Gets the method to use for handling missing values. Will be one of
407: * M_NORMAL, M_AVERAGE, M_MAXDIFF or M_DELETE.
408: *
409: * @return the method used for handling missing values.
410: */
411: public SelectedTag getMissingMode() {
412:
413: return new SelectedTag(m_MissingMode, TAGS_MISSING);
414: }
415:
416: /**
417: * Sets the method to use for handling missing values. Values other than
418: * M_NORMAL, M_AVERAGE, M_MAXDIFF and M_DELETE will be ignored.
419: *
420: * @param newMode the method to use for handling missing values.
421: */
422: public void setMissingMode(SelectedTag newMode) {
423:
424: if (newMode.getTags() == TAGS_MISSING) {
425: m_MissingMode = newMode.getSelectedTag().getID();
426: }
427: }
428:
429: /**
430: * Returns an enumeration describing the available options.
431: *
432: * @return an enumeration of all the available options.
433: */
434: public Enumeration listOptions() {
435:
436: Vector optVector = new Vector(3);
437: optVector.addElement(new Option(
438: "\tManual blend setting (default 20%)\n", "B", 1,
439: "-B <num>"));
440: optVector
441: .addElement(new Option(
442: "\tEnable entropic auto-blend setting (symbolic class only)\n",
443: "E", 0, "-E"));
444: optVector
445: .addElement(new Option(
446: "\tSpecify the missing value treatment mode (default a)\n"
447: + "\tValid options are: a(verage), d(elete), m(axdiff), n(ormal)\n",
448: "M", 1, "-M <char>"));
449: return optVector.elements();
450: }
451:
452: /**
453: * Returns the tip text for this property
454: * @return tip text for this property suitable for
455: * displaying in the explorer/experimenter gui
456: */
457: public String globalBlendTipText() {
458: return "The parameter for global blending. Values are restricted to [0,100].";
459: }
460:
461: /**
462: * Set the global blend parameter
463: * @param b the value for global blending
464: */
465: public void setGlobalBlend(int b) {
466: m_GlobalBlend = b;
467: if (m_GlobalBlend > 100) {
468: m_GlobalBlend = 100;
469: }
470: if (m_GlobalBlend < 0) {
471: m_GlobalBlend = 0;
472: }
473: }
474:
475: /**
476: * Get the value of the global blend parameter
477: * @return the value of the global blend parameter
478: */
479: public int getGlobalBlend() {
480: return m_GlobalBlend;
481: }
482:
483: /**
484: * Returns the tip text for this property
485: * @return tip text for this property suitable for
486: * displaying in the explorer/experimenter gui
487: */
488: public String entropicAutoBlendTipText() {
489: return "Whether entropy-based blending is to be used.";
490: }
491:
492: /**
493: * Set whether entropic blending is to be used.
494: * @param e true if entropic blending is to be used
495: */
496: public void setEntropicAutoBlend(boolean e) {
497: if (e) {
498: m_BlendMethod = B_ENTROPY;
499: } else {
500: m_BlendMethod = B_SPHERE;
501: }
502: }
503:
504: /**
505: * Get whether entropic blending being used
506: * @return true if entropic blending is used
507: */
508: public boolean getEntropicAutoBlend() {
509: if (m_BlendMethod == B_ENTROPY) {
510: return true;
511: }
512:
513: return false;
514: }
515:
516: /**
517: * Parses a given list of options. <p/>
518: *
519: <!-- options-start -->
520: * Valid options are: <p/>
521: *
522: * <pre> -B <num>
523: * Manual blend setting (default 20%)
524: * </pre>
525: *
526: * <pre> -E
527: * Enable entropic auto-blend setting (symbolic class only)
528: * </pre>
529: *
530: * <pre> -M <char>
531: * Specify the missing value treatment mode (default a)
532: * Valid options are: a(verage), d(elete), m(axdiff), n(ormal)
533: * </pre>
534: *
535: <!-- options-end -->
536: *
537: * @param options the list of options as an array of strings
538: * @throws Exception if an option is not supported
539: */
540: public void setOptions(String[] options) throws Exception {
541: String debug = "(KStar.setOptions)";
542: String blendStr = Utils.getOption('B', options);
543: if (blendStr.length() != 0) {
544: setGlobalBlend(Integer.parseInt(blendStr));
545: }
546:
547: setEntropicAutoBlend(Utils.getFlag('E', options));
548:
549: String missingModeStr = Utils.getOption('M', options);
550: if (missingModeStr.length() != 0) {
551: switch (missingModeStr.charAt(0)) {
552: case 'a':
553: setMissingMode(new SelectedTag(M_AVERAGE, TAGS_MISSING));
554: break;
555: case 'd':
556: setMissingMode(new SelectedTag(M_DELETE, TAGS_MISSING));
557: break;
558: case 'm':
559: setMissingMode(new SelectedTag(M_MAXDIFF, TAGS_MISSING));
560: break;
561: case 'n':
562: setMissingMode(new SelectedTag(M_NORMAL, TAGS_MISSING));
563: break;
564: default:
565: setMissingMode(new SelectedTag(M_AVERAGE, TAGS_MISSING));
566: }
567: }
568: Utils.checkForRemainingOptions(options);
569: }
570:
571: /**
572: * Gets the current settings of K*.
573: *
574: * @return an array of strings suitable for passing to setOptions()
575: */
576: public String[] getOptions() {
577: // -B <num> -E -M <char>
578: String[] options = new String[5];
579: int itr = 0;
580: options[itr++] = "-B";
581: options[itr++] = "" + m_GlobalBlend;
582:
583: if (getEntropicAutoBlend()) {
584: options[itr++] = "-E";
585: }
586:
587: options[itr++] = "-M";
588: if (m_MissingMode == M_AVERAGE) {
589: options[itr++] = "" + "a";
590: } else if (m_MissingMode == M_DELETE) {
591: options[itr++] = "" + "d";
592: } else if (m_MissingMode == M_MAXDIFF) {
593: options[itr++] = "" + "m";
594: } else if (m_MissingMode == M_NORMAL) {
595: options[itr++] = "" + "n";
596: }
597: while (itr < options.length) {
598: options[itr++] = "";
599: }
600: return options;
601: }
602:
603: /**
604: * Returns a description of this classifier.
605: *
606: * @return a description of this classifier as a string.
607: */
608: public String toString() {
609: StringBuffer st = new StringBuffer();
610: st
611: .append("KStar Beta Verion (0.1b).\n"
612: + "Copyright (c) 1995-97 by Len Trigg (trigg@cs.waikato.ac.nz).\n"
613: + "Java port to Weka by Abdelaziz Mahoui "
614: + "(am14@cs.waikato.ac.nz).\n\nKStar options : ");
615: String[] ops = getOptions();
616: for (int i = 0; i < ops.length; i++) {
617: st.append(ops[i] + ' ');
618: }
619: return st.toString();
620: }
621:
622: /**
623: * Main method for testing this class.
624: *
625: * @param argv should contain command line options (see setOptions)
626: */
627: public static void main(String[] argv) {
628: runClassifier(new KStar(), argv);
629: }
630:
631: /**
632: * Initializes the m_Attributes of the class.
633: */
634: private void init_m_Attributes() {
635: try {
636: m_NumInstances = m_Train.numInstances();
637: m_NumClasses = m_Train.numClasses();
638: m_NumAttributes = m_Train.numAttributes();
639: m_ClassType = m_Train.classAttribute().type();
640: m_InitFlag = ON;
641: } catch (Exception e) {
642: e.printStackTrace();
643: }
644: }
645:
646: /**
647: * Updates the m_attributes of the class.
648: */
649: private void update_m_Attributes() {
650: m_NumInstances = m_Train.numInstances();
651: m_InitFlag = ON;
652: }
653:
654: /**
655: * Note: for Nominal Class Only!
656: * Generates a set of random versions of the class colomn.
657: */
658: private void generateRandomClassColomns() {
659: String debug = "(KStar.generateRandomClassColomns)";
660: Random generator = new Random(42);
661: // Random generator = new Random();
662: m_RandClassCols = new int[NUM_RAND_COLS + 1][];
663: int[] classvals = classValues();
664: for (int i = 0; i < NUM_RAND_COLS; i++) {
665: // generate a randomized version of the class colomn
666: m_RandClassCols[i] = randomize(classvals, generator);
667: }
668: // original colomn is preserved in colomn NUM_RAND_COLS
669: m_RandClassCols[NUM_RAND_COLS] = classvals;
670: }
671:
672: /**
673: * Note: for Nominal Class Only!
674: * Returns an array of the class values
675: *
676: * @return an array of class values
677: */
678: private int[] classValues() {
679: String debug = "(KStar.classValues)";
680: int[] classval = new int[m_NumInstances];
681: for (int i = 0; i < m_NumInstances; i++) {
682: try {
683: classval[i] = (int) m_Train.instance(i).classValue();
684: } catch (Exception ex) {
685: ex.printStackTrace();
686: }
687: }
688: return classval;
689: }
690:
691: /**
692: * Returns a copy of the array with its elements randomly redistributed.
693: *
694: * @param array the array to randomize.
695: * @param generator the random number generator to use
696: * @return a copy of the array with its elements randomly redistributed.
697: */
698: private int[] randomize(int[] array, Random generator) {
699: String debug = "(KStar.randomize)";
700: int index;
701: int temp;
702: int[] newArray = new int[array.length];
703: System.arraycopy(array, 0, newArray, 0, array.length);
704: for (int j = newArray.length - 1; j > 0; j--) {
705: index = (int) (generator.nextDouble() * (double) j);
706: temp = newArray[j];
707: newArray[j] = newArray[index];
708: newArray[index] = temp;
709: }
710: return newArray;
711: }
712:
713: } // class end
|