covertree.java

矩阵的QR分解算法

      	m_TreeStats.incrPointCount();
    }
    
    //if root is the only node
    if(m_Root.num_children==0) {
      NeighborList list = new NeighborList(k);
      list.insertSorted(d, m_Root.p());
      return list;
    }
    //else
    while(cover_set_current.length>0) {
      cover_set_next = new Stack<d_node>();
      for(int i=0; i<cover_set_current.length; i++) {
	par = cover_set_current.element(i);
	parent = par.n;
	for(int c=0; c<parent.num_children; c++) {
	  child = parent.children.element(c);
	  upper_bound = upper_k.peek().distance;
	  if(c==0)
	    d = par.dist;
	  else {
	    d = upper_bound + child.max_dist;
	    d = Math.sqrt(m_DistanceFunction.distance(child.p(), target, d*d, m_TreeStats));
	      if(m_TreeStats!=null)
		m_TreeStats.incrPointCount();
	  }
	  if(d <= (upper_bound + child.max_dist)) {
	    if(c>0 && d < upper_bound) {
	      update(upper_k, d);
	    }
	    if(child.num_children > 0) {
	      cover_set_next.push(new d_node(d, child));
	      if(m_TreeStats!=null)
		m_TreeStats.incrIntNodeCount();
	    }
	    else if (d <= upper_bound){
	      zero_set.push(new d_node(d, child));
	      if(m_TreeStats!=null)
		m_TreeStats.incrLeafCount();
	    }
	  }
	} //end for current_set children
      } //end for current_set elements
      cover_set_current = cover_set_next;
    } //end while(curret_set not empty)
    
    NeighborList list = new NeighborList(k);
    d_node tmpnode;
    upper_bound = upper_k.peek().distance;      
    for(int i=0; i<zero_set.length; i++) {
      tmpnode = zero_set.element(i);
      if(tmpnode.dist <= upper_bound)
	list.insertSorted(tmpnode.dist, tmpnode.n.p());
    }
    
    if(list.currentLength()<=0)
      throw new Exception("Error: No neighbour found. This cannot happen");
    
    return list;
  }
  
