rule.java

一个数据挖掘软件ALPHAMINERR的整个过程的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.
 */

/*
 *    Rule.java
 *    Copyright (C) 2003 Peter A. Flach, Nicolas Lachiche
 *
 *    Thanks to Amelie Deltour for porting the original C code to Java
 *    and integrating it into Weka.
 */

package weka.associations.tertius;

import java.io.Serializable;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Enumeration;

import weka.core.Instance;
import weka.core.Instances;

/**
 * Class representing a rule with a body and a head.
 *
 * @author  <a href="mailto:[e-mail]">Am閘ie Deltour</a>
 */

public class Rule implements Serializable, Cloneable {

  /** The body of the rule. */
  private Body m_body;

  /** The head of the rule. */
  private Head m_head;

  /** Can repeat predicates in the rule ? */
  private boolean m_repeatPredicate;

  /** Maximal number of literals in the rule. */
  private int m_maxLiterals;

  /** Can there be negations in the body ? */
  private boolean m_negBody;
  
  /** Can there be negations in the head ? */
  private boolean m_negHead;

  /** Is this rule a classification rule ? */
  private boolean m_classRule;

  /** Can there be only one literal in the head ? */
  private boolean m_singleHead;

  /** Number of instances in the data this rule deals with. */
  private int m_numInstances;

  /** Set of counter-instances of this rule. */
  private ArrayList m_counterInstances;

  /** Counter for the counter-instances of this rule. */
  private int m_counter;

  /** Confirmation of this rule. */
  private double m_confirmation;

  /** Optimistic estimate of this rule. */
  private double m_optimistic;

  /**
   * Constructor for a rule when the counter-instances are not stored,
   * giving all the constraints applied to this rule.
   * 
   * @param repeatPredicate True if predicates can be repeated.
   * @param maxLiterals Maximum number of literals.
   * @param negBody True if negation is allowed in the body.
   * @param negHead True if negation is allowed in the head. 
   * @param classRule True if the rule is a classification rule.
   * @param horn True if the rule is a horn clause.
   */
  public Rule(boolean repeatPredicate, int maxLiterals, boolean negBody, 
	      boolean negHead, boolean classRule, boolean horn) {

    m_body = new Body();
    m_head = new Head();
    m_repeatPredicate = repeatPredicate;
    m_maxLiterals = maxLiterals;
    m_negBody = negBody && !horn;
    m_negHead = negHead && !horn;
    m_classRule = classRule;
    m_singleHead = classRule || horn;
  }
    
  /**
   * Constructor for a rule when the counter-instances are stored,
   * giving all the constraints applied to this rule.
   * The counter-instances are initialized to all the instances in the dataset.
   * 
   * @param instances The dataset.
   * @param repeatPredicate True if predicates can be repeated.
   * @param maxLiterals Maximum number of literals.
   * @param negBody True if negation is allowed in the body.
   * @param negHead True if negation is allowed in the head. 
   * @param classRule True if the rule is a classification rule.
   * @param horn True if the rule is a horn clause.
   */
  public Rule(Instances instances,
	      boolean repeatPredicate, int maxLiterals, boolean negBody, 
	      boolean negHead, boolean classRule, boolean horn) {

    m_body = new Body(instances);
    m_head = new Head(instances);
    m_repeatPredicate = repeatPredicate;
    m_maxLiterals = maxLiterals;
    m_negBody = negBody && !horn;
    m_negHead = negHead && !horn;
    m_classRule = classRule;
    m_singleHead = classRule || horn;
    m_numInstances = instances.numInstances();
    m_counterInstances = new ArrayList(m_numInstances);
    Enumeration em = instances.emerateInstances();
    while (em.hasMoreElements()) {
      m_counterInstances.add(em.nextElement());
    }
  }

