aprioritgui.java

apriori算法java 带有详细注解

/* -------------------------------------------------------------------------- */
/*                                                                            */
/*                      ASSOCIATION RULE DATA MINING                          */
/*                                                                            */
/*                              Frans Coenen                                  */
/*                                                                            */
/*                          Monday 15 June 2003                               */
/*                                                                            */
/*                    Department of Computer Science                          */
/*                     The University of Liverpool                            */
/*                                                                            */
/* -------------------------------------------------------------------------- */

import java.io.*;
import java.util.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

// Other packages

public class AprioriTgui extends JFrame implements ActionListener{

    /* ------ FIELDS ------ */

    // GUI features
    private BufferedReader fileInput;
    private JTextArea textArea;
    private JButton openButton, minSupport, runButton;

    /** Ttree node structure. <P> Arrays of these structures are used to store
    nodes at the same level in any sub-branch of the T-tree.  */

    protected class TtreeNode {
    	/** The support associate wuth the itemset represented by the node. */
        protected int support = 0;
	/** A reference variable to the child (if any) of the node. */
	protected TtreeNode[] childRef = null;

	/** Default constructor */

	protected TtreeNode() {
	    }

	/** One argument constructor.
	@param sup the support value to be included in the structure. */

	private TtreeNode(int sup) {
	    support = sup;
	    }
	}

    // Data structures
    /** The reference to start of t-tree. */
    private TtreeNode[] startTtreeRef;
    /** 2-D aray to hold input data from data file */
    private short[][] dataArray = null;

    // Constants
    /** Minimum support value */
    private static final double MIN_SUPPORT = 0.0;
    /** Maximum support value */
    private static final double MAX_SUPPORT = 100.0;

    // Flags
    /** Input format PK flag */
    private boolean inputFormatOkFlag = true;
    /** Flag to indicate whether system has data or not. */
    private boolean haveDataFlag = false;
    /** Flag to indicate whether system has support value or not. */
    private boolean hasSupportFlag = false;
    /** The next level indicator flag: set to <TT>true</TT> if new level generated
    and by default. */
    private boolean nextLevelExists = true ;

    // Other fields
    /** Data file name. */
    private File fileName;
    /** Number of rows. */
    private int numRows    = 0;
    /** Number of Cols. */
    private int numCols = 0;
    /** Support. */
    private double support = 20.0;
    /** Minimum support in terms of rows. */
    private double minSupportRows = 1.0;

    public AprioriTgui(String s) {
        super(s);

	// Content pane
        Container container = getContentPane();
        container.setBackground(Color.pink);
        container.setLayout(new BorderLayout(5,5)); // 5 pixel gaps

	// Run button
	runButton = new JButton("Run");
        runButton.addActionListener(this);
	runButton.setEnabled(false);

        // Open button
        openButton = new JButton("Open File");
        openButton.addActionListener(this);

	// Input Support
	minSupport = new JButton("Add Min. Sup.");
        minSupport.addActionListener(this);

	// Button Panel
	JPanel buttonPanel = new JPanel();
	buttonPanel.setLayout(new GridLayout(1,3));
	buttonPanel.add(openButton);
	buttonPanel.add(minSupport);
	buttonPanel.add(runButton);
	container.add(buttonPanel,BorderLayout.NORTH);

	// Text area
	textArea = new JTextArea(40, 15);
	textArea.setEditable(false);
        container.add(new JScrollPane(textArea),BorderLayout.CENTER);

	// Credits Panel
	JPanel creditsPanel = new JPanel();
	creditsPanel.setBackground(Color.pink);
	creditsPanel.setLayout(new GridLayout(4,1));
	Label creditLabel1 = new Label("LUCS-KDD (Liverpool University Computer " +
				"Science - Knowledge Discovery");
	Label creditLabel2 = new Label("in Data) group Apriori-T " +
				"demonstrator.");
	Label creditLabel3 = new Label(" ");
	Label creditLabel4 = new Label("Created by Frans Coenen (17 June " +
				"2003)");
	creditsPanel.add(creditLabel1);
	creditsPanel.add(creditLabel2);
	creditsPanel.add(creditLabel3);
	creditsPanel.add(creditLabel4);
	container.add(creditsPanel,BorderLayout.SOUTH);
	}

    /* ACTION PERFORMED */

