ECLAT处理垂直数据格式算法实现

算法说明：
1. 构造垂直数据格式，把原始数据的事务对应的元素集变为由元素对应的事务集
2. 对垂直数据格式中的元素Apriori算法
2.1 构造频繁1项集：遍历垂直数据格式中的元素并找出其事务集大小满足最小支持度的元素 作为频繁1项集
2.2 递归由频繁k-1项集构造频繁k项集：
   2.2.1 根据Apriori方法判断两个k-1项集是否可连接为项集
   2.2.2 对于已连接的k项集，判断它的所有k-1项集是否都在频繁k-1项集中出现
   2.2.3 对于满足2.2.2的k项集，判断其支持度是否满足条件

package com.ustc.eclat;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class Eclat {

	private int minSup;

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		/**
		 * 1. 构造垂直数据格式，把原始数据的事务对应的元素集变为由元素对应的事务集 
        * 2. 对垂直数据格式中的元素Apriori算法 
           * 2.1 构造频繁1项集：遍历垂直数据格式中的元素并找出其事务集大小满足最小支持度的元素 作为频繁1项集 
           * 2.2 递归由频繁k-1项集构造频繁k项集： 
              * 2.2.1 根据Apriori方法判断两个k-1项集是否可连接为项集
              * 2.2.2 对于已连接的k项集，判断它的所有k-1项集是否都在频繁k-1项集中出现 
              * 2.2.3 对于满足2.2.2的k项集，判断其支持度是否满足条件
		 * 
		 */
		long startTime = System.currentTimeMillis();
		Eclat eclat = new Eclat();
		/*
		 * eclat.setMinSup(2); List<String> datas = eclat.buildData(); //构造数据集
		 */
		eclat.setMinSup(1000);
		List<String> datas = eclat.buildData("retail.dat");
		Map<String, Set<String>> itemSetMap = eclat.buildItemSet(datas); // 构造垂直数据格式
		// eclat.printVItemSet(itemSetMap);
		eclat.buildF1Items(itemSetMap);
		eclat.printItemSet(itemSetMap.keySet(), 1);
		int i = 2;
		do {

			itemSetMap = eclat.buildFreqItemSet(itemSetMap);
			eclat.printItemSet(itemSetMap.keySet(), i);
			i++;
		} while (itemSetMap.size() != 0);
		long endTime = System.currentTimeMillis();
		System.out.println("共用时：" + (endTime - startTime) + "ms");

		// buildFreqItemSet(itemSetMap); //构造频繁集
	}

	/**
	 * 1.构造数据集
	 */
	public List<String> buildData(String... fileName) {

		List<String> data = new ArrayList<String>();
		if (fileName.length != 0) {
			File file = new File(fileName[0]);
			try {
				BufferedReader reader = new BufferedReader(new FileReader(file));
				String line;
				while ((line = reader.readLine()) != null) {
					data.add(line);
				}

			} catch (FileNotFoundException e) {

				e.printStackTrace();
			} catch (IOException e) {

				e.printStackTrace();
			}
		} else {

			data.add("I1 I2 I5");
			data.add("I2 I4");
			data.add("I2 I3");
			data.add("I1 I2 I4");
			data.add("I1 I3");
			data.add("I2 I3");
			data.add("I1 I3");
			data.add("I1 I2 I3 I5");
			data.add("I1 I2 I3");
		}
		return data;
	}

	/**
	 * 2.构造垂直数据格式 Map-Key为事务中的每一个频繁元素项 Map-Value为每一个事务项对应的事务行的集合
	 * 
	 * @param datas
	 * @return
	 */
	public Map<String, Set<String>> buildItemSet(List<String> datas) {
		Map<String, Set<String>> itemSetMap = new HashMap<String, Set<String>>();
		Set<String> tranSet; // 事务集
		String[] items;
		int lineNum = 1; // 事务行号从1开始
		for (String data : datas) { // 事务编号以"T" + 事务行号的形式表示;每一条data记录为一行.
			String tran = "T" + lineNum;
			items = data.trim().split(" ");
			for (String item : items) {
				if (itemSetMap.get(item) == null) {
					tranSet = new HashSet<String>();
					tranSet.add(tran);
					itemSetMap.put(item, tranSet);
				} else {
					itemSetMap.get(item).add(tran);
				}
			}
			lineNum++;
		}
		return itemSetMap;
	}

	/**
	 * 3. 由垂直数据格式构造频繁1项集(这里直接在垂直数据格式上进行操作了)
	 * 
	 * @param itemSetMap
	 */
	public void buildF1Items(Map<String, Set<String>> itemSetMap) {
		String[] items = itemSetMap.keySet().toArray(new String[0]);
		for (String item : items) {
			if (itemSetMap.get(item).size() < this.minSup) {
				itemSetMap.remove(item);
			}
		}
	}

	/**
	 * 4 由频繁1项集开始构造频繁项集
	 */
	public Map<String, Set<String>> buildFreqItemSet(
			Map<String, Set<String>> preItemSetMap) {

		String[] items = preItemSetMap.keySet().toArray(new String[0]);
		Map<String, Set<String>> result = new HashMap<String, Set<String>>();
		for (int i = 0; i < items.length - 1; i++) {
			for (int j = i + 1; j < items.length; j++) {
				String[] iItems = items[i].split(" ");
				String[] jItems = items[j].split(" ");
				if (this.isCanLink(iItems, jItems)) { // 如果两个k-1项集可执行连接操作，则连接成k项集
					String[] kItems = new String[iItems.length + 1];
					int k = 0;
					for (; k < iItems.length; k++) {
						kItems[k] = iItems[k];
					}
					kItems[k] = jItems[k - 1];
					Arrays.sort(kItems); // 对kItems中的元素进行排序
					// 判断kItems的所有k-1子集是否包含在items里，如果不全包括，则该k项集必定不频繁
					Set<String> kitemSet = new TreeSet<String>();
					for (String str : kItems) {
						kitemSet.add(str);
					}
					List<Set<String>> preItemSetList = new ArrayList<Set<String>>();
					for (String str : items) {
						preItemSetList.add(strToSet(str));
					}
					if (!isNeedCut(preItemSetList, kitemSet)) {
						Set<String> tranSet = this.buildIntersection(
								preItemSetMap.get(items[i]), preItemSetMap
										.get(items[j]));
						if (tranSet.size() >= this.minSup) {
							StringBuffer sb = new StringBuffer();
							for (String str : kItems) {
								sb.append(str + " ");
							}
							result.put(sb.toString().trim(), tranSet);
						}
					}

				}
			}
		}

		return result;
	}

	/**
	 * 4.1 判断两个项集合是否可执行连接操作，由k-1项连接成k项
	 * 
	 * @param s1
	 * @param s2
	 * @return
	 */
	public boolean isCanLink(String[] s1, String[] s2) {
		boolean flag = true;
		if (s1.length == s2.length) {
			for (int i = 0; i < s1.length - 1; i++) {
				if (!s1[i].equals(s2[i])) {
					flag = false;
					break;
				}
			}
			if (s1[s1.length - 1].equals(s2[s2.length - 1])) {
				flag = false;
			}
		} else {
			flag = false;
		}

		return flag;
	}

	/**
	 * 4.2 把项字符串转为项的集合
	 * 
	 * @param str
	 * @return
	 */
	public Set<String> strToSet(String str) {
		Set<String> itemSet = new TreeSet<String>();
		String[] strs = str.split(" ");
		for (String s : strs) {
			itemSet.add(s);
		}

		return itemSet;
	}

	/**
	 * 4.3 判断set的所有k-1项子集是否都在setList，如果不全在，如果不在该k项集将被cut掉
	 * 
	 * @param setList
	 * @param set
	 * @return
	 */
	public boolean isNeedCut(List<Set<String>> setList, Set<String> set) {
		boolean flag = false;
		List<Set<String>> subSets = getSubset(set); // 获得k项集的所有k-1项集
		for (Set<String> subSet : subSets) {
			// 判断当前的k-1项集set是否在频繁k-1项集中出现，如出现，则不需要cut
			// 若没有出现，则需要被cut
			if (!isContained(setList, subSet)) {
				flag = true;
				break;
			}
		}
		return flag;
	}

	/**
	 * 4.3.1 获得k项集的所有k-1项集
	 * 
	 * @param set
	 * @return
	 */
	List<Set<String>> getSubset(Set<String> set) {

		List<Set<String>> result = new ArrayList<Set<String>>();
		String[] setArr = set.toArray(new String[0]);
		for (int i = 0; i < setArr.length; i++) {
			Set<String> subSet = new TreeSet<String>();
			for (int j = 0; j < setArr.length; j++) {
				if (i != j) {
					subSet.add((String) setArr[j]);
				}
			}
			result.add(subSet);
		}
		return result;
	}

	/**
	 * 4.3.2 判断k项集的某k-1项集是否包含在频繁k-1项集列表中
	 * 
	 * @param setList
	 * @param set
	 * @return
	 */
	boolean isContained(List<Set<String>> setList, Set<String> set) {

		boolean flag = false;
		int position = 0;
		for (Set<String> s : setList) {

			String[] sArr = s.toArray(new String[0]);
			String[] setArr = set.toArray(new String[0]);
			for (int i = 0; i < sArr.length; i++) {
				if (sArr[i].equals(setArr[i])) { // 如果对应位置的元素相同，则position为当前位置的值
					position = i;
				} else {
					break;
				}
			}
			// 如果position等于了数组的长度，说明已找到某个setList中的集合与
			// set集合相同了，退出循环，返回包含
			// 否则，把position置为0进入下一个比较
			if (position == sArr.length - 1) {
				flag = true;
				break;
			} else {
				flag = false;
				position = 0;
			}

		}
		return flag;
	}

	/**
	 * 4.4 求两个集合的交集
	 * 
	 * @param s1
	 * @param s2
	 * @return
	 */
	public Set<String> buildIntersection(Set<String> s1, Set<String> s2) {
		Map<String, Integer> itemMap = new HashMap<String, Integer>();
		Set<String> result = new HashSet<String>();
		for (String str : s1) {
			itemMap.put(str, 1);
		}
		for (String str : s2) {
			if (itemMap.get(str) != null && itemMap.get(str) == 1) {
				result.add(str);
			}
		}
		return result;
	}

	/**
	 * 输出垂直数据格式
	 */
	public void printVItemSet(Map<String, Set<String>> itemSetMap) {
		Set<String> itemSet = itemSetMap.keySet();
		Set<String> trans;
		for (String item : itemSet) {
			System.out.print(item + ": ");
			trans = itemSetMap.get(item);
			for (String tran : trans) {
				System.out.print(tran + ", ");
			}
			System.out.println();
		}
	}

	/**
	 * 输出频繁项集
	 * 
	 * @param items
	 * @param i
	 */
	public void printItemSet(Set<String> items, int i) {
		System.out.print("频繁" + i + "项集： 共" + items.size() + "项：");
		for (String item : items) {
			System.out.print("{" + item + "}, ");
		}
		System.out.println();
	}

	public void setMinSup(int minSup) {
		this.minSup = minSup;
	}

}