Apriori算法的java实现，apriori算法java

介绍

Apriori算法是一个经典的数据挖掘算法，Apriori的单词的意思是"先验的"，说明这个算法是具有先验性质的，就是说要通过上一次的结果推导出下一次的结果，这个如何体现将会在下面的分析中会慢慢的体现出来。Apriori算法的用处是挖掘频繁项集的，频繁项集粗俗的理解就是找出经常出现的组合，然后根据这些组合最终推出我们的关联规则。

Apriori算法原理

Apriori算法是一种逐层搜索的迭代式算法，其中k项集用于挖掘(k+1)项集，这是依靠他的先验性质的：

频繁项集的所有非空子集一定是也是频繁的。

通过这个性质可以对候选集进行剪枝。用k项集如何生成(k+1)项集呢，这个是算法里面最难也是最核心的部分。

通过2个步骤

1、连接步，将频繁项自己与自己进行连接运算。

2、剪枝步，去除候选集项中的不符合要求的候选项，不符合要求指的是这个候选项的子集并非都是频繁项，要遵守上文提到的先验性质。

3、通过1,2步骤还不够，在后面还要根据支持度计数筛选掉不满足最小支持度数的候选集。

算法的代码实现如下：

package com.gdut.mahao;


import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class Apriori {

	private final static int SUPPORT = 2; // 支持度阈值
	private final static double CONFIDENCE = 0.7; // 置信度阈值

	private final static String ITEM_SPLIT = ","; // 项之间的分隔符
	private final static String CON = "-->"; // 项之间的分隔符

	private final static List<String> transList = new ArrayList<String>(); // 所有交易

	static {// 初始化交易记录，在apriori算法中，应保证项集中的项是有序的
		transList.add("1,2,5,");
		transList.add("2,4,");
		transList.add("2,3,");
		transList.add("1,2,4,");
		transList.add("1,3,");
		transList.add("2,3,");
		transList.add("1,3,");
		transList.add("1,2,3,5,");
		transList.add("1,2,3,");
	}

	public Map<String, Integer> getFC() {
		Map<String, Integer> frequentCollectionMap = new HashMap<String, Integer>();// 所有的频繁集

		frequentCollectionMap.putAll(getItem1FC());

		Map<String, Integer> itemkFcMap = new HashMap<String, Integer>();
		itemkFcMap.putAll(getItem1FC());
		while (itemkFcMap != null && itemkFcMap.size() != 0) {
			Map<String, Integer> candidateCollection = getCandidateCollection(itemkFcMap);
			Set<String> ccKeySet = candidateCollection.keySet();
			// 对候选集项进行累加计数
			for (String trans : transList) {
				for (String candidate : ccKeySet) {
					boolean flag = true;// 用来判断交易中是否出现该候选项，如果出现，计数加1
					String[] candidateItems = candidate.split(ITEM_SPLIT);
					for (String candidateItem : candidateItems) {
						if (trans.indexOf(candidateItem + ITEM_SPLIT) == -1) {
							flag = false;
							break;
						}
					}
					if (flag) {
						Integer count = candidateCollection.get(candidate);
						candidateCollection.put(candidate, count + 1);
					}
				}
			}

			// 从候选集中找到符合支持度的频繁集项
			itemkFcMap.clear();
			for (String candidate : ccKeySet) {
				Integer count = candidateCollection.get(candidate);
				if (count >= SUPPORT) {
					itemkFcMap.put(candidate, count);
				}
			}
			// 合并所有频繁集
			frequentCollectionMap.putAll(itemkFcMap);
		}
		return frequentCollectionMap;
	}

	private Map<String, Integer> getCandidateCollection(
			Map<String, Integer> itemkFcMap) {
		Map<String, Integer> candidateCollection = new HashMap<String, Integer>();
		Set<String> itemkSet1 = itemkFcMap.keySet();
		Set<String> itemkSet2 = itemkFcMap.keySet();

		for (String itemk1 : itemkSet1) {
			for (String itemk2 : itemkSet2) {
				// 进行连接
				String[] tmp1 = itemk1.split(ITEM_SPLIT);
				String[] tmp2 = itemk2.split(ITEM_SPLIT);

				String c = "";
				if (tmp1.length == 1) {//itemkFcMap存放的是候选1项集集合时
					if (tmp1[0].compareTo(tmp2[0]) < 0) {
						c = tmp1[0] + ITEM_SPLIT + tmp2[0] + ITEM_SPLIT;
					}
				} else {
					boolean flag = true;//是否可以进行连接
					for (int i = 0; i < tmp1.length - 1; i++) {
						if (!tmp1[i].equals(tmp2[i])) {
							flag = false;
							break;
						}
					}
					if (flag && (tmp1[tmp1.length - 1].compareTo(tmp2[tmp2.length - 1]) < 0)) {
						c = itemk1 + tmp2[tmp2.length - 1] + ITEM_SPLIT;
					}
				}
				// 进行剪枝
				boolean hasInfrequentSubSet = false;/