instrumentedalternatingtree.java

Boosting算法软件包

	    pInt[i]= m_predictors.size();
	    addPredictorNodeToList(pNode[i]);
	    // 1.b) Generate the exampleMasks for the split.
	    examplesMask= makeExampleMask(partition[i], m_examples.length);
	    m_masks.add(examplesMask);
	    // 1.c) Create the splitter builders for this prediction node.
	    SplitterBuilder[] childArray= new SplitterBuilder[parentArray.length];
	    for (int j= 0; j < parentArray.length; j++) {
		childArray[j]= parentArray[j].spawn(examplesMask, partition[i].length);
	    }
	    PredictorNodeSB pnSB= new PredictorNodeSB(pInt[i], childArray);
	    m_splitterBuilders.add(pnSB);
	}
	// 2) Add new splitter node.
	parent.addSplitterNode(sNode);
	m_splitters.add(pInt);
	return sNode;
    }
  
  
    /**
     *  add a CandidateSplit 								
     *  @param the candidate that has been chosen as a split
     */
    public void addCandidate(CandidateSplit candidate) throws InstrumentException {
	AtreeCandidateSplit acand= null;
	SplitterNode node= null;
	try {
	    acand= (AtreeCandidateSplit) candidate;
	} catch (ClassCastException e) {
	    throw new InstrumentException("Sent non-atree candidate to atree.addCandidate");
	}
    
	// Check if we should just update the root's prediction.
	if (acand.updateRoot) {
	    updateRoot();
	} else {
	    Bag[] bags= acand.getPartition();
	    int[][] partition= acand.getDataSplit();
	    Splitter splitter= acand.getSplitter();
	    PredictorNode parent= (PredictorNode) m_predictors.get(acand.getPredictorNode());
      
	    Prediction[] predictions= m_booster.getPredictions(bags, partition);
	    m_booster.update(predictions, partition);
	    if (parent==null) {
		System.err.println("Parent is null!");
	    }
	    lastBasePredictor= new AtreePredictor(splitter, parent, predictions, m_booster);
	    node= findSplitter(parent, splitter);
	    if (node != null && (predictions.length > 0 && !(predictions[0] instanceof NormalizedPrediction)) ) {
		for (int i=0; i < node.predictorNodes.length; i++) {
		    node.predictorNodes[i].addToPrediction(predictions[i]);
		}
	    } else {
		SplitterBuilder[] parentArray= ((PredictorNodeSB) m_splitterBuilders.get(acand.getPredictorNode())).SB;
		node = insert(bags, parent, splitter, parentArray, predictions, partition);
	    }
	}
	/*
	System.out.println("Adding Candidate: " + candidate);
	
	System.out.println("Node being added:" );
	System.out.println("" + node );

	System.out.println("m_predictors:");
	for (int i=0; i<m_predictors.size(); i++) {
	    System.out.println("i: "+ i + m_predictors.get(i));
	}
	System.out.println("m_predictors.index:");
	for (int i=0; i<m_predictors.size(); i++) {
	    System.out.println("i: "+ i + ((PredictorNode)(m_predictors.get(i))).getIndex());
	}
	System.out.println("m_splitters:\n");
	for (int i=0; i<m_splitters.size(); i++) {
	    System.out.println("i: "+i+m_splitters.get(i));
	}
	System.out.println("m_splitterBuilders:\n");
	for (int i=0; i<m_splitterBuilders.size(); i++) {
	    System.out.println("i: "+i+m_splitterBuilders.get(i));
	}
	*/
    }
  
    /**
     *  add a CandidateSplit using the Predictions instead of generating them               
     *  @param the candidate that has been chosen as a split
     *  @param predictions from this split
     */
    public void addCandidate(CandidateSplit candidate, Prediction[] predictions) 
	throws InstrumentException {
    
	AtreeCandidateSplit acand= null;
	try {
	    acand= (AtreeCandidateSplit) candidate;
	} catch (ClassCastException e) {
	    throw new InstrumentException("Sent non-atree candidate to atree.addCandidate");
	}
    
	// Check if we should just update the root's prediction.
	// Does this ever happen?
	if (acand.updateRoot) {
	    updateRoot();
	} else {
	    Bag[] bags= acand.getPartition();
	    int[][] partition= acand.getDataSplit();
	    Splitter splitter= acand.getSplitter();
	    PredictorNode parent= (PredictorNode) m_predictors.get(acand.getPredictorNode());
      
	    m_booster.update(predictions, partition);
	    if (parent==null) {
		System.err.println("Adding candidate and the parent is null!");
	    }
	    lastBasePredictor= new AtreePredictor(splitter, parent, predictions, m_booster);
	    SplitterNode node= findSplitter(parent, splitter);
	    if (node != null) {
		for (int i=0; i < node.predictorNodes.length; i++) {
		    node.predictorNodes[i].addToPrediction(predictions[i]);
		}
	    } else {
		SplitterBuilder[] parentArray= ((PredictorNodeSB) m_splitterBuilders.get(acand.getPredictorNode())).SB;
		insert(bags, parent, splitter, parentArray, predictions, partition);
	    }
	}
    } 
  
    /**
     * Instrument this tree by using the AlternatingTree.  This method
     * is like an automated version of the learn() method used by the
     * Controller.  Instead of evaluating the set returned by
     * getCandidates(), this tree will be built using the splitters
     * that are already used in the AlternatingTree.  Using each
     * splitter, we create the CandidateSplit and add it to the tree.
     * @param tree
     */
    public void instrumentAlternatingTree(AlternatingTree tree) throws InstrumentException, NotSupportedException {
	// get the nodes for the tree
	// the defaults for these lists should come from the tree
	// TODO:decide if we really need to return the predictors with the splitters
	ArrayList predictors= new ArrayList(25);
	ArrayList splitters= new ArrayList(25);
    
	tree.getNodes(predictors, splitters);
	CandidateSplit split= null;
	// create each candidate split and add it to this tree
	// by finding adding all the splitters that match the current predictor node
	for (int i=0; i < m_predictors.size(); i++) {
	    PredictorNode prediction= (PredictorNode) m_predictors.get(i);
	    String predictionID= prediction.getID();
      
	    for (int j=0; j < splitters.size(); j++) {
		SplitterNode splitter= (SplitterNode) splitters.get(j);
		// get the splitter ID without the final 2 characters
		String splitterID= splitter.getID().substring(0, splitter.getID().length() - 2);
		// compare this splitter ID to the prediction ID
		// if they match, then add this splitter to the tree with this predictor
		if (splitterID.equals(predictionID)) {
		    PredictorNodeSB splitterBuilder= (PredictorNodeSB) m_splitterBuilders.get(i);
		    // find the splitter builder with the same type as this splitter
		    // build a CandidateSplit and add it to this tree
		    for (int k=0; k < splitterBuilder.SB.length; k++) {
			// check that the Splitter and SplitterBuilder have the same type,
			// and that they have the same AttributeDescription
			//if (splitter.splitter.getType().equals(splitterBuilder.SB[k].getType())) {
			if (splitterBuilder.SB[k].canBuild(splitter.splitter)) {
			    split= splitterBuilder.SB[k].build(splitter.splitter);
			    // find the predictors that have this splitter as their root
			    Prediction[] predictions= new Prediction[splitter.getPredictorNodes().length];
			    for (int n=0; n < predictions.length; n++) {
				predictions[n]= splitter.getPredictorNodes()[n].prediction;
			    }
              
			    // add split to tree
			    AtreeCandidateSplit added= new AtreeCandidateSplit(i, split);
			    addCandidate(added, predictions);
			    // remove the split from the list of splitters
			    // decrement the index to make sure we do not skip a splitter in the list
			    splitters.remove(j--);
			    // break out of this loop and move to the next splitter
			    break;
			}
		    }
		}
	    }
	}
    }
  
    /**
     *  Get the combined classifier.
     *  Simply returns a pointer to the root predictor nodes, so that
     *  the returned tree will share nodes with this Instrumented Tree.
     *  
     *  @return An alternating decision tree created by this object   		
     */
    public WritablePredictor getCombinedPredictor() {
	PredictorNode p= (PredictorNode) m_predictors.get(0);
	AlternatingTree retval= new AlternatingTree(p);
	return (retval);
    }
  
    /** Adjusts the predictions of all of the existing {@link PredictorNode}s in
     *  the tree.  									*/
    public void adjustPredictions() {
	int[][] examples= null;
	boolean[] exMask= null;
	int count= 0;
	PredictorNode[] pn= null;
	int s= m_splitters.size();
	int[] pNodes= null;
	Bag[] b= null;
	int nodeNo= 0;
	Prediction[] p= null;
	for (int i= 0; i < s; i++) {
	    pNodes= (int[]) m_splitters.get(i);
	    pn= new PredictorNode[pNodes.length];
	    examples= new int[pNodes.length][];
	    b= new Bag[pNodes.length];
	    for (int j= 0; j < pNodes.length; j++) {
		nodeNo= pNodes[j];
		exMask= (boolean[]) m_masks.get(nodeNo);
		pn[j]= (PredictorNode) m_predictors.get(nodeNo);
		examples[j]= makeIndices(exMask);
		b[j]= m_booster.newBag(examples[j]);
	    }
	    p= m_booster.getPredictions(b,examples);
	    m_booster.update(p, examples);
	    for (int j= 0; i < pNodes.length; j++)
		pn[j].addToPrediction(p[j]);
	}
    }
    /** Produces a string describing this tree.						*/
    public String toString() {
	return (((PredictorNode) m_predictors.get(0)).toString());
    }
    /**
     * returns the last base predictor that was added using addCandidate.
     */
    public Predictor getLastBasePredictor() {
	return lastBasePredictor;
    }

    public boolean boosterIsFinished() {
	if(m_booster instanceof BrownBoost){
	    BrownBoost b = (BrownBoost) m_booster;
	    return b.isFinished();
	}

	double EPS = 1e-50;
	double w = m_booster.getTotalWeight();
	if ((w < EPS) || Double.isNaN(w)) {
	    System.out.println("JBoost boosting process is completed.");
	    System.out.println("\tThe boosting has finished early.");
	    System.out.println("\tThis is a result of too little weight being placed on examples");
	    System.out.println("\t(which will cause an underflow error).");
	    System.out.println("\tThis is not necessarily a bad thing.  Look at the margin curve to find out more.");
	    return true;
	}

	return false;
    }

    //---------------------------------- Un-Implemented ----------------------------------------//
    public void addExample(Example e) {
    }
    public void finalizeData() {
    }
    public void resetData() {
    }
    //---------------------------------- Protected Members -------------------------------------//
    /**
     * Add a predictorNode to this list.  						*/
    protected void addPredictorNodeToList(PredictorNode pn) {
	m_predictors.add(pn);
    }
    /**
     * Add a splitterNode to this list.  						*/
    protected void addSplitterNode(SplitterNode sn) {
	m_splitters.add(sn);
    }
    protected Booster getBooster() {
	return (m_booster);
    }
    protected int getIndex() {
	return (m_index);
    }
    protected void setIndex(int ind) {
	m_index= ind;
    }
  
    public ArrayList getMasks() {
	return m_masks;
    }
  
    private void setAddType(Configuration config) throws ConfigurationException {
    
	String aT= config.getString("ATreeType", "ADD_ALL");
    
	if (aT.equals("ADD_ALL")) {
	    m_treeType= AtreeType.ADD_ALL;
	}
	else if (aT.equals("ADD_ROOT")) {
	    m_treeType= AtreeType.ADD_ROOT;
	}
	else if (aT.equals("ADD_SINGLES")) {
	    m_treeType= AtreeType.ADD_SINGLES;
	}
	else if (aT.equals("ADD_ROOT_OR_SINGLES")) {
	    m_treeType= AtreeType.ADD_ROOT_OR_SINGLES;
	}
	else {
	    throw new ConfigurationException("Unknown value: " + aT + " for Atree_AddType");
	}
    
	if (Monitor.logLevel > 3) Monitor.log("Add Type is " + aT + " " + m_treeType);
    }
  
    
    /** Make a integer array of m_examples given an ExampleMask				*/
    private int[] makeIndices(boolean[] exMask) {
	int[] examples= null;
	int count= 0;
	for (int j= 0; j < exMask.length; j++)
	    if (exMask[j] == true)
		count++;
	examples= new int[count];
	count= 0;
	for (int j= 0; j < exMask.length; j++)
	    if (exMask[j] == true)
		examples[count++]= j;
	return (examples);
    }
    /** the last base predictor added to the tree */
    private Predictor lastBasePredictor= null;
    /** Construct an example mask - this should be in some generic place 		*/
    boolean[] makeExampleMask(int[] exampleList, int s) {
	boolean[] em= new boolean[s];
	Arrays.fill(em, false);
	int length= exampleList.length;
	for (int i= 0; i < length; i++)
	    em[exampleList[i]]= true;
	return (em);
    }


}






/** A description of a candidate splitter */
class AtreeCandidateSplit extends CandidateSplit {
    boolean updateRoot;
    private int pNode;
    /** the predictor node in the atree which owns the builder */
    public int getPredictorNode() {
	return (pNode);
    }
    /** Constructor to convert from a {@link CandidateSplit}   */
    public AtreeCandidateSplit(int pn, CandidateSplit b) {
	pNode= pn;
	builder= b.getBuilder();
	splitter= b.getSplitter();
	partition= b.getPartition();
	loss= b.getLoss();
	updateRoot= false;
    }
    /** Constructor to specify that only the root prediction should be updated.	*/
    public AtreeCandidateSplit(double loss) {
	updateRoot= true;
	this.loss= loss;
	pNode= 0;
	builder= null;
	splitter= null;
	partition= null;
    }
}
/** Contains a SplitterBuilder and the number of the PredictorNode to which it belongs.	*/
class PredictorNodeSB {
    public int pNode;
    public SplitterBuilder[] SB;
    public PredictorNodeSB(int p, SplitterBuilder[] sb) {
	SB= sb;
        pNode= p;
    }
}