aprioriapplet.java

java实现的Applet的Appriori算法

import java.awt.*;
import java.applet.*;
import java.awt.event.*;
import java.lang.*;
import java.io.*;
import javax.swing.JOptionPane;
import java.util.StringTokenizer;
import java.util.Random;
import java.util.Vector;

public class AprioriApplet extends Applet
						implements ActionListener {

	private Label lblItems = new Label("Items");
	private TextField tfItems = new TextField("beef,pork,veel,cheese,bag,milk,juice,salsa,ice-cream,bread,bacon,oil,sausage,onion,tomato,potato,cookies,jam,butter,water");

	private Label lblMinSup = new Label("Minimum Support");
	private TextField tfMinSup = new TextField("5%");

	private Label lblTrans = new Label("Number of Transactions");
	private TextField tfTrans = new TextField("100");

	private Label lblMinConf = new Label("Minimum Confidence");
	private TextField tfMinConf = new TextField("40%");

	private Button btnTransaction = new Button("Create Transactions");
	private Button btnRule = new Button("Identify Rules");
	private List lstTransactions = new List();
	private List lstRules = new List();

	private Apriori assorule = null;

    public void init() {
		btnTransaction.addActionListener(this);
		btnRule.addActionListener(this);

		setLayout(null);
		setSize(600, 600);

		lblItems.setBounds(10, 10, 35, 22);
		add(lblItems);
		tfItems.setBounds(48, 10, 542, 22);
		add(tfItems);

		lblTrans.setBounds(10, 35, 135, 22);
		add(lblTrans);
		tfTrans.setBounds(155, 35, 50, 22);
		add(tfTrans);

		lblMinSup.setBounds(220, 35, 100, 22);
		add(lblMinSup);
		tfMinSup.setBounds(323, 35, 50, 22);
		add(tfMinSup);

		lblMinConf.setBounds(380, 35, 120, 22);
		add(lblMinConf);
		tfMinConf.setBounds(510, 35, 50, 22);
		add(tfMinConf);

		btnTransaction.setBounds(75, 60, 150, 26);
		add(btnTransaction);

		btnRule.setBounds(375, 60, 150, 26);
		add(btnRule);

		lstTransactions.setBounds(10, 90, 285, 500);
		add(lstTransactions);

		lstRules.setBounds(305, 90, 280, 500);
		add(lstRules);

		assorule = new Apriori(lstTransactions, lstRules);
	}

    private double getDoubleValue(String str_num){
		boolean percentage = false;
		if(str_num.indexOf("%") > 0){
			str_num = str_num.substring(0, str_num.length()-1);
			percentage = true;
		}
		double value = Double.parseDouble(str_num);
		if(percentage){
			value /= 100;
		}

		return value;
	}

    public void actionPerformed(ActionEvent ae){
		if(ae.getSource() == btnTransaction){
			int transNum = Integer.parseInt(tfTrans.getText());
			assorule.setOptions(tfItems.getText(), transNum);
			assorule.createTransactions();
		} else {
			if(lstTransactions.getItemCount() == 0){
				int transNum = Integer.parseInt(tfTrans.getText());
				assorule.setOptions(tfItems.getText(), transNum);
				assorule.createTransactions();
			}
			double minSup = getDoubleValue(tfMinSup.getText());
			double minConf = getDoubleValue(tfMinConf.getText());

			assorule.setOptions(minSup, minConf);
			assorule.identifyRules();
		}
	}
}

class Apriori {
	private int trans_number;
	private double min_support;
	private double min_confidence;

	private List lstTransactions;
	private List lstRules;

	Vector vec_items = new Vector();
	Vector vec_transactions = new Vector();
	Vector vec_rules = new Vector();

	public Apriori(List lst_trans, List lst_rules){
		trans_number = 100;
		min_support = 0.2;
		min_confidence = 0.6;

		lstTransactions = lst_trans;
		lstRules = lst_rules;
	}

	public void setOptions(String s_items, int trans_num,
					double min_sup, double min_conf)
	{
		trans_number = trans_num;
		min_support = min_sup;
		min_confidence = min_conf;

		iniItems(s_items);
	}

	public void setOptions(String s_items, int trans_num)
	{
		trans_number = trans_num;
		iniItems(s_items);
	}

	public void setOptions(double min_sup, double min_conf){
		min_support = min_sup;
		if(min_support > 1.0){
			min_support /= trans_number;
		}
		min_confidence = min_conf;
	}

	public void iniItems(String stritems) {
		vec_items.removeAllElements();
		StringTokenizer st = new StringTokenizer(stritems, ",");
		int index = 0;

		while(st.hasMoreElements()) {
			String str_item = st.nextToken().trim();
			Item item = new Item(index, str_item);
			vec_items.add(item);
			index++;
        }
	}

