kdtree.java

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

    
    m_DistanceFunction.checkInstances();
  }


  /**
   * Adds one instance to the KDTree.
   * @param instance the instance to be added 
  */
  public void updateKDTree(Instance instance) 
  throws Exception {

    boolean success = m_Root.addInstance(instance);
    if (!success) {
      // make a new tree
      double [][] dummyRanges = null; 
      buildKDTree(m_Instances, dummyRanges);
    }
  }

  /**
   * Deletes one instance in the KDTree.
   * @param instance the instance to be deleted
   */
  public void deleteInstance(Instance instance) 
  throws Exception {
    int index =0;
    //    for (int 
    deleteInstance(index);
  }

  /**
   * Deletes one instance in the KDTree.
   * @param index the index of the instance to be deleted
   * @return true if instance was deleted
   */
  public boolean deleteInstance(int index) throws Exception {
    
    boolean success = false;
    int pos = m_InstList.deleteOneIndex(index);
    if (pos >= 0) {
      m_Root.tidyUpAfterDelete(pos);
      success =  true;
    } 
    if (!success) {
      // make a new tree
      double [][] dummyRanges = null; 
      buildKDTree(m_Instances, dummyRanges);
    }
    return success;
  }

  /**
   * toString  
   * @return string representing the tree
   */
  public String toString() {
    StringBuffer text = new StringBuffer();
    KDTreeNode tree = m_Root;
    int[] num = new int[1];
    num[0] = 0;
    // index list in string format:
    //for (int i = 0; i <= m_InstList.length(); i++) {
    //  int instIndex = m_InstList.get(i);
    //  text.append(instIndex + "/ ");
    //} 

    text.append("\nKDTree build:");
    text.append(tree.statToString(true, true));
    // tree in string format:
    text.append(tree.nodeToString(true));
    return text.toString();
  }  

  /**
   * Assigns instances to centers using KDTree. 
   * 
   * @param centers the current centers
   * @param assignments the centerindex for each instance
   * @param pc the threshold value for pruning.
   * @param p True if pruning should be used.
   */
  public void centerInstances(Instances centers, int [] assignments,
				double pc) throws Exception {
    
    int [] centList = new int[centers.numInstances()];
    for (int i = 0; i < centers.numInstances(); i++)
      centList[i] = i;

    m_Root.determineAssignments(centers, centList, 
			 assignments, pc, m_Prune);
  }
  
  /**
   * Used for debug println's.
   * @param output string that is printed
   */
  private void OOPS(String output) {
    System.out.println(output);
  }

  /**
   * Normalizes a given value of a numeric attribute.
   *
   * @param x the value to be normalized
   * @param i the attribute's index
   * @param r the ranges for each attribute
   */
  private double norm(double x, int i, double[][] r) {

    if (Double.isNaN(r[i][0]) || (r[i][1]) == 0) {
      return 0;
    } else {
      return (x - r[i][0]) / (r[i][1]);
    }
  }

  /**
   * Returns array of boolean set true or false if instance is part
   * of next left kdtree.
   * @param left list of boolean values, true if instance belongs to left
   * @param instList list of indexes of instances of this node
   * @param splitDim index of splitting attribute
   * @param splitValue value at which the node is split
   * @return number of instances that belong to the left
   */
  private int checkSplitInstances(boolean [] left,
				  int [] instList,
				  int splitDim, double splitValue) {

    // length of left should be same as length of instList
    int numLeft = 0;
    for (int i = 0; i < instList.length; i++) {
      // value <= splitValue
      if (m_DistanceFunction.valueIsSmallerEqual(
	     m_Instances.instance(instList[i]), 
	     splitDim,
             splitValue)) {
	left[i] = true;
        numLeft++;
      } else {
	left[i] = false;
      }
    }
    return numLeft;
  }

  /**
   * Sorts instances newly into left and right part.
   * @param left list of flags, set true by this method if instance
   * should go to the left follow node
   * @param instList list of instances of this node
   * @param iLeft index to the left 
   * @param iLeft index to the left 
   */
  private void splitInstances(boolean [] left,
			      int [] instList, 
			      int iLeft,
			      int iRight) {

    for (int i = 0; i < instList.length; i++) {
      if (left[i]) {
	m_InstList.set(iLeft++, instList[i]);
      } else {
	m_InstList.set(iRight++, instList[i]);
      }
    }
  }


  /** -------------------------------------------------------------------------------- 
   ** variables for nearest neighbour search 
   *  --------------------------------------------------------------------------------*/

  /** index/indices of current target */
  private int [] m_NearestList;

  /** length of nearest list (can be larger than k) */
  private int m_NearestListLength = 0;

  /** true if more than of k nearest neighbours */
  private boolean m_MultipleFurthest = false;

  /** number of nearest neighbours k */
  private int m_kNN = 0; 

  /** distance to current nearest neighbour */
  private double m_MinDist = Double.MAX_VALUE;

  /** distance to current furthest of the neighbours */
  private double m_MaxMinDist = Double.MAX_VALUE;

  /** index of the furthest of the neighbours in m_NearestList */
  private int m_FurthestNear = 0;

  /** distance to current nearest neighbour */
  private double [] m_DistanceList;

  /**
   * Find k nearest neighbours to target. This is the main method.
   *
   * @param target the instance to find nearest neighbour for
   * @param maxDist the distance to the nearest neighbor so far
   * @param nearest the index of the nearest neighbor (second return value)
   */
  public int findKNearestNeighbour(Instance target,
                                   int kNN,
                                   int [] nearestList,
                                   double [] distanceList) 
    throws Exception {
    m_kNN = kNN;
    double maxDist = Double.MAX_VALUE;
    m_NearestList = nearestList;
    m_DistanceList = distanceList;
    m_NearestListLength = 0;
    int[] num = new int[1]; 
    num[0] = 0;
    double minDist = m_Root.kNearestNeighbour(target, maxDist);
    return m_NearestListLength;
  }

  /**
   * Get the distance of the furthest of the nearest neighbour 
   * the index of this instance 
   * in the index list.
   * @param nearest index of k nearest instances
   */
  private int checkFurthestNear() {
    double max = 0.0;
    int furthestNear = 0;
    for (int i = 0; i < m_kNN; i++) {
      if (m_DistanceList[i] > max) {
	max = m_DistanceList[i];
	furthestNear = i;
      } 
    }
    return furthestNear;
  }

  /**
   * the GET and SET - functions ===============================================
   **/

  /**
   * Sets KDTree to be valid for dataset in m_Instances.
   * @param flag if KDtree is valid 
   */
  public void setValid(boolean valid) {
    m_Valid = valid;
  }

  /**
   * Returns true if valid flag is true.
   * @return flag if KDtree is valid 
   */
  public boolean isValid() {
    return m_Valid;
  }

  /**
   * Gets number of instances in KDTree.
   * @return number of instances
   */
  public int numInstances() {
    return m_Instances.numInstances();
  }

  /**
   * Gets instances used in the tree.
   * @return model information
   */
  public Instances getInstances() {
    return m_Instances;
  }

  /**
   * Gets instance list  used in the tree.
   * @return instance list
   */
  public DynamicArrayOfPosInt getInstList() {
    return m_InstList;
  }


  /**
   * Gets the distance function specification string, 
   * which contains the class name of distance function
   * the filter and any options to the filter
   *
   * @return the filter string.
   */
  protected String getDistanceFunctionSpec() {
    
    DistanceFunction c = getDistanceFunction();
    if (c instanceof OptionHandler) {
      return c.getClass().getName() + " "
	+ Utils.joinOptions(((OptionHandler)c).getOptions());
    }
    return c.getClass().getName();
  }

  /**
   * Sets the distance function.
   * @param distanceF the distance function with all options set
   */
  public void setDistanceFunction(DistanceFunction distanceF) {
    m_DistanceFunction = distanceF;
  }

  /**
   * Gets the distance function.
   * @return the distance function
   */
  public DistanceFunction getDistanceFunction() {
    return m_DistanceFunction;
  }

  /**
   * Sets the minimum relative box width.
   * @param i the minimum relative box width
   */
  public void setMinBoxRelWidth(double i) throws Exception {
    m_MinBoxRelWidth = i;
  }

  /**
   * Gets the minimum relative box width.
   * @return the minimum relative box width
   */
  public double getMinBoxRelWidth() {
    return  m_MinBoxRelWidth;
  }

  /**
   * Sets the maximum number of instances in a leaf.
   * @param i the maximum number of instances in a leaf
   */
  public void setMaxInstInLeaf(int i) throws Exception {
    m_MaxInstInLeaf = i;
  }

  /**
   * Get the maximum number of instances in a leaf.
   * @return the maximum number of instances in a leaf
   */
  public int getMaxInstInLeaf() {
    return  m_MaxInstInLeaf;
  }

  /**
   * Sets the flag for pruning of the blacklisting algorithm.
   * @param p true to use pruning.
   */
  public void setPrune(boolean p) {
      m_Prune = p;
  }

  /**
   * Gets the pruning flag.
   * @return True if pruning
   */
  public boolean getPrune() {
    return m_Prune;
  }

  /**
   * Sets the flag for normalizing the widths of a KDTree Node by the width
   * of the dimension in the universe. 
   * @param n true to use normalizing.
   */
  public void setNormalize(boolean n) {
      m_Normalize = n;
  }

  /**
   * Gets the normalize flag.
   * @return True if normalizing
   */
  public boolean getNormalize() {
    return m_Normalize;
  }

  /**
   * Sets the debug level.
   * debug level = 0, means no output
   * @param d debuglevel
   */
  public void setDebugLevel(int d) {
    m_DebugLevel = d;
  }

  /**
   * Gets the debug level.
   * @return debug level
   */
  public int getDebugLevel() {
    return m_DebugLevel;
  }

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

    Vector newVector = new Vector(5);
    newVector.addElement(new Option(
				    "\tPruning will be done\n"
				    +"\t(Use this to prune).",
				    "P", 0,"-P"));
    newVector.addElement(new Option(
				    "\tSet minimal width of a box\n"
				    +"\t(default = 1.0E-2).",
				    "W", 0,"-W <value>"));
    newVector.addElement(new Option(
				    "\tMaximal number of instances in a leaf\n"
				    +"\t(default = 40).",
				    "L", 0,"-L"));
    newVector.addElement(new Option(
				    "\tDistance function\n"
				    +"\t(default = Euclidean Distance).",
				    "D", 0,"-D"));
    newVector.addElement(new Option(
				    "\tNormalizing will be done\n"
				    +"\t(Select dimension for split, with normalising to universe).",
				    "N", 0,"-N"));
     return newVector.elements();
  }

  /**
   * Parses a given list of options.
   * @param options the list of options as an array of strings
   * @exception Exception if an option is not supported
   *
   **/
  public void setOptions(String[] options)
    throws Exception {

    if (Utils.getFlag('P', options)) {
      setPrune(true);
    } else {
      setPrune(false);
    }

    String optionString = Utils.getOption('W', options);
    if (optionString.length() != 0) {
      setMinBoxRelWidth(Double.parseDouble(optionString));
    }

    optionString = Utils.getOption('L', options);
    if (optionString.length() != 0) {
      setMaxInstInLeaf(Integer.parseInt(optionString));
    }

    String funcString = Utils.getOption('D', options);
    if (funcString.length() != 0) {
      String [] funcSpec = Utils.splitOptions(funcString);
      String funcName = funcSpec[0];
      funcSpec[0] = "";
      setDistanceFunction((DistanceFunction) Utils.forName(DistanceFunction.class,
							   funcName, funcSpec));
    }

    if (Utils.getFlag('N', options)) {
      setNormalize(true);
    } else {
      setNormalize(false);
    }

    optionString = Utils.getOption('U', options);
    int debugLevel = 0;
    if (optionString.length() != 0) {
      try {
	debugLevel = Integer.parseInt(optionString);
      } catch (NumberFormatException e) {
	throw new Exception(optionString +
                            "is an illegal value for option U"); 
      }
    }
    setDebugLevel(debugLevel);
  }

  /**
   * Gets the current settings of KDtree.
   * @return an array of strings suitable for passing to setOptions
   */
  public String[] getOptions() {
    String[] options = new String[10];
    int current = 0;
    
    if (getPrune()) {
      options[current++] = "-P";
    }
    options[current++] = "-W";
    options[current++] = "" + getMinBoxRelWidth();
    options[current++] = "-L";
    options[current++] = "" + getMaxInstInLeaf();
    options[current++] = "-D";
    options[current++] = "" + getDistanceFunctionSpec();
    if (getNormalize()) {
      options[current++] = "-N";
    }
    int dL = getDebugLevel();
    if (dL > 0) {
      options[current++] = "-U";
      options[current++] = "" + dL;
    }
    while (current < options.length) {
      options[current++] = "";
    }
    return  options;
  }

  /**
   * Main method for testing this class
   */
  public static void main(String [] args) {
    try {
      if (args.length < 1 ) {
	System.err.println("Usage : weka.gui.visualize.VisualizePanel "
			   +"<dataset> [<dataset> <dataset>...]");
	System.exit(1);
      }
    }catch (Exception ex) {
      ex.printStackTrace();
      System.err.println(ex.getMessage());
    }
  }
}