/*********************************NNSearch related stuff above.********************/  

  /**
   * Returns k-NNs of a given target instance, from among the previously
   * supplied training instances (supplied through setInstances method)
   * P.S.: May return more than k-NNs if more one instances have
   * the same distance to the target as the kth NN.
   * 
   * @param target The instance for which k-NNs are required.
   * @param k The number of k-NNs to find.
   * @return The k-NN instances of the given target instance. 
   * @throws Exception If there is some problem find the k-NNs.
   */
  public Instances kNearestNeighbours(Instance target, int k) throws Exception {
    if(m_Stats!=null)
      m_Stats.searchStart();
    CoverTree querytree = new CoverTree();
    Instances insts = new Instances(m_Instances, 0);
    insts.add(target);
    querytree.setInstances(insts);
    Stack<NeighborList> result = new Stack<NeighborList>();
    batch_nearest_neighbor(k, this.m_Root, querytree.m_Root, result);
    if(m_Stats!=null)
      m_Stats.searchFinish();

    insts = new Instances(m_Instances, 0);
    NeighborNode node = result.element(0).getFirst();
    m_DistanceList = new double[result.element(0).currentLength()];
    int i=0;
    while(node != null) {
      insts.add(node.m_Instance);
      m_DistanceList[i] = node.m_Distance;
      i++; node = node.m_Next;
    }
    return insts;
  }
  
  /**
   * Returns the NN instance of a given target instance, from among
   * the previously supplied training instances.
   * 
   * @param target The instance for which NN is required.
   * @throws Exception If there is some problem finding the nearest
   * neighbour.
   * @return The NN instance of the target instance.
   */
  public Instance nearestNeighbour(Instance target) throws Exception {
    return kNearestNeighbours(target, 1).instance(0);
  }

  /**
   * Returns the distances of the (k)-NN(s) found earlier
   * by kNearestNeighbours()/nearestNeighbour().
   * 
   * @throws Exception If the tree hasn't been built (by calling 
   * setInstances()), or none of kNearestNeighbours() or 
   * nearestNeighbour() has been called before. 
   * @return The distances (in the same order) of the k-NNs. 
   */
  public double[] getDistances() throws Exception {
    if(m_Instances==null || m_DistanceList==null)
      throw new Exception("The tree has not been supplied with a set of " +
	  		  "instances or getDistances() has been called " +
      			  "before calling kNearestNeighbours().");
    return m_DistanceList;
  }
  
  /**
   * Checks if there is any instance with missing values. Throws an
   * exception if there is, as KDTree does not handle missing values.
   * 
   * @param instances 	the instances to check
   * @throws Exception 	if missing values are encountered
   */
  protected void checkMissing(Instances instances) throws Exception {
    for (int i = 0; i < instances.numInstances(); i++) {
      Instance ins = instances.instance(i);
      for (int j = 0; j < ins.numValues(); j++) {
	if (ins.index(j) != ins.classIndex())
	  if (ins.isMissingSparse(j)) {
	    throw new Exception("ERROR: KDTree can not deal with missing "
		+ "values. Please run ReplaceMissingValues filter "
		+ "on the dataset before passing it on to the KDTree.");
	  }
      }
    }
  }

  /**
   * Builds the Cover Tree on the given set of instances.
   * 
   * @param instances The insts on which the Cover Tree is to be 
   * built. 
   * @throws Exception If some error occurs while 
   * building the Cover Tree
   */
  public void setInstances(Instances instances) throws Exception {
    super.setInstances(instances);
    buildCoverTree(instances);
  }

  /** 
   * Adds an instance to the cover tree. 
   * P.S.: The current version doesn't allow
   * addition of instances after batch construction.
   * 
   * @param ins The instance to add.
   * @throws Exception Alway throws this, as current 
   * implementation doesn't allow addition of instances 
   * after building.
   */
  public void update(Instance ins) throws Exception {
    throw new Exception("BottomUpConstruction method does not allow addition " +
    "of new Instances.");
  }

  /** 
   * Adds the given instance info. This implementation updates only the 
   * range datastructures of the EuclideanDistance. Nothing is 
   * required to be updated in the built Cover Tree.
   * 
   * @param ins 	The instance to add the information of. Usually this is
   * 			the test instance supplied to update the range of 
   * 			attributes in the distance function.
   */
  public void addInstanceInfo(Instance ins) {
    if(m_Instances!=null) {
      try {
      m_DistanceFunction.update(ins);
      } catch(Exception ex) { ex.printStackTrace(); }
    }
    else 
      if(m_Instances==null)
	      throw new IllegalStateException("No instances supplied yet. Cannot update without"+
	                          "supplying a set of instances first.");
  }
  
  /**
   * Sets the distance function to use for nearest neighbour search.
   * Currently only EuclideanDistance is supported.
   * 
   * @param df 		the distance function to use 
   * @throws Exception 	if not EuclideanDistance
   */
  public void setDistanceFunction(DistanceFunction df) throws Exception {
    if (!(df instanceof EuclideanDistance))
      throw new Exception("CoverTree currently only works with "
	  + "EuclideanDistanceFunction.");
    m_DistanceFunction = m_EuclideanDistance = (EuclideanDistance) df;
  }
  
  /**
   * Returns the tip text for this property.
   * 
   * @return 		tip text for this property suitable for
   * 			displaying in the explorer/experimenter gui
   */
  public String baseTipText() {
    return "The base for the expansion constant.";
  }

  /**
   * Returns the base in use for expansion constant.
   * 
   * @return base 	currently in use.
   */
  public double getBase() {
    return m_Base;
  }
  
  /**
   * Sets the base to use for expansion constant.
   * The 2 in 2^i in the paper.
   * 
   * @param b 		the new base;
   */
  public void setBase(double b) {
    m_Base = b;
  }
  
  /**
   * Returns the size of the tree. 
   * (number of internal nodes + number of leaves)
   * 
   * @return 		the size of the tree
   */
  public double measureTreeSize() {
    return m_NumNodes;
  }
  
  /**
   * Returns the number of leaves.
   * 
   * @return 		the number of leaves
   */
  public double measureNumLeaves() {
    return m_NumLeaves;
  }
  
  /**
   * Returns the depth of the tree.
   * 
   * @return 		the number of rules
   */
  public double measureMaxDepth() {
    return m_MaxDepth;
  }
    
  /**
   * Returns an enumeration of the additional measure names.
   * 
   * @return 		an enumeration of the measure names
   */
  public Enumeration enumerateMeasures() {
    Vector newVector = new Vector();
    newVector.addElement("measureTreeSize");
    newVector.addElement("measureNumLeaves");
    newVector.addElement("measureMaxDepth");
    if(m_Stats!=null) {
      for(Enumeration e = m_Stats.enumerateMeasures(); e.hasMoreElements();) {
        newVector.addElement(e.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 (additionalMeasureName.compareToIgnoreCase("measureMaxDepth") == 0) {
      return measureMaxDepth();
    } else if (additionalMeasureName.compareToIgnoreCase("measureTreeSize") == 0) {
      return measureTreeSize();
    } else if (additionalMeasureName.compareToIgnoreCase("measureNumLeaves") == 0) {
      return measureNumLeaves();
    } else if(m_Stats!=null) {
      return m_Stats.getMeasure(additionalMeasureName);
    } else {
      throw new IllegalArgumentException(additionalMeasureName 
			  + " not supported (KDTree)");
    }
  }
  
  /********Utility print functions.****** */
  /**
   * Prints a string to stdout. 
   * 
   * @param s The string to print.
   */
  protected static void print(String s) {
    System.out.print(s);
  }

  /** 
   * Prints a string to stdout followed by 
   * newline.
   * 
   * @param s The string to print. 
   */
  protected static void println(String s) {
    System.out.println(s);
  }

  /** 
   * Prints an object to stdout.
   * 
   * @param o The object to print. 
   */
  protected static void print(Object o) {
    System.out.print(o);
  }

  /** 
   * Prints an object to stdout followed by 
   * newline.
   * 
   * @param o The object to print.  
   */
  protected static void println(Object o) {
    System.out.println(o);
  }

  /** 
   * Prints the specified number of spaces.
   * 
   * @param s The number of space characters to print.  
   */
  protected static void print_space(int s) {
    for (int i = 0; i < s; i++)
      System.out.print(" ");
  }

  /**
   * Prints a cover tree starting from the given node.
   * 
   * @param depth The depth of top_node.
   * @param top_node The node to start printing from. 
   */
  protected static void print(int depth, CoverTreeNode top_node) {
    print_space(depth);
    println(top_node.p());
    if (top_node.num_children > 0) {
      print_space(depth);
      print("scale = " + top_node.scale + "\n");
      print_space(depth);
      print("num children = " + top_node.num_children + "\n");
      Syste