数据挖掘系列003 关联规则ECLAT算法

关联规则用于发现交易数据中，不同商品之间的关系，这些规则反映了顾客的购买行为模式。如顾客经常在购买A商品的时候也会购买B商品，著名的“啤酒与尿布”的案例就是关联规则的成功应用案例

导语

不同于Apriori和FP算法所采用的按照交易事务来水平划分项集的数据挖掘方式，把数据集中的项划归到每个事务下，ECLAT算法采用了另一种思路：把数据集中的事务划归到每个项下。本文采用如下数据：

	A;B;E;
	B;D;
	B;C;
	A;B;D
	A;C;
	B;C;
	A;C;
	A;B;C;E;
	A;B;C;

下表左边为Apriori、FP算法所采用的数据结构，右边是ECLAT算法所采用的数据结构两部分：

算法介绍

ECLAT算法把数据库事务划归到每个项下，使得该算法相较于Apriori和FP-Growth算法可以基于集合运算更简便的得到频繁项集，该算法得到频繁项集的基本思路如下：

1. 首先对数据库进行一次遍历，生成项对应的事务集，如上图左上角表格T1。
2. 然后把所有项作为一个集合I_all，求该集合的子集,设第i个子集为I_i,如上图中橘黄色箭头指示的集合列表。
3. 对每个子集I_i中的项对应的事务集合求并集为T_i，如上图蓝色箭头指示的集合列表
4. T_i中元素个数大于阀值的集合，即为频繁项集。

如果设置频繁项的频次阀值为2，则上图中红色的集合为频繁项集。

简单实现

ECLAT 算法只需要一次数据库的遍历，生成以项（item）为key，以出现该item的交易事务Id所组成的集合为value的map。然后频繁项集就可以基于该map获取到。其获取频繁项集的实现代码如下：

package association;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

import set.SetUtils;

public class ECLAT {
	public static String SPLIT = ";";
	public static int F = 2;
	public static double C = 0.7;

	public static List<String> transList = new ArrayList<String>();

	static {
		transList.add("T1;A;B;E;");
		transList.add("T2;B;D;");
		transList.add("T3;B;C;");
		transList.add("T4;A;B;D;");
		transList.add("T5;A;C;");
		transList.add("T6;B;C;");
		transList.add("T7;A;C;");
		transList.add("T8;A;B;C;E;");
		transList.add("T9;A;B;C;");
	}


	private Map<String,Set<String>> datas;


	private void etl(){
		datas = new HashMap<String, Set<String>>();
		for (String string : transList) {
			String[] records = string.split(SPLIT);
			for(int i = 1;i<records.length;i++){
				if(!datas.containsKey(records[i])){
					datas.put(records[i],new HashSet<String>());
				}
				datas.get(records[i]).add(records[0]);
			}
		}
	}

	public List<String> getFItems(){
		etl();
		Set<String> keys = datas.keySet();
		Set<String> items = new HashSet<String>();
		items.addAll(keys);
		ArrayList<Set<String>> subsets = SetUtils.getSubset(items);
		Set<String> tmp = new HashSet<String>();
		List<String> fItems = new ArrayList<String>();
		for (Set<String> set : subsets) {
			tmp.clear();
			Iterator<String> it = set.iterator();
			if(it.hasNext()){
				tmp.addAll(datas.get(it.next()));
				while(it.hasNext() && tmp.size()>=F){
					tmp.retainAll(datas.get(it.next()));
				}
			}
			if(tmp.size()>=F){
				fItems.add(set.toString()+":"+tmp.size());
			}
		}
		return fItems;
	}

	public static void main(String[] args) {
		ECLAT eclat = new  ECLAT();
	
		List<String> fItems = eclat.getFItems();
		for (String string : fItems) {
			System.out.println(string);
		}
	}
}