kkconditionalestimator.java

数据挖掘estimators算法

/*
 *    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.
 */

/*
 *    KKConditionalEstimator.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.
 *
 * @author Len Trigg ([e-mail])
 * @version $Revision: 1.4 $
 */
public class KKConditionalEstimator implements ConditionalEstimator {

  /** Vector containing all of the values seen */
  private double [] m_Values;

  /** Vector containing all of the conditioning values seen */
  private double [] m_CondValues;

  /** Vector containing the associated weights */
  private double [] m_Weights;

  /**
   * Number of values stored in m_Weights, m_CondValues, and m_Values so far
   */
  private int m_NumValues;

  /** The sum of the weights so far */
  private double m_SumOfWeights;

  /** Current standard dev */
  private double m_StandardDev;

  /** Whether we can optimise the kernel summation */
  private boolean m_AllWeightsOne;

  /** The numeric precision */
  private double m_Precision;

  /**
   * 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_NumValues;
    int middle = 0;
    while (low < high) {
      middle = (low + high) / 2;
      double current = m_CondValues[middle];
      if (current == key) {
	double secondary = m_Values[middle];
	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;
  }

  /**
   * Round a data value using the defined precision for this estimator
   *
   * @param data the value to round
   * @return the rounded data value
   */
  private double round(double data) {

    return Math.rint(data / m_Precision) * m_Precision;
  }
  
  /**
   * Constructor
   *
   * @param precision the  precision to which numeric values are given. For
   * example, if the precision is stated to be 0.1, the values in the
   * interval (0.25,0.35] are all treated as 0.3. 
   */
  public KKConditionalEstimator(double precision) {

    m_CondValues = new double [50];
    m_Values = new double [50];
    m_Weights = new double [50];
    m_NumValues = 0;
    m_SumOfWeights = 0;
    m_StandardDev = 0;
    m_AllWeightsOne = true;
    m_Precision = precision;
  }

  /**
   * 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) {

    data = round(data);
    given = round(given);
    int insertIndex = findNearestPair(given, data);
    if ((m_NumValues <= insertIndex)
	|| (m_CondValues[insertIndex] != given)
	|| (m_Values[insertIndex] != data)) {
      if (m_NumValues < m_Values.length) {
	int left = m_NumValues - insertIndex; 
	System.arraycopy(m_Values, insertIndex, 
			 m_Values, insertIndex + 1, left);
	System.arraycopy(m_CondValues, insertIndex, 
			 m_CondValues, insertIndex + 1, left);
	System.arraycopy(m_Weights, insertIndex, 
			 m_Weights, insertIndex + 1, left);
	m_Values[insertIndex] = data;
	m_CondValues[insertIndex] = given;
	m_Weights[insertIndex] = weight;
	m_NumValues++;
      } else {
	double [] newValues = new double [m_Values.length*2];
	double [] newCondValues = new double [m_Values.length*2];
	double [] newWeights = new double [m_Values.length*2];
	int left = m_NumValues - insertIndex; 
	System.arraycopy(m_Values, 0, newValues, 0, insertIndex);
	System.arraycopy(m_CondValues, 0, newCondValues, 0, insertIndex);
	System.arraycopy(m_Weights, 0, newWeights, 0, insertIndex);
	newValues[insertIndex] = data;
	newCondValues[insertIndex] = given;
	newWeights[insertIndex] = weight;
	System.arraycopy(m_Values, insertIndex, 
			 newValues, insertIndex+1, left);
	System.arraycopy(m_CondValues, insertIndex, 
			 newCondValues, insertIndex+1, left);
	System.arraycopy(m_Weights, insertIndex, 
			 newWeights, insertIndex+1, left);
	m_NumValues++;
	m_Values = newValues;
	m_CondValues = newCondValues;
	m_Weights = newWeights;
      }
      if (weight != 1) {
	m_AllWeightsOne = false;
      }
    } else {
      m_Weights[insertIndex] += weight;
      m_AllWeightsOne = false;      
    }
    m_SumOfWeights += weight;
    double range = m_CondValues[m_NumValues-1] - m_CondValues[0];
    m_StandardDev = Math.max(range / Math.sqrt(m_SumOfWeights), 
			     // allow at most 3 sds within one interval
			     m_Precision / (2 * 3));
  }

  /**
   * 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) {

    Estimator result = new KernelEstimator(m_Precision);
    if (m_NumValues == 0) {
      return result;
    }

    double delta = 0, currentProb = 0;
    double zLower, zUpper;
    for(int i = 0; i < m_NumValues; i++) {
      delta = m_CondValues[i] - given;
      zLower = (delta - (m_Precision / 2)) / m_StandardDev;
      zUpper = (delta + (m_Precision / 2)) / m_StandardDev;
      currentProb = (Statistics.normalProbability(zUpper)
		     - Statistics.normalProbability(zLower));
      result.addValue(m_Values[i], currentProb * m_Weights[i]);
    }
    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() {

    String result = "KK Conditional Estimator. " 
      + m_NumValues + " Normal Kernels:\n"
      + "StandardDev = " + Utils.doubleToString(m_StandardDev,4,2) 
      + "  \nMeans =";
    for(int i = 0; i < m_NumValues; i++) {
      result += " (" + m_Values[i] + ", " + m_CondValues[i] + ")";
      if (!m_AllWeightsOne) {
	  result += "w=" + m_Weights[i];
      }
    }
    return result;
  }

  /**
   * Main method for testing this class. Creates some random points
   * in the range 0 - 100, 
   * and prints out a distribution conditional on some value
   *
   * @param argv should contain: seed conditional_value numpoints
   */
  public static void main(String [] argv) {

    try {
      int seed = 42;
      if (argv.length > 0) {
	seed = Integer.parseInt(argv[0]);
      }
      KKConditionalEstimator newEst = new KKConditionalEstimator(0.1);

      // 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());
    }
  }
}