content: /*
   *    This program is free software; you can redistribute it and/or modify
   *    it under the terms of the GNU General Public License as published by
   *    the Free Software Foundation; either version 2 of the License, or
   *    (at your option) any later version.
   *
   *    This program is distributed in the hope that it will be useful,
   *    but WITHOUT ANY WARRANTY; without even the implied warranty of
   *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   *    GNU General Public License for more details.
   *
   *    You should have received a copy of the GNU General Public License
   *    along with this program; if not, write to the Free Software
   *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
   */
  
  /**
   *    KStarNominalAttribute.java
   *    Copyright (C) 1995 Univeristy of Waikato
   *    Java port to Weka by Abdelaziz Mahoui (am14@cs.waikato.ac.nz).
   *
   */
  
  
  package weka.classifiers.lazy.kstar;
  
  import weka.core.Attribute;
  import weka.core.Instance;
  import weka.core.Instances;
  import weka.core.RevisionHandler;
  import weka.core.RevisionUtils;
  
  /**
   * A custom class which provides the environment for computing the
   * transformation probability of a specified test instance nominal
   * attribute to a specified train instance nominal attribute.
   *
   * @author Len Trigg (len@reeltwo.com)
   * @author Abdelaziz Mahoui (am14@cs.waikato.ac.nz)
   * @version $Revision 1.0 $
   */
  public class KStarNominalAttribute
    implements KStarConstants, RevisionHandler {
    
    /** The training instances used for classification. */
    protected Instances m_TrainSet;
  
    /** The test instance */
    protected Instance m_Test;
  
    /** The train instance */
    protected Instance m_Train;
  
    /** The index of the nominal attribute in the test and train instances */
    protected int m_AttrIndex;
  
    /** The stop parameter */
    protected double m_Stop = 1.0;
  
    /** Probability of test attribute transforming into train attribute 
        with missing value */
    protected double m_MissingProb = 1.0;
  
    /** Average probability of test attribute transforming into train 
        attribute */
    protected double m_AverageProb = 1.0;
  
    /** Smallest probability of test attribute transforming into 
        train attribute */
    protected double m_SmallestProb = 1.0;
  
    /** Number of trai instances with no missing attribute values */
    protected int m_TotalCount;
  
    /** Distribution of the attribute value in the train dataset */
    protected int [] m_Distribution;
  
    /** Set of colomns: each colomn representing a randomised version 
        of the train dataset class colomn */
    protected int [][] m_RandClassCols;
  
    /** A cache for storing attribute values and their corresponding 
        stop parameters */
    protected KStarCache m_Cache;
  
    // KStar Global settings
  
    /** The number of instances in the dataset */
    protected int m_NumInstances;
  
    /** The number of class values */
    protected int m_NumClasses;
  
    /** The number of attributes */
    protected int m_NumAttributes;
  
    /** The class attribute type */
    protected int m_ClassType;
  
    /** missing value treatment */
    protected int m_MissingMode = M_AVERAGE;
  
    /** B_SPHERE = use specified blend, B_ENTROPY = entropic blend setting */
    protected int m_BlendMethod = B_SPHERE ;
  
    /** default sphere of influence blend setting */
    protected int m_BlendFactor = 20;
    
    /**
     * Constructor
     */
    public KStarNominalAttribute(Instance test, Instance train, int attrIndex,
  			       Instances trainSet, int [][] randClassCol, 
  			       KStarCache cache)
    {
      m_Test = test;
      m_Train = train;
      m_AttrIndex = attrIndex;
      m_TrainSet = trainSet;
      m_RandClassCols = randClassCol;
      m_Cache = cache;
      init();
    }
  
    /**
     * Initializes the m_Attributes of the class.
     */
    private void init() {
      try {
        m_NumInstances  = m_TrainSet.numInstances();
        m_NumClasses    = m_TrainSet.numClasses();
        m_NumAttributes = m_TrainSet.numAttributes();
        m_ClassType     = m_TrainSet.classAttribute().type();
      } catch(Exception e) {
        e.printStackTrace();
      }
    }
  
    /**
     * Calculates the probability of the indexed nominal attribute of the test
     * instance transforming into the indexed nominal attribute of the training 
     * instance.
     *
     * @return the value of the transformation probability.
     */
    public double transProb() {
      String debug = "(KStarNominalAttribute.transProb) ";
      double transProb = 0.0;
      // check if the attribute value has been encountred before
      // in which case it should be in the nominal cache
      if (m_Cache.containsKey(m_Test.value(m_AttrIndex))) {
        KStarCache.TableEntry te = 
  	m_Cache.getCacheValues(m_Test.value(m_AttrIndex));
        m_Stop = te.value;
        m_MissingProb = te.pmiss;
      }
      else {
        generateAttrDistribution();
        // we have to compute the parameters
        if (m_BlendMethod == B_ENTROPY) {
  	m_Stop = stopProbUsingEntropy();
        }
        else { // default is B_SPHERE
  	m_Stop = stopProbUsingBlend();
        }
        // store the values in cache
        m_Cache.store( m_Test.value(m_AttrIndex), m_Stop, m_MissingProb );
      }
      // we've got our m_Stop, then what?
      if (m_Train.isMissing(m_AttrIndex)) {
        transProb = m_MissingProb;
      }
      else {
        try {
  	transProb = (1.0 - m_Stop) / m_Test.attribute(m_AttrIndex).numValues();
  	if ( (int)m_Test.value(m_AttrIndex) == 
  	     (int)m_Train.value(m_AttrIndex) )
  	  {
  	    transProb += m_Stop;
  	  }
        } catch (Exception e) {
  	e.printStackTrace();
        }
      }
      return transProb;
    }
    
    /**
     * Calculates the "stop parameter" for this attribute using
     * the entropy method: the value is computed using a root finder
     * algorithm. The method takes advantage of the calculation to
     * compute the smallest and average transformation probabilities
     * once the stop factor is obtained. It also sets the transformation
     * probability to an attribute with a missing value.
     *
     * @return the value of the stop parameter.
     *
     */
    private double stopProbUsingEntropy() {
      String debug = "(KStarNominalAttribute.stopProbUsingEntropy)";
      if ( m_ClassType != Attribute.NOMINAL ) {
        System.err.println("Error: "+debug+" attribute class must be nominal!");
        System.exit(1);
      }
      int itcount = 0;
      double stopProb;
      double lower, upper, pstop;
      double bestminprob = 0.0, bestpsum = 0.0;
      double bestdiff = 0.0, bestpstop = 0.0;
      double currentdiff, lastdiff, stepsize, delta;
      
      KStarWrapper botvals = new KStarWrapper();
      KStarWrapper upvals = new KStarWrapper();
      KStarWrapper vals = new KStarWrapper();
  
      // Initial values for root finder
      lower = 0.0 + ROOT_FINDER_ACCURACY/2.0;
      upper = 1.0 - ROOT_FINDER_ACCURACY/2.0;
      
      // Find (approx) entropy ranges
      calculateEntropy(upper, upvals);
      calculateEntropy(lower, botvals);
      
      if (upvals.avgProb == 0) {
        // When there are no training instances with the test value:
        // doesn't matter what exact value we use for pstop, just acts as
        // a constant scale factor in this case.
        calculateEntropy(lower, vals);
      }
      else
        {
  	// Optimise the scale factor
  	if ( (upvals.randEntropy - upvals.actEntropy < 
  	      botvals.randEntropy - botvals.actEntropy) &&
  	     (botvals.randEntropy - botvals.actEntropy > FLOOR) )
  	  {
  	    bestpstop = pstop = lower;
  	    stepsize = INITIAL_STEP;
  	    bestminprob = botvals.minProb;
  	    bestpsum = botvals.avgProb;
  	  }
  	else {
  	  bestpstop = pstop = upper;
  	  stepsize = -INITIAL_STEP;
  	  bestminprob = upvals.minProb;
  	  bestpsum = upvals.avgProb;
  	}
  	bestdiff = currentdiff = FLOOR;
  	itcount = 0;
  	/* Enter the root finder */
  	while (true)
  	  {
  	    itcount++;	
  	    lastdiff = currentdiff;
  	    pstop += stepsize;
  	    if (pstop <= lower) {
  	      pstop = lower;
  	      currentdiff = 0.0;
  	      delta = -1.0;
  	    }
  	    else if (pstop >= upper) {
  	      pstop = upper;
  	      currentdiff = 0.0;
  	      delta = -1.0;
  	    }
  	    else {
  	      calculateEntropy(pstop, vals);
  	      currentdiff = vals.randEntropy - vals.actEntropy;
  
  	      if (currentdiff < FLOOR) {
  		currentdiff = FLOOR;
  		if ((Math.abs(stepsize) < INITIAL_STEP) && 
  		    (bestdiff == FLOOR)) {
  		  bestpstop = lower;
  		  bestminprob = botvals.minProb;
  		  bestpsum = botvals.avgProb;
  		  break;
  		}
  	      }
  	      delta = currentdiff - lastdiff;
  	    }
  	    if (currentdiff > bestdiff) {
  	      bestdiff = currentdiff;
  	      bestpstop = pstop;
  	      bestminprob = vals.minProb;
  	      bestpsum = vals.avgProb;
  	    }
  	    if (delta < 0) {
  	      if (Math.abs(stepsize) < ROOT_FINDER_ACCURACY) {
  		break;
  	      }
  	      else {
  		stepsize /= -2.0;
  	      }
  	    }
  	    if (itcount > ROOT_FINDER_MAX_ITER) {
  	      break;
  	    }
  	  }
        }
      
      m_SmallestProb = bestminprob;
      m_AverageProb = bestpsum;
      // Set the probability of transforming to a missing value
      switch ( m_MissingMode )
        {
        case M_DELETE:
  	m_MissingProb = 0.0;
  	break;
        case M_NORMAL:
  	m_MissingProb = 1.0;
  	break;
        case M_MAXDIFF:
  	m_MissingProb = m_SmallestProb;
  	break;
        case M_AVERAGE:
  	m_MissingProb = m_AverageProb;
  	break;
        }
  
      if ( Math.abs(bestpsum - (double)m_TotalCount) < EPSILON) { 
        // No difference in the values
        stopProb = 1.0;
      }
      else {
        stopProb = bestpstop;
      }
      return stopProb;
    }
  
    /**
     * Calculates the entropy of the actual class prediction
     * and the entropy for random class prediction. It also
     * calculates the smallest and average transformation probabilities.
     *
     * @param stop the stop parameter
     * @param params the object wrapper for the parameters:
     * actual entropy, random entropy, average probability and smallest 
     * probability.
     * @return the values are returned in the object "params".
     *
     */
    private void calculateEntropy( double stop, KStarWrapper params) {
      String debug = "(KStarNominalAttribute.calculateEntropy)";
      int i,j,k;
      Instance train;
      double actent = 0.0, randent=0.0;
      double pstar, tprob, psum=0.0, minprob=1.0;
      double actClassProb, randClassProb;
      double [][] pseudoClassProb = new double[NUM_RAND_COLS+1][m_NumClasses];
      // init ...
      for(j = 0; j <= NUM_RAND_COLS; j++) {
        for(i = 0; i < m_NumClasses; i++) {
  	pseudoClassProb[j][i] = 0.0;
        }
      }
      for (i=0; i < m_NumInstances; i++) {
        train = m_TrainSet.instance(i);
        if (!train.isMissing(m_AttrIndex)) {
  	pstar = PStar(m_Test, train, m_AttrIndex, stop);
  	tprob = pstar / m_TotalCount;
  	if (pstar < minprob) {
  	  minprob = pstar;
  	}
  	psum += tprob;
  	// filter instances with same class value
  	for (k=0 ; k <= NUM_RAND_COLS ; k++) {
  	  // instance i is assigned a random class value in colomn k;
  	  // colomn k = NUM_RAND_COLS contains the original mapping: 
  	  // instance -> class vlaue
  	  pseudoClassProb[k][ m_RandClassCols[k][i] ] += tprob;
  	}
        }
      }
      // compute the actual entropy using the class probs
      // with the original class value mapping (colomn NUM_RAND_COLS)
      for (j=m_NumClasses-1; j>=0; j--) {
        actClassProb = pseudoClassProb[NUM_RAND_COLS][j] / psum;
        if (actClassProb > 0) {
      	actent -= actClassProb * Math.log(actClassProb) / LOG2;
        }
      }
      // compute a random entropy using the pseudo class probs
      // excluding the colomn NUM_RAND_COLS
      for (k=0; k < NUM_RAND_COLS;k++) {
        for (i = m_NumClasses-1; i >= 0; i--) {
    	randClassProb = pseudoClassProb[k][i] / psum;
    	if (randClassProb > 0) {
    	  randent -= randClassProb * Math.log(randClassProb) / LOG2;
  	}
        }
      }
      randent /= NUM_RAND_COLS;
      // return the results ... Yuk !!!
      params.actEntropy = actent;
      params.randEntropy = randent;
      params.avgProb = psum;
      params.minProb = minprob;
    }
    
    /**
     * Calculates the "stop parameter" for this attribute using
     * the blend method: the value is computed using a root finder
     * algorithm. The method takes advantage of this calculation to
     * compute the smallest and average transformation probabilities
     * once the stop factor is obtained. It also sets the transformation
     * probability to an attribute with a missing value.
     *
     * @return the value of the stop parameter.
     *
     */
    private double stopProbUsingBlend() {
      String debug = "(KStarNominalAttribute.stopProbUsingBlend) ";
      int itcount = 0;
      double stopProb, aimfor;
      double lower, upper, tstop;
  
      KStarWrapper botvals = new KStarWrapper();
      KStarWrapper upvals = new KStarWrapper();
      KStarWrapper vals = new KStarWrapper();
  
      int testvalue = (int)m_Test.value(m_AttrIndex);
      aimfor = (m_TotalCount - m_Distribution[testvalue]) * 
        (double)m_BlendFactor / 100.0 + m_Distribution[testvalue];
  
      // Initial values for root finder
      tstop = 1.0 - (double)m_BlendFactor / 100.0;
      lower = 0.0 + ROOT_FINDER_ACCURACY/2.0;
      upper = 1.0 - ROOT_FINDER_ACCURACY/2.0;
  
      // Find out function border values
      calculateSphereSize(testvalue, lower, botvals);
      botvals.sphere -= aimfor;
      calculateSphereSize(testvalue, upper, upvals);
      upvals.sphere -= aimfor;
      
      if (upvals.avgProb == 0) {
        // When there are no training instances with the test value:
        // doesn't matter what exact value we use for tstop, just acts as
        // a constant scale factor in this case.
        calculateSphereSize(testvalue, tstop, vals);
      }
      else if (upvals.sphere > 0) {
        // Can't include aimfor instances, going for min possible
        tstop = upper;
        vals.avgProb = upvals.avgProb;
      }
      else {
        // Enter the root finder
        for (;;) {
  	itcount++;
  	calculateSphereSize(testvalue, tstop, vals);
  	vals.sphere -= aimfor;
  	if ( Math.abs(vals.sphere) <= ROOT_FINDER_ACCURACY ||
  	     itcount >= ROOT_FINDER_MAX_ITER )
  	  {
  	    break;
  	  }
  	if (vals.sphere > 0.0) {
  	  lower = tstop;
  	  tstop = (upper + lower) / 2.0;
  	}
  	else {
  	  upper = tstop;
  	  tstop = (upper + lower) / 2.0;
  	}
        }
      }
  
      m_SmallestProb = vals.minProb;
      m_AverageProb = vals.avgProb;
      // Set the probability of transforming to a missing value
      switch ( m_MissingMode )
        {
        case M_DELETE:
  	m_MissingProb = 0.0;
  	break;
        case M_NORMAL:
  	m_MissingProb = 1.0;
  	break;
        case M_MAXDIFF:
  	m_MissingProb = m_SmallestProb;
  	break;
        case M_AVERAGE:
  	m_MissingProb = m_AverageProb;
  	break;
        }
      
      if ( Math.abs(vals.avgProb - m_TotalCount) < EPSILON) { 
        // No difference in the values
        stopProb = 1.0;
      }
      else {
        stopProb = tstop;
      }
      return stopProb;
    }
    
    /**
     * Calculates the size of the "sphere of influence" defined as:
     * sphere = sum(P^2)/sum(P)^2
     * P(i|j) = (1-tstop)*P(i) + ((i==j)?tstop:0).
     * This method takes advantage of the calculation to compute the values of
     * the "smallest" and "average" transformation probabilities when using
     * the specified stop parameter.
     *
     * @param testValue the value of the test instance
     * @param stop the stop parameter
     * @param params a wrapper of the parameters to be computed:
     * "sphere" the sphere size
     * "avgprob" the average transformation probability
     * "minProb" the smallest transformation probability
     * @return the values are returned in "params" object.
     *
     */
    private void calculateSphereSize(int testvalue, double stop, 
  				   KStarWrapper params) {
      String debug = "(KStarNominalAttribute.calculateSphereSize) ";
      int i, thiscount;
      double tprob, tval = 0.0, t1 = 0.0;
      double sphere, minprob = 1.0, transprob = 0.0;
  
      for(i = 0; i < m_Distribution.length; i++) {
        thiscount = m_Distribution[i];
        if ( thiscount != 0 ) {
  	if ( testvalue == i ) {
  	  tprob = (stop + (1 - stop) / m_Distribution.length) / m_TotalCount;
  	  tval += tprob * thiscount;
  	  t1 += tprob * tprob * thiscount;
  	}
  	else {
  	  tprob = ((1 - stop) / m_Distribution.length) / m_TotalCount;
  	  tval += tprob * thiscount;
  	  t1 += tprob * tprob * thiscount;
  	}
  	if ( minprob > tprob * m_TotalCount ) {
  	  minprob = tprob * m_TotalCount;
  	}
        }
      }
      transprob = tval;
      sphere = (t1 == 0) ? 0 : ((tval * tval) / t1);
      // return values ... Yck!!!
      params.sphere = sphere;
      params.avgProb = transprob;
      params.minProb = minprob;
    }
    
    /**
     * Calculates the nominal probability function defined as:
     * P(i|j) = (1-stop) * P(i) + ((i==j) ? stop : 0)
     * In this case, it calculates the transformation probability of the
     * indexed test attribute to the indexed train attribute.
     *
     * @param test the test instance
     * @param train the train instance
     * @param col the attribute index
     * @return the value of the tranformation probability.
     *
     */
    private double PStar(Instance test, Instance train, int col, double stop) {
      String debug = "(KStarNominalAttribute.PStar) ";
      double pstar;
      int numvalues = 0;
      try {
        numvalues = test.attribute(col).numValues();
      } catch (Exception ex) {
        ex.printStackTrace();
      }
      if ( (int)test.value(col) == (int)train.value(col) ) {
        pstar = stop + (1 - stop) / numvalues;
      }
      else {
        pstar = (1 - stop) / numvalues;
      }
      return pstar;
    }
    
    /**
     * Calculates the distribution, in the dataset, of the indexed nominal
     * attribute values. It also counts the actual number of training instances
     * that contributed (those with non-missing values) to calculate the 
     * distribution.
     */
    private void generateAttrDistribution() {
      String debug = "(KStarNominalAttribute.generateAttrDistribution)";
      m_Distribution = new int[ m_TrainSet.attribute(m_AttrIndex).numValues() ];
      int i;
      Instance train;
      for (i=0; i < m_NumInstances; i++) {
        train = m_TrainSet.instance(i);
        if ( !train.isMissing(m_AttrIndex) ) {
  	m_TotalCount++;
  	m_Distribution[(int)train.value(m_AttrIndex)]++;
        }
      }
    }
  
    /**
     * Sets the options.
     *
     */
    public void setOptions(int missingmode, int blendmethod, int blendfactor) {
      m_MissingMode = missingmode;
      m_BlendMethod = blendmethod;
      m_BlendFactor = blendfactor;
    }
    
    /**
     * Returns the revision string.
     * 
     * @return		the revision
     */
    public String getRevision() {
      return RevisionUtils.extract("$Revision: 1.7 $");
    }
  } // class
  