nearestneighboursearch.java

矩阵的QR分解算法

      for(; current.m_Next != null; current = current.m_Next) {
        currentK++;
        currentDist = current.m_Distance;
        if ((currentK >= k) && (currentDist != current.m_Next.m_Distance)) {
          m_Last = current;
          current.m_Next = null;
          break;
        }
      }
    }
    
    /**
     * Prints out the contents of the neighborlist.
     */
    public void printList() {
      
      if (isEmpty()) {
        System.out.println("Empty list");
      } else {
        NeighborNode current = m_First;
        while (current != null) {
          System.out.println("Node: instance " + current.m_Instance
          + ", distance " + current.m_Distance);
          current = current.m_Next;
        }
        System.out.println();
      }
    }
    
    /**
     * returns the first element in the list.
     * 
     * @return			the first element
     */
    public NeighborNode getFirst() {
      return m_First;
    }
    
    /**
     * returns the last element in the list.
     * 
     * @return			the last element
     */
    public NeighborNode getLast() {
      return m_Last;
    }
    
  }
  
  /** The neighbourhood of instances to find neighbours in. */
  protected Instances m_Instances;
  
  /** The number of neighbours to find. */
  protected int m_kNN;

  /** the distance function used. */
  protected DistanceFunction m_DistanceFunction = new EuclideanDistance();

  /** Performance statistics. */
  protected PerformanceStats m_Stats = null;
  
  /** Should we measure Performance. */
  protected boolean m_MeasurePerformance = false;
  
  /**
   * Constructor.
   */
  public NearestNeighbourSearch() {
    if(m_MeasurePerformance)
      m_Stats = new PerformanceStats();
  }
  
  /**
   * Constructor. 
   * 
   * @param insts 	The set of instances that constitute the neighbourhood.
   */
  public NearestNeighbourSearch(Instances insts) {
    this();
    m_Instances = insts;
  }
  
  /**
   * Returns a string describing this nearest neighbour search algorithm.
   * 
   * @return 		a description of the algorithm for displaying in the 
   * 			explorer/experimenter gui
   */
  public String globalInfo() {
    return 
        "Abstract class for nearest neighbour search. All algorithms (classes) that "
      + "do nearest neighbour search should extend this class.";
  }

  /**
   * Returns an enumeration describing the available options.
   *
   * @return 		an enumeration of all the available options.
   */
  public Enumeration listOptions() {
    Vector newVector = new Vector();

    newVector.add(new Option(
	"\tDistance function to use.\n"
	+ "\t(default: weka.core.EuclideanDistance)",
	"A", 1,"-A <classname and options>"));
    
    newVector.add(new Option(
	"\tCalculate performance statistics.",
	"P", 0,"-P"));
    
    return newVector.elements();
  }
  
  /**
   * Parses a given list of options. Valid options are:
   *
   <!-- options-start -->
   <!-- options-end -->
   *
   * @param options 	the list of options as an array of strings
   * @throws Exception 	if an option is not supported
   */
  public void setOptions(String[] options) throws Exception {
    String nnSearchClass = Utils.getOption('A', options);
    if(nnSearchClass.length() != 0) {
      String nnSearchClassSpec[] = Utils.splitOptions(nnSearchClass);
      if(nnSearchClassSpec.length == 0) { 
        throw new Exception("Invalid DistanceFunction specification string."); 
      }
      String className = nnSearchClassSpec[0];
      nnSearchClassSpec[0] = "";

      setDistanceFunction( (DistanceFunction)
                            Utils.forName( DistanceFunction.class, 
                                           className, nnSearchClassSpec) );
    }
    else {
      setDistanceFunction(new EuclideanDistance());
    }
    
    setMeasurePerformance(Utils.getFlag('P',options));
  }

  /**
   * Gets the current settings.
   *
   * @return 		an array of strings suitable for passing to setOptions()
   */
  public String [] getOptions() {
    Vector<String>	result;
    
    result = new Vector<String>();

    result.add("-A");
    result.add((m_DistanceFunction.getClass().getName() + " " +
                   Utils.joinOptions(m_DistanceFunction.getOptions())).trim());
    
    if(getMeasurePerformance())
      result.add("-P");
    
    return result.toArray(new String[result.size()]);
  }

  /** 
   * Returns the tip text for this property.
   * 
   * @return 		tip text for this property suitable for
   *         		displaying in the explorer/experimenter gui
   */
  public String distanceFunctionTipText() {
    return "The distance function to use for finding neighbours " +
           "(default: weka.core.EuclideanDistance). ";
  }
  
  /**
   * returns the distance function currently in use.
   * 
   * @return		the distance function
   */
  public DistanceFunction getDistanceFunction() {
    return m_DistanceFunction;
  }
  
  /**
   * sets the distance function to use for nearest neighbour search.
   * 
   * @param df		the new distance function to use
   * @throws Exception	if instances cannot be processed
   */
  public void setDistanceFunction(DistanceFunction df) throws Exception {
    m_DistanceFunction = df;
  }

  /** 
   * Returns the tip text for this property.
   * 
   * @return 		tip text for this property suitable for
   *         		displaying in the explorer/experimenter gui
   */
  public String measurePerformanceTipText() {
    return "Whether to calculate performance statistics " +
           "for the NN search or not";
  }
  
  /**
   * Gets whether performance statistics are being calculated or not.
   * 
   * @return		true if the measure performance is calculated
   */
  public boolean getMeasurePerformance() {
    return m_MeasurePerformance;
  }
  
  /**
   * Sets whether to calculate the performance statistics or not.
   * 
   * @param measurePerformance	if true then the performance is calculated
   */
  public void setMeasurePerformance(boolean measurePerformance) {
    m_MeasurePerformance = measurePerformance;
    if(m_MeasurePerformance) {
      if(m_Stats==null)
        m_Stats = new PerformanceStats();
    }
    else
      m_Stats = null;
  }
    
  /** 
   * Returns the nearest instance in the current neighbourhood to the supplied
   * instance.
   * 
   * @param target 	The instance to find the nearest neighbour for.
   * @return		the nearest neighbor
   * @throws Exception 	if the nearest neighbour could not be found.
   */
  public abstract Instance nearestNeighbour(Instance target) throws Exception;
  
  /**
   * Returns k nearest instances in the current neighbourhood to the supplied
   * instance.
   *  
   * @param target 	The instance to find the k nearest neighbours for.
   * @param k		The number of nearest neighbours to find.
   * @return		the k nearest neighbors
   * @throws Exception 	if the neighbours could not be found.
   */
  public abstract Instances kNearestNeighbours(Instance target, int k) throws Exception;
 
  /**
   * Returns the distances of the k nearest neighbours. The kNearestNeighbours
   * or nearestNeighbour needs to be called first for this to work.
   *
   * @return		the distances
   * @throws Exception 	if called before calling kNearestNeighbours
   *            	or nearestNeighbours.
   */
  public abstract double[] getDistances() throws Exception;
  
  /**
   * Updates the NearNeighbourSearch algorithm for the new added instance.
   * P.S.: The method assumes the instance has already been added to the 
   * m_Instances object by the caller.
   * 
   * @param ins		the instance to add
   * @throws Exception	if updating fails
   */
  public abstract void update(Instance ins) throws Exception;

  /** 
   * Adds information from the given instance without modifying the 
   * datastructure a lot.
   * 
   * @param ins		the instance to add the information from
   */
  public void addInstanceInfo(Instance ins) {
  }
  
  /**
   * Sets the instances.
   * 
   * @param insts	the instances to use
   * @throws Exception	if setting fails
   */
  public void setInstances(Instances insts) throws Exception {
    m_Instances = insts;
  }
  
  /** 
   * returns the instances currently set.
   * 
   * @return		the current instances
   */
  public Instances getInstances() {
    return m_Instances;
  }

  /** 
   * Gets the class object that contains the performance statistics of
   * the search method. 
   * 
   * @return		the performance statistics
   */
  public PerformanceStats getPerformanceStats() {
    return m_Stats;
  }

  /**
   * Returns an enumeration of the additional measure names.
   * 
   * @return 		an enumeration of the measure names
   */
  public Enumeration enumerateMeasures() {
    Vector newVector; 
    if(m_Stats == null) {
      newVector = new Vector(0);
    }
    else {
      newVector = new Vector();
      Enumeration en = m_Stats.enumerateMeasures();
      while(en.hasMoreElements())
        newVector.add(en.nextElement());
    }
    return newVector.elements();
  }
  
  /**
   * Returns the value of the named measure.
   * 
   * @param additionalMeasureName 	the name of the measure to query for 
   * 					its value
   * @return 				the value of the named measure
   * @throws IllegalArgumentException 	if the named measure is not supported
   */
  public double getMeasure(String additionalMeasureName) {
    if(m_Stats==null)
      throw new IllegalArgumentException(additionalMeasureName 
        + " not supported (NearestNeighbourSearch)");
    else
      return m_Stats.getMeasure(additionalMeasureName);
  }

  /** 
   * sorts the two given arrays.
   * 
   * @param arrayToSort 	The array sorting should be based on.
   * @param linkedArray		The array that should have the same ordering as 
   * 				arrayToSort.
   */
  public static void combSort11(double arrayToSort[], int linkedArray[]) {
    int switches, j, top, gap;
    double hold1; int hold2;
    gap = arrayToSort.length;
    do {
      gap=(int)(gap/1.3);
      switch(gap) {
        case 0:
          gap = 1;
          break;
        case 9:
        case 10:
          gap=11;
          break;
        default:
          break;
      }
      switches=0;
      top = arrayToSort.length-gap;
      for(int i=0; i<top; i++) {
        j=i+gap;
        if(arrayToSort[i] > arrayToSort[j]) {
          hold1=arrayToSort[i];
          hold2=linkedArray[i];
          arrayToSort[i]=arrayToSort[j];
          linkedArray[i]=linkedArray[j];
          arrayToSort[j]=hold1;
          linkedArray[j]=hold2;
          switches++;
        }//endif
      }//endfor
    } while(switches>0 || gap>1);
  }
   
  /**
   * Partitions the instances around a pivot. Used by quicksort and
   * kthSmallestValue.
   *
   * @param arrayToSort 	the array of doubles to be sorted
   * @param linkedArray		the linked array
   * @param l 			the first index of the subset 
   * @param r 			the last index of the subset 
   * @return 			the index of the middle element
   */
  protected static int partition(double[] arrayToSort, double[] linkedArray, int l, int r) {
    double pivot = arrayToSort[(l + r) / 2];
    double help;

    while (l < r) {
      while ((arrayToSort[l] < pivot) && (l < r)) {
        l++;
      }
      while ((arrayToSort[r] > pivot) && (l < r)) {
        r--;
      }
      if (l < r) {
        help = arrayToSort[l];
        arrayToSort[l] = arrayToSort[r];
        arrayToSort[r] = help;
        help = linkedArray[l];
        linkedArray[l] = linkedArray[r];
        linkedArray[r] = help;
        l++;
        r--;
      }
    }
    if ((l == r) && (arrayToSort[r] > pivot)) {
      r--;
    } 

    return r;
  }
  
  /**
   * performs quicksort.
   * 
   * @param arrayToSort		the array to sort
   * @param linkedArray		the linked array
   * @param left 		the first index of the subset 
   * @param right		the last index of the subset 
   */
  public static void quickSort(double[] arrayToSort, double[] linkedArray, int left, int right) {
    if (left < right) {
      int middle = partition(arrayToSort, linkedArray, left, right);
      quickSort(arrayToSort, linkedArray, left, middle);
      quickSort(arrayToSort, linkedArray, middle + 1, right);
    }
  }
}