Apriori算法及java实现

《Apriori算法及java实现》由会员分享，可在线阅读，更多相关《Apriori算法及java实现（17页珍藏版）》请在装配图网上搜索。

1、1 Apriori 介绍Apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k项集用于探索（k+1）项集。首先，通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做Li,然后利用Li找频繁2项集的集合L2，L2找L3,如此下去，直到不能再找到任何频繁 k项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。其中，Apriori算法具有这样一条 性质：任一频繁项集的所有非空子集也必须是频繁的。 因为假如P（l）最小支持度阈值，当有元素A添加到I中时，结果项集（A n I）不可能比I出现次数更多。因此 A nI也不是频繁的。2连接步和剪枝步在上述的关联规则

2、挖掘过程的两个步骤中，第一步往往是总体性能的瓶颈。Apriori算法采用连接步和剪枝步两种方式来找出所有的频繁项集。1）连接步为找出Lk （所有的频繁k项集的集合），通过将Lk-i （所有的频繁k-1项集的集合）与自身连接产生候选k项集的集合。候选集合记作Ck。设li和12是Lk-i中的成员。记1酉表示h中的第j项。假设Apriori算法对事务或项集中的项按字典次序排序，即对于（k-i）项集li,liil i2 Vik-i。将 Lk-i 与自身连接，如果（1ii=1 2i）&（ 1 i2=122）& &（lik-2=l 2k-2）&（l ik-i=min_supRetur n L=所有的频繁集

3、；Procedure apriori_gen (Lk-1:frequent(k-1)-itemsets)For each 项集 11 属于 Lk-1For each项集b属于lf(l 11=l 21)&( l 12=l 22)& & (l 1k-2=l 2k-2)&(l 1k-1B)=P(B|A)=support_cou nt(AB)/support_cou nt(A)关联规则产生步骤如下：1) 对于每个频繁项集I，产生其所有非空真子集；2) 对于每个非空真子集 s,如果 support_count(l)/support_count(s)=min_conf，则输 出s-(l-s)，其中，min

4、_conf是最小置信度阈值。例如，在上述例子中，针对频繁集I1，I2 ,15。可以产生哪些关联规则？该频繁集的非空真子集有I1，I2，I1，I5，I2，I5，I1 ，I2和I5，对应置信度如下:I1& 12-15con fide nce=2/4=50%I1& 15-12con fide nce=2/2=100%I2& 15-11con fide nce=2/2=100%I1 -I2& 15con fide nce=2/6=33%I2 -I1 &I5con fide nce=2/7=29%I5 -I1 &I2co nfide nce=2/2=100%如果 min_conf=70%,则强规则有 I

5、1& 15-12 ，I2& 15-11 ，I5 -I1 & 12。5. Apriori 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 stat

