一、实验室名称：

无

二、实验项目名称：

关联规则挖掘

三、实验学时：

四、实验原理：

频繁项集产生（Frequent Itemset Generation）

其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。

规则的产生（Rule Generation）

其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则（strong rule）。

Apriori算法

性质一：如果一个项集是频繁的，则它的所有子集一定也是频繁的

性质二：相反，如果一个项集是非频繁的，则它的所有超集也一定是非频繁的

五、实验目的：

（1）学会调用WEKA包实现关联规则的挖掘

（2）自己编程实现Apriori算法

六、实验内容：

（1）学会调用WEKA包实现关联规则的挖掘

（2）自己编程实现Apriori算法

七、实验器材（设备、元器件）：

Windows eclipse

八、实验步骤：

1. 调用WEKA包实现关联规则的挖掘

打开weka，使用数据soybean.arff

选择关联规则挖掘并设置参数

Start 完成关联规则挖掘

2. 实现 Apriori 算法

读取数据
首先获取频繁一项集合（注意对于数据结构的选取提高计算效率）
利用K项频繁集生成K+1频繁候选集：自连接+剪枝
重新扫描数据集，确定K+1频繁候选集中真正频繁的项集
重复上面两步

实验代码：

package shuwa2;

import java.io.*;
import java.util.*;
 
public class Apriori {
 
	static String filePath = "d:\\1.txt";
	static ArrayList<ArrayList<String>> D = new ArrayList<ArrayList<String>>();// 事务数据库
	static HashMap<ArrayList<String>, Double> C = new HashMap<ArrayList<String>, Double>();// 项目集
	static HashMap<ArrayList<String>, Double> L = new HashMap<ArrayList<String>, Double>();// 候选集
	static double min_support = 0.5;// 最小支持度
	static double min_confident = 0.7;// 最小置信度
 
	// 用于存取候选集每次计算结果，最后计算关联规则，就不用再次遍历事务数据库，这么麻烦了。
	static HashMap<ArrayList<String>, Double> L_ALL = new HashMap<ArrayList<String>, Double>();
 
	/**
	 * 将txt中的二维表读入T中
	 * 
	 * @param filePath
	 *            TXT的文件路径，注意文件路径分隔符必须写成\\
	 * @return ArrayList<ArrayList<String>>，存放每行元素List的List
	 */
	public static ArrayList<ArrayList<String>> readTable(String filePath) {
		ArrayList<ArrayList<String>> T = new ArrayList<ArrayList<String>>();
		Scanner scanner;
		try {
			scanner = new Scanner(new File(filePath));// 指定读入文件
			while (scanner.hasNext()) {
				T.add(new ArrayList<String>(Arrays.asList(scanner.nextLine()
						.split(" "))));
			}
			scanner.close();// 必须关闭这个流，否则有警告。
		} catch (FileNotFoundException e) {
			System.out.println("文件不存在！请检查路径。");
		}
		return T;
	}
 
	// 剪枝步，删去C少于最小支持度的元素，形成L
	public static void pruning(HashMap<ArrayList<String>, Double> C,
			HashMap<ArrayList<String>, Double> L) {
		L.clear();
		// 根据项目集生成候选集
		L.putAll(C);
		// 删除少于最小支持度的元素
		ArrayList<ArrayList<String>> delete_key = new ArrayList<ArrayList<String>>();
		for (ArrayList<String> key : L.keySet()) {
			if (L.get(key) < min_support) {
				delete_key.add(key);
			}
		}
		for (int i = 0; i < delete_key.size(); i++) {
			L.remove(delete_key.get(i));
		}
	}
 
	/**
	 * 初始化事务数据库、项目集、候选集
	 */
	public static void init() {
		D = readTable(filePath);
 
		// 扫描事务数据库。生成项目集，支持度=改元素在事务数据库出现的次数/事务数据库的事务数
		for (int i = 0; i < D.size(); i++) {
			for (int j = 0; j < D.get(i).size(); j++) {
				String[] e = { D.get(i).get(j) };
				ArrayList<String> item = new ArrayList<String>(Arrays.asList(e));
				if (!C.containsKey(item)) {
					C.put(item, 1.0 / D.size());
				} else {
					C.put(item, C.get(item) + 1.0 / D.size());
				}
			}
		}
 
		pruning(C, L);// 剪枝
 
		L_ALL.putAll(L);
 
	}
 
