数据挖掘：关联规则

时间限制: 5秒  内存限制: 64M

数据挖掘有很广泛的应用领域。其中，最广为人知且易于理解的就是关联规则了。所谓关联规则，有时也称之为购物篮分析 (market basket analysis)，其主要目的是在一个数据集中找出不同项之间的关系。例如，购买鞋的顾客，有10%的可能也会买袜子；60%的买面包的顾客，也会买牛奶。一个有名的例子就是"尿布和啤酒"的故事了。

美国沃尔玛连锁店超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售，表面上看似毫不相关的商品。但是这个奇怪的举措却使尿布和啤酒的销量都增加了。有人分析，原因可能是美国的妇女们经常会嘱咐她们的丈夫下班以后要为孩子买尿布。而丈夫在买完尿布之后又要顺手买回自己爱喝的啤酒，因此啤酒和尿布在一起购买的机会就变得很大了。沃尔玛是如何发现了尿布和啤酒之间的关系呢？正是数据挖掘的关联规则思想。商家请人对超市一年多原始交易数字进行了详细的分析，分析的结果揭示了这对神奇的组合。

关联规则在其它应用场合也有很好的应用。例如：在商业销售上，关联规则可用于交叉销售，以得到更大的收入；在保险业务方面，如果出现了不常见的索赔要求组合，则可能为欺诈，需要作进一步的调查。在医疗方面，可找出可能的治疗组合；在银行方面，对顾客进行分析，可以推荐感兴趣的服务等等。

发现关联规则的算法目前已经有很多种，其中最基本的是Apriori算法。由Rakesh Agrawal 在 1994 年提出的，详细的介绍参考这里《Fast Algorithms for Mining Association Rules》。

 

简单地说，关联规则的目标是发现出现频度较高的组合。比如假设上图中，Database TDB中A、B、C、D、E分别代表不同的商品， Tid=10的用户同时购买了A,C,D三种商品，Tid=20的用户同时购买了B,C,E三种商品，等等。

 

该算法寻找所有出现次数超过支持度的子项。所谓支持度，就是至少要出现的次数。例如，A,C的组合共出现了2次(Tid=10和30)，它的支持度就是2。对用户给定一个支持度，Apirori算法每次扫描，把出现次数不够支持度的项从候选集中去除，然后再在此基础上生成更多项组合的子集。

=====

本题要求做一个简单的关联规则的数据挖掘。为了简化，只做两项组合的频繁集，题目中的商品也只用一个字母代替。

 

输入：

最小支持度support(>1)，交易记录的数量N，紧跟着是N个具体的交易记录。

 

输出：

所有支持度≥support的二项组合，以及对应的支持度。

 

样例输入：

2□4↵

a,c,d↵

b,c,e↵

a,b,c,e↵

b,e↵

 

样例输出：

a,c:2↵

b,c:2↵

b,e:3↵

c,e:2↵

 

参考解答：请将文件重命名为Main.class然后执行。

 

 

 

 

 

import java.util.Scanner;

 public class Main{  
	 
	 public static void main(String[] args){  
		 StringBuilder sBuilder = new StringBuilder();  
		 Scanner scanner = new Scanner(System.in);
		 String str = scanner.nextLine();
		 String[] in = str.split(" ");
		 int support = Integer.parseInt(in[0]);
		 int N = Integer.parseInt(in[1]);
		 String[] arr = new String[N];
		 for(int i=0;i<N;i++){
			 arr[i] = scanner.nextLine().replaceAll(",", "");//把读入的字符串去除","，由a,b,c,d变成abcd
		 }
		 scanner.close();
		 for(int i=0;i<N;i++){
			 int len1 = arr[i].length();
			 for(int j=0;j<len1-1;j++){
				 for(int k=j+1;k<len1;k++){
					 String s = arr[i].charAt(j) + "," +arr[i].charAt(k);
					 sBuilder.append(s).append(" ");
				 }
			 }
		 }
		 String tString = sBuilder.toString().trim();//两个两个连接完成的数组，去除最后的空格
		 String[] result = tString.split(" ");//把连接成的字符串再分成数组，便于查找
		 int len2 = result.length;
		 sBuilder = new StringBuilder();//把sBuilder置为空值
		 for(int i=0;i<len2-1;i++){
			 int num = 1;
			 for(int j=i+1;j<len2;j++){
				 if(result[i].equals(result[j])){
					 num++;
				 }
			 }
			 if(num >= support && sBuilder.indexOf(result[i]) == -1){//判断是否已经输出过
				 sBuilder.append(result[i]).append(" ");//没有输出过就添加到sBuilder判断
				 System.out.println(result[i]+":"+num);
			 }
		 }
	 }     
}