	public void createTransactions() {
		vec_transactions.removeAllElements();
		lstTransactions.removeAll();

		Random rnd_num = new Random();
		Random rnd_item = new Random();

		int allitems = vec_items.size();
		int maxitems = allitems/2;
		for(int i=0; i<trans_number; i++) {
			StringBuffer transaction = new StringBuffer();
			StringBuffer s_trans = new StringBuffer();
			int num = rnd_num.nextInt(maxitems-2)+2;	//number of items in this transaction

			Vector created = new Vector();
			while (num>0)
			{
				int item_no = rnd_item.nextInt(allitems);
				if(created.indexOf(new Integer(item_no)) < 0)
				{
					Item temp_item = (Item)vec_items.elementAt(item_no);
					transaction.append(""+item_no);
					s_trans.append(temp_item.getItemName());
					if(num > 1) {
						transaction.append(",");
						s_trans.append(",");
					}

					num--;
					created.addElement(new Integer(item_no));
				}
			}
			created = null;

			vec_transactions.addElement(transaction.toString());

			lstTransactions.add(""+(i+1)+":"+s_trans);
		}//end for i
	}

	public void identifyRules() {
		vec_rules.removeAllElements();
		lstRules.removeAll();

		indexItems();

		//start with two item rules
		int item_count = vec_items.size();
		int min_supp = (int)(min_support*trans_number);
		for(int i=0; i<item_count-1; i++){
			Item item1 = (Item)vec_items.elementAt(i);
			if(item1.getTransSetSize() < min_supp){
				continue;
			}
			//lstRules.add(item1.toString());
			for(int j=i+1; j<item_count; j++){
				Item item2 = (Item)vec_items.elementAt(j);
				if(item2.getTransSetSize() < min_supp){
					continue;
				}
				//lstRules.add(item2.toString());

				Vector v_intersect = item1.interTransSet(item2);
				int supp = v_intersect.size();
				double conf = (double)supp/(double)item1.getTransSetSize();
				if(supp >= min_supp && conf >= min_confidence) {
					Vector vec1 = new Vector();
					vec1.add(item1);
					Vector vec2 = new Vector();
					vec2.add(item2);
					Rule new_rule = new Rule(vec1, vec2, (double)supp/trans_number,
						conf, item1.getTransSet(), item2.getTransSet(), v_intersect);
					vec_rules.add(new_rule);

					lstRules.add(new_rule.toString());
				}

				conf = supp/item2.getTransSetSize();
				if(supp >= min_supp && conf >= min_confidence) {
					Vector vec1 = new Vector();
					vec1.add(item2);
					Vector vec2 = new Vector();
					vec2.add(item1);
					lstRules.add(""+supp+" "+conf);
					Rule new_rule = new Rule(vec1, vec2, (double)supp/trans_number,
						conf, item2.getTransSet(), item1.getTransSet(), v_intersect);
					vec_rules.add(new_rule);

					lstRules.add(new_rule.toString());
				}
			}
		}

		//find all others
		int new_num = 0;
		int start_pos = 0;
		boolean done = false;
		while(!done){
			done = true;
			start_pos = new_num;
			new_num = vec_rules.size();
			lstRules.add("");
			for(int i=0; i<item_count; i++){
				Item item = (Item)vec_items.elementAt(i);
				if(item.getTransSetSize() < min_supp){
					continue;
				}
				for(int j=start_pos; j<new_num; j++) {
					Rule rule = (Rule)vec_rules.elementAt(j);

					//check support first
					Vector v_intersect = rule.interSuppSet(item);
					int supp = v_intersect.size();
					if(supp < min_supp){
						v_intersect = null;
						continue;
					}

					//check association
					if(!rule.isInCause(item) && !rule.isInEffect(item)){
						Vector v_new_cause_trans = rule.interCauseSet(item);
						double conf = (double)supp/(double)v_new_cause_trans.size();
						if(conf >= min_confidence){
							Vector v_new_cause = new Vector(rule.cause);
							v_new_cause.add(item);
							Rule new_rule = new Rule(v_new_cause, rule.effect,
								(double)supp/trans_number, conf, v_new_cause_trans,
								rule.vec_effect, v_intersect);
							addRule(start_pos, vec_rules.size(), new_rule);
							//vec_rules.add(new_rule);
							//lstRules.add(new_rule.toString());
							done = false;
						}

						Vector v_new_effect_trans = rule.interEffectSet(item);
						conf = (double)supp/(double)v_new_effect_trans.size();
						if(conf >= min_confidence){
							Vector v_new_effect = new Vector(rule.effect);
							v_new_effect.add(item);
							Rule new_rule = new Rule(rule.cause, v_new_effect,
								(double)supp/trans_number, conf, rule.vec_cause,
								v_new_effect_trans, v_intersect);
							addRule(start_pos, vec_rules.size(), new_rule);
							//vec_rules.add(new_rule);
							//lstRules.add(new_rule.toString());
							done = false;
						}
					}
				}
			}
		}

		if(vec_rules.size() == 0){
			lstRules.add("no association rules found.");
		}
	}