	// 两个整数集求并集
	public static ArrayList<String> arrayListUnion(
			ArrayList<String> arraylist1, ArrayList<String> arraylist2) {
		ArrayList<String> arraylist = new ArrayList<String>();
		arraylist.addAll(arraylist1);
		arraylist.addAll(arraylist2);
		arraylist = new ArrayList<String>(new HashSet<String>(arraylist));
		return arraylist;
	}
 
	/**
	 * 迭代求出最终的候选频繁集
	 * 
	 * @param C
	 *            完成初始化的项目集
	 * @param L
	 *            完成初始化的候选集
	 * @return 最终的候选频繁集
	 */
	public static HashMap<ArrayList<String>, Double> iteration(
			HashMap<ArrayList<String>, Double> C,
			HashMap<ArrayList<String>, Double> L) {
		HashMap<ArrayList<String>, Double> L_temp = new HashMap<ArrayList<String>, Double>();// 用于判断是否结束剪枝的临时变量
 
		int t = 1;// 迭代次数
		while (L.size() > 0) {// 一旦被剪枝后剪干净，剪枝之前则是最终要求的结果。
			t++;
			L_temp.clear();
			L_temp.putAll(L);
			// 一、连接步
			C.clear();
			// 1.将L中的项以一定的规则两两匹配
			ArrayList<ArrayList<String>> L_key = new ArrayList<ArrayList<String>>(
					L.keySet());
			for (int i = 0; i < L_key.size(); i++) {
				for (int j = i + 1; j < L_key.size(); j++) {
					ArrayList<String> C_item = new ArrayList<String>();
					C_item = new ArrayList<String>(arrayListUnion(L_key.get(i),
							L_key.get(j)));
					if (C_item.size() == t) {
						C.put(C_item, 0.0);// 频繁项集的所有非空子集都必须是频繁的
					}
				}
			}
			// 2.通过扫描D，计算此项的支持度
			for (ArrayList<String> key : C.keySet()) {
				for (int i = 0; i < D.size(); i++) {
					if (D.get(i).containsAll(key)) {
						C.put(key, C.get(key) + 1.0 / D.size());
					}
				}
			}
			// System.out.println(C);
			// 二、剪枝步
			pruning(C, L);
			// System.out.println(L);
			// System.out.println("===");
 
			L_ALL.putAll(L);
		}
 
		return L_temp;
	}
 
	// 求一个集合的所有子集
	public static ArrayList<ArrayList<String>> getSubset(ArrayList<String> L) {
		if (L.size() > 0) {
			ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
			for (int i = 0; i < Math.pow(2, L.size()); i++) {// 集合子集个数=2的该集合长度的乘方
				ArrayList<String> subSet = new ArrayList<String>();
				int index = i;// 索引从0一直到2的集合长度的乘方-1
				for (int j = 0; j < L.size(); j++) {
					// 通过逐一位移，判断索引那一位是1，如果是，再添加此项
					if ((index & 1) == 1) {// 位与运算，判断最后一位是否为1
						subSet.add(L.get(j));
					}
					index >>= 1;// 索引右移一位
				}
				result.add(subSet); // 把子集存储起来
			}
			return result;
		} else {
			return null;
		}
	}
 
	// 判断两个集合相交是否为空
	public static boolean intersectionIsNull(ArrayList<String> l1,
			ArrayList<String> l2) {
		Set<String> s1 = new HashSet<String>(l1);
		Set<String> s2 = new HashSet<String>(l2);
 
		s1.retainAll(s2);
		if (s1.size() > 0) {
			return false;
		} else {
			return true;
		}
	}
 