6、ic double CONFIDENCE = 0.7; / 置信度阈值private final static String ITEM_SPLIT=; /项之间的分隔符private final static String CON=-; /项之间的分隔符private final static List transList=new ArrayList(); /所有交易static/初始化交易记录transList.add(1;2;5;);transList.add(2;4;);transList.add(2;3;);transList.add(1;2;4;);transList.add(1;3

7、;);transList.add(2;3;);transList.add(1;3;);transList.add(1;2;3;5;);transList.add(1;2;3;);public Map getFC()Map frequentCollectionMap=new HashMap();所有的频繁集frequentCollectionMap.putAII(getltem1FC();Map itemkFcMap=new HashMap();itemkFcMap.putAII(getltem 1FC();while(itemkFcMap!=null&itemkFcMap.size()!=O)

8、Map candidateCollection=getCandidateCollection(itemkFcMap);Set ccKeySet=candidateCollection.keySet();/对候选集项进行累加计数for(String trans:transList)for(String candidate:ccKeySet)boolean flag=true;用来判断交易中是否出现该候选项，如果出现，计数加 1String candidateltems=candidate.split(ITEM_SPLIT);for(String candidateltem:candidatelt

9、ems)if(trans.indexOf(candidateltem+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

10、)itemkFcMap.put(candidate, count);/合并所有频繁集frequentCollectionMap.putAII(itemkFcMap);return frequentCollectionMap;private Map getCandidateCollection(Map itemkFcMap)Map candidateCollection=new HashMap();Set itemkSet 1=itemkFcMap.keySet();Set itemkSet2=itemkFcMap.keySet();for(String itemk1:itemkSet1)for

11、(String itemk2:itemkSet2)/进行连接String tmp1=itemk1.split(ITEM_SPLIT);String tmp2=itemk2.split(ITEM_SPLI T);String c=;if(tmp1.length=1)if(pareTo(tmp20)0) c=tmp10+ITEM_SPLIT+tmp20+ITEM_SPLIT;elseboolean flag=true;for(int i=O;itmp1.length-1;i+)if(!tmp1i.equals(tmp2i)flag=false;break;if(flag&(tmp1tmp1.len

12、gth-pareTo(tmp2tmp2.length-1)0) c=itemk1+tmp2tmp2.length-1+ITEM_SP LIT;/进行剪枝boolean hasInfrequentSubSet = false;if (!c.equals() String tmpC = c.split(ITEM_SPLIT);for (int i = 0; i tmpC .l ength; i+) String subC =;for (int j = 0; j tmpC .l ength; j+) if (i != j) subC = subC+tmpCj+ITEM_SP LIT;if (item

13、kFcMap.get(subC) = null) hasInfrequentSubSet = true; break;elsehaslnfrequentSubSet=true;if(!haslnfrequentSubSet)candidateCollection.put(c, 0);return candidatecollection;private Map getltem1FC()Map sltem1FcMap=new HashMap();Map rltem1FcMap=new HashMap(); 频繁 1 项集for(String trans:transList)String items

14、=trans.split(ITEM_SPLIT);for(String item:items)Integer count=sltem1FcMap.get(item+ITEM_SPLIT); if(count=null) sltem1FcMap.put(item+ITEM_SPLIT, 1);elsesltem1FcMap.put(item+ITEM_SPLIT, count+1);Set keySet=sltem1FcMap.keySet(); for(String key:keySet)Integer count=sltem1FcMap.get(key); if(count=SUPPORT)

15、 rltem1FcMap.put(key, count);return rItem1FcMap;public Map getRelationRules(Map frequentCollectionMap)Map relationRules=new HashMap();Set keySet=frequentCollectionMap.keySet();for (String key : keySet) double countAII=frequentCollectionMap.get(key);String keyItems = key.split(ITEM_SPLIT);if(keyltems

16、 .l ength1)List source=new ArrayList();Collections.addAII(source, keyItems);ListList result=new ArrayListList(); buildSubSet(source,result); 获得 source 的所有非空子集 for(List itemList:result)if(itemList.size()source.size() 只处理真子集List otherList=new ArrayList();for(String sourceltem:source)if(!itemList.conta

17、ins(sourceltem)otherList.add(sourceltem);String reasonStr=; 前置String resultStr=; 结果for(String item:itemList)reasonStr=reasonSt 叶item+ITEM_SPLIT;for(String item:otherList)resultStr=resultStr+item+ITEM_SPLIT;double countReason=frequentCollectionMap.get(reasonStr);double itemConfidence=countAII/countRe

18、ason; 计算置信度if(itemConfidence=CONFIDENCE)String ruIe=reasonSt 叶CON+resultStr;relationRules.put(rule, itemConfidence);return relationRules;private void buildSubSet(List sourceSet, ListList result) /仅有一个元素时，递归终止。此时非空子集仅为其自身，所以直接添加到result中if (sourceSet.size() = 1) List set = new ArrayList();set.add(sour

19、ceSet.get(O);result.add(set); else if (sourceSet.size() 1) /当有n个元素时，递归求出前n-1个子集，在于result中buildSubSet(sourceSet.subList(O, sourceSet.size() - 1), result);int size = result.size();/求出此时result的长度，用于后面的追加第n个元素时计数/把第n个元素加入到集合中List single = new ArrayList();single.add(sourceSet.get(sourceSet.size() - 1);re

20、sult.add(single);/在保留前面的n-1子集的情况下，把第n个元素分别加到前n个子集中，并把新的集加入到result中；/为保留原有n-1的子集，所以需要先对其进行复制List clone;for (int i = 0; i size; i+) clone = new ArrayList();for (String str : result.get(i) clone.add(str);clone.add(sourceSet.get(sourceSet.size() - 1);result.add(clone);Apriori apriori=new Apriori();Map f

21、requentCollectionMap=apriori.getFC();System.out.println(”频繁集+);Set fcKeySet=frequentCollectionMap.keySet(); for(String fcKey:fcKeySet)System.out.println(fcKey+ : +frequentCollectionMap.get(fcKey);Map relationRulesMap=apriori.getRelationRules(frequentCollectionMap);System.out.println(-关联规则+);Set rrKeySet=relationRulesMap.keySet();for(String rrKey:rrKeySet)System.out.println(rrKey+ : +relationRulesMap.get(rrKey);