  /**
   * Returns a shallow copy of this rule.
   * The structured is copied but the literals themselves are not copied.
   *
   * @return A copy of this Rule.
   */
  public Object clone() {

    Object result = null;
    try {
      result = super.clone();
      /* Clone the body and the head. */
      ((Rule) result).m_body = (Body) m_body.clone();
      ((Rule) result).m_head = (Head) m_head.clone();
      /* Clone the set of counter-instances. */
      if (m_counterInstances != null) {
	((Rule) result).m_counterInstances
	  = (ArrayList) m_counterInstances.clone();
      }
    } catch (Exception e) {
      /* An exception is not supposed to happen here. */
      e.printStackTrace();
      System.exit(0);
    }
    return result;
  }

  /**
   * Test if an instance is a counter-instance of this rule.
   * 
   * @param instance The instance to test.
   * @return True if the instance is a counter-instance.
   */
  public boolean counterInstance(Instance instance) {

    return ((m_body.counterInstance(instance) 
	     && m_head.counterInstance(instance)));
  }

  /**
   * Update the number of counter-instances of this rule in the dataset.
   * This method should be used is the rule does not store its counter-instances.
   *
   * @param instances The dataset.
   */
  public void upDate(Instances instances) {

    Enumeration em = instances.emerateInstances();
    m_numInstances = instances.numInstances();
    m_counter = 0;
    while (em.hasMoreElements()) {
      if (this.counterInstance((Instance) em.nextElement())) {
	m_counter++;
      }
    }
    m_head.upDate(instances);
    m_body.upDate(instances);
  }

  /**
   * Get the confirmation value of this rule.
   *
   * @return The confirmation.
   */
  public double getConfirmation() {

    return m_confirmation;
  }

  /**
   * Get the optimistic estimate of the confirmation obtained by refining
   * this rule.
   * 
   * @return The optimistic estimate.
   */
  public double getOptimistic() {

    return m_optimistic;
  }

  /*
   * Get the expected number of counter-instances of this rule,
   * calculated from the number of instances satisfying the body and
   * the number of instances satisfying the negation of the head.
   *
   * @return The expected number of counter-instances.
   */
  public double getExpectedNumber() {

    return (double) m_body.getCounterInstancesNumber() 
      * (double) m_head.getCounterInstancesNumber() 
      / (double) m_numInstances;
  }

  /**
   * Get the expected frequency of counter-instances of this rule.
   *
   * @return The expected frequency of counter-instances.
   */
  public double getExpectedFrequency() {

    return getExpectedNumber() / (double) m_numInstances;
  }

  /**
   * Get the observed number of counter-instances of this rule in the dataset.
   *
   * @return The observed number of counter-instances.
   */
  public int getObservedNumber() {

    if (m_counterInstances != null) {
      return m_counterInstances.size();
    } else {
      return m_counter;
    }
  }

  /**
   * Get the observed frequency of counter-instances of this rule in the dataset.
   * 
   * @return The expected frequency of counter-instances.
   */
  public double getObservedFrequency() {

    return (double) getObservedNumber() / (double) m_numInstances;
  }

  /**
   * Get the rate of True Positive instances of this rule.
   *
   * @return The TP-rate.
   */
  public double getTPRate() {

    int tp = m_body.getCounterInstancesNumber() - getObservedNumber();
    int fn = m_numInstances - m_head.getCounterInstancesNumber() - tp;
    return ((double) tp / (double) (tp + fn));
  }

  /**
   * Get the rate of False Positive instances of this rule.
   *
   * @return The FP-rate.
   */
  public double getFPRate() {

    int fp = getObservedNumber();
    int tn = m_head.getCounterInstancesNumber() - fp;
    return ((double) fp / (double) (fp + tn));
  }

  /**
   * Calculate the confirmation of this rule.
   */
  public void calculateConfirmation() {

    double expected = getExpectedFrequency();
    double observed = getObservedFrequency();
    if ((expected == 0) || (expected == 1)) {
      m_confirmation = 0;
    } else {
      m_confirmation = (expected - observed) / (Math.sqrt(expected) - expected);
    }
  }

