middleoutconstructor.java

矩阵的QR分解算法

   * @param node The root TempNode
   * @param startidx The start of the portion of 
   * master index array the TempNodes 
   * are made from. 
   * @param endidx The end of the portion of 
   * master index array the TempNodes are 
   * made from. 
   * @param depth The depth in the tree where 
   * this root TempNode is made (needed when 
   * leaves of a tree deeper down are built 
   * middle out).
   * @return The root BallTreeNode.
   */
  protected BallNode makeBallTreeNodes(TempNode node, int startidx, 
      int endidx, int depth) {
    BallNode ball=null;
    
    if(node.left!=null && node.right!=null) { //make an internal node
      ball = new BallNode(
      startidx, endidx, m_NumNodes, 
      node.anchor,
      node.radius
      );
      m_NumNodes += 1;
      ball.m_Left = makeBallTreeNodes(node.left, startidx, startidx+node.left.points.length()-1, depth+1);
      ball.m_Right= makeBallTreeNodes(node.right, startidx+node.left.points.length(), endidx, depth+1);
      m_MaxDepth++;
    }
    else { //make a leaf node
      ball = new BallNode(startidx, endidx, m_NumNodes,       
      node.anchor, 
      node.radius 
                         );
      m_NumNodes += 1;      
      m_NumLeaves += 1;
    }
    return ball;
  }
    
  /**
   * Returns an anchor point which is furthest from the
   * mean point for a given set of points (instances) 
   * (The anchor instance is chosen from the given
   * set of points).
   * 
   * @param startIdx The start index of the points
   * for which anchor point is required.
   * @param endIdx The end index of the points for
   * which anchor point is required.
   * @return The furthest point/instance from the mean 
   * of given set of points.
   */
  protected TempNode getFurthestFromMeanAnchor(int startIdx, int endIdx) {
    TempNode anchor = new TempNode();
    Instance centroid = BallNode.calcCentroidPivot(startIdx, endIdx, m_InstList, 
                                                   m_Instances);
    Instance temp;
    double tmpr;
    anchor.radius = Double.NEGATIVE_INFINITY;
    for(int i=startIdx; i<=endIdx; i++) {
      temp = m_Instances.instance(m_InstList[i]);
      tmpr = m_DistanceFunction.distance(centroid, temp);
      if(tmpr > anchor.radius) {
        anchor.idx = m_InstList[i];
        anchor.anchor = temp;
        anchor.radius = tmpr;
      }
    }
    
    setPoints(anchor, startIdx, endIdx, m_InstList);
    return anchor;
  }
  
  /** 
   * Returns a random anchor point/instance from a 
   * given set of points/instances.
   * 
   * @param startIdx The start index of the points
   * for which anchor is required.
   * @param endIdx The end index of the points for
   * which anchor is required.
   * @return The random anchor point/instance
   * for the given set of 
   */
  protected TempNode getRandomAnchor(int startIdx, int endIdx) {
    TempNode anchr1 = new TempNode();
    anchr1.idx = m_InstList[startIdx+rand.nextInt((endIdx-startIdx+1))];
    anchr1.anchor = m_Instances.instance(anchr1.idx);
    setPoints(anchr1, startIdx, endIdx, m_InstList);
    anchr1.radius = ((ListNode)anchr1.points.getFirst()).distance;
    
    return anchr1;
  }
  
  /**
   * Sets the points of an anchor node. It takes the
   * indices of points from the given portion of 
   * an index array and stores those indices, together
   * with their distances to the given anchor node, 
   * in the point index list of the anchor node.
   *  
   * @param node The node in which the points are
   * needed to be set.
   * @param startIdx The start of the portion in 
   * the given index array (the master index
   * array).
   * @param endIdx The end of the portion in the
   * given index array. 
   * @param indices The index array.
   */
  public void setPoints(TempNode node, int startIdx, int endIdx, int[] indices) {
    node.points = new MyIdxList();    
    Instance temp; double dist;
    for(int i=startIdx; i<=endIdx; i++) {
      temp = m_Instances.instance(indices[i]);
      dist = m_DistanceFunction.distance(node.anchor, temp);
      node.points.insertReverseSorted(indices[i], dist);
    }
  }

  /**
   * Sets the distances of a supplied new
   * anchor to all the rest of the 
   * previous anchor points.
   * @param anchors The old anchor points.
   * @param newAnchor The new anchor point.
   * @param anchorDistances The vector to
   * store the distances of newAnchor to 
   * each of the old anchors.
   * @throws Exception If there is some 
   * problem in calculating the distances.
   */
  public void setInterAnchorDistances(Vector anchors, TempNode newAnchor,
                                      Vector anchorDistances) throws Exception {
    double[] distArray = new double[anchors.size()];
    
    for(int i=0; i<anchors.size(); i++) {
      Instance anchr = ((TempNode)anchors.elementAt(i)).anchor;
      distArray[i] = m_DistanceFunction.distance(anchr, newAnchor.anchor);
    }
    anchorDistances.add(distArray);
  }
  
  /**
   * Removes points from old anchors that
   * are nearer to the given new anchor and
   * adds them to the list of points of the
   * new anchor. 
   * @param newAnchor The new anchor.
   * @param anchors The old anchors.
   * @param anchorDistances The distances
   * of new anchor to each of the old 
   * anchors.
   */
  public void stealPoints(TempNode newAnchor, Vector anchors, 
                          Vector anchorDistances) {
                            
    int maxIdx = -1; 
    double maxDist = Double.NEGATIVE_INFINITY;
    double[] distArray = (double[])anchorDistances.lastElement();
    
    for(int i=0; i<distArray.length; i++)
      if(maxDist < distArray[i]) {
        maxDist = distArray[i]; maxIdx = i;
      }
    
    boolean pointsStolen=false;
    TempNode anchorI;
    double newDist, distI, interAnchMidDist;
    Instance newAnchInst = newAnchor.anchor, anchIInst;
    for(int i=0; i<anchors.size(); i++) {
      anchorI = (TempNode)anchors.elementAt(i);
      anchIInst = anchorI.anchor;
      
      pointsStolen = false;
      interAnchMidDist = m_DistanceFunction.distance(newAnchInst, anchIInst)/2D;
      for(int j=0; j<anchorI.points.length(); j++) {
        ListNode tmp = (ListNode) anchorI.points.get(j);
        //break if we reach a point whose distance is less than the midpoint
        //of inter anchor distance
        if(tmp.distance < interAnchMidDist)
          break;
        //else test if this point can be stolen by the new anchor
        newDist = m_DistanceFunction.distance(newAnchInst, 
                                              m_Instances.instance(tmp.idx));
        distI = tmp.distance;
        if(newDist < distI) {
          newAnchor.points.insertReverseSorted(tmp.idx, newDist);
          anchorI.points.remove(j);
          pointsStolen=true;
        }
      }
      if (pointsStolen)
        anchorI.radius = ((ListNode)anchorI.points.getFirst()).distance;
    }//end for
  }//end stealPoints()

  /**
  /**
   * Calculates the centroid pivot of a node based on its
   * two child nodes (if merging two nodes).
   * @param node1 The first child.
   * @param node2 The second child.
   * @param insts The set of instances on which the tree 
   * is being built (as dataset header information is 
   * required). 
   * @return The centroid pivot of a node. 
   */
  public Instance calcPivot(TempNode node1, TempNode node2, Instances insts) {
    int classIdx = m_Instances.classIndex();
    double[] attrVals = new double[insts.numAttributes()];
    Instance temp;
    double anchr1Ratio = (double)node1.points.length() / 
                         (node1.points.length()+node2.points.length()),
           anchr2Ratio = (double)node2.points.length() / 
                         (node1.points.length()+node2.points.length());                         ;
    for(int k=0; k<node1.anchor.numValues(); k++) {
      if(node1.anchor.index(k)==classIdx)
        continue;
      attrVals[k] += node1.anchor.valueSparse(k)*anchr1Ratio;
    }
    for(int k=0; k<node2.anchor.numValues(); k++) {
      if(node2.anchor.index(k)==classIdx)
        continue;
      attrVals[k] += node2.anchor.valueSparse(k)*anchr2Ratio;
    }
    temp = new Instance(1.0, attrVals);
    return temp;
  }
  
  /**
   * Calculates the centroid pivot of a node based on 
   * the list of points that it  contains (tbe two 
   * lists of its children are provided).
   * @param list1 The point index list of first child.
   * @param list2 The point index list of second 
   * child.
   * @param insts The insts object on which the tree 
   * is being built (for header information). 
   * @return The centroid pivot of the node. 
   */
  public Instance calcPivot(MyIdxList list1, MyIdxList list2, Instances insts) {
    int classIdx = m_Instances.classIndex();
    double[] attrVals = new double[insts.numAttributes()];
    
    Instance temp;
    for(int i=0; i<list1.length(); i++) {
      temp = insts.instance(((ListNode)list1.get(i)).idx);
      for(int k=0; k<temp.numValues(); k++) {
        if(temp.index(k)==classIdx)
          continue;
        attrVals[k] += temp.valueSparse(k);
      }
    }
    for(int j=0; j<list2.length(); j++) {
      temp = insts.instance(((ListNode)list2.get(j)).idx);
      for(int k=0; k<temp.numValues(); k++) {
        if(temp.index(k)==classIdx)
          continue;
        attrVals[k] += temp.valueSparse(k);
      }
    }
    for(int j=0, numInsts=list1.length()+list2.length(); 
        j < attrVals.length; j++) {
      attrVals[j] /= numInsts;
    }
    temp = new Instance(1.0, attrVals);
    return temp;
  }
  
  /** 
   * Calculates the radius of a node based on its two 
   * child nodes (if merging two nodes).
   * @param n1 The first child of the node.
   * @param n2 The second child of the node.
   * @return The radius of the node. 
   * @throws Exception
   */
  public double calcRadius(TempNode n1, TempNode n2) {
	  Instance p1 = n1.anchor, p2 = n2.anchor;
	  double radius = n1.radius + m_DistanceFunction.distance(p1, p2) + n2.radius;
	  return radius/2;
  }
  
  /**
   * Calculates the radius of a node based on the
   * list of points that it contains (the two lists of 
   * its children are provided). 
   * @param list1 The point index list of first child.
   * @param list2 The point index list of second child.
   * @param pivot The centre/pivot of the node.
   * @param insts The instances on which the tree is 
   * being built (for header info). 
   * @return The radius of the node. 
   */
  public double calcRadius(MyIdxList list1, MyIdxList list2, 
                           Instance pivot, Instances insts) {
    double radius = Double.NEGATIVE_INFINITY;
    
    for(int i=0; i<list1.length(); i++) {
      double dist = m_DistanceFunction.distance(pivot, 
                                              insts.instance(((ListNode)list1.get(i)).idx));
      if(dist>radius)
        radius = dist;
    }
    for(int j=0; j<list2.length(); j++) {
      double dist = m_DistanceFunction.distance(pivot, 
                                              insts.instance(((ListNode)list2.get(j)).idx));
      if(dist>radius)
        radius = dist;
    }
    return radius;
  }
  
  /**
   * Adds an instance to the tree. This implementation of 
   * MiddleOutConstructor doesn't support addition of 
   * instances to already built tree, hence it always
   * throws an exception.
   * @param node The root of the tree to which the 
   * instance is to be added.
   * @param inst The instance to add to the tree.
   * @return The updated master index array after 
   * adding the instance.
   * @throws Exception Always as this implementation of
   * MiddleOutConstructor doesn't support addition of
   * instances after batch construction of the tree.
   */
  public int[] addInstance(BallNode node, Instance inst) throws Exception {
    throw new Exception("Addition of instances after the tree is built, not " +
                        "possible with MiddleOutConstructor.");
  }  
  
  /**
   * Sets the maximum number of instances allowed in a leaf.
   * @param num The maximum number of instances allowed in 
   * a leaf.
   * @throws Exception If the num is < 2, as the method 
   * cannot work for < 2 instances. 
   */ 
  public void setMaxInstancesInLeaf(int num) throws Exception {
    if(num<2)
      throw new Exception("The maximum number of instances in a leaf for " +
                          "using MiddleOutConstructor must be >=2.");
    super.setMaxInstancesInLeaf(num);
  }  
  
  /**
   * Returns the tip text for this property.
   * 
   * @return 		tip text for this property suitable for
   * 			displaying in the explorer/experimenter gui
   */
  public String initialAnchorRandomTipText() {
    return "Whether the initial anchor is chosen randomly.";
  }
  
  /** 
   * Gets whether if the initial anchor is chosen randomly.
   * @return true if the initial anchor is a random one. 
   */
  public boolean isInitialAnchorRandom() {
    return m_RandomInitialAnchor;
  }
  
  /** 
   * Sets whether if the initial anchor is chosen randomly. If not 
   * then if it is the furthest point from the mean/centroid.
   * @param randomInitialAnchor Should be true if the first 
   * anchor is to be chosen randomly.
   */
  public void setInitialAnchorRandom(boolean randomInitialAnchor) {
    m_RandomInitialAnchor = randomInitialAnchor;
  }
  
  /**
   * Returns the tip text for this property.
   * 
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String seedTipText() {
    return "The seed value for the random number generator.";
  }

  /**
   * Returns the seed for random number generator.
   * @return The random number seed.