classifiertree.java

一个很好的LIBSVM的JAVA源码。对于要研究和改进SVM算法的学者。可以参考。来自数据挖掘工具YALE工具包。

   * instance is named "i". The results are returned as two stringbuffers: 
   * a section of code for assignment of the class, and a section of
   * code containing support code (eg: other support methods).
   *
   * @param className the classname that this static classifier has
   * @return an array containing two stringbuffers, the first string containing
   * assignment code, and the second containing source for support code.
   * @exception Exception if something goes wrong
   */
  public StringBuffer [] toSource(String className) throws Exception {
    
    StringBuffer [] result = new StringBuffer [2];
    if (m_isLeaf) {
      result[0] = new StringBuffer("    p = " 
	+ m_localModel.distribution().maxClass(0) + ";\n");
      result[1] = new StringBuffer("");
    } else {
      StringBuffer text = new StringBuffer();
      String nextIndent = "      ";
      StringBuffer atEnd = new StringBuffer();

      long printID = ClassifierTree.nextID();

      text.append("  static double N") 
	.append(Integer.toHexString(m_localModel.hashCode()) + printID)
	.append("(Object []i) {\n")
	.append("    double p = Double.NaN;\n");

      text.append("    if (")
	.append(m_localModel.sourceExpression(-1, m_train))
	.append(") {\n");
      text.append("      p = ")
	.append(m_localModel.distribution().maxClass(0))
	.append(";\n");
      text.append("    } ");
      for (int i = 0; i < m_sons.length; i++) {
	text.append("else if (" + m_localModel.sourceExpression(i, m_train) 
		    + ") {\n");
	if (m_sons[i].m_isLeaf) {
	  text.append("      p = " 
		      + m_localModel.distribution().maxClass(i) + ";\n");
	} else {
	  StringBuffer [] sub = m_sons[i].toSource(className);
	  text.append(sub[0]);
	  atEnd.append(sub[1]);
	}
	text.append("    } ");
	if (i == m_sons.length - 1) {
	  text.append('\n');
	}
      }

      text.append("    return p;\n  }\n");

      result[0] = new StringBuffer("    p = " + className + ".N");
      result[0].append(Integer.toHexString(m_localModel.hashCode()) +  printID)
	.append("(i);\n");
      result[1] = text.append(atEnd);
    }
    return result;
  }

  /**
   * Returns number of leaves in tree structure.
   */
  public int numLeaves() {
    
    int num = 0;
    int i;
    
    if (m_isLeaf)
      return 1;
    else
      for (i=0;i<m_sons.length;i++)
	num = num+m_sons[i].numLeaves();
        
    return num;
  }

  /**
   * Returns number of nodes in tree structure.
   */
  public int numNodes() {
    
    int no = 1;
    int i;
    
    if (!m_isLeaf)
      for (i=0;i<m_sons.length;i++)
	no = no+m_sons[i].numNodes();
    
    return no;
  }

  /**
   * Prints tree structure.
   */
  public String toString() {

    try {
      StringBuffer text = new StringBuffer();
      
      if (m_isLeaf) {
	text.append(": ");
	text.append(m_localModel.dumpLabel(0,m_train));
      }else
	dumpTree(0,text);
      text.append("\n\nNumber of Leaves  : \t"+numLeaves()+"\n");
      text.append("\nSize of the tree : \t"+numNodes()+"\n");
 
      return text.toString();
    } catch (Exception e) {
      return "Can't print classification tree.";
    }
  }

  /**
   * Returns a newly created tree.
   *
   * @param data the training data
   * @exception Exception if something goes wrong
   */
  protected ClassifierTree getNewTree(Instances data) throws Exception {
	 
    ClassifierTree newTree = new ClassifierTree(m_toSelectModel);
    newTree.buildTree(data, false);
    
    return newTree;
  }

  /**
   * Returns a newly created tree.
   *
   * @param data the training data
   * @param test the pruning data.
   * @exception Exception if something goes wrong
   */
  protected ClassifierTree getNewTree(Instances train, Instances test) 
       throws Exception {
	 
    ClassifierTree newTree = new ClassifierTree(m_toSelectModel);
    newTree.buildTree(train, test, false);
    
    return newTree;
  }

  /**
   * Help method for printing tree structure.
   *
   * @exception Exception if something goes wrong
   */
  private void dumpTree(int depth,StringBuffer text) 
       throws Exception {
    
    int i,j;
    
    for (i=0;i<m_sons.length;i++) {
      text.append("\n");;
      for (j=0;j<depth;j++)
	text.append("|   ");
      text.append(m_localModel.leftSide(m_train));
      text.append(m_localModel.rightSide(i, m_train));
      if (m_sons[i].m_isLeaf) {
	text.append(": ");
	text.append(m_localModel.dumpLabel(i,m_train));
      }else
	m_sons[i].dumpTree(depth+1,text);
    }
  }

  /**
   * Help method for printing tree structure as a graph.
   *
   * @exception Exception if something goes wrong
   */
  private void graphTree(StringBuffer text) throws Exception {
    
    for (int i = 0; i < m_sons.length; i++) {
      text.append("N" + m_id  
		  + "->" + 
		  "N" + m_sons[i].m_id +
		  " [label=\"" + m_localModel.rightSide(i,m_train).trim() + 
		  "\"]\n");
      if (m_sons[i].m_isLeaf) {
	text.append("N" + m_sons[i].m_id +
		    " [label=\""+m_localModel.dumpLabel(i,m_train)+"\" "+ 
		    "shape=box style=filled ");
	if (m_train != null && m_train.numInstances() > 0) {
	  text.append("data =\n" + m_sons[i].m_train + "\n");
	  text.append(",\n");
	}
	text.append("]\n");
      } else {
	text.append("N" + m_sons[i].m_id +
		    " [label=\""+m_sons[i].m_localModel.leftSide(m_train) + 
		    "\" ");
	if (m_train != null && m_train.numInstances() > 0) {
	  text.append("data =\n" + m_sons[i].m_train + "\n");
	  text.append(",\n");
	}
	text.append("]\n");
	m_sons[i].graphTree(text);
      }
    }
  }

  /**
   * Prints the tree in prefix form
   */
  private void prefixTree(StringBuffer text) throws Exception {

    text.append("[");
    text.append(m_localModel.leftSide(m_train)+":");
    for (int i = 0; i < m_sons.length; i++) {
      if (i > 0) {
	text.append(",\n");
      }
      text.append(m_localModel.rightSide(i, m_train));
    }
    for (int i = 0; i < m_sons.length; i++) {
      if (m_sons[i].m_isLeaf) {
	text.append("[");
	text.append(m_localModel.dumpLabel(i,m_train));
	text.append("]");
      } else {
	m_sons[i].prefixTree(text);
      }
    }
    text.append("]");
  }

  /**
   * Help method for computing class probabilities of 
   * a given instance.
   *
   * @exception Exception if something goes wrong
   */
  private double getProbsLaplace(int classIndex, Instance instance, double weight) 
    throws Exception {
    
    double [] weights;
    double prob = 0;
    int treeIndex;
    int i,j;
    
    if (m_isLeaf) {
      return weight * localModel().classProbLaplace(classIndex, instance, -1);
    } else {
      treeIndex = localModel().whichSubset(instance);
      if (treeIndex == -1) {
	weights = localModel().weights(instance);
	for (i = 0; i < m_sons.length; i++) {
	  if (!son(i).m_isEmpty) {
	    if (!son(i).m_isLeaf) {
	      prob += son(i).getProbsLaplace(classIndex, instance, 
					     weights[i] * weight);
	    } else {
	      prob += weight * weights[i] * 
		localModel().classProbLaplace(classIndex, instance, i);
	    }
	  }
	}
	return prob;
      } else {
	if (son(treeIndex).m_isLeaf) {
	  return weight * localModel().classProbLaplace(classIndex, instance, 
							treeIndex);
	} else {
	  return son(treeIndex).getProbsLaplace(classIndex, instance, weight);
	}
      }
    }
  }

  /**
   * Help method for computing class probabilities of 
   * a given instance.
   *
   * @exception Exception if something goes wrong
   */
  private double getProbs(int classIndex, Instance instance, double weight) 
    throws Exception {
    
    double [] weights;
    double prob = 0;
    int treeIndex;
    int i,j;
    
    if (m_isLeaf) {
      return weight * localModel().classProb(classIndex, instance, -1);
    } else {
      treeIndex = localModel().whichSubset(instance);
      if (treeIndex == -1) {
	weights = localModel().weights(instance);
	for (i = 0; i < m_sons.length; i++) {
	  if (!son(i).m_isEmpty) {
	    prob += son(i).getProbs(classIndex, instance, 
				    weights[i] * weight);
	  }
	}
	return prob;
      } else {
	if (son(treeIndex).m_isEmpty) {
	  return weight * localModel().classProb(classIndex, instance, 
						 treeIndex);
	} else {
	  return son(treeIndex).getProbs(classIndex, instance, weight);
	}
      }
    }
  }

  /**
   * Method just exists to make program easier to read.
   */
  private ClassifierSplitModel localModel() {
    
    return (ClassifierSplitModel)m_localModel;
  }
  
  /**
   * Method just exists to make program easier to read.
   */
  private ClassifierTree son(int index) {
    
    return (ClassifierTree)m_sons[index];
  }
}