    public void actionPerformed(ActionEvent event) {
        if (event.getActionCommand().equals("Open File")) getFileName();
	if (event.getActionCommand().equals("Read File")) readFile();
        if (event.getActionCommand().equals("Add Min. Sup.")) addSupport();
	if (event.getActionCommand().equals("Run")) aprioriT();
	}

    /* ---------------------------------------------------------------- */
    /*                                                                  */
    /*                            APRIORI-T                             */
    /*                                                                  */
    /* ---------------------------------------------------------------- */

    private void aprioriT() {
 	textArea.append("Apriori-T (Minimum support threshold = " + support +
		     "%)\n-----------------------------------------\n" +
		"Generating K=1 large itemsets\n");

	// Determin mimimum support in terms of rows
	minSupportRows = numRows*support/100.0;

	// Create Top level of T-tree (First pass of dataset)
	createTtreeTopLevel();

	// Generate level 2
	generateLevel2();

	// Further passes of the dataset
	createTtreeLevelN();

	textArea.append("\n");
	outputFrequentSets();
	}

    /* CREATE T-TREE TOP LEVEL */

    /** Generates level 1 (top) of the T-tree. */

    protected void createTtreeTopLevel() {

	// Dimension and initialise top level of T-tree

	startTtreeRef = new TtreeNode[numCols+1];
	for (int index=1;index<=numCols;index++)
	    			startTtreeRef[index] = new TtreeNode();

        // Add support for each 1 itemset

	createTtreeTopLevel2();

	// Prune top level, setting any unsupport 1 itemsets to null

	pruneLevelN(startTtreeRef,1);
	}

    /** Adds supports to level 1 (top) of the T-tree. */

    protected void createTtreeTopLevel2() {

        // Loop through data set record by record and add support for each
	// 1 itemset

	for (int index1=0;index1<dataArray.length;index1++) {
	    // Non null record (if initial data set has been reordered and
	    // pruned some records may be empty!
	    if (dataArray[index1] != null) {
    	        for (int index2=0;index2<dataArray[index1].length;index2++) {
		    startTtreeRef[dataArray[index1][index2]].support++;
		    }
		}
	    }
	}

    /* CREATE T-TREE LEVEL N */

    /** Commences the process of determining the remaining levels in the T-tree
    (other than the top level), level by level in an "Apriori" manner. <P>
    Follows an add support, prune, generate loop until there are no more levels
    to generate. */

    protected void createTtreeLevelN() {
        int nextLevel=2;

	// Loop while a further level exists

	while (nextLevelExists) {
	    textArea.append("Generating K=" + nextLevel + " large itemsets\n");
	    // Add support
	    addSupportToTtreeLevelN(nextLevel);
	    // Prune unsupported candidate sets
	    pruneLevelN(startTtreeRef,nextLevel);
	    // Attempt to generate next level
	    nextLevelExists=false;
	    generateLevelN(startTtreeRef,1,nextLevel,null);
	    nextLevel++;
	    }
	}

    /* ADD SUPPORT VALUES TO T-TREE LEVEL N */

    /** Commences process of adding support to a given level in the T-tree
    (other than the top level).
    @param level the current level number (top leve = 1). */

    protected void addSupportToTtreeLevelN(int level) {
	// Loop through data set record by record
        for (int index=0;index<dataArray.length;index++) {
	    // Non null record (if initial data set has been reordered and
	    // pruned some records may be empty
	    if (dataArray[index] != null) {
	        addSupportToTtreeFindLevel(startTtreeRef,level,
				dataArray[index].length,dataArray[index]);
	        }
	    }
	}

    /* ADD SUPPORT TO T-TREE FIND LEVEL */

    /** Adds support to a given level in the T-tree (other than the top level).
    <P> Operates in a recursive manner to first find the appropriate level in
    the T-tree before processing the required level (when found).
    @param linkRef the reference to the current sub-branch of T-tree (start at
    top of tree)
    @param level the level marker, set to the required level at the start and
    then decremented by 1 on each recursion.
    @param endIndex the length of current level in a sub-branch of the T-tree.
    @param itemSet the current itemset under consideration. */

