impurity.java

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

/*
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 *    Impurity.java
 *    Copyright (C) 1999 Yong Wang
 *
 */

package weka.classifiers.m5;

import java.io.*;
import java.util.*;
import weka.core.*;

/**
 * Class for handling the impurity values when spliting the instances
 * @author Yong Wang ([e-mail])
 * @version $Revision: 1.4 $
 */
public final class Impurity{
  double n;                   // number of total instances 
  int attr;                   // splitting attribute 
  double nl;                  // number of instances in the left group 
  double nr;                  // number of instances in the right group 
  double sl;                  // sum of the left group  
  double sr;                  // sum of the right group 
  double s2l;                 // squared sum of the left group 
  double s2r;                 // squared sum of the right group 
  double sdl;                 // standard deviation of the left group 
  double sdr;                 // standard deviation of the right group 
  double vl;                  // variance of the left group 
  double vr;                  // variance of the right group 
  double sd;                  // overall standard deviation 
  double va;                  // overall variance 

  double impurity;            // impurity value;
  int order;                  // order = 1, variance; order = 2, standard deviation; order = 3, the cubic root of the variance;  
                              // order = k, the k-th order root of the variance

  /**
   * Constructs an Impurity object containing the impurity values of partitioning the instances using an attribute
   * @param partition the index of the last instance in the left subset
   * @param attribute the attribute used in partitioning
   * @param inst instances
   * @param k the order of the impurity; =1, the variance; =2, the stardard deviation; =k, the k-th order root of the variance
   */
  public Impurity(int partition,int attribute,Instances inst,int k){

    Values values = new Values(0,inst.numInstances()-1,inst.classIndex(),inst);
    attr = attribute;
    n   = inst.numInstances();
    sd  = values.sd; 
    va  = values.va;

    values = new Values(0,partition,inst.classIndex(),inst);
    nl  = partition + 1;
    sl  = values.sum;
    s2l = values.sqrSum;

    values = new Values(partition+1,inst.numInstances()-1,inst.classIndex(),inst);
    nr  = inst.numInstances() - partition -1;
    sr  = values.sum;
    s2r = values.sqrSum;

    order = k;
    this.incremental(0,0);
  }

  /**
   * Converts an Impurity object to a string
   * @return the converted string
   */
  public final String  toString() {
    
    StringBuffer text = new StringBuffer();
    
    text.append("Print impurity values:\n");
    text.append("    Number of total instances:\t" + n + "\n");
    text.append("    Splitting attribute:\t\t" + attr + "\n");
    text.append("    Number of the instances in the left:\t" + nl + "\n");
    text.append("    Number of the instances in the right:\t" + nr + "\n");
    text.append("    Sum of the left:\t\t\t" + sl + "\n");
    text.append("    Sum of the right:\t\t\t" + sr + "\n");
    text.append("    Squared sum of the left:\t\t" + s2l + "\n"); 
    text.append("    Squared sum of the right:\t\t" + s2r + "\n");
    text.append("    Standard deviation of the left:\t" + sdl + "\n");
    text.append("    Standard deviation of the right:\t" + sdr + "\n");
    text.append("    Variance of the left:\t\t" + vr + "\n");
    text.append("    Variance of the right:\t\t" + vr + "\n");
    text.append("    Overall standard deviation:\t\t" + sd + "\n");
    text.append("    Overall variance:\t\t\t" + va + "\n");
    text.append("    Impurity (order " + order + "):\t\t" + impurity + "\n");

    return text.toString();
  }
  
  /**
   * Incrementally computes the impurirty values
   * @param value the incremental value 
   * @param type if type=1, value will be added to the left subset; type=-1, to the right subset; type=0, initializes
   */
  public final void  incremental(double value,int type){
    double y=0.,yl=0.,yr=0.;

    switch(type){
    case 1:
      nl += 1;
      nr -= 1;
      sl += value;
      sr -= value;
      s2l += value*value;
      s2r -= value*value;
      break;
    case -1:
      nl -= 1;
      nr += 1;
      sl -= value;
      sr += value;
      s2l -= value*value;
      s2r += value*value;
      break;
    case 0:
      break;
    default: M5Utils.errorMsg("wrong type in Impurity.incremental().");
    }

    if(nl<=0.0){
      vl=0.0;
      sdl=0.0;
    }
    else {
      vl = (nl*s2l-sl*sl)/((double)nl*((double)nl));
      vl = Math.abs(vl);
      sdl = Math.sqrt(vl);
    }
    if(nr<=0.0){
      vr=0.0;
      sdr=0.0;
    }
    else {
      vr = (nr*s2r-sr*sr)/((double)nr*((double)nr));
      vr = Math.abs(vr);
      sdr = Math.sqrt(vr);
    }

    if(order <= 0)M5Utils.errorMsg("Impurity order less than zero in Impurity.incremental()");
    else if(order == 1) {
      y = va; yl = vl; yr = vr;
    } else {
      y  = Math.pow(va,1./order);
      yl = Math.pow(vl,1./order);
      yr = Math.pow(vr,1./order);
    }

    if(nl<=0.0 || nr<=0.0)
      impurity = 0.0;
    else { 
      impurity = y - ((double)nl/(double)n)*yl - ((double)nr/(double)n)*yr;
    }
  }

}