citationknn.java

用于快速分类

  /**
   * Turn the references and citers list into a probability distribution
   *
   * @return the probability distribution
   * @throws Exception if computation of distribution fails
   */
  protected double[] makeDistribution() throws Exception {
    
    double total = 0;
    double[] distribution = new double[m_TrainBags.numClasses()];
    boolean debug = false;

    total = (double)m_TrainBags.numClasses() / Math.max(1, m_TrainBags.numInstances());

    for(int i = 0; i < m_TrainBags.numClasses(); i++){
      distribution[i] = 1.0 / Math.max(1, m_TrainBags.numInstances());
      if(debug) System.out.println("distribution[" + i + "]: " + distribution[i]);
    }

    if(debug)System.out.println("total: " + total);

    for(int i = 0; i < m_TrainBags.numClasses(); i++){
      distribution[i] += m_References[i];
      distribution[i] += m_Citers[i];
    }

    total = 0;
    //total
    for(int i = 0; i < m_TrainBags.numClasses(); i++){
      total += distribution[i];
      if(debug)System.out.println("distribution[" + i + "]: " + distribution[i]);
    }

    for(int i = 0; i < m_TrainBags.numClasses(); i++){
      distribution[i] = distribution[i] / total;
      if(debug)System.out.println("distribution[" + i + "]: " + distribution[i]);

    }

    return distribution;
  }

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

    result.addElement(new Option(
          "\tNumber of Nearest References (default 1)",
          "R", 0, "-R <number of references>"));
    
    result.addElement(new Option(
          "\tNumber of Nearest Citers (default 1)",
          "C", 0, "-C <number of citers>"));
    
    result.addElement(new Option(
          "\tRank of the Hausdorff Distance (default 1)",
          "H", 0, "-H <rank>"));

    return result.elements();
  }

  /**
   * Sets the OptionHandler's options using the given list. All options
   * will be set (or reset) during this call (i.e. incremental setting
   * of options is not possible). <p/>
   *
   <!-- options-start -->
   * Valid options are: <p/>
   * 
   * <pre> -R &lt;number of references&gt;
   *  Number of Nearest References (default 1)</pre>
   * 
   * <pre> -C &lt;number of citers&gt;
   *  Number of Nearest Citers (default 1)</pre>
   * 
   * <pre> -H &lt;rank&gt;
   *  Rank of the Hausdorff Distance (default 1)</pre>
   * 
   <!-- 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{
    setDebug(Utils.getFlag('D', options));

    String option = Utils.getOption('R', options);
    if(option.length() != 0)
      setNumReferences(Integer.parseInt(option));
    else
      setNumReferences(1);

    option = Utils.getOption('C', options);
    if(option.length() != 0)
      setNumCiters(Integer.parseInt(option));
    else
      setNumCiters(1);

    option = Utils.getOption('H', options);
    if(option.length() != 0)
      setHDRank(Integer.parseInt(option));
    else
      setHDRank(1);
  }
  /**
   * Gets the current option settings for the OptionHandler.
   *
   * @return the list of current option settings as an array of strings
   */
  public String[] getOptions() {
    Vector        result;
    
    result = new Vector();

    if (getDebug())
      result.add("-D");
    
    result.add("-R");
    result.add("" + getNumReferences());
    
    result.add("-C");
    result.add("" + getNumCiters());
    
    result.add("-H");
    result.add("" + getHDRank());

    return (String[]) result.toArray(new String[result.size()]);
  }

  /**
   * Main method for testing this class.
   *
   * @param argv should contain the command line arguments to the
   * scheme (see Evaluation)
   */
  public static void main(String[] argv) {
    runClassifier(new CitationKNN(), argv);
  }

  //########################################################################
  //########################################################################
  //########################################################################
  //########################################################################
  //########################################################################

  /**
   * A class for storing data about a neighboring instance
   */
  private class NeighborNode 
    implements Serializable {

    /** for serialization */
    static final long serialVersionUID = -3947320761906511289L;
    
    /** The neighbor bag */
    private Instance mBag;

    /** The distance from the current instance to this neighbor */
    private double mDistance;

    /** A link to the next neighbor instance */
    private NeighborNode mNext;

    /** the position in the bag */
    private int mBagPosition;    
    
    /**
     * Create a new neighbor node.
     *
     * @param distance the distance to the neighbor
     * @param bag the bag instance
     * @param position the position in the bag
     * @param next the next neighbor node
     */
    public NeighborNode(double distance, Instance bag, int position, NeighborNode next){
      mDistance = distance;
      mBag = bag;
      mNext = next;
      mBagPosition = position;
    }

    /**
     * Create a new neighbor node that doesn't link to any other nodes.
     *
     * @param distance the distance to the neighbor
     * @param bag the neighbor instance
     * @param position the position in the bag
     */
    public NeighborNode(double distance, Instance bag, int position) {
      this(distance, bag, position, null);
    }
  }
  
  //##################################################
  /**
   * A class for a linked list to store the nearest k neighbours
   * to an instance. We use a list so that we can take care of
   * cases where multiple neighbours are the same distance away.
   * i.e. the minimum length of the list is k.
   */
  private class NeighborList 
    implements Serializable {
    
    /** for serialization */
    static final long serialVersionUID = 3432555644456217394L;
    
    /** The first node in the list */
    private NeighborNode mFirst;
    /** The last node in the list */
    private NeighborNode mLast;

    /** The number of nodes to attempt to maintain in the list */
    private int mLength = 1;

    /**
     * Creates the neighborlist with a desired length
     *
     * @param length the length of list to attempt to maintain
     */
    public NeighborList(int length) {
      mLength = length;
    }
    /**
     * Gets whether the list is empty.
     *
     * @return true if so
     */
    public boolean isEmpty() {
      return (mFirst == null);
    }
    /**
     * Gets the current length of the list.
     *
     * @return the current length of the list
     */
    public int currentLength() {

      int i = 0;
      NeighborNode current = mFirst;
      while (current != null) {
        i++;
        current = current.mNext;
      }
      return i;
    }

    /**
     * Inserts an instance neighbor into the list, maintaining the list
     * sorted by distance.
     *
     * @param distance the distance to the instance
     * @param bag the neighboring instance
     * @param position the position in the bag
     */
    public void insertSorted(double distance, Instance bag, int position) {

      if (isEmpty()) {
        mFirst = mLast = new NeighborNode(distance, bag, position);
      } else {
        NeighborNode current = mFirst;
        if (distance < mFirst.mDistance) {// Insert at head
          mFirst = new NeighborNode(distance, bag, position, mFirst);
        } else { // Insert further down the list
          for( ;(current.mNext != null) && 
              (current.mNext.mDistance < distance); 
              current = current.mNext);
          current.mNext = new NeighborNode(distance, bag, position, current.mNext);
          if (current.equals(mLast)) {
            mLast = current.mNext;
          }
        }

        // Trip down the list until we've got k list elements (or more if the
        // distance to the last elements is the same).
        int valcount = 0;
        for(current = mFirst; current.mNext != null; 
            current = current.mNext) {
          valcount++;
          if ((valcount >= mLength) && (current.mDistance != 
                current.mNext.mDistance)) {
            mLast = current;
            current.mNext = null;
            break;
                }
            }
      }
    }

    /**
     * Prunes the list to contain the k nearest neighbors. If there are
     * multiple neighbors at the k'th distance, all will be kept.
     *
     * @param k the number of neighbors to keep in the list.
     */
    public void pruneToK(int k) {
      if (isEmpty())
        return;
      if (k < 1)
        k = 1;

      int currentK = 0;
      double currentDist = mFirst.mDistance;
      NeighborNode current = mFirst;
      for(; current.mNext != null; current = current.mNext) {
        currentK++;
        currentDist = current.mDistance;
        if ((currentK >= k) && (currentDist != current.mNext.mDistance)) {
          mLast = current;
          current.mNext = null;
          break;
        }
      }
    }

    /**
     * Prints out the contents of the neighborlist
     */
    public void printList() {

      if (isEmpty()) {
        System.out.println("Empty list");
      } else {
        NeighborNode current = mFirst;
        while (current != null) {
          System.out.print("Node: instance " + current.mBagPosition + "\n");
          System.out.println(current.mBag);
          System.out.println(", distance " + current.mDistance);
          current = current.mNext;
        }
        System.out.println();
      }
    }
    /**
     * Prints out the contents of the neighborlist
     */
    public void printReducedList() {

      if (isEmpty()) {
        System.out.println("Empty list");
      } else {
        NeighborNode current = mFirst;
        while (current != null) {
          System.out.print("Node: bag " + current.mBagPosition + "  (" + current.mBag.relationalValue(1).numInstances() +"): ");
          //for(int i = 0; i < current.mBag.getInstances().numInstances(); i++){
          //System.out.print(" " + (current.mBag).getInstances().instance(i));
          //}
          System.out.print("   <" + current.mBag.classValue() + ">");
          System.out.println("  (d: " + current.mDistance + ")");
          current = current.mNext;
        }
        System.out.println();
      }
    }
  }
}