tertius.java

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

      return false;
    }
    return true;
  }

  /**
   * Test if a rule can be explored (if it is interesting for the results 
   * or for refining).
   *
   * @param rule The rule to consider.
   * @return True if the rule can be explored, false otherwise.
   */
  private boolean canExplore(Rule rule) {
    if (rule.getOptimistic() < m_confirmationThreshold) {
      return false;
    }
    if (m_best != 0) {
      if (numValuesInResult() < m_best) {
	return true;
      }	
      Rule worstResult = (Rule) m_results.getLast();
      if (rule.getOptimistic() >= worstResult.getConfirmation()) {
	return true;
      }
      return false;      
    } else {
      return true;
    }
  }    

  /**
   * Test if a rule can be stored in the agenda.
   *
   * @param rule The rule to consider.
   * @return True if the rule can be stored, false otherwise.
   */
  private boolean canStoreInNodes(Rule rule) {
    if (rule.getObservedNumber() == 0) {
      return false;
    }
    return true;
  }

  /**
   * Test if it is worth calculating the confirmation of a rule.
   *
   * @param rule The rule to consider.
   * @return True if the confirmation can be calculated, false otherwise.
   */
  private boolean canCalculateConfirmation(Rule rule) {
    if (rule.getObservedFrequency() > m_noiseThreshold) {
      return false;
    }
    return true;
  }

  /**
   * Test if a rule can be added to the results.
   *
   * @param rule The rule to consider.
   * @return True if the rule can be stored, false otherwise.
   */
  private boolean canStoreInResults(Rule rule) {
    if (rule.getConfirmation() < m_confirmationThreshold) {
      return false;
    }
    if (m_best != 0) {
      if (numValuesInResult() < m_best) {
	return true;
      }
      Rule worstResult = (Rule) m_results.getLast();
      if (rule.getConfirmation() >= worstResult.getConfirmation()) {
	return true;
      }
      return false;    
    } else {
      return true;
    }
  }

  /**
   * Add a rule in the appropriate place in the list of the results, 
   * according to the confirmation and 
   * number of counter-instances of the rule. <p>
   * Subsumption tests are performed and the rule may not be added. <p>
   * Previous results may also be removed because of sumption.
   */
  private void addResult(Rule rule) {

    Rule current;
    boolean added = false;

    /* Iterate the list until we find the right place. */
    SimpleLinkedList.LinkedListIterator iter = m_results.iterator();
    while (iter.hasNext()) {
      current = (Rule) iter.next();
      if (Rule.confirmationThenObservedComparator.compare(current, rule) > 0) {
	iter.addBefore(rule);
	added = true;
	break;
      }
      /* Subsumption tests to see if the rule can be added. */
      if ((m_subsumption || m_sameClause || m_equivalent)
	  && current.subsumes(rule)) {
	if (current.numLiterals() == rule.numLiterals()) {
	  if (current.equivalentTo(rule)) {
	    /* Equivalent rules. */
	    if (m_equivalent) {
	      return;
	    }
	  } else {
	    /* Same clauses. */
	    if (m_sameClause
		&& Rule.confirmationComparator.compare(current, rule) < 0) {
	      return;
	    }
	  }
	} else {
	  /* Subsumption. */
	  if (m_subsumption
	      && Rule.observedComparator.compare(current, rule) <= 0) {	
	    return;
	  }
	}
      }
    }

    if (added == false) {
      /* The rule must be added in the end of the results. */
      m_results.add(rule);
    }

    /* Iterate the results with a lower confirmation 
     *  to see if some of them must be removed. */
    SimpleLinkedList.LinkedListInverseIterator inverse 
      = m_results.inverseIterator();
    while (inverse.hasPrevious()) {
      current = (Rule) inverse.previous();
      if (Rule.confirmationThenObservedComparator.compare(current, rule) < 0) {
	break;
      }
      if (current != rule && rule.subsumes(current)) {
	if (current.numLiterals() == rule.numLiterals()) {
	  if (!current.equivalentTo(rule)) {
	    /* Same clauses. */
	    if (m_sameClause
		&& Rule.confirmationComparator.compare(current, rule) > 0) {
	      inverse.remove();
	    }
	  }
	} else {
	  /* Subsumption. */
	  if (m_subsumption
	      && Rule.observedComparator.compare(rule, current) <= 0) {	
	    inverse.remove();
	  }
	}	
      }
    }

    /* Remove the rules with the worst confirmation value 
     * if there are too many results. */
    if (m_best != 0 && numValuesInResult() > m_best) {
      Rule worstRule = (Rule) m_results.getLast();
      inverse = m_results.inverseIterator();
      while (inverse.hasPrevious()) {
	current = (Rule) inverse.previous();
	if (Rule.confirmationComparator.compare(current, worstRule) < 0) {
	  break;
	}
	inverse.remove();
      }
    }

    /* Print the new current values. */
    printValues();
  }

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

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

    // class
    result.enable(Capability.NOMINAL_CLASS);
    result.enable(Capability.MISSING_CLASS_VALUES);
    
    return result;
  }
  
  /**
   * Method that launches the search to find the rules with the highest 
   * confirmation.
   *
   * @param instances The instances to be used for generating the rules.
   * @throws Exception if rules can't be built successfully.
   */
  public void buildAssociations(Instances instances) throws Exception {

    Frame valuesFrame = null; /* Frame to display the current values. */

    /* Initialization of the search. */
    if (m_parts == null) {
      m_instances = instances;
    } else {
      m_instances = new IndividualInstances(instances, m_parts);
    }    
    m_results = new SimpleLinkedList();
    m_hypotheses = 0;
    m_explored = 0;
    m_status = NORMAL;

    if (m_classIndex == -1)
      m_instances.setClassIndex(m_instances.numAttributes()-1);     
    else if (m_classIndex < m_instances.numAttributes() && m_classIndex >= 0)
      m_instances.setClassIndex(m_classIndex);
    else
      throw new Exception("Invalid class index.");
    
    // can associator handle the data?
    getCapabilities().testWithFail(m_instances);
    
    /* Initialization of the window for current values. */
    if (m_printValues == WINDOW) {
      m_valuesText = new TextField(37);
      m_valuesText.setEditable(false);
      m_valuesText.setFont(new Font("Monospaced", Font.PLAIN, 12));    
      Label valuesLabel = new Label("Best and worst current values:");
      Button stop = new Button("Stop search");
      stop.addActionListener(new ActionListener() {
	  public void actionPerformed(ActionEvent e) {
	    /* Signal the interruption to the search. */
	    m_status = STOP;
	  }
	});
      valuesFrame = new Frame("Tertius status");
      valuesFrame.setResizable(false);
      valuesFrame.add(m_valuesText, BorderLayout.CENTER);
      valuesFrame.add(stop, BorderLayout.SOUTH);
      valuesFrame.add(valuesLabel, BorderLayout.NORTH);
      valuesFrame.pack();
      valuesFrame.setVisible(true);
    } else if (m_printValues == OUT) {
      System.out.println("Best and worst current values:");
    }
      
    Date start = new Date();

    /* Build the predicates and launch the search. */
    m_predicates = buildPredicates();
    beginSearch();    

    Date end = new Date();

    if (m_printValues == WINDOW) {
      valuesFrame.dispose();
    }

    m_time = new Date(end.getTime() - start.getTime());
  }

  /**
   * Run the search.
   */
  public void run() {
    try {
      search();
    } catch (OutOfMemoryError e) {
      /* Garbage collect what can be collected to be able to continue. */
      System.gc();
      m_status = MEMORY;
    }
    endSearch();
  }

  /**
   * Begin the search by starting a new thread.
   */
  private synchronized void beginSearch() throws Exception {
    /* This method must be synchronized to be able to 
     * call the wait() method. */
    Thread search = new Thread(this);
    search.start();
    try {
      /* Wait for the end of the thread. */
      wait();
    } catch (InterruptedException e) {
      /* Signal the interruption to the search. */
      m_status = STOP;
    }
  }

  /**
   * End the search by notifying to the waiting thread that it is finished.
   */
  private synchronized void endSearch() {
    /* This method must be synchronized to be able to
     * call the notify() method. */
    notify();
  }

  /**
   * Search in the space of hypotheses the rules that have the highest 
   * confirmation.
   * The search starts with the empty rule, other rules are generated by 
   * refinement.
   */
  public void search() {

    SimpleLinkedList nodes = new SimpleLinkedList(); /* The agenda. */
    Rule currentNode;
    SimpleLinkedList children;
    SimpleLinkedList.LinkedListIterator iter;
    Rule child;
    boolean negBody = (m_negation == BODY || m_negation == ALL);
    boolean negHead = (m_negation == HEAD || m_negation == ALL);

    /* Start with the empty rule. */
      nodes.add(new Rule(m_repeat, m_numLiterals, negBody, negHead,
			 m_classification, m_horn));
    
    /* Print the current values. */
    printValues();

    /* Explore the rules in the agenda. */
    while (m_status != STOP && !nodes.isEmpty()) {
      currentNode = (Rule) nodes.removeFirst();
      if (canRefine(currentNode)) {
	children = currentNode.refine(m_predicates);
	iter = children.iterator();
	/* Calculate the optimistic estimate of the children and 
	 * consider them for adding to the agenda and to the results. */
	while (iter.hasNext()) {
	  m_hypotheses++;
	  child = (Rule) iter.next();
	  child.upDate(m_instances);
	  if (canCalculateOptimistic(child)) {
	    child.calculateOptimistic();
	    if (canExplore(child)) {
	      m_explored++;
	      if (canStoreInNodes(child)) {
	      } else {
		iter.remove();
	      }
	      if (canCalculateConfirmation(child)) {
		child.calculateConfirmation();
		if (canStoreInResults(child)) {
		  addResult(child);
		}	  
	      }
	    } else {
	      iter.remove();
	    }
	  } else {
	    iter.remove();
	  }
	}
	/* Since the agenda is already sorted it is more efficient
	 * to sort the children only and then merge. */
	children.sort(Rule.optimisticThenObservedComparator);
	nodes.merge(children, Rule.optimisticThenObservedComparator);
      } else {
	/* The agenda being sorted, it is not worth considering the following 
	 * nodes. */
	break;
      }
    }
  }


  /**
   * Print the current best and worst values. 
   */
  private void printValues() {

    if (m_printValues == NO) {
      return;
    } else {
      if (m_results.isEmpty()) {
	if (m_printValues == OUT) {
	  System.out.print("0.000000 0.000000 - 0.000000 0.000000");
	} else { //m_printValues == WINDOW
	  m_valuesText.setText("0.000000 0.000000 - 0.000000 0.000000");
	}
      } else {
	Rule best = (Rule) m_results.getFirst();
	Rule worst = (Rule) m_results.getLast();
	String values = best.valuesToString() + " - " + worst.valuesToString();
	if (m_printValues == OUT) {
	  System.out.print("\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b"
			   + "\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b");
	  System.out.print(values);
	} else { //m_printValues == WINDOW
	  m_valuesText.setText(values);
	}
      }
    }
  }

  /**
   * Outputs the best rules found with their confirmation value and number 
   * of counter-instances.
   * Also gives the number of hypotheses considered and explored, and the 
   * time needed. 
   */
  public String toString() {

    StringBuffer text = new StringBuffer();
    SimpleDateFormat dateFormat 
      = new SimpleDateFormat("mm 'min' ss 's' SSS 'ms'");
    SimpleLinkedList.LinkedListIterator iter = m_results.iterator();
    int size = m_results.size();
    int i = 0;

    text.append("\nTertius\n=======\n\n");

    while (iter.hasNext()) {
      Rule current = (Rule) iter.next();
      text.append(Utils.doubleToString((double) i + 1,
				       (int) (Math.log(size) 
					      / Math.log(10) + 1),
				       0)
		  + ". ");
      text.append("/* ");
      if (m_roc) {
	text.append(current.rocToString());
      } else {
	text.append(current.valuesToString());
      }
      text.append(" */ ");
      text.append(current.toString());
      text.append("\n");
      i++;
    }
 
    text.append("\nNumber of hypotheses considered: " + m_hypotheses);
    text.append("\nNumber of hypotheses explored: " + m_explored);
    text.append("\nTime: " + dateFormat.format(m_time));

    if (m_status == MEMORY) {
      text.append("\n\nNot enough memory to continue the search");
    } else if (m_status == STOP) {
      text.append("\n\nSearch interrupted");
    }

    return text.toString();
  }

  /**
   * Main method.
   * 
   * @param args the commandline parameters
   */
  public static void main(String [] args) {

    String trainFileString;
    Reader reader;
    Instances instances;
    Tertius tertius = new Tertius();
    StringBuffer text = new StringBuffer();

    try {
      /* Help string giving all the command line options. */
      text.append("\n\nTertius options:\n\n");
      text.append("-t <name of training file>\n");
      text.append("\tSet training file.\n");
      Enumeration enu = tertius.listOptions();
      while (enu.hasMoreElements()) {
	Option option = (Option) enu.nextElement();
	text.append(option.synopsis() + "\n");
	text.append(option.description() + "\n");
      }

      /* Training file. */
      trainFileString = Utils.getOption('t', args);
      if (trainFileString.length() == 0) {
	throw new Exception("No training file given!");
      }
      try {
	reader = new BufferedReader(new FileReader(trainFileString));
      } catch (Exception e) {
	throw new Exception("Can't open file " + e.getMessage() + ".");
      }

      instances = new Instances(reader);

      /* Tertius options. */
      tertius.setOptions(args);
      Utils.checkForRemainingOptions(args);

      /* Build the rules and output the results. */
      tertius.buildAssociations(instances);
      System.out.println(tertius);

    } catch (Exception e) {
      System.err.println("\nWeka exception: " + e.getMessage() + text);
    }
  }
}