covertree.java

矩阵的QR分解算法

    
    /** the kth nearest ones. */
    MyHeapElement m_KthNearest[] = null;
    
    /** The number of kth nearest elements. */
    int m_KthNearestSize = 0;
    
    /** the initial size of the heap. */
    int initSize=10;
    
    /**
     * returns the number of k nearest.
     * 
     * @return the number of k nearest
     * @see     #m_KthNearestSize
     */
    public int noOfKthNearest() {
      return m_KthNearestSize;
    }
    
    /**
     * Stores kth nearest elements (if there are 
     * more than one).
     * @param d the distance 
     */
    public void putKthNearest(double d) {
      if(m_KthNearest==null) {
        m_KthNearest = new MyHeapElement[initSize];
      }
      if(m_KthNearestSize>=m_KthNearest.length) {
        initSize += initSize;
        MyHeapElement temp[] = new MyHeapElement[initSize];
        System.arraycopy(m_KthNearest, 0, temp, 0, m_KthNearest.length);
        m_KthNearest = temp;
      }
      m_KthNearest[m_KthNearestSize++] = new MyHeapElement(d);
    }
    
    /**
     * returns the kth nearest element or null if none there.
     * 
     * @return      the kth nearest element
     */
    public MyHeapElement getKthNearest() {
      if(m_KthNearestSize==0)
        return null;
      m_KthNearestSize--;
      return m_KthNearest[m_KthNearestSize];
    }
    
    /** 
     * performs upheap operation for the heap 
     * to maintian its properties. 
     */
    protected void upheap() {
      int i = m_heap[0].index;
      MyHeapElement temp;
      while( i > 1  && m_heap[i].distance>m_heap[i/2].distance) {
        temp = m_heap[i];
        m_heap[i] = m_heap[i/2];
        i = i/2;
        m_heap[i] = temp; //this is i/2 done here to avoid another division.
      }
    }
    
    /** 
     * performs downheap operation for the heap 
     * to maintian its properties. 
     */
    protected void downheap() {
      int i = 1;
      MyHeapElement temp;
      while( ( (2*i) <= m_heap[0].index &&
      m_heap[i].distance < m_heap[2*i].distance )
      ||
      ( (2*i+1) <= m_heap[0].index &&
      m_heap[i].distance < m_heap[2*i+1].distance) ) {
        if((2*i+1)<=m_heap[0].index) {
          if(m_heap[2*i].distance>m_heap[2*i+1].distance) {
            temp = m_heap[i];
            m_heap[i] = m_heap[2*i];
            i = 2*i;
            m_heap[i] = temp;
          }
          else {
            temp = m_heap[i];
            m_heap[i] = m_heap[2*i+1];
            i = 2*i+1;
            m_heap[i] = temp;
          }
        }
        else {
          temp = m_heap[i];
          m_heap[i] = m_heap[2*i];
          i = 2*i;
          m_heap[i] = temp;
        }
      }
    }
    
    /**
     * returns the total size.
     * 
     * @return      the total size
     */
    public int totalSize() {
      return size()+noOfKthNearest();
    }
  }
  
  /**
   * A class for storing data about a neighboring instance.
   * 
   * @author Ashraf M. Kibriya (amk14[at-the-rate]cs[dot]waikato[dot]ac[dot]nz)
   * @version $Revision: 1.3 $
   */
  protected class MyHeapElement {
    
    /** the distance. */
    public double distance;
    
    /** 
     * The index of this element. Also used as 
     * the size of the heap in the first element.
     */
    int index = 0;
    
    /**
     * constructor.
     * 
     * @param d   the distance
     */
    public MyHeapElement(double d) {
      distance = d;
    }
  }
  
  /**
   * stores a CoverTreeNode and its distance to the current query node.
   * 
   * @author Ashraf M. Kibriya (amk14[at-the-rate]cs[dot]waikato[dot]ac[dot]nz)
   * @version $Revision: 1.3 $
   */
  private class d_node {
    
    /** The distance of the node's point to the query point. */
    double dist;
    
    /** The node. */
    CoverTreeNode n;
    
    /** 
     * Constructor.
     * @param d The distance of the node to the query.
     * @param node The node. 
     */
    public d_node(double d, CoverTreeNode node) {
      dist = d;
      n = node;
    }
  };

  /** 
   * Initializes a heap with k values of the the given upper_bound.
   * 
   * @param heap The heap to put values into.
   * @param upper_bound The value to put into heap (the value with 
   * which it should be initialized).
   * @param k The number of times upper_bound should be put into
   * heap for initialization.
   * @throws Exception If there is some problem in initializing 
   * the heap (if k &gt; size of the heap).
   */
  protected void setter(MyHeap heap, double upper_bound, final int k) throws Exception {
    if(heap.size()>0)
      heap.m_heap[0].index=0;

    while(heap.size() < k) {
      heap.put(upper_bound);
    }
  }

  /** 
   * Replaces the current top/max value in the heap with the new one.
   * The new max value should be &lt;= the old one.
   * 
   * @param upper_bound The heap.
   * @param new_bound The new value that should replace the old top one.
   * @throws Exception if the new value is greater than the old value.
   */
  protected void update(MyHeap upper_bound, double new_bound) throws Exception {
    upper_bound.putBySubstitute(new_bound);
  }
  
  /**
   * Returns a cover set for a given level/scale.
   * A cover set for a level consists of nodes whose 
   * Instances/centres are which are inside the query
   * ball at that level. If no cover set exists for the
   * given level (if it is the first time it is going 
   * to be used), than a new one is created.  
   * 
   * @param idx The level/scale for which the cover set 
   * is required.
   * @param cover_sets The covers sets. Consists of stack 
   * of a stack of d_node objects. 
   * @return The cover set for the given level/scale.
   */
  protected Stack<d_node> getCoverSet(int idx, Stack<Stack<d_node>> cover_sets) {
    if (cover_sets.length <= idx) {
      int i = cover_sets.length - 1;
      while (i < idx) {
        i++;
        Stack<d_node> new_cover_set = new Stack<d_node>();
        cover_sets.push(new_cover_set);
      }
    }
    return cover_sets.element(idx);
  }
  
  /**
   * Copies the contents of one zero set to the other. This
   * is required if we are going to inspect child of some query node 
   * (if the queries are given in batch in the form of a cover tree).
   * Only those nodes are copied to the new zero set that are inside
   * the query ball of query_chi.
   * P.S.: A zero set is a set of all leaf nodes that are found
   * to be inside the query ball.  
   *   
   * @param query_chi The child node of our query node that we are 
   * going to inspect. 
   * @param new_upper_k New heap that will store the distances of the
   * k NNs for query_chi.
   * @param zero_set The zero set of query_chi's parent that needs
   * to be copied.
   * @param new_zero_set The new zero set of query_chi where old zero
   * sets need to be copied into.
   * @throws Exception If there is some problem.
   */
  protected void copy_zero_set(CoverTreeNode query_chi, MyHeap new_upper_k, 
      			Stack<d_node> zero_set, Stack<d_node> new_zero_set) throws Exception {
    new_zero_set.clear();
    d_node ele;
    for (int i = 0; i < zero_set.length; i++) {
      ele = zero_set.element(i);
      double upper_dist = new_upper_k.peek().distance + query_chi.max_dist;
      if (shell(ele.dist, query_chi.parent_dist, upper_dist)) {
        double d = Math.sqrt(m_DistanceFunction.distance(query_chi.p(), ele.n
            .p(), upper_dist * upper_dist));
        if (m_TreeStats != null)
          m_TreeStats.incrPointCount();
        if (d <= upper_dist) {
          if (d < new_upper_k.peek().distance)
            update(new_upper_k, d);
          d_node temp = new d_node(d, ele.n);
          new_zero_set.push(temp);
          if (m_TreeStats != null)
            m_TreeStats.incrLeafCount();
        }//end if(d<newupperbound)
      }//end if(shell(...
    }//end for
  }
  

  /**
   * Copies the contents of one set of cover sets to the other. It
   * is required if we are going to inspect child of some query node 
   * (if the queries are given in batch in the form of a cover tree).
   * For each level, only those nodes are copied to the new set 
   * which are inside the query ball of query_chi at that level.
   * 
   * @param query_chi The child node of our query node that we are 
   * going to inspect. 
   * @param new_upper_k New heap that will store the distances of the
   * k NNs for query_chi.
   * @param cover_sets The cover_sets of query_chi's parent, which
   * need to be copied to new_cover_sets.
   * @param new_cover_sets The new set of cover_sets that need to
   * contain contents of cover_sets. 
   * @param current_scale The scale/level we are inspecting in our 
   * cover tree.
   * @param max_scale The maximum level so far possible in our 
   * search (this is only updated as we descend and a deeper
   * child is found inside the query ball).   
   * @throws Exception If there is problem.
   */
  protected void copy_cover_sets(CoverTreeNode query_chi, MyHeap new_upper_k,
      		Stack<Stack<d_node>> cover_sets,
      		Stack<Stack<d_node>> new_cover_sets,
      		int current_scale, int max_scale) throws Exception {
    new_cover_sets.clear();
    for (; current_scale <= max_scale; current_scale++) {
      d_node ele;
      Stack<d_node> cover_set_currentscale = getCoverSet(current_scale,
          cover_sets);
      for (int i = 0; i < cover_set_currentscale.length; i++) { // ; ele != end;
                                                                // ele++) {
        ele = cover_set_currentscale.element(i);
        double upper_dist = new_upper_k.peek().distance + query_chi.max_dist
            + ele.n.max_dist;
        if (shell(ele.dist, query_chi.parent_dist, upper_dist)) {
          double d = Math.sqrt(m_DistanceFunction.distance(query_chi.p(), ele.n
              .p(), upper_dist * upper_dist));
          if (m_TreeStats != null)
            m_TreeStats.incrPointCount();
          if (d <= upper_dist) {
            if (d < new_upper_k.peek().distance)
              update(new_upper_k, d);
            d_node temp = new d_node(d, ele.n);
            new_cover_sets.element(current_scale).push(temp);
            if (m_TreeStats != null)
              m_TreeStats.incrIntNodeCount();
          }// end if(d<=..
        }// end if(shell(...
      }// end for(coverset_i)
    }// end for(scales)
  }
  

  /**
   * Prints the given cover sets and zero set.
   * 
   * @param cover_sets The cover sets to print.
   * @param zero_set The zero set to print.  
   * @param current_scale The scale/level to start printing
   * the cover sets from. 
   * @param max_scale The max scale/level to print the cover
   * sets upto. 
   */
  void print_cover_sets(Stack<Stack<d_node>> cover_sets,
      Stack<d_node> zero_set, int current_scale, int max_scale) {
    d_node ele;
    println("cover set = ");
    for (; current_scale <= max_scale; current_scale++) {
      println("" + current_scale);
      for (int i = 0; i < cover_sets.element(current_scale).length; i++) {
        ele = cover_sets.element(current_scale).element(i);
        CoverTreeNode n = ele.n;
        println(n.p());
      }
    }
    println("infinity");
    for (int i = 0; i < zero_set.length; i++) {
      ele = zero_set.element(i);
      CoverTreeNode n = ele.n;
      println(n.p());
    }
  }
  
  
  /**
   * Swap two nodes in a cover set.
   * 
   * @param a The index first node.
   * @param b The index of second node.
   * @param cover_set The cover set in which the two nodes are.
   */

  protected void SWAP(int a, int b, Stack<d_node>cover_set) {				
    d_node tmp = cover_set.element(a);
    cover_set.set(a, cover_set.element(b));
    cover_set.set(b, tmp);
  }
  
  
  
  /**
   * Returns the difference of two given nodes distance to 
   * the query. It is used in half-sorting a cover set. 
   *   
   * @param p1 The index of first node.
   * @param p2 The index of second node.
   * @param cover_set The cover set containing the two given
   * nodes.
   * @return dist_to_query_of_p1 - dist_to_query_of_p2
   */