mismo.java

Java 编写的多种数据挖掘算法 包括聚类、分类、预处理等

        m_I1.insert(i2);
      } else {
        m_I1.delete(i2);
      }
      if ((y2 == -1) && (a2 == C2)) {
        m_I2.insert(i2);
      } else {
        m_I2.delete(i2);
      }
      if ((y2 == 1) && (a2 == C2)) {
        m_I3.insert(i2);
      } else {
        m_I3.delete(i2);
      }
      if ((y2 == -1) && (a2 == 0)) {
        m_I4.insert(i2);
      } else {
        m_I4.delete(i2);
      }

      // Update error cache using new Lagrange multipliers
      for (int j = m_I0.getNext(-1); j != -1; j = m_I0.getNext(j)) {
        if ((j != i1) && (j != i2)) {
          m_errors[j] += 
            y1 * (a1 - alph1) * m_kernel.eval(i1, j, m_data.instance(i1)) + 
            y2 * (a2 - alph2) * m_kernel.eval(i2, j, m_data.instance(i2));
        }
      }

      // Update error cache for i1 and i2
      m_errors[i1] += y1 * (a1 - alph1) * k11 + y2 * (a2 - alph2) * k12;
      m_errors[i2] += y1 * (a1 - alph1) * k12 + y2 * (a2 - alph2) * k22;

      // Update array with Lagrange multipliers
      m_alpha[i1] = a1;
      m_alpha[i2] = a2;

      // Update thresholds
      m_bLow = -Double.MAX_VALUE; m_bUp = Double.MAX_VALUE;
      m_iLow = -1; m_iUp = -1;
      for (int j = m_I0.getNext(-1); j != -1; j = m_I0.getNext(j)) {
        if (m_errors[j] < m_bUp) {
          m_bUp = m_errors[j]; m_iUp = j;
        }
        if (m_errors[j] > m_bLow) {
          m_bLow = m_errors[j]; m_iLow = j;
        }
      }
      if (!m_I0.contains(i1)) {
        if (m_I3.contains(i1) || m_I4.contains(i1)) {
          if (m_errors[i1] > m_bLow) {
            m_bLow = m_errors[i1]; m_iLow = i1;
          } 
        } else {
          if (m_errors[i1] < m_bUp) {
            m_bUp = m_errors[i1]; m_iUp = i1;
          }
        }
      }
      if (!m_I0.contains(i2)) {
        if (m_I3.contains(i2) || m_I4.contains(i2)) {
          if (m_errors[i2] > m_bLow) {
            m_bLow = m_errors[i2]; m_iLow = i2;
          }
        } else {
          if (m_errors[i2] < m_bUp) {
            m_bUp = m_errors[i2]; m_iUp = i2;
          }
        }
      }
      if ((m_iLow == -1) || (m_iUp == -1)) {
        throw new Exception("This should never happen!");
      }

      // Made some progress.
      return true;
    }

    /**
     * Quick and dirty check whether the quadratic programming problem is solved.
     * 
     * @throws Exception if something goes wrong
     */
    protected void checkClassifier() throws Exception {

      double sum = 0;
      for (int i = 0; i < m_alpha.length; i++) {
        if (m_alpha[i] > 0) {
          sum += m_class[i] * m_alpha[i];
        }
      }
      System.err.println("Sum of y(i) * alpha(i): " + sum);

      for (int i = 0; i < m_alpha.length; i++) {
        double output = SVMOutput(i, m_data.instance(i));
        if (Utils.eq(m_alpha[i], 0)) {
          if (Utils.sm(m_class[i] * output, 1)) {
            System.err.println("KKT condition 1 violated: " + m_class[i] * output);
          }
        } 
        if (Utils.gr(m_alpha[i], 0) && 
            Utils.sm(m_alpha[i], m_C * m_data.instance(i).weight())) {
          if (!Utils.eq(m_class[i] * output, 1)) {
            System.err.println("KKT condition 2 violated: " + m_class[i] * output);
          }
            } 
        if (Utils.eq(m_alpha[i], m_C * m_data.instance(i).weight())) {
          if (Utils.gr(m_class[i] * output, 1)) {
            System.err.println("KKT condition 3 violated: " + m_class[i] * output);
          }
        } 
      }
    }  
  }

  /** Normalize training data */
  public static final int FILTER_NORMALIZE = 0;
  /** Standardize training data */
  public static final int FILTER_STANDARDIZE = 1;
  /** No normalization/standardization */
  public static final int FILTER_NONE = 2;
  /** The filter to apply to the training data */
  public static final Tag [] TAGS_FILTER = {
    new Tag(FILTER_NORMALIZE, "Normalize training data"),
    new Tag(FILTER_STANDARDIZE, "Standardize training data"),
    new Tag(FILTER_NONE, "No normalization/standardization"),
  };

  /** The binary classifier(s) */
  protected BinaryMISMO[][] m_classifiers = null;

  /** The complexity parameter. */
  protected double m_C = 1.0;

  /** Epsilon for rounding. */
  protected double m_eps = 1.0e-12;

  /** Tolerance for accuracy of result. */
  protected double m_tol = 1.0e-3;

  /** Whether to normalize/standardize/neither */
  protected int m_filterType = FILTER_NORMALIZE;

  /** Use MIMinimax feature space?  */
  protected boolean m_minimax = false;   

  /** The filter used to make attributes numeric. */
  protected NominalToBinary m_NominalToBinary;

  /** The filter used to standardize/normalize all values. */
  protected Filter m_Filter = null;

  /** The filter used to get rid of missing values. */
  protected ReplaceMissingValues m_Missing;

  /** The class index from the training data */
  protected int m_classIndex = -1;

  /** The class attribute */
  protected Attribute m_classAttribute;
  
  /** Kernel to use **/
  protected Kernel m_kernel = new MIPolyKernel();

  /** Turn off all checks and conversions? Turning them off assumes
    that data is purely numeric, doesn't contain any missing values,
    and has a nominal class. Turning them off also means that
    no header information will be stored if the machine is linear. 
    Finally, it also assumes that no instance has a weight equal to 0.*/
  protected boolean m_checksTurnedOff;

  /** Precision constant for updating sets */
  protected static double m_Del = 1000 * Double.MIN_VALUE;

  /** Whether logistic models are to be fit */
  protected boolean m_fitLogisticModels = false;

  /** The number of folds for the internal cross-validation */
  protected int m_numFolds = -1;

  /** The random number seed  */
  protected int m_randomSeed = 1;

  /**
   * Turns off checks for missing values, etc. Use with caution.
   */
  public void turnChecksOff() {

    m_checksTurnedOff = true;
  }

  /**
   * Turns on checks for missing values, etc.
   */
  public void turnChecksOn() {

    m_checksTurnedOff = false;
  }

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

    // attributes
    result.enable(Capability.NOMINAL_ATTRIBUTES);
    result.enable(Capability.RELATIONAL_ATTRIBUTES);
    result.enable(Capability.MISSING_VALUES);

    // class
    result.disableAllClasses();
    result.disableAllClassDependencies();
    result.enable(Capability.NOMINAL_CLASS);
    result.enable(Capability.MISSING_CLASS_VALUES);
    
    // other
    result.enable(Capability.ONLY_MULTIINSTANCE);
    
    return result;
  }

  /**
   * Returns the capabilities of this multi-instance classifier for the
   * relational data.
   *
   * @return            the capabilities of this object
   * @see               Capabilities
   */
  public Capabilities getMultiInstanceCapabilities() {
    Capabilities result = ((MultiInstanceCapabilitiesHandler) getKernel()).getMultiInstanceCapabilities();
    result.setOwner(this);

    // attribute
    result.enableAllAttributeDependencies();
    // with NominalToBinary we can also handle nominal attributes, but only
    // if the kernel can handle numeric attributes
    if (result.handles(Capability.NUMERIC_ATTRIBUTES))
      result.enable(Capability.NOMINAL_ATTRIBUTES);
    result.enable(Capability.MISSING_VALUES);
    
    return result;
  }

  /**
   * Method for building the classifier. Implements a one-against-one
   * wrapper for multi-class problems.
   *
   * @param insts the set of training instances
   * @throws Exception if the classifier can't be built successfully
   */
  public void buildClassifier(Instances insts) throws Exception {
    if (!m_checksTurnedOff) {
      // can classifier handle the data?
      getCapabilities().testWithFail(insts);

      // remove instances with missing class
      insts = new Instances(insts);
      insts.deleteWithMissingClass();

      /* Removes all the instances with weight equal to 0.
         MUST be done since condition (8) of Keerthi's paper 
         is made with the assertion Ci > 0 (See equation (3a). */
      Instances data = new Instances(insts, insts.numInstances());
      for(int i = 0; i < insts.numInstances(); i++){
        if(insts.instance(i).weight() > 0)
          data.add(insts.instance(i));
      }
      if (data.numInstances() == 0) {
        throw new Exception("No training instances left after removing " + 
            "instance with either a weight null or a missing class!");
      }
      insts = data;     
    }

    // filter data
    if (!m_checksTurnedOff) 
      m_Missing = new ReplaceMissingValues();
    else 
      m_Missing = null;

    if (getCapabilities().handles(Capability.NUMERIC_ATTRIBUTES)) {
      boolean onlyNumeric = true;
      if (!m_checksTurnedOff) {
	for (int i = 0; i < insts.numAttributes(); i++) {
	  if (i != insts.classIndex()) {
	    if (!insts.attribute(i).isNumeric()) {
	      onlyNumeric = false;
	      break;
	    }
	  }
	}
      }
      
      if (!onlyNumeric) {
	m_NominalToBinary = new NominalToBinary();
	// exclude the bag attribute
	m_NominalToBinary.setAttributeIndices("2-last");
      }
      else {
	m_NominalToBinary = null;
      }
    }
    else {
      m_NominalToBinary = null;
    }

    if (m_filterType == FILTER_STANDARDIZE) 
      m_Filter = new Standardize();
    else if (m_filterType == FILTER_NORMALIZE)
      m_Filter = new Normalize();
    else 
      m_Filter = null;


    Instances transformedInsts;
    Filter convertToProp = new MultiInstanceToPropositional();
    Filter convertToMI = new PropositionalToMultiInstance();

    //transform the data into single-instance format
    if (m_minimax){ 
      /* using SimpleMI class minimax transform method. 
         this method transforms the multi-instance dataset into minmax feature space (single-instance) */
      SimpleMI transMinimax = new SimpleMI();
      transMinimax.setTransformMethod(
          new SelectedTag(
            SimpleMI.TRANSFORMMETHOD_MINIMAX, SimpleMI.TAGS_TRANSFORMMETHOD));
      transformedInsts = transMinimax.transform(insts);
    }
    else { 
      convertToProp.setInputFormat(insts);
      transformedInsts=Filter.useFilter(insts, convertToProp);
    }

    if (m_Missing != null) {
      m_Missing.setInputFormat(transformedInsts);
      transformedInsts = Filter.useFilter(transformedInsts, m_Missing); 
    }

    if (m_NominalToBinary != null) { 
      m_NominalToBinary.setInputFormat(transformedInsts);
      transformedInsts = Filter.useFilter(transformedInsts, m_NominalToBinary); 
    }

    if (m_Filter != null) {
      m_Filter.setInputFormat(transformedInsts);
      transformedInsts = Filter.useFilter(transformedInsts, m_Filter); 
    }

    // convert the single-instance format to multi-instance format
    convertToMI.setInputFormat(transformedInsts);
    insts = Filter.useFilter( transformedInsts, convertToMI);

    m_classIndex = insts.classIndex();
    m_classAttribute = insts.classAttribute();

    // Generate subsets representing each class
    Instances[] subsets = new Instances[insts.numClasses()];
    for (int i = 0; i < insts.numClasses(); i++) {
      subsets[i] = new Instances(insts, insts.numInstances());
    }
    for (int j = 0; j < insts.numInstances(); j++) {
      Instance inst = insts.instance(j);
      subsets[(int)inst.classValue()].add(inst);
    }
    for (int i = 0; i < insts.numClasses(); i++) {
      subsets[i].compactify();
    }

    // Build the binary classifiers
    Random rand = new Random(m_randomSeed);
    m_classifiers = new BinaryMISMO[insts.numClasses()][insts.numClasses()];
    for (int i = 0; i < insts.numClasses(); i++) {
      for (int j = i + 1; j < insts.numClasses(); j++) {
        m_classifiers[i][j] = new BinaryMISMO();  
        m_classifiers[i][j].setKernel(Kernel.makeCopy(getKernel()));
        Instances data = new Instances(insts, insts.numInstances());
        for (int k = 0; k < subsets[i].numInstances(); k++) {
          data.add(subsets[i].instance(k));
        }
        for (int k = 0; k < subsets[j].numInstances(); k++) {
          data.add(subsets[j].instance(k));
        }  
        data.compactify(); 
        data.randomize(rand);
        m_classifiers[i][j].buildClassifier(data, i, j, 
            m_fitLogisticModels,
            m_numFolds, m_randomSeed);
      }
    } 

  }

  /**
   * Estimates class probabilities for given instance.
   * 
   * @param inst the instance to compute the distribution for
   * @return the class probabilities
   * @throws Exception if computation fails
   */
  public double[] distributionForInstance(Instance inst) throws Exception { 

    //convert instance into instances
    Instances insts = new Instances(inst.dataset(), 0);
    insts.add(inst);

    //transform the data into single-instance format
    Filter convertToProp = new MultiInstanceToPropositional();
    Filter convertToMI = new PropositionalToMultiInstance();

    if (m_minimax){ // using minimax feature space
      SimpleMI transMinimax = new SimpleMI();
      transMinimax.setTransformMethod(
          new SelectedTag(
            SimpleMI.TRANSFORMMETHOD_MINIMAX, SimpleMI.TAGS_TRANSFORMMETHOD));
      insts = transMinimax.transform (insts);
    }
    else{
      convertToProp.setInputFormat(insts);
      insts=Filter.useFilter( insts, convertToProp);
    }