	/**
	 * 根据最终的关联集，根据公式计算出各个关联事件
	 */
	public static void connection() {
		for (ArrayList<String> key : L.keySet()) {// 对最终的关联集各个事件进行判断
			ArrayList<ArrayList<String>> key_allSubset = getSubset(key);
			// System.out.println(key_allSubset);
			for (int i = 0; i < key_allSubset.size(); i++) {
				ArrayList<String> item_pre = key_allSubset.get(i);
				if (0 < item_pre.size() && item_pre.size() < key.size()) {// 求其非空真子集
					// 各个非空互补真子集之间形成关联事件
					double item_pre_support = L_ALL.get(item_pre);
					for (int j = 0; j < key_allSubset.size(); j++) {
						ArrayList<String> item_post = key_allSubset.get(j);
						if (0 < item_post.size()
								&& item_post.size() < key.size()
								&& arrayListUnion(item_pre, item_post).equals(
										key)
								&& intersectionIsNull(item_pre, item_post)) {
							double item_post_support = L_ALL.get(item_post);// 互补真子集的支持度比则是事件的置信度
							double confident = item_pre_support
									/ item_post_support; // 事件的置信度
							if (confident > min_confident) {// 如果事件的置信度大于最小置信度
								System.out
										.println(item_pre + "==>" + item_post);// 则是一个关联事件
								// System.out.println(item_pre_support + "==>" +
								// item_post_support);
							}
						}
 
					}
				}
			}
		}
	}
 
	public static void main(String[] args) {
 
		init();
		System.out.println(D); System.out.println(C); System.out.println(L);
		System.out.println("===");
		L = iteration(C, L);
		System.out.println(L); System.out.println(L_ALL);
		System.out.println("===");
		connection();
 
	}
}

九、实验数据及结果分析：

实验数据：

I1 I2 I3 I4

I1 I2 I3

I3 I4

I1 I2 I5

实验结果：

[[I1, I2, I3, I4], [I1, I2, I3], [I3, I4], [I1, I2, I5]]

{[I1]=0.75, [I2]=0.75, [I3]=0.75, [I4]=0.5, [I5]=0.25}

{[I2]=0.75, [I3]=0.75, [I4]=0.5, [I1]=0.75}

===

{[I1, I2, I3]=0.5}

{[I1, I3]=0.5, [I2, I3]=0.5, [I1, I2]=0.75, [I3, I4]=0.5, [I1]=0.75, [I2]=0.75, [I3]=0.75, [I4]=0.5, [I1, I2, I3]=0.5}

===

[I1]==>[I2, I3]

[I2]==>[I1, I3]

[I1, I2]==>[I3]

[I3]==>[I1, I2]

关联数据挖掘成功

十、实验结论：

无

十一、总结及心得体会：

掌握了weka图形界面对关联规则挖掘的使用，自己尝试实现了apriori算法，对关联规则挖掘有了更高的认识

十二、对本实验过程及方法、手段的改进建议：

无

关联规则挖掘

一、实验室名称：

二、实验项目名称：

三、实验学时：

四、实验原理：

五、实验目的：

六、实验内容：

七、实验器材（设备、元器件）：

八、实验步骤：

1. 调用WEKA包实现关联规则的挖掘

2. 实现 Apriori 算法

九、实验数据及结果分析：

十、实验结论：

十一、总结及心得体会：

十二、对本实验过程及方法、手段的改进建议：

暂无评论

发表评论取消回复

关联规则挖掘

一、 实验室名称：

二、 实验项目名称：

三、 实验学时：

四、 实验原理：

五、 实验目的：

六、 实验内容：

七、 实验器材（设备、元器件）：

八、 实验步骤：

1. 调用WEKA包实现关联规则的挖掘

2. 实现 Apriori 算法

九、 实验数据及结果分析：

十、 实验结论：

十一、 总结及心得体会：

十二、 对本实验过程及方法、手段的改进建议：

暂无评论

发表评论 取消回复

一、实验室名称：

二、实验项目名称：

三、实验学时：

四、实验原理：

五、实验目的：

六、实验内容：

七、实验器材（设备、元器件）：

八、实验步骤：

九、实验数据及结果分析：

十、实验结论：

十一、总结及心得体会：

十二、对本实验过程及方法、手段的改进建议：

发表评论取消回复