decisiontree.java

Decision Tree Decision Tree Decision Tree

        node.negBranch = new DecisionTreeNode();
        generateNextNode2(node.negBranch,negExampleList,attributeList);
        }

    /** Continue to generate next decision tree node.
    @param node the current decision tree node.
    @param exampleList the currebt list of examples.
    @param attributeList the cuttent list of attrbutes. */

    private void generateNextNode2(DecisionTreeNode node,
                               int[] exampleList, short[] attributeList) {
        // No more examples
        if (exampleList==null) node.attNumber = 0;

        // Example list only references one class
        else if (exampleListUniform(exampleList)) {
            int lastIndex = testDataArray[exampleList[0]].length-1;
            short nodeClass = testDataArray[exampleList[0]][lastIndex];
            node.attNumber = nodeClass;
            }
        // Check attribute list
        else if (attributeList==null) {
//System.out.println("attributeList is null");
            short nodeClass = getDominantClass(exampleList);
            node.attNumber  = nodeClass;
            }
        // Prooced by first removing attributes that do not appear in the
        // examples
        else {
            attributeList = pruneAttributeList(attributeList,exampleList);
            // All attributes in attribute list may have been
            // pruned because they do not appear in examples,
            // there for check for empty attribute list.
            if (attributeList==null) {
//System.out.println("attributeList is null (after pruning)");
                short nodeClass = getDominantClass(exampleList);
                node.attNumber  = nodeClass;
                }    
            else generateNextNode(node,attributeList,exampleList);
            }
        }

    /** Prunes the attribute list by removing attributes that do not
    appear in the examples.
    @param attributeList the cuttent list of attrbutes.
    @param exampleList the currebt list of examples.
    @return revise attribute list. */

    private short[] pruneAttributeList(short[] attributeList, int[] exampleList) {
        int i=0;
//outputIntArray("attribute list",attributeList);
//outputIntArray("exampleList",exampleList);

        // Loop
        while(i<attributeList.length) {
            boolean attFound = false;
            for (int j=0;j<exampleList.length;j++) {
                if (memberOf(attributeList[i],dataArray[exampleList[j]])) {
                    attFound=true;
                    break;
                    }
                }
            // If not in ecamples remove from list
            if (!attFound) attributeList = newAttributeList(i,attributeList);
            else i++;
            // Check for emty attribute list
            if (attributeList==null) return(null);
            }

        // Returm
        return(attributeList);
        }

    /** Counts the number of positive examples.
    @param attNum the attribute to be included in the positive list.
    @param exampleList the current example list.
    @return the number of positive examples.    */

    private int countPosExamples(short attNum, int[] exampleList) {
       // Count number of examples
       int counter=0;
       for (int i=0;i<exampleList.length;i++) {
           if (memberOf(attNum,testDataArray[exampleList[i]])) counter++;
           }

       // Return
       return(counter);
       }

    /** Create new positive and negative example lists.
    @param
    @param attNum the attribute to be included in the positive list.
    @param oldExampleList the current (old) example list.
    @param posExampleList the new example list containg the given attribute.
    @param negExampleList the new example list not containg the given
    attribute. */

    private void createNewExampleLists(short attNum, int[] exampleList,
                                int[] posExampleList, int[] negExampleList) {
        int posIndex = 0;
        int negIndex = 0;

        // Loop through old example list
        for (int i=0;i<exampleList.length;i++) {
            if (memberOf(attNum,testDataArray[exampleList[i]])) {
                posExampleList[posIndex] = exampleList[i];
                posIndex++;
                }
            else {
                negExampleList[negIndex] = exampleList[i];
                negIndex++;
                }
            }
        }

    /** Determines if given example list has a uniform class associated with
    it.
    @param exampleList the given example list.
    @return true if uniform, false otherwise.   */

    private boolean exampleListUniform(int[] exampleList) {

        // Start class
        int lastIndex = testDataArray[exampleList[0]].length-1;
        int classNum  = testDataArray[exampleList[0]][lastIndex];

        // Loop through example list
        for (int i=1;i<exampleList.length;i++) {
            lastIndex = testDataArray[exampleList[i]].length-1;
            int newClassNum  = testDataArray[exampleList[i]][lastIndex];
            if (classNum!=newClassNum) return(false);
            }

        // End
        return(true);
        }

    /** Identifies and return dominant class in example list.
    @param exampleList the given example list.
    @return true if uniform, false otherwise.    */

    private short getDominantClass(int[] exampleList) {
        // Create class array
        int[] classArray = new int[numClasses];
        for (int i=0;i<classArray.length;i++) classArray[i]=0;

        // Loop through example list
        for (int i=0;i<exampleList.length;i++) {
            int lastIndex = testDataArray[exampleList[i]].length-1;
            int classNum = testDataArray[exampleList[i]][lastIndex];
            int classIndex = classNum-numAttributes-1;
            // Increment
            classArray[classIndex]++;
            }

        // Find dominant class
        int domClassIndex = 0;
        int domClassCount = classArray[0];
        for (int i=1;i<classArray.length;i++) {
            if (classArray[i]>domClassCount) {
                domClassIndex = i;
                domClassCount = classArray[i];
                }
            }

        // Return
        short classNum = (short) (domClassIndex+numAttributes+1);
        return(classNum);
        }

    /** Selects attribute from attribute list on which to split (stub).  
    @param attributeList the cuttent list of attrbutes.
    @param exampleList the currebt list of examples.
    @return the attribute index of the selected attribute. */

    protected int selectAttribute(short[] attributeList, int[] exampleList) {
       return(0);
       }

    /** Removes indicated attribute from attribute list.
    @param index the location in the old attributes list of the attribute to be 
    removed.
    @param oldAttList the old attribute list to be revised.
    @return new attribute list.     */

    private short[] newAttributeList(int index, short[] oldAttList) {
        // New list is empty
        if (oldAttList.length==1) return(null);

        // Create new list
        short[] newAttList = new short[oldAttList.length-1];
        int j=0;
        for (int i=0;i<index;i++,j++) newAttList[j]=oldAttList[i];
        for (int i=index+1;i<oldAttList.length;i++,j++)
                                                  newAttList[j]=oldAttList[i];
        // Emd
        return(newAttList);
        }

    /** Create attribute list.
    &return the newly created attribute list */

    private short[] createAttributeList() {
        short[] attributeList = new short[numOneItemSets-numClasses];
        for (short i=0;i<attributeList.length;i++) attributeList[i] =
                                                                (short) (i+1);

        // Return
        return(attributeList);
        }

    /** Create a list of exmples in test set.
    @return the generated list of examples. */

    private int[] generateExampleList() {
        int[] exampleList = new int[testDataArray.length];

        // Populate
        for(int i=0;i<exampleList.length;i++) exampleList[i]=i;

        // Return
        return(exampleList);
        }
    /* ---------------------------------------------------------------- */
    /*                                                                  */
    /*                       GENERATE RULE LIST                         */
    /*                                                                  */
    /* ---------------------------------------------------------------- */

    /** Generates a rule list by processing decision tree. */

    private void generateRuleList() {
        short[] antecedent = new short[0];
        generateRuleList(antecedent,root);
        }

    /** Continues process of generating a rule list, ordered according to size
    of antecedent, by processing current node.
    @param antecedent the list of antecedent attributes sofar
    @param node the current node in the decision tree. */

    private void generateRuleList(short[] antecedent, DecisionTreeNode node) {
        if (node.posBranch==null) {
            if (node.attNumber>0) {
                short[] consequent = new short[1];
                consequent[0] = node.attNumber;
                insertRuleIntoRulelist(antecedent,consequent,0.0);
                numRules++;
                }
            }
        else {
            short[] newAntecedent = reallocInsert(antecedent,node.attNumber);
            generateRuleList(newAntecedent,node.posBranch);
            generateRuleList(antecedent,node.negBranch);
            }
        }

    /* ------------------------------------------------------------- */
    /*                                                               */
    /*                         CLASSIFIER                            */
    /*                                                               */
    /* ------------------------------------------------------------- */

    /* TEST CLASSIFICATION */
    /** Tests the generated classification rules using the test set and returns
    percentage accuracy.
    @return the perecentage accuarcy. */

    protected double testClassification() {
	int correctClassCounter = 0;

	// Check if test data exists, if not return' 0'
	if (testDataArray==null) {
	    System.out.println("WARNING: No test data");
            return(0.0);
	    }

	// Check if any classification rules have been generated, if not
	// return'0'
	if (startRulelist==null) {
	    String s = "No classification rules generated!\n";
	    System.out.print(s);
            return(0.0);
	    }

	// Loop through test set
	int index=0;
    	for(;index<testDataArray.length;index++) {
	    // Note: classifyRecord methods are contained in the
	    // AprioriTFPclass class. To classify without default use
	    // classifyRecord, with defualt use classifyRecordDefault.
            short classResult =
	               classifyRecordDefault(testDataArray[index]);
	    // If zero error has occured