weightedmahalanobis.java

wekaUT是 university texas austin 开发的基于weka的半指导学习(semi supervised learning)的分类器

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

/*
 *    WeightedMahalanobis.java
 *    Copyright (C) 2001 Mikhail Bilenko
 *
 */

package weka.core.metrics;

import weka.clusterers.InstancePair; 
import weka.core.*;
import java.util.*;

import Jama.Matrix;
import Jama.EigenvalueDecomposition;

/** 
 * WeightedMahalanobis class
 *
 * Implements a weighted Mahalanobis distance metric weighted by a full matrix of weights. 
 *
 * @author Mikhail Bilenko ([e-mail])
 * @version $Revision: 1.10 $
 */

public class WeightedMahalanobis extends  LearnableMetric implements OptionHandler {
  /** The full matrix of attribute weights */
  protected double[][] m_weightsMatrix = null;
  /** weights^0.5, used to project instances to the new space to speed up calculations */
  protected double[][] m_weightsMatrixSquare = null; 

  /** A hash where instances are projected using the weights */
  protected HashMap m_projectedInstanceHash = null;

  /** Max instance storage (max is in the space of projected instances, values are in **ORIGINAL** space)
   *  Currently somewhat convoluted, TODO:  re-write the max value code in MPCKMeans */
  protected double [][] m_maxPoints = null;
  // store the hypercube in the projected space
  protected double [][] m_maxProjPoints = null;  

  /** We can have different ways of converting from distance to similarity  */
  public static final int CONVERSION_LAPLACIAN = 1;
  public static final int CONVERSION_UNIT = 2;
  public static final int CONVERSION_EXPONENTIAL = 4;
  public static final Tag[] TAGS_CONVERSION = {
    new Tag(CONVERSION_UNIT, "similarity = 1-distance"),
    new Tag(CONVERSION_LAPLACIAN, "similarity=1/(1+distance)"),
    new Tag(CONVERSION_EXPONENTIAL, "similarity=exp(-distance)")
      };
  /** The method of converting, by default laplacian */
  protected int m_conversionType = CONVERSION_LAPLACIAN;

  /**
   * Create a new metric.
   * @param numAttributes the number of attributes that the metric will work on
   */ 
  public WeightedMahalanobis(int numAttributes) throws Exception {
    buildMetric(numAttributes);
  }

  /** Create a default new metric */
  public WeightedMahalanobis() {
  } 
   
  /**
   * Creates a new metric which takes specified attributes.
   *
   * @param _attrIdxs An array containing attribute indeces that will
   * be used in the metric
   */
  public WeightedMahalanobis(int[] _attrIdxs) throws Exception {
    setAttrIdxs(_attrIdxs);
    buildMetric(_attrIdxs.length);	
  }

  /**
   * Reset all values that have been learned
   */
  public void resetMetric() throws Exception {
    m_trained = false;
    m_projectedInstanceHash = new HashMap();
    if (m_weightsMatrix != null) { 
      for (int i = 0; i < m_weightsMatrix.length; i++) {
	Arrays.fill(m_weightsMatrix[i], 0);
	Arrays.fill(m_weightsMatrixSquare[i], 0);
	m_weightsMatrix[i][i] = 1;
	m_weightsMatrixSquare[i][i] = 1; 
      }
    }
    recomputeNormalizer();
    recomputeRegularizer();
  }

  /**
   * Generates a new Metric. Has to initialize all fields of the metric
   * with default values.
   *
   * @param numAttributes the number of attributes that the metric will work on
   * @exception Exception if the distance metric has not been
   * generated successfully.
   */
  public void buildMetric(int numAttributes) throws Exception {
    m_numAttributes = numAttributes;
    m_weightsMatrix = new double[numAttributes][numAttributes];
    m_weightsMatrixSquare = new double[numAttributes][numAttributes];
    m_maxProjPoints = new double[2][numAttributes];
    m_attrIdxs = new int[numAttributes];
    for (int i = 0; i < numAttributes; i++) {
      m_attrIdxs[i] = i;
    }
    resetMetric();
  }

    
  /**
   * Generates a new Metric. Has to initialize all fields of the metric
   * with default values
   *
   * @param options an array of options suitable for passing to setOptions.
   * May be null. 
   * @exception Exception if the distance metric has not been
   * generated successfully.
   */
  public void buildMetric(int numAttributes, String[] options) throws Exception {
    buildMetric(numAttributes);
  }

