rule.java

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

   */
  private SimpleLinkedList refine(Predicate pred, int firstIndex, int lastIndex, 
				 boolean addToBody, boolean addToHead) {

    SimpleLinkedList result = new SimpleLinkedList();
    Literal currentLit;
    Literal negation;
    Rule refinement;
    for (int i = firstIndex; i < lastIndex; i++) {
      currentLit = pred.getLiteral(i);
      if (addToBody) {
	refinement = addTermToBody(currentLit);
	if (refinement != null) {
	  result.add(refinement);
	}
      }
      if (addToHead) {
	refinement = addTermToHead(currentLit);
	if (refinement != null) {
	  result.add(refinement);
	}
      }
      negation = currentLit.getNegation();
      if (negation != null) {
	if (addToBody) {
	  refinement = addTermToBody(negation);
	  if (refinement != null) {
	    result.add(refinement);
	  }
	}
	if (addToHead) {
	  refinement = addTermToHead(negation);
	  if (refinement != null) {
	    result.add(refinement);
	  }
	}
      }
    }
    return result;
  }

  /**
   * Refine a rule by adding literal from a set of predictes.
   * 
   * @param predicates The predicates available.
   * @return The list of the children obtained by refining the rule.
   */
  public SimpleLinkedList refine(ArrayList predicates) {

    SimpleLinkedList result = new SimpleLinkedList();
    Predicate currentPred;
    boolean addToBody;
    boolean addToHead;

    if (this.numLiterals() == m_maxLiterals) {
      return result;
    }

    if (this.isEmpty()) {
      /* Literals can be added on both sides of the rule. */
      for (int i = 0; i < predicates.size(); i++) {
	currentPred = (Predicate) predicates.get(i);
	result.addAll(refine(currentPred,
			     0, currentPred.numLiterals(),
			     true, true));
      }
    } else if (m_body.isEmpty() || m_head.isEmpty()) {
      /* Literals can be added to the empty side only. */
      LiteralSet side;
      Literal last;
      if (m_body.isEmpty()) {
	side = m_head;
	addToBody = true;
	addToHead = false;
      } else { // m_head.isEmpty()
	side = m_body;
	addToBody = false;
	addToHead = true;
      }
      last = side.getLastLiteral();
      currentPred = last.getPredicate();
      if (m_repeatPredicate) {
	result.addAll(refine(currentPred,
			     currentPred.indexOf(last) + 1, 
			     currentPred.numLiterals(),
			     addToBody, addToHead));
      }
      for (int i = predicates.indexOf(currentPred) + 1; i < predicates.size(); 
	   i++) {
	currentPred = (Predicate) predicates.get(i);
	result.addAll(refine(currentPred,
			     0, currentPred.numLiterals(),
			     addToBody, addToHead));		
      }
    } else {
      Literal lastLitBody = m_body.getLastLiteral();
      Literal lastLitHead = m_head.getLastLiteral();
      Predicate lastPredBody = lastLitBody.getPredicate();
      Predicate lastPredHead = lastLitHead.getPredicate();
      int lastLitBodyIndex = lastPredBody.indexOf(lastLitBody);
      int lastLitHeadIndex = lastPredHead.indexOf(lastLitHead);
      int lastPredBodyIndex = predicates.indexOf(lastPredBody);
      int lastPredHeadIndex = predicates.indexOf(lastPredHead);
      Predicate inferiorPred;
      Predicate superiorPred;
      int inferiorLit;
      int superiorLit;
      addToBody = (m_head.numLiterals() == 1
		   && (lastPredBodyIndex < lastPredHeadIndex 
		       || (lastPredBodyIndex == lastPredHeadIndex 
			   && lastLitBodyIndex < lastLitHeadIndex)));
      addToHead = (m_body.numLiterals() == 1
		   && (lastPredHeadIndex < lastPredBodyIndex
		       || (lastPredHeadIndex == lastPredBodyIndex
			   && lastLitHeadIndex < lastLitBodyIndex)));      
      if (addToBody || addToHead) {
	/* Add literals in the gap between the body and the head. */
	if (addToBody) {
	  inferiorPred = lastPredBody;
	  inferiorLit = lastLitBodyIndex;
	  superiorPred = lastPredHead;
	  superiorLit = lastLitHeadIndex;
	} else { // addToHead
	  inferiorPred = lastPredHead;
	  inferiorLit = lastLitHeadIndex;
	  superiorPred = lastPredBody;
	  superiorLit = lastLitBodyIndex;
	}
	if (predicates.indexOf(inferiorPred) 
	    < predicates.indexOf(superiorPred)) {
	  if (m_repeatPredicate) {
	    result.addAll(refine(inferiorPred, 
				 inferiorLit + 1, inferiorPred.numLiterals(),
				 addToBody, addToHead));
	  }
	  for (int j = predicates.indexOf(inferiorPred) + 1; 
	       j < predicates.indexOf(superiorPred); j++) {
	    currentPred = (Predicate) predicates.get(j);
	    result.addAll(refine(currentPred,
				 0, currentPred.numLiterals(),
				 addToBody, addToHead));
	  }
	  if (m_repeatPredicate) {
	    result.addAll(refine(superiorPred,
				 0, superiorLit,
				 addToBody, addToHead));
	  }
	} else { 
	  //((inferiorPred.getIndex() == superiorPred.getIndex())
	  //&& (inferiorLit < superiorLit))
	  if (m_repeatPredicate) {
	    result.addAll(refine(inferiorPred,
				 inferiorLit + 1, superiorLit,
				 addToBody, addToHead));
	  }
	}	
      }	
      /* Add other literals. */
      if (predicates.indexOf(lastPredBody) > predicates.indexOf(lastPredHead)) {
	superiorPred = lastPredBody;
	superiorLit = lastPredBody.indexOf(lastLitBody);
      } else if (predicates.indexOf(lastPredBody) 
		 < predicates.indexOf(lastPredHead)) {
	superiorPred = lastPredHead;
	superiorLit = lastPredHead.indexOf(lastLitHead);
      } else {
	superiorPred = lastPredBody;
	if (lastLitBodyIndex > lastLitHeadIndex) {
	  superiorLit = lastPredBody.indexOf(lastLitBody);
	} else {
	  superiorLit = lastPredHead.indexOf(lastLitHead);
	}
      }
      if (m_repeatPredicate) {
	result.addAll(refine(superiorPred,
			     superiorLit + 1, superiorPred.numLiterals(),
			     true, true));
      }
      for (int j = predicates.indexOf(superiorPred) + 1; j < predicates.size(); 
	   j++) {
	currentPred = (Predicate) predicates.get(j);
	result.addAll(refine(currentPred,
			     0, currentPred.numLiterals(),
			     true, true));
      }
    }
    return result;
  }

  /**
   * Test if this rule subsumes another rule.
   *
   * @param otherRule The other rule.
   * @return True if the other rule is subsumed.
   */
  public boolean subsumes(Rule otherRule) {    

    if (this.numLiterals() > otherRule.numLiterals()) {
      return false;
    }
    return (m_body.isIncludedIn(otherRule) && m_head.isIncludedIn(otherRule));
  }

  /**
   * Test if this rule and another rule correspond to the same clause.
   *
   * @param otherRule The other rule.
   * @return True if both rules correspond to the same clause.
   */
  public boolean sameClauseAs(Rule otherRule) {

    return (this.numLiterals() == otherRule.numLiterals()
	    && this.subsumes(otherRule));
  }

  /**
   * Test if this rule is equivalent to another rule.
   *
   * @param otherRule The other rule.
   * @return True if both rules are equivalent.
   */
  public boolean equivalentTo(Rule otherRule) {

    return (this.numLiterals() == otherRule.numLiterals()
	    && m_head.negationIncludedIn(otherRule.m_body)
	    && m_body.negationIncludedIn(otherRule.m_head));
  }

  /**
   * Test if the body of the rule contains a literal.
   * 
   * @param lit The literal to look for.
   * @return True if the literal is contained in the body of the rule.
   */
  public boolean bodyContains(Literal lit) {

    return m_body.contains(lit);
  }

  /**
   * Test if the head of the rule contains a literal.
   * 
   * @param lit The literal to look for.
   * @return True if the literal is contained in the head of the rule.
   */
  public boolean headContains(Literal lit) {

    return m_head.contains(lit);
  }

  /**
   * Test if this rule is over the frequency threshold.
   *
   * @param minFrequency The frequency threshold.
   * @return True if the rule is over the threshold.
   */
  public boolean overFrequencyThreshold(double minFrequency) {

    return (m_body.overFrequencyThreshold(minFrequency) 
	    && m_head.overFrequencyThreshold(minFrequency));
  }

  /**
   * Test if the body of the rule is true.
   *
   * @return True if the body is always satisfied.
   */
  public boolean hasTrueBody() {

    return (!m_body.isEmpty()
	    && m_body.hasMaxCounterInstances());
  }

  /**
   * Test if the head of the rule is false.
   *
   * @return True if the body is never satisfied.
   */
  public boolean hasFalseHead() {

    return (!m_head.isEmpty()
	    && m_head.hasMaxCounterInstances());
  }

  /**
   * Return a String giving the confirmation and optimistic estimate of 
   * this rule.
   * 
   * @return A String with the values of the rule.
   */
  public String valuesToString() {

    StringBuffer text = new StringBuffer();
    DecimalFormat decimalFormat = new DecimalFormat("0.000000");
    text.append(decimalFormat.format(getConfirmation()));
    text.append(" ");
    text.append(decimalFormat.format(getObservedFrequency()));
    return text.toString();
  }

  /**
   * Return a String giving the TP-rate and FP-rate of 
   * this rule.
   * 
   * @return A String with the values of the rule.
   */
  public String rocToString() {

    StringBuffer text = new StringBuffer();
    DecimalFormat decimalFormat = new DecimalFormat("0.000000");
    text.append(decimalFormat.format(getConfirmation()));
    text.append(" ");
    text.append(decimalFormat.format(getTPRate()));
    text.append(" ");
    text.append(decimalFormat.format(getFPRate()));
    return text.toString();
  }

  /**
   * Retrun a String for this rule.
   *
   * @return The String describing this rule.
   */
  public String toString() {

    StringBuffer text = new StringBuffer();
    text.append(m_body.toString());
    text.append(" ==> ");
    text.append(m_head.toString());
    return text.toString();
  }

  /**
   * Comparator used to compare two rules according to their confirmation value.
   */
  public static Comparator confirmationComparator = new Comparator() {

      public int compare(Object o1, Object o2) {

	Rule r1 = (Rule) o1;
	Rule r2 = (Rule) o2;
	double conf1 = r1.getConfirmation();
	double conf2 = r2.getConfirmation();
	if (conf1 > conf2) {
	  return -1;
	} else if (conf1 < conf2) {
	  return 1;
	} else {
	  return 0;
	}
      }
    };

  /**
   * Comparator used to compare two rules according to their observed number
   * of counter-instances.
   */
  public static Comparator observedComparator = new Comparator() {

      public int compare(Object o1, Object o2) {

	Rule r1 = (Rule) o1;
	Rule r2 = (Rule) o2;
	double obs1 = r1.getObservedFrequency();
	double obs2 = r2.getObservedFrequency();
	if (obs1 < obs2) {
	  return -1;
	} else if (obs1 > obs2) {
	  return 1;
	} else {
	  return 0;
	}
      }
    };

  /**
   * Comparator used to compare two rules according to their optimistic estimate.
   */
  public static Comparator optimisticComparator = new Comparator() {

      public int compare(Object o1, Object o2) {

	Rule r1 = (Rule) o1;
	Rule r2 = (Rule) o2;
	double opt1 = r1.getOptimistic();
	double opt2 = r2.getOptimistic();
	if (opt1 > opt2) {
	  return -1;
	} else if (opt1 < opt2) {
	  return 1;
	} else {
	  return 0;
	}
      }
    };

  /**
   * Comparator used to compare two rules according to their confirmation and 
   * then their observed number of counter-instances.
   */
  public static Comparator confirmationThenObservedComparator 
    = new Comparator() {
	public int compare(Object o1, Object o2) {

	  int confirmationComparison = confirmationComparator.compare(o1, o2);
	  if (confirmationComparison != 0) {
	    return confirmationComparison;
	  } else {
	    return observedComparator.compare(o1, o2);
	  }
	}
      };
  
  /**
   * Comparator used to compare two rules according to their optimistic estimate
   * and then their observed number of counter-instances.
   */
  public static Comparator optimisticThenObservedComparator = new Comparator() {
      public int compare(Object o1, Object o2) {
	int optimisticComparison = optimisticComparator.compare(o1, o2);
	if (optimisticComparison != 0) {
	  return optimisticComparison;
	} else {
	  return observedComparator.compare(o1, o2);
	}
      }
    };
}