	private void addRule(int start_pos, int end_pos, Rule rule){
		for(int i=start_pos; i<end_pos; i++){
			if(vec_rules.elementAt(i).equals(rule)){
				return;
			}
		}

		vec_rules.add(rule);
		lstRules.add(rule.toString());
	}

	private void indexItems() {
		for(int i=0; i<vec_items.size(); i++){
			Item temp_item = (Item)vec_items.elementAt(i);
			temp_item.clearTransSet();
		}

		for(int i=0; i<vec_transactions.size(); i++){
			String str_trans = (String)vec_transactions.elementAt(i);
			StringTokenizer st = new StringTokenizer(str_trans, ",");
			while(st.hasMoreElements()) {
				int item_no = Integer.valueOf(st.nextToken().trim()).intValue();
				Item item = (Item)vec_items.elementAt(item_no);
				item.addTransaction(i);
        	}
		}
	}
}

class Item {

	private int item_no = -1;
	private String item_name;
	private Vector trans_set = new Vector();

	public Item(int new_no, String name) {
		item_no = new_no;
		item_name = name;
	}

	public int getItemNo(){
		return item_no;
	}

	public String getItemName(){
		return item_name;
	}

	public void addTransaction(int trans_no) {
		if(trans_set.indexOf(new Integer(trans_no)) < 0) {
			trans_set.addElement(new Integer(trans_no));
		}
	}

	public void clearTransSet(){
		trans_set.removeAllElements();
	}

	public int getTransSetSize(){
		return trans_set.size();
	}

	public String getTransSetText(){
		String str_set=""+item_no+":";
		for(int i=0; i<trans_set.size(); i++){
			str_set += ((Integer)trans_set.elementAt(i)).intValue();
			str_set += ",";
		}
		return str_set;
	}

	public String toString(){
		return getItemName();
	}

	public Vector getTransSet(){
		return trans_set;
	}

	public Vector interTransSet(Item item2){
		Vector intersection = new Vector();
		Vector trans_set2 = item2.getTransSet();
		for(int i=0; i<trans_set.size(); i++){
			if(trans_set2.indexOf(trans_set.elementAt(i)) >= 0){
				intersection.add(trans_set.elementAt(i));
			}
		}
		return intersection;
	}
}

class Rule {

	Vector cause;
	Vector effect;
	double support = 0.0;
	double confidence = 0.0;

	Vector vec_cause;
	Vector vec_effect;
	Vector vec_support;

	public Rule(Vector v_cause, Vector v_effect, double supp,
			double conf, Vector v_cause_trans, Vector v_effect_trans, Vector v_supp_trans) {
		cause = v_cause;
		effect = v_effect;
		support = supp;
		confidence = conf;
		vec_cause = v_cause_trans;
		vec_effect = v_effect_trans;
		vec_support = v_supp_trans;
	}

	public boolean isInCause(Item item) {
		return (cause.indexOf(item) >= 0);
	}

	public boolean isInEffect(Item item){
		return (effect.indexOf(item) >= 0);
	}

	public String toString() {
		String srule = getItemsText(cause) + " --> " + getItemsText(effect);
		srule += "  ("+(int)(support*100)+"%, "+(int)(confidence*100)+"%)";
		return srule;
	}

	private String getItemsText(Vector vec) {
		String str_items = "[";

		for(int i=0; i<vec.size(); i++) {
			if(i!=0){
				str_items += ",";
			}
			str_items += vec.elementAt(i).toString();
		}
		str_items += "]";

		return str_items;
	}

	public Vector interCauseSet(Item item){
		Vector intersection = new Vector();
		Vector trans_set = item.getTransSet();
		for(int i=0; i<vec_cause.size(); i++){
			if(trans_set.indexOf(vec_cause.elementAt(i)) >= 0){
				intersection.add(vec_cause.elementAt(i));
			}
		}
		return intersection;
	}

	public Vector interEffectSet(Item item){
		Vector intersection = new Vector();
		Vector trans_set = item.getTransSet();
		for(int i=0; i<vec_effect.size(); i++){
			if(trans_set.indexOf(vec_effect.elementAt(i)) >= 0){
				intersection.add(vec_effect.elementAt(i));
			}
		}
		return intersection;
	}

	public Vector interSuppSet(Item item){
		Vector intersection = new Vector();
		Vector trans_set = item.getTransSet();
		for(int i=0; i<vec_support.size(); i++){
			if(trans_set.indexOf(vec_support.elementAt(i)) >= 0){
				intersection.add(vec_support.elementAt(i));
			}
		}
		return intersection;
	}

	public boolean equals(Rule rule2){
		boolean same = (cause.size() == rule2.cause.size());
		same &= (effect.size() == rule2.effect.size());
		if(!same){
			return false;
		}

		for(int i=0; i<cause.size(); i++){
			if(rule2.cause.indexOf(cause.elementAt(i)) < 0){
				return false;
			}
		}

		for(int i=0; i<effect.size(); i++){
			if(rule2.effect.indexOf(effect.elementAt(i)) < 0){
				return false;
			}
		}

		return true;
	}
}