  /**
   * Calculate the optimistic estimate of this rule.
   */
  public void calculateOptimistic() {

    int counterInstances = this.getObservedNumber();
    int body = m_body.getCounterInstancesNumber();
    int notHead = m_head.getCounterInstancesNumber();
    int n = m_numInstances;
    double expectedOptimistic;
    /* optimistic expected number of counter-instances */
    if (counterInstances <= body - notHead) {
      expectedOptimistic = (double) (notHead * (body - counterInstances)) 
	/ (double) (n * n);
    } else if (counterInstances <= notHead - body) {
      expectedOptimistic = (double) (body * (notHead - counterInstances)) 
	/ (double) (n * n);
    } else {
      expectedOptimistic = (double) ((notHead + body - counterInstances)
				     * (notHead + body - counterInstances)) 
	/ (double) (4 * n * n);
    }
    if ((expectedOptimistic == 0) || (expectedOptimistic == 1)) {
      m_optimistic = 0;
    } else {
      m_optimistic = expectedOptimistic 
	/ (Math.sqrt(expectedOptimistic) - expectedOptimistic);
    }
  }

  /**
   * Test if this rule is empty.
   * 
   * @return True if it is the empty rule.
   */
  public boolean isEmpty() {

    return (m_head.isEmpty() && m_body.isEmpty());
  }

  /**
   * Give the number of literals in this rule.
   * 
   * @return The number of literals.
   */
  public int numLiterals() {

    return m_body.numLiterals() + m_head.numLiterals();
  }

  /**
   * Add a literal to the body of the rule.
   *
   * @param newLit The literal to add.
   * @return The rule obtained by adding the literal, null if the literal can
   * not be added because of the constraints on the rule.
   */
  private Rule addTermToBody(Literal newLit) {

    if (!m_negBody && newLit.negative()
     	|| (m_classRule && newLit.getPredicate().isClass())
	|| (newLit instanceof IndividualLiteral
	    && (((IndividualLiteral) newLit).getType() 
		- m_body.getType()) > 1
	    && (((IndividualLiteral) newLit).getType() 
		- m_head.getType()) > 1)) {
      return null;
    } else {
      Rule result = (Rule) this.clone();
      result.m_body.addElement(newLit);
      /* Update the counter-instances. */
      if (m_counterInstances != null) {
	for (int i = result.m_counterInstances.size() - 1; i >= 0; i--) {
	  Instance current = (Instance) result.m_counterInstances.get(i);
	  if (!result.m_body.canKeep(current, newLit)) {
	    result.m_counterInstances.remove(i);
	  }
	}
      }
      return result;
    }
  }

  /**
   * Add a literal to the head of the rule.
   *
   * @param newLit The literal to add.
   * @return The rule obtained by adding the literal, null if the literal can
   * not be added because of the constraints on the rule.
   */
  private Rule addTermToHead(Literal newLit) {
    if ((!m_negHead && newLit.negative())
     	|| (m_classRule && !newLit.getPredicate().isClass()) 
     	|| (m_singleHead && !m_head.isEmpty())
	|| (newLit instanceof IndividualLiteral
	    && ((IndividualLiteral) newLit).getType() 
	    != IndividualLiteral.INDIVIDUAL_PROPERTY)) {
      return null;
    } else { 
      Rule result = (Rule) this.clone();
      result.m_head.addElement(newLit);
      /* Update counter-instances. */
      if (m_counterInstances != null) {
	for (int i = result.m_counterInstances.size() - 1; i >= 0; i--) {
	  Instance current = (Instance) result.m_counterInstances.get(i);
	  if (!result.m_head.canKeep(current, newLit)) {
	    result.m_counterInstances.remove(i);
	  }
	}
      }
      return result;
    }
  }

  /**
   * Refine a rule by adding a range of literals of a predicate, either to
   * the head or to the body of the rule.
   * 
   * @param pred The predicate to consider.
   * @param firstIndex The index of the first literal of the predicate to add.
   * @param lastIndex The index of the last literal of the predicate to add.
   * @param addTobody True if the literals should be added to the body.
   * @param addToHead True if the literals should be added to the head.
   * @return A list of rules obtained by refinement.
   */