/* *    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. *//* *    NNConditionalEstimator.java *    Copyright (C) 1999 Len Trigg * */package weka.estimators;import java.util.*;import weka.core.*;/**  * Conditional probability estimator for a numeric domain conditional upon * a numeric domain (using Mahalanobis distance). * * @author Len Trigg (trigg@cs.waikato.ac.nz) * @version $Revision: 1.4 $ */public class NNConditionalEstimator implements ConditionalEstimator {  /** Vector containing all of the values seen */  private Vector m_Values = new Vector();  /** Vector containing all of the conditioning values seen */  private Vector m_CondValues = new Vector();  /** Vector containing the associated weights */  private Vector m_Weights = new Vector();  /** The sum of the weights so far */  private double m_SumOfWeights;  /** Current Conditional mean */  private double m_CondMean;  /** Current Values mean */  private double m_ValueMean;  /** Current covariance matrix */  private Matrix m_Covariance;  /** Whether we can optimise the kernel summation */  private boolean m_AllWeightsOne = true;  /** 2 * PI */  private static double TWO_PI = 2 * Math.PI;    // ===============  // Private methods  // ===============  /**   * Execute a binary search to locate the nearest data value   *   * @param key the data value to locate   * @param secondaryKey the data value to locate   * @return the index of the nearest data value   */  private int findNearestPair(double key, double secondaryKey) {        int low = 0;     int high = m_CondValues.size();    int middle = 0;    while (low < high) {      middle = (low + high) / 2;      double current = ((Double)m_CondValues.elementAt(middle)).doubleValue();      if (current == key) {	double secondary = ((Double)m_Values.elementAt(middle)).doubleValue();	if (secondary == secondaryKey) {	  return middle;	}	if (secondary > secondaryKey) {	  high = middle;	} else if (secondary < secondaryKey) {	  low = middle + 1;	}      }      if (current > key) {	high = middle;      } else if (current < key) {	low = middle + 1;      }    }    return low;  }  /** Calculate covariance and value means */  private void calculateCovariance() {        double sumValues = 0, sumConds = 0;    for(int i = 0; i < m_Values.size(); i++) {      sumValues += ((Double)m_Values.elementAt(i)).doubleValue()	* ((Double)m_Weights.elementAt(i)).doubleValue();      sumConds += ((Double)m_CondValues.elementAt(i)).doubleValue()	* ((Double)m_Weights.elementAt(i)).doubleValue();    }    m_ValueMean = sumValues / m_SumOfWeights;    m_CondMean = sumConds / m_SumOfWeights;    double c00 = 0, c01 = 0, c10 = 0, c11 = 0;    for(int i = 0; i < m_Values.size(); i++) {      double x = ((Double)m_Values.elementAt(i)).doubleValue();      double y = ((Double)m_CondValues.elementAt(i)).doubleValue();      double weight = ((Double)m_Weights.elementAt(i)).doubleValue();      c00 += (x - m_ValueMean) * (x - m_ValueMean) * weight;      c01 += (x - m_ValueMean) * (y - m_CondMean) * weight;      c11 += (y - m_CondMean) * (y - m_CondMean) * weight;    }    c00 /= (m_SumOfWeights - 1.0);    c01 /= (m_SumOfWeights - 1.0);    c10 = c01;    c11 /= (m_SumOfWeights - 1.0);    m_Covariance = new Matrix(2, 2);    m_Covariance.setElement(0, 0, c00);    m_Covariance.setElement(0, 1, c01);    m_Covariance.setElement(1, 0, c10);    m_Covariance.setElement(1, 1, c11);  }  /**   * Returns value for normal kernel   *   * @param x the argument to the kernel function   * @param variance the variance   * @return the value for a normal kernel   */  private double normalKernel(double x, double variance) {        return Math.exp(-x * x / (2 * variance)) / Math.sqrt(variance * TWO_PI);  }    /**   * Add a new data value to the current estimator.   *   * @param data the new data value    * @param given the new value that data is conditional upon    * @param weight the weight assigned to the data value    */  public void addValue(double data, double given, double weight) {        int insertIndex = findNearestPair(given, data);    if ((m_Values.size() <= insertIndex)	|| (((Double)m_CondValues.elementAt(insertIndex)).doubleValue()	    != given)	|| (((Double)m_Values.elementAt(insertIndex)).doubleValue()	    != data)) {      m_CondValues.insertElementAt(new Double(given), insertIndex);      m_Values.insertElementAt(new Double(data), insertIndex);      m_Weights.insertElementAt(new Double(weight), insertIndex);      if (weight != 1) {	m_AllWeightsOne = false;      }    } else {      double newWeight = ((Double)m_Weights.elementAt(insertIndex))	.doubleValue();      newWeight += weight;      m_Weights.setElementAt(new Double(newWeight), insertIndex);      m_AllWeightsOne = false;          }    m_SumOfWeights += weight;    // Invalidate any previously calculated covariance matrix    m_Covariance = null;  }  /**   * Get a probability estimator for a value   *   * @param data the value to estimate the probability of   * @param given the new value that data is conditional upon    * @return the estimator for the supplied value given the condition   */  public Estimator getEstimator(double given) {        if (m_Covariance == null) {      calculateCovariance();    }    Estimator result = new MahalanobisEstimator(m_Covariance,						given - m_CondMean,						m_ValueMean);    return result;  }  /**   * Get a probability estimate for a value   *   * @param data the value to estimate the probability of   * @param given the new value that data is conditional upon    * @return the estimated probability of the supplied value   */  public double getProbability(double data, double given) {        return getEstimator(given).getProbability(data);  }  /** Display a representation of this estimator */  public String toString() {        if (m_Covariance == null) {      calculateCovariance();    }    String result = "NN Conditional Estimator. "      + m_CondValues.size()       + " data points.  Mean = " + Utils.doubleToString(m_ValueMean, 4, 2)      + "  Conditional mean = " + Utils.doubleToString(m_CondMean, 4, 2);    result += "  Covariance Matrix: \n" + m_Covariance;    return result;  }  /**   * Main method for testing this class.   *   * @param argv should contain a sequence of numeric values   */  public static void main(String [] argv) {        try {      int seed = 42;      if (argv.length > 0) {	seed = Integer.parseInt(argv[0]);      }      NNConditionalEstimator newEst = new NNConditionalEstimator();      // Create 100 random points and add them      Random r = new Random(seed);            int numPoints = 50;      if (argv.length > 2) {	numPoints = Integer.parseInt(argv[2]);      }      for(int i = 0; i < numPoints; i++) {	int x = Math.abs(r.nextInt() % 100);	int y = Math.abs(r.nextInt() % 100);	System.out.println("# " + x + "  " + y);	newEst.addValue(x, y, 1);      }      //    System.out.println(newEst);      int cond;      if (argv.length > 1) {	cond = Integer.parseInt(argv[1]);      }      else cond = Math.abs(r.nextInt() % 100);      System.out.println("## Conditional = " + cond);      Estimator result = newEst.getEstimator(cond);      for(int i = 0; i <= 100; i+= 5) {	System.out.println(" " + i + "  " + result.getProbability(i));      }    } catch (Exception e) {      System.out.println(e.getMessage());    }  }}