算法描述

（1）掃描全部數據，產生候選1-項集的集合C1；
（2）根據最小支持度，由候選1-項集的集合C1產生頻繁1-項集的集合L1；
（3）對k>1，重復執行步驟（4）、（5）、（6）；
（4）由Lk執行連接和剪枝操作，產生候選（k+l）-項集的集合Ck+1；
（5）根據最小支持度，由候選（k+l）-項集的集合Ck+1，產生頻繁（k+1）-項集的集合Lk+1；
（6）若L≠Φ，則k=k+1，跳往步驟（4）；否則，跳往步驟（7）；
（7）根據最小置信度，由頻繁項集產生強關聯規則，結束。

代碼

public class Apriori2
{private final static int SUPPORT = 8; // 支持度閾值private final static double CONFIDENCE = 0.6; // 置信度閾值private final static String ITEM_SPLIT = " "; // 項之間的分隔符private final static String CON = "->"; // 項之間的分隔符/*** 算法主程序* @param dataList* @return Map<String, Integer>*/public Map<String, Integer> apriori(ArrayList<String> dataList){Map<String, Integer> stepFrequentSetMap = new HashMap<>(findFrequentOneSets(dataList));//找出候選// 1-項集//頻繁項集Map<String, Integer> frequentSetMap = new HashMap<String, Integer>(stepFrequentSetMap);while(stepFrequentSetMap.size() > 0)//上一步的頻繁項集不為空{Map<String, Integer> candidateSetMap = aprioriGen(stepFrequentSetMap);//生成候選集Set<String> candidateKeySet = candidateSetMap.keySet();//掃描D，進行計數，計算候選集的支持度計數for(String data:dataList){for(String candidate:candidateKeySet){boolean flag = true;String[] strings = candidate.split(ITEM_SPLIT);for(String string:strings){if(!data.contains(string + ITEM_SPLIT))//找不出候選項集中的元素，退出{flag = false;break;}}if(flag)candidateSetMap.put(candidate, candidateSetMap.get(candidate)+1);//支持度加一}}//從候選集中找到符合支持度的頻繁項集stepFrequentSetMap.clear();for(String candidate:candidateKeySet){Integer count = candidateSetMap.get(candidate);if(count>=SUPPORT)stepFrequentSetMap.put(candidate, count);}// 合并所有頻繁集frequentSetMap.putAll(stepFrequentSetMap);}return frequentSetMap;}/*** 找出候選K-項集* @param dataList* @return Map<String, Integer>*/private Map<String, Integer> findFrequentOneSets(ArrayList<String> dataList){Map<String, Integer> resultSetMap = new HashMap<>();for(String data:dataList){String[] strings = data.split(ITEM_SPLIT);for(String string:strings){string += ITEM_SPLIT;if(resultSetMap.get(string)==null){resultSetMap.put(string, 1);}else {resultSetMap.put(string, resultSetMap.get(string)+1);}}}return resultSetMap;}/*** 根據上一步的頻繁項集的集合選出候選集* @param setMap* @return*/private Map<String, Integer> aprioriGen(Map<String, Integer> setMap){Map<String, Integer> candidateSetMap = new HashMap<>();Set<String> candidateSet = setMap.keySet();for(String s1:candidateSet){String[] strings1 = s1.split(ITEM_SPLIT);String s1String = "";for(String temp:strings1)s1String += temp+ITEM_SPLIT;for(String s2:candidateSet){String[] strings2 = s2.split(ITEM_SPLIT);boolean flag = true;for(int i=0;i<strings1.length-1;i++){if(strings1[i].compareTo(strings2[i])!=0)//存在不同元素，不能連接{flag = false;break;}}if(flag && strings1[strings1.length-1].compareTo(strings2[strings1.length-1])<0){//連接步：產生候選String c = s1String+strings2[strings2.length-1]+ITEM_SPLIT;if(hasInfrequentSubset(c, setMap)){//剪枝步：刪除非頻繁的候選}else {candidateSetMap.put(c, 0);}}}}return candidateSetMap;}/*** 使用先驗知識，判斷候選集是否是頻繁項集* @param candidateSet* @param setMap* @return boolean*/private boolean hasInfrequentSubset(String candidateSet, Map<String, Integer> setMap){String[] strings = candidateSet.split(ITEM_SPLIT);//候選集//找出候選集所有的子集，并判斷每個子集是否屬于頻繁子集for(int i=0;i<strings.length;i++){String subString = "";for(int j=0;j<strings.length;j++)//遍歷所有子集{if(j!=i){subString += strings[j]+ITEM_SPLIT;}}if(setMap.get(subString)==null)return true;}return false;}/*** 由頻繁項集產生關聯規則* @param frequentSetMap* @return*/public Map<String, Double> getRelationRules(Map<String, Integer> frequentSetMap){Map<String, Double> relationsMap = new HashMap<>();Set<String> keySet = frequentSetMap.keySet();for(String key:keySet)//遍歷所有頻繁項集{List<String> keySubset = subset(key);//頻繁項的所有子集for(String keySubsetItem:keySubset)//遍歷所有子集{//子集keySubsetItem也是頻繁項Integer count = frequentSetMap.get(keySubsetItem);if(count!=null)//計算置信度{Double confidence = (1.0*frequentSetMap.get(key))/(1.0*frequentSetMap.get(keySubsetItem));if(confidence>CONFIDENCE)relationsMap.put(keySubsetItem+CON+expect(key, keySubsetItem), confidence);}}}return relationsMap;}/*** 求一個集合所有的非空真子集** @param sourceSet* @return* 為了以后可以用在其他地方，這里我們不是用遞歸的方法** 參考：http://blog.163.com/xiaohui_1123@126/blog/static/3980524020109784356915/* 思路：假設集合S（A,B,C,D），其大小為4，擁有2的4次方個子集，即0-15，二進制表示為0000，0001，...，1111。* 對應的子集為空集，{D}，...，{A,B,C,D}。*/private List<String> subset(String sourceSet){List<String> result = new ArrayList<>();String[] strings = sourceSet.split(ITEM_SPLIT);//非空真子集for(int i=1;i<(int)(Math.pow(2, strings.length))-1;i++){String item = "";String flag = "";int ii=i;do{flag += ""+ii%2;ii = ii/2;} while (ii>0);for(int j=flag.length()-1;j>=0;j--){if(flag.charAt(j)=='1'){item = strings[j]+ITEM_SPLIT+item;}}result.add(item);}return result;}/*** 集合運算，A/B* @param A* @param B* @return*/private String expect(String stringA,String stringB){String result = "";String[] stringAs = stringA.split(ITEM_SPLIT);String[] stringBs = stringB.split(ITEM_SPLIT);for(int i=0;i<stringAs.length;i++){boolean flag = true;for(int j=0;j<stringBs.length;j++){if(stringAs[i].compareTo(stringBs[j])==0){flag = false;break;}}if(flag)result += stringAs[i]+ITEM_SPLIT;}return result;}public static void readTxt(String fileName){try { // 防止文件建立或讀取失敗，用catch捕捉錯誤并打印，也可以throw/* 讀入TXT文件 */File filename = new File(fileName); // 要讀取以上路徑的input。txt文件InputStreamReader reader = new InputStreamReader(new FileInputStream(filename)); // 建立一個輸入流對象readerBufferedReader br = new BufferedReader(reader); // 建立一個對象，它把文件內容轉成計算機能讀懂的語言String line = "";line = br.readLine();while (line != null) {dataList.add(line);line = br.readLine();}} catch (Exception e) {e.printStackTrace();}}public static ArrayList<String> dataList = new ArrayList<>();public static void main(String[] args){readTxt("test.txt");System.out.println("=數據集合==========");for(String string:dataList){System.out.println(string);}Apriori2 apriori2 = new Apriori2();System.out.println("=頻繁項集==========");Map<String, Integer> frequentSetMap = apriori2.apriori(dataList);Set<String> keySet = frequentSetMap.keySet();for(String key:keySet){System.out.println(key+" : "+frequentSetMap.get(key));}System.out.println("=關聯規則==========");Map<String, Double> relationRulesMap = apriori2.getRelationRules(frequentSetMap);Set<String> rrKeySet = relationRulesMap.keySet();for (String rrKey : rrKeySet){System.out.println(rrKey + "  :  " + relationRulesMap.get(rrKey));}}
}