  /**
   * Create a new metric for operating on specified instances
   * @param data instances that the metric will be used on
   */
  public  void buildMetric(Instances data) throws Exception {
    m_classIndex = data.classIndex();
    m_numAttributes = data.numAttributes();
    if (m_classIndex != m_numAttributes-1 && m_classIndex != -1) {
      throw new Exception("Class attribute (" + m_classIndex + ") should be the last attribute!!!");
    }
    if (m_classIndex != -1) {
      m_numAttributes--;
    }
    System.out.println("About to build metric with " + m_numAttributes + " attributes, trainable=" + m_trainable);
    buildMetric(m_numAttributes);
    if (m_trainable) {
      learnMetric(data);
    }
  }
    
  
  /**
   * Returns a distance value between two instances. 
   * @param instance1 First instance.
   * @param instance2 Second instance.
   * @exception Exception if distance could not be estimated.
   */
  public double distance(Instance instance1, Instance instance2) throws Exception {
    double distance = 0; 
    if (m_weightsMatrixSquare != null) {
      double [] projValues1;
      double [] projValues2;
      if (m_projectedInstanceHash.containsKey(instance1)) {
	projValues1 = (double []) m_projectedInstanceHash.get(instance1);
      } else {
	projValues1 = projectInstance(instance1); 
      }

      if (m_projectedInstanceHash.containsKey(instance2)) {
	projValues2 = (double []) m_projectedInstanceHash.get(instance2);
      } else {
	projValues2 = projectInstance(instance2); 
      }

      double diff = 0;
      for (int i = 0; i < projValues1.length; i++) {
	if (i != m_classIndex) {
	  diff = projValues1[i] - projValues2[i];
	  distance += diff * diff;
	}
      }
    } else {  // do the full matrix computation
      //      System.out.println("full matrix");
      double[] diffValues = new double[m_weightsMatrix.length];
      for (int i = 0; i < diffValues.length; i++) {
	diffValues[i] = instance1.value(i) - instance2.value(i);
      }

      double [] xyM = new double[m_weightsMatrix.length];
      for (int i = 0; i < m_weightsMatrix.length; i++) {
	for (int j = 0; j < m_weightsMatrix.length; j++) {
	  xyM[i] += diffValues[j] * m_weightsMatrix[j][i];
	}
      }

      for (int i = 0; i < m_weightsMatrix.length; i++) {
	distance += xyM[i] * diffValues[i];
      }
    }
    distance = Math.sqrt(distance);
    return distance;
  }

  /** Return the penalty contribution - distance*distance */
  public double penalty(Instance instance1,
			Instance instance2) throws Exception {
    double distance = distance(instance1, instance2);
    return distance * distance; 
  }

  /** Return the penalty contribution - distance*distance */
  public double penaltySymmetric(Instance instance1,
			Instance instance2) throws Exception {
    double distance = distance(instance1, instance2);
    return distance * distance; 
  }
  

  /** given an instance, project it using the weights matrix and store it in the hash */
  public double[] projectInstance(Instance instance) {
    int numValues = instance.numValues();
    double[] values = instance.toDoubleArray();
    double[] projValues = new double[numValues];

    if (m_weightsMatrixSquare == null) {
      return null; 
    } 

    if (m_maxProjPoints == null) { 
      m_maxPoints = new double [2][m_weightsMatrix.length];
      m_maxProjPoints = new double[2][m_weightsMatrix.length];
      Arrays.fill(m_maxProjPoints[0], Double.MAX_VALUE);
      Arrays.fill(m_maxProjPoints[1], Double.MIN_VALUE);
    }
    
    for (int i = 0; i < m_weightsMatrix.length; i++) {
      if (i != m_classIndex) {
	for (int j = 0; j < m_weightsMatrix.length; j++) {
	  projValues[i] += values[j] * m_weightsMatrixSquare[j][i];
	}

	// update the enclosing maxPoints
	if (projValues[i] < m_maxProjPoints[0][i]) {
	  m_maxProjPoints[0][i] = projValues[i];
	}
	if (projValues[i] > m_maxProjPoints[1][i]) {
	  m_maxProjPoints[1][i] = projValues[i];
	} 
      } else { // class attribute
	projValues[i] = values[i];
      } 
    }
    m_projectedInstanceHash.put(instance, projValues);
    return projValues;
  }

  /** Get the maxPoints instances */
  public double [][] getMaxPoints(HashMap constraintMap, Instances instances) throws Exception {
    m_maxPoints = new double [2][m_weightsMatrix.length];
    InstancePair maxConstraint = null;
    double maxDistance = -Double.MIN_VALUE; 
    Iterator iterator = constraintMap.entrySet().iterator();
    while (iterator.hasNext()) {
      Map.Entry entry = (Map.Entry) iterator.next();
      int type = ((Integer) entry.getValue()).intValue();
      if (type == InstancePair.CANNOT_LINK) {
	InstancePair pair = (InstancePair) entry.getKey();
	int firstIdx = pair.first;
	int secondIdx = pair.second;
	Instance instance1 = instances.instance(firstIdx);
	Instance instance2 = instances.instance(secondIdx);
	double distance = distance(instance1, instance2);
	if (distance >= maxDistance) {
	  maxConstraint = pair;
	  maxDistance = distance; 
	}