cobweb.java

数据挖掘中聚类的算法

      + "For more information see:\n\n"
      + getTechnicalInformation().toString();
  }

  /**
   * Returns an instance of a TechnicalInformation object, containing 
   * detailed information about the technical background of this class,
   * e.g., paper reference or book this class is based on.
   * 
   * @return the technical information about this class
   */
  public TechnicalInformation getTechnicalInformation() {
    TechnicalInformation 	result;
    TechnicalInformation 	additional;
    
    result = new TechnicalInformation(Type.ARTICLE);
    result.setValue(Field.AUTHOR, "D. Fisher");
    result.setValue(Field.YEAR, "1987");
    result.setValue(Field.TITLE, "Knowledge acquisition via incremental conceptual clustering");
    result.setValue(Field.JOURNAL, "Machine Learning");
    result.setValue(Field.VOLUME, "2");
    result.setValue(Field.NUMBER, "2");
    result.setValue(Field.PAGES, "139-172");
    
    additional = result.add(Type.ARTICLE);
    additional.setValue(Field.AUTHOR, "J. H. Gennari and P. Langley and D. Fisher");
    additional.setValue(Field.YEAR, "1990");
    additional.setValue(Field.TITLE, "Models of incremental concept formation");
    additional.setValue(Field.JOURNAL, "Artificial Intelligence");
    additional.setValue(Field.VOLUME, "40");
    additional.setValue(Field.PAGES, "11-61");
    
    return result;
  }

  /**
   * Returns default capabilities of the clusterer.
   *
   * @return      the capabilities of this clusterer
   */
  public Capabilities getCapabilities() {
    Capabilities result = super.getCapabilities();

    // attributes
    result.enable(Capability.NOMINAL_ATTRIBUTES);
    result.enable(Capability.NUMERIC_ATTRIBUTES);
    result.enable(Capability.DATE_ATTRIBUTES);
    result.enable(Capability.MISSING_VALUES);

    // other
    result.setMinimumNumberInstances(0);
    
    return result;
  }

  /**
   * Builds the clusterer.
   *
   * @param data the training instances.
   * @throws Exception if something goes wrong.
   */
  public void buildClusterer(Instances data) throws Exception {
    m_numberOfClusters = -1;
    m_cobwebTree = null;
    m_numberSplits = 0;
    m_numberMerges = 0;

    // can clusterer handle the data?
    getCapabilities().testWithFail(data);

    // randomize the instances
    data = new Instances(data);
    data.randomize(new Random(getSeed()));

    for (int i = 0; i < data.numInstances(); i++) {
      updateClusterer(data.instance(i));
    }
    
    updateFinished();
  }

  /**
   * Singals the end of the updating.
   */
  public void updateFinished() {
    determineNumberOfClusters();
  }

  /**
   * Classifies a given instance.
   *
   * @param instance the instance to be assigned to a cluster
   * @return the number of the assigned cluster as an interger
   * if the class is enumerated, otherwise the predicted value
   * @throws Exception if instance could not be classified
   * successfully
   */
  public int clusterInstance(Instance instance) throws Exception {
    CNode host = m_cobwebTree;
    CNode temp = null;
    
    determineNumberOfClusters();
    
    do {
      if (host.m_children == null) {
	temp = null;
	break;
      }

      host.updateStats(instance, false);
      temp = host.findHost(instance, true);
      host.updateStats(instance, true);
      
      if (temp != null) {
	host = temp;
      }
    } while (temp != null);
    
    return host.m_clusterNum;
  }

  /**
   * determines the number of clusters if necessary
   * 
   * @see #m_numberOfClusters
   * @see #m_numberOfClustersDetermined
   */
  protected void determineNumberOfClusters() {
    if (    !m_numberOfClustersDetermined 
	 && (m_cobwebTree != null) ) {
      int[] numClusts = new int [1];
      numClusts[0] = 0;
      try {
	m_cobwebTree.assignClusterNums(numClusts);
      }
      catch (Exception e) {
	e.printStackTrace();
	numClusts[0] = 0;
      }
      m_numberOfClusters = numClusts[0];

      m_numberOfClustersDetermined = true;
    }
  }
  
  /**
   * Returns the number of clusters.
   *
   * @return the number of clusters
   */
  public int numberOfClusters() {
    determineNumberOfClusters();
    return m_numberOfClusters;
  }

  /**
   * Adds an instance to the clusterer.
   *
   * @param newInstance the instance to be added
   * @throws Exception 	if something goes wrong
   */
  public void updateClusterer(Instance newInstance) throws Exception {
    m_numberOfClustersDetermined = false;
    
    if (m_cobwebTree == null) {
      m_cobwebTree = new CNode(newInstance.numAttributes(), newInstance);
    } else {
      m_cobwebTree.addInstance(newInstance);
    }
  }
  
  /**
   * Adds an instance to the Cobweb tree.
   *
   * @param newInstance the instance to be added
   * @throws Exception if something goes wrong
   * @deprecated updateClusterer(Instance) should be used instead
   * @see #updateClusterer(Instance)
   */
  public void addInstance(Instance newInstance) throws Exception {
    updateClusterer(newInstance);
  }

  /**
   * Returns an enumeration describing the available options.
   *
   * @return an enumeration of all the available options.
   **/
  public Enumeration listOptions() {
    Vector result = new Vector();
    
    result.addElement(new Option(
	"\tAcuity.\n"
	+"\t(default=1.0)",
	"A", 1,"-A <acuity>"));
    
    result.addElement(new Option(
	"\tCutoff.\n"
	+"\t(default=0.002)",
	"C", 1,"-C <cutoff>"));

    Enumeration en = super.listOptions();
    while (en.hasMoreElements())
      result.addElement(en.nextElement());
    
    return result.elements();
  }

  /**
   * Parses a given list of options. <p/>
   *
   <!-- options-start -->
   * Valid options are: <p/>
   * 
   * <pre> -A &lt;acuity&gt;
   *  Acuity.
   *  (default=1.0)</pre>
   * 
   * <pre> -C &lt;cutoff&gt;
   *  Cutoff.
   *  (default=0.002)</pre>
   * 
   * <pre> -S &lt;num&gt;
   *  Random number seed.
   *  (default 42)</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 {
    String optionString;

    optionString = Utils.getOption('A', options); 
    if (optionString.length() != 0) {
      Double temp = new Double(optionString);
      setAcuity(temp.doubleValue());
    }
    else {
      m_acuity = 1.0;
    }
    optionString = Utils.getOption('C', options); 
    if (optionString.length() != 0) {
      Double temp = new Double(optionString);
      setCutoff(temp.doubleValue());
    }
    else {
      m_cutoff = 0.01 * Cobweb.m_normal;
    }
    
    super.setOptions(options);
  }

  /**
   * Returns the tip text for this property
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String acuityTipText() {
    return "set the minimum standard deviation for numeric attributes";
  }

  /**
   * set the acuity.
   * @param a the acuity value
   */
  public void setAcuity(double a) {
    m_acuity = a;
  }

  /**
   * get the acuity value
   * @return the acuity
   */
  public double getAcuity() {
    return m_acuity;
  }

  /**
   * Returns the tip text for this property
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String cutoffTipText() {
    return "set the category utility threshold by which to prune nodes";
  }

  /**
   * set the cutoff
   * @param c the cutof
   */
  public void setCutoff(double c) {
    m_cutoff = c;
  }

  /**
   * get the cutoff
   * @return the cutoff
   */
  public double getCutoff() {
    return m_cutoff;
  }
  
  /**
   * Returns the tip text for this property
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String saveInstanceDataTipText() {
    return "save instance information for visualization purposes";
  }

  /**
   * Get the value of saveInstances.
   *
   * @return Value of saveInstances.
   */
  public boolean getSaveInstanceData() {
    
    return m_saveInstances;
  }
  
  /**
   * Set the value of saveInstances.
   *
   * @param newsaveInstances Value to assign to saveInstances.
   */
  public void setSaveInstanceData(boolean newsaveInstances) {
    
    m_saveInstances = newsaveInstances;
  }

  /**
   * Gets the current settings of Cobweb.
   *
   * @return an array of strings suitable for passing to setOptions()
   */
  public String[] getOptions() {
    int       		i;
    Vector<String>    	result;
    String[]  		options;

    result = new Vector<String>();

    result.add("-A"); 
    result.add("" + m_acuity);
    result.add("-C"); 
    result.add("" + m_cutoff);

    options = super.getOptions();
    for (i = 0; i < options.length; i++)
      result.add(options[i]);

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

  /**
   * Returns a description of the clusterer as a string.
   *
   * @return a string describing the clusterer.
   */
  public String toString() { 
    StringBuffer text = new StringBuffer();
    if (m_cobwebTree == null) {
      return "Cobweb hasn't been built yet!";
    }
    else {
      m_cobwebTree.dumpTree(0, text); 
      return "Number of merges: "
	+ m_numberMerges+"\nNumber of splits: "
	+ m_numberSplits+"\nNumber of clusters: "
	+ numberOfClusters() +"\n"+text.toString()+"\n\n";
     
    }
  }
    
  /**
   *  Returns the type of graphs this class
   *  represents
   *  @return Drawable.TREE
   */   
  public int graphType() {
      return Drawable.TREE;
  }

  /**
   * Generates the graph string of the Cobweb tree
   *
   * @return a <code>String</code> value
   * @throws Exception if an error occurs
   */
  public String graph() throws Exception {
    StringBuffer text = new StringBuffer();
    
    text.append("digraph CobwebTree {\n");
    m_cobwebTree.graphTree(text);
    text.append("}\n");
    return text.toString();
  }

  /** 
   * Main method
   * 
   * @param argv the commandline options
   */
  public static void main(String[] argv) {
    runClusterer(new Cobweb(), argv);
  }
}