    private void addSupportToTtreeFindLevel(TtreeNode[] linkRef, int level,
    			int endIndex, short[] itemSet) {

	// At right leve;

	if (level == 1) {
	    // Step through itemSet
	    for (int index1=0;index1 < endIndex;index1++) {
		// If valid node update, i.e. a non null node
		if (linkRef[itemSet[index1]] != null) {
		    linkRef[itemSet[index1]].support++;
		    }
		}
	    }

	// At wrong level

	else {
	    // Step through itemSet
	    for (int index=0;index<endIndex;index++) {
		// If child branch step down branch
		if (linkRef[itemSet[index]] != null) {
		    if (linkRef[itemSet[index]].childRef != null)
		    	 addSupportToTtreeFindLevel(linkRef[itemSet[index]].childRef,
						level-1,index,itemSet);
		    }
		}
	    }
	}

    /*---------------------------------------------------------------------- */
    /*                                                                       */
    /*                                 PRUNING                               */
    /*                                                                       */
    /*---------------------------------------------------------------------- */

    /* PRUNE LEVEL N */

    /** Prunes the given level in the T-tree. <P> Operates in a recursive
    manner to first find the appropriate level in the T-tree before processing
    the required level (when found). Pruning carried out according to value of
    <TT>minSupport</TT> field.
    @param linkRef The reference to the current sub-branch of T-tree (start at
    top of tree)
    @param level the level marker, set to the required level at the start and
    then decremented by 1 on each recursion. */

    protected void pruneLevelN(TtreeNode [] linkRef, int level) {
        int size = linkRef.length;

	// At right leve;

	if (level == 1) {
	    // Step through level and set to null where below min support
	    for (int index1=1;index1 < size;index1++) {
	        if (linkRef[index1] != null) {
	            if (linkRef[index1].support < minSupportRows)
		    		linkRef[index1] = null;
	            }
		}
	    }

	// Wrong level

	else {
	    // Step through row
	    for (int index1=1;index1 < size;index1++) {
	        if (linkRef[index1] != null) {
		    // If child branch step down branch
		    if (linkRef[index1].childRef != null)
				pruneLevelN(linkRef[index1].childRef,level-1);
		    }
		}
	    }
	}

    /*---------------------------------------------------------------------- */
    /*                                                                       */
    /*                            LEVEL GENERATION                           */
    /*                                                                       */
    /*---------------------------------------------------------------------- */

    /* GENERATE LEVEL 2 */

    /** Generates level 2 of the T-tree. <P> The general
    <TT>generateLevelN</TT> method assumes we have to first find the right
    level in the T-tree, that is not necessary in this case of level 2. */

    protected void generateLevel2() {

	// Set next level flag

	nextLevelExists=false;

	// loop through top level

	for (int index=2;index<startTtreeRef.length;index++) {
	    // If supported T-tree node (i.e. it exists)
	    if (startTtreeRef[index] != null) generateNextLevel(startTtreeRef,
	    				index,realloc2(null,(short) index));
	    }
	}

    /* GENERATE LEVEL N */

    /** Commences process of generating remaining levels in the T-tree (other
    than top and 2nd levels). <P> Proceeds in a recursive manner level by level
    untill the required level is reached. Example, if we have a T-tree of the form:

    <PRE>
    (A) ----- (B) ----- (C)
               |         |
	       |         |
	      (A)       (A) ----- (B)
    </PRE><P>
    Where all nodes are supported and we wish to add the third level we would
    walk the tree and attempt to add new nodes to every level 2 node found.
    Having found the correct level we step through starting from B (we cannot
    add a node to A), so in this case there is only one node from which a level
    3 node may be attached.
    @param linkRef the reference to the current sub-branch of T-tree (start at
    top of tree).
    @param level the level marker, set to 1 at the start of the recursion and
    incremented by 1 on each repetition.
    @param requiredLevel the required level.
    @param itemSet the current itemset under consideration. */

    protected void generateLevelN(TtreeNode[] linkRef, int level,
    					int requiredLevel, short[] itemSet) {
	int index1;
	int localSize = linkRef.length;

	// Correct level

	if (level == requiredLevel) {
	    for (index1=2;index1<localSize;index1++) {
	        // If supported T-tree node
	    	if (linkRef[index1] != null) generateNextLevel(linkRef,index1,
					realloc2(itemSet,(short) index1));
	        }
	    }

	// Wrong level

	else {
	    for (index1=2;index1<localSize;index1++) {
	        // If supported T-tree node
	        if (linkRef[index1] != null) {
		    generateLevelN(linkRef[index1].childRef,level+1,
		    		requiredLevel,realloc2(itemSet,(short) index1));
		    }
		}
	    }