node.java

:<<数据挖掘--实用机器学习技术及java实现>>一书的配套源程序

    function.coeffs = x.regression(y,n,k); 
  }
  
  /**
   * Finds the appropriate order of the unsmoothed linear model at this node
   * @exception Exception if something goes wrong
   */
  public final void  function() throws Exception {

    int n,jmin,flag=0;
    double err1,err2,sdy;
    Errors e1,e2;
    Function f1 = unsmoothed;
    Function f2;

    if(f1.terms[0]!=0){
      sdy = M5Utils.stdDev(instances.classIndex(),instances);
      this.regression(f1);
      valueNode = false;
      if(model != LINEAR_REGRESSION){
	e1 = f1.errors(instances);
	err1 = e1.rootMeanSqrErr * this.factor(instances.numInstances(),
					   f1.terms[0]+1,pruningFactor);
	flag = 0;
	
	while(flag==0){
	  jmin = f1.insignificant(sdy,instances);
	  if(jmin==-1)flag = 1;
	  else {
	    f2 = f1.remove(jmin);
	    this.regression(f2);
	    e2 = f2.errors(instances);
	    err2 = e2.rootMeanSqrErr * this.factor(instances.numInstances(),
					       f2.terms[0]+1,pruningFactor);
	    if(err2 > err1 && err2 > deviation * 0.00001) flag = 1;
	    else {        // compare estimated error with and without attr jmin
	      f1 = f2;
	      err1 = err2;
	      if(f1.terms[0]==0) flag = 1;
	    }
	  }
	}
      }
      unsmoothed = f1;
    }
    if(unsmoothed.terms[0] == 0){      // constant function without attributes
      this.valueNode();
    } 
  }
  
  /**
   * Calculates a multiplication factor used at this node
   * @param n the number of instances
   * @param v the number of the coefficients
   * @pruningFactor the pruning factor
   * @return multiplication factor
   */
  public final double  factor(int n,int v,double pruningFactor) {

    double factor=0.0;
    
    if(n <= v)return 10.0;  /* Caution */
    factor = (double)(n+pruningFactor*v)/(double)(n-v);
    
    return factor;
  }

  /**
   * Smoothens all unsmoothed formulae at the tree leaves under this node.
   */
  public final void  smoothen()
  {
    if (type == false) {
      smoothed = unsmoothed.copy(); 
      if(upNode != null)
	this.smoothenFormula(this);
    }
    else {
      leftNode.smoothen();
      rightNode.smoothen();
    }
  }
  
  /**
   * Recursively smoothens the unsmoothed linear model at this node with the 
   *     unsmoothed linear models at the nodes above this
   * @param current the unsmoothed linear model at the up node of the 
   *     'current' will be used for smoothening
   */
  public final void  smoothenFormula(Node current) {

    int i=smoothed.terms[0],j=current.upNode.unsmoothed.terms[0],k,l,
      smoothingConstant=15;
    Function function;
    
    function = Function.combine(smoothed,current.upNode.unsmoothed);
    
    function.coeffs[0] = 
      M5Utils.smoothenValue(smoothed.coeffs[0],
			    current.upNode.unsmoothed.coeffs[0],
			    current.instances.numInstances(),
			    smoothingConstant);
    for(k=function.terms[0];k>=1;k--){
      if(i>=1 && j>=1){
	if(function.terms[k]==smoothed.terms[i] && function.terms[k]==
	   current.upNode.unsmoothed.terms[j]){
	  function.coeffs[k] = 
	    M5Utils.smoothenValue(smoothed.coeffs[i],
				  current.upNode.unsmoothed.coeffs[j],
				  current.instances.numInstances(),
				  smoothingConstant);
	  i--;j--;
	}
	else if(function.terms[k]==smoothed.terms[i] && 
		function.terms[k]!=current.upNode.unsmoothed.terms[j]){
	  function.coeffs[k] = 
	    M5Utils.smoothenValue(smoothed.coeffs[i],
				  0.0,
				  current.instances.numInstances(),
				  smoothingConstant);
	  i--;
	}
	else if(function.terms[k]!=smoothed.terms[i] && 
		function.terms[k]==current.upNode.unsmoothed.terms[j]){
	  function.coeffs[k] = 
	    M5Utils.smoothenValue(0.0,
				  current.upNode.unsmoothed.coeffs[j],
				  current.instances.numInstances(),
				  smoothingConstant);
	  j--;
	}
	else M5Utils.errorMsg("wrong terms value in smoothing_formula().");
      }
      else if(i<1&&j<1)break;
      else if(j>=1){
	for(l=k;l>=1;l--) 
	  function.coeffs[l] = 
	    M5Utils.smoothenValue(0.0,
				  current.upNode.unsmoothed.coeffs[j--],
				  current.instances.numInstances(),
				  smoothingConstant);
	break;
      }
      else {
	for(l=k;l>=1;l--) 
	  function.coeffs[l] = 
	    M5Utils.smoothenValue(smoothed.coeffs[i--],
				  0.0,
				  current.instances.numInstances(),
				  smoothingConstant);
	break;
      }
    }
    smoothed = function;
    if(current.upNode.upNode != null) this.smoothenFormula(current.upNode);
  }
  
  /**
   * Converts the predictions by the tree under this node to a string
   * @param insta instances
   * @param smooth =ture using the smoothed models; otherwise, the unsmoothed
   * @return the converted string
   * @exception Exception if something goes wrong
   */
  public final String  predictionsToString(Instances inst,int lmNo,
					   boolean smooth) throws Exception {
    int i,lmNum;
    double value;
    StringBuffer text = new StringBuffer();
    
    text.append("    Predicting test instances (" + 
		inst.attribute(inst.classIndex()).name() + ", column " 
		+ (inst.classIndex()+1) +")\n\n");
    for(i=0;i<=inst.numInstances()-1;i++){
      lmNum = this.leafNum(inst.instance(i));
      if(lmNo==0 || lmNo==lmNum){
	text.append("      Predicting " + i + " (LM" + lmNum + "):  ");
	text.append(inst.instance(i).toString() + "\n");
	value = this.predict(inst.instance(i),smooth);
	if(inst.instance(i).classIsMissing() == false)
	  text.append("      Actual value: " + 
		      M5Utils.doubleToStringG(inst.instance(i).classValue(),9,4) + 
		      "    Prediction: " + M5Utils.doubleToStringG(value,9,4) + 
		      "    Abs. error: " + M5Utils.doubleToStringG(Math.abs(inst.instance(i).classValue()-value),9,4) + 
		      "\n\n");
	else text.append("      Actual value:   missing    Prediction: " + 
			 M5Utils.doubleToStringG(value,9,4) + 
			 "    Abs. Error: undefined\n\n");
      }
    }

    return text.toString();
  }  
 
  /**
   * Detects which leaf a instance falls into
   * @param i instance i
   * @param inst instances
   * @return the leaf no.
   */
  public final int  leafNum(Instance instance) {
    
    int lmNum=0;
    
    if(type == false){
      lmNum = lm;
    }
    else {
      if (instance.value(splitAttr) <= splitValue)
	lmNum = leftNode.leafNum(instance);
      else lmNum = rightNode.leafNum(instance);
    }
    
    return lmNum;
  }

  /**
   * Predicts the class value of an instance by the tree 
   * @param i instance i
   * @smooth =true, uses the smoothed model; otherwise uses the unsmoothed 
   * @inst instances
   * @return the predicted value
   */
  public final double  predict(Instance instance,boolean smooth) {

    double y=0.0;
    
    if(type == false) {                 // LEAF
      if(smooth==true){
	y = smoothed.predict(instance);
      }
      else {
	if(valueNode == true) y = unsmoothed.coeffs[0];
	else y = unsmoothed.predict(instance);
      }
    }
    else {                             // NODE
      if(instance.value(splitAttr) <= splitValue)
	y = leftNode.predict(instance,smooth);
      else y = rightNode.predict(instance,smooth);
    }

    return y;
  }

  /**
   * Evaluates a tree
   * @param inst instances
   * @smooth =true, evaluates the smoothed models; 
   *         =false, evaluats the unsmoothed models
   * @return the evaluation results
   * @exception Exception if something goes wrong
   */
  public final Errors  errors(Instances inst,boolean smooth) throws Exception 
  {
    int i;
    double tmp;
    Errors e = new Errors(0,inst.numInstances()-1);
    
    for(i=0;i<=inst.numInstances()-1;i++){
      tmp = this.predict(inst.instance(i),smooth) - inst.instance(i).classValue();
      e.sumErr += tmp;
      e.sumAbsErr += Math.abs(tmp);
      e.sumSqrErr += tmp * tmp;
    }
    
    e.meanAbsErr = e.sumAbsErr / e.numInstances;
    e.meanSqrErr = (e.sumSqrErr - e.sumErr * e.sumErr/e.numInstances)
      / e.numInstances;
    e.meanSqrErr = Math.abs(e.meanSqrErr);
    e.rootMeanSqrErr = Math.sqrt(e.meanSqrErr);
    
    return e;
  }

  /**
   * Computes performance measures of a tree
   * @param inst instances
   * @param smooth =true uses the smoothed models; 
   *        otherwise uses the unsmoothed models
   * @return the performance measures
   * @exception Exception if something goes wrong
   */
  public final Measures  measures(Instances inst,boolean smooth) throws Exception {

    int i,numInstances,count;
    double sd,y1[],y2[];
    Measures measures = new Measures();
    
    errors = this.errors(inst,smooth);
    numInstances = errors.numInstances -  errors.missingInstances;
    y1 = new double[numInstances];
    y2 = new double[numInstances];
    count=0;
    for(i=0;i<=inst.numInstances()-1;i++){
      y1[count] = this.predict(inst.instance(i),smooth);
      y2[count] = inst.instance(i).classValue();
      count++;
    }

    measures.correlation = M5Utils.correlation(y1,y2,numInstances);

    sd = M5Utils.stdDev(inst.classIndex(),inst);
    if(sd > 0.0){
      measures.meanAbsErr = errors.meanAbsErr;
      measures.meanSqrErr = errors.meanSqrErr;
      measures.type=0;
    } 
    else {
      if(numInstances >= 1){
	measures.type=1;
	measures.meanAbsErr = errors.meanAbsErr;
	measures.meanSqrErr = errors.meanSqrErr;
      }
      else {
	measures.type=2;
	measures.meanAbsErr = 0.0;
	measures.meanSqrErr = 0.0;
      }
    }
    
    return measures;
  }

  /**
   * Computes performance measures for both unsmoothed and smoothed models
   * @param inst instances
   * @exception Exception if something goes wrong
   */
  public final Measures[]  validation(Instances inst) throws Exception {

    Measures measures[] = new Measures[2];

    // without smoothing 
    measures[0] = this.measures(inst,false);
    
    // with smoothing 
    if(model == MODEL_TREE){
      measures[1] = this.measures(inst,true);
    }
    else measures[1] = new Measures();
    
    return measures;
  }
  
  /**
   * Makes a copy of the tree under this node
   * @param up the parant node of the new node
   * @return a copy of the tree under this node
   * @exception Exception if something goes wrong
   */
  public final Node  copy(Node up) throws Exception {

    Node node = new Node(instances,upNode);

    node.type = type;
    node.splitAttr = splitAttr;
    node.splitValue = splitValue;
    node.unsmoothed = unsmoothed.copy();
    node.smoothed = smoothed.copy();
    node.valueNode = valueNode;
    node.upNode = up;
    if(errors == null) node.errors = null;
    else node.errors = errors.copy();
    node.numParameters = node.numParameters;
    if(sf == null) node.sf = null;
    else node.sf = sf.copy();
    node.instances = new Instances(instances,0,
					    instances.numInstances());
    node.lm = lm;

    node.model = model;
    node.pruningFactor = pruningFactor;
    node.deviation = deviation;

    if(leftNode != null) node.leftNode = leftNode.copy(node); 
    else node.leftNode = null;
    if(rightNode != null) node.rightNode = rightNode.copy(node); 
    else node.rightNode = null;

    return node;
  }

  /**
   * Converts the performance measures into a string
   * @param measures[] contains both the unsmoothed and smoothed measures
   * @param inst the instances
   * @param lmNo also converts the predictions by all linear models if lmNo=0, 
   *        or one linear model spedified by lmNo.
   * @param verbosity the verbosity level
   * @param str the type of evaluation, one of 
   *        "t" for training, "T" for testing, 
   *        "f" for fold training, "F" for fold testing, 
   *        "x" for cross-validation
   * @return the converted string
   * @exception Exception if something goes wrong
   */
  public final String  measuresToString(Measures measures[],Instances 
					inst,int lmNo,int verbosity,String str) throws Exception {

    StringBuffer text = new StringBuffer();
    double absDev,sd;

    absDev = M5Utils.absDev(inst.classIndex(),inst);
    sd = M5Utils.stdDev(inst.classIndex(),inst);
    
    text.append("  Without smoothing:\n\n");
    if((verbosity>=2 || lmNo !=0) && 
       (str.equals("T") == true || str.equals("F") == true)) 
      text.append(predictionsToString(inst,lmNo,false));
    text.append(measures[0].toString(absDev,sd,str,"u") + "\n\n");
    text.append("  With smoothing:\n\n");
    if((verbosity>=2 || lmNo !=0) && 
       (str.equals("T") == true || str.equals("F") == true)) 
      text.append(this.predictionsToString(inst,lmNo,true));
    text.append(measures[1].toString(absDev,sd,str,"s") + "\n\n");
    
    return text.toString();
  }  

}