aprioritgui.java

apriori算法java 带有详细注解

	}

    /* GENERATE NEXT LEVEL */

    /** Generates a new level in the T-tree from a given "parent" node. <P>
    Example 1, given the following:

    <PRE>
    (A) ----- (B) ----- (C)
               |         |
	       |         |
	      (A)       (A) ----- (B)
    </PRE><P>
    where we wish to add a level 3 node to node (B), i.e. the node {A}, we
    would proceed as follows:
    <OL>
    <LI> Generate a new level in the T-tree attached to node (B) of length
    one less than the numeric equivalent of B i.e. 2-1=1.
    <LI> Loop through parent level from (A) to node immediately before (B).
    <LI> For each supported parent node create an itemset label by combing the
    index of the parent node (e.g. A) with the complete itemset label for B ---
    {C,B} (note reverse order), thus for parent node (B) we would get a new
    level in the T-tree with one node in it --- {C,B,A} represented as A.
    <LI> For this node to be a candidate large item set its size-1 subsets must
    be supported, there are three of these in this example {C,A}, {C,B} and
    {B,A}. We know that the first two are supported because they are in the
    current branch, but {B,A} is in another branch. So we must generate this
    set and test it. More generally we must test all cardinality-1 subsets
    which do not include the first element. This is done using the method
    <TT>testCombinations</TT>.
    </OL>
    <P>Example 2, given:
    <PRE>
    (A) ----- (D)
               |
	       |
	      (A) ----- (B) ----- (C)
	                           |
				   |
				  (A) ----- (B)
    </PRE><P>
    where we wish to add a level 4 node (A) to (B) this would represent the
    complete label {D,C,B,A}, the N-1 subsets will then be {{D,C,B},{D,C,A},
    {D,B,A} and {C,B,A}}. We know the first two are supported becuase they are
    contained in the current sub-branch of the T-tree, {D,B,A} and {C,B,A} are
    not.
    </OL>
    @param parentRef the reference to the level in the sub-branch of the T-tree
    under consideration.
    @param endIndex the index of the current node under consideration.
    @param itemSet the complete label represented by the current node (required
    to generate further itemsets to be X-checked). */

    protected void generateNextLevel(TtreeNode[] parentRef, int endIndex,
    			short[] itemSet) {
	parentRef[endIndex].childRef = new TtreeNode[endIndex];	// New level
        short[] newItemSet;
	// Generate a level in Ttree

	TtreeNode currentNode = parentRef[endIndex];

	// Loop through parent sub-level of siblings upto current node
	for (int index=1;index<endIndex;index++) {
	    // Check if "uncle" element is supported (i.e. it exists)
	    if (parentRef[index] != null) {
		// Create an appropriate itemSet label to test
	        newItemSet = realloc2(itemSet,(short) index);
		if (testCombinations(newItemSet)) {
		    currentNode.childRef[index] = new TtreeNode();
		    nextLevelExists=true;
		    }
	        else currentNode.childRef[index] = null;
	        }
	    }
	}

    /* TEST COMBINATIONS */

    /** Commences the process of testing whether the N-1 sized sub-sets of a
    newly created T-tree node are supported elsewhere in the Ttree --- (a
    process refered to as "X-Checking"). <P> Thus given a candidate large
    itemsets whose size-1 subsets are contained (supported) in the current
    branch of the T-tree, tests whether size-1 subsets contained in other
    branches are supported. Proceed as follows:
    <OL>
    <LI> Using current item set split this into two subsets:
    <P>itemSet1 = first two items in current item set
    <P>itemSet2 = remainder of items in current item set
    <LI> Calculate size-1 combinations in itemSet2
    <LI> For each combination from (2) append to itemSet1
    </OL>
    <P>Example 1:
    <PRE>
    currentItemSet = {A,B,C}
    itemSet1 = {B,A} (change of ordering)
    size = {A,B,C}-2 = 1
    itemSet2 = {C} (currentItemSet with first two elements removed)
    calculate combinations between {B,A} and {C}
    </PRE>
    <P>Example 2:
    <PRE>
    currentItemSet = {A,B,C,D}
    itemSet1 = {B,A} (change of ordering)
    itemSet2 = {C,D} (currentItemSet with first two elements removed)
    calculate combinations between {B,A} and {C,D}
    </PRE>
    @param currentItemSet the given itemset.		*/

    protected boolean testCombinations(short[] currentItemSet) {

        if (currentItemSet.length < 3) return(true);

	// Creat itemSet1 (note ordering)

	short[] itemSet1 = new short[2];
	itemSet1[0] = currentItemSet[1];
	itemSet1[1] = currentItemSet[0];

	// Creat itemSet2

	int size = currentItemSet.length-2;
	short[] itemSet2 = removeFirstNelements(currentItemSet,2);

	// Calculate combinations

	return(combinations(null,0,2,itemSet1,itemSet2));
	}

    /* COMBINATIONS */

    /** Determines the cardinality N combinations of a given itemset and then
    checks whether those combinations are supported in the T-tree. <P>
    Operates in a recursive manner.
    <P>Example 1: Given --- sofarSet=null,
    startIndex=0, endIndex=2, itemSet1 = {B,A} and itemSet2 = {C}
    <PRE>
    itemSet2.length = 1
    endIndex = 2 greater than itemSet2.length if condition succeeds
    tesSet = null+{B,A} = {B,A}
    retutn true if {B,A} supported and null otherwise
    </PRE>
    <P>Example 2: Given --- sofarSet=null,
    startIndex=0, endIndex=2, itemSet1 = {B,A} and itemSet2 = {C,D}
    <PRE>
    endindex not greater than length {C,D}
    go into loop
    tempSet = {} + {C} = {C}
    	combinations with --- sofarSet={C}, startIndex=1,
			endIndex=3, itemSet1 = {B,A} and itemSet2 = {C}
	endIndex greater than length {C,D}
	testSet = {C} + {B,A} = {C,B,A}
    tempSet = {} + {D} = {D}
    	combinations with --- sofarSet={D}, startIndex=1,
			endIndex=3, itemSet1 = {B,A} and itemSet2 = {C}
	endIndex greater than length {C,D}
	testSet = {D} + {B,A} = {D,B,A}
    </PRE>
    @param sofarSet The combination itemset generated so far (set to null at
    start)
    @param startIndex the current index in the given itemSet2 (set to 0 at
    start).
    @param endIndex The current index of the given itemset (set to 2 at start)
    and incremented on each recursion until it is greater than the length of
    itemset2.
    @param itemSet1 The first two elements (reversed) of the totla label for the
    current item set.
    @param itemSet2 The remainder of the current item set.
    */

    private boolean combinations(short[] sofarSet, int startIndex,
    		    int endIndex, short[] itemSet1, short[] itemSet2) {
	// At level

	if (endIndex > itemSet2.length) {
	    short[] testSet = append(sofarSet,itemSet1);
	    // If testSet exists in the T-tree sofar then it is supported
	    return(findItemSetInTtree(testSet));
	    }

	// Otherwise
	else {
	    short[] tempSet;
	    for (int index=startIndex;index<endIndex;index++) {
	        tempSet = realloc2(sofarSet,itemSet2[index]);
	        if (!combinations(tempSet,index+1,endIndex+1,itemSet1,
				itemSet2)) return(false);
	        }
	    }

	// Return

	return(true);
	}

    /*---------------------------------------------------------------------- */
    /*                                                                       */
    /*                        T-TREE SEARCH METHODS                          */
    /*                                                                       */
    /*---------------------------------------------------------------------- */

    /* FIND ITEM SET IN T-TREE*/

    /** Commences process of determining if an itemset exists in a T-tree. <P>
    Used to X-check existance of Ttree nodes when generating new levels of the
    Tree. Note that T-tree node labels are stored in "reverse", e.g. {3,2,1}.
    @param itemSet the given itemset (IN REVERSE ORDER).
    @return returns true if itemset found and false otherwise. */

    private boolean findItemSetInTtree(short[] itemSet) {

    	// first element of itemset in Ttree (Note: Ttree itemsets stored in
	// reverse)
  	if (startTtreeRef[itemSet[0]] != null) {
    	    int lastIndex = itemSet.length-1;
	    // If single item set return true
	    if (lastIndex == 0) return(true);
	    // Otherwise continue down branch
	    else return(findItemSetInTtree2(itemSet,1,lastIndex,
			startTtreeRef[itemSet[0]].childRef));
	    }
	// Item set not in Ttree
    	else return(false);
	}

    /** Returns true if the given itemset is found in the T-tree and false
    otherwise. <P> Operates recursively.
    @param itemSet the given itemset.
    @param index the current index in the given T-tree level (set to 1 at
    start).
    @param lastIndex the end index of the current T-tree level.
    @param linRef the reference to the current T-tree level.
    @return returns true if itemset found and false otherwise. */

    private boolean findItemSetInTtree2(short[] itemSet, int index,
    			int lastIndex, TtreeNode[] linkRef) {

        // Element at "index" in item set exists in Ttree
  	if (linkRef[itemSet[index]] != null) {
  	    // If element at "index" is last element of item set then item set
	    // found
	    if (index == lastIndex) return(true);
	    // Otherwise continue
	    else return(findItemSetInTtree2(itemSet,index+1,lastIndex,
	    		linkRef[itemSet[index]].childRef));
	    }
	// Item set not in Ttree
	else return(false);
    	}

    /* ---------------------------------------------------------------- */
    /*                                                                  */
    /*                  GET MINIMUM SUPPORT VALUE                       */
    /*                                                                  */
    /* ---------------------------------------------------------------- */

    /* GET SUPPORT */

    private void addSupport() {
        try{
           while (true) {
               String stNum1 = JOptionPane.showInputDialog("Input minimum " +
	       		" support value between " + MIN_SUPPORT + " and " +
							MAX_SUPPORT);
	       if (stNum1.indexOf('.') > 0)
	       			support = Double.parseDouble(stNum1);
               else support = Integer.parseInt(stNum1);
               if (support>=MIN_SUPPORT && support<=MAX_SUPPORT) break;
               JOptionPane.showMessageDialog(null,
	       		"MINIMUM SUPPORT VALUE INPUT ERROR:\n" +
	       		"input = " + support +
	       		"\nminimum support input must be a floating point\n" +
			         "number between " + MIN_SUPPORT + " and " +
							MAX_SUPPORT);

	       }
	    textArea.append("Minimum support = " + support + "%\n");
	    hasSupportFlag=true;
	    }
        catch(NumberFormatException e) {
            hasSupportFlag=false;
	    runButton.setEnabled(false);
	    }

        // Enable run button if have data and a minimum support value.
	if (haveDataFlag && hasSupportFlag) runButton.setEnabled(true);
	}

    /* ---------------------------------------------------------------- */
    /*                                                                  */
    /*                           OPEN NAME                              */
    /*                                                                  */
    /* ---------------------------------------------------------------- */

    /* OPEN THE FILE */

    private void getFileName() {
        // Display file dialog so user can select file to open
	JFileChooser fileChooser = new JFileChooser();
	fileChooser.setFileSelectionMode(JFileChooser.FILES_ONLY);
	int result = fileChooser.showOpenDialog(this);

	// If cancel button selected return
	if (result == JFileChooser.CANCEL_OPTION) return;

	// Obtain selected file
	fileName = fileChooser.getSelectedFile();
	// Read file if readabale (i.e not a direcrory etc.).
	if (checkFileName()) {
	    readFile();
	    }

	// Check ordering
	if (inputFormatOkFlag) {
	    if (checkOrdering()) {
	        // Enable run button if have data and a minimum support value.
	        if (haveDataFlag && hasSupportFlag) runButton.setEnabled(true);
	        // Output to text area
	        outputDataArray();
		textArea.append("Number of records = " + numRows + "\n");
		countNumCols();
		textArea.append("Number of columns = " + numCols + "\n");
		}
	    else {
	        haveDataFlag = false;
	        inputFormatOkFlag = true;
	        textArea.append("Error reading file: " + fileName + "\n\n");
	        runButton.setEnabled(false);
	        }
	    }
	}

    /* CHECK FILE NAME */

    /* Return flase if selected file is a directory, access is denied or is
    not a file name. */

    private boolean checkFileName() {
	if (fileName.exists()) {
	    if (fileName.canRead()) {
		if (fileName.isFile()) return(true);
		else JOptionPane.showMessageDialog(null,
				"FILE ERROR: File is a directory");
		}
	    else JOptionPane.showMessageDialog(null,
	    			"FILE ERROR: Access denied");
	    }
	else JOptionPane.showMessageDialog(null,
				"FILE ERROR: No such file!");
	// Return

	return(false);
	}

    /* READ FILE */

    private void readFile() {

	try {
	    // Dimension data structure
	    inputFormatOkFlag=true;
	    getNumberOfLines();
	    if (inputFormatOkFlag) {
	        dataArray = new short[numRows][];
	        // Read file
	        inputDataSet();
  	        // Set have data flag to true
	        haveDataFlag = true;
		}
	    else {
	        haveDataFlag = false;
		textArea.append("Error reading file: " + fileName + "\n\n");
		runButton.setEnabled(false);
		}
	    }
	catch(IOException ioException) {
	    JOptionPane.showMessageDialog(this,"Error reading File",
			 "Error 5: ",JOptionPane.ERROR_MESSAGE);
	    closeFile();
	    System.exit(1);
	    }
	}

    /* GET NUMBER OF LINES */

    /** Gets number of lines in file and prepares data structure. */

    private void getNumberOfLines() throws IOException {
        int counter = 0;

	// Open the file
	openFile();

	// Loop through file incrementing counter
	// get first row.
	String line = fileInput.readLine();
	while (line != null) {
	    checkLine(counter+1,line);
	    StringTokenizer dataLine = new StringTokenizer(line);
            int numberOfTokens = dataLine.countTokens();
	    if (numberOfTokens == 0) break;
	    counter++;
            line = fileInput.readLine();
	    }

	numRows = counter;
        closeFile();
	}

    /* CHECK LINE */

    /** Check whether input file is of appropriate numeric input. */

    private void checkLine(int counter, String str) {

        for (int index=0;index <str.length();index++) {
            if (!Character.isDigit(str.charAt(index)) &&
	    			!Character.isWhitespace(str.charAt(index))) {
                JOptionPane.showMessageDialog(null,"FILE INPUT ERROR:\ncharcater " +
		       "on line " + counter + " is not a digit or white space");
	        inputFormatOkFlag = false;
		break;
		}