数据仓库与数据挖掘课程APRIORI算法学习一简介Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。
而且算法已经被广泛的应用到商业、网络安全等各个领域。
它是一种最有影响的挖掘布尔关联规则频繁项集的算法。
其核心是基于两阶段频集思想的递推算法。
该关联规则在分类上属于单维、单层、布尔关联规则。
在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集[1]。
二基本思想该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。
然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。
然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。
一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。
为了生成所有频集，使用了递归的方法。
挖掘步骤：(1) 依据支持度[2]找出所有频繁项集(频度)。
(2) 依据置信度[3]产生关联规则(强度)。
三核心流程Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。
是基于这样的事实：算法使用频繁项集性质的先验知识。
Apriori使用一种称作逐层搜索的迭代方法，k-项集用于探索(k+1)-项集。
首先，找出频繁1-项集的集合。
该集合记作L1。
L1用于找频繁2-项集的集合L2，而L2用于找L3，如此下去，直到不能找到频繁k-项集。
找每个Lk需要一次数据库扫描。
这个算法的思路，简单的说就是如果集合I不是频繁项集，那么所有包含集T400T500T600T700T800T900I1,I2,I4I1,I3I2,I3I1,I3I1,I2,I3,I5I1,I2,I3算法的基本过程如下图：首先扫描所有事务，得到1-项集C1，根据支持度要求滤去不满足条件项集，得到频繁1-项集。
下面进行递归运算：已知频繁k-项集(频繁1-项集已知)，根据频繁k-项集中的项，连接得到所有可能的K+1_项，并进行剪枝（如果该k+1_项集的所有k项子集不都能满足支持度条件，那么该k+1_项集被剪掉），得到1+kC项集，然后滤去该1+kC项集中不满足支持度条件的项得到频繁k+1-项集。
如果得到的1k C 项集为空，则算法结束。
连接的方法：假设kL 项集中的所有项都是按照相同的顺序排列的，那么如果][i k L 和][j k L 中的前k-1项都是完全相同的，而第k 项不同，则][i k L 和][j k L 是可连接的。
比如2L 中的{I1,I2}和{I1,I3}就是可连接的，连接之后得到{I1,I2,I3}，但是{I1,I2}和{I2,I3}是不可连接的，否则将导致项集中出现重复项。
关于剪枝再举例说明一下，如在由2L 生成3L 的过程中，列举得到的3_项集包括{I1,I2,I3},{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}，但是由于{I3,I4}和{I4,I5}没有出现在2L 中，所以{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}被剪枝掉了。
简单的讲:发现频繁项集，过程为（1）扫描（2）计数（3）比较（4）产生频繁项集（5）连接、剪枝，产生候选项集。
重复步骤（1）~（5）直到不能发现更大的频集。
2、产生关联规则，过程为:根据前面提到的置信度的定义，关联规则的产生如下：（1）对于每个频繁项集L ，产生L 的所有非空子集； （2）对于L 的每个非空子集S ，如果 P （L ）/P （S ）≧min_conf 则输出规则“S àL-S ”注：L-S 表示在项集L 中除去S 子集的项集 伪代码 伪代码描述： // 找出频繁 1 项集L1 =find_frequent_1-itemsets(D);For(k=2;Lk-1 !=null;k++){// 产生候选，并剪枝Ck =apriori_gen(Lk-1 );// 扫描 D 进行候选计数For each 事务t in D{Ct =subset(Ck,t); // 得到 t 的子集 For each 候选 c 属于 Ct c.count++; }//返回候选项集中不小于最小支持度的项集Lk ={c 属于 Ck | c.count>=min_sup}}Return L= 所有的频繁集；第一步：连接（join）Procedure apriori_gen (Lk-1 :frequent(k-1)-itemsets)For each 项集l1 属于Lk-1For each 项集l2 属于Lk-1If( (l1 [1]=l2 [1])&&( l1 [2]=l2 [2])&& ……&& (l1 [k-2]=l2 [k-2])&&(l1 [k-1]<l2 [k-1]) )then{c = l1 连接l2 // 连接步：产生候选//若k-1项集中已经存在子集c则进行剪枝if has_infrequent_subset(c, Lk-1 ) thendelete c; // 剪枝步：删除非频繁候选else add c to Ck;}Return Ck;第二步：剪枝（prune） Procedure has_infrequent_sub (c:candidate k-itemset; Lk-1 :frequent(k-1)-itemsets) For each (k-1)-subset s of cIf s 不属于Lk-1 thenReturn true;Return false;四具体实例及代码实现交易ID 商品ID列表T100 I1，I2，I5T200 I2，I4T300 I2，I3T400 I1，I2，I4T500 I1，I3T600 I2，I3T700 I1，I3T800 I1，I2，I3，I5T900 I1，I2，I3上图为某商场的交易记录，共有9个事务，利用Apriori算法寻找所有的频繁项集的过程如下:详细介绍下候选3项集的集合C3的产生过程：从连接步，首先C3={{I1,I2,I3}，{I1,I2,I5}，{I1,I3,I5}，{I2,I3,I4}，{I2,I3,I5}，{I2,I4,I5}}（C3是由L2与自身连接产生）。
根据Apriori性质，频繁项集的所有子集也必须频繁的，可以确定有4个候选集{I1,I3,I5}，{I2,I3,I4}，{I2,I3,I5}，{I2,I4,I5}}不可能时频繁的，因为它们存在子集不属于频繁集，因此将它们从C3中删除。
注意，由于Apriori算法使用逐层搜索技术，给定候选k项集后，只需检查它们的（k-1）个子集是否频繁。
伪代码：L1=find_frequent_1-itemsets(D); // 找出所有频繁1项集For(k=2;Lk-1!=null;k++){Ck=apriori_gen(Lk-1); // 产生候选，并剪枝For each 事务t in D{ // 扫描D进行候选计数Ct =subset(Ck,t); // 得到t的子集For each 候选c 属于Ctc.count++;}Lk={c属于Ck | c.count>=min_sup}}Return L=所有的频繁集；Procedure apriori_gen(Lk-1:frequent(k-1)-itemsets)For each项集l1属于Lk-1For each项集l2属于Lk-1If((l1[1]=l2[1])&&( l1[2]=l2[2])&&……..&& (l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])) then{c=l1连接l2 //连接步：产生候选if has_infrequent_subset(c,Lk-1) thendelete c; //剪枝步：删除非频繁候选else add c to Ck;}Return Ck;Procedure has_infrequent_sub(c:candidate k-itemset; Lk-1:frequent(k-1)-itemsets) For each(k-1)-subset s of cIf s不属于Lk-1 thenReturn true;Return false;Java代码package com.apriori;import java.util.ArrayList;import java.util.Collections;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.Set;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{//初始化交易记录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;// 用来判断交易中是否出现该候选项，如果出现，计数加1String[] 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=newHashMap<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){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;if (!c.equals("")) {String[] tmpC =c.split(ITEM_SPLIT);for (int i = 0; i < tmpC.length; i++) {String subC = "";for (int j = 0; j < tmpC.length; j++) {if (i != j) {subC = subC+tmpC[j]+ITEM_SPLIT;}}if(itemkFcMap.get(subC) == null) {hasInfrequentSubSet = true;break;}}}else{hasInfrequentSubSet=true;}if(!hasInfrequentSubSet){candidateCollection.put(c, 0);}}}return candidateCollection;}private Map<String,Integer> getItem1FC(){Map<String,Integer> sItem1FcMap=newHashMap<String,Integer>();Map<String,Integer> rItem1FcMap=newHashMap<String,Integer>();//频繁1项集for(String trans:transList){String[] items=trans.split(ITEM_SPLIT);for(String item:items){Integercount=sItem1FcMap.get(item+ITEM_SPLIT);if(count==null){sItem1FcMap.put(item+ITEM_SPLIT, 1);}else{sItem1FcMap.put(item+ITEM_SPLIT, count+1);}}}Set<String> keySet=sItem1FcMap.keySet();for(String key:keySet){Integer count=sItem1FcMap.get(key);if(count>=SUPPORT){rItem1FcMap.put(key, count);}}return rItem1FcMap;}public Map<String,Double> getRelationRules(Map<String,Integer> frequentCollectionMap){Map<String,Double> relationRules=newHashMap<String,Double>();Set<String> keySet=frequentCollectionMap.keySet();for (String key : keySet) {double countAll=frequentCollectionMap.get(key);String[] keyItems = key.split(ITEM_SPLIT);if(keyItems.length>1){List<String> source=new ArrayList<String>();Collections.addAll(source, keyItems);List<List<String>> result=newArrayList<List<String>>();buildSubSet(source,result);//获得source的所有非空子集for(List<String> itemList:result){if(itemList.size()<source.size()){//只处理真子集List<String> otherList=new ArrayList<String>();for(String sourceItem:source){if(!itemList.contains(sourceItem)){otherList.add(sourceItem);}}String reasonStr="";//前置String resultStr="";//结果for(String item:itemList){reasonStr=reasonStr+item+ITEM_SPLIT;}for(String item:otherList){resultStr=resultStr+item+ITEM_SPLIT;}double countReason=frequentCollectionMap.get(reasonStr);double itemConfidence=countAll/countReason;//计算置信度if(itemConfidence>=CONFIDENCE){String rule=reasonStr+CON+resultStr;relationRules.put(rule, itemConfidence);}}}}}return relationRules;}private void buildSubSet(List<String> sourceSet, List<List<String>> result) {// 仅有一个元素时，递归终止。