smoreg.java

MacroWeka扩展了著名数据挖掘工具weka

      }   
    } 
	
    // case 2 : i2 is in I_0b	
    else if(m_I0.contains(i2) && 0 < alpha2_ && alpha2_ < m_C * m_data.instance(i2).weight()){
      if(m_bLow-(F2+m_epsilon) > 2 * m_tol){
	optimality = false;
	i1 = m_iLow;
	// for i2 in I_0b choose the better i1
	if((F2 + m_epsilon) - m_bUp > m_bLow - (F2 + m_epsilon)){
	  i1 = m_iUp;
	}
      }else if((F2 + m_epsilon)-m_bUp > 2 * m_tol){
	optimality = false;
	i1 = m_iUp;
	// for i2 in I_0b choose the better i1...
	if(m_bLow-(F2+m_epsilon) > (F2+m_epsilon)-m_bUp){
	  i1 = m_iLow;
	}
      }   
    }
	
    // case 3 : i2 is in I_1	
    else if(m_I1.contains(i2)){
      if(m_bLow-(F2+m_epsilon) > 2 * m_tol){
	optimality = false;
	i1 = m_iLow;
	// for i2 in I_1 choose the better i1
	if((F2 + m_epsilon) - m_bUp > m_bLow - (F2 + m_epsilon)){
	  i1 = m_iUp;
	}
      } else if((F2 - m_epsilon)-m_bUp > 2 * m_tol){
	optimality = false;
	i1 = m_iUp;
	// for i2 in I_1 choose the better i1...
	if(m_bLow-(F2-m_epsilon) > (F2-m_epsilon)-m_bUp){
	  i1 = m_iLow;
	}
      }   
    }

    // case 4 : i2 is in I_2	
    else if(m_I2.contains(i2)){
      if((F2+m_epsilon)-m_bUp > 2 * m_tol){
	optimality = false;
	i1 = m_iUp;
      }
    }
	
    // case 5 : i2 is in I_3	
    else if(m_I3.contains(i2)){
      if(m_bLow-(F2-m_epsilon) > 2 * m_tol){
	optimality = false;
	i1 = m_iLow;
      }
    }

    else{
      throw new RuntimeException("Inconsistent state ! I0, I1, I2 and I3 " +
				 "must cover the whole set of indices.");
    }

    if(optimality){
      return 0;
    }

    if(takeStep(i1, i2)){
      return 1;
    } else {
      return 0;
    }
  }


  /**
   * Method solving for the Lagrange multipliers for
   * two instances. (As defined in Shevade's paper.)
   *
   * @param i1 index of the first instance
   * @param i2 index of the second instance
   * @return true if multipliers could be found
   * @exception Exception if something goes wrong
   */
  protected boolean takeStep(int i1, int i2) throws Exception{

    if(i1 == i2){
      return false;
    }

    double alpha1 = m_alpha[i1];
    double alpha1_ = m_alpha_[i1];
    double alpha2 = m_alpha[i2];
    double alpha2_ = m_alpha_[i2];

    double F1 = m_fcache[i1];
    double F2 = m_fcache[i2];

    double k11 = m_kernel.eval(i1, i1, m_data.instance(i1));
    double k12 = m_kernel.eval(i1, i2, m_data.instance(i1));
    double k22 = m_kernel.eval(i2, i2, m_data.instance(i2));	
    double eta = -2*k12+k11+k22;
    double gamma = alpha1 - alpha1_ + alpha2 - alpha2_;

    // In case of numerical instabilies eta might be sligthly less than 0.
    // (Theoretically, it cannot happen with a kernel which respects Mercer's condition.)
    if(eta < 0)	    
      eta = 0;
	
    boolean case1 = false, case2 = false, case3 = false, case4 = false, finished = false;
    double deltaphi = F1 - F2;
    double L, H;
    boolean changed = false;
    double a1, a2;
	
    while(!finished){
	    
      // this loop is passed at most three times
      // Case variables needed to avoid attempting small changes twices

      if(!case1 && 
	 (alpha1 > 0 || (alpha1_ == 0 && deltaphi > 0)) &&
	 (alpha2 > 0 || (alpha2_ == 0 && deltaphi < 0)) ){

	// compute L, H (wrt alpha1, alpha2)
	L = java.lang.Math.max(0, gamma - m_C * m_data.instance(i1).weight());
	H = java.lang.Math.min(m_C * m_data.instance(i2).weight(), gamma);

	if(L < H){
	  if(eta > 0){
	    a2 = alpha2 - (deltaphi / eta);
	    if(a2 > H) a2 = H;
	    else if(a2 < L) a2 = L;
	  } else {
	    double Lobj = -L*deltaphi;
	    double Hobj = -H*deltaphi;
	    if(Lobj > Hobj)
	      a2 = L;
	    else
	      a2 = H;
	  }
	  a1 = alpha1 - (a2 - alpha2);
	  // update alpha1, alpha2 if change is larger than some eps
	  if(java.lang.Math.abs(a1-alpha1) > m_eps || 
	     java.lang.Math.abs(a2-alpha2) > m_eps){
	    alpha1 = a1;
	    alpha2 = a2;
	    changed = true;
	  }
	} else {
	  finished = true;
	}
	case1 = true;
	    
      } else if(!case2 && 
		(alpha1 > 0 || (alpha1_ == 0 && deltaphi > 2 * m_epsilon)) &&
		(alpha2_ > 0 || (alpha2 == 0 && deltaphi > 2 * m_epsilon)) ){
		
	// compute L, H (wrt alpha1, alpha2_)
	L = java.lang.Math.max(0, -gamma);
	H = java.lang.Math.min(m_C * m_data.instance(i2).weight(), -gamma + m_C*m_data.instance(i1).weight());

	if(L < H){
	  if(eta > 0){
	    a2 = alpha2_ + ((deltaphi - 2*m_epsilon) / eta);
	    if(a2 > H) a2 = H;
	    else if(a2 < L) a2 = L;
	  } else {
	    double Lobj = L*(-2*m_epsilon + deltaphi);
	    double Hobj = H*(-2*m_epsilon + deltaphi);
	    if(Lobj > Hobj)
	      a2 = L;
	    else
	      a2 = H;
	  }
	  a1 = alpha1 + (a2 - alpha2_);
	  // update alpha1, alpha2_ if change is larger than some eps
	  if(java.lang.Math.abs(a1-alpha1) > m_eps || 
	     java.lang.Math.abs(a2-alpha2_) > m_eps){
	    alpha1 = a1;
	    alpha2_ = a2;
	    changed = true;
	  }
	} else {
	  finished = true;
	}
	case2 = true;

      } else if(!case3 && 
		(alpha1_ > 0 || (alpha1 == 0 && deltaphi < -2 * m_epsilon)) &&
		(alpha2 > 0 || (alpha2_ == 0 && deltaphi < -2 * m_epsilon)) ){
		
	// compute L, H (wrt alpha1_, alpha2)
	L = java.lang.Math.max(0, gamma);
	H = java.lang.Math.min(m_C * m_data.instance(i2).weight(), m_C * m_data.instance(i1).weight() + gamma);

	if(L < H){
	  if(eta > 0){
	    a2 = alpha2 - ((deltaphi + 2*m_epsilon) / eta);
	    if(a2 > H) a2 = H;
	    else if(a2 < L) a2 = L;
	  } else {
	    double Lobj = -L*(2*m_epsilon + deltaphi);
	    double Hobj = -H*(2*m_epsilon + deltaphi);
	    if(Lobj > Hobj)
	      a2 = L;
	    else
	      a2 = H;
	  }
	  a1 = alpha1_ + (a2 - alpha2);
	  // update alpha1_, alpha2 if change is larger than some eps
	  if(java.lang.Math.abs(a1-alpha1_) > m_eps || 
	     java.lang.Math.abs(a2-alpha2) > m_eps){
	    alpha1_ = a1;
	    alpha2 = a2;
	    changed = true;
	  }
	} else {
	  finished = true;
	}
	case3 = true;

      } else if(!case4 && 
		(alpha1_ > 0 || (alpha1 == 0 && deltaphi < 0)) &&
		(alpha2_ > 0 || (alpha2 == 0 && deltaphi > 0)) ){
		
	// compute L, H (wrt alpha1_, alpha2_)
	L = java.lang.Math.max(0, -gamma - m_C * m_data.instance(i1).weight());
	H = java.lang.Math.min(m_C * m_data.instance(i2).weight(), -gamma);

	if(L < H){
	  if(eta > 0){
	    a2 = alpha2_ + deltaphi / eta;
	    if(a2 > H) a2 = H;
	    else if(a2 < L) a2 = L;
	  } else {
	    double Lobj = L*deltaphi;
	    double Hobj = H*deltaphi;
	    if(Lobj > Hobj)
	      a2 = L;
	    else
	      a2 = H;
	  }
	  a1 = alpha1_ - (a2 - alpha2_);
	  // update alpha1_, alpha2_ if change is larger than some eps
	  if(java.lang.Math.abs(a1-alpha1_) > m_eps || 
	     java.lang.Math.abs(a2-alpha2_) > m_eps){
	    alpha1_ = a1;
	    alpha2_ = a2;	
	    changed = true;
	  }
	} else {
	  finished = true;
	}
	case4 = true;
      } else {
	finished = true;
      }
	    
      // update deltaphi
      deltaphi += eta * ((alpha2 - alpha2_) - (m_alpha[i2] - m_alpha_[i2]));
    }
	
    if(changed){

      // update f-cache[i] for i in I_0 using new Lagrange multipliers
      for (int i = m_I0.getNext(-1); i != -1; i = m_I0.getNext(i)) {
	if (i != i1 && i != i2){
	  m_fcache[i] += 
	    ((m_alpha[i1] - m_alpha_[i1]) - (alpha1 - alpha1_)) * m_kernel.eval(i1, i, m_data.instance(i1)) +
	    ((m_alpha[i2] - m_alpha_[i2]) - (alpha2 - alpha2_)) * m_kernel.eval(i2, i, m_data.instance(i2));
	}
      }
	    
      // update f-cache[i1] and f-cache[i2]
      m_fcache[i1] += 
	((m_alpha[i1] - m_alpha_[i1]) - (alpha1 - alpha1_)) * k11 +
	((m_alpha[i2] - m_alpha_[i2]) - (alpha2 - alpha2_)) * k12;
      m_fcache[i2] += 
	((m_alpha[i1] - m_alpha_[i1]) - (alpha1 - alpha1_)) * k12 +
	((m_alpha[i2] - m_alpha_[i2]) - (alpha2 - alpha2_)) * k22;

      // to prevent precision problems
      if(alpha1 > m_C * m_data.instance(i1).weight() - m_Del * m_C * m_data.instance(i1).weight()){
	alpha1 = m_C * m_data.instance(i1).weight();
      } else if (alpha1 <= m_Del * m_C * m_data.instance(i1).weight()){
	alpha1 = 0;
      }
      if(alpha1_ > m_C * m_data.instance(i1).weight() - m_Del * m_C * m_data.instance(i1).weight()){
	alpha1_ = m_C * m_data.instance(i1).weight();
      } else if (alpha1_ <= m_Del * m_C * m_data.instance(i1).weight()){
	alpha1_ = 0;
      }
      if(alpha2 > m_C * m_data.instance(i2).weight() - m_Del * m_C * m_data.instance(i2).weight()){
	alpha2 = m_C * m_data.instance(i2).weight();
      } else if (alpha2 <= m_Del * m_C * m_data.instance(i2).weight()){
	alpha2 = 0;
      }
      if(alpha2_ > m_C * m_data.instance(i2).weight() - m_Del * m_C * m_data.instance(i2).weight()){
	alpha2_ = m_C * m_data.instance(i2).weight();
      } else if (alpha2_ <= m_Del * m_C * m_data.instance(i2).weight()){
	alpha2_ = 0;
      }
	
      // Store the changes in alpha, alpha' array
      m_alpha[i1] = alpha1;
      m_alpha_[i1] = alpha1_;
      m_alpha[i2] = alpha2;
      m_alpha_[i2] = alpha2_;

      // update I_0, I_1, I_2, I_3
      if((0 < alpha1 && alpha1 < m_C * m_data.instance(i1).weight()) ||
	 (0 < alpha1_ && alpha1_ < m_C * m_data.instance(i1).weight())){
	m_I0.insert(i1);
      } else { 
	m_I0.delete(i1);
      }
      if((alpha1 == 0 && alpha1_ == 0)){
	m_I1.insert(i1);
      } else { 
	m_I1.delete(i1);
      }
      if((alpha1 == 0 && alpha1_ == m_C * m_data.instance(i1).weight())){
	m_I2.insert(i1);
      } else { 
	m_I2.delete(i1);
      }
      if((alpha1 == m_C * m_data.instance(i1).weight() && alpha1_ == 0)){
	m_I3.insert(i1);
      } else { 
	m_I3.delete(i1);
      }
      if((0 < alpha2 && alpha2 < m_C * m_data.instance(i2).weight()) ||
	 (0 < alpha2_ && alpha2_ < m_C * m_data.instance(i2).weight())){
	m_I0.insert(i2);
      } else { 
	m_I0.delete(i2);
      }
      if((alpha2 == 0 && alpha2_ == 0)){
	m_I1.insert(i2);
      } else { 
	m_I1.delete(i2);
      }
      if((alpha2 == 0 && alpha2_ == m_C * m_data.instance(i2).weight())){
	m_I2.insert(i2);
      } else { 
	m_I2.delete(i2);
      }
      if((alpha2 == m_C * m_data.instance(i2).weight() && alpha2_ == 0)){
	m_I3.insert(i2);
      } else { 
	m_I3.delete(i2);
      }

      // for debuggage
      // checkSets();
      // checkAlphas();

      // Compute (i_low, b_low) and (i_up, b_up) by applying the conditions
      // mentionned above, using only i1, i2 and indices in I_0
      m_bLow = -Double.MAX_VALUE; m_bUp = Double.MAX_VALUE;
      m_iLow =-1; m_iUp = -1;
      for (int i = m_I0.getNext(-1); i != -1; i = m_I0.getNext(i)) {
	if(0 < m_alpha_[i] && m_alpha_[i] < m_C * m_data.instance(i).weight() && 
	   (m_fcache[i] + m_epsilon > m_bLow)){
	  m_bLow = m_fcache[i] + m_epsilon; m_iLow = i;
	} else if(0 < m_alpha[i] && m_alpha[i] < m_C * m_data.instance(i).weight() && 
		  (m_fcache[i] - m_epsilon > m_bLow)){
	  m_bLow = m_fcache[i] - m_epsilon; m_iLow = i;
	}
	if(0 < m_alpha[i] && m_alpha[i] < m_C * m_data.instance(i).weight() && 
	   (m_fcache[i] - m_epsilon < m_bUp)){
	  m_bUp = m_fcache[i] - m_epsilon; m_iUp = i;
	} else if(0 < m_alpha_[i] && m_alpha_[i] < m_C * m_data.instance(i).weight() && 
		  (m_fcache[i] + m_epsilon < m_bUp)){		    
	  m_bUp = m_fcache[i] + m_epsilon; m_iUp = i;
	}
      }

      if(!m_I0.contains(i1)){
	if(m_I2.contains(i1) && 
	   (m_fcache[i1] + m_epsilon > m_bLow)){
	  m_bLow = m_fcache[i1] + m_epsilon; m_iLow = i1;
	} else if (m_I1.contains(i1) && 
		   (m_fcache[i1] - m_epsilon > m_bLow)){
	  m_bLow = m_fcache[i1] - m_epsilon; m_iLow = i1;
	}
	if(m_I3.contains(i1) && 
	   (m_fcache[i1] - m_epsilon < m_bUp)){
	  m_bUp = m_fcache[i1] - m_epsilon; m_iUp = i1;
	} else if (m_I1.contains(i1) && 
		   (m_fcache[i1] + m_epsilon < m_bUp)){
	  m_bUp = m_fcache[i1] + m_epsilon; m_iUp = i1;
	}
      }
	    
      if(!m_I0.contains(i2)){
	if(m_I2.contains(i2) && 
	   (m_fcache[i2] + m_epsilon > m_bLow)){
	  m_bLow = m_fcache[i2] + m_epsilon; m_iLow = i2;
	} else if (m_I1.contains(i2) && 
		   (m_fcache[i2] - m_epsilon > m_bLow)){
	  m_bLow = m_fcache[i2] - m_epsilon; m_iLow = i2;
	}
	if(m_I3.contains(i2) && 
	   (m_fcache[i2] - m_epsilon < m_bUp)){
	  m_bUp = m_fcache[i2] - m_epsilon; m_iUp = i2;
	} else if (m_I1.contains(i2) && 
		   (m_fcache[i2] + m_epsilon < m_bUp)){
	  m_bUp = m_fcache[i2] + m_epsilon; m_iUp = i2;
	}
      }
      if(m_iLow == -1 || m_iUp == -1){
	throw new RuntimeException("Fatal error! The program failled to "
				   + "initialize i_Low, iUp.");
      }
      return true;
    } else {
      return false;
    }    
  }


  /**
   * Classifies a given instance.
   *
   * @param instance the instance to be classified
   * @return the classification
   * @exception Exception if instance could not be classified
   * successfully
   */
  public double classifyInstance(Instance inst) throws Exception {

    // Filter instance
    if (!m_checksTurnedOff) {
      m_Missing.input(inst);
      m_Missing.batchFinished();
      inst = m_Missing.output();
    }

    if (!m_onlyNumeric) {
      m_NominalToBinary.input(inst);
      m_NominalToBinary.batchFinished();
      inst = m_NominalToBinary.output();
    }
	
    if (m_Filter != null) {
      m_Filter.input(inst);
      m_Filter.batchFinished();
      inst = m_Filter.output();
    }

    // classification :

    double result = m_b;

    // Is the machine linear?
    if (!m_useRBF && m_exponent == 1.0) {
	
      // Is weight vector stored in sparse format?
      if (m_sparseWeights == null) {
	int n1 = inst.numValues(); 
	for (int p = 0; p < n1; p++) {
	  if (inst.index(p) != m_classIndex) {
	    result += m_weights[inst.index(p)] * inst.valueSparse(p);
	  }
	}
      } else {
	int n1 = inst.numValues(); int n2 = m_sparseWeights.length;
	for (int p1 = 0, p2 = 0; p1 < n1 && p2 < n2;) {
	  int ind1 = inst.index(p1); 
	  int ind2 = m_sparseIndices[p2];
	  if (ind1 == ind2) {
	    if (ind1 != m_classIndex) {
	      result += inst.valueSparse(p1) * m_sparseWeights[p2];
	    }
	    p1++; p2++;
	  } else if (ind1 > ind2) {
	    p2++;
	  } else { 
	    p1++;
	  }
	}
      }
    } else {
      for (int i = 0; i < m_alpha.length; i++) { 
	result += (m_alpha[i] - m_alpha_[i]) * m_kernel.eval(-1, i, inst);
      }
    }

    // apply the inverse transformation 
    // (due to the normalization/standardization)
    return (result - m_Blin) / m_Alin;
  }